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 #include "llvm/Transforms/Utils/SSAUpdater.h"
  15 #include "llvm/Instructions.h"
  16 #include "llvm/ADT/DenseMap.h"
  17 #include "llvm/Support/AlignOf.h"
  18 #include "llvm/Support/Allocator.h"
  19 #include "llvm/Support/CFG.h"
  20 #include "llvm/Support/Debug.h"
  21 #include "llvm/Support/raw_ostream.h"
  22 using namespace llvm;
  23
  24 /// BBInfo - Per-basic block information used internally by SSAUpdater.
  25 /// The predecessors of each block are cached here since pred_iterator is
  26 /// slow and we need to iterate over the blocks at least a few times.
  27 class SSAUpdater::BBInfo {
  28 public:
  29   Value *AvailableVal; // Value to use in this block.
  30   BasicBlock *DefBB;   // Block that defines the available value.
  31   unsigned NumPreds;   // Number of predecessor blocks.
  32   BasicBlock **Preds;  // Array[NumPreds] of predecessor blocks.
  33   unsigned Counter;    // Marker to identify blocks already visited.
  34   PHINode *PHITag;     // Marker for existing PHIs that match.
  35
  36   BBInfo(BasicBlock *BB, Value *V, BumpPtrAllocator *Allocator);
  37 };
  38 typedef DenseMap<BasicBlock*, SSAUpdater::BBInfo*> BBMapTy;
  39
  40 SSAUpdater::BBInfo::BBInfo(BasicBlock *BB, Value *V,
  41                            BumpPtrAllocator *Allocator)
  42   : AvailableVal(V), DefBB(0), NumPreds(0), Preds(0), Counter(0), PHITag(0) {
  43   // If this block has a known value, don't bother finding its predecessors.
  44   if (V) {
  45     DefBB = BB;
  46     return;
  47   }
  48
  49   // We can get our predecessor info by walking the pred_iterator list, but it
  50   // is relatively slow.  If we already have PHI nodes in this block, walk one
  51   // of them to get the predecessor list instead.
  52   if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) {
  53     NumPreds = SomePhi->getNumIncomingValues();
  54     Preds = static_cast<BasicBlock**>
  55       (Allocator->Allocate(NumPreds * sizeof(BasicBlock*),
  56                            AlignOf<BasicBlock*>::Alignment));
  57     for (unsigned pi = 0; pi != NumPreds; ++pi)
  58       Preds[pi] = SomePhi->getIncomingBlock(pi);
  59     return;
  60   }
  61
  62   // Stash the predecessors in a temporary vector until we know how much space
  63   // to allocate for them.
  64   SmallVector<BasicBlock*, 10> TmpPreds;
  65   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
  66     TmpPreds.push_back(*PI);
  67     ++NumPreds;
  68   }
  69   Preds = static_cast<BasicBlock**>
  70     (Allocator->Allocate(NumPreds * sizeof(BasicBlock*),
  71                          AlignOf<BasicBlock*>::Alignment));
  72   memcpy(Preds, TmpPreds.data(), NumPreds * sizeof(BasicBlock*));
  73 }
  74
  75 typedef DenseMap<BasicBlock*, Value*> AvailableValsTy;
  76 static AvailableValsTy &getAvailableVals(void *AV) {
  77   return *static_cast<AvailableValsTy*>(AV);
  78 }
  79
  80 static BBMapTy *getBBMap(void *BM) {
  81   return static_cast<BBMapTy*>(BM);
  82 }
  83
  84 static BumpPtrAllocator *getAllocator(void *BPA) {
  85   return static_cast<BumpPtrAllocator*>(BPA);
  86 }
  87
  88 SSAUpdater::SSAUpdater(SmallVectorImpl<PHINode*> *NewPHI)
  89   : AV(0), PrototypeValue(0), BM(0), BPA(0), InsertedPHIs(NewPHI) {}
  90
  91 SSAUpdater::~SSAUpdater() {
  92   delete &getAvailableVals(AV);
  93 }
  94
  95 /// Initialize - Reset this object to get ready for a new set of SSA
  96 /// updates.  ProtoValue is the value used to name PHI nodes.
  97 void SSAUpdater::Initialize(Value *ProtoValue) {
  98   if (AV == 0)
  99     AV = new AvailableValsTy();
 100   else
 101     getAvailableVals(AV).clear();
 102   PrototypeValue = ProtoValue;
 103 }
 104
 105 /// HasValueForBlock - Return true if the SSAUpdater already has a value for
 106 /// the specified block.
 107 bool SSAUpdater::HasValueForBlock(BasicBlock *BB) const {
 108   return getAvailableVals(AV).count(BB);
 109 }
 110
 111 /// AddAvailableValue - Indicate that a rewritten value is available in the
 112 /// specified block with the specified value.
 113 void SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) {
 114   assert(PrototypeValue != 0 && "Need to initialize SSAUpdater");
 115   assert(PrototypeValue->getType() == V->getType() &&
 116          "All rewritten values must have the same type");
 117   getAvailableVals(AV)[BB] = V;
 118 }
 119
 120 /// IsEquivalentPHI - Check if PHI has the same incoming value as specified
 121 /// in ValueMapping for each predecessor block.
 122 static bool IsEquivalentPHI(PHINode *PHI,
 123                             DenseMap<BasicBlock*, Value*> &ValueMapping) {
 124   unsigned PHINumValues = PHI->getNumIncomingValues();
 125   if (PHINumValues != ValueMapping.size())
 126     return false;
 127
 128   // Scan the phi to see if it matches.
 129   for (unsigned i = 0, e = PHINumValues; i != e; ++i)
 130     if (ValueMapping[PHI->getIncomingBlock(i)] !=
 131         PHI->getIncomingValue(i)) {
 132       return false;
 133     }
 134
 135   return true;
 136 }
 137
 138 /// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is
 139 /// live at the end of the specified block.
 140 Value *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) {
 141   assert(BM == 0 && BPA == 0 && "Unexpected Internal State");
 142   Value *Res = GetValueAtEndOfBlockInternal(BB);
 143   assert(BM == 0 && BPA == 0 && "Unexpected Internal State");
 144   return Res;
 145 }
 146
 147 /// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that
 148 /// is live in the middle of the specified block.
 149 ///
 150 /// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one
 151 /// important case: if there is a definition of the rewritten value after the
 152 /// 'use' in BB.  Consider code like this:
 153 ///
 154 ///      X1 = ...
 155 ///   SomeBB:
 156 ///      use(X)
 157 ///      X2 = ...
 158 ///      br Cond, SomeBB, OutBB
 159 ///
 160 /// In this case, there are two values (X1 and X2) added to the AvailableVals
 161 /// set by the client of the rewriter, and those values are both live out of
 162 /// their respective blocks.  However, the use of X happens in the *middle* of
 163 /// a block.  Because of this, we need to insert a new PHI node in SomeBB to
 164 /// merge the appropriate values, and this value isn't live out of the block.
 165 ///
 166 Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) {
 167   // If there is no definition of the renamed variable in this block, just use
 168   // GetValueAtEndOfBlock to do our work.
 169   if (!HasValueForBlock(BB))
 170     return GetValueAtEndOfBlock(BB);
 171
 172   // Otherwise, we have the hard case.  Get the live-in values for each
 173   // predecessor.
 174   SmallVector<std::pair<BasicBlock*, Value*>, 8> PredValues;
 175   Value *SingularValue = 0;
 176
 177   // We can get our predecessor info by walking the pred_iterator list, but it
 178   // is relatively slow.  If we already have PHI nodes in this block, walk one
 179   // of them to get the predecessor list instead.
 180   if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) {
 181     for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) {
 182       BasicBlock *PredBB = SomePhi->getIncomingBlock(i);
 183       Value *PredVal = GetValueAtEndOfBlock(PredBB);
 184       PredValues.push_back(std::make_pair(PredBB, PredVal));
 185
 186       // Compute SingularValue.
 187       if (i == 0)
 188         SingularValue = PredVal;
 189       else if (PredVal != SingularValue)
 190         SingularValue = 0;
 191     }
 192   } else {
 193     bool isFirstPred = true;
 194     for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
 195       BasicBlock *PredBB = *PI;
 196       Value *PredVal = GetValueAtEndOfBlock(PredBB);
 197       PredValues.push_back(std::make_pair(PredBB, PredVal));
 198
 199       // Compute SingularValue.
 200       if (isFirstPred) {
 201         SingularValue = PredVal;
 202         isFirstPred = false;
 203       } else if (PredVal != SingularValue)
 204         SingularValue = 0;
 205     }
 206   }
 207
 208   // If there are no predecessors, just return undef.
 209   if (PredValues.empty())
 210     return UndefValue::get(PrototypeValue->getType());
 211
 212   // Otherwise, if all the merged values are the same, just use it.
 213   if (SingularValue != 0)
 214     return SingularValue;
 215
 216   // Otherwise, we do need a PHI: check to see if we already have one available
 217   // in this block that produces the right value.
 218   if (isa<PHINode>(BB->begin())) {
 219     DenseMap<BasicBlock*, Value*> ValueMapping(PredValues.begin(),
 220                                                PredValues.end());
 221     PHINode *SomePHI;
 222     for (BasicBlock::iterator It = BB->begin();
 223          (SomePHI = dyn_cast<PHINode>(It)); ++It) {
 224       if (IsEquivalentPHI(SomePHI, ValueMapping))
 225         return SomePHI;
 226     }
 227   }
 228
 229   // Ok, we have no way out, insert a new one now.
 230   PHINode *InsertedPHI = PHINode::Create(PrototypeValue->getType(),
 231                                          PrototypeValue->getName(),
 232                                          &BB->front());
 233   InsertedPHI->reserveOperandSpace(PredValues.size());
 234
 235   // Fill in all the predecessors of the PHI.
 236   for (unsigned i = 0, e = PredValues.size(); i != e; ++i)
 237     InsertedPHI->addIncoming(PredValues[i].second, PredValues[i].first);
 238
 239   // See if the PHI node can be merged to a single value.  This can happen in
 240   // loop cases when we get a PHI of itself and one other value.
 241   if (Value *ConstVal = InsertedPHI->hasConstantValue()) {
 242     InsertedPHI->eraseFromParent();
 243     return ConstVal;
 244   }
 245
 246   // If the client wants to know about all new instructions, tell it.
 247   if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);
 248
 249   DEBUG(dbgs() << "  Inserted PHI: " << *InsertedPHI << "\n");
 250   return InsertedPHI;
 251 }
 252
 253 /// RewriteUse - Rewrite a use of the symbolic value.  This handles PHI nodes,
 254 /// which use their value in the corresponding predecessor.
 255 void SSAUpdater::RewriteUse(Use &U) {
 256   Instruction *User = cast<Instruction>(U.getUser());
 257
 258   Value *V;
 259   if (PHINode *UserPN = dyn_cast<PHINode>(User))
 260     V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));
 261   else
 262     V = GetValueInMiddleOfBlock(User->getParent());
 263
 264   U.set(V);
 265 }
 266
 267 /// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry
 268 /// for the specified BB and if so, return it.  If not, construct SSA form by
 269 /// first calculating the required placement of PHIs and then inserting new
 270 /// PHIs where needed.
 271 Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) {
 272   AvailableValsTy &AvailableVals = getAvailableVals(AV);
 273   if (Value *V = AvailableVals[BB])
 274     return V;
 275
 276   // Pool allocation used internally by GetValueAtEndOfBlock.
 277   BumpPtrAllocator AllocatorObj;
 278   BBMapTy BBMapObj;
 279   BPA = &AllocatorObj;
 280   BM = &BBMapObj;
 281
 282   BBInfo *Info = new (AllocatorObj) BBInfo(BB, 0, &AllocatorObj);
 283   BBMapObj[BB] = Info;
 284
 285   bool Changed;
 286   unsigned Counter = 1;
 287   do {
 288     Changed = false;
 289     FindPHIPlacement(BB, Info, Changed, Counter);
 290     ++Counter;
 291   } while (Changed);
 292
 293   FindAvailableVal(BB, Info, Counter);
 294
 295   BPA = 0;
 296   BM = 0;
 297   return Info->AvailableVal;
 298 }
 299
 300 /// FindPHIPlacement - Recursively visit the predecessors of a block to find
 301 /// the reaching definition for each predecessor and then determine whether
 302 /// a PHI is needed in this block.
 303 void SSAUpdater::FindPHIPlacement(BasicBlock *BB, BBInfo *Info, bool &Changed,
 304                                   unsigned Counter) {
 305   AvailableValsTy &AvailableVals = getAvailableVals(AV);
 306   BBMapTy *BBMap = getBBMap(BM);
 307   BumpPtrAllocator *Allocator = getAllocator(BPA);
 308   bool BBNeedsPHI = false;
 309   BasicBlock *SamePredDefBB = 0;
 310
 311   // If there are no predecessors, then we must have found an unreachable
 312   // block.  Treat it as a definition with 'undef'.
 313   if (Info->NumPreds == 0) {
 314     Info->AvailableVal = UndefValue::get(PrototypeValue->getType());
 315     Info->DefBB = BB;
 316     return;
 317   }
 318
 319   Info->Counter = Counter;
 320   for (unsigned pi = 0; pi != Info->NumPreds; ++pi) {
 321     BasicBlock *Pred = Info->Preds[pi];
 322     BBMapTy::value_type &BBMapBucket = BBMap->FindAndConstruct(Pred);
 323     if (!BBMapBucket.second) {
 324       Value *PredVal = AvailableVals.lookup(Pred);
 325       BBMapBucket.second = new (*Allocator) BBInfo(Pred, PredVal, Allocator);
 326     }
 327     BBInfo *PredInfo = BBMapBucket.second;
 328     BasicBlock *DefBB = 0;
 329     if (!PredInfo->AvailableVal) {
 330       if (PredInfo->Counter != Counter)
 331         FindPHIPlacement(Pred, PredInfo, Changed, Counter);
 332
 333       // Ignore back edges where the value is not yet known.
 334       if (!PredInfo->DefBB)
 335         continue;
 336     }
 337     DefBB = PredInfo->DefBB;
 338
 339     if (!SamePredDefBB)
 340       SamePredDefBB = DefBB;
 341     else if (DefBB != SamePredDefBB)
 342       BBNeedsPHI = true;
 343   }
 344
 345   BasicBlock *NewDefBB = (BBNeedsPHI ? BB : SamePredDefBB);
 346   if (Info->DefBB != NewDefBB) {
 347     Changed = true;
 348     Info->DefBB = NewDefBB;
 349   }
 350 }
 351
 352 /// FindAvailableVal - If this block requires a PHI, first check if an existing
 353 /// PHI matches the PHI placement and reaching definitions computed earlier,
 354 /// and if not, create a new PHI.  Visit all the block's predecessors to
 355 /// calculate the available value for each one and fill in the incoming values
 356 /// for a new PHI.
 357 void SSAUpdater::FindAvailableVal(BasicBlock *BB, BBInfo *Info,
 358                                   unsigned Counter) {
 359   if (Info->AvailableVal || Info->Counter == Counter)
 360     return;
 361
 362   AvailableValsTy &AvailableVals = getAvailableVals(AV);
 363   BBMapTy *BBMap = getBBMap(BM);
 364
 365   // Check if there needs to be a PHI in BB.
 366   PHINode *NewPHI = 0;
 367   if (Info->DefBB == BB) {
 368     // Look for an existing PHI.
 369     FindExistingPHI(BB, Info);
 370     if (!Info->AvailableVal) {
 371       NewPHI = PHINode::Create(PrototypeValue->getType(),
 372                                PrototypeValue->getName(), &BB->front());
 373       NewPHI->reserveOperandSpace(Info->NumPreds);
 374       Info->AvailableVal = NewPHI;
 375       AvailableVals[BB] = NewPHI;
 376     }
 377   }
 378
 379   // Iterate through the block's predecessors.
 380   Info->Counter = Counter;
 381   for (unsigned pi = 0; pi != Info->NumPreds; ++pi) {
 382     BasicBlock *Pred = Info->Preds[pi];
 383     BBInfo *PredInfo = (*BBMap)[Pred];
 384     FindAvailableVal(Pred, PredInfo, Counter);
 385     if (NewPHI) {
 386       // Skip to the nearest preceding definition.
 387       if (PredInfo->DefBB != Pred)
 388         PredInfo = (*BBMap)[PredInfo->DefBB];
 389       NewPHI->addIncoming(PredInfo->AvailableVal, Pred);
 390     } else if (!Info->AvailableVal)
 391       Info->AvailableVal = PredInfo->AvailableVal;
 392   }
 393
 394   if (NewPHI) {
 395     DEBUG(dbgs() << "  Inserted PHI: " << *NewPHI << "\n");
 396
 397     // If the client wants to know about all new instructions, tell it.
 398     if (InsertedPHIs) InsertedPHIs->push_back(NewPHI);
 399   }
 400 }
 401
 402 /// FindExistingPHI - Look through the PHI nodes in a block to see if any of
 403 /// them match what is needed.
 404 void SSAUpdater::FindExistingPHI(BasicBlock *BB, BBInfo *Info) {
 405   PHINode *SomePHI;
 406   for (BasicBlock::iterator It = BB->begin();
 407        (SomePHI = dyn_cast<PHINode>(It)); ++It) {
 408     if (CheckIfPHIMatches(BB, Info, SomePHI)) {
 409       RecordMatchingPHI(SomePHI);
 410       break;
 411     }
 412     ClearPHITags(SomePHI);
 413   }
 414 }
 415
 416 /// CheckIfPHIMatches - Check if Val is a PHI node in block BB that matches
 417 /// the placement and values in the BBMap.
 418 bool SSAUpdater::CheckIfPHIMatches(BasicBlock *BB, BBInfo *Info, Value *Val) {
 419   if (Info->AvailableVal)
 420     return Val == Info->AvailableVal;
 421
 422   // Check if Val is a PHI in this block.
 423   PHINode *PHI = dyn_cast<PHINode>(Val);
 424   if (!PHI || PHI->getParent() != BB)
 425     return false;
 426
 427   // If this block has already been visited, check if this PHI matches.
 428   if (Info->PHITag)
 429     return PHI == Info->PHITag;
 430   Info->PHITag = PHI;
 431   bool IsMatch = true;
 432
 433   // Iterate through the predecessors.
 434   BBMapTy *BBMap = getBBMap(BM);
 435   for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
 436     BasicBlock *Pred = PHI->getIncomingBlock(i);
 437     Value *IncomingVal = PHI->getIncomingValue(i);
 438     BBInfo *PredInfo = (*BBMap)[Pred];
 439     // Skip to the nearest preceding definition.
 440     if (PredInfo->DefBB != Pred) {
 441       Pred = PredInfo->DefBB;
 442       PredInfo = (*BBMap)[Pred];
 443     }
 444     if (!CheckIfPHIMatches(Pred, PredInfo, IncomingVal)) {
 445       IsMatch = false;
 446       break;
 447     }
 448   }
 449   return IsMatch;
 450 }
 451
 452 /// RecordMatchingPHI - For a PHI node that matches, record it and its input
 453 /// PHIs in both the BBMap and the AvailableVals mapping.
 454 void SSAUpdater::RecordMatchingPHI(PHINode *PHI) {
 455   BBMapTy *BBMap = getBBMap(BM);
 456   AvailableValsTy &AvailableVals = getAvailableVals(AV);
 457   SmallVector<PHINode*, 20> WorkList;
 458   WorkList.push_back(PHI);
 459
 460   while (!WorkList.empty()) {
 461     PHI = WorkList.pop_back_val();
 462     BasicBlock *BB = PHI->getParent();
 463     BBInfo *Info = (*BBMap)[BB];
 464     if (!Info || Info->AvailableVal)
 465       return;
 466
 467     // Record the PHI.
 468     AvailableVals[BB] = PHI;
 469     Info->AvailableVal = PHI;
 470
 471     // Iterate through the PHI's incoming values.
 472     for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
 473       PHINode *IncomingVal = dyn_cast<PHINode>(PHI->getIncomingValue(i));
 474       if (!IncomingVal) continue;
 475       WorkList.push_back(IncomingVal);
 476     }
 477   }
 478 }
 479
 480 /// ClearPHITags - When one of the existing PHI nodes fails to match, clear
 481 /// the PHITag values that were stored in the BBMap when checking to see if
 482 /// it matched.
 483 void SSAUpdater::ClearPHITags(PHINode *PHI) {
 484   BBMapTy *BBMap = getBBMap(BM);
 485   SmallVector<PHINode*, 20> WorkList;
 486   WorkList.push_back(PHI);
 487
 488   while (!WorkList.empty()) {
 489     PHI = WorkList.pop_back_val();
 490     BasicBlock *BB = PHI->getParent();
 491     BBInfo *Info = (*BBMap)[BB];
 492     if (!Info || Info->AvailableVal || !Info->PHITag)
 493       continue;
 494
 495     // Clear the tag.
 496     Info->PHITag = 0;
 497
 498     // Iterate through the PHI's incoming values.
 499     for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
 500       PHINode *IncomingVal = dyn_cast<PHINode>(PHI->getIncomingValue(i));
 501       if (!IncomingVal) continue;
 502       WorkList.push_back(IncomingVal);
 503     }
 504   }
 505 }