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 /// GetExistingPHI - Check if BB already contains a phi node that is equivalent
 139 /// to the specified mapping from predecessor blocks to incoming values.
 140 static Value *GetExistingPHI(BasicBlock *BB,
 141                              DenseMap<BasicBlock*, Value*> &ValueMapping) {
 142   PHINode *SomePHI;
 143   for (BasicBlock::iterator It = BB->begin();
 144        (SomePHI = dyn_cast<PHINode>(It)); ++It) {
 145     if (IsEquivalentPHI(SomePHI, ValueMapping))
 146       return SomePHI;
 147   }
 148   return 0;
 149 }
 150
 151 /// GetExistingPHI - Check if BB already contains an equivalent phi node.
 152 /// The InputIt type must be an iterator over std::pair<BasicBlock*, Value*>
 153 /// objects that specify the mapping from predecessor blocks to incoming values.
 154 template<typename InputIt>
 155 static Value *GetExistingPHI(BasicBlock *BB, const InputIt &I,
 156                              const InputIt &E) {
 157   // Avoid create the mapping if BB has no phi nodes at all.
 158   if (!isa<PHINode>(BB->begin()))
 159     return 0;
 160   DenseMap<BasicBlock*, Value*> ValueMapping(I, E);
 161   return GetExistingPHI(BB, ValueMapping);
 162 }
 163
 164 /// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is
 165 /// live at the end of the specified block.
 166 Value *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) {
 167   assert(BM == 0 && BPA == 0 && "Unexpected Internal State");
 168   Value *Res = GetValueAtEndOfBlockInternal(BB);
 169   assert(BM == 0 && BPA == 0 && "Unexpected Internal State");
 170   return Res;
 171 }
 172
 173 /// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that
 174 /// is live in the middle of the specified block.
 175 ///
 176 /// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one
 177 /// important case: if there is a definition of the rewritten value after the
 178 /// 'use' in BB.  Consider code like this:
 179 ///
 180 ///      X1 = ...
 181 ///   SomeBB:
 182 ///      use(X)
 183 ///      X2 = ...
 184 ///      br Cond, SomeBB, OutBB
 185 ///
 186 /// In this case, there are two values (X1 and X2) added to the AvailableVals
 187 /// set by the client of the rewriter, and those values are both live out of
 188 /// their respective blocks.  However, the use of X happens in the *middle* of
 189 /// a block.  Because of this, we need to insert a new PHI node in SomeBB to
 190 /// merge the appropriate values, and this value isn't live out of the block.
 191 ///
 192 Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) {
 193   // If there is no definition of the renamed variable in this block, just use
 194   // GetValueAtEndOfBlock to do our work.
 195   if (!HasValueForBlock(BB))
 196     return GetValueAtEndOfBlock(BB);
 197
 198   // Otherwise, we have the hard case.  Get the live-in values for each
 199   // predecessor.
 200   SmallVector<std::pair<BasicBlock*, Value*>, 8> PredValues;
 201   Value *SingularValue = 0;
 202
 203   // We can get our predecessor info by walking the pred_iterator list, but it
 204   // is relatively slow.  If we already have PHI nodes in this block, walk one
 205   // of them to get the predecessor list instead.
 206   if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) {
 207     for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) {
 208       BasicBlock *PredBB = SomePhi->getIncomingBlock(i);
 209       Value *PredVal = GetValueAtEndOfBlock(PredBB);
 210       PredValues.push_back(std::make_pair(PredBB, PredVal));
 211
 212       // Compute SingularValue.
 213       if (i == 0)
 214         SingularValue = PredVal;
 215       else if (PredVal != SingularValue)
 216         SingularValue = 0;
 217     }
 218   } else {
 219     bool isFirstPred = true;
 220     for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
 221       BasicBlock *PredBB = *PI;
 222       Value *PredVal = GetValueAtEndOfBlock(PredBB);
 223       PredValues.push_back(std::make_pair(PredBB, PredVal));
 224
 225       // Compute SingularValue.
 226       if (isFirstPred) {
 227         SingularValue = PredVal;
 228         isFirstPred = false;
 229       } else if (PredVal != SingularValue)
 230         SingularValue = 0;
 231     }
 232   }
 233
 234   // If there are no predecessors, just return undef.
 235   if (PredValues.empty())
 236     return UndefValue::get(PrototypeValue->getType());
 237
 238   // Otherwise, if all the merged values are the same, just use it.
 239   if (SingularValue != 0)
 240     return SingularValue;
 241
 242   // Otherwise, we do need a PHI.
 243   if (Value *ExistingPHI = GetExistingPHI(BB, PredValues.begin(),
 244                                           PredValues.end()))
 245     return ExistingPHI;
 246
 247   // Ok, we have no way out, insert a new one now.
 248   PHINode *InsertedPHI = PHINode::Create(PrototypeValue->getType(),
 249                                          PrototypeValue->getName(),
 250                                          &BB->front());
 251   InsertedPHI->reserveOperandSpace(PredValues.size());
 252
 253   // Fill in all the predecessors of the PHI.
 254   for (unsigned i = 0, e = PredValues.size(); i != e; ++i)
 255     InsertedPHI->addIncoming(PredValues[i].second, PredValues[i].first);
 256
 257   // See if the PHI node can be merged to a single value.  This can happen in
 258   // loop cases when we get a PHI of itself and one other value.
 259   if (Value *ConstVal = InsertedPHI->hasConstantValue()) {
 260     InsertedPHI->eraseFromParent();
 261     return ConstVal;
 262   }
 263
 264   // If the client wants to know about all new instructions, tell it.
 265   if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);
 266
 267   DEBUG(dbgs() << "  Inserted PHI: " << *InsertedPHI << "\n");
 268   return InsertedPHI;
 269 }
 270
 271 /// RewriteUse - Rewrite a use of the symbolic value.  This handles PHI nodes,
 272 /// which use their value in the corresponding predecessor.
 273 void SSAUpdater::RewriteUse(Use &U) {
 274   Instruction *User = cast<Instruction>(U.getUser());
 275
 276   Value *V;
 277   if (PHINode *UserPN = dyn_cast<PHINode>(User))
 278     V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));
 279   else
 280     V = GetValueInMiddleOfBlock(User->getParent());
 281
 282   U.set(V);
 283 }
 284
 285 /// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry
 286 /// for the specified BB and if so, return it.  If not, construct SSA form by
 287 /// first calculating the required placement of PHIs and then inserting new
 288 /// PHIs where needed.
 289 Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) {
 290   AvailableValsTy &AvailableVals = getAvailableVals(AV);
 291   if (Value *V = AvailableVals[BB])
 292     return V;
 293
 294   // Pool allocation used internally by GetValueAtEndOfBlock.
 295   BumpPtrAllocator AllocatorObj;
 296   BBMapTy BBMapObj;
 297   BPA = &AllocatorObj;
 298   BM = &BBMapObj;
 299
 300   BBInfo *Info = new (AllocatorObj) BBInfo(BB, 0, &AllocatorObj);
 301   BBMapObj[BB] = Info;
 302
 303   bool Changed;
 304   unsigned Counter = 1;
 305   do {
 306     Changed = false;
 307     FindPHIPlacement(BB, Info, Changed, Counter);
 308     ++Counter;
 309   } while (Changed);
 310
 311   FindAvailableVal(BB, Info, Counter);
 312
 313   BPA = 0;
 314   BM = 0;
 315   return Info->AvailableVal;
 316 }
 317
 318 /// FindPHIPlacement - Recursively visit the predecessors of a block to find
 319 /// the reaching definition for each predecessor and then determine whether
 320 /// a PHI is needed in this block.
 321 void SSAUpdater::FindPHIPlacement(BasicBlock *BB, BBInfo *Info, bool &Changed,
 322                                   unsigned Counter) {
 323   AvailableValsTy &AvailableVals = getAvailableVals(AV);
 324   BBMapTy *BBMap = getBBMap(BM);
 325   BumpPtrAllocator *Allocator = getAllocator(BPA);
 326   bool BBNeedsPHI = false;
 327   BasicBlock *SamePredDefBB = 0;
 328
 329   // If there are no predecessors, then we must have found an unreachable
 330   // block.  Treat it as a definition with 'undef'.
 331   if (Info->NumPreds == 0) {
 332     Info->AvailableVal = UndefValue::get(PrototypeValue->getType());
 333     Info->DefBB = BB;
 334     return;
 335   }
 336
 337   Info->Counter = Counter;
 338   for (unsigned pi = 0; pi != Info->NumPreds; ++pi) {
 339     BasicBlock *Pred = Info->Preds[pi];
 340     BBMapTy::value_type &BBMapBucket = BBMap->FindAndConstruct(Pred);
 341     if (!BBMapBucket.second) {
 342       Value *PredVal = AvailableVals.lookup(Pred);
 343       BBMapBucket.second = new (*Allocator) BBInfo(Pred, PredVal, Allocator);
 344     }
 345     BBInfo *PredInfo = BBMapBucket.second;
 346     BasicBlock *DefBB = 0;
 347     if (!PredInfo->AvailableVal) {
 348       if (PredInfo->Counter != Counter)
 349         FindPHIPlacement(Pred, PredInfo, Changed, Counter);
 350
 351       // Ignore back edges where the value is not yet known.
 352       if (!PredInfo->DefBB)
 353         continue;
 354     }
 355     DefBB = PredInfo->DefBB;
 356
 357     if (!SamePredDefBB)
 358       SamePredDefBB = DefBB;
 359     else if (DefBB != SamePredDefBB)
 360       BBNeedsPHI = true;
 361   }
 362
 363   BasicBlock *NewDefBB = (BBNeedsPHI ? BB : SamePredDefBB);
 364   if (Info->DefBB != NewDefBB) {
 365     Changed = true;
 366     Info->DefBB = NewDefBB;
 367   }
 368 }
 369
 370 /// FindAvailableVal - If this block requires a PHI, first check if an existing
 371 /// PHI matches the PHI placement and reaching definitions computed earlier,
 372 /// and if not, create a new PHI.  Visit all the block's predecessors to
 373 /// calculate the available value for each one and fill in the incoming values
 374 /// for a new PHI.
 375 void SSAUpdater::FindAvailableVal(BasicBlock *BB, BBInfo *Info,
 376                                   unsigned Counter) {
 377   if (Info->AvailableVal || Info->Counter == Counter)
 378     return;
 379
 380   AvailableValsTy &AvailableVals = getAvailableVals(AV);
 381   BBMapTy *BBMap = getBBMap(BM);
 382
 383   // Check if there needs to be a PHI in BB.
 384   PHINode *NewPHI = 0;
 385   if (Info->DefBB == BB) {
 386     // Look for an existing PHI.
 387     FindExistingPHI(BB, Info);
 388     if (!Info->AvailableVal) {
 389       NewPHI = PHINode::Create(PrototypeValue->getType(),
 390                                PrototypeValue->getName(), &BB->front());
 391       NewPHI->reserveOperandSpace(Info->NumPreds);
 392       Info->AvailableVal = NewPHI;
 393       AvailableVals[BB] = NewPHI;
 394     }
 395   }
 396
 397   // Iterate through the block's predecessors.
 398   Info->Counter = Counter;
 399   for (unsigned pi = 0; pi != Info->NumPreds; ++pi) {
 400     BasicBlock *Pred = Info->Preds[pi];
 401     BBInfo *PredInfo = (*BBMap)[Pred];
 402     FindAvailableVal(Pred, PredInfo, Counter);
 403     if (NewPHI) {
 404       // Skip to the nearest preceding definition.
 405       if (PredInfo->DefBB != Pred)
 406         PredInfo = (*BBMap)[PredInfo->DefBB];
 407       NewPHI->addIncoming(PredInfo->AvailableVal, Pred);
 408     } else if (!Info->AvailableVal)
 409       Info->AvailableVal = PredInfo->AvailableVal;
 410   }
 411
 412   if (NewPHI) {
 413     DEBUG(dbgs() << "  Inserted PHI: " << *NewPHI << "\n");
 414
 415     // If the client wants to know about all new instructions, tell it.
 416     if (InsertedPHIs) InsertedPHIs->push_back(NewPHI);
 417   }
 418 }
 419
 420 /// FindExistingPHI - Look through the PHI nodes in a block to see if any of
 421 /// them match what is needed.
 422 void SSAUpdater::FindExistingPHI(BasicBlock *BB, BBInfo *Info) {
 423   PHINode *SomePHI;
 424   for (BasicBlock::iterator It = BB->begin();
 425        (SomePHI = dyn_cast<PHINode>(It)); ++It) {
 426     if (CheckIfPHIMatches(BB, Info, SomePHI)) {
 427       RecordMatchingPHI(BB, Info, SomePHI);
 428       break;
 429     }
 430     ClearPHITags(BB, Info, SomePHI);
 431   }
 432 }
 433
 434 /// CheckIfPHIMatches - Check if Val is a PHI node in block BB that matches
 435 /// the placement and values in the BBMap.
 436 bool SSAUpdater::CheckIfPHIMatches(BasicBlock *BB, BBInfo *Info, Value *Val) {
 437   if (Info->AvailableVal)
 438     return Val == Info->AvailableVal;
 439
 440   // Check if Val is a PHI in this block.
 441   PHINode *PHI = dyn_cast<PHINode>(Val);
 442   if (!PHI || PHI->getParent() != BB)
 443     return false;
 444
 445   // If this block has already been visited, check if this PHI matches.
 446   if (Info->PHITag)
 447     return PHI == Info->PHITag;
 448   Info->PHITag = PHI;
 449   bool IsMatch = true;
 450
 451   // Iterate through the predecessors.
 452   BBMapTy *BBMap = getBBMap(BM);
 453   for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
 454     BasicBlock *Pred = PHI->getIncomingBlock(i);
 455     Value *IncomingVal = PHI->getIncomingValue(i);
 456     BBInfo *PredInfo = (*BBMap)[Pred];
 457     // Skip to the nearest preceding definition.
 458     if (PredInfo->DefBB != Pred) {
 459       Pred = PredInfo->DefBB;
 460       PredInfo = (*BBMap)[Pred];
 461     }
 462     if (!CheckIfPHIMatches(Pred, PredInfo, IncomingVal)) {
 463       IsMatch = false;
 464       break;
 465     }
 466   }
 467   return IsMatch;
 468 }
 469
 470 /// RecordMatchingPHI - For a PHI node that matches, record it in both the
 471 /// BBMap and the AvailableVals mapping.  Recursively record its input PHIs
 472 /// as well.
 473 void SSAUpdater::RecordMatchingPHI(BasicBlock *BB, BBInfo *Info, PHINode *PHI) {
 474   if (!Info || Info->AvailableVal)
 475     return;
 476
 477   // Record the PHI.
 478   AvailableValsTy &AvailableVals = getAvailableVals(AV);
 479   AvailableVals[BB] = PHI;
 480   Info->AvailableVal = PHI;
 481
 482   // Iterate through the predecessors.
 483   BBMapTy *BBMap = getBBMap(BM);
 484   for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
 485     PHINode *PHIVal = dyn_cast<PHINode>(PHI->getIncomingValue(i));
 486     if (!PHIVal) continue;
 487     BasicBlock *Pred = PHIVal->getParent();
 488     RecordMatchingPHI(Pred, (*BBMap)[Pred], PHIVal);
 489   }
 490 }
 491
 492 /// ClearPHITags - When one of the existing PHI nodes fails to match, clear
 493 /// the PHITag values stored in the BBMap while checking to see if it matched.
 494 void SSAUpdater::ClearPHITags(BasicBlock *BB, BBInfo *Info, PHINode *PHI) {
 495   if (!Info || Info->AvailableVal || !Info->PHITag)
 496     return;
 497
 498   // Clear the tag.
 499   Info->PHITag = 0;
 500
 501   // Iterate through the predecessors.
 502   BBMapTy *BBMap = getBBMap(BM);
 503   for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
 504     PHINode *PHIVal = dyn_cast<PHINode>(PHI->getIncomingValue(i));
 505     if (!PHIVal) continue;
 506     BasicBlock *Pred = PHIVal->getParent();
 507     ClearPHITags(Pred, (*BBMap)[Pred], PHIVal);
 508   }
 509 }