1 //===--- LivePhysRegs.cpp - Live Physical Register Set --------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the LivePhysRegs utility for tracking liveness of
11 // physical registers across machine instructions in forward or backward order.
12 // A more detailed description can be found in the corresponding header file.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/CodeGen/LivePhysRegs.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/Support/Debug.h"
22 #include "llvm/Support/raw_ostream.h"
23 using namespace llvm;
24 
25 
26 /// \brief 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<unsigned, const MachineOperand*>> *Clobbers) {
32   SparseSet<unsigned>::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 /// Simulates liveness when stepping backwards over an instruction(bundle):
44 /// Remove Defs, add uses. This is the recommended way of calculating liveness.
45 void LivePhysRegs::stepBackward(const MachineInstr &MI) {
46   // Remove defined registers and regmask kills from the set.
47   for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
48     if (O->isReg()) {
49       if (!O->isDef())
50         continue;
51       unsigned Reg = O->getReg();
52       if (!TargetRegisterInfo::isPhysicalRegister(Reg))
53         continue;
54       removeReg(Reg);
55     } else if (O->isRegMask())
56       removeRegsInMask(*O, nullptr);
57   }
58 
59   // Add uses to the set.
60   for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
61     if (!O->isReg() || !O->readsReg())
62       continue;
63     unsigned Reg = O->getReg();
64     if (!TargetRegisterInfo::isPhysicalRegister(Reg))
65       continue;
66     addReg(Reg);
67   }
68 }
69 
70 /// Simulates liveness when stepping forward over an instruction(bundle): Remove
71 /// killed-uses, add defs. This is the not recommended way, because it depends
72 /// on accurate kill flags. If possible use stepBackward() instead of this
73 /// function.
74 void LivePhysRegs::stepForward(const MachineInstr &MI,
75         SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> &Clobbers) {
76   // Remove killed registers from the set.
77   for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
78     if (O->isReg()) {
79       unsigned Reg = O->getReg();
80       if (!TargetRegisterInfo::isPhysicalRegister(Reg))
81         continue;
82       if (O->isDef()) {
83         // Note, dead defs are still recorded.  The caller should decide how to
84         // handle them.
85         Clobbers.push_back(std::make_pair(Reg, &*O));
86       } else {
87         if (!O->isKill())
88           continue;
89         assert(O->isUse());
90         removeReg(Reg);
91       }
92     } else if (O->isRegMask())
93       removeRegsInMask(*O, &Clobbers);
94   }
95 
96   // Add defs to the set.
97   for (auto Reg : Clobbers) {
98     // Skip dead defs.  They shouldn't be added to the set.
99     if (Reg.second->isReg() && Reg.second->isDead())
100       continue;
101     addReg(Reg.first);
102   }
103 }
104 
105 /// Prin the currently live registers to OS.
106 void LivePhysRegs::print(raw_ostream &OS) const {
107   OS << "Live Registers:";
108   if (!TRI) {
109     OS << " (uninitialized)\n";
110     return;
111   }
112 
113   if (empty()) {
114     OS << " (empty)\n";
115     return;
116   }
117 
118   for (const_iterator I = begin(), E = end(); I != E; ++I)
119     OS << " " << PrintReg(*I, TRI);
120   OS << "\n";
121 }
122 
123 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
124 LLVM_DUMP_METHOD void LivePhysRegs::dump() const {
125   dbgs() << "  " << *this;
126 }
127 #endif
128 
129 bool LivePhysRegs::available(const MachineRegisterInfo &MRI,
130                              unsigned Reg) const {
131   if (LiveRegs.count(Reg))
132     return false;
133   if (MRI.isReserved(Reg))
134     return false;
135   for (MCRegAliasIterator R(Reg, TRI, false); R.isValid(); ++R) {
136     if (LiveRegs.count(*R))
137       return false;
138   }
139   return true;
140 }
141 
142 /// Add live-in registers of basic block \p MBB to \p LiveRegs.
143 void LivePhysRegs::addBlockLiveIns(const MachineBasicBlock &MBB) {
144   for (const auto &LI : MBB.liveins()) {
145     MCSubRegIndexIterator S(LI.PhysReg, TRI);
146     if (LI.LaneMask.all() || (LI.LaneMask.any() && !S.isValid())) {
147       addReg(LI.PhysReg);
148       continue;
149     }
150     for (; S.isValid(); ++S) {
151       unsigned SI = S.getSubRegIndex();
152       if ((LI.LaneMask & TRI->getSubRegIndexLaneMask(SI)).any())
153         addReg(S.getSubReg());
154     }
155   }
156 }
157 
158 /// Add pristine registers to the given \p LiveRegs. This function removes
159 /// actually saved callee save registers when \p InPrologueEpilogue is false.
160 static void addPristines(LivePhysRegs &LiveRegs, const MachineFunction &MF,
161                          const MachineFrameInfo &MFI,
162                          const TargetRegisterInfo &TRI) {
163   const MachineRegisterInfo &MRI = MF.getRegInfo();
164   for (const MCPhysReg *CSR = MRI.getCalleeSavedRegs(); CSR && *CSR;
165        ++CSR)
166     LiveRegs.addReg(*CSR);
167   for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
168     LiveRegs.removeReg(Info.getReg());
169 }
170 
171 void LivePhysRegs::addLiveOutsNoPristines(const MachineBasicBlock &MBB) {
172   // To get the live-outs we simply merge the live-ins of all successors.
173   for (const MachineBasicBlock *Succ : MBB.successors())
174     addBlockLiveIns(*Succ);
175 }
176 
177 void LivePhysRegs::addLiveOuts(const MachineBasicBlock &MBB) {
178   const MachineFunction &MF = *MBB.getParent();
179   const MachineFrameInfo &MFI = MF.getFrameInfo();
180   if (MFI.isCalleeSavedInfoValid()) {
181     if (MBB.isReturnBlock()) {
182       // The return block has no successors whose live-ins we could merge
183       // below. So instead we add the callee saved registers manually.
184       const MachineRegisterInfo &MRI = MF.getRegInfo();
185       for (const MCPhysReg *I = MRI.getCalleeSavedRegs(); *I; ++I)
186         addReg(*I);
187     } else {
188       addPristines(*this, MF, MFI, *TRI);
189     }
190   }
191 
192   addLiveOutsNoPristines(MBB);
193 }
194 
195 void LivePhysRegs::addLiveIns(const MachineBasicBlock &MBB) {
196   const MachineFunction &MF = *MBB.getParent();
197   const MachineFrameInfo &MFI = MF.getFrameInfo();
198   if (MFI.isCalleeSavedInfoValid())
199     addPristines(*this, MF, MFI, *TRI);
200   addBlockLiveIns(MBB);
201 }
202 
203 void llvm::computeLiveIns(LivePhysRegs &LiveRegs, const TargetRegisterInfo &TRI,
204                           MachineBasicBlock &MBB) {
205   assert(MBB.livein_empty());
206   LiveRegs.init(TRI);
207   LiveRegs.addLiveOutsNoPristines(MBB);
208   for (MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend()))
209     LiveRegs.stepBackward(MI);
210 
211   for (unsigned Reg : LiveRegs) {
212     // Skip the register if we are about to add one of its super registers.
213     bool ContainsSuperReg = false;
214     for (MCSuperRegIterator SReg(Reg, &TRI); SReg.isValid(); ++SReg) {
215       if (LiveRegs.contains(*SReg)) {
216         ContainsSuperReg = true;
217         break;
218       }
219     }
220     if (ContainsSuperReg)
221       continue;
222     MBB.addLiveIn(Reg);
223   }
224 }
225