lib/CodeGen/StrongPHIElimination.cpp

//===- 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 "PHIEliminationUtils.h"
#include "llvm/CodeGen/Passes.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"
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<Node*, 2> 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<unsigned, unsigned> &CurrentDominatingParent,
      DenseMap<unsigned, unsigned> &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<unsigned, Node*> RegNodeMap;

    // Maps a basic block to a list of its defs of registers that appear as PHI
    // sources.
    DenseMap<MachineBasicBlock*, std::vector<MachineInstr*> > 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<unsigned, std::pair<MachineInstr*, unsigned> > 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<std::pair<MachineBasicBlock*, unsigned> > SrcCopySet;
    SrcCopySet InsertedSrcCopySet;

    // Maps pairs of predecessor basic blocks and colors to their defining copy
    // instructions.
    typedef DenseMap<std::pair<MachineBasicBlock*, unsigned>, MachineInstr*>
      SrcCopyMap;
    SrcCopyMap InsertedSrcCopyMap;

    // Maps inserted destination copy registers to their defining copy
    // instructions.
    typedef DenseMap<unsigned, MachineInstr*> 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

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<MachineDominatorTree>();
  AU.addRequired<SlotIndexes>();
  AU.addPreserved<SlotIndexes>();
  AU.addRequired<LiveIntervals>();
  AU.addPreserved<LiveIntervals>();
  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;
    }
  }
  return NULL;
}

bool StrongPHIElimination::runOnMachineFunction(MachineFunction &MF) {
  MRI = &MF.getRegInfo();
  TII = MF.getTarget().getInstrInfo();
  DT = &getAnalysis<MachineDominatorTree>();
  LI = &getAnalysis<LiveIntervals>();

  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<unsigned, unsigned> CurrentDominatingParent;
  DenseMap<unsigned, unsigned> ImmediateDominatingParent;
  for (df_iterator<MachineDomTreeNode*> 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<unsigned, unsigned> 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.ranges.size() == 1
           && "PHI destination copy's live interval should be a single live "
               "range from the beginning of the BB to the copy instruction.");
    LiveRange *DestLR = DestLI.begin();
    VNInfo *NewVNI = NewLI.getVNInfoAt(DestLR->start);
    if (!NewVNI) {
      NewVNI = NewLI.createValueCopy(DestLR->valno, LI->getVNInfoAllocator());
      MachineInstr *CopyInstr = I->second;
      CopyInstr->getOperand(1).setIsKill(true);
    }

    LiveRange NewLR(DestLR->start, DestLR->end, NewVNI);
    NewLI.addRange(NewLR);

    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.removeRange(LastUseIndex.getDefIndex(), LI->getMBBEndIdx(MBB));
    LastUse->setIsKill(true);
  }

  LI->renumber();

  Allocator.Reset();
  RegNodeMap.clear();
  PHISrcDefs.clear();
  InsertedSrcCopySet.clear();
  InsertedSrcCopyMap.clear();
  InsertedDestCopies.clear();

  return Changed;
}

void StrongPHIElimination::addReg(unsigned Reg) {
  if (RegNodeMap.count(Reg))
    return;
  RegNodeMap[Reg] = 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<unsigned, Node*>::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<unsigned, unsigned> &CurrentDominatingParent,
    DenseMap<unsigned, unsigned> &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<MachineInstr*> &DefInstrs = PHISrcDefs[&MBB];
  std::sort(DefInstrs.begin(), DefInstrs.end(), MIIndexCompare(LI));

  for (std::vector<MachineInstr*>::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 NewParent = CurrentDominatingParent[DestColor];
      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);
        CurrentDominatingParent[DestColor] = 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;
      }
    }
  }

  // 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
  // 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 NewParent = CurrentDominatingParent[Color];
      while (NewParent
             && (!DT->dominates(MRI->getVRegDef(NewParent)->getParent(), &MBB)
                 || !getRegColor(NewParent)))
        NewParent = ImmediateDominatingParent[NewParent];
      CurrentDominatingParent[Color] = 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<MachineInstr*, unsigned> 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
        CurrentPHIForColor[Color] = std::make_pair(PHI, PredOperandReg);
    }
  }
}

void StrongPHIElimination::InsertCopiesForPHI(MachineInstr *PHI,
                                              MachineBasicBlock *MBB) {
  assert(PHI->isPHI());
  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.getVNInfoAt(PredIndex.getPrevIndex());
      assert(SrcVNI);
      SrcVNI->setHasPHIKill(true);
      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);

      // addLiveRangeToEndOfBlock() also adds the phikill flag to the VNInfo for
      // the newly added range.
      LI->addLiveRangeToEndOfBlock(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);
      }

      if (!InsertedSrcCopyMap.count(std::make_pair(PredBB, PHIColor)))
        InsertedSrcCopyMap[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.removeRange(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.getDefIndex());
    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
    // 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.addRange(LiveRange(MBBStartIndex,
                              PHIIndex.getDefIndex(),
                              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);

  // 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->getOrCreateInterval(CopyReg);
  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(),
                            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());

  VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getDefIndex());
  assert(DestVNI);
  DestVNI->def = DestCopyIndex.getDefIndex();

  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<VNInfo*, VNInfo*> VNMap;
  for (LiveInterval::iterator LRI = OldLI.begin(), LRE = OldLI.end();
       LRI != LRE; ++LRI) {
    LiveRange OldLR = *LRI;
    VNInfo *OldVN = OldLR.valno;

    VNInfo *&NewVN = VNMap[OldVN];
    if (!NewVN) {
      NewVN = NewLI.createValueCopy(OldVN, LI->getVNInfoAllocator());
      VNMap[OldVN] = NewVN;
    }

    LiveRange LR(OldLR.start, OldLR.end, NewVN);
    NewLI.addRange(LR);
  }

  // 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);
}