X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocLocal.cpp;h=4d2e3a318b4f3126d846bb569dfe30b23a65e235;hb=86020e46289643de2f8c7603b550ffc8b6aff376;hp=b3d320a914f94fed5d05dabff8769e4a0258323f;hpb=ce63ffb52f249b62cdf2d250c128007b13f27e71;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocLocal.cpp b/lib/CodeGen/RegAllocLocal.cpp index b3d320a914f..4d2e3a318b4 100644 --- a/lib/CodeGen/RegAllocLocal.cpp +++ b/lib/CodeGen/RegAllocLocal.cpp @@ -24,7 +24,6 @@ #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" @@ -44,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) {} @@ -153,6 +152,7 @@ namespace { } virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); AU.addRequiredID(PHIEliminationID); AU.addRequiredID(TwoAddressInstructionPassID); MachineFunctionPass::getAnalysisUsage(AU); @@ -233,14 +233,17 @@ namespace { /// 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. @@ -261,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; @@ -293,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(); @@ -307,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. @@ -318,7 +321,7 @@ void RALocal::spillVirtReg(MachineBasicBlock &MBB, getVirt2PhysRegMapSlot(VirtReg) = 0; // VirtReg no longer available - DOUT << "\n"; + DEBUG(dbgs() << '\n'); removePhysReg(PhysReg); } @@ -471,15 +474,17 @@ unsigned RALocal::getReg(MachineBasicBlock &MBB, MachineInstr *I, /// 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 @@ -494,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! @@ -507,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); @@ -522,7 +531,7 @@ MachineInstr *RALocal::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, std::string msg; raw_string_ostream Msg(msg); Msg << "Ran out of registers during register allocation!"; - if (MI->getOpcode() == TargetInstrInfo::INLINEASM) { + if (MI->isInlineAsm()) { Msg << "\nPlease check your inline asm statement for invalid " << "constraints:\n"; MI->print(Msg, TM); @@ -535,7 +544,7 @@ MachineInstr *RALocal::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, std::string msg; raw_string_ostream Msg(msg); Msg << "Ran out of registers during register allocation!"; - if (MI->getOpcode() == TargetInstrInfo::INLINEASM) { + if (MI->isInlineAsm()) { Msg << "\nPlease check your inline asm statement for invalid " << "constraints:\n"; MI->print(Msg, TM); @@ -713,8 +722,11 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { // loop over each instruction MachineBasicBlock::iterator MII = MBB.begin(); - DEBUG(const BasicBlock *LBB = MBB.getBasicBlock(); - if (LBB) errs() << "\nStarting RegAlloc of BB: " << LBB->getName()); + 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(), @@ -739,13 +751,24 @@ 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; + unsigned SrcCopyPhysReg = 0U; + bool isCopy = TII->isMoveInstr(*MI, SrcCopyReg, DstCopyReg, + SrcCopySubReg, DstCopySubReg); + if (isCopy && TargetRegisterInfo::isVirtualRegister(SrcCopyReg)) + SrcCopyPhysReg = getVirt2PhysRegMapSlot(SrcCopyReg); // Loop over the implicit uses, making sure that they are at the head of the // use order list, so they don't get reallocated. @@ -773,7 +796,7 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { // have in them, then mark them unallocatable. // If any virtual regs are earlyclobber, allocate them now (before // freeing inputs that are killed). - if (MI->getOpcode()==TargetInstrInfo::INLINEASM) { + if (MI->isInlineAsm()) { for (unsigned i = 0; i != MI->getNumOperands(); ++i) { MachineOperand& MO = MI->getOperand(i); if (MO.isReg() && MO.isDef() && MO.isEarlyClobber() && @@ -789,8 +812,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(); @@ -818,6 +841,18 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { } } + // If a DBG_VALUE says something is located in a spilled register, + // change the DBG_VALUE to be undef, which prevents the register + // from being reloaded here. Doing that would change the generated + // code, unless another use immediately follows this instruction. + if (MI->isDebugValue() && + MI->getNumOperands()==3 && MI->getOperand(0).isReg()) { + unsigned VirtReg = MI->getOperand(0).getReg(); + if (VirtReg && TargetRegisterInfo::isVirtualRegister(VirtReg) && + !getVirt2PhysRegMapSlot(VirtReg)) + MI->getOperand(0).setReg(0U); + } + // Get the used operands into registers. This has the potential to spill // incoming values if we are out of registers. Note that we completely // ignore physical register uses here. We assume that if an explicit @@ -830,7 +865,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 @@ -855,15 +891,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); } } @@ -943,13 +979,35 @@ 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 try to reuse the input as the output; + // that will make the copy go away. + // If this is a copy, the source reg is a phys reg, and + // that reg is available, use that phys reg for DestPhysReg. + // If this is a copy, the source reg is a virtual reg, and + // the phys reg that was assigned to that virtual reg is now + // available, use that phys reg for DestPhysReg. (If it's now + // available that means this was the last use of the source.) + if (isCopy && + TargetRegisterInfo::isPhysicalRegister(SrcCopyReg) && + isPhysRegAvailable(SrcCopyReg)) { + DestPhysReg = SrcCopyReg; + assignVirtToPhysReg(DestVirtReg, DestPhysReg); + } else if (isCopy && + TargetRegisterInfo::isVirtualRegister(SrcCopyReg) && + SrcCopyPhysReg && isPhysRegAvailable(SrcCopyPhysReg) && + MF->getRegInfo().getRegClass(DestVirtReg)-> + contains(SrcCopyPhysReg)) { + DestPhysReg = SrcCopyPhysReg; + 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 } } @@ -971,16 +1029,16 @@ 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); } } @@ -990,9 +1048,9 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { // 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.) - unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; - if (TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg) && - SrcReg == DstReg && DeadDefs.empty()) + if (TII->isMoveInstr(*MI, SrcCopyReg, DstCopyReg, + SrcCopySubReg, DstCopySubReg) && + SrcCopyReg == DstCopyReg && DeadDefs.empty()) MBB.erase(MI); } @@ -1028,7 +1086,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();