X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocBigBlock.cpp;h=91e4099d0c45761fea7ca9849b6d062d2984104b;hb=236aa8a5032282d8793b537c0f3f7ffb381a83d4;hp=7f402a62b817d751bcbee590a7d6fae7e297b99a;hpb=76c1b97e4020faace8c95a127f1eab66c278fb58;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocBigBlock.cpp b/lib/CodeGen/RegAllocBigBlock.cpp index 7f402a62b81..91e4099d0c4 100644 --- a/lib/CodeGen/RegAllocBigBlock.cpp +++ b/lib/CodeGen/RegAllocBigBlock.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by Duraid Madina and is distributed under the -// University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -32,8 +32,8 @@ #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" -#include "llvm/CodeGen/SSARegMap.h" #include "llvm/CodeGen/MachineFrameInfo.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/LiveVariables.h" #include "llvm/CodeGen/RegAllocRegistry.h" #include "llvm/Target/TargetInstrInfo.h" @@ -44,7 +44,6 @@ #include "llvm/ADT/IndexedMap.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" #include using namespace llvm; @@ -53,11 +52,11 @@ STATISTIC(NumStores, "Number of stores added"); STATISTIC(NumLoads , "Number of loads added"); STATISTIC(NumFolded, "Number of loads/stores folded into instructions"); -namespace { - static RegisterRegAlloc - bigBlockRegAlloc("bigblock", " Big-block register allocator", - createBigBlockRegisterAllocator); +static RegisterRegAlloc + bigBlockRegAlloc("bigblock", "Big-block register allocator", + createBigBlockRegisterAllocator); +namespace { /// VRegKeyInfo - Defines magic values required to use VirtRegs as DenseMap /// keys. struct VRegKeyInfo { @@ -83,7 +82,7 @@ namespace { class VISIBILITY_HIDDEN RABigBlock : public MachineFunctionPass { public: static char ID; - RABigBlock() : MachineFunctionPass((intptr_t)&ID) {} + RABigBlock() : MachineFunctionPass(&ID) {} private: /// TM - For getting at TargetMachine info /// @@ -95,11 +94,7 @@ namespace { /// RegInfo - For dealing with machine register info (aliases, folds /// etc) - const MRegisterInfo *RegInfo; - - /// LV - Our generic LiveVariables pointer - /// - LiveVariables *LV; + const TargetRegisterInfo *RegInfo; typedef SmallVector VRegTimes; @@ -156,8 +151,8 @@ namespace { /// markVirtRegModified - Lets us flip bits in the VirtRegModified bitset /// void markVirtRegModified(unsigned Reg, bool Val = true) { - assert(MRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); - Reg -= MRegisterInfo::FirstVirtualRegister; + assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); + Reg -= TargetRegisterInfo::FirstVirtualRegister; if (VirtRegModified.size() <= Reg) VirtRegModified.resize(Reg+1); VirtRegModified[Reg] = Val; @@ -166,10 +161,10 @@ namespace { /// isVirtRegModified - Lets us query the VirtRegModified bitset /// bool isVirtRegModified(unsigned Reg) const { - assert(MRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); - assert(Reg - MRegisterInfo::FirstVirtualRegister < VirtRegModified.size() + assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); + assert(Reg - TargetRegisterInfo::FirstVirtualRegister < VirtRegModified.size() && "Illegal virtual register!"); - return VirtRegModified[Reg - MRegisterInfo::FirstVirtualRegister]; + return VirtRegModified[Reg - TargetRegisterInfo::FirstVirtualRegister]; } public: @@ -182,7 +177,6 @@ namespace { /// getAnalaysisUsage - declares the required analyses /// virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(); AU.addRequiredID(PHIEliminationID); AU.addRequiredID(TwoAddressInstructionPassID); MachineFunctionPass::getAnalysisUsage(AU); @@ -319,6 +313,9 @@ void RABigBlock::spillVirtReg(MachineBasicBlock &MBB, " the intended one."); DOUT << " Spilling register " << RegInfo->getName(PhysReg) << " containing %reg" << VirtReg; + + const TargetInstrInfo* TII = MBB.getParent()->getTarget().getInstrInfo(); + if (!isVirtRegModified(VirtReg)) DOUT << " which has not been modified, so no store necessary!"; @@ -326,10 +323,10 @@ void RABigBlock::spillVirtReg(MachineBasicBlock &MBB, // register. We only need to spill it into its stack slot if it has been // modified. if (isVirtRegModified(VirtReg)) { - const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg); + const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); int FrameIndex = getStackSpaceFor(VirtReg, RC); DOUT << " to stack slot #" << FrameIndex; - RegInfo->storeRegToStackSlot(MBB, I, PhysReg, FrameIndex, RC); + TII->storeRegToStackSlot(MBB, I, PhysReg, true, FrameIndex, RC); ++NumStores; // Update statistics } @@ -388,7 +385,7 @@ bool RABigBlock::isPhysRegAvailable(unsigned PhysReg) const { // not free! for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg); *AliasSet; ++AliasSet) - if (PhysRegsUsed[*AliasSet] != -1) // Aliased register in use? + if (PhysRegsUsed[*AliasSet] >= 0) // Aliased register in use? return false; // Can't use this reg then. return true; } @@ -418,7 +415,7 @@ unsigned RABigBlock::getFreeReg(const TargetRegisterClass *RC) { /// unsigned RABigBlock::chooseReg(MachineBasicBlock &MBB, MachineInstr *I, unsigned VirtReg) { - const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg); + const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); // First check to see if we have a free register of the requested type... unsigned PhysReg = getFreeReg(RC); @@ -502,6 +499,7 @@ unsigned RABigBlock::chooseReg(MachineBasicBlock &MBB, MachineInstr *I, MachineInstr *RABigBlock::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, unsigned OpNum) { unsigned VirtReg = MI->getOperand(OpNum).getReg(); + const TargetInstrInfo* TII = MBB.getParent()->getTarget().getInstrInfo(); // If the virtual register is already available in a physical register, // just update the instruction and return. @@ -512,7 +510,7 @@ MachineInstr *RABigBlock::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI // Otherwise, if we have free physical registers available to hold the // value, use them. - const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg); + const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); unsigned PhysReg = getFreeReg(RC); int FrameIndex = getStackSpaceFor(VirtReg, RC); @@ -520,11 +518,11 @@ MachineInstr *RABigBlock::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI assignVirtToPhysReg(VirtReg, PhysReg); } else { // no free registers available. // try to fold the spill into the instruction - if(MachineInstr* FMI = RegInfo->foldMemoryOperand(MI, OpNum, FrameIndex)) { + SmallVector Ops; + Ops.push_back(OpNum); + if(MachineInstr* FMI = TII->foldMemoryOperand(*MF, MI, Ops, FrameIndex)) { ++NumFolded; - // Since we changed the address of MI, make sure to update live variables - // to know that the new instruction has the properties of the old one. - LV->instructionChanged(MI, FMI); + FMI->copyKillDeadInfo(MI); return MBB.insert(MBB.erase(MI), FMI); } @@ -540,10 +538,10 @@ MachineInstr *RABigBlock::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI << RegInfo->getName(PhysReg) << "\n"; // Add move instruction(s) - RegInfo->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex, RC); + TII->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex, RC); ++NumLoads; // Update statistics - MF->setPhysRegUsed(PhysReg); + MF->getRegInfo().setPhysRegUsed(PhysReg); MI->getOperand(OpNum).setReg(PhysReg); // Assign the input register return MI; } @@ -562,8 +560,8 @@ void RABigBlock::FillVRegReadTable(MachineBasicBlock &MBB) { for (unsigned i = 0; i != MI->getNumOperands(); ++i) { MachineOperand& MO = MI->getOperand(i); // look for vreg reads.. - if (MO.isRegister() && !MO.isDef() && MO.getReg() && - MRegisterInfo::isVirtualRegister(MO.getReg())) { + if (MO.isReg() && !MO.isDef() && MO.getReg() && + TargetRegisterInfo::isVirtualRegister(MO.getReg())) { // ..and add them to the read table. VRegTimes* &Times = VRegReadTable[MO.getReg()]; if(!VRegReadTable[MO.getReg()]) { @@ -591,7 +589,7 @@ void RABigBlock::FillVRegReadTable(MachineBasicBlock &MBB) { static bool isReadModWriteImplicitKill(MachineInstr *MI, unsigned Reg) { for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand& MO = MI->getOperand(i); - if (MO.isRegister() && MO.getReg() == Reg && MO.isImplicit() && + if (MO.isReg() && MO.getReg() == Reg && MO.isImplicit() && MO.isDef() && !MO.isDead()) return true; } @@ -603,7 +601,7 @@ static bool isReadModWriteImplicitKill(MachineInstr *MI, unsigned Reg) { static bool isReadModWriteImplicitDef(MachineInstr *MI, unsigned Reg) { for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand& MO = MI->getOperand(i); - if (MO.isRegister() && MO.getReg() == Reg && MO.isImplicit() && + if (MO.isReg() && MO.getReg() == Reg && MO.isImplicit() && !MO.isDef() && MO.isKill()) return true; } @@ -622,16 +620,17 @@ void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { // If this is the first basic block in the machine function, add live-in // registers as active. if (&MBB == &*MF->begin()) { - for (MachineFunction::livein_iterator I = MF->livein_begin(), - E = MF->livein_end(); I != E; ++I) { + for (MachineRegisterInfo::livein_iterator + I = MF->getRegInfo().livein_begin(), + E = MF->getRegInfo().livein_end(); I != E; ++I) { unsigned Reg = I->first; - MF->setPhysRegUsed(Reg); + MF->getRegInfo().setPhysRegUsed(Reg); PhysRegsUsed[Reg] = 0; // It is free and reserved now for (const unsigned *AliasSet = RegInfo->getSubRegisters(Reg); *AliasSet; ++AliasSet) { if (PhysRegsUsed[*AliasSet] != -2) { PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now - MF->setPhysRegUsed(*AliasSet); + MF->getRegInfo().setPhysRegUsed(*AliasSet); } } } @@ -642,7 +641,7 @@ void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { while (MII != MBB.end()) { MachineInstr *MI = MII++; MBBCurTime++; - const TargetInstrDescriptor &TID = TII.get(MI->getOpcode()); + const TargetInstrDesc &TID = MI->getDesc(); DEBUG(DOUT << "\nTime=" << MBBCurTime << " Starting RegAlloc of: " << *MI; DOUT << " Regs have values: "; for (unsigned i = 0; i != RegInfo->getNumRegs(); ++i) @@ -654,7 +653,7 @@ void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { SmallVector Kills; for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand& MO = MI->getOperand(i); - if (MO.isRegister() && MO.isKill()) { + if (MO.isReg() && MO.isKill()) { if (!MO.isImplicit()) Kills.push_back(MO.getReg()); else if (!isReadModWriteImplicitKill(MI, MO.getReg())) @@ -674,8 +673,8 @@ void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { for (unsigned i = 0; i != MI->getNumOperands(); ++i) { MachineOperand& MO = MI->getOperand(i); // here we are looking for only used operands (never def&use) - if (MO.isRegister() && !MO.isDef() && MO.getReg() && !MO.isImplicit() && - MRegisterInfo::isVirtualRegister(MO.getReg())) + if (MO.isReg() && !MO.isDef() && MO.getReg() && !MO.isImplicit() && + TargetRegisterInfo::isVirtualRegister(MO.getReg())) MI = reloadVirtReg(MBB, MI, i); } @@ -686,7 +685,7 @@ void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { for (unsigned i = 0, e = Kills.size(); i != e; ++i) { unsigned VirtReg = Kills[i]; unsigned PhysReg = VirtReg; - if (MRegisterInfo::isVirtualRegister(VirtReg)) { + if (TargetRegisterInfo::isVirtualRegister(VirtReg)) { // If the virtual register was never materialized into a register, it // might not be in the map, but it won't hurt to zero it out anyway. unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg); @@ -696,7 +695,7 @@ void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { // Unallocatable register dead, ignore. continue; } else { - assert(!PhysRegsUsed[PhysReg] || PhysRegsUsed[PhysReg] == -1 && + assert((!PhysRegsUsed[PhysReg] || PhysRegsUsed[PhysReg] == -1) && "Silently clearing a virtual register?"); } @@ -720,8 +719,8 @@ void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { // are defined, and marking explicit destinations in the PhysRegsUsed map. for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand& MO = MI->getOperand(i); - if (MO.isRegister() && MO.isDef() && !MO.isImplicit() && MO.getReg() && - MRegisterInfo::isPhysicalRegister(MO.getReg())) { + if (MO.isReg() && MO.isDef() && !MO.isImplicit() && MO.getReg() && + TargetRegisterInfo::isPhysicalRegister(MO.getReg())) { unsigned Reg = MO.getReg(); if (PhysRegsUsed[Reg] == -2) continue; // Something like ESP. // These are extra physical register defs when a sub-register @@ -729,34 +728,34 @@ void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { // larger registers). Ignore. if (isReadModWriteImplicitDef(MI, MO.getReg())) continue; - MF->setPhysRegUsed(Reg); + MF->getRegInfo().setPhysRegUsed(Reg); spillPhysReg(MBB, MI, Reg, true); // Spill any existing value in reg PhysRegsUsed[Reg] = 0; // It is free and reserved now for (const unsigned *AliasSet = RegInfo->getSubRegisters(Reg); *AliasSet; ++AliasSet) { if (PhysRegsUsed[*AliasSet] != -2) { PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now - MF->setPhysRegUsed(*AliasSet); + MF->getRegInfo().setPhysRegUsed(*AliasSet); } } } } // Loop over the implicit defs, spilling them as well. - if (TID.ImplicitDefs) { - for (const unsigned *ImplicitDefs = TID.ImplicitDefs; + if (TID.getImplicitDefs()) { + for (const unsigned *ImplicitDefs = TID.getImplicitDefs(); *ImplicitDefs; ++ImplicitDefs) { unsigned Reg = *ImplicitDefs; if (PhysRegsUsed[Reg] != -2) { spillPhysReg(MBB, MI, Reg, true); PhysRegsUsed[Reg] = 0; // It is free and reserved now } - MF->setPhysRegUsed(Reg); + MF->getRegInfo().setPhysRegUsed(Reg); for (const unsigned *AliasSet = RegInfo->getSubRegisters(Reg); *AliasSet; ++AliasSet) { if (PhysRegsUsed[*AliasSet] != -2) { PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now - MF->setPhysRegUsed(*AliasSet); + MF->getRegInfo().setPhysRegUsed(*AliasSet); } } } @@ -765,7 +764,7 @@ void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { SmallVector DeadDefs; for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand& MO = MI->getOperand(i); - if (MO.isRegister() && MO.isDead()) + if (MO.isReg() && MO.isDead()) DeadDefs.push_back(MO.getReg()); } @@ -776,15 +775,15 @@ void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { // for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand& MO = MI->getOperand(i); - if (MO.isRegister() && MO.isDef() && MO.getReg() && - MRegisterInfo::isVirtualRegister(MO.getReg())) { + if (MO.isReg() && MO.isDef() && MO.getReg() && + TargetRegisterInfo::isVirtualRegister(MO.getReg())) { unsigned DestVirtReg = MO.getReg(); unsigned DestPhysReg; // If DestVirtReg already has a value, use it. if (!(DestPhysReg = getVirt2PhysRegMapSlot(DestVirtReg))) DestPhysReg = chooseReg(MBB, MI, DestVirtReg); - MF->setPhysRegUsed(DestPhysReg); + MF->getRegInfo().setPhysRegUsed(DestPhysReg); markVirtRegModified(DestVirtReg); MI->getOperand(i).setReg(DestPhysReg); // Assign the output register } @@ -796,7 +795,7 @@ void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { for (unsigned i = 0, e = DeadDefs.size(); i != e; ++i) { unsigned VirtReg = DeadDefs[i]; unsigned PhysReg = VirtReg; - if (MRegisterInfo::isVirtualRegister(VirtReg)) { + if (TargetRegisterInfo::isVirtualRegister(VirtReg)) { unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg); PhysReg = PhysRegSlot; assert(PhysReg != 0); @@ -809,14 +808,14 @@ void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { if (PhysReg) { DOUT << " Register " << RegInfo->getName(PhysReg) << " [%reg" << VirtReg - << "] is never used, removing it frame live list\n"; + << "] is never used, removing it from live set\n"; removePhysReg(PhysReg); for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg); *AliasSet; ++AliasSet) { if (PhysRegsUsed[*AliasSet] != -2) { DOUT << " Register " << RegInfo->getName(*AliasSet) << " [%reg" << *AliasSet - << "] is never used, removing it frame live list\n"; + << "] is never used, removing it from live set\n"; removePhysReg(*AliasSet); } } @@ -824,23 +823,22 @@ void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { } // Finally, if this is a noop copy instruction, zap it. - unsigned SrcReg, DstReg; - if (TII.isMoveInstr(*MI, SrcReg, DstReg) && SrcReg == DstReg) { - LV->removeVirtualRegistersKilled(MI); - LV->removeVirtualRegistersDead(MI); + unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; + if (TII.isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg) && + SrcReg == DstReg) MBB.erase(MI); - } } MachineBasicBlock::iterator MI = MBB.getFirstTerminator(); // Spill all physical registers holding virtual registers now. for (unsigned i = 0, e = RegInfo->getNumRegs(); i != e; ++i) - if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2) + if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2) { if (unsigned VirtReg = PhysRegsUsed[i]) spillVirtReg(MBB, MI, VirtReg, i); else removePhysReg(i); + } } /// runOnMachineFunction - Register allocate the whole function @@ -850,7 +848,6 @@ bool RABigBlock::runOnMachineFunction(MachineFunction &Fn) { MF = &Fn; TM = &Fn.getTarget(); RegInfo = TM->getRegisterInfo(); - LV = &getAnalysis(); PhysRegsUsed.assign(RegInfo->getNumRegs(), -1); @@ -866,9 +863,10 @@ bool RABigBlock::runOnMachineFunction(MachineFunction &Fn) { // initialize the virtual->physical register map to have a 'null' // mapping for all virtual registers - Virt2PhysRegMap.grow(MF->getSSARegMap()->getLastVirtReg()); - StackSlotForVirtReg.grow(MF->getSSARegMap()->getLastVirtReg()); - VirtRegModified.resize(MF->getSSARegMap()->getLastVirtReg() - MRegisterInfo::FirstVirtualRegister + 1,0); + Virt2PhysRegMap.grow(MF->getRegInfo().getLastVirtReg()); + StackSlotForVirtReg.grow(MF->getRegInfo().getLastVirtReg()); + VirtRegModified.resize(MF->getRegInfo().getLastVirtReg() - + TargetRegisterInfo::FirstVirtualRegister + 1, 0); // Loop over all of the basic blocks, eliminating virtual register references for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();