lib/Transforms/Utils/SSAUpdater.cpp

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