1 //===- GenericDomTreeUpdaterImpl.h ------------------------------*- 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 implements the GenericDomTreeUpdater class. This file should only 10 // be included by files that implement a specialization of the relevant 11 // templates. Currently these are: 12 // - llvm/lib/Analysis/DomTreeUpdater.cpp 13 // - llvm/lib/CodeGen/MachineDomTreeUpdater.cpp 14 // 15 //===----------------------------------------------------------------------===// 16 #ifndef LLVM_ANALYSIS_GENERICDOMTREEUPDATERIMPL_H 17 #define LLVM_ANALYSIS_GENERICDOMTREEUPDATERIMPL_H 18 19 #include "llvm/ADT/SmallBitVector.h" 20 #include "llvm/Analysis/GenericDomTreeUpdater.h" 21 #include "llvm/Support/Debug.h" 22 #include "llvm/Support/raw_ostream.h" 23 24 namespace llvm { 25 26 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT> 27 template <typename FuncT> 28 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::recalculate( 29 FuncT &F) { 30 if (Strategy == UpdateStrategy::Eager) { 31 if (DT) 32 DT->recalculate(F); 33 if (PDT) 34 PDT->recalculate(F); 35 return; 36 } 37 38 // There is little performance gain if we pend the recalculation under 39 // Lazy UpdateStrategy so we recalculate available trees immediately. 40 41 // Prevent forceFlushDeletedBB() from erasing DomTree or PostDomTree nodes. 42 IsRecalculatingDomTree = IsRecalculatingPostDomTree = true; 43 44 // Because all trees are going to be up-to-date after recalculation, 45 // flush awaiting deleted BasicBlocks. 46 derived().forceFlushDeletedBB(); 47 if (DT) 48 DT->recalculate(F); 49 if (PDT) 50 PDT->recalculate(F); 51 52 // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes. 53 IsRecalculatingDomTree = IsRecalculatingPostDomTree = false; 54 PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size(); 55 dropOutOfDateUpdates(); 56 } 57 58 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT> 59 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::applyUpdates( 60 ArrayRef<UpdateT> Updates) { 61 if (!DT && !PDT) 62 return; 63 64 if (Strategy == UpdateStrategy::Lazy) { 65 PendUpdates.reserve(PendUpdates.size() + Updates.size()); 66 for (const auto &U : Updates) 67 if (!isSelfDominance(U)) 68 PendUpdates.push_back(U); 69 70 return; 71 } 72 73 if (DT) 74 DT->applyUpdates(Updates); 75 if (PDT) 76 PDT->applyUpdates(Updates); 77 } 78 79 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT> 80 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>:: 81 applyUpdatesPermissive(ArrayRef<UpdateT> Updates) { 82 if (!DT && !PDT) 83 return; 84 85 SmallSet<std::pair<BasicBlockT *, BasicBlockT *>, 8> Seen; 86 SmallVector<UpdateT, 8> DeduplicatedUpdates; 87 for (const auto &U : Updates) { 88 auto Edge = std::make_pair(U.getFrom(), U.getTo()); 89 // Because it is illegal to submit updates that have already been applied 90 // and updates to an edge need to be strictly ordered, 91 // it is safe to infer the existence of an edge from the first update 92 // to this edge. 93 // If the first update to an edge is "Delete", it means that the edge 94 // existed before. If the first update to an edge is "Insert", it means 95 // that the edge didn't exist before. 96 // 97 // For example, if the user submits {{Delete, A, B}, {Insert, A, B}}, 98 // because 99 // 1. it is illegal to submit updates that have already been applied, 100 // i.e., user cannot delete an nonexistent edge, 101 // 2. updates to an edge need to be strictly ordered, 102 // So, initially edge A -> B existed. 103 // We can then safely ignore future updates to this edge and directly 104 // inspect the current CFG: 105 // a. If the edge still exists, because the user cannot insert an existent 106 // edge, so both {Delete, A, B}, {Insert, A, B} actually happened and 107 // resulted in a no-op. DTU won't submit any update in this case. 108 // b. If the edge doesn't exist, we can then infer that {Delete, A, B} 109 // actually happened but {Insert, A, B} was an invalid update which never 110 // happened. DTU will submit {Delete, A, B} in this case. 111 if (!isSelfDominance(U) && Seen.insert(Edge).second) { 112 // If the update doesn't appear in the CFG, it means that 113 // either the change isn't made or relevant operations 114 // result in a no-op. 115 if (isUpdateValid(U)) { 116 if (isLazy()) 117 PendUpdates.push_back(U); 118 else 119 DeduplicatedUpdates.push_back(U); 120 } 121 } 122 } 123 124 if (Strategy == UpdateStrategy::Lazy) 125 return; 126 127 if (DT) 128 DT->applyUpdates(DeduplicatedUpdates); 129 if (PDT) 130 PDT->applyUpdates(DeduplicatedUpdates); 131 } 132 133 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT> 134 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::splitCriticalEdge( 135 BasicBlockT *FromBB, BasicBlockT *ToBB, BasicBlockT *NewBB) { 136 if (!DT && !PDT) 137 return; 138 139 CriticalEdge E = {FromBB, ToBB, NewBB}; 140 if (Strategy == UpdateStrategy::Lazy) { 141 PendUpdates.push_back(E); 142 return; 143 } 144 145 if (DT) 146 splitDTCriticalEdges(E); 147 if (PDT) 148 splitPDTCriticalEdges(E); 149 } 150 151 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT> 152 DomTreeT & 153 GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::getDomTree() { 154 assert(DT && "Invalid acquisition of a null DomTree"); 155 applyDomTreeUpdates(); 156 dropOutOfDateUpdates(); 157 return *DT; 158 } 159 160 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT> 161 PostDomTreeT & 162 GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::getPostDomTree() { 163 assert(PDT && "Invalid acquisition of a null PostDomTree"); 164 applyPostDomTreeUpdates(); 165 dropOutOfDateUpdates(); 166 return *PDT; 167 } 168 169 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT> 170 LLVM_DUMP_METHOD void 171 GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::dump() const { 172 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 173 raw_ostream &OS = llvm::dbgs(); 174 175 OS << "Available Trees: "; 176 if (DT || PDT) { 177 if (DT) 178 OS << "DomTree "; 179 if (PDT) 180 OS << "PostDomTree "; 181 OS << "\n"; 182 } else 183 OS << "None\n"; 184 185 OS << "UpdateStrategy: "; 186 if (Strategy == UpdateStrategy::Eager) { 187 OS << "Eager\n"; 188 return; 189 } else 190 OS << "Lazy\n"; 191 int Index = 0; 192 193 auto printBlockInfo = [&](BasicBlockT *BB, StringRef Ending) { 194 if (BB) { 195 auto S = BB->getName(); 196 if (!BB->hasName()) 197 S = "(no name)"; 198 OS << S << "(" << BB << ")" << Ending; 199 } else { 200 OS << "(badref)" << Ending; 201 } 202 }; 203 204 auto printUpdates = 205 [&](typename ArrayRef<DomTreeUpdate>::const_iterator begin, 206 typename ArrayRef<DomTreeUpdate>::const_iterator end) { 207 if (begin == end) 208 OS << " None\n"; 209 Index = 0; 210 for (auto It = begin, ItEnd = end; It != ItEnd; ++It) { 211 if (!It->IsCriticalEdgeSplit) { 212 auto U = It->Update; 213 OS << " " << Index << " : "; 214 ++Index; 215 if (U.getKind() == DomTreeT::Insert) 216 OS << "Insert, "; 217 else 218 OS << "Delete, "; 219 printBlockInfo(U.getFrom(), ", "); 220 printBlockInfo(U.getTo(), "\n"); 221 } else { 222 const auto &Edge = It->EdgeSplit; 223 OS << " " << Index++ << " : Split critical edge, "; 224 printBlockInfo(Edge.FromBB, ", "); 225 printBlockInfo(Edge.ToBB, ", "); 226 printBlockInfo(Edge.NewBB, "\n"); 227 } 228 } 229 }; 230 231 if (DT) { 232 const auto I = PendUpdates.begin() + PendDTUpdateIndex; 233 assert(PendUpdates.begin() <= I && I <= PendUpdates.end() && 234 "Iterator out of range."); 235 OS << "Applied but not cleared DomTreeUpdates:\n"; 236 printUpdates(PendUpdates.begin(), I); 237 OS << "Pending DomTreeUpdates:\n"; 238 printUpdates(I, PendUpdates.end()); 239 } 240 241 if (PDT) { 242 const auto I = PendUpdates.begin() + PendPDTUpdateIndex; 243 assert(PendUpdates.begin() <= I && I <= PendUpdates.end() && 244 "Iterator out of range."); 245 OS << "Applied but not cleared PostDomTreeUpdates:\n"; 246 printUpdates(PendUpdates.begin(), I); 247 OS << "Pending PostDomTreeUpdates:\n"; 248 printUpdates(I, PendUpdates.end()); 249 } 250 251 OS << "Pending DeletedBBs:\n"; 252 Index = 0; 253 for (const auto *BB : DeletedBBs) { 254 OS << " " << Index << " : "; 255 ++Index; 256 if (BB->hasName()) 257 OS << BB->getName() << "("; 258 else 259 OS << "(no name)("; 260 OS << BB << ")\n"; 261 } 262 #endif 263 } 264 265 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT> 266 template <bool IsForward> 267 void GenericDomTreeUpdater<DerivedT, DomTreeT, 268 PostDomTreeT>::applyUpdatesImpl() { 269 auto *DomTree = [&]() { 270 if constexpr (IsForward) 271 return DT; 272 else 273 return PDT; 274 }(); 275 // No pending DomTreeUpdates. 276 if (Strategy != UpdateStrategy::Lazy || !DomTree) 277 return; 278 size_t &PendUpdateIndex = IsForward ? PendDTUpdateIndex : PendPDTUpdateIndex; 279 280 // Only apply updates not are applied by (Post)DomTree. 281 while (IsForward ? hasPendingDomTreeUpdates() 282 : hasPendingPostDomTreeUpdates()) { 283 auto I = PendUpdates.begin() + PendUpdateIndex; 284 const auto E = PendUpdates.end(); 285 assert(I < E && "Iterator range invalid; there should be DomTree updates."); 286 if (!I->IsCriticalEdgeSplit) { 287 SmallVector<UpdateT, 32> NormalUpdates; 288 for (; I != E && !I->IsCriticalEdgeSplit; ++I) 289 NormalUpdates.push_back(I->Update); 290 DomTree->applyUpdates(NormalUpdates); 291 PendUpdateIndex += NormalUpdates.size(); 292 } else { 293 SmallVector<CriticalEdge> CriticalEdges; 294 for (; I != E && I->IsCriticalEdgeSplit; ++I) 295 CriticalEdges.push_back(I->EdgeSplit); 296 IsForward ? splitDTCriticalEdges(CriticalEdges) 297 : splitPDTCriticalEdges(CriticalEdges); 298 PendUpdateIndex += CriticalEdges.size(); 299 } 300 } 301 } 302 303 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT> 304 bool GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::isUpdateValid( 305 UpdateT Update) const { 306 const auto *From = Update.getFrom(); 307 const auto *To = Update.getTo(); 308 const auto Kind = Update.getKind(); 309 310 // Discard updates by inspecting the current state of successors of From. 311 // Since isUpdateValid() must be called *after* the Terminator of From is 312 // altered we can determine if the update is unnecessary for batch updates 313 // or invalid for a single update. 314 const bool HasEdge = llvm::is_contained(successors(From), To); 315 316 // If the IR does not match the update, 317 // 1. In batch updates, this update is unnecessary. 318 // 2. When called by insertEdge*()/deleteEdge*(), this update is invalid. 319 // Edge does not exist in IR. 320 if (Kind == DomTreeT::Insert && !HasEdge) 321 return false; 322 323 // Edge exists in IR. 324 if (Kind == DomTreeT::Delete && HasEdge) 325 return false; 326 327 return true; 328 } 329 330 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT> 331 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::eraseDelBBNode( 332 BasicBlockT *DelBB) { 333 if (DT && !IsRecalculatingDomTree) 334 if (DT->getNode(DelBB)) 335 DT->eraseNode(DelBB); 336 337 if (PDT && !IsRecalculatingPostDomTree) 338 if (PDT->getNode(DelBB)) 339 PDT->eraseNode(DelBB); 340 } 341 342 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT> 343 void GenericDomTreeUpdater<DerivedT, DomTreeT, 344 PostDomTreeT>::tryFlushDeletedBB() { 345 if (!hasPendingUpdates()) 346 derived().forceFlushDeletedBB(); 347 } 348 349 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT> 350 void GenericDomTreeUpdater<DerivedT, DomTreeT, 351 PostDomTreeT>::dropOutOfDateUpdates() { 352 if (Strategy == UpdateStrategy::Eager) 353 return; 354 355 tryFlushDeletedBB(); 356 357 // Drop all updates applied by both trees. 358 if (!DT) 359 PendDTUpdateIndex = PendUpdates.size(); 360 if (!PDT) 361 PendPDTUpdateIndex = PendUpdates.size(); 362 363 const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex); 364 const auto B = PendUpdates.begin(); 365 const auto E = PendUpdates.begin() + dropIndex; 366 assert(B <= E && "Iterator out of range."); 367 PendUpdates.erase(B, E); 368 // Calculate current index. 369 PendDTUpdateIndex -= dropIndex; 370 PendPDTUpdateIndex -= dropIndex; 371 } 372 373 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT> 374 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>:: 375 splitDTCriticalEdges(ArrayRef<CriticalEdge> Edges) { 376 // Bail out early if there is nothing to do. 377 if (!DT || Edges.empty()) 378 return; 379 380 // Remember all the basic blocks that are inserted during 381 // edge splitting. 382 // Invariant: NewBBs == all the basic blocks contained in the NewBB 383 // field of all the elements of Edges. 384 // I.e., forall elt in Edges, it exists BB in NewBBs 385 // such as BB == elt.NewBB. 386 SmallSet<BasicBlockT *, 32> NewBBs; 387 for (auto &Edge : Edges) 388 NewBBs.insert(Edge.NewBB); 389 // For each element in Edges, remember whether or not element 390 // is the new immediate domminator of its successor. The mapping is done by 391 // index, i.e., the information for the ith element of Edges is 392 // the ith element of IsNewIDom. 393 SmallBitVector IsNewIDom(Edges.size(), true); 394 395 // Collect all the dominance properties info, before invalidating 396 // the underlying DT. 397 for (const auto &[Idx, Edge] : enumerate(Edges)) { 398 // Update dominator information. 399 BasicBlockT *Succ = Edge.ToBB; 400 auto *SuccDTNode = DT->getNode(Succ); 401 402 for (BasicBlockT *PredBB : predecessors(Succ)) { 403 if (PredBB == Edge.NewBB) 404 continue; 405 // If we are in this situation: 406 // FromBB1 FromBB2 407 // + + 408 // + + + + 409 // + + + + 410 // ... Split1 Split2 ... 411 // + + 412 // + + 413 // + 414 // Succ 415 // Instead of checking the domiance property with Split2, we check it 416 // with FromBB2 since Split2 is still unknown of the underlying DT 417 // structure. 418 if (NewBBs.contains(PredBB)) { 419 assert(pred_size(PredBB) == 1 && "A basic block resulting from a " 420 "critical edge split has more " 421 "than one predecessor!"); 422 PredBB = *pred_begin(PredBB); 423 } 424 if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) { 425 IsNewIDom[Idx] = false; 426 break; 427 } 428 } 429 } 430 431 // Now, update DT with the collected dominance properties info. 432 for (const auto &[Idx, Edge] : enumerate(Edges)) { 433 // We know FromBB dominates NewBB. 434 auto *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB); 435 436 // If all the other predecessors of "Succ" are dominated by "Succ" itself 437 // then the new block is the new immediate dominator of "Succ". Otherwise, 438 // the new block doesn't dominate anything. 439 if (IsNewIDom[Idx]) 440 DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode); 441 } 442 } 443 444 // Post dominator tree is different, the new basic block in critical edge 445 // may become the new root. 446 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT> 447 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>:: 448 splitPDTCriticalEdges(ArrayRef<CriticalEdge> Edges) { 449 // Bail out early if there is nothing to do. 450 if (!PDT || Edges.empty()) 451 return; 452 453 std::vector<UpdateT> Updates; 454 for (const auto &Edge : Edges) { 455 Updates.push_back({PostDomTreeT::Insert, Edge.FromBB, Edge.NewBB}); 456 Updates.push_back({PostDomTreeT::Insert, Edge.NewBB, Edge.ToBB}); 457 if (!llvm::is_contained(successors(Edge.FromBB), Edge.ToBB)) 458 Updates.push_back({PostDomTreeT::Delete, Edge.FromBB, Edge.ToBB}); 459 } 460 PDT->applyUpdates(Updates); 461 } 462 463 } // namespace llvm 464 465 #endif // LLVM_ANALYSIS_GENERICDOMTREEUPDATERIMPL_H 466