X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FStrongPHIElimination.cpp;h=b337c5393343b0cd11bcd0b41f2841c6eb2ceb1f;hb=fe532525cc4912ec0d1b4e91fa0396122dd087b3;hp=5c70423cceccb980a95750866dc1de066771d59b;hpb=7c8818630991855830c94c79e1035222f3749689;p=oota-llvm.git diff --git a/lib/CodeGen/StrongPHIElimination.cpp b/lib/CodeGen/StrongPHIElimination.cpp index 5c70423ccec..b337c539334 100644 --- a/lib/CodeGen/StrongPHIElimination.cpp +++ b/lib/CodeGen/StrongPHIElimination.cpp @@ -39,15 +39,17 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "strongphielim" -#include "PHIEliminationUtils.h" #include "llvm/CodeGen/Passes.h" +#include "PHIEliminationUtils.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/Statistic.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/Target/TargetInstrInfo.h" #include "llvm/Support/Debug.h" +#include "llvm/Target/TargetInstrInfo.h" using namespace llvm; namespace { @@ -89,7 +91,15 @@ namespace { /// Add a register in a new congruence class containing only itself. void addReg(unsigned); - /// Join the congruence classes of two registers. + /// Join the congruence classes of two registers. This function is biased + /// towards the left argument, i.e. after + /// + /// addReg(r2); + /// unionRegs(r1, r2); + /// + /// the leader of the unioned congruence class is the same as the leader of + /// r1's congruence class prior to the union. This is actually relied upon + /// in the copy insertion code. void unionRegs(unsigned, unsigned); /// Get the color of a register. The color is 0 if the register has been @@ -179,6 +189,10 @@ namespace { }; } // namespace +STATISTIC(NumPHIsLowered, "Number of PHIs lowered"); +STATISTIC(NumDestCopiesInserted, "Number of destination copies inserted"); +STATISTIC(NumSrcCopiesInserted, "Number of source copies inserted"); + char StrongPHIElimination::ID = 0; INITIALIZE_PASS_BEGIN(StrongPHIElimination, "strong-phi-node-elimination", "Eliminate PHI nodes for register allocation, intelligently", false, false) @@ -214,7 +228,6 @@ static MachineOperand *findLastUse(MachineBasicBlock *MBB, unsigned Reg) { return &MO; } } - return NULL; } bool StrongPHIElimination::runOnMachineFunction(MachineFunction &MF) { @@ -376,12 +389,10 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction &MF) { MachineOperand *LastUse = findLastUse(MBB, SrcReg); assert(LastUse); SlotIndex LastUseIndex = LI->getInstructionIndex(LastUse->getParent()); - SrcLI.removeRange(LastUseIndex.getDefIndex(), LI->getMBBEndIdx(MBB)); + SrcLI.removeRange(LastUseIndex.getRegSlot(), LI->getMBBEndIdx(MBB)); LastUse->setIsKill(true); } - LI->renumber(); - Allocator.Reset(); RegNodeMap.clear(); PHISrcDefs.clear(); @@ -393,9 +404,9 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction &MF) { } void StrongPHIElimination::addReg(unsigned Reg) { - if (RegNodeMap.count(Reg)) - return; - RegNodeMap[Reg] = new (Allocator) Node(Reg); + Node *&N = RegNodeMap[Reg]; + if (!N) + N = new (Allocator) Node(Reg); } StrongPHIElimination::Node* @@ -543,7 +554,8 @@ StrongPHIElimination::SplitInterferencesForBasicBlock( // handle it here by tracking defining machine instructions rather than // virtual registers. For now, we just handle the situation conservatively // in a way that will possibly lead to false interferences. - unsigned NewParent = CurrentDominatingParent[DestColor]; + unsigned &CurrentParent = CurrentDominatingParent[DestColor]; + unsigned NewParent = CurrentParent; if (NewParent == DestReg) continue; @@ -562,18 +574,18 @@ StrongPHIElimination::SplitInterferencesForBasicBlock( // could be improved by using a heuristic that decides which of the two // registers to isolate. isolateReg(DestReg); - CurrentDominatingParent[DestColor] = NewParent; + CurrentParent = NewParent; } else { // If there is no interference, update ImmediateDominatingParent and set // the CurrentDominatingParent for this color to the current register. ImmediateDominatingParent[DestReg] = NewParent; - CurrentDominatingParent[DestColor] = DestReg; + CurrentParent = DestReg; } } } // We now walk the PHIs in successor blocks and check for interferences. This - // is necesary because the use of a PHI's operands are logically contained in + // is necessary because the use of a PHI's operands are logically contained in // the predecessor block. The def of a PHI's destination register is processed // along with the other defs in a basic block. @@ -602,12 +614,13 @@ StrongPHIElimination::SplitInterferencesForBasicBlock( // Pop registers from the stack represented by ImmediateDominatingParent // until we find a parent that dominates the current instruction. - unsigned NewParent = CurrentDominatingParent[Color]; + unsigned &CurrentParent = CurrentDominatingParent[Color]; + unsigned NewParent = CurrentParent; while (NewParent && (!DT->dominates(MRI->getVRegDef(NewParent)->getParent(), &MBB) || !getRegColor(NewParent))) NewParent = ImmediateDominatingParent[NewParent]; - CurrentDominatingParent[Color] = NewParent; + CurrentParent = NewParent; // If there is an interference with a register, always isolate the // register rather than the PHI. It is also possible to isolate the @@ -617,7 +630,8 @@ StrongPHIElimination::SplitInterferencesForBasicBlock( && NewParent != PredOperandReg) isolateReg(NewParent); - std::pair CurrentPHI = CurrentPHIForColor[Color]; + std::pair + &CurrentPHI = CurrentPHIForColor[Color]; // If two PHIs have the same operand from every shared predecessor, then // they don't actually interfere. Otherwise, isolate the current PHI. This @@ -626,7 +640,7 @@ StrongPHIElimination::SplitInterferencesForBasicBlock( if (CurrentPHI.first && CurrentPHI.second != PredOperandReg) isolatePHI(PHI); else - CurrentPHIForColor[Color] = std::make_pair(PHI, PredOperandReg); + CurrentPHI = std::make_pair(PHI, PredOperandReg); } } } @@ -634,6 +648,7 @@ StrongPHIElimination::SplitInterferencesForBasicBlock( void StrongPHIElimination::InsertCopiesForPHI(MachineInstr *PHI, MachineBasicBlock *MBB) { assert(PHI->isPHI()); + ++NumPHIsLowered; unsigned PHIColor = getPHIColor(PHI); for (unsigned i = 1; i < PHI->getNumOperands(); i += 2) { @@ -656,9 +671,9 @@ void StrongPHIElimination::InsertCopiesForPHI(MachineInstr *PHI, if (PHIColor && SrcColor == PHIColor) { LiveInterval &SrcInterval = LI->getInterval(SrcReg); SlotIndex PredIndex = LI->getMBBEndIdx(PredBB); - VNInfo *SrcVNI = SrcInterval.getVNInfoAt(PredIndex.getPrevIndex()); + VNInfo *SrcVNI = SrcInterval.getVNInfoBefore(PredIndex); + (void)SrcVNI; assert(SrcVNI); - SrcVNI->setHasPHIKill(true); continue; } @@ -683,6 +698,7 @@ void StrongPHIElimination::InsertCopiesForPHI(MachineInstr *PHI, TII->get(TargetOpcode::COPY), CopyReg).addReg(SrcReg, 0, SrcSubReg); LI->InsertMachineInstrInMaps(CopyInstr); + ++NumSrcCopiesInserted; // addLiveRangeToEndOfBlock() also adds the phikill flag to the VNInfo for // the newly added range. @@ -698,8 +714,9 @@ void StrongPHIElimination::InsertCopiesForPHI(MachineInstr *PHI, assert(getRegColor(CopyReg) == CopyReg); } - if (!InsertedSrcCopyMap.count(std::make_pair(PredBB, PHIColor))) - InsertedSrcCopyMap[std::make_pair(PredBB, PHIColor)] = CopyInstr; + // Insert into map if not already there. + InsertedSrcCopyMap.insert(std::make_pair(std::make_pair(PredBB, PHIColor), + CopyInstr)); } SrcMO.setReg(CopyReg); @@ -726,9 +743,8 @@ void StrongPHIElimination::InsertCopiesForPHI(MachineInstr *PHI, // Set the phi-def flag for the VN at this PHI. SlotIndex PHIIndex = LI->getInstructionIndex(PHI); - VNInfo *DestVNI = DestLI.getVNInfoAt(PHIIndex.getDefIndex()); + VNInfo *DestVNI = DestLI.getVNInfoAt(PHIIndex.getRegSlot()); assert(DestVNI); - DestVNI->setIsPHIDef(true); // Prior to PHI elimination, the live ranges of PHIs begin at their defining // instruction. After PHI elimination, PHI instructions are replaced by VNs @@ -737,7 +753,7 @@ void StrongPHIElimination::InsertCopiesForPHI(MachineInstr *PHI, SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB); DestVNI->def = MBBStartIndex; DestLI.addRange(LiveRange(MBBStartIndex, - PHIIndex.getDefIndex(), + PHIIndex.getRegSlot(), DestVNI)); return; } @@ -752,6 +768,7 @@ void StrongPHIElimination::InsertCopiesForPHI(MachineInstr *PHI, DestReg).addReg(CopyReg); LI->InsertMachineInstrInMaps(CopyInstr); PHI->getOperand(0).setReg(CopyReg); + ++NumDestCopiesInserted; // Add the region from the beginning of MBB to the copy instruction to // CopyReg's live interval, and give the VNInfo the phidef flag. @@ -759,22 +776,20 @@ void StrongPHIElimination::InsertCopiesForPHI(MachineInstr *PHI, SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB); SlotIndex DestCopyIndex = LI->getInstructionIndex(CopyInstr); VNInfo *CopyVNI = CopyLI.getNextValue(MBBStartIndex, - CopyInstr, LI->getVNInfoAllocator()); - CopyVNI->setIsPHIDef(true); CopyLI.addRange(LiveRange(MBBStartIndex, - DestCopyIndex.getDefIndex(), + DestCopyIndex.getRegSlot(), CopyVNI)); // Adjust DestReg's live interval to adjust for its new definition at // CopyInstr. LiveInterval &DestLI = LI->getOrCreateInterval(DestReg); SlotIndex PHIIndex = LI->getInstructionIndex(PHI); - DestLI.removeRange(PHIIndex.getDefIndex(), DestCopyIndex.getDefIndex()); + DestLI.removeRange(PHIIndex.getRegSlot(), DestCopyIndex.getRegSlot()); - VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getDefIndex()); + VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getRegSlot()); assert(DestVNI); - DestVNI->def = DestCopyIndex.getDefIndex(); + DestVNI->def = DestCopyIndex.getRegSlot(); InsertedDestCopies[CopyReg] = CopyInstr; }