MFC 261991:

Upgrade our copy of llvm/clang to 3.4 release.  This version supports
all of the features in the current working draft of the upcoming C++
standard, provisionally named C++1y.

The code generator's performance is greatly increased, and the loop
auto-vectorizer is now enabled at -Os and -O2 in addition to -O3.  The
PowerPC backend has made several major improvements to code generation
quality and compile time, and the X86, SPARC, ARM32, Aarch64 and SystemZ
backends have all seen major feature work.

Release notes for llvm and clang can be found here:
<http://llvm.org/releases/3.4/docs/ReleaseNotes.html>
<http://llvm.org/releases/3.4/tools/clang/docs/ReleaseNotes.html>

MFC 262121 (by emaste):

Update lldb for clang/llvm 3.4 import

This commit largely restores the lldb source to the upstream r196259
snapshot with the addition of threaded inferior support and a few bug
fixes.

Specific upstream lldb revisions restored include:
   SVN      git
  181387  779e6ac
  181703  7bef4e2
  182099  b31044e
  182650  f2dcf35
  182683  0d91b80
  183862  15c1774
  183929  99447a6
  184177  0b2934b
  184948  4dc3761
  184954  007e7bc
  186990  eebd175

Sponsored by:	DARPA, AFRL

MFC 262186 (by emaste):

Fix mismerge in r262121

A break statement was lost in the merge.  The error had no functional
impact, but restore it to reduce the diff against upstream.

MFC 262303:

Pull in r197521 from upstream clang trunk (by rdivacky):

  Use the integrated assembler by default on FreeBSD/ppc and ppc64.

Requested by:	jhibbits

MFC 262611:

Pull in r196874 from upstream llvm trunk:

  Fix a crash that occurs when PWD is invalid.

  MCJIT needs to be able to run in hostile environments, even when PWD
  is invalid. There's no need to crash MCJIT in this case.

  The obvious fix is to simply leave MCContext's CompilationDir empty
  when PWD can't be determined. This way, MCJIT clients,
  and other clients that link with LLVM don't need a valid working directory.

  If we do want to guarantee valid CompilationDir, that should be done
  only for clients of getCompilationDir(). This is as simple as checking
  for an empty string.

  The only current use of getCompilationDir is EmitGenDwarfInfo, which
  won't conceivably run with an invalid working dir. However, in the
  purely hypothetically and untestable case that this happens, the
  AT_comp_dir will be omitted from the compilation_unit DIE.

This should help fix assertions occurring with ports-mgmt/tinderbox,
when it is using jails, and sometimes invalidates clang's current
working directory.

Reported by:	decke

MFC 262809:

Pull in r203007 from upstream clang trunk:

  Don't produce an alias between destructors with different calling conventions.

  Fixes pr19007.

(Please note that is an LLVM PR identifier, not a FreeBSD one.)

This should fix Firefox and/or libxul crashes (due to problems with
regparm/stdcall calling conventions) on i386.

Reported by:	multiple users on freebsd-current
PR:		bin/187103

MFC 263048:

Repair recognition of "CC" as an alias for the C++ compiler, since it
was silently broken by upstream for a Windows-specific use-case.

Apparently some versions of CMake still rely on this archaic feature...

Reported by:	rakuco

MFC 263049:

Garbage collect the old way of adding the libstdc++ include directories
in clang's InitHeaderSearch.cpp.  This has been superseded by David
Chisnall's commit in r255321.

Moreover, if libc++ is used, the libstdc++ include directories should
not be in the search path at all.  These directories are now only used
if you pass -stdlib=libstdc++.

1 files changed, 0 insertions, 825 deletions

diff --git a/contrib/llvm/lib/CodeGen/StrongPHIElimination.cpp b/contrib/llvm/lib/CodeGen/StrongPHIElimination.cpp
deleted file mode 100644
index b337c53..0000000
--- a/contrib/llvm/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<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
-
-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<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;
-    }
-  }
-}
-
-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.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<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 &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<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
-        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->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);
-      }
-
-      // 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.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.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.addRange(LiveRange(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->getOrCreateInterval(CopyReg);
-  SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
-  SlotIndex DestCopyIndex = LI->getInstructionIndex(CopyInstr);
-  VNInfo *CopyVNI = CopyLI.getNextValue(MBBStartIndex,
-                                        LI->getVNInfoAllocator());
-  CopyLI.addRange(LiveRange(MBBStartIndex,
-                            DestCopyIndex.getRegSlot(),
-                            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.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<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);
-}