From 27d6681496a77aed117ec2d8bcee0d48cdf9072d Mon Sep 17 00:00:00 2001 From: Owen Anderson Date: Wed, 13 Aug 2008 17:25:42 +0000 Subject: [PATCH] 1) Merge entire live intervals instead of parts of them. 2) Conditionalize temporary insertion if we don't need it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54741 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/StrongPHIElimination.cpp | 98 ++++++++++------------------ 1 file changed, 36 insertions(+), 62 deletions(-) diff --git a/lib/CodeGen/StrongPHIElimination.cpp b/lib/CodeGen/StrongPHIElimination.cpp index 9eb4af1d1cc..a06909f72e4 100644 --- a/lib/CodeGen/StrongPHIElimination.cpp +++ b/lib/CodeGen/StrongPHIElimination.cpp @@ -141,8 +141,7 @@ namespace { void ScheduleCopies(MachineBasicBlock* MBB, std::set& pushed); void InsertCopies(MachineDomTreeNode* MBB, SmallPtrSet& v); - void mergeLiveIntervals(unsigned primary, unsigned secondary, - MachineBasicBlock* pred); + void mergeLiveIntervals(unsigned primary, unsigned secondary); }; } @@ -725,16 +724,29 @@ void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB, if (!copy_set.empty()) { std::pair curr = *copy_set.begin(); copy_set.erase(curr.first); + worklist.insert(curr); - 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; + 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); - worklist.insert(curr); + 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)); + } } } @@ -749,11 +761,13 @@ void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB, // 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) + InsertedPHIDests.begin(), E = InsertedPHIDests.end(); I != E; ++I) { + unsigned bar = 0; if (RegHandled.insert(I->first).second && !LI.getOrCreateInterval(I->first).liveAt( LI.getMBBEndIdx(I->second->getParent()))) LI.addLiveRangeToEndOfBlock(I->first, I->second); + } } /// InsertCopies - insert copies into MBB and all of its successors @@ -816,63 +830,23 @@ void StrongPHIElimination::InsertCopies(MachineDomTreeNode* MDTN, } void StrongPHIElimination::mergeLiveIntervals(unsigned primary, - unsigned secondary, - MachineBasicBlock* pred) { + unsigned secondary) { LiveIntervals& LI = getAnalysis(); LiveInterval& LHS = LI.getOrCreateInterval(primary); LiveInterval& RHS = LI.getOrCreateInterval(secondary); LI.computeNumbering(); - const LiveRange* RangeMergingIn = - RHS.getLiveRangeContaining(LI.getMBBEndIdx(pred)); - VNInfo* RHSVN = RangeMergingIn->valno; - VNInfo* NewVN = LHS.getNextValue(RangeMergingIn->valno->def, - RangeMergingIn->valno->copy, - LI.getVNInfoAllocator()); - - // If we discover that a live range was defined by a two-addr - // instruction, we need to merge over the input as well, even if - // it has a different VNInfo. - SmallPtrSet MergedVNs; - MergedVNs.insert(RHSVN); - + + SmallVector VNSet (RHS.vni_begin(), RHS.vni_end()); DenseMap VNMap; - VNMap.insert(std::make_pair(RangeMergingIn->valno, NewVN)); - - // Find all VNs that are the inputs to two-address instructiosn - // chaining upwards from the VN we're trying to merge. - bool addedVN = true; - while (addedVN) { - addedVN = false; - unsigned defIndex = RHSVN->def; - - if (defIndex != ~0U) { - MachineInstr* instr = LI.getInstructionFromIndex(defIndex); - - for (unsigned i = 0; i < instr->getNumOperands(); ++i) { - if (instr->getOperand(i).isReg() && - instr->getOperand(i).getReg() == secondary) - if (instr->isRegReDefinedByTwoAddr(secondary, i)) { - RHSVN = RHS.getLiveRangeContaining(defIndex-1)->valno; - addedVN = true; - - VNInfo* NextVN = LHS.getNextValue(RHSVN->def, - RHSVN->copy, - LI.getVNInfoAllocator()); - VNMap.insert(std::make_pair(RHSVN, NextVN)); - - break; - } - } - } - } - - // Merge VNs from RHS into LHS using the mapping we computed above. - for (DenseMap::iterator VI = VNMap.begin(), - VE = VNMap.end(); VI != VE; ++VI) { - LHS.MergeValueInAsValue(RHS, VI->first, VI->second); - RHS.removeValNo(VI->first); + for (SmallVector::iterator VI = VNSet.begin(), + VE = VNSet.end(); VI != VE; ++VI) { + VNInfo* NewVN = LHS.getNextValue((*VI)->def, + (*VI)->copy, + LI.getVNInfoAllocator()); + LHS.MergeValueInAsValue(RHS, *VI, NewVN); + RHS.removeValNo(*VI); } if (RHS.begin() == RHS.end()) @@ -925,7 +899,7 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) { std::map::iterator SI = I->second.begin(); if (SI->first != I->first) { - mergeLiveIntervals(I->first, SI->first, SI->second); + mergeLiveIntervals(I->first, SI->first); Fn.getRegInfo().replaceRegWith(SI->first, I->first); if (RenameSets.count(SI->first)) { -- 2.34.1