Track IR ordering of SelectionDAG nodes 3/4.
[oota-llvm.git] / lib / CodeGen / MachineRegisterInfo.cpp
1 //===-- lib/Codegen/MachineRegisterInfo.cpp -------------------------------===//
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 // Implementation of the MachineRegisterInfo class.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "llvm/CodeGen/MachineRegisterInfo.h"
15 #include "llvm/CodeGen/MachineInstrBuilder.h"
16 #include "llvm/Target/TargetInstrInfo.h"
17 #include "llvm/Target/TargetMachine.h"
18 #include "llvm/Support/raw_os_ostream.h"
19
20 using namespace llvm;
21
22 MachineRegisterInfo::MachineRegisterInfo(const TargetRegisterInfo &TRI)
23   : TRI(&TRI), IsSSA(true), TracksLiveness(true) {
24   VRegInfo.reserve(256);
25   RegAllocHints.reserve(256);
26   UsedRegUnits.resize(TRI.getNumRegUnits());
27   UsedPhysRegMask.resize(TRI.getNumRegs());
28
29   // Create the physreg use/def lists.
30   PhysRegUseDefLists = new MachineOperand*[TRI.getNumRegs()];
31   memset(PhysRegUseDefLists, 0, sizeof(MachineOperand*)*TRI.getNumRegs());
32 }
33
34 MachineRegisterInfo::~MachineRegisterInfo() {
35   delete [] PhysRegUseDefLists;
36 }
37
38 /// setRegClass - Set the register class of the specified virtual register.
39 ///
40 void
41 MachineRegisterInfo::setRegClass(unsigned Reg, const TargetRegisterClass *RC) {
42   assert(RC && RC->isAllocatable() && "Invalid RC for virtual register");
43   VRegInfo[Reg].first = RC;
44 }
45
46 const TargetRegisterClass *
47 MachineRegisterInfo::constrainRegClass(unsigned Reg,
48                                        const TargetRegisterClass *RC,
49                                        unsigned MinNumRegs) {
50   const TargetRegisterClass *OldRC = getRegClass(Reg);
51   if (OldRC == RC)
52     return RC;
53   const TargetRegisterClass *NewRC = TRI->getCommonSubClass(OldRC, RC);
54   if (!NewRC || NewRC == OldRC)
55     return NewRC;
56   if (NewRC->getNumRegs() < MinNumRegs)
57     return 0;
58   setRegClass(Reg, NewRC);
59   return NewRC;
60 }
61
62 bool
63 MachineRegisterInfo::recomputeRegClass(unsigned Reg, const TargetMachine &TM) {
64   const TargetInstrInfo *TII = TM.getInstrInfo();
65   const TargetRegisterClass *OldRC = getRegClass(Reg);
66   const TargetRegisterClass *NewRC = TRI->getLargestLegalSuperClass(OldRC);
67
68   // Stop early if there is no room to grow.
69   if (NewRC == OldRC)
70     return false;
71
72   // Accumulate constraints from all uses.
73   for (reg_nodbg_iterator I = reg_nodbg_begin(Reg), E = reg_nodbg_end(); I != E;
74        ++I) {
75     const TargetRegisterClass *OpRC =
76       I->getRegClassConstraint(I.getOperandNo(), TII, TRI);
77     if (unsigned SubIdx = I.getOperand().getSubReg()) {
78       if (OpRC)
79         NewRC = TRI->getMatchingSuperRegClass(NewRC, OpRC, SubIdx);
80       else
81         NewRC = TRI->getSubClassWithSubReg(NewRC, SubIdx);
82     } else if (OpRC)
83       NewRC = TRI->getCommonSubClass(NewRC, OpRC);
84     if (!NewRC || NewRC == OldRC)
85       return false;
86   }
87   setRegClass(Reg, NewRC);
88   return true;
89 }
90
91 /// createVirtualRegister - Create and return a new virtual register in the
92 /// function with the specified register class.
93 ///
94 unsigned
95 MachineRegisterInfo::createVirtualRegister(const TargetRegisterClass *RegClass){
96   assert(RegClass && "Cannot create register without RegClass!");
97   assert(RegClass->isAllocatable() &&
98          "Virtual register RegClass must be allocatable.");
99
100   // New virtual register number.
101   unsigned Reg = TargetRegisterInfo::index2VirtReg(getNumVirtRegs());
102   VRegInfo.grow(Reg);
103   VRegInfo[Reg].first = RegClass;
104   RegAllocHints.grow(Reg);
105   return Reg;
106 }
107
108 /// clearVirtRegs - Remove all virtual registers (after physreg assignment).
109 void MachineRegisterInfo::clearVirtRegs() {
110 #ifndef NDEBUG
111   for (unsigned i = 0, e = getNumVirtRegs(); i != e; ++i) {
112     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
113     if (!VRegInfo[Reg].second)
114       continue;
115     verifyUseList(Reg);
116     llvm_unreachable("Remaining virtual register operands");
117   }
118 #endif
119   VRegInfo.clear();
120 }
121
122 void MachineRegisterInfo::verifyUseList(unsigned Reg) const {
123 #ifndef NDEBUG
124   bool Valid = true;
125   for (reg_iterator I = reg_begin(Reg), E = reg_end(); I != E; ++I) {
126     MachineOperand *MO = &I.getOperand();
127     MachineInstr *MI = MO->getParent();
128     if (!MI) {
129       errs() << PrintReg(Reg, TRI) << " use list MachineOperand " << MO
130              << " has no parent instruction.\n";
131       Valid = false;
132     }
133     MachineOperand *MO0 = &MI->getOperand(0);
134     unsigned NumOps = MI->getNumOperands();
135     if (!(MO >= MO0 && MO < MO0+NumOps)) {
136       errs() << PrintReg(Reg, TRI) << " use list MachineOperand " << MO
137              << " doesn't belong to parent MI: " << *MI;
138       Valid = false;
139     }
140     if (!MO->isReg()) {
141       errs() << PrintReg(Reg, TRI) << " MachineOperand " << MO << ": " << *MO
142              << " is not a register\n";
143       Valid = false;
144     }
145     if (MO->getReg() != Reg) {
146       errs() << PrintReg(Reg, TRI) << " use-list MachineOperand " << MO << ": "
147              << *MO << " is the wrong register\n";
148       Valid = false;
149     }
150   }
151   assert(Valid && "Invalid use list");
152 #endif
153 }
154
155 void MachineRegisterInfo::verifyUseLists() const {
156 #ifndef NDEBUG
157   for (unsigned i = 0, e = getNumVirtRegs(); i != e; ++i)
158     verifyUseList(TargetRegisterInfo::index2VirtReg(i));
159   for (unsigned i = 1, e = TRI->getNumRegs(); i != e; ++i)
160     verifyUseList(i);
161 #endif
162 }
163
164 /// Add MO to the linked list of operands for its register.
165 void MachineRegisterInfo::addRegOperandToUseList(MachineOperand *MO) {
166   assert(!MO->isOnRegUseList() && "Already on list");
167   MachineOperand *&HeadRef = getRegUseDefListHead(MO->getReg());
168   MachineOperand *const Head = HeadRef;
169
170   // Head points to the first list element.
171   // Next is NULL on the last list element.
172   // Prev pointers are circular, so Head->Prev == Last.
173
174   // Head is NULL for an empty list.
175   if (!Head) {
176     MO->Contents.Reg.Prev = MO;
177     MO->Contents.Reg.Next = 0;
178     HeadRef = MO;
179     return;
180   }
181   assert(MO->getReg() == Head->getReg() && "Different regs on the same list!");
182
183   // Insert MO between Last and Head in the circular Prev chain.
184   MachineOperand *Last = Head->Contents.Reg.Prev;
185   assert(Last && "Inconsistent use list");
186   assert(MO->getReg() == Last->getReg() && "Different regs on the same list!");
187   Head->Contents.Reg.Prev = MO;
188   MO->Contents.Reg.Prev = Last;
189
190   // Def operands always precede uses. This allows def_iterator to stop early.
191   // Insert def operands at the front, and use operands at the back.
192   if (MO->isDef()) {
193     // Insert def at the front.
194     MO->Contents.Reg.Next = Head;
195     HeadRef = MO;
196   } else {
197     // Insert use at the end.
198     MO->Contents.Reg.Next = 0;
199     Last->Contents.Reg.Next = MO;
200   }
201 }
202
203 /// Remove MO from its use-def list.
204 void MachineRegisterInfo::removeRegOperandFromUseList(MachineOperand *MO) {
205   assert(MO->isOnRegUseList() && "Operand not on use list");
206   MachineOperand *&HeadRef = getRegUseDefListHead(MO->getReg());
207   MachineOperand *const Head = HeadRef;
208   assert(Head && "List already empty");
209
210   // Unlink this from the doubly linked list of operands.
211   MachineOperand *Next = MO->Contents.Reg.Next;
212   MachineOperand *Prev = MO->Contents.Reg.Prev;
213
214   // Prev links are circular, next link is NULL instead of looping back to Head.
215   if (MO == Head)
216     HeadRef = Next;
217   else
218     Prev->Contents.Reg.Next = Next;
219
220   (Next ? Next : Head)->Contents.Reg.Prev = Prev;
221
222   MO->Contents.Reg.Prev = 0;
223   MO->Contents.Reg.Next = 0;
224 }
225
226 /// Move NumOps operands from Src to Dst, updating use-def lists as needed.
227 ///
228 /// The Dst range is assumed to be uninitialized memory. (Or it may contain
229 /// operands that won't be destroyed, which is OK because the MO destructor is
230 /// trivial anyway).
231 ///
232 /// The Src and Dst ranges may overlap.
233 void MachineRegisterInfo::moveOperands(MachineOperand *Dst,
234                                        MachineOperand *Src,
235                                        unsigned NumOps) {
236   assert(Src != Dst && NumOps && "Noop moveOperands");
237
238   // Copy backwards if Dst is within the Src range.
239   int Stride = 1;
240   if (Dst >= Src && Dst < Src + NumOps) {
241     Stride = -1;
242     Dst += NumOps - 1;
243     Src += NumOps - 1;
244   }
245
246   // Copy one operand at a time.
247   do {
248     new (Dst) MachineOperand(*Src);
249
250     // Dst takes Src's place in the use-def chain.
251     if (Src->isReg()) {
252       MachineOperand *&Head = getRegUseDefListHead(Src->getReg());
253       MachineOperand *Prev = Src->Contents.Reg.Prev;
254       MachineOperand *Next = Src->Contents.Reg.Next;
255       assert(Head && "List empty, but operand is chained");
256       assert(Prev && "Operand was not on use-def list");
257
258       // Prev links are circular, next link is NULL instead of looping back to
259       // Head.
260       if (Src == Head)
261         Head = Dst;
262       else
263         Prev->Contents.Reg.Next = Dst;
264
265       // Update Prev pointer. This also works when Src was pointing to itself
266       // in a 1-element list. In that case Head == Dst.
267       (Next ? Next : Head)->Contents.Reg.Prev = Dst;
268     }
269
270     Dst += Stride;
271     Src += Stride;
272   } while (--NumOps);
273 }
274
275 /// replaceRegWith - Replace all instances of FromReg with ToReg in the
276 /// machine function.  This is like llvm-level X->replaceAllUsesWith(Y),
277 /// except that it also changes any definitions of the register as well.
278 void MachineRegisterInfo::replaceRegWith(unsigned FromReg, unsigned ToReg) {
279   assert(FromReg != ToReg && "Cannot replace a reg with itself");
280
281   // TODO: This could be more efficient by bulk changing the operands.
282   for (reg_iterator I = reg_begin(FromReg), E = reg_end(); I != E; ) {
283     MachineOperand &O = I.getOperand();
284     ++I;
285     O.setReg(ToReg);
286   }
287 }
288
289
290 /// getVRegDef - Return the machine instr that defines the specified virtual
291 /// register or null if none is found.  This assumes that the code is in SSA
292 /// form, so there should only be one definition.
293 MachineInstr *MachineRegisterInfo::getVRegDef(unsigned Reg) const {
294   // Since we are in SSA form, we can use the first definition.
295   def_iterator I = def_begin(Reg);
296   assert((I.atEnd() || llvm::next(I) == def_end()) &&
297          "getVRegDef assumes a single definition or no definition");
298   return !I.atEnd() ? &*I : 0;
299 }
300
301 /// getUniqueVRegDef - Return the unique machine instr that defines the
302 /// specified virtual register or null if none is found.  If there are
303 /// multiple definitions or no definition, return null.
304 MachineInstr *MachineRegisterInfo::getUniqueVRegDef(unsigned Reg) const {
305   if (def_empty(Reg)) return 0;
306   def_iterator I = def_begin(Reg);
307   if (llvm::next(I) != def_end())
308     return 0;
309   return &*I;
310 }
311
312 bool MachineRegisterInfo::hasOneNonDBGUse(unsigned RegNo) const {
313   use_nodbg_iterator UI = use_nodbg_begin(RegNo);
314   if (UI == use_nodbg_end())
315     return false;
316   return ++UI == use_nodbg_end();
317 }
318
319 /// clearKillFlags - Iterate over all the uses of the given register and
320 /// clear the kill flag from the MachineOperand. This function is used by
321 /// optimization passes which extend register lifetimes and need only
322 /// preserve conservative kill flag information.
323 void MachineRegisterInfo::clearKillFlags(unsigned Reg) const {
324   for (use_iterator UI = use_begin(Reg), UE = use_end(); UI != UE; ++UI)
325     UI.getOperand().setIsKill(false);
326 }
327
328 bool MachineRegisterInfo::isLiveIn(unsigned Reg) const {
329   for (livein_iterator I = livein_begin(), E = livein_end(); I != E; ++I)
330     if (I->first == Reg || I->second == Reg)
331       return true;
332   return false;
333 }
334
335 /// getLiveInPhysReg - If VReg is a live-in virtual register, return the
336 /// corresponding live-in physical register.
337 unsigned MachineRegisterInfo::getLiveInPhysReg(unsigned VReg) const {
338   for (livein_iterator I = livein_begin(), E = livein_end(); I != E; ++I)
339     if (I->second == VReg)
340       return I->first;
341   return 0;
342 }
343
344 /// getLiveInVirtReg - If PReg is a live-in physical register, return the
345 /// corresponding live-in physical register.
346 unsigned MachineRegisterInfo::getLiveInVirtReg(unsigned PReg) const {
347   for (livein_iterator I = livein_begin(), E = livein_end(); I != E; ++I)
348     if (I->first == PReg)
349       return I->second;
350   return 0;
351 }
352
353 /// EmitLiveInCopies - Emit copies to initialize livein virtual registers
354 /// into the given entry block.
355 void
356 MachineRegisterInfo::EmitLiveInCopies(MachineBasicBlock *EntryMBB,
357                                       const TargetRegisterInfo &TRI,
358                                       const TargetInstrInfo &TII) {
359   // Emit the copies into the top of the block.
360   for (unsigned i = 0, e = LiveIns.size(); i != e; ++i)
361     if (LiveIns[i].second) {
362       if (use_empty(LiveIns[i].second)) {
363         // The livein has no uses. Drop it.
364         //
365         // It would be preferable to have isel avoid creating live-in
366         // records for unused arguments in the first place, but it's
367         // complicated by the debug info code for arguments.
368         LiveIns.erase(LiveIns.begin() + i);
369         --i; --e;
370       } else {
371         // Emit a copy.
372         BuildMI(*EntryMBB, EntryMBB->begin(), DebugLoc(),
373                 TII.get(TargetOpcode::COPY), LiveIns[i].second)
374           .addReg(LiveIns[i].first);
375
376         // Add the register to the entry block live-in set.
377         EntryMBB->addLiveIn(LiveIns[i].first);
378       }
379     } else {
380       // Add the register to the entry block live-in set.
381       EntryMBB->addLiveIn(LiveIns[i].first);
382     }
383 }
384
385 #ifndef NDEBUG
386 void MachineRegisterInfo::dumpUses(unsigned Reg) const {
387   for (use_iterator I = use_begin(Reg), E = use_end(); I != E; ++I)
388     I.getOperand().getParent()->dump();
389 }
390 #endif
391
392 void MachineRegisterInfo::freezeReservedRegs(const MachineFunction &MF) {
393   ReservedRegs = TRI->getReservedRegs(MF);
394   assert(ReservedRegs.size() == TRI->getNumRegs() &&
395          "Invalid ReservedRegs vector from target");
396 }
397
398 bool MachineRegisterInfo::isConstantPhysReg(unsigned PhysReg,
399                                             const MachineFunction &MF) const {
400   assert(TargetRegisterInfo::isPhysicalRegister(PhysReg));
401
402   // Check if any overlapping register is modified, or allocatable so it may be
403   // used later.
404   for (MCRegAliasIterator AI(PhysReg, TRI, true); AI.isValid(); ++AI)
405     if (!def_empty(*AI) || isAllocatable(*AI))
406       return false;
407   return true;
408 }