lib/CodeGen/StrongPHIElimination.cpp

   1 //===- StrongPHIElimination.cpp - Eliminate PHI nodes by inserting copies -===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass eliminates PHI instructions by aggressively coalescing the copies
  11 // that would be inserted by a naive algorithm and only inserting the copies
  12 // that are necessary. The coalescing technique initially assumes that all
  13 // registers appearing in a PHI instruction do not interfere. It then eliminates
  14 // proven interferences, using dominators to only perform a linear number of
  15 // interference tests instead of the quadratic number of interference tests
  16 // that this would naively require. This is a technique derived from:
  17 //
  18 //    Budimlic, et al. Fast copy coalescing and live-range identification.
  19 //    In Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language
  20 //    Design and Implementation (Berlin, Germany, June 17 - 19, 2002).
  21 //    PLDI '02. ACM, New York, NY, 25-32.
  22 //
  23 // The original implementation constructs a data structure they call a dominance
  24 // forest for this purpose. The dominance forest was shown to be unnecessary,
  25 // as it is possible to emulate the creation and traversal of a dominance forest
  26 // by directly using the dominator tree, rather than actually constructing the
  27 // dominance forest.  This technique is explained in:
  28 //
  29 //   Boissinot, et al. Revisiting Out-of-SSA Translation for Correctness, Code
  30 //     Quality and Efficiency,
  31 //   In Proceedings of the 7th annual IEEE/ACM International Symposium on Code
  32 //   Generation and Optimization (Seattle, Washington, March 22 - 25, 2009).
  33 //   CGO '09. IEEE, Washington, DC, 114-125.
  34 //
  35 // Careful implementation allows for all of the dominator forest interference
  36 // checks to be performed at once in a single depth-first traversal of the
  37 // dominator tree, which is what is implemented here.
  38 //
  39 //===----------------------------------------------------------------------===//
  40
  41 #define DEBUG_TYPE "strongphielim"
  42 #include "PHIEliminationUtils.h"
  43 #include "llvm/CodeGen/Passes.h"
  44 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  45 #include "llvm/CodeGen/MachineDominators.h"
  46 #include "llvm/CodeGen/MachineFunctionPass.h"
  47 #include "llvm/CodeGen/MachineInstrBuilder.h"
  48 #include "llvm/CodeGen/MachineRegisterInfo.h"
  49 #include "llvm/Target/TargetInstrInfo.h"
  50 #include "llvm/Support/Debug.h"
  51 using namespace llvm;
  52
  53 namespace {
  54   class StrongPHIElimination : public MachineFunctionPass {
  55   public:
  56     static char ID; // Pass identification, replacement for typeid
  57     StrongPHIElimination() : MachineFunctionPass(ID) {
  58       initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
  59     }
  60
  61     virtual void getAnalysisUsage(AnalysisUsage&) const;
  62     bool runOnMachineFunction(MachineFunction&);
  63
  64   private:
  65     /// This struct represents a single node in the union-find data structure
  66     /// representing the variable congruence classes. There is one difference
  67     /// from a normal union-find data structure. We steal two bits from the parent
  68     /// pointer . One of these bits is used to represent whether the register
  69     /// itself has been isolated, and the other is used to represent whether the
  70     /// PHI with that register as its destination has been isolated.
  71     ///
  72     /// Note that this leads to the strange situation where the leader of a
  73     /// congruence class may no longer logically be a member, due to being
  74     /// isolated.
  75     struct Node {
  76       enum Flags {
  77         kRegisterIsolatedFlag = 1,
  78         kPHIIsolatedFlag = 2
  79       };
  80       Node(unsigned v) : value(v), rank(0) { parent.setPointer(this); }
  81
  82       Node* getLeader();
  83
  84       PointerIntPair<Node*, 2> parent;
  85       unsigned value;
  86       unsigned rank;
  87     };
  88
  89     /// Add a register in a new congruence class containing only itself.
  90     void addReg(unsigned);
  91
  92     /// Join the congruence classes of two registers.
  93     void unionRegs(unsigned, unsigned);
  94
  95     /// Get the color of a register. The color is 0 if the register has been
  96     /// isolated.
  97     unsigned getRegColor(unsigned);
  98
  99     // Isolate a register.
 100     void isolateReg(unsigned);
 101
 102     /// Get the color of a PHI. The color of a PHI is 0 if the PHI has been
 103     /// isolated. Otherwise, it is the original color of its destination and
 104     /// all of its operands (before they were isolated, if they were).
 105     unsigned getPHIColor(MachineInstr*);
 106
 107     /// Isolate a PHI.
 108     void isolatePHI(MachineInstr*);
 109
 110     /// Traverses a basic block, splitting any interferences found between
 111     /// registers in the same congruence class. It takes two DenseMaps as
 112     /// arguments that it also updates: CurrentDominatingParent, which maps
 113     /// a color to the register in that congruence class whose definition was
 114     /// most recently seen, and ImmediateDominatingParent, which maps a register
 115     /// to the register in the same congruence class that most immediately
 116     /// dominates it.
 117     ///
 118     /// This function assumes that it is being called in a depth-first traversal
 119     /// of the dominator tree.
 120     void SplitInterferencesForBasicBlock(
 121       MachineBasicBlock&,
 122       DenseMap<unsigned, unsigned>& CurrentDominatingParent,
 123       DenseMap<unsigned, unsigned>& ImmediateDominatingParent);
 124
 125     // Lowers a PHI instruction, inserting copies of the source and destination
 126     // registers as necessary.
 127     void InsertCopiesForPHI(MachineInstr*, MachineBasicBlock*);
 128
 129     // Merges the live interval of Reg into NewReg and renames Reg to NewReg
 130     // everywhere that Reg appears. Requires Reg and NewReg to have non-
 131     // overlapping lifetimes.
 132     void MergeLIsAndRename(unsigned Reg, unsigned NewReg);
 133
 134     MachineRegisterInfo* MRI;
 135     const TargetInstrInfo* TII;
 136     MachineDominatorTree* DT;
 137     LiveIntervals* LI;
 138
 139     BumpPtrAllocator Allocator;
 140
 141     DenseMap<unsigned, Node*> RegNodeMap;
 142
 143     // Maps a basic block to a list of its defs of registers that appear as PHI
 144     // sources.
 145     DenseMap<MachineBasicBlock*, std::vector<MachineInstr*> > PHISrcDefs;
 146
 147     // FIXME: Can these two data structures be combined? Would a std::multimap
 148     // be any better?
 149
 150     // Stores pairs of predecessor basic blocks and the source registers of
 151     // inserted copy instructions.
 152     typedef DenseSet<std::pair<MachineBasicBlock*, unsigned> > SrcCopySet;
 153     SrcCopySet InsertedSrcCopySet;
 154
 155     // Maps pairs of predecessor basic blocks and colors to their defining copy
 156     // instructions.
 157     typedef DenseMap<std::pair<MachineBasicBlock*, unsigned>, MachineInstr*>
 158       SrcCopyMap;
 159     SrcCopyMap InsertedSrcCopyMap;
 160
 161     // Maps inserted destination copy registers to their defining copy
 162     // instructions.
 163     typedef DenseMap<unsigned, MachineInstr*> DestCopyMap;
 164     DestCopyMap InsertedDestCopies;
 165   };
 166
 167   struct MIIndexCompare {
 168     MIIndexCompare(LiveIntervals* LiveIntervals) : LI(LiveIntervals) { }
 169
 170     bool operator()(const MachineInstr* LHS, const MachineInstr* RHS) const {
 171       return LI->getInstructionIndex(LHS) < LI->getInstructionIndex(RHS);
 172     }
 173
 174     LiveIntervals* LI;
 175   };
 176 } // namespace
 177
 178 char StrongPHIElimination::ID = 0;
 179 INITIALIZE_PASS_BEGIN(StrongPHIElimination, "strong-phi-node-elimination",
 180   "Eliminate PHI nodes for register allocation, intelligently", false, false)
 181 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 182 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
 183 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
 184 INITIALIZE_PASS_END(StrongPHIElimination, "strong-phi-node-elimination",
 185   "Eliminate PHI nodes for register allocation, intelligently", false, false)
 186
 187 char &llvm::StrongPHIEliminationID = StrongPHIElimination::ID;
 188
 189 void StrongPHIElimination::getAnalysisUsage(AnalysisUsage& AU) const {
 190   AU.setPreservesCFG();
 191   AU.addRequired<MachineDominatorTree>();
 192   AU.addRequired<SlotIndexes>();
 193   AU.addPreserved<SlotIndexes>();
 194   AU.addRequired<LiveIntervals>();
 195   AU.addPreserved<LiveIntervals>();
 196   MachineFunctionPass::getAnalysisUsage(AU);
 197 }
 198
 199 static MachineOperand* findLastUse(MachineBasicBlock* MBB, unsigned Reg) {
 200   // FIXME: This only needs to check from the first terminator, as only the
 201   // first terminator can use a virtual register.
 202   for (MachineBasicBlock::reverse_iterator RI = MBB->rbegin(); ; ++RI) {
 203     assert (RI != MBB->rend());
 204     MachineInstr* MI = &*RI;
 205
 206     for (MachineInstr::mop_iterator OI = MI->operands_begin(),
 207          OE = MI->operands_end(); OI != OE; ++OI) {
 208       MachineOperand& MO = *OI;
 209       if (MO.isReg() && MO.isUse() && MO.getReg() == Reg)
 210         return &MO;
 211     }
 212   }
 213   return NULL;
 214 }
 215
 216 bool StrongPHIElimination::runOnMachineFunction(MachineFunction& MF) {
 217   MRI = &MF.getRegInfo();
 218   TII = MF.getTarget().getInstrInfo();
 219   DT = &getAnalysis<MachineDominatorTree>();
 220   LI = &getAnalysis<LiveIntervals>();
 221
 222   for (MachineFunction::iterator I = MF.begin(), E = MF.end();
 223        I != E; ++I) {
 224     for (MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
 225          BBI != BBE && BBI->isPHI(); ++BBI) {
 226       unsigned DestReg = BBI->getOperand(0).getReg();
 227       addReg(DestReg);
 228       PHISrcDefs[I].push_back(BBI);
 229
 230       for (unsigned i = 1; i < BBI->getNumOperands(); i += 2) {
 231         MachineOperand& SrcMO = BBI->getOperand(i);
 232         unsigned SrcReg = SrcMO.getReg();
 233         addReg(SrcReg);
 234         unionRegs(DestReg, SrcReg);
 235
 236         for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(SrcReg),
 237              DE = MRI->def_end(); DI != DE; ++DI) {
 238           PHISrcDefs[DI->getParent()].push_back(&*DI);
 239         }
 240       }
 241     }
 242   }
 243
 244   // Perform a depth-first traversal of the dominator tree, splitting
 245   // interferences amongst PHI-congruence classes.
 246   DenseMap<unsigned, unsigned> CurrentDominatingParent;
 247   DenseMap<unsigned, unsigned> ImmediateDominatingParent;
 248   for (df_iterator<MachineDomTreeNode*> DI = df_begin(DT->getRootNode()),
 249        DE = df_end(DT->getRootNode()); DI != DE; ++DI) {
 250     SplitInterferencesForBasicBlock(*DI->getBlock(),
 251                                     CurrentDominatingParent,
 252                                     ImmediateDominatingParent);
 253   }
 254
 255   // Insert copies for all PHI source and destination registers.
 256   for (MachineFunction::iterator I = MF.begin(), E = MF.end();
 257        I != E; ++I) {
 258     for (MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
 259          BBI != BBE && BBI->isPHI(); ++BBI) {
 260       InsertCopiesForPHI(BBI, I);
 261     }
 262   }
 263
 264   // FIXME: Preserve the equivalence classes during copy insertion and use
 265   // the preversed equivalence classes instead of recomputing them.
 266   RegNodeMap.clear();
 267   for (MachineFunction::iterator I = MF.begin(), E = MF.end();
 268        I != E; ++I) {
 269     for (MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
 270          BBI != BBE && BBI->isPHI(); ++BBI) {
 271       unsigned DestReg = BBI->getOperand(0).getReg();
 272       addReg(DestReg);
 273
 274       for (unsigned i = 1; i < BBI->getNumOperands(); i += 2) {
 275         unsigned SrcReg = BBI->getOperand(i).getReg();
 276         addReg(SrcReg);
 277         unionRegs(DestReg, SrcReg);
 278       }
 279     }
 280   }
 281
 282   DenseMap<unsigned, unsigned> RegRenamingMap;
 283   bool Changed = false;
 284   for (MachineFunction::iterator I = MF.begin(), E = MF.end();
 285        I != E; ++I) {
 286     MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
 287     while (BBI != BBE && BBI->isPHI()) {
 288       MachineInstr* PHI = BBI;
 289
 290       assert(PHI->getNumOperands() > 0);
 291
 292       unsigned SrcReg = PHI->getOperand(1).getReg();
 293       unsigned SrcColor = getRegColor(SrcReg);
 294       unsigned NewReg = RegRenamingMap[SrcColor];
 295       if (!NewReg) {
 296         NewReg = SrcReg;
 297         RegRenamingMap[SrcColor] = SrcReg;
 298       }
 299       MergeLIsAndRename(SrcReg, NewReg);
 300
 301       unsigned DestReg = PHI->getOperand(0).getReg();
 302       if (!InsertedDestCopies.count(DestReg))
 303         MergeLIsAndRename(DestReg, NewReg);
 304
 305       for (unsigned i = 3; i < PHI->getNumOperands(); i += 2) {
 306         unsigned SrcReg = PHI->getOperand(i).getReg();
 307         MergeLIsAndRename(SrcReg, NewReg);
 308       }
 309
 310       ++BBI;
 311       LI->RemoveMachineInstrFromMaps(PHI);
 312       PHI->eraseFromParent();
 313       Changed = true;
 314     }
 315   }
 316
 317   // Due to the insertion of copies to split live ranges, the live intervals are
 318   // guaranteed to not overlap, except in one case: an original PHI source and a
 319   // PHI destination copy. In this case, they have the same value and thus don't
 320   // truly intersect, so we merge them into the value live at that point.
 321   // FIXME: Is there some better way we can handle this?
 322   for (DestCopyMap::iterator I = InsertedDestCopies.begin(),
 323        E = InsertedDestCopies.end(); I != E; ++I) {
 324     unsigned DestReg = I->first;
 325     unsigned DestColor = getRegColor(DestReg);
 326     unsigned NewReg = RegRenamingMap[DestColor];
 327
 328     LiveInterval& DestLI = LI->getInterval(DestReg);
 329     LiveInterval& NewLI = LI->getInterval(NewReg);
 330
 331     assert(DestLI.ranges.size() == 1
 332            && "PHI destination copy's live interval should be a single live "
 333                "range from the beginning of the BB to the copy instruction.");
 334     LiveRange* DestLR = DestLI.begin();
 335     VNInfo* NewVNI = NewLI.getVNInfoAt(DestLR->start);
 336     if (!NewVNI) {
 337       NewVNI = NewLI.createValueCopy(DestLR->valno, LI->getVNInfoAllocator());
 338       MachineInstr* CopyInstr = I->second;
 339       CopyInstr->getOperand(1).setIsKill(true);
 340     }
 341
 342     LiveRange NewLR(DestLR->start, DestLR->end, NewVNI);
 343     NewLI.addRange(NewLR);
 344
 345     LI->removeInterval(DestReg);
 346     MRI->replaceRegWith(DestReg, NewReg);
 347   }
 348
 349   // Adjust the live intervals of all PHI source registers to handle the case
 350   // where the PHIs in successor blocks were the only later uses of the source
 351   // register.
 352   for (SrcCopySet::iterator I = InsertedSrcCopySet.begin(),
 353        E = InsertedSrcCopySet.end(); I != E; ++I) {
 354     MachineBasicBlock* MBB = I->first;
 355     unsigned SrcReg = I->second;
 356     if (unsigned RenamedRegister = RegRenamingMap[getRegColor(SrcReg)])
 357       SrcReg = RenamedRegister;
 358
 359     LiveInterval& SrcLI = LI->getInterval(SrcReg);
 360
 361     bool isLiveOut = false;
 362     for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
 363          SE = MBB->succ_end(); SI != SE; ++SI) {
 364       if (SrcLI.liveAt(LI->getMBBStartIdx(*SI))) {
 365         isLiveOut = true;
 366         break;
 367       }
 368     }
 369
 370     if (isLiveOut)
 371       continue;
 372
 373     MachineOperand* LastUse = findLastUse(MBB, SrcReg);
 374     assert(LastUse);
 375     SlotIndex LastUseIndex = LI->getInstructionIndex(LastUse->getParent());
 376     SrcLI.removeRange(LastUseIndex.getDefIndex(), LI->getMBBEndIdx(MBB));
 377     LastUse->setIsKill(true);
 378   }
 379
 380   LI->renumber();
 381
 382   Allocator.Reset();
 383   RegNodeMap.clear();
 384   PHISrcDefs.clear();
 385   InsertedSrcCopySet.clear();
 386   InsertedSrcCopyMap.clear();
 387   InsertedDestCopies.clear();
 388
 389   return Changed;
 390 }
 391
 392 void StrongPHIElimination::addReg(unsigned Reg) {
 393   if (RegNodeMap.count(Reg))
 394     return;
 395   RegNodeMap[Reg] = new (Allocator) Node(Reg);
 396 }
 397
 398 StrongPHIElimination::Node*
 399 StrongPHIElimination::Node::getLeader() {
 400   Node* parentPointer = parent.getPointer();
 401   if (parentPointer == this)
 402     return this;
 403   Node* newParent = parentPointer->getLeader();
 404   parent.setPointer(newParent);
 405   return newParent;
 406 }
 407
 408 unsigned StrongPHIElimination::getRegColor(unsigned Reg) {
 409   DenseMap<unsigned, Node*>::iterator RI = RegNodeMap.find(Reg);
 410   if (RI == RegNodeMap.end())
 411     return 0;
 412   Node* Node = RI->second;
 413   if (Node->parent.getInt() & Node::kRegisterIsolatedFlag)
 414     return 0;
 415   return Node->getLeader()->value;
 416 }
 417
 418 void StrongPHIElimination::unionRegs(unsigned Reg1, unsigned Reg2) {
 419   Node* Node1 = RegNodeMap[Reg1]->getLeader();
 420   Node* Node2 = RegNodeMap[Reg2]->getLeader();
 421
 422   if (Node1->rank > Node2->rank) {
 423     Node2->parent.setPointer(Node1->getLeader());
 424   } else if (Node1->rank < Node2->rank) {
 425     Node1->parent.setPointer(Node2->getLeader());
 426   } else if (Node1 != Node2) {
 427     Node2->parent.setPointer(Node1->getLeader());
 428     Node1->rank++;
 429   }
 430 }
 431
 432 void StrongPHIElimination::isolateReg(unsigned Reg) {
 433   Node* Node = RegNodeMap[Reg];
 434   Node->parent.setInt(Node->parent.getInt() | Node::kRegisterIsolatedFlag);
 435 }
 436
 437 unsigned StrongPHIElimination::getPHIColor(MachineInstr* PHI) {
 438   assert(PHI->isPHI());
 439
 440   unsigned DestReg = PHI->getOperand(0).getReg();
 441   Node* DestNode = RegNodeMap[DestReg];
 442   if (DestNode->parent.getInt() & Node::kPHIIsolatedFlag)
 443     return 0;
 444
 445   for (unsigned i = 1; i < PHI->getNumOperands(); i += 2) {
 446     unsigned SrcColor = getRegColor(PHI->getOperand(i).getReg());
 447     if (SrcColor)
 448       return SrcColor;
 449   }
 450   return 0;
 451 }
 452
 453 void StrongPHIElimination::isolatePHI(MachineInstr* PHI) {
 454   assert(PHI->isPHI());
 455   Node* Node = RegNodeMap[PHI->getOperand(0).getReg()];
 456   Node->parent.setInt(Node->parent.getInt() | Node::kPHIIsolatedFlag);
 457 }
 458
 459 /// SplitInterferencesForBasicBlock - traverses a basic block, splitting any
 460 /// interferences found between registers in the same congruence class. It
 461 /// takes two DenseMaps as arguments that it also updates:
 462 ///
 463 /// 1) CurrentDominatingParent, which maps a color to the register in that
 464 ///    congruence class whose definition was most recently seen.
 465 ///
 466 /// 2) ImmediateDominatingParent, which maps a register to the register in the
 467 ///    same congruence class that most immediately dominates it.
 468 ///
 469 /// This function assumes that it is being called in a depth-first traversal
 470 /// of the dominator tree.
 471 ///
 472 /// The algorithm used here is a generalization of the dominance-based SSA test
 473 /// for two variables. If there are variables a_1, ..., a_n such that
 474 ///
 475 ///   def(a_1) dom ... dom def(a_n),
 476 ///
 477 /// then we can test for an interference between any two a_i by only using O(n)
 478 /// interference tests between pairs of variables. If i < j and a_i and a_j
 479 /// interfere, then a_i is alive at def(a_j), so it is also alive at def(a_i+1).
 480 /// Thus, in order to test for an interference involving a_i, we need only check
 481 /// for a potential interference with a_i+1.
 482 ///
 483 /// This method can be generalized to arbitrary sets of variables by performing
 484 /// a depth-first traversal of the dominator tree. As we traverse down a branch
 485 /// of the dominator tree, we keep track of the current dominating variable and
 486 /// only perform an interference test with that variable. However, when we go to
 487 /// another branch of the dominator tree, the definition of the current dominating
 488 /// variable may no longer dominate the current block. In order to correct this,
 489 /// we need to use a stack of past choices of the current dominating variable
 490 /// and pop from this stack until we find a variable whose definition actually
 491 /// dominates the current block.
 492 ///
 493 /// There will be one push on this stack for each variable that has become the
 494 /// current dominating variable, so instead of using an explicit stack we can
 495 /// simply associate the previous choice for a current dominating variable with
 496 /// the new choice. This works better in our implementation, where we test for
 497 /// interference in multiple distinct sets at once.
 498 void
 499 StrongPHIElimination::SplitInterferencesForBasicBlock(
 500     MachineBasicBlock& MBB,
 501     DenseMap<unsigned, unsigned>& CurrentDominatingParent,
 502     DenseMap<unsigned, unsigned>& ImmediateDominatingParent) {
 503   // Sort defs by their order in the original basic block, as the code below
 504   // assumes that it is processing definitions in dominance order.
 505   std::vector<MachineInstr*>& DefInstrs = PHISrcDefs[&MBB];
 506   std::sort(DefInstrs.begin(), DefInstrs.end(), MIIndexCompare(LI));
 507
 508   for (std::vector<MachineInstr*>::const_iterator BBI = DefInstrs.begin(),
 509        BBE = DefInstrs.end(); BBI != BBE; ++BBI) {
 510     for (MachineInstr::const_mop_iterator I = (*BBI)->operands_begin(),
 511          E = (*BBI)->operands_end(); I != E; ++I) {
 512       const MachineOperand& MO = *I;
 513
 514       // FIXME: This would be faster if it were possible to bail out of checking
 515       // an instruction's operands after the explicit defs, but this is incorrect
 516       // for variadic instructions, which may appear before register allocation
 517       // in the future.
 518       if (!MO.isReg() || !MO.isDef())
 519         continue;
 520
 521       unsigned DestReg = MO.getReg();
 522       if (!DestReg || !TargetRegisterInfo::isVirtualRegister(DestReg))
 523         continue;
 524
 525       // If the virtual register being defined is not used in any PHI or has
 526       // already been isolated, then there are no more interferences to check.
 527       unsigned DestColor = getRegColor(DestReg);
 528       if (!DestColor)
 529         continue;
 530
 531       // The input to this pass sometimes is not in SSA form in every basic
 532       // block, as some virtual registers have redefinitions. We could eliminate
 533       // this by fixing the passes that generate the non-SSA code, or we could
 534       // handle it here by tracking defining machine instructions rather than
 535       // virtual registers. For now, we just handle the situation conservatively
 536       // in a way that will possibly lead to false interferences.
 537       unsigned NewParent = CurrentDominatingParent[DestColor];
 538       if (NewParent == DestReg)
 539         continue;
 540
 541       // Pop registers from the stack represented by ImmediateDominatingParent
 542       // until we find a parent that dominates the current instruction.
 543       while (NewParent && (!DT->dominates(MRI->getVRegDef(NewParent), *BBI)
 544                            || !getRegColor(NewParent)))
 545         NewParent = ImmediateDominatingParent[NewParent];
 546
 547       // If NewParent is nonzero, then its definition dominates the current
 548       // instruction, so it is only necessary to check for the liveness of
 549       // NewParent in order to check for an interference.
 550       if (NewParent
 551           && LI->getInterval(NewParent).liveAt(LI->getInstructionIndex(*BBI))) {
 552         // If there is an interference, always isolate the new register. This
 553         // could be improved by using a heuristic that decides which of the two
 554         // registers to isolate.
 555         isolateReg(DestReg);
 556         CurrentDominatingParent[DestColor] = NewParent;
 557       } else {
 558         // If there is no interference, update ImmediateDominatingParent and set
 559         // the CurrentDominatingParent for this color to the current register.
 560         ImmediateDominatingParent[DestReg] = NewParent;
 561         CurrentDominatingParent[DestColor] = DestReg;
 562       }
 563     }
 564   }
 565
 566   // We now walk the PHIs in successor blocks and check for interferences. This
 567   // is necesary because the use of a PHI's operands are logically contained in
 568   // the predecessor block. The def of a PHI's destination register is processed
 569   // along with the other defs in a basic block.
 570
 571   // The map CurrentPHIForColor maps a color to a pair of a MachineInstr* and a
 572   // virtual register, which is the operand of that PHI corresponding to the
 573   // current basic block.
 574   // FIXME: This should use a container that doesn't always perform heap
 575   // allocation.
 576   DenseMap<unsigned, std::pair<MachineInstr*, unsigned> > CurrentPHIForColor;
 577
 578   for (MachineBasicBlock::succ_iterator SI = MBB.succ_begin(),
 579        SE = MBB.succ_end(); SI != SE; ++SI) {
 580     for (MachineBasicBlock::iterator BBI = (*SI)->begin(), BBE = (*SI)->end();
 581          BBI != BBE && BBI->isPHI(); ++BBI) {
 582       MachineInstr* PHI = BBI;
 583
 584       // If a PHI is already isolated, either by being isolated directly or
 585       // having all of its operands isolated, ignore it.
 586       unsigned Color = getPHIColor(PHI);
 587       if (!Color)
 588         continue;
 589
 590       // Find the index of the PHI operand that corresponds to this basic block.
 591       unsigned PredIndex;
 592       for (PredIndex = 1; PredIndex < PHI->getNumOperands(); PredIndex += 2) {
 593         if (PHI->getOperand(PredIndex + 1).getMBB() == &MBB)
 594           break;
 595       }
 596       assert(PredIndex < PHI->getNumOperands());
 597       unsigned PredOperandReg = PHI->getOperand(PredIndex).getReg();
 598
 599       // Pop registers from the stack represented by ImmediateDominatingParent
 600       // until we find a parent that dominates the current instruction.
 601       unsigned NewParent = CurrentDominatingParent[Color];
 602       while (NewParent
 603              && (!DT->dominates(MRI->getVRegDef(NewParent)->getParent(), &MBB)
 604                  || !getRegColor(NewParent)))
 605         NewParent = ImmediateDominatingParent[NewParent];
 606       CurrentDominatingParent[Color] = NewParent;
 607
 608       // If there is an interference with a register, always isolate the
 609       // register rather than the PHI. It is also possible to isolate the
 610       // PHI, but that introduces copies for all of the registers involved
 611       // in that PHI.
 612       if (NewParent && LI->isLiveOutOfMBB(LI->getInterval(NewParent), &MBB)
 613                     && NewParent != PredOperandReg)
 614         isolateReg(NewParent);
 615
 616       std::pair<MachineInstr*, unsigned> CurrentPHI = CurrentPHIForColor[Color];
 617
 618       // If two PHIs have the same operand from every shared predecessor, then
 619       // they don't actually interfere. Otherwise, isolate the current PHI. This
 620       // could possibly be improved, e.g. we could isolate the PHI with the
 621       // fewest operands.
 622       if (CurrentPHI.first && CurrentPHI.second != PredOperandReg)
 623         isolatePHI(PHI);
 624       else
 625         CurrentPHIForColor[Color] = std::make_pair(PHI, PredOperandReg);
 626     }
 627   }
 628 }
 629
 630 void StrongPHIElimination::InsertCopiesForPHI(MachineInstr* PHI,
 631                                               MachineBasicBlock* MBB) {
 632   assert(PHI->isPHI());
 633   unsigned PHIColor = getPHIColor(PHI);
 634
 635   for (unsigned i = 1; i < PHI->getNumOperands(); i += 2) {
 636     MachineOperand& SrcMO = PHI->getOperand(i);
 637
 638     // If a source is defined by an implicit def, there is no need to insert a
 639     // copy in the predecessor.
 640     if (SrcMO.isUndef())
 641       continue;
 642
 643     unsigned SrcReg = SrcMO.getReg();
 644     assert(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
 645            "Machine PHI Operands must all be virtual registers!");
 646
 647     MachineBasicBlock* PredBB = PHI->getOperand(i + 1).getMBB();
 648     unsigned SrcColor = getRegColor(SrcReg);
 649
 650     // If neither the PHI nor the operand were isolated, then we only need to
 651     // set the phi-kill flag on the VNInfo at this PHI.
 652     if (PHIColor && SrcColor == PHIColor) {
 653       LiveInterval& SrcInterval = LI->getInterval(SrcReg);
 654       SlotIndex PredIndex = LI->getMBBEndIdx(PredBB);
 655       VNInfo* SrcVNI = SrcInterval.getVNInfoAt(PredIndex.getPrevIndex());
 656       assert(SrcVNI);
 657       SrcVNI->setHasPHIKill(true);
 658       continue;
 659     }
 660
 661     unsigned CopyReg = 0;
 662     if (PHIColor) {
 663       SrcCopyMap::const_iterator I
 664         = InsertedSrcCopyMap.find(std::make_pair(PredBB, PHIColor));
 665       CopyReg
 666         = I != InsertedSrcCopyMap.end() ? I->second->getOperand(0).getReg() : 0;
 667     }
 668
 669     if (!CopyReg) {
 670       const TargetRegisterClass* RC = MRI->getRegClass(SrcReg);
 671       CopyReg = MRI->createVirtualRegister(RC);
 672
 673       MachineBasicBlock::iterator
 674         CopyInsertPoint = findPHICopyInsertPoint(PredBB, MBB, SrcReg);
 675       unsigned SrcSubReg = SrcMO.getSubReg();
 676       MachineInstr* CopyInstr = BuildMI(*PredBB,
 677                                         CopyInsertPoint,
 678                                         PHI->getDebugLoc(),
 679                                         TII->get(TargetOpcode::COPY),
 680                                         CopyReg).addReg(SrcReg, 0, SrcSubReg);
 681       LI->InsertMachineInstrInMaps(CopyInstr);
 682
 683       // addLiveRangeToEndOfBlock() also adds the phikill flag to the VNInfo for
 684       // the newly added range.
 685       LI->addLiveRangeToEndOfBlock(CopyReg, CopyInstr);
 686       InsertedSrcCopySet.insert(std::make_pair(PredBB, SrcReg));
 687
 688       addReg(CopyReg);
 689       if (PHIColor) {
 690         unionRegs(PHIColor, CopyReg);
 691         assert(getRegColor(CopyReg) != CopyReg);
 692       } else {
 693         PHIColor = CopyReg;
 694         assert(getRegColor(CopyReg) == CopyReg);
 695       }
 696
 697       if (!InsertedSrcCopyMap.count(std::make_pair(PredBB, PHIColor)))
 698         InsertedSrcCopyMap[std::make_pair(PredBB, PHIColor)] = CopyInstr;
 699     }
 700
 701     SrcMO.setReg(CopyReg);
 702
 703     // If SrcReg is not live beyond the PHI, trim its interval so that it is no
 704     // longer live-in to MBB. Note that SrcReg may appear in other PHIs that are
 705     // processed later, but this is still correct to do at this point because we
 706     // never rely on LiveIntervals being correct while inserting copies.
 707     // FIXME: Should this just count uses at PHIs like the normal PHIElimination
 708     // pass does?
 709     LiveInterval& SrcLI = LI->getInterval(SrcReg);
 710     SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
 711     SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
 712     SlotIndex NextInstrIndex = PHIIndex.getNextIndex();
 713     if (SrcLI.liveAt(MBBStartIndex) && SrcLI.expiredAt(NextInstrIndex))
 714       SrcLI.removeRange(MBBStartIndex, PHIIndex, true);
 715   }
 716
 717   unsigned DestReg = PHI->getOperand(0).getReg();
 718   unsigned DestColor = getRegColor(DestReg);
 719
 720   if (PHIColor && DestColor == PHIColor) {
 721     LiveInterval& DestLI = LI->getInterval(DestReg);
 722
 723     // Set the phi-def flag for the VN at this PHI.
 724     SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
 725     VNInfo* DestVNI = DestLI.getVNInfoAt(PHIIndex.getDefIndex());
 726     assert(DestVNI);
 727     DestVNI->setIsPHIDef(true);
 728
 729     // Prior to PHI elimination, the live ranges of PHIs begin at their defining
 730     // instruction. After PHI elimination, PHI instructions are replaced by VNs
 731     // with the phi-def flag set, and the live ranges of these VNs start at the
 732     // beginning of the basic block.
 733     SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
 734     DestVNI->def = MBBStartIndex;
 735     DestLI.addRange(LiveRange(MBBStartIndex,
 736                               PHIIndex.getDefIndex(),
 737                               DestVNI));
 738     return;
 739   }
 740
 741   const TargetRegisterClass* RC = MRI->getRegClass(DestReg);
 742   unsigned CopyReg = MRI->createVirtualRegister(RC);
 743
 744   MachineInstr* CopyInstr = BuildMI(*MBB,
 745                                     MBB->SkipPHIsAndLabels(MBB->begin()),
 746                                     PHI->getDebugLoc(),
 747                                     TII->get(TargetOpcode::COPY),
 748                                     DestReg).addReg(CopyReg);
 749   LI->InsertMachineInstrInMaps(CopyInstr);
 750   PHI->getOperand(0).setReg(CopyReg);
 751
 752   // Add the region from the beginning of MBB to the copy instruction to
 753   // CopyReg's live interval, and give the VNInfo the phidef flag.
 754   LiveInterval& CopyLI = LI->getOrCreateInterval(CopyReg);
 755   SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
 756   SlotIndex DestCopyIndex = LI->getInstructionIndex(CopyInstr);
 757   VNInfo* CopyVNI = CopyLI.getNextValue(MBBStartIndex,
 758                                         CopyInstr,
 759                                         LI->getVNInfoAllocator());
 760   CopyVNI->setIsPHIDef(true);
 761   CopyLI.addRange(LiveRange(MBBStartIndex,
 762                             DestCopyIndex.getDefIndex(),
 763                             CopyVNI));
 764
 765   // Adjust DestReg's live interval to adjust for its new definition at
 766   // CopyInstr.
 767   LiveInterval& DestLI = LI->getOrCreateInterval(DestReg);
 768   SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
 769   DestLI.removeRange(PHIIndex.getDefIndex(), DestCopyIndex.getDefIndex());
 770
 771   VNInfo* DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getDefIndex());
 772   assert(DestVNI);
 773   DestVNI->def = DestCopyIndex.getDefIndex();
 774
 775   InsertedDestCopies[CopyReg] = CopyInstr;
 776 }
 777
 778 void StrongPHIElimination::MergeLIsAndRename(unsigned Reg, unsigned NewReg) {
 779   if (Reg == NewReg)
 780     return;
 781
 782   LiveInterval& OldLI = LI->getInterval(Reg);
 783   LiveInterval& NewLI = LI->getInterval(NewReg);
 784
 785   // Merge the live ranges of the two registers.
 786   DenseMap<VNInfo*, VNInfo*> VNMap;
 787   for (LiveInterval::iterator LRI = OldLI.begin(), LRE = OldLI.end();
 788        LRI != LRE; ++LRI) {
 789     LiveRange OldLR = *LRI;
 790     VNInfo* OldVN = OldLR.valno;
 791
 792     VNInfo*& NewVN = VNMap[OldVN];
 793     if (!NewVN) {
 794       NewVN = NewLI.createValueCopy(OldVN, LI->getVNInfoAllocator());
 795       VNMap[OldVN] = NewVN;
 796     }
 797
 798     LiveRange LR(OldLR.start, OldLR.end, NewVN);
 799     NewLI.addRange(LR);
 800   }
 801
 802   // Remove the LiveInterval for the register being renamed and replace all
 803   // of its defs and uses with the new register.
 804   LI->removeInterval(Reg);
 805   MRI->replaceRegWith(Reg, NewReg);
 806 }