X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FStrongPHIElimination.cpp;h=0bf6f8e4c2384daad8a1cb1644477deac2a79fac;hb=081c34b725980f995be9080eaec24cd3dfaaf065;hp=a2c12554f37744672944234e881c3a884b385aa2;hpb=f41538d1b54f55e8900394929b50f7ce3e61125f;p=oota-llvm.git diff --git a/lib/CodeGen/StrongPHIElimination.cpp b/lib/CodeGen/StrongPHIElimination.cpp index a2c12554f37..0bf6f8e4c23 100644 --- a/lib/CodeGen/StrongPHIElimination.cpp +++ b/lib/CodeGen/StrongPHIElimination.cpp @@ -25,6 +25,7 @@ #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/RegisterCoalescer.h" @@ -32,14 +33,15 @@ #include "llvm/Target/TargetMachine.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/Statistic.h" -#include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" using namespace llvm; namespace { - struct VISIBILITY_HIDDEN StrongPHIElimination : public MachineFunctionPass { + struct StrongPHIElimination : public MachineFunctionPass { static char ID; // Pass identification, replacement for typeid - StrongPHIElimination() : MachineFunctionPass(&ID) {} + StrongPHIElimination() : MachineFunctionPass(ID) { + initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry()); + } // Waiting stores, for each MBB, the set of copies that need to // be inserted into that MBB @@ -50,7 +52,7 @@ namespace { std::map > Stacks; // Registers in UsedByAnother are PHI nodes that are themselves - // used as operands to another another PHI node + // used as operands to another PHI node std::set UsedByAnother; // RenameSets are the is a map from a PHI-defined register @@ -71,7 +73,10 @@ namespace { bool runOnMachineFunction(MachineFunction &Fn); virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); AU.addRequired(); + AU.addRequired(); + AU.addPreserved(); AU.addRequired(); // TODO: Actually make this true. @@ -147,11 +152,15 @@ namespace { } char StrongPHIElimination::ID = 0; -static RegisterPass -X("strong-phi-node-elimination", - "Eliminate PHI nodes for register allocation, intelligently"); +INITIALIZE_PASS_BEGIN(StrongPHIElimination, "strong-phi-node-elimination", + "Eliminate PHI nodes for register allocation, intelligently", false, false) +INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) +INITIALIZE_PASS_DEPENDENCY(SlotIndexes) +INITIALIZE_PASS_DEPENDENCY(LiveIntervals) +INITIALIZE_PASS_END(StrongPHIElimination, "strong-phi-node-elimination", + "Eliminate PHI nodes for register allocation, intelligently", false, false) -const PassInfo *const llvm::StrongPHIEliminationID = &X; +char &llvm::StrongPHIEliminationID = StrongPHIElimination::ID; /// computeDFS - Computes the DFS-in and DFS-out numbers of the dominator tree /// of the given MachineFunction. These numbers are then used in other parts @@ -294,7 +303,7 @@ StrongPHIElimination::computeDomForest( static bool isLiveIn(unsigned r, MachineBasicBlock* MBB, LiveIntervals& LI) { LiveInterval& I = LI.getOrCreateInterval(r); - unsigned idx = LI.getMBBStartIdx(MBB); + SlotIndex idx = LI.getMBBStartIdx(MBB); return I.liveAt(idx); } @@ -417,7 +426,7 @@ void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) { // Iterate over all the PHI nodes in this block MachineBasicBlock::iterator P = MBB->begin(); - while (P != MBB->end() && P->getOpcode() == TargetInstrInfo::PHI) { + while (P != MBB->end() && P->isPHI()) { unsigned DestReg = P->getOperand(0).getReg(); // Don't both doing PHI elimination for dead PHI's. @@ -427,7 +436,7 @@ void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) { } LiveInterval& PI = LI.getOrCreateInterval(DestReg); - unsigned pIdx = LI.getDefIndex(LI.getInstructionIndex(P)); + SlotIndex pIdx = LI.getInstructionIndex(P).getDefIndex(); VNInfo* PVN = PI.getLiveRangeContaining(pIdx)->valno; PhiValueNumber.insert(std::make_pair(DestReg, PVN->id)); @@ -450,7 +459,7 @@ void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) { // We don't need to insert copies for implicit_defs. MachineInstr* DefMI = MRI.getVRegDef(SrcReg); - if (DefMI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) + if (DefMI->isImplicitDef()) ProcessedNames.insert(SrcReg); // Check for trivial interferences via liveness information, allowing us @@ -468,7 +477,7 @@ void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) { if (isLiveIn(SrcReg, P->getParent(), LI) || isLiveOut(P->getOperand(0).getReg(), MRI.getVRegDef(SrcReg)->getParent(), LI) || - ( MRI.getVRegDef(SrcReg)->getOpcode() == TargetInstrInfo::PHI && + ( MRI.getVRegDef(SrcReg)->isPHI() && isLiveIn(P->getOperand(0).getReg(), MRI.getVRegDef(SrcReg)->getParent(), LI) ) || ProcessedNames.count(SrcReg) || @@ -553,8 +562,8 @@ void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) { // Add the renaming set for this PHI node to our overall renaming information for (std::map::iterator QI = PHIUnion.begin(), QE = PHIUnion.end(); QI != QE; ++QI) { - DOUT << "Adding Renaming: " << QI->first << " -> " - << P->getOperand(0).getReg() << "\n"; + DEBUG(dbgs() << "Adding Renaming: " << QI->first << " -> " + << P->getOperand(0).getReg() << "\n"); } RenameSets.insert(std::make_pair(P->getOperand(0).getReg(), PHIUnion)); @@ -693,10 +702,10 @@ void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB, // Insert copy from curr.second to a temporary at // the Phi defining curr.second MachineBasicBlock::iterator PI = MRI.getVRegDef(curr.second); - TII->copyRegToReg(*PI->getParent(), PI, t, - curr.second, RC, RC); - - DOUT << "Inserted copy from " << curr.second << " to " << t << "\n"; + BuildMI(*PI->getParent(), PI, DebugLoc(), TII->get(TargetOpcode::COPY), + t).addReg(curr.second); + DEBUG(dbgs() << "Inserted copy from " << curr.second << " to " << t + << "\n"); // Push temporary on Stacks Stacks[curr.second].push_back(t); @@ -709,11 +718,11 @@ void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB, } // Insert copy from map[curr.first] to curr.second - TII->copyRegToReg(*MBB, MBB->getFirstTerminator(), curr.second, - map[curr.first], RC, RC); + BuildMI(*MBB, MBB->getFirstTerminator(), DebugLoc(), + TII->get(TargetOpcode::COPY), curr.second).addReg(map[curr.first]); map[curr.first] = curr.second; - DOUT << "Inserted copy from " << curr.first << " to " - << curr.second << "\n"; + DEBUG(dbgs() << "Inserted copy from " << curr.first << " to " + << curr.second << "\n"); // Push this copy onto InsertedPHICopies so we can // update LiveIntervals with it. @@ -746,7 +755,7 @@ void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB, LiveInterval& I = LI.getInterval(curr.second); MachineBasicBlock::iterator term = MBB->getFirstTerminator(); - unsigned endIdx = 0; + SlotIndex endIdx = SlotIndex(); if (term != MBB->end()) endIdx = LI.getInstructionIndex(term); else @@ -758,8 +767,8 @@ void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB, // Insert a copy from dest to a new temporary t at the end of b unsigned t = MF->getRegInfo().createVirtualRegister(RC); - TII->copyRegToReg(*MBB, MBB->getFirstTerminator(), t, - curr.second, RC, RC); + BuildMI(*MBB, MBB->getFirstTerminator(), DebugLoc(), + TII->get(TargetOpcode::COPY), t).addReg(curr.second); map[curr.second] = t; MachineBasicBlock::iterator TI = MBB->getFirstTerminator(); @@ -770,7 +779,7 @@ void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB, // Renumber the instructions so that we can perform the index computations // needed to create new live intervals. - LI.computeNumbering(); + LI.renumber(); // For copies that we inserted at the ends of predecessors, we construct // live intervals. This is pretty easy, since we know that the destination @@ -782,16 +791,15 @@ void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB, InsertedPHIDests.begin(), E = InsertedPHIDests.end(); I != E; ++I) { if (RegHandled.insert(I->first).second) { LiveInterval& Int = LI.getOrCreateInterval(I->first); - unsigned instrIdx = LI.getInstructionIndex(I->second); - if (Int.liveAt(LiveIntervals::getDefIndex(instrIdx))) - Int.removeRange(LiveIntervals::getDefIndex(instrIdx), - LI.getMBBEndIdx(I->second->getParent())+1, + SlotIndex instrIdx = LI.getInstructionIndex(I->second); + if (Int.liveAt(instrIdx.getDefIndex())) + Int.removeRange(instrIdx.getDefIndex(), + LI.getMBBEndIdx(I->second->getParent()).getNextSlot(), true); LiveRange R = LI.addLiveRangeToEndOfBlock(I->first, I->second); - R.valno->copy = I->second; - R.valno->def = - LiveIntervals::getDefIndex(LI.getInstructionIndex(I->second)); + R.valno->setCopy(I->second); + R.valno->def = LI.getInstructionIndex(I->second).getDefIndex(); } } } @@ -808,7 +816,7 @@ void StrongPHIElimination::InsertCopies(MachineDomTreeNode* MDTN, // Rewrite register uses from Stacks for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ++I) { - if (I->getOpcode() == TargetInstrInfo::PHI) + if (I->isPHI()) continue; for (unsigned i = 0; i < I->getNumOperands(); ++i) @@ -816,8 +824,8 @@ void StrongPHIElimination::InsertCopies(MachineDomTreeNode* MDTN, Stacks[I->getOperand(i).getReg()].size()) { // Remove the live range for the old vreg. LiveInterval& OldInt = LI.getInterval(I->getOperand(i).getReg()); - LiveInterval::iterator OldLR = OldInt.FindLiveRangeContaining( - LiveIntervals::getUseIndex(LI.getInstructionIndex(I))); + LiveInterval::iterator OldLR = + OldInt.FindLiveRangeContaining(LI.getInstructionIndex(I).getUseIndex()); if (OldLR != OldInt.end()) OldInt.removeRange(*OldLR, true); @@ -827,13 +835,9 @@ void StrongPHIElimination::InsertCopies(MachineDomTreeNode* MDTN, // Add a live range for the new vreg LiveInterval& Int = LI.getInterval(I->getOperand(i).getReg()); VNInfo* FirstVN = *Int.vni_begin(); - FirstVN->hasPHIKill = false; - if (I->getOperand(i).isKill()) - FirstVN->kills.push_back( - LiveIntervals::getUseIndex(LI.getInstructionIndex(I))); - + FirstVN->setHasPHIKill(false); LiveRange LR (LI.getMBBStartIdx(I->getParent()), - LiveIntervals::getUseIndex(LI.getInstructionIndex(I))+1, + LI.getInstructionIndex(I).getUseIndex().getNextSlot(), FirstVN); Int.addRange(LR); @@ -862,14 +866,14 @@ bool StrongPHIElimination::mergeLiveIntervals(unsigned primary, LiveInterval& LHS = LI.getOrCreateInterval(primary); LiveInterval& RHS = LI.getOrCreateInterval(secondary); - LI.computeNumbering(); + LI.renumber(); DenseMap VNMap; for (LiveInterval::iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { LiveRange R = *I; - unsigned Start = R.start; - unsigned End = R.end; + SlotIndex Start = R.start; + SlotIndex End = R.end; if (LHS.getLiveRangeContaining(Start)) return false; @@ -886,10 +890,7 @@ bool StrongPHIElimination::mergeLiveIntervals(unsigned primary, VNInfo* OldVN = R.valno; VNInfo*& NewVN = VNMap[OldVN]; if (!NewVN) { - NewVN = LHS.getNextValue(OldVN->def, - OldVN->copy, - LI.getVNInfoAllocator()); - NewVN->kills = OldVN->kills; + NewVN = LHS.createValueCopy(OldVN, LI.getVNInfoAllocator()); } LiveRange LR (R.start, R.end, NewVN); @@ -909,8 +910,7 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) { // Determine which phi node operands need copies for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) - if (!I->empty() && - I->begin()->getOpcode() == TargetInstrInfo::PHI) + if (!I->empty() && I->begin()->isPHI()) processBlock(I); // Break interferences where two different phis want to coalesce @@ -930,7 +930,8 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) { unsigned reg = OI->first; ++OI; I->second.erase(reg); - DOUT << "Removing Renaming: " << reg << " -> " << I->first << "\n"; + DEBUG(dbgs() << "Removing Renaming: " << reg << " -> " << I->first + << "\n"); } } } @@ -947,7 +948,7 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) { while (I->second.size()) { std::map::iterator SI = I->second.begin(); - DOUT << "Renaming: " << SI->first << " -> " << I->first << "\n"; + DEBUG(dbgs() << "Renaming: " << SI->first << " -> " << I->first << "\n"); if (SI->first != I->first) { if (mergeLiveIntervals(I->first, SI->first)) { @@ -961,33 +962,32 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) { } else { // Insert a last-minute copy if a conflict was detected. const TargetInstrInfo *TII = Fn.getTarget().getInstrInfo(); - const TargetRegisterClass *RC = Fn.getRegInfo().getRegClass(I->first); - TII->copyRegToReg(*SI->second, SI->second->getFirstTerminator(), - I->first, SI->first, RC, RC); + BuildMI(*SI->second, SI->second->getFirstTerminator(), DebugLoc(), + TII->get(TargetOpcode::COPY), I->first).addReg(SI->first); - LI.computeNumbering(); + LI.renumber(); LiveInterval& Int = LI.getOrCreateInterval(I->first); - unsigned instrIdx = + SlotIndex instrIdx = LI.getInstructionIndex(--SI->second->getFirstTerminator()); - if (Int.liveAt(LiveIntervals::getDefIndex(instrIdx))) - Int.removeRange(LiveIntervals::getDefIndex(instrIdx), - LI.getMBBEndIdx(SI->second)+1, true); + if (Int.liveAt(instrIdx.getDefIndex())) + Int.removeRange(instrIdx.getDefIndex(), + LI.getMBBEndIdx(SI->second).getNextSlot(), true); LiveRange R = LI.addLiveRangeToEndOfBlock(I->first, --SI->second->getFirstTerminator()); - R.valno->copy = --SI->second->getFirstTerminator(); - R.valno->def = LiveIntervals::getDefIndex(instrIdx); + R.valno->setCopy(--SI->second->getFirstTerminator()); + R.valno->def = instrIdx.getDefIndex(); - DOUT << "Renaming failed: " << SI->first << " -> " - << I->first << "\n"; + DEBUG(dbgs() << "Renaming failed: " << SI->first << " -> " + << I->first << "\n"); } } LiveInterval& Int = LI.getOrCreateInterval(I->first); const LiveRange* LR = Int.getLiveRangeContaining(LI.getMBBEndIdx(SI->second)); - LR->valno->hasPHIKill = true; + LR->valno->setHasPHIKill(true); I->second.erase(SI->first); } @@ -997,7 +997,7 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) { for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) { for (MachineBasicBlock::iterator BI = I->begin(), BE = I->end(); BI != BE; ++BI) - if (BI->getOpcode() == TargetInstrInfo::PHI) + if (BI->isPHI()) phis.push_back(BI); } @@ -1012,7 +1012,7 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) { if (PI.containsOneValue()) { LI.removeInterval(DestReg); } else { - unsigned idx = LI.getDefIndex(LI.getInstructionIndex(PInstr)); + SlotIndex idx = LI.getInstructionIndex(PInstr).getDefIndex(); PI.removeRange(*PI.getLiveRangeContaining(idx), true); } } else { @@ -1026,8 +1026,7 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) { LiveInterval& InputI = LI.getInterval(reg); if (MBB != PInstr->getParent() && InputI.liveAt(LI.getMBBStartIdx(PInstr->getParent())) && - InputI.expiredAt(LI.getInstructionIndex(PInstr) + - LiveInterval::InstrSlots::NUM)) + InputI.expiredAt(LI.getInstructionIndex(PInstr).getNextIndex())) InputI.removeRange(LI.getMBBStartIdx(PInstr->getParent()), LI.getInstructionIndex(PInstr), true); @@ -1035,9 +1034,9 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) { // If the PHI is not dead, then the valno defined by the PHI // now has an unknown def. - unsigned idx = LI.getDefIndex(LI.getInstructionIndex(PInstr)); + SlotIndex idx = LI.getInstructionIndex(PInstr).getDefIndex(); const LiveRange* PLR = PI.getLiveRangeContaining(idx); - PLR->valno->def = ~0U; + PLR->valno->setIsPHIDef(true); LiveRange R (LI.getMBBStartIdx(PInstr->getParent()), PLR->start, PLR->valno); PI.addRange(R); @@ -1047,7 +1046,7 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) { PInstr->eraseFromParent(); } - LI.computeNumbering(); + LI.renumber(); return true; }