From 67b28826cdc7be697acdd3e536a05665fd2a9752 Mon Sep 17 00:00:00 2001 From: Rafael Espindola Date: Mon, 14 Oct 2013 16:39:04 +0000 Subject: [PATCH] Remove the now unused strong phi elimination pass. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@192604 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/Passes.h | 8 - include/llvm/InitializePasses.h | 1 - lib/CodeGen/CMakeLists.txt | 1 - lib/CodeGen/CodeGen.cpp | 1 - lib/CodeGen/Passes.cpp | 17 +- lib/CodeGen/StrongPHIElimination.cpp | 825 --------------------------- 6 files changed, 3 insertions(+), 850 deletions(-) delete mode 100644 lib/CodeGen/StrongPHIElimination.cpp diff --git a/include/llvm/CodeGen/Passes.h b/include/llvm/CodeGen/Passes.h index 4e9180cc6ed..552ed45481c 100644 --- a/include/llvm/CodeGen/Passes.h +++ b/include/llvm/CodeGen/Passes.h @@ -381,14 +381,6 @@ namespace llvm { /// these register allocator like this: AU.addRequiredID(PHIEliminationID); extern char &PHIEliminationID; - /// StrongPHIElimination - This pass eliminates machine instruction PHI - /// nodes by inserting copy instructions. This destroys SSA information, but - /// is the desired input for some register allocators. This pass is - /// "required" by these register allocator like this: - /// AU.addRequiredID(PHIEliminationID); - /// This pass is still in development - extern char &StrongPHIEliminationID; - /// LiveIntervals - This analysis keeps track of the live ranges of virtual /// and physical registers. extern char &LiveIntervalsID; diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h index bb82d942903..6cb75cb6ffb 100644 --- a/include/llvm/InitializePasses.h +++ b/include/llvm/InitializePasses.h @@ -242,7 +242,6 @@ void initializeStripDeadPrototypesPassPass(PassRegistry&); void initializeStripDebugDeclarePass(PassRegistry&); void initializeStripNonDebugSymbolsPass(PassRegistry&); void initializeStripSymbolsPass(PassRegistry&); -void initializeStrongPHIEliminationPass(PassRegistry&); void initializeTailCallElimPass(PassRegistry&); void initializeTailDuplicatePassPass(PassRegistry&); void initializeTargetPassConfigPass(PassRegistry&); diff --git a/lib/CodeGen/CMakeLists.txt b/lib/CodeGen/CMakeLists.txt index 56aa3309d3d..a00df3b2c30 100644 --- a/lib/CodeGen/CMakeLists.txt +++ b/lib/CodeGen/CMakeLists.txt @@ -97,7 +97,6 @@ add_llvm_library(LLVMCodeGen StackColoring.cpp StackProtector.cpp StackSlotColoring.cpp - StrongPHIElimination.cpp TailDuplication.cpp TargetFrameLoweringImpl.cpp TargetInstrInfo.cpp diff --git a/lib/CodeGen/CodeGen.cpp b/lib/CodeGen/CodeGen.cpp index c641991d408..920a48e1e8d 100644 --- a/lib/CodeGen/CodeGen.cpp +++ b/lib/CodeGen/CodeGen.cpp @@ -60,7 +60,6 @@ void llvm::initializeCodeGen(PassRegistry &Registry) { initializeStackProtectorPass(Registry); initializeStackColoringPass(Registry); initializeStackSlotColoringPass(Registry); - initializeStrongPHIEliminationPass(Registry); initializeTailDuplicatePassPass(Registry); initializeTargetPassConfigPass(Registry); initializeTwoAddressInstructionPassPass(Registry); diff --git a/lib/CodeGen/Passes.cpp b/lib/CodeGen/Passes.cpp index 84eb8b876f1..f4ffd03ec3e 100644 --- a/lib/CodeGen/Passes.cpp +++ b/lib/CodeGen/Passes.cpp @@ -58,8 +58,6 @@ OptimizeRegAlloc("optimize-regalloc", cl::Hidden, static cl::opt EnableMachineSched("enable-misched", cl::Hidden, cl::desc("Enable the machine instruction scheduling pass.")); -static cl::opt EnableStrongPHIElim("strong-phi-elim", cl::Hidden, - cl::desc("Use strong PHI elimination.")); static cl::opt DisablePostRAMachineLICM("disable-postra-machine-licm", cl::Hidden, cl::desc("Disable Machine LICM")); @@ -675,24 +673,15 @@ void TargetPassConfig::addOptimizedRegAlloc(FunctionPass *RegAllocPass) { // preferably fix the scavenger to not depend on them). addPass(&LiveVariablesID); - // Add passes that move from transformed SSA into conventional SSA. This is a - // "copy coalescing" problem. - // - if (!EnableStrongPHIElim) { - // Edge splitting is smarter with machine loop info. - addPass(&MachineLoopInfoID); - addPass(&PHIEliminationID); - } + // Edge splitting is smarter with machine loop info. + addPass(&MachineLoopInfoID); + addPass(&PHIEliminationID); // Eventually, we want to run LiveIntervals before PHI elimination. if (EarlyLiveIntervals) addPass(&LiveIntervalsID); addPass(&TwoAddressInstructionPassID); - - if (EnableStrongPHIElim) - addPass(&StrongPHIEliminationID); - addPass(&RegisterCoalescerID); // PreRA instruction scheduling. diff --git a/lib/CodeGen/StrongPHIElimination.cpp b/lib/CodeGen/StrongPHIElimination.cpp deleted file mode 100644 index b3cf6cc2afd..00000000000 --- a/lib/CodeGen/StrongPHIElimination.cpp +++ /dev/null @@ -1,825 +0,0 @@ -//===- StrongPHIElimination.cpp - Eliminate PHI nodes by inserting copies -===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This pass eliminates PHI instructions by aggressively coalescing the copies -// that would be inserted by a naive algorithm and only inserting the copies -// that are necessary. The coalescing technique initially assumes that all -// registers appearing in a PHI instruction do not interfere. It then eliminates -// proven interferences, using dominators to only perform a linear number of -// interference tests instead of the quadratic number of interference tests -// that this would naively require. This is a technique derived from: -// -// Budimlic, et al. Fast copy coalescing and live-range identification. -// In Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language -// Design and Implementation (Berlin, Germany, June 17 - 19, 2002). -// PLDI '02. ACM, New York, NY, 25-32. -// -// The original implementation constructs a data structure they call a dominance -// forest for this purpose. The dominance forest was shown to be unnecessary, -// as it is possible to emulate the creation and traversal of a dominance forest -// by directly using the dominator tree, rather than actually constructing the -// dominance forest. This technique is explained in: -// -// Boissinot, et al. Revisiting Out-of-SSA Translation for Correctness, Code -// Quality and Efficiency, -// In Proceedings of the 7th annual IEEE/ACM International Symposium on Code -// Generation and Optimization (Seattle, Washington, March 22 - 25, 2009). -// CGO '09. IEEE, Washington, DC, 114-125. -// -// Careful implementation allows for all of the dominator forest interference -// checks to be performed at once in a single depth-first traversal of the -// dominator tree, which is what is implemented here. -// -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "strongphielim" -#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/Support/Debug.h" -#include "llvm/Target/TargetInstrInfo.h" -using namespace llvm; - -namespace { - class StrongPHIElimination : public MachineFunctionPass { - public: - static char ID; // Pass identification, replacement for typeid - StrongPHIElimination() : MachineFunctionPass(ID) { - initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry()); - } - - virtual void getAnalysisUsage(AnalysisUsage&) const; - bool runOnMachineFunction(MachineFunction&); - - private: - /// This struct represents a single node in the union-find data structure - /// representing the variable congruence classes. There is one difference - /// from a normal union-find data structure. We steal two bits from the parent - /// pointer . One of these bits is used to represent whether the register - /// itself has been isolated, and the other is used to represent whether the - /// PHI with that register as its destination has been isolated. - /// - /// Note that this leads to the strange situation where the leader of a - /// congruence class may no longer logically be a member, due to being - /// isolated. - struct Node { - enum Flags { - kRegisterIsolatedFlag = 1, - kPHIIsolatedFlag = 2 - }; - Node(unsigned v) : value(v), rank(0) { parent.setPointer(this); } - - Node *getLeader(); - - PointerIntPair parent; - unsigned value; - unsigned rank; - }; - - /// Add a register in a new congruence class containing only itself. - void addReg(unsigned); - - /// 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 - /// isolated. - unsigned getRegColor(unsigned); - - // Isolate a register. - void isolateReg(unsigned); - - /// Get the color of a PHI. The color of a PHI is 0 if the PHI has been - /// isolated. Otherwise, it is the original color of its destination and - /// all of its operands (before they were isolated, if they were). - unsigned getPHIColor(MachineInstr*); - - /// Isolate a PHI. - void isolatePHI(MachineInstr*); - - /// Traverses a basic block, splitting any interferences found between - /// registers in the same congruence class. It takes two DenseMaps as - /// arguments that it also updates: CurrentDominatingParent, which maps - /// a color to the register in that congruence class whose definition was - /// most recently seen, and ImmediateDominatingParent, which maps a register - /// to the register in the same congruence class that most immediately - /// dominates it. - /// - /// This function assumes that it is being called in a depth-first traversal - /// of the dominator tree. - void SplitInterferencesForBasicBlock( - MachineBasicBlock&, - DenseMap &CurrentDominatingParent, - DenseMap &ImmediateDominatingParent); - - // Lowers a PHI instruction, inserting copies of the source and destination - // registers as necessary. - void InsertCopiesForPHI(MachineInstr*, MachineBasicBlock*); - - // Merges the live interval of Reg into NewReg and renames Reg to NewReg - // everywhere that Reg appears. Requires Reg and NewReg to have non- - // overlapping lifetimes. - void MergeLIsAndRename(unsigned Reg, unsigned NewReg); - - MachineRegisterInfo *MRI; - const TargetInstrInfo *TII; - MachineDominatorTree *DT; - LiveIntervals *LI; - - BumpPtrAllocator Allocator; - - DenseMap RegNodeMap; - - // Maps a basic block to a list of its defs of registers that appear as PHI - // sources. - DenseMap > PHISrcDefs; - - // Maps a color to a pair of a MachineInstr* and a virtual register, which - // is the operand of that PHI corresponding to the current basic block. - DenseMap > CurrentPHIForColor; - - // FIXME: Can these two data structures be combined? Would a std::multimap - // be any better? - - // Stores pairs of predecessor basic blocks and the source registers of - // inserted copy instructions. - typedef DenseSet > SrcCopySet; - SrcCopySet InsertedSrcCopySet; - - // Maps pairs of predecessor basic blocks and colors to their defining copy - // instructions. - typedef DenseMap, MachineInstr*> - SrcCopyMap; - SrcCopyMap InsertedSrcCopyMap; - - // Maps inserted destination copy registers to their defining copy - // instructions. - typedef DenseMap DestCopyMap; - DestCopyMap InsertedDestCopies; - }; - - struct MIIndexCompare { - MIIndexCompare(LiveIntervals *LiveIntervals) : LI(LiveIntervals) { } - - bool operator()(const MachineInstr *LHS, const MachineInstr *RHS) const { - return LI->getInstructionIndex(LHS) < LI->getInstructionIndex(RHS); - } - - LiveIntervals *LI; - }; -} // 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) -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) - -char &llvm::StrongPHIEliminationID = StrongPHIElimination::ID; - -void StrongPHIElimination::getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesCFG(); - AU.addRequired(); - AU.addRequired(); - AU.addPreserved(); - AU.addRequired(); - AU.addPreserved(); - MachineFunctionPass::getAnalysisUsage(AU); -} - -static MachineOperand *findLastUse(MachineBasicBlock *MBB, unsigned Reg) { - // FIXME: This only needs to check from the first terminator, as only the - // first terminator can use a virtual register. - for (MachineBasicBlock::reverse_iterator RI = MBB->rbegin(); ; ++RI) { - assert (RI != MBB->rend()); - MachineInstr *MI = &*RI; - - for (MachineInstr::mop_iterator OI = MI->operands_begin(), - OE = MI->operands_end(); OI != OE; ++OI) { - MachineOperand &MO = *OI; - if (MO.isReg() && MO.isUse() && MO.getReg() == Reg) - return &MO; - } - } -} - -bool StrongPHIElimination::runOnMachineFunction(MachineFunction &MF) { - MRI = &MF.getRegInfo(); - TII = MF.getTarget().getInstrInfo(); - DT = &getAnalysis(); - LI = &getAnalysis(); - - for (MachineFunction::iterator I = MF.begin(), E = MF.end(); - I != E; ++I) { - for (MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end(); - BBI != BBE && BBI->isPHI(); ++BBI) { - unsigned DestReg = BBI->getOperand(0).getReg(); - addReg(DestReg); - PHISrcDefs[I].push_back(BBI); - - for (unsigned i = 1; i < BBI->getNumOperands(); i += 2) { - MachineOperand &SrcMO = BBI->getOperand(i); - unsigned SrcReg = SrcMO.getReg(); - addReg(SrcReg); - unionRegs(DestReg, SrcReg); - - MachineInstr *DefMI = MRI->getVRegDef(SrcReg); - if (DefMI) - PHISrcDefs[DefMI->getParent()].push_back(DefMI); - } - } - } - - // Perform a depth-first traversal of the dominator tree, splitting - // interferences amongst PHI-congruence classes. - DenseMap CurrentDominatingParent; - DenseMap ImmediateDominatingParent; - for (df_iterator DI = df_begin(DT->getRootNode()), - DE = df_end(DT->getRootNode()); DI != DE; ++DI) { - SplitInterferencesForBasicBlock(*DI->getBlock(), - CurrentDominatingParent, - ImmediateDominatingParent); - } - - // Insert copies for all PHI source and destination registers. - for (MachineFunction::iterator I = MF.begin(), E = MF.end(); - I != E; ++I) { - for (MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end(); - BBI != BBE && BBI->isPHI(); ++BBI) { - InsertCopiesForPHI(BBI, I); - } - } - - // FIXME: Preserve the equivalence classes during copy insertion and use - // the preversed equivalence classes instead of recomputing them. - RegNodeMap.clear(); - for (MachineFunction::iterator I = MF.begin(), E = MF.end(); - I != E; ++I) { - for (MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end(); - BBI != BBE && BBI->isPHI(); ++BBI) { - unsigned DestReg = BBI->getOperand(0).getReg(); - addReg(DestReg); - - for (unsigned i = 1; i < BBI->getNumOperands(); i += 2) { - unsigned SrcReg = BBI->getOperand(i).getReg(); - addReg(SrcReg); - unionRegs(DestReg, SrcReg); - } - } - } - - DenseMap RegRenamingMap; - bool Changed = false; - for (MachineFunction::iterator I = MF.begin(), E = MF.end(); - I != E; ++I) { - MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end(); - while (BBI != BBE && BBI->isPHI()) { - MachineInstr *PHI = BBI; - - assert(PHI->getNumOperands() > 0); - - unsigned SrcReg = PHI->getOperand(1).getReg(); - unsigned SrcColor = getRegColor(SrcReg); - unsigned NewReg = RegRenamingMap[SrcColor]; - if (!NewReg) { - NewReg = SrcReg; - RegRenamingMap[SrcColor] = SrcReg; - } - MergeLIsAndRename(SrcReg, NewReg); - - unsigned DestReg = PHI->getOperand(0).getReg(); - if (!InsertedDestCopies.count(DestReg)) - MergeLIsAndRename(DestReg, NewReg); - - for (unsigned i = 3; i < PHI->getNumOperands(); i += 2) { - unsigned SrcReg = PHI->getOperand(i).getReg(); - MergeLIsAndRename(SrcReg, NewReg); - } - - ++BBI; - LI->RemoveMachineInstrFromMaps(PHI); - PHI->eraseFromParent(); - Changed = true; - } - } - - // Due to the insertion of copies to split live ranges, the live intervals are - // guaranteed to not overlap, except in one case: an original PHI source and a - // PHI destination copy. In this case, they have the same value and thus don't - // truly intersect, so we merge them into the value live at that point. - // FIXME: Is there some better way we can handle this? - for (DestCopyMap::iterator I = InsertedDestCopies.begin(), - E = InsertedDestCopies.end(); I != E; ++I) { - unsigned DestReg = I->first; - unsigned DestColor = getRegColor(DestReg); - unsigned NewReg = RegRenamingMap[DestColor]; - - LiveInterval &DestLI = LI->getInterval(DestReg); - LiveInterval &NewLI = LI->getInterval(NewReg); - - assert(DestLI.size() == 1 - && "PHI destination copy's live interval should be a single live " - "range from the beginning of the BB to the copy instruction."); - LiveInterval::Segment *DestS = DestLI.begin(); - VNInfo *NewVNI = NewLI.getVNInfoAt(DestS->start); - if (!NewVNI) { - NewVNI = NewLI.createValueCopy(DestS->valno, LI->getVNInfoAllocator()); - MachineInstr *CopyInstr = I->second; - CopyInstr->getOperand(1).setIsKill(true); - } - - LiveInterval::Segment NewS(DestS->start, DestS->end, NewVNI); - NewLI.addSegment(NewS); - - LI->removeInterval(DestReg); - MRI->replaceRegWith(DestReg, NewReg); - } - - // Adjust the live intervals of all PHI source registers to handle the case - // where the PHIs in successor blocks were the only later uses of the source - // register. - for (SrcCopySet::iterator I = InsertedSrcCopySet.begin(), - E = InsertedSrcCopySet.end(); I != E; ++I) { - MachineBasicBlock *MBB = I->first; - unsigned SrcReg = I->second; - if (unsigned RenamedRegister = RegRenamingMap[getRegColor(SrcReg)]) - SrcReg = RenamedRegister; - - LiveInterval &SrcLI = LI->getInterval(SrcReg); - - bool isLiveOut = false; - for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), - SE = MBB->succ_end(); SI != SE; ++SI) { - if (SrcLI.liveAt(LI->getMBBStartIdx(*SI))) { - isLiveOut = true; - break; - } - } - - if (isLiveOut) - continue; - - MachineOperand *LastUse = findLastUse(MBB, SrcReg); - assert(LastUse); - SlotIndex LastUseIndex = LI->getInstructionIndex(LastUse->getParent()); - SrcLI.removeSegment(LastUseIndex.getRegSlot(), LI->getMBBEndIdx(MBB)); - LastUse->setIsKill(true); - } - - Allocator.Reset(); - RegNodeMap.clear(); - PHISrcDefs.clear(); - InsertedSrcCopySet.clear(); - InsertedSrcCopyMap.clear(); - InsertedDestCopies.clear(); - - return Changed; -} - -void StrongPHIElimination::addReg(unsigned Reg) { - Node *&N = RegNodeMap[Reg]; - if (!N) - N = new (Allocator) Node(Reg); -} - -StrongPHIElimination::Node* -StrongPHIElimination::Node::getLeader() { - Node *N = this; - Node *Parent = parent.getPointer(); - Node *Grandparent = Parent->parent.getPointer(); - - while (Parent != Grandparent) { - N->parent.setPointer(Grandparent); - N = Grandparent; - Parent = Parent->parent.getPointer(); - Grandparent = Parent->parent.getPointer(); - } - - return Parent; -} - -unsigned StrongPHIElimination::getRegColor(unsigned Reg) { - DenseMap::iterator RI = RegNodeMap.find(Reg); - if (RI == RegNodeMap.end()) - return 0; - Node *Node = RI->second; - if (Node->parent.getInt() & Node::kRegisterIsolatedFlag) - return 0; - return Node->getLeader()->value; -} - -void StrongPHIElimination::unionRegs(unsigned Reg1, unsigned Reg2) { - Node *Node1 = RegNodeMap[Reg1]->getLeader(); - Node *Node2 = RegNodeMap[Reg2]->getLeader(); - - if (Node1->rank > Node2->rank) { - Node2->parent.setPointer(Node1->getLeader()); - } else if (Node1->rank < Node2->rank) { - Node1->parent.setPointer(Node2->getLeader()); - } else if (Node1 != Node2) { - Node2->parent.setPointer(Node1->getLeader()); - Node1->rank++; - } -} - -void StrongPHIElimination::isolateReg(unsigned Reg) { - Node *Node = RegNodeMap[Reg]; - Node->parent.setInt(Node->parent.getInt() | Node::kRegisterIsolatedFlag); -} - -unsigned StrongPHIElimination::getPHIColor(MachineInstr *PHI) { - assert(PHI->isPHI()); - - unsigned DestReg = PHI->getOperand(0).getReg(); - Node *DestNode = RegNodeMap[DestReg]; - if (DestNode->parent.getInt() & Node::kPHIIsolatedFlag) - return 0; - - for (unsigned i = 1; i < PHI->getNumOperands(); i += 2) { - unsigned SrcColor = getRegColor(PHI->getOperand(i).getReg()); - if (SrcColor) - return SrcColor; - } - return 0; -} - -void StrongPHIElimination::isolatePHI(MachineInstr *PHI) { - assert(PHI->isPHI()); - Node *Node = RegNodeMap[PHI->getOperand(0).getReg()]; - Node->parent.setInt(Node->parent.getInt() | Node::kPHIIsolatedFlag); -} - -/// SplitInterferencesForBasicBlock - traverses a basic block, splitting any -/// interferences found between registers in the same congruence class. It -/// takes two DenseMaps as arguments that it also updates: -/// -/// 1) CurrentDominatingParent, which maps a color to the register in that -/// congruence class whose definition was most recently seen. -/// -/// 2) ImmediateDominatingParent, which maps a register to the register in the -/// same congruence class that most immediately dominates it. -/// -/// This function assumes that it is being called in a depth-first traversal -/// of the dominator tree. -/// -/// The algorithm used here is a generalization of the dominance-based SSA test -/// for two variables. If there are variables a_1, ..., a_n such that -/// -/// def(a_1) dom ... dom def(a_n), -/// -/// then we can test for an interference between any two a_i by only using O(n) -/// interference tests between pairs of variables. If i < j and a_i and a_j -/// interfere, then a_i is alive at def(a_j), so it is also alive at def(a_i+1). -/// Thus, in order to test for an interference involving a_i, we need only check -/// for a potential interference with a_i+1. -/// -/// This method can be generalized to arbitrary sets of variables by performing -/// a depth-first traversal of the dominator tree. As we traverse down a branch -/// of the dominator tree, we keep track of the current dominating variable and -/// only perform an interference test with that variable. However, when we go to -/// another branch of the dominator tree, the definition of the current dominating -/// variable may no longer dominate the current block. In order to correct this, -/// we need to use a stack of past choices of the current dominating variable -/// and pop from this stack until we find a variable whose definition actually -/// dominates the current block. -/// -/// There will be one push on this stack for each variable that has become the -/// current dominating variable, so instead of using an explicit stack we can -/// simply associate the previous choice for a current dominating variable with -/// the new choice. This works better in our implementation, where we test for -/// interference in multiple distinct sets at once. -void -StrongPHIElimination::SplitInterferencesForBasicBlock( - MachineBasicBlock &MBB, - DenseMap &CurrentDominatingParent, - DenseMap &ImmediateDominatingParent) { - // Sort defs by their order in the original basic block, as the code below - // assumes that it is processing definitions in dominance order. - std::vector &DefInstrs = PHISrcDefs[&MBB]; - std::sort(DefInstrs.begin(), DefInstrs.end(), MIIndexCompare(LI)); - - for (std::vector::const_iterator BBI = DefInstrs.begin(), - BBE = DefInstrs.end(); BBI != BBE; ++BBI) { - for (MachineInstr::const_mop_iterator I = (*BBI)->operands_begin(), - E = (*BBI)->operands_end(); I != E; ++I) { - const MachineOperand &MO = *I; - - // FIXME: This would be faster if it were possible to bail out of checking - // an instruction's operands after the explicit defs, but this is incorrect - // for variadic instructions, which may appear before register allocation - // in the future. - if (!MO.isReg() || !MO.isDef()) - continue; - - unsigned DestReg = MO.getReg(); - if (!DestReg || !TargetRegisterInfo::isVirtualRegister(DestReg)) - continue; - - // If the virtual register being defined is not used in any PHI or has - // already been isolated, then there are no more interferences to check. - unsigned DestColor = getRegColor(DestReg); - if (!DestColor) - continue; - - // The input to this pass sometimes is not in SSA form in every basic - // block, as some virtual registers have redefinitions. We could eliminate - // this by fixing the passes that generate the non-SSA code, or we could - // 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 &CurrentParent = CurrentDominatingParent[DestColor]; - unsigned NewParent = CurrentParent; - if (NewParent == DestReg) - continue; - - // Pop registers from the stack represented by ImmediateDominatingParent - // until we find a parent that dominates the current instruction. - while (NewParent && (!DT->dominates(MRI->getVRegDef(NewParent), *BBI) - || !getRegColor(NewParent))) - NewParent = ImmediateDominatingParent[NewParent]; - - // If NewParent is nonzero, then its definition dominates the current - // instruction, so it is only necessary to check for the liveness of - // NewParent in order to check for an interference. - if (NewParent - && LI->getInterval(NewParent).liveAt(LI->getInstructionIndex(*BBI))) { - // If there is an interference, always isolate the new register. This - // could be improved by using a heuristic that decides which of the two - // registers to isolate. - isolateReg(DestReg); - CurrentParent = NewParent; - } else { - // If there is no interference, update ImmediateDominatingParent and set - // the CurrentDominatingParent for this color to the current register. - ImmediateDominatingParent[DestReg] = NewParent; - CurrentParent = DestReg; - } - } - } - - // We now walk the PHIs in successor blocks and check for interferences. This - // 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. - - CurrentPHIForColor.clear(); - - for (MachineBasicBlock::succ_iterator SI = MBB.succ_begin(), - SE = MBB.succ_end(); SI != SE; ++SI) { - for (MachineBasicBlock::iterator BBI = (*SI)->begin(), BBE = (*SI)->end(); - BBI != BBE && BBI->isPHI(); ++BBI) { - MachineInstr *PHI = BBI; - - // If a PHI is already isolated, either by being isolated directly or - // having all of its operands isolated, ignore it. - unsigned Color = getPHIColor(PHI); - if (!Color) - continue; - - // Find the index of the PHI operand that corresponds to this basic block. - unsigned PredIndex; - for (PredIndex = 1; PredIndex < PHI->getNumOperands(); PredIndex += 2) { - if (PHI->getOperand(PredIndex + 1).getMBB() == &MBB) - break; - } - assert(PredIndex < PHI->getNumOperands()); - unsigned PredOperandReg = PHI->getOperand(PredIndex).getReg(); - - // Pop registers from the stack represented by ImmediateDominatingParent - // until we find a parent that dominates the current instruction. - unsigned &CurrentParent = CurrentDominatingParent[Color]; - unsigned NewParent = CurrentParent; - while (NewParent - && (!DT->dominates(MRI->getVRegDef(NewParent)->getParent(), &MBB) - || !getRegColor(NewParent))) - NewParent = ImmediateDominatingParent[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 - // PHI, but that introduces copies for all of the registers involved - // in that PHI. - if (NewParent && LI->isLiveOutOfMBB(LI->getInterval(NewParent), &MBB) - && NewParent != PredOperandReg) - isolateReg(NewParent); - - 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 - // could possibly be improved, e.g. we could isolate the PHI with the - // fewest operands. - if (CurrentPHI.first && CurrentPHI.second != PredOperandReg) - isolatePHI(PHI); - else - CurrentPHI = std::make_pair(PHI, PredOperandReg); - } - } -} - -void StrongPHIElimination::InsertCopiesForPHI(MachineInstr *PHI, - MachineBasicBlock *MBB) { - assert(PHI->isPHI()); - ++NumPHIsLowered; - unsigned PHIColor = getPHIColor(PHI); - - for (unsigned i = 1; i < PHI->getNumOperands(); i += 2) { - MachineOperand &SrcMO = PHI->getOperand(i); - - // If a source is defined by an implicit def, there is no need to insert a - // copy in the predecessor. - if (SrcMO.isUndef()) - continue; - - unsigned SrcReg = SrcMO.getReg(); - assert(TargetRegisterInfo::isVirtualRegister(SrcReg) && - "Machine PHI Operands must all be virtual registers!"); - - MachineBasicBlock *PredBB = PHI->getOperand(i + 1).getMBB(); - unsigned SrcColor = getRegColor(SrcReg); - - // If neither the PHI nor the operand were isolated, then we only need to - // set the phi-kill flag on the VNInfo at this PHI. - if (PHIColor && SrcColor == PHIColor) { - LiveInterval &SrcInterval = LI->getInterval(SrcReg); - SlotIndex PredIndex = LI->getMBBEndIdx(PredBB); - VNInfo *SrcVNI = SrcInterval.getVNInfoBefore(PredIndex); - (void)SrcVNI; - assert(SrcVNI); - continue; - } - - unsigned CopyReg = 0; - if (PHIColor) { - SrcCopyMap::const_iterator I - = InsertedSrcCopyMap.find(std::make_pair(PredBB, PHIColor)); - CopyReg - = I != InsertedSrcCopyMap.end() ? I->second->getOperand(0).getReg() : 0; - } - - if (!CopyReg) { - const TargetRegisterClass *RC = MRI->getRegClass(SrcReg); - CopyReg = MRI->createVirtualRegister(RC); - - MachineBasicBlock::iterator - CopyInsertPoint = findPHICopyInsertPoint(PredBB, MBB, SrcReg); - unsigned SrcSubReg = SrcMO.getSubReg(); - MachineInstr *CopyInstr = BuildMI(*PredBB, - CopyInsertPoint, - PHI->getDebugLoc(), - 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. - LI->addSegmentToEndOfBlock(CopyReg, CopyInstr); - InsertedSrcCopySet.insert(std::make_pair(PredBB, SrcReg)); - - addReg(CopyReg); - if (PHIColor) { - unionRegs(PHIColor, CopyReg); - assert(getRegColor(CopyReg) != CopyReg); - } else { - PHIColor = CopyReg; - assert(getRegColor(CopyReg) == CopyReg); - } - - // Insert into map if not already there. - InsertedSrcCopyMap.insert(std::make_pair(std::make_pair(PredBB, PHIColor), - CopyInstr)); - } - - SrcMO.setReg(CopyReg); - - // If SrcReg is not live beyond the PHI, trim its interval so that it is no - // longer live-in to MBB. Note that SrcReg may appear in other PHIs that are - // processed later, but this is still correct to do at this point because we - // never rely on LiveIntervals being correct while inserting copies. - // FIXME: Should this just count uses at PHIs like the normal PHIElimination - // pass does? - LiveInterval &SrcLI = LI->getInterval(SrcReg); - SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB); - SlotIndex PHIIndex = LI->getInstructionIndex(PHI); - SlotIndex NextInstrIndex = PHIIndex.getNextIndex(); - if (SrcLI.liveAt(MBBStartIndex) && SrcLI.expiredAt(NextInstrIndex)) - SrcLI.removeSegment(MBBStartIndex, PHIIndex, true); - } - - unsigned DestReg = PHI->getOperand(0).getReg(); - unsigned DestColor = getRegColor(DestReg); - - if (PHIColor && DestColor == PHIColor) { - LiveInterval &DestLI = LI->getInterval(DestReg); - - // Set the phi-def flag for the VN at this PHI. - SlotIndex PHIIndex = LI->getInstructionIndex(PHI); - VNInfo *DestVNI = DestLI.getVNInfoAt(PHIIndex.getRegSlot()); - assert(DestVNI); - - // Prior to PHI elimination, the live ranges of PHIs begin at their defining - // instruction. After PHI elimination, PHI instructions are replaced by VNs - // with the phi-def flag set, and the live ranges of these VNs start at the - // beginning of the basic block. - SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB); - DestVNI->def = MBBStartIndex; - DestLI.addSegment(LiveInterval::Segment(MBBStartIndex, - PHIIndex.getRegSlot(), - DestVNI)); - return; - } - - const TargetRegisterClass *RC = MRI->getRegClass(DestReg); - unsigned CopyReg = MRI->createVirtualRegister(RC); - - MachineInstr *CopyInstr = BuildMI(*MBB, - MBB->SkipPHIsAndLabels(MBB->begin()), - PHI->getDebugLoc(), - TII->get(TargetOpcode::COPY), - 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. - LiveInterval &CopyLI = LI->createEmptyInterval(CopyReg); - SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB); - SlotIndex DestCopyIndex = LI->getInstructionIndex(CopyInstr); - VNInfo *CopyVNI = CopyLI.getNextValue(MBBStartIndex, - LI->getVNInfoAllocator()); - CopyLI.addSegment(LiveInterval::Segment(MBBStartIndex, - DestCopyIndex.getRegSlot(), - CopyVNI)); - - // Adjust DestReg's live interval to adjust for its new definition at - // CopyInstr. - LiveInterval &DestLI = LI->createEmptyInterval(DestReg); - SlotIndex PHIIndex = LI->getInstructionIndex(PHI); - DestLI.removeSegment(PHIIndex.getRegSlot(), DestCopyIndex.getRegSlot()); - - VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getRegSlot()); - assert(DestVNI); - DestVNI->def = DestCopyIndex.getRegSlot(); - - InsertedDestCopies[CopyReg] = CopyInstr; -} - -void StrongPHIElimination::MergeLIsAndRename(unsigned Reg, unsigned NewReg) { - if (Reg == NewReg) - return; - - LiveInterval &OldLI = LI->getInterval(Reg); - LiveInterval &NewLI = LI->getInterval(NewReg); - - // Merge the live ranges of the two registers. - DenseMap VNMap; - for (LiveInterval::iterator SI = OldLI.begin(), SE = OldLI.end(); - SI != SE; ++SI) { - LiveInterval::Segment OldS = *SI; - VNInfo *OldVN = OldS.valno; - - VNInfo *&NewVN = VNMap[OldVN]; - if (!NewVN) { - NewVN = NewLI.createValueCopy(OldVN, LI->getVNInfoAllocator()); - VNMap[OldVN] = NewVN; - } - - LiveInterval::Segment S(OldS.start, OldS.end, NewVN); - NewLI.addSegment(S); - } - - // Remove the LiveInterval for the register being renamed and replace all - // of its defs and uses with the new register. - LI->removeInterval(Reg); - MRI->replaceRegWith(Reg, NewReg); -} -- 2.34.1