contrib/llvm/include/llvm/Transforms/Utils/SSAUpdaterImpl.h

   1 //===-- SSAUpdaterImpl.h - SSA Updater Implementation -----------*- C++ -*-===//
   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 provides a template that implements the core algorithm for the
  11 // SSAUpdater and MachineSSAUpdater.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
  16 #define LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
  17
  18 namespace llvm {
  19
  20 template<typename T> class SSAUpdaterTraits;
  21
  22 template<typename UpdaterT>
  23 class SSAUpdaterImpl {
  24 private:
  25   UpdaterT *Updater;
  26
  27   typedef SSAUpdaterTraits<UpdaterT> Traits;
  28   typedef typename Traits::BlkT BlkT;
  29   typedef typename Traits::ValT ValT;
  30   typedef typename Traits::PhiT PhiT;
  31
  32   /// BBInfo - Per-basic block information used internally by SSAUpdaterImpl.
  33   /// The predecessors of each block are cached here since pred_iterator is
  34   /// slow and we need to iterate over the blocks at least a few times.
  35   class BBInfo {
  36   public:
  37     BlkT *BB;          // Back-pointer to the corresponding block.
  38     ValT AvailableVal; // Value to use in this block.
  39     BBInfo *DefBB;     // Block that defines the available value.
  40     int BlkNum;        // Postorder number.
  41     BBInfo *IDom;      // Immediate dominator.
  42     unsigned NumPreds; // Number of predecessor blocks.
  43     BBInfo **Preds;    // Array[NumPreds] of predecessor blocks.
  44     PhiT *PHITag;      // Marker for existing PHIs that match.
  45
  46     BBInfo(BlkT *ThisBB, ValT V)
  47       : BB(ThisBB), AvailableVal(V), DefBB(V ? this : 0), BlkNum(0), IDom(0),
  48       NumPreds(0), Preds(0), PHITag(0) { }
  49   };
  50
  51   typedef DenseMap<BlkT*, ValT> AvailableValsTy;
  52   AvailableValsTy *AvailableVals;
  53
  54   SmallVectorImpl<PhiT*> *InsertedPHIs;
  55
  56   typedef SmallVectorImpl<BBInfo*> BlockListTy;
  57   typedef DenseMap<BlkT*, BBInfo*> BBMapTy;
  58   BBMapTy BBMap;
  59   BumpPtrAllocator Allocator;
  60
  61 public:
  62   explicit SSAUpdaterImpl(UpdaterT *U, AvailableValsTy *A,
  63                           SmallVectorImpl<PhiT*> *Ins) :
  64     Updater(U), AvailableVals(A), InsertedPHIs(Ins) { }
  65
  66   /// GetValue - Check to see if AvailableVals has an entry for the specified
  67   /// BB and if so, return it.  If not, construct SSA form by first
  68   /// calculating the required placement of PHIs and then inserting new PHIs
  69   /// where needed.
  70   ValT GetValue(BlkT *BB) {
  71     SmallVector<BBInfo*, 100> BlockList;
  72     BBInfo *PseudoEntry = BuildBlockList(BB, &BlockList);
  73
  74     // Special case: bail out if BB is unreachable.
  75     if (BlockList.size() == 0) {
  76       ValT V = Traits::GetUndefVal(BB, Updater);
  77       (*AvailableVals)[BB] = V;
  78       return V;
  79     }
  80
  81     FindDominators(&BlockList, PseudoEntry);
  82     FindPHIPlacement(&BlockList);
  83     FindAvailableVals(&BlockList);
  84
  85     return BBMap[BB]->DefBB->AvailableVal;
  86   }
  87
  88   /// BuildBlockList - Starting from the specified basic block, traverse back
  89   /// through its predecessors until reaching blocks with known values.
  90   /// Create BBInfo structures for the blocks and append them to the block
  91   /// list.
  92   BBInfo *BuildBlockList(BlkT *BB, BlockListTy *BlockList) {
  93     SmallVector<BBInfo*, 10> RootList;
  94     SmallVector<BBInfo*, 64> WorkList;
  95
  96     BBInfo *Info = new (Allocator) BBInfo(BB, 0);
  97     BBMap[BB] = Info;
  98     WorkList.push_back(Info);
  99
 100     // Search backward from BB, creating BBInfos along the way and stopping
 101     // when reaching blocks that define the value.  Record those defining
 102     // blocks on the RootList.
 103     SmallVector<BlkT*, 10> Preds;
 104     while (!WorkList.empty()) {
 105       Info = WorkList.pop_back_val();
 106       Preds.clear();
 107       Traits::FindPredecessorBlocks(Info->BB, &Preds);
 108       Info->NumPreds = Preds.size();
 109       if (Info->NumPreds == 0)
 110         Info->Preds = 0;
 111       else
 112         Info->Preds = static_cast<BBInfo**>
 113           (Allocator.Allocate(Info->NumPreds * sizeof(BBInfo*),
 114                               AlignOf<BBInfo*>::Alignment));
 115
 116       for (unsigned p = 0; p != Info->NumPreds; ++p) {
 117         BlkT *Pred = Preds[p];
 118         // Check if BBMap already has a BBInfo for the predecessor block.
 119         typename BBMapTy::value_type &BBMapBucket =
 120           BBMap.FindAndConstruct(Pred);
 121         if (BBMapBucket.second) {
 122           Info->Preds[p] = BBMapBucket.second;
 123           continue;
 124         }
 125
 126         // Create a new BBInfo for the predecessor.
 127         ValT PredVal = AvailableVals->lookup(Pred);
 128         BBInfo *PredInfo = new (Allocator) BBInfo(Pred, PredVal);
 129         BBMapBucket.second = PredInfo;
 130         Info->Preds[p] = PredInfo;
 131
 132         if (PredInfo->AvailableVal) {
 133           RootList.push_back(PredInfo);
 134           continue;
 135         }
 136         WorkList.push_back(PredInfo);
 137       }
 138     }
 139
 140     // Now that we know what blocks are backwards-reachable from the starting
 141     // block, do a forward depth-first traversal to assign postorder numbers
 142     // to those blocks.
 143     BBInfo *PseudoEntry = new (Allocator) BBInfo(0, 0);
 144     unsigned BlkNum = 1;
 145
 146     // Initialize the worklist with the roots from the backward traversal.
 147     while (!RootList.empty()) {
 148       Info = RootList.pop_back_val();
 149       Info->IDom = PseudoEntry;
 150       Info->BlkNum = -1;
 151       WorkList.push_back(Info);
 152     }
 153
 154     while (!WorkList.empty()) {
 155       Info = WorkList.back();
 156
 157       if (Info->BlkNum == -2) {
 158         // All the successors have been handled; assign the postorder number.
 159         Info->BlkNum = BlkNum++;
 160         // If not a root, put it on the BlockList.
 161         if (!Info->AvailableVal)
 162           BlockList->push_back(Info);
 163         WorkList.pop_back();
 164         continue;
 165       }
 166
 167       // Leave this entry on the worklist, but set its BlkNum to mark that its
 168       // successors have been put on the worklist.  When it returns to the top
 169       // the list, after handling its successors, it will be assigned a
 170       // number.
 171       Info->BlkNum = -2;
 172
 173       // Add unvisited successors to the work list.
 174       for (typename Traits::BlkSucc_iterator SI =
 175              Traits::BlkSucc_begin(Info->BB),
 176              E = Traits::BlkSucc_end(Info->BB); SI != E; ++SI) {
 177         BBInfo *SuccInfo = BBMap[*SI];
 178         if (!SuccInfo || SuccInfo->BlkNum)
 179           continue;
 180         SuccInfo->BlkNum = -1;
 181         WorkList.push_back(SuccInfo);
 182       }
 183     }
 184     PseudoEntry->BlkNum = BlkNum;
 185     return PseudoEntry;
 186   }
 187
 188   /// IntersectDominators - This is the dataflow lattice "meet" operation for
 189   /// finding dominators.  Given two basic blocks, it walks up the dominator
 190   /// tree until it finds a common dominator of both.  It uses the postorder
 191   /// number of the blocks to determine how to do that.
 192   BBInfo *IntersectDominators(BBInfo *Blk1, BBInfo *Blk2) {
 193     while (Blk1 != Blk2) {
 194       while (Blk1->BlkNum < Blk2->BlkNum) {
 195         Blk1 = Blk1->IDom;
 196         if (!Blk1)
 197           return Blk2;
 198       }
 199       while (Blk2->BlkNum < Blk1->BlkNum) {
 200         Blk2 = Blk2->IDom;
 201         if (!Blk2)
 202           return Blk1;
 203       }
 204     }
 205     return Blk1;
 206   }
 207
 208   /// FindDominators - Calculate the dominator tree for the subset of the CFG
 209   /// corresponding to the basic blocks on the BlockList.  This uses the
 210   /// algorithm from: "A Simple, Fast Dominance Algorithm" by Cooper, Harvey
 211   /// and Kennedy, published in Software--Practice and Experience, 2001,
 212   /// 4:1-10.  Because the CFG subset does not include any edges leading into
 213   /// blocks that define the value, the results are not the usual dominator
 214   /// tree.  The CFG subset has a single pseudo-entry node with edges to a set
 215   /// of root nodes for blocks that define the value.  The dominators for this
 216   /// subset CFG are not the standard dominators but they are adequate for
 217   /// placing PHIs within the subset CFG.
 218   void FindDominators(BlockListTy *BlockList, BBInfo *PseudoEntry) {
 219     bool Changed;
 220     do {
 221       Changed = false;
 222       // Iterate over the list in reverse order, i.e., forward on CFG edges.
 223       for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
 224              E = BlockList->rend(); I != E; ++I) {
 225         BBInfo *Info = *I;
 226         BBInfo *NewIDom = 0;
 227
 228         // Iterate through the block's predecessors.
 229         for (unsigned p = 0; p != Info->NumPreds; ++p) {
 230           BBInfo *Pred = Info->Preds[p];
 231
 232           // Treat an unreachable predecessor as a definition with 'undef'.
 233           if (Pred->BlkNum == 0) {
 234             Pred->AvailableVal = Traits::GetUndefVal(Pred->BB, Updater);
 235             (*AvailableVals)[Pred->BB] = Pred->AvailableVal;
 236             Pred->DefBB = Pred;
 237             Pred->BlkNum = PseudoEntry->BlkNum;
 238             PseudoEntry->BlkNum++;
 239           }
 240
 241           if (!NewIDom)
 242             NewIDom = Pred;
 243           else
 244             NewIDom = IntersectDominators(NewIDom, Pred);
 245         }
 246
 247         // Check if the IDom value has changed.
 248         if (NewIDom && NewIDom != Info->IDom) {
 249           Info->IDom = NewIDom;
 250           Changed = true;
 251         }
 252       }
 253     } while (Changed);
 254   }
 255
 256   /// IsDefInDomFrontier - Search up the dominator tree from Pred to IDom for
 257   /// any blocks containing definitions of the value.  If one is found, then
 258   /// the successor of Pred is in the dominance frontier for the definition,
 259   /// and this function returns true.
 260   bool IsDefInDomFrontier(const BBInfo *Pred, const BBInfo *IDom) {
 261     for (; Pred != IDom; Pred = Pred->IDom) {
 262       if (Pred->DefBB == Pred)
 263         return true;
 264     }
 265     return false;
 266   }
 267
 268   /// FindPHIPlacement - PHIs are needed in the iterated dominance frontiers
 269   /// of the known definitions.  Iteratively add PHIs in the dom frontiers
 270   /// until nothing changes.  Along the way, keep track of the nearest
 271   /// dominating definitions for non-PHI blocks.
 272   void FindPHIPlacement(BlockListTy *BlockList) {
 273     bool Changed;
 274     do {
 275       Changed = false;
 276       // Iterate over the list in reverse order, i.e., forward on CFG edges.
 277       for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
 278              E = BlockList->rend(); I != E; ++I) {
 279         BBInfo *Info = *I;
 280
 281         // If this block already needs a PHI, there is nothing to do here.
 282         if (Info->DefBB == Info)
 283           continue;
 284
 285         // Default to use the same def as the immediate dominator.
 286         BBInfo *NewDefBB = Info->IDom->DefBB;
 287         for (unsigned p = 0; p != Info->NumPreds; ++p) {
 288           if (IsDefInDomFrontier(Info->Preds[p], Info->IDom)) {
 289             // Need a PHI here.
 290             NewDefBB = Info;
 291             break;
 292           }
 293         }
 294
 295         // Check if anything changed.
 296         if (NewDefBB != Info->DefBB) {
 297           Info->DefBB = NewDefBB;
 298           Changed = true;
 299         }
 300       }
 301     } while (Changed);
 302   }
 303
 304   /// FindAvailableVal - If this block requires a PHI, first check if an
 305   /// existing PHI matches the PHI placement and reaching definitions computed
 306   /// earlier, and if not, create a new PHI.  Visit all the block's
 307   /// predecessors to calculate the available value for each one and fill in
 308   /// the incoming values for a new PHI.
 309   void FindAvailableVals(BlockListTy *BlockList) {
 310     // Go through the worklist in forward order (i.e., backward through the CFG)
 311     // and check if existing PHIs can be used.  If not, create empty PHIs where
 312     // they are needed.
 313     for (typename BlockListTy::iterator I = BlockList->begin(),
 314            E = BlockList->end(); I != E; ++I) {
 315       BBInfo *Info = *I;
 316       // Check if there needs to be a PHI in BB.
 317       if (Info->DefBB != Info)
 318         continue;
 319
 320       // Look for an existing PHI.
 321       FindExistingPHI(Info->BB, BlockList);
 322       if (Info->AvailableVal)
 323         continue;
 324
 325       ValT PHI = Traits::CreateEmptyPHI(Info->BB, Info->NumPreds, Updater);
 326       Info->AvailableVal = PHI;
 327       (*AvailableVals)[Info->BB] = PHI;
 328     }
 329
 330     // Now go back through the worklist in reverse order to fill in the
 331     // arguments for any new PHIs added in the forward traversal.
 332     for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
 333            E = BlockList->rend(); I != E; ++I) {
 334       BBInfo *Info = *I;
 335
 336       if (Info->DefBB != Info) {
 337         // Record the available value at join nodes to speed up subsequent
 338         // uses of this SSAUpdater for the same value.
 339         if (Info->NumPreds > 1)
 340           (*AvailableVals)[Info->BB] = Info->DefBB->AvailableVal;
 341         continue;
 342       }
 343
 344       // Check if this block contains a newly added PHI.
 345       PhiT *PHI = Traits::ValueIsNewPHI(Info->AvailableVal, Updater);
 346       if (!PHI)
 347         continue;
 348
 349       // Iterate through the block's predecessors.
 350       for (unsigned p = 0; p != Info->NumPreds; ++p) {
 351         BBInfo *PredInfo = Info->Preds[p];
 352         BlkT *Pred = PredInfo->BB;
 353         // Skip to the nearest preceding definition.
 354         if (PredInfo->DefBB != PredInfo)
 355           PredInfo = PredInfo->DefBB;
 356         Traits::AddPHIOperand(PHI, PredInfo->AvailableVal, Pred);
 357       }
 358
 359       DEBUG(dbgs() << "  Inserted PHI: " << *PHI << "\n");
 360
 361       // If the client wants to know about all new instructions, tell it.
 362       if (InsertedPHIs) InsertedPHIs->push_back(PHI);
 363     }
 364   }
 365
 366   /// FindExistingPHI - Look through the PHI nodes in a block to see if any of
 367   /// them match what is needed.
 368   void FindExistingPHI(BlkT *BB, BlockListTy *BlockList) {
 369     for (typename BlkT::iterator BBI = BB->begin(), BBE = BB->end();
 370          BBI != BBE; ++BBI) {
 371       PhiT *SomePHI = Traits::InstrIsPHI(BBI);
 372       if (!SomePHI)
 373         break;
 374       if (CheckIfPHIMatches(SomePHI)) {
 375         RecordMatchingPHI(SomePHI);
 376         break;
 377       }
 378       // Match failed: clear all the PHITag values.
 379       for (typename BlockListTy::iterator I = BlockList->begin(),
 380              E = BlockList->end(); I != E; ++I)
 381         (*I)->PHITag = 0;
 382     }
 383   }
 384
 385   /// CheckIfPHIMatches - Check if a PHI node matches the placement and values
 386   /// in the BBMap.
 387   bool CheckIfPHIMatches(PhiT *PHI) {
 388     SmallVector<PhiT*, 20> WorkList;
 389     WorkList.push_back(PHI);
 390
 391     // Mark that the block containing this PHI has been visited.
 392     BBMap[PHI->getParent()]->PHITag = PHI;
 393
 394     while (!WorkList.empty()) {
 395       PHI = WorkList.pop_back_val();
 396
 397       // Iterate through the PHI's incoming values.
 398       for (typename Traits::PHI_iterator I = Traits::PHI_begin(PHI),
 399              E = Traits::PHI_end(PHI); I != E; ++I) {
 400         ValT IncomingVal = I.getIncomingValue();
 401         BBInfo *PredInfo = BBMap[I.getIncomingBlock()];
 402         // Skip to the nearest preceding definition.
 403         if (PredInfo->DefBB != PredInfo)
 404           PredInfo = PredInfo->DefBB;
 405
 406         // Check if it matches the expected value.
 407         if (PredInfo->AvailableVal) {
 408           if (IncomingVal == PredInfo->AvailableVal)
 409             continue;
 410           return false;
 411         }
 412
 413         // Check if the value is a PHI in the correct block.
 414         PhiT *IncomingPHIVal = Traits::ValueIsPHI(IncomingVal, Updater);
 415         if (!IncomingPHIVal || IncomingPHIVal->getParent() != PredInfo->BB)
 416           return false;
 417
 418         // If this block has already been visited, check if this PHI matches.
 419         if (PredInfo->PHITag) {
 420           if (IncomingPHIVal == PredInfo->PHITag)
 421             continue;
 422           return false;
 423         }
 424         PredInfo->PHITag = IncomingPHIVal;
 425
 426         WorkList.push_back(IncomingPHIVal);
 427       }
 428     }
 429     return true;
 430   }
 431
 432   /// RecordMatchingPHI - For a PHI node that matches, record it and its input
 433   /// PHIs in both the BBMap and the AvailableVals mapping.
 434   void RecordMatchingPHI(PhiT *PHI) {
 435     SmallVector<PhiT*, 20> WorkList;
 436     WorkList.push_back(PHI);
 437
 438     // Record this PHI.
 439     BlkT *BB = PHI->getParent();
 440     ValT PHIVal = Traits::GetPHIValue(PHI);
 441     (*AvailableVals)[BB] = PHIVal;
 442     BBMap[BB]->AvailableVal = PHIVal;
 443
 444     while (!WorkList.empty()) {
 445       PHI = WorkList.pop_back_val();
 446
 447       // Iterate through the PHI's incoming values.
 448       for (typename Traits::PHI_iterator I = Traits::PHI_begin(PHI),
 449              E = Traits::PHI_end(PHI); I != E; ++I) {
 450         ValT IncomingVal = I.getIncomingValue();
 451         PhiT *IncomingPHI = Traits::ValueIsPHI(IncomingVal, Updater);
 452         if (!IncomingPHI) continue;
 453         BB = IncomingPHI->getParent();
 454         BBInfo *Info = BBMap[BB];
 455         if (!Info || Info->AvailableVal)
 456           continue;
 457
 458         // Record the PHI and add it to the worklist.
 459         (*AvailableVals)[BB] = IncomingVal;
 460         Info->AvailableVal = IncomingVal;
 461         WorkList.push_back(IncomingPHI);
 462       }
 463     }
 464   }
 465 };
 466
 467 } // End llvm namespace
 468
 469 #endif