lib/CodeGen/MachineSSAUpdater.cpp

   1 //===- MachineSSAUpdater.cpp - Unstructured SSA Update Tool ---------------===//
   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 file implements the MachineSSAUpdater class. It's based on SSAUpdater
  11 // class in lib/Transforms/Utils.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/CodeGen/MachineSSAUpdater.h"
  16 #include "llvm/CodeGen/MachineInstr.h"
  17 #include "llvm/CodeGen/MachineInstrBuilder.h"
  18 #include "llvm/CodeGen/MachineRegisterInfo.h"
  19 #include "llvm/Target/TargetInstrInfo.h"
  20 #include "llvm/Target/TargetMachine.h"
  21 #include "llvm/Target/TargetRegisterInfo.h"
  22 #include "llvm/ADT/DenseMap.h"
  23 #include "llvm/ADT/SmallVector.h"
  24 #include "llvm/Support/AlignOf.h"
  25 #include "llvm/Support/Allocator.h"
  26 #include "llvm/Support/Debug.h"
  27 #include "llvm/Support/ErrorHandling.h"
  28 #include "llvm/Support/raw_ostream.h"
  29 using namespace llvm;
  30
  31 /// BBInfo - Per-basic block information used internally by MachineSSAUpdater.
  32 class MachineSSAUpdater::BBInfo {
  33 public:
  34   MachineBasicBlock *BB; // Back-pointer to the corresponding block.
  35   unsigned AvailableVal; // Value to use in this block.
  36   BBInfo *DefBB;         // Block that defines the available value.
  37   int BlkNum;            // Postorder number.
  38   BBInfo *IDom;          // Immediate dominator.
  39   unsigned NumPreds;     // Number of predecessor blocks.
  40   BBInfo **Preds;        // Array[NumPreds] of predecessor blocks.
  41   MachineInstr *PHITag;  // Marker for existing PHIs that match.
  42
  43   BBInfo(MachineBasicBlock *ThisBB, unsigned V)
  44     : BB(ThisBB), AvailableVal(V), DefBB(V ? this : 0), BlkNum(0), IDom(0),
  45       NumPreds(0), Preds(0), PHITag(0) { }
  46 };
  47
  48 typedef DenseMap<MachineBasicBlock*, MachineSSAUpdater::BBInfo*> BBMapTy;
  49
  50 typedef DenseMap<MachineBasicBlock*, unsigned> AvailableValsTy;
  51 static AvailableValsTy &getAvailableVals(void *AV) {
  52   return *static_cast<AvailableValsTy*>(AV);
  53 }
  54
  55 static BBMapTy *getBBMap(void *BM) {
  56   return static_cast<BBMapTy*>(BM);
  57 }
  58
  59 MachineSSAUpdater::MachineSSAUpdater(MachineFunction &MF,
  60                                      SmallVectorImpl<MachineInstr*> *NewPHI)
  61   : AV(0), BM(0), InsertedPHIs(NewPHI) {
  62   TII = MF.getTarget().getInstrInfo();
  63   MRI = &MF.getRegInfo();
  64 }
  65
  66 MachineSSAUpdater::~MachineSSAUpdater() {
  67   delete &getAvailableVals(AV);
  68 }
  69
  70 /// Initialize - Reset this object to get ready for a new set of SSA
  71 /// updates.  ProtoValue is the value used to name PHI nodes.
  72 void MachineSSAUpdater::Initialize(unsigned V) {
  73   if (AV == 0)
  74     AV = new AvailableValsTy();
  75   else
  76     getAvailableVals(AV).clear();
  77
  78   VR = V;
  79   VRC = MRI->getRegClass(VR);
  80 }
  81
  82 /// HasValueForBlock - Return true if the MachineSSAUpdater already has a value for
  83 /// the specified block.
  84 bool MachineSSAUpdater::HasValueForBlock(MachineBasicBlock *BB) const {
  85   return getAvailableVals(AV).count(BB);
  86 }
  87
  88 /// AddAvailableValue - Indicate that a rewritten value is available in the
  89 /// specified block with the specified value.
  90 void MachineSSAUpdater::AddAvailableValue(MachineBasicBlock *BB, unsigned V) {
  91   getAvailableVals(AV)[BB] = V;
  92 }
  93
  94 /// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is
  95 /// live at the end of the specified block.
  96 unsigned MachineSSAUpdater::GetValueAtEndOfBlock(MachineBasicBlock *BB) {
  97   return GetValueAtEndOfBlockInternal(BB);
  98 }
  99
 100 static
 101 unsigned LookForIdenticalPHI(MachineBasicBlock *BB,
 102           SmallVector<std::pair<MachineBasicBlock*, unsigned>, 8> &PredValues) {
 103   if (BB->empty())
 104     return 0;
 105
 106   MachineBasicBlock::iterator I = BB->front();
 107   if (!I->isPHI())
 108     return 0;
 109
 110   AvailableValsTy AVals;
 111   for (unsigned i = 0, e = PredValues.size(); i != e; ++i)
 112     AVals[PredValues[i].first] = PredValues[i].second;
 113   while (I != BB->end() && I->isPHI()) {
 114     bool Same = true;
 115     for (unsigned i = 1, e = I->getNumOperands(); i != e; i += 2) {
 116       unsigned SrcReg = I->getOperand(i).getReg();
 117       MachineBasicBlock *SrcBB = I->getOperand(i+1).getMBB();
 118       if (AVals[SrcBB] != SrcReg) {
 119         Same = false;
 120         break;
 121       }
 122     }
 123     if (Same)
 124       return I->getOperand(0).getReg();
 125     ++I;
 126   }
 127   return 0;
 128 }
 129
 130 /// InsertNewDef - Insert an empty PHI or IMPLICIT_DEF instruction which define
 131 /// a value of the given register class at the start of the specified basic
 132 /// block. It returns the virtual register defined by the instruction.
 133 static
 134 MachineInstr *InsertNewDef(unsigned Opcode,
 135                            MachineBasicBlock *BB, MachineBasicBlock::iterator I,
 136                            const TargetRegisterClass *RC,
 137                            MachineRegisterInfo *MRI, const TargetInstrInfo *TII) {
 138   unsigned NewVR = MRI->createVirtualRegister(RC);
 139   return BuildMI(*BB, I, DebugLoc(), TII->get(Opcode), NewVR);
 140 }
 141
 142 /// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that
 143 /// is live in the middle of the specified block.
 144 ///
 145 /// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one
 146 /// important case: if there is a definition of the rewritten value after the
 147 /// 'use' in BB.  Consider code like this:
 148 ///
 149 ///      X1 = ...
 150 ///   SomeBB:
 151 ///      use(X)
 152 ///      X2 = ...
 153 ///      br Cond, SomeBB, OutBB
 154 ///
 155 /// In this case, there are two values (X1 and X2) added to the AvailableVals
 156 /// set by the client of the rewriter, and those values are both live out of
 157 /// their respective blocks.  However, the use of X happens in the *middle* of
 158 /// a block.  Because of this, we need to insert a new PHI node in SomeBB to
 159 /// merge the appropriate values, and this value isn't live out of the block.
 160 ///
 161 unsigned MachineSSAUpdater::GetValueInMiddleOfBlock(MachineBasicBlock *BB) {
 162   // If there is no definition of the renamed variable in this block, just use
 163   // GetValueAtEndOfBlock to do our work.
 164   if (!HasValueForBlock(BB))
 165     return GetValueAtEndOfBlockInternal(BB);
 166
 167   // If there are no predecessors, just return undef.
 168   if (BB->pred_empty()) {
 169     // Insert an implicit_def to represent an undef value.
 170     MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF,
 171                                         BB, BB->getFirstTerminator(),
 172                                         VRC, MRI, TII);
 173     return NewDef->getOperand(0).getReg();
 174   }
 175
 176   // Otherwise, we have the hard case.  Get the live-in values for each
 177   // predecessor.
 178   SmallVector<std::pair<MachineBasicBlock*, unsigned>, 8> PredValues;
 179   unsigned SingularValue = 0;
 180
 181   bool isFirstPred = true;
 182   for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
 183          E = BB->pred_end(); PI != E; ++PI) {
 184     MachineBasicBlock *PredBB = *PI;
 185     unsigned PredVal = GetValueAtEndOfBlockInternal(PredBB);
 186     PredValues.push_back(std::make_pair(PredBB, PredVal));
 187
 188     // Compute SingularValue.
 189     if (isFirstPred) {
 190       SingularValue = PredVal;
 191       isFirstPred = false;
 192     } else if (PredVal != SingularValue)
 193       SingularValue = 0;
 194   }
 195
 196   // Otherwise, if all the merged values are the same, just use it.
 197   if (SingularValue != 0)
 198     return SingularValue;
 199
 200   // If an identical PHI is already in BB, just reuse it.
 201   unsigned DupPHI = LookForIdenticalPHI(BB, PredValues);
 202   if (DupPHI)
 203     return DupPHI;
 204
 205   // Otherwise, we do need a PHI: insert one now.
 206   MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->front();
 207   MachineInstr *InsertedPHI = InsertNewDef(TargetOpcode::PHI, BB,
 208                                            Loc, VRC, MRI, TII);
 209
 210   // Fill in all the predecessors of the PHI.
 211   MachineInstrBuilder MIB(InsertedPHI);
 212   for (unsigned i = 0, e = PredValues.size(); i != e; ++i)
 213     MIB.addReg(PredValues[i].second).addMBB(PredValues[i].first);
 214
 215   // See if the PHI node can be merged to a single value.  This can happen in
 216   // loop cases when we get a PHI of itself and one other value.
 217   if (unsigned ConstVal = InsertedPHI->isConstantValuePHI()) {
 218     InsertedPHI->eraseFromParent();
 219     return ConstVal;
 220   }
 221
 222   // If the client wants to know about all new instructions, tell it.
 223   if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);
 224
 225   DEBUG(dbgs() << "  Inserted PHI: " << *InsertedPHI << "\n");
 226   return InsertedPHI->getOperand(0).getReg();
 227 }
 228
 229 static
 230 MachineBasicBlock *findCorrespondingPred(const MachineInstr *MI,
 231                                          MachineOperand *U) {
 232   for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) {
 233     if (&MI->getOperand(i) == U)
 234       return MI->getOperand(i+1).getMBB();
 235   }
 236
 237   llvm_unreachable("MachineOperand::getParent() failure?");
 238   return 0;
 239 }
 240
 241 /// RewriteUse - Rewrite a use of the symbolic value.  This handles PHI nodes,
 242 /// which use their value in the corresponding predecessor.
 243 void MachineSSAUpdater::RewriteUse(MachineOperand &U) {
 244   MachineInstr *UseMI = U.getParent();
 245   unsigned NewVR = 0;
 246   if (UseMI->isPHI()) {
 247     MachineBasicBlock *SourceBB = findCorrespondingPred(UseMI, &U);
 248     NewVR = GetValueAtEndOfBlockInternal(SourceBB);
 249   } else {
 250     NewVR = GetValueInMiddleOfBlock(UseMI->getParent());
 251   }
 252
 253   U.setReg(NewVR);
 254 }
 255
 256 void MachineSSAUpdater::ReplaceRegWith(unsigned OldReg, unsigned NewReg) {
 257   MRI->replaceRegWith(OldReg, NewReg);
 258
 259   AvailableValsTy &AvailableVals = getAvailableVals(AV);
 260   for (DenseMap<MachineBasicBlock*, unsigned>::iterator
 261          I = AvailableVals.begin(), E = AvailableVals.end(); I != E; ++I)
 262     if (I->second == OldReg)
 263       I->second = NewReg;
 264 }
 265
 266 /// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry
 267 /// for the specified BB and if so, return it.  If not, construct SSA form by
 268 /// first calculating the required placement of PHIs and then inserting new
 269 /// PHIs where needed.
 270 unsigned MachineSSAUpdater::GetValueAtEndOfBlockInternal(MachineBasicBlock *BB){
 271   AvailableValsTy &AvailableVals = getAvailableVals(AV);
 272   if (unsigned V = AvailableVals[BB])
 273     return V;
 274
 275   // Pool allocation used internally by GetValueAtEndOfBlock.
 276   BumpPtrAllocator Allocator;
 277   BBMapTy BBMapObj;
 278   BM = &BBMapObj;
 279
 280   SmallVector<BBInfo*, 100> BlockList;
 281   BuildBlockList(BB, &BlockList, &Allocator);
 282
 283   // Special case: bail out if BB is unreachable.
 284   if (BlockList.size() == 0) {
 285     BM = 0;
 286     // Insert an implicit_def to represent an undef value.
 287     MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF,
 288                                         BB, BB->getFirstTerminator(),
 289                                         VRC, MRI, TII);
 290     unsigned V = NewDef->getOperand(0).getReg();
 291     AvailableVals[BB] = V;
 292     return V;
 293   }
 294
 295   FindDominators(&BlockList);
 296   FindPHIPlacement(&BlockList);
 297   FindAvailableVals(&BlockList);
 298
 299   BM = 0;
 300   return BBMapObj[BB]->DefBB->AvailableVal;
 301 }
 302
 303 /// FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds
 304 /// vector, set Info->NumPreds, and allocate space in Info->Preds.
 305 static void FindPredecessorBlocks(MachineSSAUpdater::BBInfo *Info,
 306                                   SmallVectorImpl<MachineBasicBlock*> *Preds,
 307                                   BumpPtrAllocator *Allocator) {
 308   MachineBasicBlock *BB = Info->BB;
 309   for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
 310          E = BB->pred_end(); PI != E; ++PI)
 311     Preds->push_back(*PI);
 312
 313   Info->NumPreds = Preds->size();
 314   Info->Preds = static_cast<MachineSSAUpdater::BBInfo**>
 315     (Allocator->Allocate(Info->NumPreds * sizeof(MachineSSAUpdater::BBInfo*),
 316                          AlignOf<MachineSSAUpdater::BBInfo*>::Alignment));
 317 }
 318
 319 /// BuildBlockList - Starting from the specified basic block, traverse back
 320 /// through its predecessors until reaching blocks with known values.  Create
 321 /// BBInfo structures for the blocks and append them to the block list.
 322 void MachineSSAUpdater::BuildBlockList(MachineBasicBlock *BB,
 323                                        BlockListTy *BlockList,
 324                                        BumpPtrAllocator *Allocator) {
 325   AvailableValsTy &AvailableVals = getAvailableVals(AV);
 326   BBMapTy *BBMap = getBBMap(BM);
 327   SmallVector<BBInfo*, 10> RootList;
 328   SmallVector<BBInfo*, 64> WorkList;
 329
 330   BBInfo *Info = new (*Allocator) BBInfo(BB, 0);
 331   (*BBMap)[BB] = Info;
 332   WorkList.push_back(Info);
 333
 334   // Search backward from BB, creating BBInfos along the way and stopping when
 335   // reaching blocks that define the value.  Record those defining blocks on
 336   // the RootList.
 337   SmallVector<MachineBasicBlock*, 10> Preds;
 338   while (!WorkList.empty()) {
 339     Info = WorkList.pop_back_val();
 340     Preds.clear();
 341     FindPredecessorBlocks(Info, &Preds, Allocator);
 342
 343     // Treat an unreachable predecessor as a definition with 'undef'.
 344     if (Info->NumPreds == 0) {
 345       // Insert an implicit_def to represent an undef value.
 346       MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF,
 347                                           Info->BB,
 348                                           Info->BB->getFirstTerminator(),
 349                                           VRC, MRI, TII);
 350       Info->AvailableVal = NewDef->getOperand(0).getReg();
 351       Info->DefBB = Info;
 352       RootList.push_back(Info);
 353       continue;
 354     }
 355
 356     for (unsigned p = 0; p != Info->NumPreds; ++p) {
 357       MachineBasicBlock *Pred = Preds[p];
 358       // Check if BBMap already has a BBInfo for the predecessor block.
 359       BBMapTy::value_type &BBMapBucket = BBMap->FindAndConstruct(Pred);
 360       if (BBMapBucket.second) {
 361         Info->Preds[p] = BBMapBucket.second;
 362         continue;
 363       }
 364
 365       // Create a new BBInfo for the predecessor.
 366       unsigned PredVal = AvailableVals.lookup(Pred);
 367       BBInfo *PredInfo = new (*Allocator) BBInfo(Pred, PredVal);
 368       BBMapBucket.second = PredInfo;
 369       Info->Preds[p] = PredInfo;
 370
 371       if (PredInfo->AvailableVal) {
 372         RootList.push_back(PredInfo);
 373         continue;
 374       }
 375       WorkList.push_back(PredInfo);
 376     }
 377   }
 378
 379   // Now that we know what blocks are backwards-reachable from the starting
 380   // block, do a forward depth-first traversal to assign postorder numbers
 381   // to those blocks.
 382   BBInfo *PseudoEntry = new (*Allocator) BBInfo(0, 0);
 383   unsigned BlkNum = 1;
 384
 385   // Initialize the worklist with the roots from the backward traversal.
 386   while (!RootList.empty()) {
 387     Info = RootList.pop_back_val();
 388     Info->IDom = PseudoEntry;
 389     Info->BlkNum = -1;
 390     WorkList.push_back(Info);
 391   }
 392
 393   while (!WorkList.empty()) {
 394     Info = WorkList.back();
 395
 396     if (Info->BlkNum == -2) {
 397       // All the successors have been handled; assign the postorder number.
 398       Info->BlkNum = BlkNum++;
 399       // If not a root, put it on the BlockList.
 400       if (!Info->AvailableVal)
 401         BlockList->push_back(Info);
 402       WorkList.pop_back();
 403       continue;
 404     }
 405
 406     // Leave this entry on the worklist, but set its BlkNum to mark that its
 407     // successors have been put on the worklist.  When it returns to the top
 408     // the list, after handling its successors, it will be assigned a number.
 409     Info->BlkNum = -2;
 410
 411     // Add unvisited successors to the work list.
 412     for (MachineBasicBlock::succ_iterator SI = Info->BB->succ_begin(),
 413            E = Info->BB->succ_end(); SI != E; ++SI) {
 414       BBInfo *SuccInfo = (*BBMap)[*SI];
 415       if (!SuccInfo || SuccInfo->BlkNum)
 416         continue;
 417       SuccInfo->BlkNum = -1;
 418       WorkList.push_back(SuccInfo);
 419     }
 420   }
 421   PseudoEntry->BlkNum = BlkNum;
 422 }
 423
 424 /// IntersectDominators - This is the dataflow lattice "meet" operation for
 425 /// finding dominators.  Given two basic blocks, it walks up the dominator
 426 /// tree until it finds a common dominator of both.  It uses the postorder
 427 /// number of the blocks to determine how to do that.
 428 static MachineSSAUpdater::BBInfo *
 429 IntersectDominators(MachineSSAUpdater::BBInfo *Blk1,
 430                     MachineSSAUpdater::BBInfo *Blk2) {
 431   while (Blk1 != Blk2) {
 432     while (Blk1->BlkNum < Blk2->BlkNum) {
 433       Blk1 = Blk1->IDom;
 434       if (!Blk1)
 435         return Blk2;
 436     }
 437     while (Blk2->BlkNum < Blk1->BlkNum) {
 438       Blk2 = Blk2->IDom;
 439       if (!Blk2)
 440         return Blk1;
 441     }
 442   }
 443   return Blk1;
 444 }
 445
 446 /// FindDominators - Calculate the dominator tree for the subset of the CFG
 447 /// corresponding to the basic blocks on the BlockList.  This uses the
 448 /// algorithm from: "A Simple, Fast Dominance Algorithm" by Cooper, Harvey and
 449 /// Kennedy, published in Software--Practice and Experience, 2001, 4:1-10.
 450 /// Because the CFG subset does not include any edges leading into blocks that
 451 /// define the value, the results are not the usual dominator tree.  The CFG
 452 /// subset has a single pseudo-entry node with edges to a set of root nodes
 453 /// for blocks that define the value.  The dominators for this subset CFG are
 454 /// not the standard dominators but they are adequate for placing PHIs within
 455 /// the subset CFG.
 456 void MachineSSAUpdater::FindDominators(BlockListTy *BlockList) {
 457   bool Changed;
 458   do {
 459     Changed = false;
 460     // Iterate over the list in reverse order, i.e., forward on CFG edges.
 461     for (BlockListTy::reverse_iterator I = BlockList->rbegin(),
 462            E = BlockList->rend(); I != E; ++I) {
 463       BBInfo *Info = *I;
 464
 465       // Start with the first predecessor.
 466       assert(Info->NumPreds > 0 && "unreachable block");
 467       BBInfo *NewIDom = Info->Preds[0];
 468
 469       // Iterate through the block's other predecessors.
 470       for (unsigned p = 1; p != Info->NumPreds; ++p) {
 471         BBInfo *Pred = Info->Preds[p];
 472         NewIDom = IntersectDominators(NewIDom, Pred);
 473       }
 474
 475       // Check if the IDom value has changed.
 476       if (NewIDom != Info->IDom) {
 477         Info->IDom = NewIDom;
 478         Changed = true;
 479       }
 480     }
 481   } while (Changed);
 482 }
 483
 484 /// IsDefInDomFrontier - Search up the dominator tree from Pred to IDom for
 485 /// any blocks containing definitions of the value.  If one is found, then the
 486 /// successor of Pred is in the dominance frontier for the definition, and
 487 /// this function returns true.
 488 static bool IsDefInDomFrontier(const MachineSSAUpdater::BBInfo *Pred,
 489                                const MachineSSAUpdater::BBInfo *IDom) {
 490   for (; Pred != IDom; Pred = Pred->IDom) {
 491     if (Pred->DefBB == Pred)
 492       return true;
 493   }
 494   return false;
 495 }
 496
 497 /// FindPHIPlacement - PHIs are needed in the iterated dominance frontiers of
 498 /// the known definitions.  Iteratively add PHIs in the dom frontiers until
 499 /// nothing changes.  Along the way, keep track of the nearest dominating
 500 /// definitions for non-PHI blocks.
 501 void MachineSSAUpdater::FindPHIPlacement(BlockListTy *BlockList) {
 502   bool Changed;
 503   do {
 504     Changed = false;
 505     // Iterate over the list in reverse order, i.e., forward on CFG edges.
 506     for (BlockListTy::reverse_iterator I = BlockList->rbegin(),
 507            E = BlockList->rend(); I != E; ++I) {
 508       BBInfo *Info = *I;
 509
 510       // If this block already needs a PHI, there is nothing to do here.
 511       if (Info->DefBB == Info)
 512         continue;
 513
 514       // Default to use the same def as the immediate dominator.
 515       BBInfo *NewDefBB = Info->IDom->DefBB;
 516       for (unsigned p = 0; p != Info->NumPreds; ++p) {
 517         if (IsDefInDomFrontier(Info->Preds[p], Info->IDom)) {
 518           // Need a PHI here.
 519           NewDefBB = Info;
 520           break;
 521         }
 522       }
 523
 524       // Check if anything changed.
 525       if (NewDefBB != Info->DefBB) {
 526         Info->DefBB = NewDefBB;
 527         Changed = true;
 528       }
 529     }
 530   } while (Changed);
 531 }
 532
 533 /// FindAvailableVal - If this block requires a PHI, first check if an existing
 534 /// PHI matches the PHI placement and reaching definitions computed earlier,
 535 /// and if not, create a new PHI.  Visit all the block's predecessors to
 536 /// calculate the available value for each one and fill in the incoming values
 537 /// for a new PHI.
 538 void MachineSSAUpdater::FindAvailableVals(BlockListTy *BlockList) {
 539   AvailableValsTy &AvailableVals = getAvailableVals(AV);
 540
 541   // Go through the worklist in forward order (i.e., backward through the CFG)
 542   // and check if existing PHIs can be used.  If not, create empty PHIs where
 543   // they are needed.
 544   for (BlockListTy::iterator I = BlockList->begin(), E = BlockList->end();
 545        I != E; ++I) {
 546     BBInfo *Info = *I;
 547     // Check if there needs to be a PHI in BB.
 548     if (Info->DefBB != Info)
 549       continue;
 550
 551     // Look for an existing PHI.
 552     FindExistingPHI(Info->BB, BlockList);
 553     if (Info->AvailableVal)
 554       continue;
 555
 556     MachineBasicBlock::iterator Loc =
 557       Info->BB->empty() ? Info->BB->end() : Info->BB->front();
 558     MachineInstr *InsertedPHI = InsertNewDef(TargetOpcode::PHI, Info->BB, Loc,
 559                                              VRC, MRI, TII);
 560     unsigned PHI = InsertedPHI->getOperand(0).getReg();
 561     Info->AvailableVal = PHI;
 562     AvailableVals[Info->BB] = PHI;
 563   }
 564
 565   // Now go back through the worklist in reverse order to fill in the arguments
 566   // for any new PHIs added in the forward traversal.
 567   for (BlockListTy::reverse_iterator I = BlockList->rbegin(),
 568          E = BlockList->rend(); I != E; ++I) {
 569     BBInfo *Info = *I;
 570
 571     if (Info->DefBB != Info) {
 572       // Record the available value at join nodes to speed up subsequent
 573       // uses of this SSAUpdater for the same value.
 574       if (Info->NumPreds > 1)
 575         AvailableVals[Info->BB] = Info->DefBB->AvailableVal;
 576       continue;
 577     }
 578
 579     // Check if this block contains a newly added PHI.
 580     unsigned PHI = Info->AvailableVal;
 581     MachineInstr *InsertedPHI = MRI->getVRegDef(PHI);
 582     if (!InsertedPHI->isPHI() || InsertedPHI->getNumOperands() > 1)
 583       continue;
 584
 585     // Iterate through the block's predecessors.
 586     MachineInstrBuilder MIB(InsertedPHI);
 587     for (unsigned p = 0; p != Info->NumPreds; ++p) {
 588       BBInfo *PredInfo = Info->Preds[p];
 589       MachineBasicBlock *Pred = PredInfo->BB;
 590       // Skip to the nearest preceding definition.
 591       if (PredInfo->DefBB != PredInfo)
 592         PredInfo = PredInfo->DefBB;
 593       MIB.addReg(PredInfo->AvailableVal).addMBB(Pred);
 594     }
 595
 596     DEBUG(dbgs() << "  Inserted PHI: " << *InsertedPHI << "\n");
 597
 598     // If the client wants to know about all new instructions, tell it.
 599     if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);
 600   }
 601 }
 602
 603 /// FindExistingPHI - Look through the PHI nodes in a block to see if any of
 604 /// them match what is needed.
 605 void MachineSSAUpdater::FindExistingPHI(MachineBasicBlock *BB,
 606                                         BlockListTy *BlockList) {
 607   for (MachineBasicBlock::iterator BBI = BB->begin(), BBE = BB->end();
 608        BBI != BBE && BBI->isPHI(); ++BBI) {
 609     if (CheckIfPHIMatches(BBI)) {
 610       RecordMatchingPHI(BBI);
 611       break;
 612     }
 613     // Match failed: clear all the PHITag values.
 614     for (BlockListTy::iterator I = BlockList->begin(), E = BlockList->end();
 615          I != E; ++I)
 616       (*I)->PHITag = 0;
 617   }
 618 }
 619
 620 /// CheckIfPHIMatches - Check if a PHI node matches the placement and values
 621 /// in the BBMap.
 622 bool MachineSSAUpdater::CheckIfPHIMatches(MachineInstr *PHI) {
 623   BBMapTy *BBMap = getBBMap(BM);
 624   SmallVector<MachineInstr*, 20> WorkList;
 625   WorkList.push_back(PHI);
 626
 627   // Mark that the block containing this PHI has been visited.
 628   (*BBMap)[PHI->getParent()]->PHITag = PHI;
 629
 630   while (!WorkList.empty()) {
 631     PHI = WorkList.pop_back_val();
 632
 633     // Iterate through the PHI's incoming values.
 634     for (unsigned i = 1, e = PHI->getNumOperands(); i != e; i += 2) {
 635       unsigned IncomingVal = PHI->getOperand(i).getReg();
 636       BBInfo *PredInfo = (*BBMap)[PHI->getOperand(i+1).getMBB()];
 637       // Skip to the nearest preceding definition.
 638       if (PredInfo->DefBB != PredInfo)
 639         PredInfo = PredInfo->DefBB;
 640
 641       // Check if it matches the expected value.
 642       if (PredInfo->AvailableVal) {
 643         if (IncomingVal == PredInfo->AvailableVal)
 644           continue;
 645         return false;
 646       }
 647
 648       // Check if the value is a PHI in the correct block.
 649       MachineInstr *IncomingPHIVal = MRI->getVRegDef(IncomingVal);
 650       if (!IncomingPHIVal->isPHI() ||
 651           IncomingPHIVal->getParent() != PredInfo->BB)
 652         return false;
 653
 654       // If this block has already been visited, check if this PHI matches.
 655       if (PredInfo->PHITag) {
 656         if (IncomingPHIVal == PredInfo->PHITag)
 657           continue;
 658         return false;
 659       }
 660       PredInfo->PHITag = IncomingPHIVal;
 661
 662       WorkList.push_back(IncomingPHIVal);
 663     }
 664   }
 665   return true;
 666 }
 667
 668 /// RecordMatchingPHI - For a PHI node that matches, record it and its input
 669 /// PHIs in both the BBMap and the AvailableVals mapping.
 670 void MachineSSAUpdater::RecordMatchingPHI(MachineInstr *PHI) {
 671   BBMapTy *BBMap = getBBMap(BM);
 672   AvailableValsTy &AvailableVals = getAvailableVals(AV);
 673   SmallVector<MachineInstr*, 20> WorkList;
 674   WorkList.push_back(PHI);
 675
 676   // Record this PHI.
 677   MachineBasicBlock *BB = PHI->getParent();
 678   AvailableVals[BB] = PHI->getOperand(0).getReg();
 679   (*BBMap)[BB]->AvailableVal = PHI->getOperand(0).getReg();
 680
 681   while (!WorkList.empty()) {
 682     PHI = WorkList.pop_back_val();
 683
 684     // Iterate through the PHI's incoming values.
 685     for (unsigned i = 1, e = PHI->getNumOperands(); i != e; i += 2) {
 686       unsigned IncomingVal = PHI->getOperand(i).getReg();
 687       MachineInstr *IncomingPHIVal = MRI->getVRegDef(IncomingVal);
 688       if (!IncomingPHIVal->isPHI()) continue;
 689       BB = IncomingPHIVal->getParent();
 690       BBInfo *Info = (*BBMap)[BB];
 691       if (!Info || Info->AvailableVal)
 692         continue;
 693
 694       // Record the PHI and add it to the worklist.
 695       AvailableVals[BB] = IncomingVal;
 696       Info->AvailableVal = IncomingVal;
 697       WorkList.push_back(IncomingPHIVal);
 698     }
 699   }
 700 }