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 /// Dumps the currently live registers to the debug output.
124 LLVM_DUMP_METHOD void LivePhysRegs::dump() const {
125 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
126   dbgs() << "  " << *this;
127 #endif
128 }
129 
130 bool LivePhysRegs::available(const MachineRegisterInfo &MRI,
131                              unsigned Reg) const {
132   if (LiveRegs.count(Reg))
133     return false;
134   if (MRI.isReserved(Reg))
135     return false;
136   for (MCRegAliasIterator R(Reg, TRI, false); R.isValid(); ++R) {
137     if (LiveRegs.count(*R))
138       return false;
139   }
140   return true;
141 }
142 
143 /// Add live-in registers of basic block \p MBB to \p LiveRegs.
144 void LivePhysRegs::addBlockLiveIns(const MachineBasicBlock &MBB) {
145   for (const auto &LI : MBB.liveins()) {
146     if (LI.LaneMask == ~0u) {
147       addReg(LI.PhysReg);
148       continue;
149     }
150     for (MCSubRegIndexIterator S(LI.PhysReg, TRI); S.isValid(); ++S)
151       if (LI.LaneMask & TRI->getSubRegIndexLaneMask(S.getSubRegIndex()))
152         addReg(S.getSubReg());
153   }
154 }
155 
156 /// Add pristine registers to the given \p LiveRegs. This function removes
157 /// actually saved callee save registers when \p InPrologueEpilogue is false.
158 static void addPristines(LivePhysRegs &LiveRegs, const MachineFunction &MF,
159                          const MachineFrameInfo &MFI,
160                          const TargetRegisterInfo &TRI) {
161   for (const MCPhysReg *CSR = TRI.getCalleeSavedRegs(&MF); CSR && *CSR; ++CSR)
162     LiveRegs.addReg(*CSR);
163   for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
164     LiveRegs.removeReg(Info.getReg());
165 }
166 
167 void LivePhysRegs::addLiveOutsNoPristines(const MachineBasicBlock &MBB) {
168   // To get the live-outs we simply merge the live-ins of all successors.
169   for (const MachineBasicBlock *Succ : MBB.successors())
170     addBlockLiveIns(*Succ);
171 }
172 
173 void LivePhysRegs::addLiveOuts(const MachineBasicBlock &MBB) {
174   const MachineFunction &MF = *MBB.getParent();
175   const MachineFrameInfo &MFI = MF.getFrameInfo();
176   if (MFI.isCalleeSavedInfoValid()) {
177     if (MBB.isReturnBlock()) {
178       // The return block has no successors whose live-ins we could merge
179       // below. So instead we add the callee saved registers manually.
180       for (const MCPhysReg *I = TRI->getCalleeSavedRegs(&MF); *I; ++I)
181         addReg(*I);
182     } else {
183       addPristines(*this, MF, MFI, *TRI);
184     }
185   }
186 
187   addLiveOutsNoPristines(MBB);
188 }
189 
190 void LivePhysRegs::addLiveIns(const MachineBasicBlock &MBB) {
191   const MachineFunction &MF = *MBB.getParent();
192   const MachineFrameInfo &MFI = MF.getFrameInfo();
193   if (MFI.isCalleeSavedInfoValid())
194     addPristines(*this, MF, MFI, *TRI);
195   addBlockLiveIns(MBB);
196 }
197