X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocLocal.cpp;h=cbb5826ce9a144a6b0b6f4e584725dc3327d5cf5;hb=717ce2b8d81f0c12145248e92c37ee7547276ce2;hp=9fc5f738b4e474c1f1818eb1c6a3ee046ee72fde;hpb=5a3c6a87b0173b9d367f7b55e7c99e5110ede057;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocLocal.cpp b/lib/CodeGen/RegAllocLocal.cpp index 9fc5f738b4e..cbb5826ce9a 100644 --- a/lib/CodeGen/RegAllocLocal.cpp +++ b/lib/CodeGen/RegAllocLocal.cpp @@ -24,7 +24,8 @@ #include "llvm/Target/TargetMachine.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" -#include "llvm/Support/Compiler.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/IndexedMap.h" #include "llvm/ADT/SmallSet.h" @@ -42,7 +43,7 @@ static RegisterRegAlloc createLocalRegisterAllocator); namespace { - class VISIBILITY_HIDDEN RALocal : public MachineFunctionPass { + class RALocal : public MachineFunctionPass { public: static char ID; RALocal() : MachineFunctionPass(&ID), StackSlotForVirtReg(-1) {} @@ -151,6 +152,7 @@ namespace { } virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); AU.addRequiredID(PHIEliminationID); AU.addRequiredID(TwoAddressInstructionPassID); MachineFunctionPass::getAnalysisUsage(AU); @@ -226,19 +228,22 @@ namespace { unsigned getReg(MachineBasicBlock &MBB, MachineInstr *MI, unsigned VirtReg, bool NoFree = false); - /// reloadVirtReg - This method transforms the specified specified virtual + /// reloadVirtReg - This method transforms the specified virtual /// register use to refer to a physical register. This method may do this /// in one of several ways: if the register is available in a physical /// register already, it uses that physical register. If the value is not /// in a physical register, and if there are physical registers available, - /// it loads it into a register. If register pressure is high, and it is - /// possible, it tries to fold the load of the virtual register into the - /// instruction itself. It avoids doing this if register pressure is low to - /// improve the chance that subsequent instructions can use the reloaded - /// value. This method returns the modified instruction. + /// it loads it into a register: PhysReg if that is an available physical + /// register, otherwise any physical register of the right class. + /// If register pressure is high, and it is possible, it tries to fold the + /// load of the virtual register into the instruction itself. It avoids + /// doing this if register pressure is low to improve the chance that + /// subsequent instructions can use the reloaded value. This method + /// returns the modified instruction. /// MachineInstr *reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, - unsigned OpNum, SmallSet &RRegs); + unsigned OpNum, SmallSet &RRegs, + unsigned PhysReg); /// ComputeLocalLiveness - Computes liveness of registers within a basic /// block, setting the killed/dead flags as appropriate. @@ -259,8 +264,8 @@ int RALocal::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { return SS; // Already has space allocated? // Allocate a new stack object for this spill location... - int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC->getSize(), - RC->getAlignment()); + int FrameIdx = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(), + RC->getAlignment()); // Assign the slot... StackSlotForVirtReg[VirtReg] = FrameIdx; @@ -291,11 +296,11 @@ void RALocal::spillVirtReg(MachineBasicBlock &MBB, assert(VirtReg && "Spilling a physical register is illegal!" " Must not have appropriate kill for the register or use exists beyond" " the intended one."); - DOUT << " Spilling register " << TRI->getName(PhysReg) - << " containing %reg" << VirtReg; + DEBUG(dbgs() << " Spilling register " << TRI->getName(PhysReg) + << " containing %reg" << VirtReg); if (!isVirtRegModified(VirtReg)) { - DOUT << " which has not been modified, so no store necessary!"; + DEBUG(dbgs() << " which has not been modified, so no store necessary!"); std::pair &LastUse = getVirtRegLastUse(VirtReg); if (LastUse.first) LastUse.first->getOperand(LastUse.second).setIsKill(); @@ -305,7 +310,7 @@ void RALocal::spillVirtReg(MachineBasicBlock &MBB, // modified. const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); int FrameIndex = getStackSpaceFor(VirtReg, RC); - DOUT << " to stack slot #" << FrameIndex; + DEBUG(dbgs() << " to stack slot #" << FrameIndex); // If the instruction reads the register that's spilled, (e.g. this can // happen if it is a move to a physical register), then the spill // instruction is not a kill. @@ -316,7 +321,7 @@ void RALocal::spillVirtReg(MachineBasicBlock &MBB, getVirt2PhysRegMapSlot(VirtReg) = 0; // VirtReg no longer available - DOUT << "\n"; + DEBUG(dbgs() << '\n'); removePhysReg(PhysReg); } @@ -464,20 +469,22 @@ unsigned RALocal::getReg(MachineBasicBlock &MBB, MachineInstr *I, } -/// reloadVirtReg - This method transforms the specified specified virtual +/// reloadVirtReg - This method transforms the specified virtual /// register use to refer to a physical register. This method may do this in /// one of several ways: if the register is available in a physical register /// already, it uses that physical register. If the value is not in a physical /// register, and if there are physical registers available, it loads it into a +/// register: PhysReg if that is an available physical register, otherwise any /// register. If register pressure is high, and it is possible, it tries to /// fold the load of the virtual register into the instruction itself. It /// avoids doing this if register pressure is low to improve the chance that -/// subsequent instructions can use the reloaded value. This method returns the -/// modified instruction. +/// subsequent instructions can use the reloaded value. This method returns +/// the modified instruction. /// MachineInstr *RALocal::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, unsigned OpNum, - SmallSet &ReloadedRegs) { + SmallSet &ReloadedRegs, + unsigned PhysReg) { unsigned VirtReg = MI->getOperand(OpNum).getReg(); // If the virtual register is already available, just update the instruction @@ -492,7 +499,11 @@ MachineInstr *RALocal::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, // Otherwise, we need to fold it into the current instruction, or reload it. // If we have registers available to hold the value, use them. const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); - unsigned PhysReg = getFreeReg(RC); + // If we already have a PhysReg (this happens when the instruction is a + // reg-to-reg copy with a PhysReg destination) use that. + if (!PhysReg || !TargetRegisterInfo::isPhysicalRegister(PhysReg) || + !isPhysRegAvailable(PhysReg)) + PhysReg = getFreeReg(RC); int FrameIndex = getStackSpaceFor(VirtReg, RC); if (PhysReg) { // Register is available, allocate it! @@ -505,8 +516,8 @@ MachineInstr *RALocal::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, markVirtRegModified(VirtReg, false); // Note that this reg was just reloaded - DOUT << " Reloading %reg" << VirtReg << " into " - << TRI->getName(PhysReg) << "\n"; + DEBUG(dbgs() << " Reloading %reg" << VirtReg << " into " + << TRI->getName(PhysReg) << "\n"); // Add move instruction(s) TII->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex, RC); @@ -517,24 +528,28 @@ MachineInstr *RALocal::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, getVirtRegLastUse(VirtReg) = std::make_pair(MI, OpNum); if (!ReloadedRegs.insert(PhysReg)) { - cerr << "Ran out of registers during register allocation!\n"; + std::string msg; + raw_string_ostream Msg(msg); + Msg << "Ran out of registers during register allocation!"; if (MI->getOpcode() == TargetInstrInfo::INLINEASM) { - cerr << "Please check your inline asm statement for invalid " + Msg << "\nPlease check your inline asm statement for invalid " << "constraints:\n"; - MI->print(cerr.stream(), TM); + MI->print(Msg, TM); } - exit(1); + llvm_report_error(Msg.str()); } for (const unsigned *SubRegs = TRI->getSubRegisters(PhysReg); *SubRegs; ++SubRegs) { if (!ReloadedRegs.insert(*SubRegs)) { - cerr << "Ran out of registers during register allocation!\n"; + std::string msg; + raw_string_ostream Msg(msg); + Msg << "Ran out of registers during register allocation!"; if (MI->getOpcode() == TargetInstrInfo::INLINEASM) { - cerr << "Please check your inline asm statement for invalid " + Msg << "\nPlease check your inline asm statement for invalid " << "constraints:\n"; - MI->print(cerr.stream(), TM); + MI->print(Msg, TM); } - exit(1); + llvm_report_error(Msg.str()); } } @@ -633,7 +648,7 @@ void RALocal::ComputeLocalLiveness(MachineBasicBlock& MBB) { // Check if this is a two address instruction. If so, then // the def does not kill the use. if (last->second.first == I && - I->isRegReDefinedByTwoAddr(i)) + I->isRegTiedToUseOperand(i)) continue; MachineOperand& lastUD = @@ -695,7 +710,7 @@ void RALocal::ComputeLocalLiveness(MachineBasicBlock& MBB) { if (isPhysReg || !usedOutsideBlock) { if (MO.isUse()) { // Don't mark uses that are tied to defs as kills. - if (MI->getDesc().getOperandConstraint(idx, TOI::TIED_TO) == -1) + if (!MI->isRegTiedToDefOperand(idx)) MO.setIsKill(true); } else MO.setIsDead(true); @@ -707,27 +722,27 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { // loop over each instruction MachineBasicBlock::iterator MII = MBB.begin(); - DEBUG(const BasicBlock *LBB = MBB.getBasicBlock(); - if (LBB) DOUT << "\nStarting RegAlloc of BB: " << LBB->getName()); - - // If this is the first basic block in the machine function, add live-in - // registers as active. - if (&MBB == &*MF->begin() || MBB.isLandingPad()) { - for (MachineBasicBlock::livein_iterator I = MBB.livein_begin(), + DEBUG({ + const BasicBlock *LBB = MBB.getBasicBlock(); + if (LBB) + dbgs() << "\nStarting RegAlloc of BB: " << LBB->getName(); + }); + + // Add live-in registers as active. + for (MachineBasicBlock::livein_iterator I = MBB.livein_begin(), E = MBB.livein_end(); I != E; ++I) { - unsigned Reg = *I; - MF->getRegInfo().setPhysRegUsed(Reg); - PhysRegsUsed[Reg] = 0; // It is free and reserved now - AddToPhysRegsUseOrder(Reg); - for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); - *SubRegs; ++SubRegs) { - if (PhysRegsUsed[*SubRegs] != -2) { - AddToPhysRegsUseOrder(*SubRegs); - PhysRegsUsed[*SubRegs] = 0; // It is free and reserved now - MF->getRegInfo().setPhysRegUsed(*SubRegs); - } + unsigned Reg = *I; + MF->getRegInfo().setPhysRegUsed(Reg); + PhysRegsUsed[Reg] = 0; // It is free and reserved now + AddToPhysRegsUseOrder(Reg); + for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); + *SubRegs; ++SubRegs) { + if (PhysRegsUsed[*SubRegs] != -2) { + AddToPhysRegsUseOrder(*SubRegs); + PhysRegsUsed[*SubRegs] = 0; // It is free and reserved now + MF->getRegInfo().setPhysRegUsed(*SubRegs); } - } + } } ComputeLocalLiveness(MBB); @@ -736,13 +751,21 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { while (MII != MBB.end()) { MachineInstr *MI = MII++; const TargetInstrDesc &TID = MI->getDesc(); - DEBUG(DOUT << "\nStarting RegAlloc of: " << *MI; - DOUT << " Regs have values: "; - for (unsigned i = 0; i != TRI->getNumRegs(); ++i) - if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2) - DOUT << "[" << TRI->getName(i) - << ",%reg" << PhysRegsUsed[i] << "] "; - DOUT << "\n"); + DEBUG({ + dbgs() << "\nStarting RegAlloc of: " << *MI; + dbgs() << " Regs have values: "; + for (unsigned i = 0; i != TRI->getNumRegs(); ++i) + if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2) + dbgs() << "[" << TRI->getName(i) + << ",%reg" << PhysRegsUsed[i] << "] "; + dbgs() << '\n'; + }); + + // Determine whether this is a copy instruction. The cases where the + // source or destination are phys regs are handled specially. + unsigned SrcCopyReg, DstCopyReg, SrcCopySubReg, DstCopySubReg; + bool isCopy = TII->isMoveInstr(*MI, SrcCopyReg, DstCopyReg, + SrcCopySubReg, DstCopySubReg); // Loop over the implicit uses, making sure that they are at the head of the // use order list, so they don't get reallocated. @@ -786,8 +809,8 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { markVirtRegModified(DestVirtReg); getVirtRegLastUse(DestVirtReg) = std::make_pair((MachineInstr*)0, 0); - DOUT << " Assigning " << TRI->getName(DestPhysReg) - << " to %reg" << DestVirtReg << "\n"; + DEBUG(dbgs() << " Assigning " << TRI->getName(DestPhysReg) + << " to %reg" << DestVirtReg << "\n"); MO.setReg(DestPhysReg); // Assign the earlyclobber register } else { unsigned Reg = MO.getReg(); @@ -827,7 +850,8 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { // here we are looking for only used operands (never def&use) if (MO.isReg() && !MO.isDef() && MO.getReg() && !MO.isImplicit() && TargetRegisterInfo::isVirtualRegister(MO.getReg())) - MI = reloadVirtReg(MBB, MI, i, ReloadedRegs); + MI = reloadVirtReg(MBB, MI, i, ReloadedRegs, + isCopy ? DstCopyReg : 0); } // If this instruction is the last user of this register, kill the @@ -852,15 +876,15 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { } if (PhysReg) { - DOUT << " Last use of " << TRI->getName(PhysReg) - << "[%reg" << VirtReg <<"], removing it from live set\n"; + DEBUG(dbgs() << " Last use of " << TRI->getName(PhysReg) + << "[%reg" << VirtReg <<"], removing it from live set\n"); removePhysReg(PhysReg); for (const unsigned *SubRegs = TRI->getSubRegisters(PhysReg); *SubRegs; ++SubRegs) { if (PhysRegsUsed[*SubRegs] != -2) { - DOUT << " Last use of " - << TRI->getName(*SubRegs) - << "[%reg" << VirtReg <<"], removing it from live set\n"; + DEBUG(dbgs() << " Last use of " + << TRI->getName(*SubRegs) << "[%reg" << VirtReg + <<"], removing it from live set\n"); removePhysReg(*SubRegs); } } @@ -940,13 +964,22 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { unsigned DestPhysReg; // If DestVirtReg already has a value, use it. - if (!(DestPhysReg = getVirt2PhysRegMapSlot(DestVirtReg))) - DestPhysReg = getReg(MBB, MI, DestVirtReg); + if (!(DestPhysReg = getVirt2PhysRegMapSlot(DestVirtReg))) { + // If this is a copy, the source reg is a phys reg, and + // that reg is available, use that phys reg for DestPhysReg. + if (isCopy && + TargetRegisterInfo::isPhysicalRegister(SrcCopyReg) && + isPhysRegAvailable(SrcCopyReg)) { + DestPhysReg = SrcCopyReg; + assignVirtToPhysReg(DestVirtReg, DestPhysReg); + } else + DestPhysReg = getReg(MBB, MI, DestVirtReg); + } MF->getRegInfo().setPhysRegUsed(DestPhysReg); markVirtRegModified(DestVirtReg); getVirtRegLastUse(DestVirtReg) = std::make_pair((MachineInstr*)0, 0); - DOUT << " Assigning " << TRI->getName(DestPhysReg) - << " to %reg" << DestVirtReg << "\n"; + DEBUG(dbgs() << " Assigning " << TRI->getName(DestPhysReg) + << " to %reg" << DestVirtReg << "\n"); MO.setReg(DestPhysReg); // Assign the output register } } @@ -968,26 +1001,28 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { } if (PhysReg) { - DOUT << " Register " << TRI->getName(PhysReg) - << " [%reg" << VirtReg - << "] is never used, removing it from live set\n"; + DEBUG(dbgs() << " Register " << TRI->getName(PhysReg) + << " [%reg" << VirtReg + << "] is never used, removing it from live set\n"); removePhysReg(PhysReg); for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg); *AliasSet; ++AliasSet) { if (PhysRegsUsed[*AliasSet] != -2) { - DOUT << " Register " << TRI->getName(*AliasSet) - << " [%reg" << *AliasSet - << "] is never used, removing it from live set\n"; + DEBUG(dbgs() << " Register " << TRI->getName(*AliasSet) + << " [%reg" << *AliasSet + << "] is never used, removing it from live set\n"); removePhysReg(*AliasSet); } } } } - // Finally, if this is a noop copy instruction, zap it. - unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; - if (TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg) && - SrcReg == DstReg) + // Finally, if this is a noop copy instruction, zap it. (Except that if + // the copy is dead, it must be kept to avoid messing up liveness info for + // the register scavenger. See pr4100.) + if (TII->isMoveInstr(*MI, SrcCopyReg, DstCopyReg, + SrcCopySubReg, DstCopySubReg) && + SrcCopyReg == DstCopyReg && DeadDefs.empty()) MBB.erase(MI); } @@ -1023,7 +1058,7 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { /// runOnMachineFunction - Register allocate the whole function /// bool RALocal::runOnMachineFunction(MachineFunction &Fn) { - DOUT << "Machine Function " << "\n"; + DEBUG(dbgs() << "Machine Function\n"); MF = &Fn; TM = &Fn.getTarget(); TRI = TM->getRegisterInfo();