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