X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocFast.cpp;h=f4c076fea0e706de84204e2afae6fa8daaa770bd;hb=ae62636ef881aa040e9c550cccb8404a4598a957;hp=3082ce16d0f4c938d733b17f1370e4655600bddb;hpb=7b79b9862c9e6fc31ec072acb09171fd6ec7b0e0;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocFast.cpp b/lib/CodeGen/RegAllocFast.cpp index 3082ce16d0f..f4c076fea0e 100644 --- a/lib/CodeGen/RegAllocFast.cpp +++ b/lib/CodeGen/RegAllocFast.cpp @@ -12,7 +12,6 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "regalloc" #include "llvm/CodeGen/Passes.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/IndexedMap.h" @@ -21,7 +20,6 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/SparseSet.h" #include "llvm/ADT/Statistic.h" -#include "llvm/BasicBlock.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" @@ -29,15 +27,18 @@ #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/RegAllocRegistry.h" #include "llvm/CodeGen/RegisterClassInfo.h" +#include "llvm/IR/BasicBlock.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetSubtargetInfo.h" #include using namespace llvm; +#define DEBUG_TYPE "regalloc" + STATISTIC(NumStores, "Number of stores added"); STATISTIC(NumLoads , "Number of loads added"); STATISTIC(NumCopies, "Number of copies coalesced"); @@ -52,7 +53,6 @@ namespace { RAFast() : MachineFunctionPass(ID), StackSlotForVirtReg(-1), isBulkSpilling(false) {} private: - const TargetMachine *TM; MachineFunction *MF; MachineRegisterInfo *MRI; const TargetRegisterInfo *TRI; @@ -75,7 +75,7 @@ namespace { bool Dirty; // Register needs spill. explicit LiveReg(unsigned v) - : LastUse(0), VirtReg(v), PhysReg(0), LastOpNum(0), Dirty(false) {} + : LastUse(nullptr), VirtReg(v), PhysReg(0), LastOpNum(0), Dirty(false){} unsigned getSparseSetIndex() const { return TargetRegisterInfo::virtReg2Index(VirtReg); @@ -113,12 +113,27 @@ namespace { // PhysRegState - One of the RegState enums, or a virtreg. std::vector PhysRegState; + // Set of register units. typedef SparseSet UsedInInstrSet; - // UsedInInstr - Set of physregs that are used in the current instruction, - // and so cannot be allocated. + // Set of register units that are used in the current instruction, and so + // cannot be allocated. UsedInInstrSet UsedInInstr; + // Mark a physreg as used in this instruction. + void markRegUsedInInstr(unsigned PhysReg) { + for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) + UsedInInstr.insert(*Units); + } + + // Check if a physreg or any of its aliases are used in this instruction. + bool isRegUsedInInstr(unsigned PhysReg) const { + for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) + if (UsedInInstr.count(*Units)) + return true; + return false; + } + // SkippedInstrs - Descriptors of instructions whose clobber list was // ignored because all registers were spilled. It is still necessary to // mark all the clobbered registers as used by the function. @@ -129,23 +144,23 @@ namespace { // not be erased. bool isBulkSpilling; - enum { + enum : unsigned { spillClean = 1, spillDirty = 100, spillImpossible = ~0u }; public: - virtual const char *getPassName() const { + const char *getPassName() const override { return "Fast Register Allocator"; } - virtual void getAnalysisUsage(AnalysisUsage &AU) const { + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesCFG(); MachineFunctionPass::getAnalysisUsage(AU); } private: - bool runOnMachineFunction(MachineFunction &Fn); + bool runOnMachineFunction(MachineFunction &Fn) override; void AllocateBasicBlock(); void handleThroughOperands(MachineInstr *MI, SmallVectorImpl &VirtDead); @@ -177,7 +192,6 @@ namespace { unsigned VirtReg, unsigned Hint); void spillAll(MachineBasicBlock::iterator MI); bool setPhysReg(MachineInstr *MI, unsigned OpNum, unsigned PhysReg); - void addRetOperands(MachineBasicBlock *MBB); }; char RAFast::ID = 0; } @@ -210,7 +224,7 @@ bool RAFast::isLastUseOfLocalReg(MachineOperand &MO) { // Check that the use/def chain has exactly one operand - MO. MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(MO.getReg()); - if (&I.getOperand() != &MO) + if (&*I != &MO) return false; return ++I == MRI->reg_nodbg_end(); } @@ -279,36 +293,33 @@ void RAFast::spillVirtReg(MachineBasicBlock::iterator MI, // If this register is used by DBG_VALUE then insert new DBG_VALUE to // identify spilled location as the place to find corresponding variable's // value. - SmallVector &LRIDbgValues = + SmallVectorImpl &LRIDbgValues = LiveDbgValueMap[LRI->VirtReg]; for (unsigned li = 0, le = LRIDbgValues.size(); li != le; ++li) { MachineInstr *DBG = LRIDbgValues[li]; - const MDNode *MDPtr = - DBG->getOperand(DBG->getNumOperands()-1).getMetadata(); - int64_t Offset = 0; - if (DBG->getOperand(1).isImm()) - Offset = DBG->getOperand(1).getImm(); - DebugLoc DL; - if (MI == MBB->end()) { - // If MI is at basic block end then use last instruction's location. - MachineBasicBlock::iterator EI = MI; - DL = (--EI)->getDebugLoc(); - } - else - DL = MI->getDebugLoc(); - if (MachineInstr *NewDV = - TII->emitFrameIndexDebugValue(*MF, FI, Offset, MDPtr, DL)) { - MachineBasicBlock *MBB = DBG->getParent(); - MBB->insert(MI, NewDV); - DEBUG(dbgs() << "Inserting debug info due to spill:" << "\n" << *NewDV); - } + const MDNode *Var = DBG->getDebugVariable(); + const MDNode *Expr = DBG->getDebugExpression(); + bool IsIndirect = DBG->isIndirectDebugValue(); + uint64_t Offset = IsIndirect ? DBG->getOperand(1).getImm() : 0; + DebugLoc DL = DBG->getDebugLoc(); + assert(cast(Var)->isValidLocationForIntrinsic(DL) && + "Expected inlined-at fields to agree"); + MachineInstr *NewDV = + BuildMI(*MBB, MI, DL, TII->get(TargetOpcode::DBG_VALUE)) + .addFrameIndex(FI) + .addImm(Offset) + .addMetadata(Var) + .addMetadata(Expr); + assert(NewDV->getParent() == MBB && "dangling parent pointer"); + (void)NewDV; + DEBUG(dbgs() << "Inserting debug info due to spill:" << "\n" << *NewDV); } // Now this register is spilled there is should not be any DBG_VALUE // pointing to this register because they are all pointing to spilled value // now. LRIDbgValues.clear(); if (SpillKill) - LR.LastUse = 0; // Don't kill register again + LR.LastUse = nullptr; // Don't kill register again } killVirtReg(LRI); } @@ -334,7 +345,7 @@ void RAFast::usePhysReg(MachineOperand &MO) { unsigned PhysReg = MO.getReg(); assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && "Bad usePhysReg operand"); - + markRegUsedInInstr(PhysReg); switch (PhysRegState[PhysReg]) { case regDisabled: break; @@ -342,7 +353,6 @@ void RAFast::usePhysReg(MachineOperand &MO) { PhysRegState[PhysReg] = regFree; // Fall through case regFree: - UsedInInstr.insert(PhysReg); MO.setIsKill(); return; default: @@ -358,17 +368,23 @@ void RAFast::usePhysReg(MachineOperand &MO) { case regDisabled: break; case regReserved: - assert(TRI->isSuperRegister(PhysReg, Alias) && + // Either PhysReg is a subregister of Alias and we mark the + // whole register as free, or PhysReg is the superregister of + // Alias and we mark all the aliases as disabled before freeing + // PhysReg. + // In the latter case, since PhysReg was disabled, this means that + // its value is defined only by physical sub-registers. This check + // is performed by the assert of the default case in this loop. + // Note: The value of the superregister may only be partial + // defined, that is why regDisabled is a valid state for aliases. + assert((TRI->isSuperRegister(PhysReg, Alias) || + TRI->isSuperRegister(Alias, PhysReg)) && "Instruction is not using a subregister of a reserved register"); - // Leave the superregister in the working set. - PhysRegState[Alias] = regFree; - UsedInInstr.insert(Alias); - MO.getParent()->addRegisterKilled(Alias, TRI, true); - return; + // Fall through. case regFree: if (TRI->isSuperRegister(PhysReg, Alias)) { // Leave the superregister in the working set. - UsedInInstr.insert(Alias); + PhysRegState[Alias] = regFree; MO.getParent()->addRegisterKilled(Alias, TRI, true); return; } @@ -382,7 +398,6 @@ void RAFast::usePhysReg(MachineOperand &MO) { // All aliases are disabled, bring register into working set. PhysRegState[PhysReg] = regFree; - UsedInInstr.insert(PhysReg); MO.setIsKill(); } @@ -391,7 +406,7 @@ void RAFast::usePhysReg(MachineOperand &MO) { /// reserved instead of allocated. void RAFast::definePhysReg(MachineInstr *MI, unsigned PhysReg, RegState NewState) { - UsedInInstr.insert(PhysReg); + markRegUsedInInstr(PhysReg); switch (unsigned VirtReg = PhysRegState[PhysReg]) { case regDisabled: break; @@ -431,7 +446,7 @@ void RAFast::definePhysReg(MachineInstr *MI, unsigned PhysReg, // can be allocated directly. // Returns spillImpossible when PhysReg or an alias can't be spilled. unsigned RAFast::calcSpillCost(unsigned PhysReg) const { - if (UsedInInstr.count(PhysReg)) { + if (isRegUsedInInstr(PhysReg)) { DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is already used in instr.\n"); return spillImpossible; } @@ -456,8 +471,6 @@ unsigned RAFast::calcSpillCost(unsigned PhysReg) const { unsigned Cost = 0; for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) { unsigned Alias = *AI; - if (UsedInInstr.count(Alias)) - return spillImpossible; switch (unsigned VirtReg = PhysRegState[Alias]) { case regDisabled: break; @@ -532,14 +545,14 @@ RAFast::LiveRegMap::iterator RAFast::allocVirtReg(MachineInstr *MI, // First try to find a completely free register. for (ArrayRef::iterator I = AO.begin(), E = AO.end(); I != E; ++I){ unsigned PhysReg = *I; - if (PhysRegState[PhysReg] == regFree && !UsedInInstr.count(PhysReg)) { + if (PhysRegState[PhysReg] == regFree && !isRegUsedInInstr(PhysReg)) { assignVirtToPhysReg(*LRI, PhysReg); return LRI; } } DEBUG(dbgs() << "Allocating " << PrintReg(VirtReg) << " from " - << RC->getName() << "\n"); + << TRI->getRegClassName(RC) << "\n"); unsigned BestReg = 0, BestCost = spillImpossible; for (ArrayRef::iterator I = AO.begin(), E = AO.end(); I != E; ++I){ @@ -564,7 +577,10 @@ RAFast::LiveRegMap::iterator RAFast::allocVirtReg(MachineInstr *MI, } // Nothing we can do. Report an error and keep going with a bad allocation. - MI->emitError("ran out of registers during register allocation"); + if (MI->isInlineAsm()) + MI->emitError("inline assembly requires more registers than available"); + else + MI->emitError("ran out of registers during register allocation"); definePhysReg(MI, *AO.begin(), regFree); return assignVirtToPhysReg(VirtReg, *AO.begin()); } @@ -577,12 +593,12 @@ RAFast::defineVirtReg(MachineInstr *MI, unsigned OpNum, "Not a virtual register"); LiveRegMap::iterator LRI; bool New; - tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg)); + std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg)); if (New) { // If there is no hint, peek at the only use of this register. if ((!Hint || !TargetRegisterInfo::isPhysicalRegister(Hint)) && MRI->hasOneNonDBGUse(VirtReg)) { - const MachineInstr &UseMI = *MRI->use_nodbg_begin(VirtReg); + const MachineInstr &UseMI = *MRI->use_instr_nodbg_begin(VirtReg); // It's a copy, use the destination register as a hint. if (UseMI.isCopyLike()) Hint = UseMI.getOperand(0).getReg(); @@ -598,7 +614,7 @@ RAFast::defineVirtReg(MachineInstr *MI, unsigned OpNum, LRI->LastUse = MI; LRI->LastOpNum = OpNum; LRI->Dirty = true; - UsedInInstr.insert(LRI->PhysReg); + markRegUsedInInstr(LRI->PhysReg); return LRI; } @@ -610,7 +626,7 @@ RAFast::reloadVirtReg(MachineInstr *MI, unsigned OpNum, "Not a virtual register"); LiveRegMap::iterator LRI; bool New; - tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg)); + std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg)); MachineOperand &MO = MI->getOperand(OpNum); if (New) { LRI = allocVirtReg(MI, LRI, Hint); @@ -648,7 +664,7 @@ RAFast::reloadVirtReg(MachineInstr *MI, unsigned OpNum, assert(LRI->PhysReg && "Register not assigned"); LRI->LastUse = MI; LRI->LastOpNum = OpNum; - UsedInInstr.insert(LRI->PhysReg); + markRegUsedInInstr(LRI->PhysReg); return LRI; } @@ -696,7 +712,7 @@ void RAFast::handleThroughOperands(MachineInstr *MI, continue; if (MO.isEarlyClobber() || MI->isRegTiedToDefOperand(i) || (MO.getSubReg() && MI->readsVirtualRegister(Reg))) { - if (ThroughRegs.insert(Reg)) + if (ThroughRegs.insert(Reg).second) DEBUG(dbgs() << ' ' << PrintReg(Reg)); } } @@ -709,8 +725,8 @@ void RAFast::handleThroughOperands(MachineInstr *MI, if (!MO.isReg() || !MO.isDef()) continue; unsigned Reg = MO.getReg(); if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; + markRegUsedInInstr(Reg); for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { - UsedInInstr.insert(*AI); if (ThroughRegs.count(PhysRegState[*AI])) definePhysReg(MI, *AI, regFree); } @@ -766,65 +782,12 @@ void RAFast::handleThroughOperands(MachineInstr *MI, if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; DEBUG(dbgs() << "\tSetting " << PrintReg(Reg, TRI) << " as used in instr\n"); - UsedInInstr.insert(Reg); + markRegUsedInInstr(Reg); } // Also mark PartialDefs as used to avoid reallocation. for (unsigned i = 0, e = PartialDefs.size(); i != e; ++i) - UsedInInstr.insert(PartialDefs[i]); -} - -/// addRetOperand - ensure that a return instruction has an operand for each -/// value live out of the function. -/// -/// Things marked both call and return are tail calls; do not do this for them. -/// The tail callee need not take the same registers as input that it produces -/// as output, and there are dependencies for its input registers elsewhere. -/// -/// FIXME: This should be done as part of instruction selection, and this helper -/// should be deleted. Until then, we use custom logic here to create the proper -/// operand under all circumstances. We can't use addRegisterKilled because that -/// doesn't make sense for undefined values. We can't simply avoid calling it -/// for undefined values, because we must ensure that the operand always exists. -void RAFast::addRetOperands(MachineBasicBlock *MBB) { - if (MBB->empty() || !MBB->back().isReturn() || MBB->back().isCall()) - return; - - MachineInstr *MI = &MBB->back(); - - for (MachineRegisterInfo::liveout_iterator - I = MBB->getParent()->getRegInfo().liveout_begin(), - E = MBB->getParent()->getRegInfo().liveout_end(); I != E; ++I) { - unsigned Reg = *I; - assert(TargetRegisterInfo::isPhysicalRegister(Reg) && - "Cannot have a live-out virtual register."); - - bool hasDef = PhysRegState[Reg] == regReserved; - - // Check if this register already has an operand. - bool Found = false; - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand &MO = MI->getOperand(i); - if (!MO.isReg() || !MO.isUse()) - continue; - - unsigned OperReg = MO.getReg(); - if (!TargetRegisterInfo::isPhysicalRegister(OperReg)) - continue; - - if (OperReg == Reg || TRI->isSuperRegister(OperReg, Reg)) { - // If the ret already has an operand for this physreg or a superset, - // don't duplicate it. Set the kill flag if the value is defined. - if (hasDef && !MO.isKill()) - MO.setIsKill(); - Found = true; - break; - } - } - if (!Found) - MachineInstrBuilder(*MF, MI) - .addReg(Reg, llvm::RegState::Implicit | getKillRegState(hasDef)); - } + markRegUsedInInstr(PartialDefs[i]); } void RAFast::AllocateBasicBlock() { @@ -836,10 +799,9 @@ void RAFast::AllocateBasicBlock() { MachineBasicBlock::iterator MII = MBB->begin(); // Add live-in registers as live. - for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), - E = MBB->livein_end(); I != E; ++I) - if (MRI->isAllocatable(*I)) - definePhysReg(MII, *I, regReserved); + for (const auto &LI : MBB->liveins()) + if (MRI->isAllocatable(LI.PhysReg)) + definePhysReg(MII, LI.PhysReg, regReserved); SmallVector VirtDead; SmallVector Coalesced; @@ -904,25 +866,27 @@ void RAFast::AllocateBasicBlock() { } else { // Modify DBG_VALUE now that the value is in a spill slot. - int64_t Offset = MI->getOperand(1).getImm(); - const MDNode *MDPtr = - MI->getOperand(MI->getNumOperands()-1).getMetadata(); + bool IsIndirect = MI->isIndirectDebugValue(); + uint64_t Offset = IsIndirect ? MI->getOperand(1).getImm() : 0; + const MDNode *Var = MI->getDebugVariable(); + const MDNode *Expr = MI->getDebugExpression(); DebugLoc DL = MI->getDebugLoc(); - if (MachineInstr *NewDV = - TII->emitFrameIndexDebugValue(*MF, SS, Offset, MDPtr, DL)) { - DEBUG(dbgs() << "Modifying debug info due to spill:" << - "\t" << *MI); - MachineBasicBlock *MBB = MI->getParent(); - MBB->insert(MBB->erase(MI), NewDV); - // Scan NewDV operands from the beginning. - MI = NewDV; - ScanDbgValue = true; - break; - } else { - // We can't allocate a physreg for a DebugValue; sorry! - DEBUG(dbgs() << "Unable to allocate vreg used by DBG_VALUE"); - MO.setReg(0); - } + MachineBasicBlock *MBB = MI->getParent(); + assert( + cast(Var)->isValidLocationForIntrinsic(DL) && + "Expected inlined-at fields to agree"); + MachineInstr *NewDV = BuildMI(*MBB, MBB->erase(MI), DL, + TII->get(TargetOpcode::DBG_VALUE)) + .addFrameIndex(SS) + .addImm(Offset) + .addMetadata(Var) + .addMetadata(Expr); + DEBUG(dbgs() << "Modifying debug info due to spill:" + << "\t" << *NewDV); + // Scan NewDV operands from the beginning. + MI = NewDV; + ScanDbgValue = true; + break; } } LiveDbgValueMap[Reg].push_back(MI); @@ -1021,10 +985,6 @@ void RAFast::AllocateBasicBlock() { } } - for (UsedInInstrSet::iterator - I = UsedInInstr.begin(), E = UsedInInstr.end(); I != E; ++I) - MRI->setPhysRegUsed(*I); - // Track registers defined by instruction - early clobbers and tied uses at // this point. UsedInInstr.clear(); @@ -1036,8 +996,7 @@ void RAFast::AllocateBasicBlock() { if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; // Look for physreg defs and tied uses. if (!MO.isDef() && !MI->isRegTiedToDefOperand(i)) continue; - for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) - UsedInInstr.insert(*AI); + markRegUsedInInstr(Reg); } } @@ -1066,8 +1025,7 @@ void RAFast::AllocateBasicBlock() { if (TargetRegisterInfo::isPhysicalRegister(Reg)) { if (!MRI->isAllocatable(Reg)) continue; - definePhysReg(MI, Reg, (MO.isImplicit() || MO.isDead()) ? - regFree : regReserved); + definePhysReg(MI, Reg, MO.isDead() ? regFree : regReserved); continue; } LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, CopySrc); @@ -1087,10 +1045,6 @@ void RAFast::AllocateBasicBlock() { killVirtReg(VirtDead[i]); VirtDead.clear(); - for (UsedInInstrSet::iterator - I = UsedInInstr.begin(), E = UsedInInstr.end(); I != E; ++I) - MRI->setPhysRegUsed(*I); - if (CopyDst && CopyDst == CopySrc && CopyDstSub == CopySrcSub) { DEBUG(dbgs() << "-- coalescing: " << *MI); Coalesced.push_back(MI); @@ -1109,9 +1063,6 @@ void RAFast::AllocateBasicBlock() { MBB->erase(Coalesced[i]); NumCopies += Coalesced.size(); - // addRetOperands must run after we've seen all defs in this block. - addRetOperands(MBB); - DEBUG(MBB->dump()); } @@ -1122,13 +1073,12 @@ bool RAFast::runOnMachineFunction(MachineFunction &Fn) { << "********** Function: " << Fn.getName() << '\n'); MF = &Fn; MRI = &MF->getRegInfo(); - TM = &Fn.getTarget(); - TRI = TM->getRegisterInfo(); - TII = TM->getInstrInfo(); + TRI = MF->getSubtarget().getRegisterInfo(); + TII = MF->getSubtarget().getInstrInfo(); MRI->freezeReservedRegs(Fn); RegClassInfo.runOnMachineFunction(Fn); UsedInInstr.clear(); - UsedInInstr.setUniverse(TRI->getNumRegs()); + UsedInInstr.setUniverse(TRI->getNumRegUnits()); assert(!MRI->isSSA() && "regalloc requires leaving SSA"); @@ -1144,13 +1094,6 @@ bool RAFast::runOnMachineFunction(MachineFunction &Fn) { AllocateBasicBlock(); } - // Add the clobber lists for all the instructions we skipped earlier. - for (SmallPtrSet::const_iterator - I = SkippedInstrs.begin(), E = SkippedInstrs.end(); I != E; ++I) - if (const uint16_t *Defs = (*I)->getImplicitDefs()) - while (*Defs) - MRI->setPhysRegUsed(*Defs++); - // All machine operands and other references to virtual registers have been // replaced. Remove the virtual registers. MRI->clearVirtRegs();