SSAUpdater.cpp revision b913863a95a70fcfe2c5b144c574307dc3d29d88
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" 23using 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. 28class SSAUpdater::BBInfo { 29public: 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 44typedef DenseMap<BasicBlock*, SSAUpdater::BBInfo*> BBMapTy; 45 46typedef DenseMap<BasicBlock*, Value*> AvailableValsTy; 47static AvailableValsTy &getAvailableVals(void *AV) { 48 return *static_cast<AvailableValsTy*>(AV); 49} 50 51static BBMapTy *getBBMap(void *BM) { 52 return static_cast<BBMapTy*>(BM); 53} 54 55SSAUpdater::SSAUpdater(SmallVectorImpl<PHINode*> *NewPHI) 56 : AV(0), PrototypeValue(0), BM(0), InsertedPHIs(NewPHI) {} 57 58SSAUpdater::~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. 64void 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. 74bool 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. 80void 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. 89static 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. 107Value *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/// 133Value *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. 222void 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. 238Value *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. 267static 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. 291void 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. 391static 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. 418void 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. 450static 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. 463void 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. 500void 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 if (Info->DefBB != Info) { 533 // Record the available value at join nodes to speed up subsequent 534 // uses of this SSAUpdater for the same value. 535 if (Info->NumPreds > 1) 536 AvailableVals[Info->BB] = Info->DefBB->AvailableVal; 537 continue; 538 } 539 540 // Check if this block contains a newly added PHI. 541 PHINode *PHI = dyn_cast<PHINode>(Info->AvailableVal); 542 if (!PHI || PHI->getNumIncomingValues() == Info->NumPreds) 543 continue; 544 545 // Iterate through the block's predecessors. 546 for (unsigned p = 0; p != Info->NumPreds; ++p) { 547 BBInfo *PredInfo = Info->Preds[p]; 548 BasicBlock *Pred = PredInfo->BB; 549 // Skip to the nearest preceding definition. 550 if (PredInfo->DefBB != PredInfo) 551 PredInfo = PredInfo->DefBB; 552 PHI->addIncoming(PredInfo->AvailableVal, Pred); 553 } 554 555 DEBUG(dbgs() << " Inserted PHI: " << *PHI << "\n"); 556 557 // If the client wants to know about all new instructions, tell it. 558 if (InsertedPHIs) InsertedPHIs->push_back(PHI); 559 } 560} 561 562/// FindExistingPHI - Look through the PHI nodes in a block to see if any of 563/// them match what is needed. 564void SSAUpdater::FindExistingPHI(BasicBlock *BB, BlockListTy *BlockList) { 565 PHINode *SomePHI; 566 for (BasicBlock::iterator It = BB->begin(); 567 (SomePHI = dyn_cast<PHINode>(It)); ++It) { 568 if (CheckIfPHIMatches(SomePHI)) { 569 RecordMatchingPHI(SomePHI); 570 break; 571 } 572 // Match failed: clear all the PHITag values. 573 for (BlockListTy::iterator I = BlockList->begin(), E = BlockList->end(); 574 I != E; ++I) 575 (*I)->PHITag = 0; 576 } 577} 578 579/// CheckIfPHIMatches - Check if a PHI node matches the placement and values 580/// in the BBMap. 581bool SSAUpdater::CheckIfPHIMatches(PHINode *PHI) { 582 BBMapTy *BBMap = getBBMap(BM); 583 SmallVector<PHINode*, 20> WorkList; 584 WorkList.push_back(PHI); 585 586 // Mark that the block containing this PHI has been visited. 587 (*BBMap)[PHI->getParent()]->PHITag = PHI; 588 589 while (!WorkList.empty()) { 590 PHI = WorkList.pop_back_val(); 591 592 // Iterate through the PHI's incoming values. 593 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) { 594 Value *IncomingVal = PHI->getIncomingValue(i); 595 BBInfo *PredInfo = (*BBMap)[PHI->getIncomingBlock(i)]; 596 // Skip to the nearest preceding definition. 597 if (PredInfo->DefBB != PredInfo) 598 PredInfo = PredInfo->DefBB; 599 600 // Check if it matches the expected value. 601 if (PredInfo->AvailableVal) { 602 if (IncomingVal == PredInfo->AvailableVal) 603 continue; 604 return false; 605 } 606 607 // Check if the value is a PHI in the correct block. 608 PHINode *IncomingPHIVal = dyn_cast<PHINode>(IncomingVal); 609 if (!IncomingPHIVal || IncomingPHIVal->getParent() != PredInfo->BB) 610 return false; 611 612 // If this block has already been visited, check if this PHI matches. 613 if (PredInfo->PHITag) { 614 if (IncomingPHIVal == PredInfo->PHITag) 615 continue; 616 return false; 617 } 618 PredInfo->PHITag = IncomingPHIVal; 619 620 WorkList.push_back(IncomingPHIVal); 621 } 622 } 623 return true; 624} 625 626/// RecordMatchingPHI - For a PHI node that matches, record it and its input 627/// PHIs in both the BBMap and the AvailableVals mapping. 628void SSAUpdater::RecordMatchingPHI(PHINode *PHI) { 629 BBMapTy *BBMap = getBBMap(BM); 630 AvailableValsTy &AvailableVals = getAvailableVals(AV); 631 SmallVector<PHINode*, 20> WorkList; 632 WorkList.push_back(PHI); 633 634 // Record this PHI. 635 BasicBlock *BB = PHI->getParent(); 636 AvailableVals[BB] = PHI; 637 (*BBMap)[BB]->AvailableVal = PHI; 638 639 while (!WorkList.empty()) { 640 PHI = WorkList.pop_back_val(); 641 642 // Iterate through the PHI's incoming values. 643 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) { 644 PHINode *IncomingPHIVal = dyn_cast<PHINode>(PHI->getIncomingValue(i)); 645 if (!IncomingPHIVal) continue; 646 BB = IncomingPHIVal->getParent(); 647 BBInfo *Info = (*BBMap)[BB]; 648 if (!Info || Info->AvailableVal) 649 continue; 650 651 // Record the PHI and add it to the worklist. 652 AvailableVals[BB] = IncomingPHIVal; 653 Info->AvailableVal = IncomingPHIVal; 654 WorkList.push_back(IncomingPHIVal); 655 } 656 } 657} 658