X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FStrongPHIElimination.cpp;h=5d7bc23694bf9100f033c606e0b892690ba79bf6;hb=a29c13086a3add78a3a79f744573fe09eaa9dc88;hp=0c785367168c270f338656c9b69607749cd4ec9e;hpb=bc91bd34f1d2e4fdfef691fbe9015eabdeec8071;p=oota-llvm.git diff --git a/lib/CodeGen/StrongPHIElimination.cpp b/lib/CodeGen/StrongPHIElimination.cpp index 0c785367168..5d7bc23694b 100644 --- a/lib/CodeGen/StrongPHIElimination.cpp +++ b/lib/CodeGen/StrongPHIElimination.cpp @@ -27,23 +27,24 @@ #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/RegisterCoalescer.h" #include "llvm/Target/TargetInstrInfo.h" #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 { static char ID; // Pass identification, replacement for typeid - StrongPHIElimination() : MachineFunctionPass((intptr_t)&ID) {} + StrongPHIElimination() : MachineFunctionPass(&ID) {} // Waiting stores, for each MBB, the set of copies that need to // be inserted into that MBB DenseMap > Waiting; + std::multimap > Waiting; // Stacks holds the renaming stack for each register std::map > Stacks; @@ -52,9 +53,10 @@ namespace { // used as operands to another another PHI node std::set UsedByAnother; - // RenameSets are the sets of operands (and their VNInfo IDs) to a PHI - // (the defining instruction of the key) that can be renamed without copies. - std::map > RenameSets; + // RenameSets are the is a map from a PHI-defined register + // to the input registers to be coalesced along with the + // predecessor block for those input registers. + std::map > RenameSets; // PhiValueNumber holds the ID numbers of the VNs for each phi that we're // eliminating, indexed by the register defined by that phi. @@ -74,6 +76,7 @@ namespace { // TODO: Actually make this true. AU.addPreserved(); + AU.addPreserved(); MachineFunctionPass::getAnalysisUsage(AU); } @@ -129,24 +132,26 @@ namespace { void computeDFS(MachineFunction& MF); void processBlock(MachineBasicBlock* MBB); - std::vector computeDomForest(std::map& instrs, + std::vector computeDomForest( + std::map& instrs, MachineRegisterInfo& MRI); void processPHIUnion(MachineInstr* Inst, - std::map& PHIUnion, + std::map& PHIUnion, std::vector& DF, std::vector >& locals); void ScheduleCopies(MachineBasicBlock* MBB, std::set& pushed); - void InsertCopies(MachineBasicBlock* MBB, + void InsertCopies(MachineDomTreeNode* MBB, SmallPtrSet& v); - void mergeLiveIntervals(unsigned primary, unsigned secondary, unsigned VN); + bool mergeLiveIntervals(unsigned primary, unsigned secondary); }; - - char StrongPHIElimination::ID = 0; - RegisterPass X("strong-phi-node-elimination", - "Eliminate PHI nodes for register allocation, intelligently"); } -const PassInfo *llvm::StrongPHIEliminationID = X.getPassInfo(); +char StrongPHIElimination::ID = 0; +static RegisterPass +X("strong-phi-node-elimination", + "Eliminate PHI nodes for register allocation, intelligently"); + +const PassInfo *const llvm::StrongPHIEliminationID = &X; /// 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 @@ -192,6 +197,8 @@ void StrongPHIElimination::computeDFS(MachineFunction& MF) { } } +namespace { + /// PreorderSorter - a helper class that is used to sort registers /// according to the preorder number of their defining blocks class PreorderSorter { @@ -219,10 +226,13 @@ public: } }; +} + /// computeDomForest - compute the subforest of the DomTree corresponding /// to the defining blocks of the registers in question std::vector -StrongPHIElimination::computeDomForest(std::map& regs, +StrongPHIElimination::computeDomForest( + std::map& regs, MachineRegisterInfo& MRI) { // Begin by creating a virtual root node, since the actual results // may well be a forest. Assume this node has maximum DFS-out number. @@ -232,8 +242,8 @@ StrongPHIElimination::computeDomForest(std::map& regs, // Populate a worklist with the registers std::vector worklist; worklist.reserve(regs.size()); - for (std::map::iterator I = regs.begin(), E = regs.end(); - I != E; ++I) + for (std::map::iterator I = regs.begin(), + E = regs.end(); I != E; ++I) worklist.push_back(I->first); // Sort the registers by the DFS-in number of their defining block @@ -285,7 +295,7 @@ static bool isLiveIn(unsigned r, MachineBasicBlock* MBB, LiveIntervals& LI) { LiveInterval& I = LI.getOrCreateInterval(r); unsigned idx = LI.getMBBStartIdx(MBB); - return I.liveBeforeAndAt(idx); + return I.liveAt(idx); } /// isLiveOut - help method that determines, from a regno, if a register is @@ -293,10 +303,9 @@ static bool isLiveIn(unsigned r, MachineBasicBlock* MBB, static bool isLiveOut(unsigned r, MachineBasicBlock* MBB, LiveIntervals& LI) { for (MachineBasicBlock::succ_iterator PI = MBB->succ_begin(), - E = MBB->succ_end(); PI != E; ++PI) { + E = MBB->succ_end(); PI != E; ++PI) if (isLiveIn(r, *PI, LI)) return true; - } return false; } @@ -408,9 +417,9 @@ void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) { // Iterate over all the PHI nodes in this block MachineBasicBlock::iterator P = MBB->begin(); - while (P->getOpcode() == TargetInstrInfo::PHI) { + while (P != MBB->end() && P->getOpcode() == TargetInstrInfo::PHI) { unsigned DestReg = P->getOperand(0).getReg(); - + // Don't both doing PHI elimination for dead PHI's. if (P->registerDefIsDead(DestReg)) { ++P; @@ -426,12 +435,23 @@ void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) { // are going to be renames rather than having copies inserted. This set // is refinded over the course of this function. UnionedBlocks is the set // of corresponding MBBs. - std::map PHIUnion; + std::map PHIUnion; SmallPtrSet UnionedBlocks; // Iterate over the operands of the PHI node for (int i = P->getNumOperands() - 1; i >= 2; i-=2) { unsigned SrcReg = P->getOperand(i-1).getReg(); + + // Don't need to try to coalesce a register with itself. + if (SrcReg == DestReg) { + ProcessedNames.insert(SrcReg); + continue; + } + + // We don't need to insert copies for implicit_defs. + MachineInstr* DefMI = MRI.getVRegDef(SrcReg); + if (DefMI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) + ProcessedNames.insert(SrcReg); // Check for trivial interferences via liveness information, allowing us // to avoid extra work later. Any registers that interfere cannot both @@ -460,13 +480,7 @@ void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) { UsedByAnother.insert(SrcReg); } else { // Otherwise, add it to the renaming set - LiveInterval& I = LI.getOrCreateInterval(SrcReg); - unsigned idx = LI.getMBBEndIdx(P->getOperand(i).getMBB()); - VNInfo* VN = I.getLiveRangeContaining(idx)->valno; - - assert(VN && "No VNInfo for register?"); - - PHIUnion.insert(std::make_pair(SrcReg, VN->id)); + PHIUnion.insert(std::make_pair(SrcReg,P->getOperand(i).getMBB())); UnionedBlocks.insert(MRI.getVRegDef(SrcReg)->getParent()); } } @@ -483,8 +497,17 @@ void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) { std::vector > localInterferences; processPHIUnion(P, PHIUnion, DF, localInterferences); + // If one of the inputs is defined in the same block as the current PHI + // then we need to check for a local interference between that input and + // the PHI. + for (std::map::iterator I = PHIUnion.begin(), + E = PHIUnion.end(); I != E; ++I) + if (MRI.getVRegDef(I->first)->getParent() == P->getParent()) + localInterferences.push_back(std::make_pair(I->first, + P->getOperand(0).getReg())); + // The dominator forest walk may have returned some register pairs whose - // interference cannot be determines from dominator analysis. We now + // interference cannot be determined from dominator analysis. We now // examine these pairs for local interferences. for (std::vector >::iterator I = localInterferences.begin(), E = localInterferences.end(); I != E; ++I) { @@ -527,12 +550,18 @@ void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) { } } - // Add the renaming set for this PHI node to our overal renaming information + // 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"; + } + RenameSets.insert(std::make_pair(P->getOperand(0).getReg(), PHIUnion)); // Remember which registers are already renamed, so that we don't try to // rename them for another PHI node in this block - for (std::map::iterator I = PHIUnion.begin(), + for (std::map::iterator I = PHIUnion.begin(), E = PHIUnion.end(); I != E; ++I) ProcessedNames.insert(I->first); @@ -545,7 +574,7 @@ void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) { /// that are known to interfere, and flag others that need to be checked for /// local interferences. void StrongPHIElimination::processPHIUnion(MachineInstr* Inst, - std::map& PHIUnion, + std::map& PHIUnion, std::vector& DF, std::vector >& locals) { @@ -617,14 +646,14 @@ void StrongPHIElimination::processPHIUnion(MachineInstr* Inst, /// of Static Single Assignment Form" by Briggs, et al. void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB, std::set& pushed) { - // FIXME: This function needs to update LiveVariables - std::map& copy_set= Waiting[MBB]; + // FIXME: This function needs to update LiveIntervals + std::multimap& copy_set= Waiting[MBB]; - std::map worklist; + std::multimap worklist; std::map map; // Setup worklist of initial copies - for (std::map::iterator I = copy_set.begin(), + for (std::multimap::iterator I = copy_set.begin(), E = copy_set.end(); I != E; ) { map.insert(std::make_pair(I->first, I->first)); map.insert(std::make_pair(I->second, I->second)); @@ -633,9 +662,9 @@ void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB, worklist.insert(*I); // Avoid iterator invalidation - unsigned first = I->first; + std::multimap::iterator OI = I; ++I; - copy_set.erase(first); + copy_set.erase(OI); } else { ++I; } @@ -646,11 +675,14 @@ void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB, MachineRegisterInfo& MRI = MF->getRegInfo(); const TargetInstrInfo *TII = MF->getTarget().getInstrInfo(); + SmallVector, 4> InsertedPHIDests; + // Iterate over the worklist, inserting copies while (!worklist.empty() || !copy_set.empty()) { while (!worklist.empty()) { - std::pair curr = *worklist.begin(); - worklist.erase(curr.first); + std::multimap::iterator WI = worklist.begin(); + std::pair curr = *WI; + worklist.erase(WI); const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(curr.first); @@ -664,28 +696,41 @@ void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB, TII->copyRegToReg(*PI->getParent(), PI, t, curr.second, RC, RC); + DOUT << "Inserted copy from " << curr.second << " to " << t << "\n"; + // Push temporary on Stacks Stacks[curr.second].push_back(t); // Insert curr.second in pushed pushed.insert(curr.second); + + // Create a live interval for this temporary + InsertedPHIDests.push_back(std::make_pair(t, --PI)); } // Insert copy from map[curr.first] to curr.second TII->copyRegToReg(*MBB, MBB->getFirstTerminator(), curr.second, map[curr.first], RC, RC); map[curr.first] = curr.second; + DOUT << "Inserted copy from " << curr.first << " to " + << curr.second << "\n"; + + // Push this copy onto InsertedPHICopies so we can + // update LiveIntervals with it. + MachineBasicBlock::iterator MI = MBB->getFirstTerminator(); + InsertedPHIDests.push_back(std::make_pair(curr.second, --MI)); // If curr.first is a destination in copy_set... - for (std::map::iterator I = copy_set.begin(), + for (std::multimap::iterator I = copy_set.begin(), E = copy_set.end(); I != E; ) if (curr.first == I->second) { std::pair temp = *I; + worklist.insert(temp); // Avoid iterator invalidation + std::multimap::iterator OI = I; ++I; - copy_set.erase(temp.first); - worklist.insert(temp); + copy_set.erase(OI); break; } else { @@ -694,46 +739,114 @@ void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB, } if (!copy_set.empty()) { - std::pair curr = *copy_set.begin(); - copy_set.erase(curr.first); + std::multimap::iterator CI = copy_set.begin(); + std::pair curr = *CI; + worklist.insert(curr); + copy_set.erase(CI); - const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(curr.first); + LiveInterval& I = LI.getInterval(curr.second); + MachineBasicBlock::iterator term = MBB->getFirstTerminator(); + unsigned endIdx = 0; + if (term != MBB->end()) + endIdx = LI.getInstructionIndex(term); + else + endIdx = LI.getMBBEndIdx(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); - map[curr.second] = t; + if (I.liveAt(endIdx)) { + const TargetRegisterClass *RC = + MF->getRegInfo().getRegClass(curr.first); + + // 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); + map[curr.second] = t; + + MachineBasicBlock::iterator TI = MBB->getFirstTerminator(); + InsertedPHIDests.push_back(std::make_pair(t, --TI)); + } + } + } + + // Renumber the instructions so that we can perform the index computations + // needed to create new live intervals. + LI.computeNumbering(); + + // For copies that we inserted at the ends of predecessors, we construct + // live intervals. This is pretty easy, since we know that the destination + // register cannot have be in live at that point previously. We just have + // to make sure that, for registers that serve as inputs to more than one + // PHI, we don't create multiple overlapping live intervals. + std::set RegHandled; + for (SmallVector, 4>::iterator I = + 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, + true); - worklist.insert(curr); + LiveRange R = LI.addLiveRangeToEndOfBlock(I->first, I->second); + R.valno->copy = I->second; + R.valno->def = + LiveIntervals::getDefIndex(LI.getInstructionIndex(I->second)); } } } /// InsertCopies - insert copies into MBB and all of its successors -void StrongPHIElimination::InsertCopies(MachineBasicBlock* MBB, +void StrongPHIElimination::InsertCopies(MachineDomTreeNode* MDTN, SmallPtrSet& visited) { + MachineBasicBlock* MBB = MDTN->getBlock(); visited.insert(MBB); std::set pushed; + LiveIntervals& LI = getAnalysis(); // Rewrite register uses from Stacks for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); - I != E; ++I) + I != E; ++I) { + if (I->getOpcode() == TargetInstrInfo::PHI) + continue; + for (unsigned i = 0; i < I->getNumOperands(); ++i) - if (I->getOperand(i).isRegister() && + if (I->getOperand(i).isReg() && 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))); + if (OldLR != OldInt.end()) + OldInt.removeRange(*OldLR, true); + + // Change the register I->getOperand(i).setReg(Stacks[I->getOperand(i).getReg()].back()); + + // 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))); + + LiveRange LR (LI.getMBBStartIdx(I->getParent()), + LiveIntervals::getUseIndex(LI.getInstructionIndex(I))+1, + FirstVN); + + Int.addRange(LR); } + } // Schedule the copies for this block ScheduleCopies(MBB, pushed); - // Recur to our successors - for (GraphTraits::ChildIteratorType I = - GraphTraits::child_begin(MBB), E = - GraphTraits::child_end(MBB); I != E; ++I) - if (!visited.count(*I)) + // Recur down the dominator tree. + for (MachineDomTreeNode::iterator I = MDTN->begin(), + E = MDTN->end(); I != E; ++I) + if (!visited.count((*I)->getBlock())) InsertCopies(*I, visited); // As we exit this block, pop the names we pushed while processing it @@ -742,110 +855,53 @@ void StrongPHIElimination::InsertCopies(MachineBasicBlock* MBB, Stacks[*I].pop_back(); } -/// ComputeUltimateVN - Assuming we are going to join two live intervals, -/// compute what the resultant value numbers for each value in the input two -/// ranges will be. This is complicated by copies between the two which can -/// and will commonly cause multiple value numbers to be merged into one. -/// -/// VN is the value number that we're trying to resolve. InstDefiningValue -/// keeps track of the new InstDefiningValue assignment for the result -/// LiveInterval. ThisFromOther/OtherFromThis are sets that keep track of -/// whether a value in this or other is a copy from the opposite set. -/// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have -/// already been assigned. -/// -/// ThisFromOther[x] - If x is defined as a copy from the other interval, this -/// contains the value number the copy is from. -/// -static unsigned ComputeUltimateVN(VNInfo *VNI, - SmallVector &NewVNInfo, - DenseMap &ThisFromOther, - DenseMap &OtherFromThis, - SmallVector &ThisValNoAssignments, - SmallVector &OtherValNoAssignments) { - unsigned VN = VNI->id; - - // If the VN has already been computed, just return it. - if (ThisValNoAssignments[VN] >= 0) - return ThisValNoAssignments[VN]; -// assert(ThisValNoAssignments[VN] != -2 && "Cyclic case?"); - - // If this val is not a copy from the other val, then it must be a new value - // number in the destination. - DenseMap::iterator I = ThisFromOther.find(VNI); - if (I == ThisFromOther.end()) { - NewVNInfo.push_back(VNI); - return ThisValNoAssignments[VN] = NewVNInfo.size()-1; - } - VNInfo *OtherValNo = I->second; - - // Otherwise, this *is* a copy from the RHS. If the other side has already - // been computed, return it. - if (OtherValNoAssignments[OtherValNo->id] >= 0) - return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo->id]; - - // Mark this value number as currently being computed, then ask what the - // ultimate value # of the other value is. - ThisValNoAssignments[VN] = -2; - unsigned UltimateVN = - ComputeUltimateVN(OtherValNo, NewVNInfo, OtherFromThis, ThisFromOther, - OtherValNoAssignments, ThisValNoAssignments); - return ThisValNoAssignments[VN] = UltimateVN; -} - -void StrongPHIElimination::mergeLiveIntervals(unsigned primary, - unsigned secondary, - unsigned secondaryVN) { +bool StrongPHIElimination::mergeLiveIntervals(unsigned primary, + unsigned secondary) { LiveIntervals& LI = getAnalysis(); LiveInterval& LHS = LI.getOrCreateInterval(primary); LiveInterval& RHS = LI.getOrCreateInterval(secondary); - // Compute the final value assignment, assuming that the live ranges can be - // coalesced. - SmallVector LHSValNoAssignments; - SmallVector RHSValNoAssignments; - SmallVector NewVNInfo; + LI.computeNumbering(); - LHSValNoAssignments.resize(LHS.getNumValNums(), -1); - RHSValNoAssignments.resize(RHS.getNumValNums(), -1); - NewVNInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums()); - - for (LiveInterval::vni_iterator I = LHS.vni_begin(), E = LHS.vni_end(); - I != E; ++I) { - VNInfo *VNI = *I; - unsigned VN = VNI->id; - if (LHSValNoAssignments[VN] >= 0 || VNI->def == ~1U) - continue; + 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; + if (LHS.getLiveRangeContaining(Start)) + return false; + + if (LHS.getLiveRangeContaining(End)) + return false; - NewVNInfo.push_back(VNI); - LHSValNoAssignments[VN] = NewVNInfo.size()-1; + LiveInterval::iterator RI = std::upper_bound(LHS.begin(), LHS.end(), R); + if (RI != LHS.end() && RI->start < End) + return false; } - for (LiveInterval::vni_iterator I = RHS.vni_begin(), E = RHS.vni_end(); - I != E; ++I) { - VNInfo *VNI = *I; - unsigned VN = VNI->id; - if (RHSValNoAssignments[VN] >= 0 || VNI->def == ~1U) - continue; - - NewVNInfo.push_back(VNI); - RHSValNoAssignments[VN] = NewVNInfo.size()-1; + for (LiveInterval::iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { + LiveRange R = *I; + VNInfo* OldVN = R.valno; + VNInfo*& NewVN = VNMap[OldVN]; + if (!NewVN) { + NewVN = LHS.getNextValue(OldVN->def, + OldVN->copy, + LI.getVNInfoAllocator()); + NewVN->kills = OldVN->kills; + } + + LiveRange LR (R.start, R.end, NewVN); + LHS.addRange(LR); } - - // If we get here, we know that we can coalesce the live ranges. Ask the - // intervals to coalesce themselves now. - - LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo); - LI.removeInterval(secondary); - // The valno that was previously the input to the PHI node - // now has a PHIKill. - LHS.getValNumInfo(RHSValNoAssignments[secondaryVN])->hasPHIKill = true; + LI.removeInterval(RHS.reg); + + return true; } bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) { - LiveIntervals& LI = getAnalysis(); // Compute DFS numbers of each block @@ -857,23 +913,85 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) { I->begin()->getOpcode() == TargetInstrInfo::PHI) processBlock(I); + // Break interferences where two different phis want to coalesce + // in the same register. + std::set seen; + typedef std::map > + RenameSetType; + for (RenameSetType::iterator I = RenameSets.begin(), E = RenameSets.end(); + I != E; ++I) { + for (std::map::iterator + OI = I->second.begin(), OE = I->second.end(); OI != OE; ) { + if (!seen.count(OI->first)) { + seen.insert(OI->first); + ++OI; + } else { + Waiting[OI->second].insert(std::make_pair(OI->first, I->first)); + unsigned reg = OI->first; + ++OI; + I->second.erase(reg); + DOUT << "Removing Renaming: " << reg << " -> " << I->first << "\n"; + } + } + } + // Insert copies - // FIXME: This process should probably preserve LiveVariables + // FIXME: This process should probably preserve LiveIntervals SmallPtrSet visited; - InsertCopies(Fn.begin(), visited); + MachineDominatorTree& MDT = getAnalysis(); + InsertCopies(MDT.getRootNode(), visited); // Perform renaming - typedef std::map > RenameSetType; for (RenameSetType::iterator I = RenameSets.begin(), E = RenameSets.end(); I != E; ++I) - for (std::map::iterator SI = I->second.begin(), - SE = I->second.end(); SI != SE; ++SI) { - mergeLiveIntervals(I->first, SI->first, SI->second); - Fn.getRegInfo().replaceRegWith(SI->first, I->first); + while (I->second.size()) { + std::map::iterator SI = I->second.begin(); + + DOUT << "Renaming: " << SI->first << " -> " << I->first << "\n"; + + if (SI->first != I->first) { + if (mergeLiveIntervals(I->first, SI->first)) { + Fn.getRegInfo().replaceRegWith(SI->first, I->first); + + if (RenameSets.count(SI->first)) { + I->second.insert(RenameSets[SI->first].begin(), + RenameSets[SI->first].end()); + RenameSets.erase(SI->first); + } + } 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); + + LI.computeNumbering(); + + LiveInterval& Int = LI.getOrCreateInterval(I->first); + unsigned instrIdx = + LI.getInstructionIndex(--SI->second->getFirstTerminator()); + if (Int.liveAt(LiveIntervals::getDefIndex(instrIdx))) + Int.removeRange(LiveIntervals::getDefIndex(instrIdx), + LI.getMBBEndIdx(SI->second)+1, true); + + LiveRange R = LI.addLiveRangeToEndOfBlock(I->first, + --SI->second->getFirstTerminator()); + R.valno->copy = --SI->second->getFirstTerminator(); + R.valno->def = LiveIntervals::getDefIndex(instrIdx); + + DOUT << "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; + + I->second.erase(SI->first); } - // FIXME: Insert last-minute copies - // Remove PHIs std::vector phis; for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) { @@ -889,20 +1007,47 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) { // If this is a dead PHI node, then remove it from LiveIntervals. unsigned DestReg = PInstr->getOperand(0).getReg(); + LiveInterval& PI = LI.getInterval(DestReg); if (PInstr->registerDefIsDead(DestReg)) { - LiveInterval& PI = LI.getInterval(DestReg); - if (PI.containsOneValue()) { LI.removeInterval(DestReg); } else { unsigned idx = LI.getDefIndex(LI.getInstructionIndex(PInstr)); PI.removeRange(*PI.getLiveRangeContaining(idx), true); } - } + } else { + // Trim live intervals of input registers. They are no longer live into + // this block if they died after the PHI. If they lived after it, don't + // trim them because they might have other legitimate uses. + for (unsigned i = 1; i < PInstr->getNumOperands(); i += 2) { + unsigned reg = PInstr->getOperand(i).getReg(); + + MachineBasicBlock* MBB = PInstr->getOperand(i+1).getMBB(); + LiveInterval& InputI = LI.getInterval(reg); + if (MBB != PInstr->getParent() && + InputI.liveAt(LI.getMBBStartIdx(PInstr->getParent())) && + InputI.expiredAt(LI.getInstructionIndex(PInstr) + + LiveIntervals::InstrSlots::NUM)) + InputI.removeRange(LI.getMBBStartIdx(PInstr->getParent()), + LI.getInstructionIndex(PInstr), + true); + } + // 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)); + const LiveRange* PLR = PI.getLiveRangeContaining(idx); + PLR->valno->def = ~0U; + LiveRange R (LI.getMBBStartIdx(PInstr->getParent()), + PLR->start, PLR->valno); + PI.addRange(R); + } + LI.RemoveMachineInstrFromMaps(PInstr); PInstr->eraseFromParent(); } + LI.computeNumbering(); + return true; }