1 //===- lib/Codegen/MachineRegisterInfo.cpp --------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Implementation of the MachineRegisterInfo class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/MachineRegisterInfo.h"
15 #include "llvm/ADT/iterator_range.h"
16 #include "llvm/CodeGen/LowLevelType.h"
17 #include "llvm/CodeGen/MachineBasicBlock.h"
18 #include "llvm/CodeGen/MachineFunction.h"
19 #include "llvm/CodeGen/MachineInstr.h"
20 #include "llvm/CodeGen/MachineInstrBuilder.h"
21 #include "llvm/CodeGen/MachineOperand.h"
22 #include "llvm/CodeGen/TargetInstrInfo.h"
23 #include "llvm/CodeGen/TargetRegisterInfo.h"
24 #include "llvm/CodeGen/TargetSubtargetInfo.h"
25 #include "llvm/IR/Attributes.h"
26 #include "llvm/IR/DebugLoc.h"
27 #include "llvm/IR/Function.h"
28 #include "llvm/MC/MCRegisterInfo.h"
29 #include "llvm/Support/Casting.h"
30 #include "llvm/Support/CommandLine.h"
31 #include "llvm/Support/Compiler.h"
32 #include "llvm/Support/ErrorHandling.h"
33 #include "llvm/Support/raw_ostream.h"
38 static cl::opt<bool> EnableSubRegLiveness("enable-subreg-liveness", cl::Hidden,
39 cl::init(true), cl::desc("Enable subregister liveness tracking."));
41 // Pin the vtable to this file.
42 void MachineRegisterInfo::Delegate::anchor() {}
44 MachineRegisterInfo::MachineRegisterInfo(MachineFunction *MF)
45 : MF(MF), TracksSubRegLiveness(MF->getSubtarget().enableSubRegLiveness() &&
46 EnableSubRegLiveness),
47 IsUpdatedCSRsInitialized(false) {
48 unsigned NumRegs = getTargetRegisterInfo()->getNumRegs();
49 VRegInfo.reserve(256);
50 RegAllocHints.reserve(256);
51 UsedPhysRegMask.resize(NumRegs);
52 PhysRegUseDefLists.reset(new MachineOperand*[NumRegs]());
55 /// setRegClass - Set the register class of the specified virtual register.
58 MachineRegisterInfo::setRegClass(unsigned Reg, const TargetRegisterClass *RC) {
59 assert(RC && RC->isAllocatable() && "Invalid RC for virtual register");
60 VRegInfo[Reg].first = RC;
63 void MachineRegisterInfo::setRegBank(unsigned Reg,
64 const RegisterBank &RegBank) {
65 VRegInfo[Reg].first = &RegBank;
68 const TargetRegisterClass *
69 MachineRegisterInfo::constrainRegClass(unsigned Reg,
70 const TargetRegisterClass *RC,
71 unsigned MinNumRegs) {
72 const TargetRegisterClass *OldRC = getRegClass(Reg);
75 const TargetRegisterClass *NewRC =
76 getTargetRegisterInfo()->getCommonSubClass(OldRC, RC);
77 if (!NewRC || NewRC == OldRC)
79 if (NewRC->getNumRegs() < MinNumRegs)
81 setRegClass(Reg, NewRC);
86 MachineRegisterInfo::recomputeRegClass(unsigned Reg) {
87 const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
88 const TargetRegisterClass *OldRC = getRegClass(Reg);
89 const TargetRegisterClass *NewRC =
90 getTargetRegisterInfo()->getLargestLegalSuperClass(OldRC, *MF);
92 // Stop early if there is no room to grow.
96 // Accumulate constraints from all uses.
97 for (MachineOperand &MO : reg_nodbg_operands(Reg)) {
98 // Apply the effect of the given operand to NewRC.
99 MachineInstr *MI = MO.getParent();
100 unsigned OpNo = &MO - &MI->getOperand(0);
101 NewRC = MI->getRegClassConstraintEffect(OpNo, NewRC, TII,
102 getTargetRegisterInfo());
103 if (!NewRC || NewRC == OldRC)
106 setRegClass(Reg, NewRC);
110 unsigned MachineRegisterInfo::createIncompleteVirtualRegister() {
111 unsigned Reg = TargetRegisterInfo::index2VirtReg(getNumVirtRegs());
113 RegAllocHints.grow(Reg);
117 /// createVirtualRegister - Create and return a new virtual register in the
118 /// function with the specified register class.
121 MachineRegisterInfo::createVirtualRegister(const TargetRegisterClass *RegClass){
122 assert(RegClass && "Cannot create register without RegClass!");
123 assert(RegClass->isAllocatable() &&
124 "Virtual register RegClass must be allocatable.");
126 // New virtual register number.
127 unsigned Reg = createIncompleteVirtualRegister();
128 VRegInfo[Reg].first = RegClass;
130 TheDelegate->MRI_NoteNewVirtualRegister(Reg);
134 LLT MachineRegisterInfo::getType(unsigned VReg) const {
135 VRegToTypeMap::const_iterator TypeIt = getVRegToType().find(VReg);
136 return TypeIt != getVRegToType().end() ? TypeIt->second : LLT{};
139 void MachineRegisterInfo::setType(unsigned VReg, LLT Ty) {
140 // Check that VReg doesn't have a class.
141 assert((getRegClassOrRegBank(VReg).isNull() ||
142 !getRegClassOrRegBank(VReg).is<const TargetRegisterClass *>()) &&
143 "Can't set the size of a non-generic virtual register");
144 getVRegToType()[VReg] = Ty;
148 MachineRegisterInfo::createGenericVirtualRegister(LLT Ty) {
149 // New virtual register number.
150 unsigned Reg = createIncompleteVirtualRegister();
151 // FIXME: Should we use a dummy register class?
152 VRegInfo[Reg].first = static_cast<RegisterBank *>(nullptr);
153 getVRegToType()[Reg] = Ty;
155 TheDelegate->MRI_NoteNewVirtualRegister(Reg);
159 void MachineRegisterInfo::clearVirtRegTypes() {
160 getVRegToType().clear();
163 /// clearVirtRegs - Remove all virtual registers (after physreg assignment).
164 void MachineRegisterInfo::clearVirtRegs() {
166 for (unsigned i = 0, e = getNumVirtRegs(); i != e; ++i) {
167 unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
168 if (!VRegInfo[Reg].second)
171 llvm_unreachable("Remaining virtual register operands");
175 for (auto &I : LiveIns)
179 void MachineRegisterInfo::verifyUseList(unsigned Reg) const {
182 for (MachineOperand &M : reg_operands(Reg)) {
183 MachineOperand *MO = &M;
184 MachineInstr *MI = MO->getParent();
186 errs() << printReg(Reg, getTargetRegisterInfo())
187 << " use list MachineOperand " << MO
188 << " has no parent instruction.\n";
192 MachineOperand *MO0 = &MI->getOperand(0);
193 unsigned NumOps = MI->getNumOperands();
194 if (!(MO >= MO0 && MO < MO0+NumOps)) {
195 errs() << printReg(Reg, getTargetRegisterInfo())
196 << " use list MachineOperand " << MO
197 << " doesn't belong to parent MI: " << *MI;
201 errs() << printReg(Reg, getTargetRegisterInfo())
202 << " MachineOperand " << MO << ": " << *MO
203 << " is not a register\n";
206 if (MO->getReg() != Reg) {
207 errs() << printReg(Reg, getTargetRegisterInfo())
208 << " use-list MachineOperand " << MO << ": "
209 << *MO << " is the wrong register\n";
213 assert(Valid && "Invalid use list");
217 void MachineRegisterInfo::verifyUseLists() const {
219 for (unsigned i = 0, e = getNumVirtRegs(); i != e; ++i)
220 verifyUseList(TargetRegisterInfo::index2VirtReg(i));
221 for (unsigned i = 1, e = getTargetRegisterInfo()->getNumRegs(); i != e; ++i)
226 /// Add MO to the linked list of operands for its register.
227 void MachineRegisterInfo::addRegOperandToUseList(MachineOperand *MO) {
228 assert(!MO->isOnRegUseList() && "Already on list");
229 MachineOperand *&HeadRef = getRegUseDefListHead(MO->getReg());
230 MachineOperand *const Head = HeadRef;
232 // Head points to the first list element.
233 // Next is NULL on the last list element.
234 // Prev pointers are circular, so Head->Prev == Last.
236 // Head is NULL for an empty list.
238 MO->Contents.Reg.Prev = MO;
239 MO->Contents.Reg.Next = nullptr;
243 assert(MO->getReg() == Head->getReg() && "Different regs on the same list!");
245 // Insert MO between Last and Head in the circular Prev chain.
246 MachineOperand *Last = Head->Contents.Reg.Prev;
247 assert(Last && "Inconsistent use list");
248 assert(MO->getReg() == Last->getReg() && "Different regs on the same list!");
249 Head->Contents.Reg.Prev = MO;
250 MO->Contents.Reg.Prev = Last;
252 // Def operands always precede uses. This allows def_iterator to stop early.
253 // Insert def operands at the front, and use operands at the back.
255 // Insert def at the front.
256 MO->Contents.Reg.Next = Head;
259 // Insert use at the end.
260 MO->Contents.Reg.Next = nullptr;
261 Last->Contents.Reg.Next = MO;
265 /// Remove MO from its use-def list.
266 void MachineRegisterInfo::removeRegOperandFromUseList(MachineOperand *MO) {
267 assert(MO->isOnRegUseList() && "Operand not on use list");
268 MachineOperand *&HeadRef = getRegUseDefListHead(MO->getReg());
269 MachineOperand *const Head = HeadRef;
270 assert(Head && "List already empty");
272 // Unlink this from the doubly linked list of operands.
273 MachineOperand *Next = MO->Contents.Reg.Next;
274 MachineOperand *Prev = MO->Contents.Reg.Prev;
276 // Prev links are circular, next link is NULL instead of looping back to Head.
280 Prev->Contents.Reg.Next = Next;
282 (Next ? Next : Head)->Contents.Reg.Prev = Prev;
284 MO->Contents.Reg.Prev = nullptr;
285 MO->Contents.Reg.Next = nullptr;
288 /// Move NumOps operands from Src to Dst, updating use-def lists as needed.
290 /// The Dst range is assumed to be uninitialized memory. (Or it may contain
291 /// operands that won't be destroyed, which is OK because the MO destructor is
294 /// The Src and Dst ranges may overlap.
295 void MachineRegisterInfo::moveOperands(MachineOperand *Dst,
298 assert(Src != Dst && NumOps && "Noop moveOperands");
300 // Copy backwards if Dst is within the Src range.
302 if (Dst >= Src && Dst < Src + NumOps) {
308 // Copy one operand at a time.
310 new (Dst) MachineOperand(*Src);
312 // Dst takes Src's place in the use-def chain.
314 MachineOperand *&Head = getRegUseDefListHead(Src->getReg());
315 MachineOperand *Prev = Src->Contents.Reg.Prev;
316 MachineOperand *Next = Src->Contents.Reg.Next;
317 assert(Head && "List empty, but operand is chained");
318 assert(Prev && "Operand was not on use-def list");
320 // Prev links are circular, next link is NULL instead of looping back to
325 Prev->Contents.Reg.Next = Dst;
327 // Update Prev pointer. This also works when Src was pointing to itself
328 // in a 1-element list. In that case Head == Dst.
329 (Next ? Next : Head)->Contents.Reg.Prev = Dst;
337 /// replaceRegWith - Replace all instances of FromReg with ToReg in the
338 /// machine function. This is like llvm-level X->replaceAllUsesWith(Y),
339 /// except that it also changes any definitions of the register as well.
340 /// If ToReg is a physical register we apply the sub register to obtain the
341 /// final/proper physical register.
342 void MachineRegisterInfo::replaceRegWith(unsigned FromReg, unsigned ToReg) {
343 assert(FromReg != ToReg && "Cannot replace a reg with itself");
345 const TargetRegisterInfo *TRI = getTargetRegisterInfo();
347 // TODO: This could be more efficient by bulk changing the operands.
348 for (reg_iterator I = reg_begin(FromReg), E = reg_end(); I != E; ) {
349 MachineOperand &O = *I;
351 if (TargetRegisterInfo::isPhysicalRegister(ToReg)) {
352 O.substPhysReg(ToReg, *TRI);
359 /// getVRegDef - Return the machine instr that defines the specified virtual
360 /// register or null if none is found. This assumes that the code is in SSA
361 /// form, so there should only be one definition.
362 MachineInstr *MachineRegisterInfo::getVRegDef(unsigned Reg) const {
363 // Since we are in SSA form, we can use the first definition.
364 def_instr_iterator I = def_instr_begin(Reg);
365 assert((I.atEnd() || std::next(I) == def_instr_end()) &&
366 "getVRegDef assumes a single definition or no definition");
367 return !I.atEnd() ? &*I : nullptr;
370 /// getUniqueVRegDef - Return the unique machine instr that defines the
371 /// specified virtual register or null if none is found. If there are
372 /// multiple definitions or no definition, return null.
373 MachineInstr *MachineRegisterInfo::getUniqueVRegDef(unsigned Reg) const {
374 if (def_empty(Reg)) return nullptr;
375 def_instr_iterator I = def_instr_begin(Reg);
376 if (std::next(I) != def_instr_end())
381 bool MachineRegisterInfo::hasOneNonDBGUse(unsigned RegNo) const {
382 use_nodbg_iterator UI = use_nodbg_begin(RegNo);
383 if (UI == use_nodbg_end())
385 return ++UI == use_nodbg_end();
388 /// clearKillFlags - Iterate over all the uses of the given register and
389 /// clear the kill flag from the MachineOperand. This function is used by
390 /// optimization passes which extend register lifetimes and need only
391 /// preserve conservative kill flag information.
392 void MachineRegisterInfo::clearKillFlags(unsigned Reg) const {
393 for (MachineOperand &MO : use_operands(Reg))
397 bool MachineRegisterInfo::isLiveIn(unsigned Reg) const {
398 for (livein_iterator I = livein_begin(), E = livein_end(); I != E; ++I)
399 if (I->first == Reg || I->second == Reg)
404 /// getLiveInPhysReg - If VReg is a live-in virtual register, return the
405 /// corresponding live-in physical register.
406 unsigned MachineRegisterInfo::getLiveInPhysReg(unsigned VReg) const {
407 for (livein_iterator I = livein_begin(), E = livein_end(); I != E; ++I)
408 if (I->second == VReg)
413 /// getLiveInVirtReg - If PReg is a live-in physical register, return the
414 /// corresponding live-in physical register.
415 unsigned MachineRegisterInfo::getLiveInVirtReg(unsigned PReg) const {
416 for (livein_iterator I = livein_begin(), E = livein_end(); I != E; ++I)
417 if (I->first == PReg)
422 /// EmitLiveInCopies - Emit copies to initialize livein virtual registers
423 /// into the given entry block.
425 MachineRegisterInfo::EmitLiveInCopies(MachineBasicBlock *EntryMBB,
426 const TargetRegisterInfo &TRI,
427 const TargetInstrInfo &TII) {
428 // Emit the copies into the top of the block.
429 for (unsigned i = 0, e = LiveIns.size(); i != e; ++i)
430 if (LiveIns[i].second) {
431 if (use_nodbg_empty(LiveIns[i].second)) {
432 // The livein has no non-dbg uses. Drop it.
434 // It would be preferable to have isel avoid creating live-in
435 // records for unused arguments in the first place, but it's
436 // complicated by the debug info code for arguments.
437 LiveIns.erase(LiveIns.begin() + i);
441 BuildMI(*EntryMBB, EntryMBB->begin(), DebugLoc(),
442 TII.get(TargetOpcode::COPY), LiveIns[i].second)
443 .addReg(LiveIns[i].first);
445 // Add the register to the entry block live-in set.
446 EntryMBB->addLiveIn(LiveIns[i].first);
449 // Add the register to the entry block live-in set.
450 EntryMBB->addLiveIn(LiveIns[i].first);
454 LaneBitmask MachineRegisterInfo::getMaxLaneMaskForVReg(unsigned Reg) const {
455 // Lane masks are only defined for vregs.
456 assert(TargetRegisterInfo::isVirtualRegister(Reg));
457 const TargetRegisterClass &TRC = *getRegClass(Reg);
458 return TRC.getLaneMask();
461 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
462 LLVM_DUMP_METHOD void MachineRegisterInfo::dumpUses(unsigned Reg) const {
463 for (MachineInstr &I : use_instructions(Reg))
468 void MachineRegisterInfo::freezeReservedRegs(const MachineFunction &MF) {
469 ReservedRegs = getTargetRegisterInfo()->getReservedRegs(MF);
470 assert(ReservedRegs.size() == getTargetRegisterInfo()->getNumRegs() &&
471 "Invalid ReservedRegs vector from target");
474 bool MachineRegisterInfo::isConstantPhysReg(unsigned PhysReg) const {
475 assert(TargetRegisterInfo::isPhysicalRegister(PhysReg));
477 const TargetRegisterInfo *TRI = getTargetRegisterInfo();
478 if (TRI->isConstantPhysReg(PhysReg))
481 // Check if any overlapping register is modified, or allocatable so it may be
483 for (MCRegAliasIterator AI(PhysReg, TRI, true);
485 if (!def_empty(*AI) || isAllocatable(*AI))
491 MachineRegisterInfo::isCallerPreservedOrConstPhysReg(unsigned PhysReg) const {
492 const TargetRegisterInfo *TRI = getTargetRegisterInfo();
493 return isConstantPhysReg(PhysReg) ||
494 TRI->isCallerPreservedPhysReg(PhysReg, *MF);
497 /// markUsesInDebugValueAsUndef - Mark every DBG_VALUE referencing the
498 /// specified register as undefined which causes the DBG_VALUE to be
499 /// deleted during LiveDebugVariables analysis.
500 void MachineRegisterInfo::markUsesInDebugValueAsUndef(unsigned Reg) const {
501 // Mark any DBG_VALUE that uses Reg as undef (but don't delete it.)
502 MachineRegisterInfo::use_instr_iterator nextI;
503 for (use_instr_iterator I = use_instr_begin(Reg), E = use_instr_end();
505 nextI = std::next(I); // I is invalidated by the setReg
506 MachineInstr *UseMI = &*I;
507 if (UseMI->isDebugValue())
508 UseMI->getOperand(0).setReg(0U);
512 static const Function *getCalledFunction(const MachineInstr &MI) {
513 for (const MachineOperand &MO : MI.operands()) {
516 const Function *Func = dyn_cast<Function>(MO.getGlobal());
523 static bool isNoReturnDef(const MachineOperand &MO) {
524 // Anything which is not a noreturn function is a real def.
525 const MachineInstr &MI = *MO.getParent();
528 const MachineBasicBlock &MBB = *MI.getParent();
529 if (!MBB.succ_empty())
531 const MachineFunction &MF = *MBB.getParent();
532 // We need to keep correct unwind information even if the function will
533 // not return, since the runtime may need it.
534 if (MF.getFunction().hasFnAttribute(Attribute::UWTable))
536 const Function *Called = getCalledFunction(MI);
537 return !(Called == nullptr || !Called->hasFnAttribute(Attribute::NoReturn) ||
538 !Called->hasFnAttribute(Attribute::NoUnwind));
541 bool MachineRegisterInfo::isPhysRegModified(unsigned PhysReg,
542 bool SkipNoReturnDef) const {
543 if (UsedPhysRegMask.test(PhysReg))
545 const TargetRegisterInfo *TRI = getTargetRegisterInfo();
546 for (MCRegAliasIterator AI(PhysReg, TRI, true); AI.isValid(); ++AI) {
547 for (const MachineOperand &MO : make_range(def_begin(*AI), def_end())) {
548 if (!SkipNoReturnDef && isNoReturnDef(MO))
556 bool MachineRegisterInfo::isPhysRegUsed(unsigned PhysReg) const {
557 if (UsedPhysRegMask.test(PhysReg))
559 const TargetRegisterInfo *TRI = getTargetRegisterInfo();
560 for (MCRegAliasIterator AliasReg(PhysReg, TRI, true); AliasReg.isValid();
562 if (!reg_nodbg_empty(*AliasReg))
568 void MachineRegisterInfo::disableCalleeSavedRegister(unsigned Reg) {
570 const TargetRegisterInfo *TRI = getTargetRegisterInfo();
571 assert(Reg && (Reg < TRI->getNumRegs()) &&
572 "Trying to disable an invalid register");
574 if (!IsUpdatedCSRsInitialized) {
575 const MCPhysReg *CSR = TRI->getCalleeSavedRegs(MF);
576 for (const MCPhysReg *I = CSR; *I; ++I)
577 UpdatedCSRs.push_back(*I);
579 // Zero value represents the end of the register list
580 // (no more registers should be pushed).
581 UpdatedCSRs.push_back(0);
583 IsUpdatedCSRsInitialized = true;
586 // Remove the register (and its aliases from the list).
587 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
588 UpdatedCSRs.erase(std::remove(UpdatedCSRs.begin(), UpdatedCSRs.end(), *AI),
592 const MCPhysReg *MachineRegisterInfo::getCalleeSavedRegs() const {
593 if (IsUpdatedCSRsInitialized)
594 return UpdatedCSRs.data();
596 return getTargetRegisterInfo()->getCalleeSavedRegs(MF);
599 void MachineRegisterInfo::setCalleeSavedRegs(ArrayRef<MCPhysReg> CSRs) {
600 if (IsUpdatedCSRsInitialized)
603 for (MCPhysReg Reg : CSRs)
604 UpdatedCSRs.push_back(Reg);
606 // Zero value represents the end of the register list
607 // (no more registers should be pushed).
608 UpdatedCSRs.push_back(0);
609 IsUpdatedCSRsInitialized = true;
612 bool MachineRegisterInfo::isReservedRegUnit(unsigned Unit) const {
613 const TargetRegisterInfo *TRI = getTargetRegisterInfo();
614 for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) {
615 bool IsRootReserved = true;
616 for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true);
617 Super.isValid(); ++Super) {
618 unsigned Reg = *Super;
619 if (!isReserved(Reg)) {
620 IsRootReserved = false;