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