1 //===--- LivePhysRegs.cpp - Live Physical Register Set --------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the LivePhysRegs utility for tracking liveness of 10 // physical registers across machine instructions in forward or backward order. 11 // A more detailed description can be found in the corresponding header file. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "llvm/CodeGen/LivePhysRegs.h" 16 #include "llvm/CodeGen/MachineFrameInfo.h" 17 #include "llvm/CodeGen/MachineFunction.h" 18 #include "llvm/CodeGen/MachineInstrBundle.h" 19 #include "llvm/CodeGen/MachineRegisterInfo.h" 20 #include "llvm/Config/llvm-config.h" 21 #include "llvm/Support/Debug.h" 22 #include "llvm/Support/raw_ostream.h" 23 using namespace llvm; 24 25 26 /// Remove all registers from the set that get clobbered by the register 27 /// mask. 28 /// The clobbers set will be the list of live registers clobbered 29 /// by the regmask. 30 void LivePhysRegs::removeRegsInMask(const MachineOperand &MO, 31 SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> *Clobbers) { 32 RegisterSet::iterator LRI = LiveRegs.begin(); 33 while (LRI != LiveRegs.end()) { 34 if (MO.clobbersPhysReg(*LRI)) { 35 if (Clobbers) 36 Clobbers->push_back(std::make_pair(*LRI, &MO)); 37 LRI = LiveRegs.erase(LRI); 38 } else 39 ++LRI; 40 } 41 } 42 43 /// Remove defined registers and regmask kills from the set. 44 void LivePhysRegs::removeDefs(const MachineInstr &MI) { 45 for (ConstMIBundleOperands O(MI); O.isValid(); ++O) { 46 if (O->isReg()) { 47 if (!O->isDef() || O->isDebug()) 48 continue; 49 Register Reg = O->getReg(); 50 if (!Register::isPhysicalRegister(Reg)) 51 continue; 52 removeReg(Reg); 53 } else if (O->isRegMask()) 54 removeRegsInMask(*O); 55 } 56 } 57 58 /// Add uses to the set. 59 void LivePhysRegs::addUses(const MachineInstr &MI) { 60 for (ConstMIBundleOperands O(MI); O.isValid(); ++O) { 61 if (!O->isReg() || !O->readsReg() || O->isDebug()) 62 continue; 63 Register Reg = O->getReg(); 64 if (!Register::isPhysicalRegister(Reg)) 65 continue; 66 addReg(Reg); 67 } 68 } 69 70 /// Simulates liveness when stepping backwards over an instruction(bundle): 71 /// Remove Defs, add uses. This is the recommended way of calculating liveness. 72 void LivePhysRegs::stepBackward(const MachineInstr &MI) { 73 // Remove defined registers and regmask kills from the set. 74 removeDefs(MI); 75 76 // Add uses to the set. 77 addUses(MI); 78 } 79 80 /// Simulates liveness when stepping forward over an instruction(bundle): Remove 81 /// killed-uses, add defs. This is the not recommended way, because it depends 82 /// on accurate kill flags. If possible use stepBackward() instead of this 83 /// function. 84 void LivePhysRegs::stepForward(const MachineInstr &MI, 85 SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> &Clobbers) { 86 // Remove killed registers from the set. 87 for (ConstMIBundleOperands O(MI); O.isValid(); ++O) { 88 if (O->isReg() && !O->isDebug()) { 89 Register Reg = O->getReg(); 90 if (!Register::isPhysicalRegister(Reg)) 91 continue; 92 if (O->isDef()) { 93 // Note, dead defs are still recorded. The caller should decide how to 94 // handle them. 95 Clobbers.push_back(std::make_pair(Reg, &*O)); 96 } else { 97 if (!O->isKill()) 98 continue; 99 assert(O->isUse()); 100 removeReg(Reg); 101 } 102 } else if (O->isRegMask()) 103 removeRegsInMask(*O, &Clobbers); 104 } 105 106 // Add defs to the set. 107 for (auto Reg : Clobbers) { 108 // Skip dead defs and registers clobbered by regmasks. They shouldn't 109 // be added to the set. 110 if (Reg.second->isReg() && Reg.second->isDead()) 111 continue; 112 if (Reg.second->isRegMask() && 113 MachineOperand::clobbersPhysReg(Reg.second->getRegMask(), Reg.first)) 114 continue; 115 addReg(Reg.first); 116 } 117 } 118 119 /// Prin the currently live registers to OS. 120 void LivePhysRegs::print(raw_ostream &OS) const { 121 OS << "Live Registers:"; 122 if (!TRI) { 123 OS << " (uninitialized)\n"; 124 return; 125 } 126 127 if (empty()) { 128 OS << " (empty)\n"; 129 return; 130 } 131 132 for (const_iterator I = begin(), E = end(); I != E; ++I) 133 OS << " " << printReg(*I, TRI); 134 OS << "\n"; 135 } 136 137 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 138 LLVM_DUMP_METHOD void LivePhysRegs::dump() const { 139 dbgs() << " " << *this; 140 } 141 #endif 142 143 bool LivePhysRegs::available(const MachineRegisterInfo &MRI, 144 MCPhysReg Reg) const { 145 if (LiveRegs.count(Reg)) 146 return false; 147 if (MRI.isReserved(Reg)) 148 return false; 149 for (MCRegAliasIterator R(Reg, TRI, false); R.isValid(); ++R) { 150 if (LiveRegs.count(*R)) 151 return false; 152 } 153 return true; 154 } 155 156 /// Add live-in registers of basic block \p MBB to \p LiveRegs. 157 void LivePhysRegs::addBlockLiveIns(const MachineBasicBlock &MBB) { 158 for (const auto &LI : MBB.liveins()) { 159 MCPhysReg Reg = LI.PhysReg; 160 LaneBitmask Mask = LI.LaneMask; 161 MCSubRegIndexIterator S(Reg, TRI); 162 assert(Mask.any() && "Invalid livein mask"); 163 if (Mask.all() || !S.isValid()) { 164 addReg(Reg); 165 continue; 166 } 167 for (; S.isValid(); ++S) { 168 unsigned SI = S.getSubRegIndex(); 169 if ((Mask & TRI->getSubRegIndexLaneMask(SI)).any()) 170 addReg(S.getSubReg()); 171 } 172 } 173 } 174 175 /// Adds all callee saved registers to \p LiveRegs. 176 static void addCalleeSavedRegs(LivePhysRegs &LiveRegs, 177 const MachineFunction &MF) { 178 const MachineRegisterInfo &MRI = MF.getRegInfo(); 179 for (const MCPhysReg *CSR = MRI.getCalleeSavedRegs(); CSR && *CSR; ++CSR) 180 LiveRegs.addReg(*CSR); 181 } 182 183 void LivePhysRegs::addPristines(const MachineFunction &MF) { 184 const MachineFrameInfo &MFI = MF.getFrameInfo(); 185 if (!MFI.isCalleeSavedInfoValid()) 186 return; 187 /// This function will usually be called on an empty object, handle this 188 /// as a special case. 189 if (empty()) { 190 /// Add all callee saved regs, then remove the ones that are saved and 191 /// restored. 192 addCalleeSavedRegs(*this, MF); 193 /// Remove the ones that are not saved/restored; they are pristine. 194 for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo()) 195 removeReg(Info.getReg()); 196 return; 197 } 198 /// If a callee-saved register that is not pristine is already present 199 /// in the set, we should make sure that it stays in it. Precompute the 200 /// set of pristine registers in a separate object. 201 /// Add all callee saved regs, then remove the ones that are saved+restored. 202 LivePhysRegs Pristine(*TRI); 203 addCalleeSavedRegs(Pristine, MF); 204 /// Remove the ones that are not saved/restored; they are pristine. 205 for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo()) 206 Pristine.removeReg(Info.getReg()); 207 for (MCPhysReg R : Pristine) 208 addReg(R); 209 } 210 211 void LivePhysRegs::addLiveOutsNoPristines(const MachineBasicBlock &MBB) { 212 // To get the live-outs we simply merge the live-ins of all successors. 213 for (const MachineBasicBlock *Succ : MBB.successors()) 214 addBlockLiveIns(*Succ); 215 if (MBB.isReturnBlock()) { 216 // Return blocks are a special case because we currently don't mark up 217 // return instructions completely: specifically, there is no explicit 218 // use for callee-saved registers. So we add all callee saved registers 219 // that are saved and restored (somewhere). This does not include 220 // callee saved registers that are unused and hence not saved and 221 // restored; they are called pristine. 222 // FIXME: PEI should add explicit markings to return instructions 223 // instead of implicitly handling them here. 224 const MachineFunction &MF = *MBB.getParent(); 225 const MachineFrameInfo &MFI = MF.getFrameInfo(); 226 if (MFI.isCalleeSavedInfoValid()) { 227 for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo()) 228 if (Info.isRestored()) 229 addReg(Info.getReg()); 230 } 231 } 232 } 233 234 void LivePhysRegs::addLiveOuts(const MachineBasicBlock &MBB) { 235 const MachineFunction &MF = *MBB.getParent(); 236 addPristines(MF); 237 addLiveOutsNoPristines(MBB); 238 } 239 240 void LivePhysRegs::addLiveIns(const MachineBasicBlock &MBB) { 241 const MachineFunction &MF = *MBB.getParent(); 242 addPristines(MF); 243 addBlockLiveIns(MBB); 244 } 245 246 void llvm::computeLiveIns(LivePhysRegs &LiveRegs, 247 const MachineBasicBlock &MBB) { 248 const MachineFunction &MF = *MBB.getParent(); 249 const MachineRegisterInfo &MRI = MF.getRegInfo(); 250 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); 251 LiveRegs.init(TRI); 252 LiveRegs.addLiveOutsNoPristines(MBB); 253 for (const MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend())) 254 LiveRegs.stepBackward(MI); 255 } 256 257 void llvm::addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs) { 258 assert(MBB.livein_empty() && "Expected empty live-in list"); 259 const MachineFunction &MF = *MBB.getParent(); 260 const MachineRegisterInfo &MRI = MF.getRegInfo(); 261 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); 262 for (MCPhysReg Reg : LiveRegs) { 263 if (MRI.isReserved(Reg)) 264 continue; 265 // Skip the register if we are about to add one of its super registers. 266 bool ContainsSuperReg = false; 267 for (MCSuperRegIterator SReg(Reg, &TRI); SReg.isValid(); ++SReg) { 268 if (LiveRegs.contains(*SReg) && !MRI.isReserved(*SReg)) { 269 ContainsSuperReg = true; 270 break; 271 } 272 } 273 if (ContainsSuperReg) 274 continue; 275 MBB.addLiveIn(Reg); 276 } 277 } 278 279 void llvm::recomputeLivenessFlags(MachineBasicBlock &MBB) { 280 const MachineFunction &MF = *MBB.getParent(); 281 const MachineRegisterInfo &MRI = MF.getRegInfo(); 282 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); 283 284 // We walk through the block backwards and start with the live outs. 285 LivePhysRegs LiveRegs; 286 LiveRegs.init(TRI); 287 LiveRegs.addLiveOutsNoPristines(MBB); 288 289 for (MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend())) { 290 // Recompute dead flags. 291 for (MIBundleOperands MO(MI); MO.isValid(); ++MO) { 292 if (!MO->isReg() || !MO->isDef() || MO->isDebug()) 293 continue; 294 295 Register Reg = MO->getReg(); 296 if (Reg == 0) 297 continue; 298 assert(Register::isPhysicalRegister(Reg)); 299 300 bool IsNotLive = LiveRegs.available(MRI, Reg); 301 MO->setIsDead(IsNotLive); 302 } 303 304 // Step backward over defs. 305 LiveRegs.removeDefs(MI); 306 307 // Recompute kill flags. 308 for (MIBundleOperands MO(MI); MO.isValid(); ++MO) { 309 if (!MO->isReg() || !MO->readsReg() || MO->isDebug()) 310 continue; 311 312 Register Reg = MO->getReg(); 313 if (Reg == 0) 314 continue; 315 assert(Register::isPhysicalRegister(Reg)); 316 317 bool IsNotLive = LiveRegs.available(MRI, Reg); 318 MO->setIsKill(IsNotLive); 319 } 320 321 // Complete the stepbackward. 322 LiveRegs.addUses(MI); 323 } 324 } 325 326 void llvm::computeAndAddLiveIns(LivePhysRegs &LiveRegs, 327 MachineBasicBlock &MBB) { 328 computeLiveIns(LiveRegs, MBB); 329 addLiveIns(MBB, LiveRegs); 330 } 331