1351278Sdim//===- DomTreeUpdater.cpp - DomTree/Post DomTree Updater --------*- C++ -*-===// 2351278Sdim// 3351278Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4351278Sdim// See https://llvm.org/LICENSE.txt for license information. 5351278Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6351278Sdim// 7351278Sdim//===----------------------------------------------------------------------===// 8351278Sdim// 9351278Sdim// This file implements the DomTreeUpdater class, which provides a uniform way 10351278Sdim// to update dominator tree related data structures. 11351278Sdim// 12351278Sdim//===----------------------------------------------------------------------===// 13351278Sdim 14351278Sdim#include "llvm/Analysis/DomTreeUpdater.h" 15351278Sdim#include "llvm/ADT/SmallSet.h" 16351278Sdim#include "llvm/Analysis/PostDominators.h" 17351278Sdim#include "llvm/IR/Dominators.h" 18351278Sdim#include "llvm/Support/GenericDomTree.h" 19351278Sdim#include <algorithm> 20351278Sdim#include <functional> 21351278Sdim#include <utility> 22351278Sdim 23351278Sdimnamespace llvm { 24351278Sdim 25351278Sdimbool DomTreeUpdater::isUpdateValid( 26351278Sdim const DominatorTree::UpdateType Update) const { 27351278Sdim const auto *From = Update.getFrom(); 28351278Sdim const auto *To = Update.getTo(); 29351278Sdim const auto Kind = Update.getKind(); 30351278Sdim 31351278Sdim // Discard updates by inspecting the current state of successors of From. 32351278Sdim // Since isUpdateValid() must be called *after* the Terminator of From is 33351278Sdim // altered we can determine if the update is unnecessary for batch updates 34351278Sdim // or invalid for a single update. 35351278Sdim const bool HasEdge = llvm::any_of( 36351278Sdim successors(From), [To](const BasicBlock *B) { return B == To; }); 37351278Sdim 38351278Sdim // If the IR does not match the update, 39351278Sdim // 1. In batch updates, this update is unnecessary. 40351278Sdim // 2. When called by insertEdge*()/deleteEdge*(), this update is invalid. 41351278Sdim // Edge does not exist in IR. 42351278Sdim if (Kind == DominatorTree::Insert && !HasEdge) 43351278Sdim return false; 44351278Sdim 45351278Sdim // Edge exists in IR. 46351278Sdim if (Kind == DominatorTree::Delete && HasEdge) 47351278Sdim return false; 48351278Sdim 49351278Sdim return true; 50351278Sdim} 51351278Sdim 52351278Sdimbool DomTreeUpdater::isSelfDominance( 53351278Sdim const DominatorTree::UpdateType Update) const { 54351278Sdim // Won't affect DomTree and PostDomTree. 55351278Sdim return Update.getFrom() == Update.getTo(); 56351278Sdim} 57351278Sdim 58351278Sdimvoid DomTreeUpdater::applyDomTreeUpdates() { 59351278Sdim // No pending DomTreeUpdates. 60351278Sdim if (Strategy != UpdateStrategy::Lazy || !DT) 61351278Sdim return; 62351278Sdim 63351278Sdim // Only apply updates not are applied by DomTree. 64351278Sdim if (hasPendingDomTreeUpdates()) { 65351278Sdim const auto I = PendUpdates.begin() + PendDTUpdateIndex; 66351278Sdim const auto E = PendUpdates.end(); 67351278Sdim assert(I < E && "Iterator range invalid; there should be DomTree updates."); 68351278Sdim DT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E)); 69351278Sdim PendDTUpdateIndex = PendUpdates.size(); 70351278Sdim } 71351278Sdim} 72351278Sdim 73351278Sdimvoid DomTreeUpdater::flush() { 74351278Sdim applyDomTreeUpdates(); 75351278Sdim applyPostDomTreeUpdates(); 76351278Sdim dropOutOfDateUpdates(); 77351278Sdim} 78351278Sdim 79351278Sdimvoid DomTreeUpdater::applyPostDomTreeUpdates() { 80351278Sdim // No pending PostDomTreeUpdates. 81351278Sdim if (Strategy != UpdateStrategy::Lazy || !PDT) 82351278Sdim return; 83351278Sdim 84351278Sdim // Only apply updates not are applied by PostDomTree. 85351278Sdim if (hasPendingPostDomTreeUpdates()) { 86351278Sdim const auto I = PendUpdates.begin() + PendPDTUpdateIndex; 87351278Sdim const auto E = PendUpdates.end(); 88351278Sdim assert(I < E && 89351278Sdim "Iterator range invalid; there should be PostDomTree updates."); 90351278Sdim PDT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E)); 91351278Sdim PendPDTUpdateIndex = PendUpdates.size(); 92351278Sdim } 93351278Sdim} 94351278Sdim 95351278Sdimvoid DomTreeUpdater::tryFlushDeletedBB() { 96351278Sdim if (!hasPendingUpdates()) 97351278Sdim forceFlushDeletedBB(); 98351278Sdim} 99351278Sdim 100351278Sdimbool DomTreeUpdater::forceFlushDeletedBB() { 101351278Sdim if (DeletedBBs.empty()) 102351278Sdim return false; 103351278Sdim 104351278Sdim for (auto *BB : DeletedBBs) { 105351278Sdim // After calling deleteBB or callbackDeleteBB under Lazy UpdateStrategy, 106351278Sdim // validateDeleteBB() removes all instructions of DelBB and adds an 107351278Sdim // UnreachableInst as its terminator. So we check whether the BasicBlock to 108351278Sdim // delete only has an UnreachableInst inside. 109351278Sdim assert(BB->getInstList().size() == 1 && 110351278Sdim isa<UnreachableInst>(BB->getTerminator()) && 111351278Sdim "DelBB has been modified while awaiting deletion."); 112351278Sdim BB->removeFromParent(); 113351278Sdim eraseDelBBNode(BB); 114351278Sdim delete BB; 115351278Sdim } 116351278Sdim DeletedBBs.clear(); 117351278Sdim Callbacks.clear(); 118351278Sdim return true; 119351278Sdim} 120351278Sdim 121351278Sdimvoid DomTreeUpdater::recalculate(Function &F) { 122351278Sdim 123351278Sdim if (Strategy == UpdateStrategy::Eager) { 124351278Sdim if (DT) 125351278Sdim DT->recalculate(F); 126351278Sdim if (PDT) 127351278Sdim PDT->recalculate(F); 128351278Sdim return; 129351278Sdim } 130351278Sdim 131351278Sdim // There is little performance gain if we pend the recalculation under 132351278Sdim // Lazy UpdateStrategy so we recalculate available trees immediately. 133351278Sdim 134351278Sdim // Prevent forceFlushDeletedBB() from erasing DomTree or PostDomTree nodes. 135351278Sdim IsRecalculatingDomTree = IsRecalculatingPostDomTree = true; 136351278Sdim 137351278Sdim // Because all trees are going to be up-to-date after recalculation, 138351278Sdim // flush awaiting deleted BasicBlocks. 139351278Sdim forceFlushDeletedBB(); 140351278Sdim if (DT) 141351278Sdim DT->recalculate(F); 142351278Sdim if (PDT) 143351278Sdim PDT->recalculate(F); 144351278Sdim 145351278Sdim // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes. 146351278Sdim IsRecalculatingDomTree = IsRecalculatingPostDomTree = false; 147351278Sdim PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size(); 148351278Sdim dropOutOfDateUpdates(); 149351278Sdim} 150351278Sdim 151351278Sdimbool DomTreeUpdater::hasPendingUpdates() const { 152351278Sdim return hasPendingDomTreeUpdates() || hasPendingPostDomTreeUpdates(); 153351278Sdim} 154351278Sdim 155351278Sdimbool DomTreeUpdater::hasPendingDomTreeUpdates() const { 156351278Sdim if (!DT) 157351278Sdim return false; 158351278Sdim return PendUpdates.size() != PendDTUpdateIndex; 159351278Sdim} 160351278Sdim 161351278Sdimbool DomTreeUpdater::hasPendingPostDomTreeUpdates() const { 162351278Sdim if (!PDT) 163351278Sdim return false; 164351278Sdim return PendUpdates.size() != PendPDTUpdateIndex; 165351278Sdim} 166351278Sdim 167351278Sdimbool DomTreeUpdater::isBBPendingDeletion(llvm::BasicBlock *DelBB) const { 168351278Sdim if (Strategy == UpdateStrategy::Eager || DeletedBBs.empty()) 169351278Sdim return false; 170351278Sdim return DeletedBBs.count(DelBB) != 0; 171351278Sdim} 172351278Sdim 173351278Sdim// The DT and PDT require the nodes related to updates 174351278Sdim// are not deleted when update functions are called. 175351278Sdim// So BasicBlock deletions must be pended when the 176351278Sdim// UpdateStrategy is Lazy. When the UpdateStrategy is 177351278Sdim// Eager, the BasicBlock will be deleted immediately. 178351278Sdimvoid DomTreeUpdater::deleteBB(BasicBlock *DelBB) { 179351278Sdim validateDeleteBB(DelBB); 180351278Sdim if (Strategy == UpdateStrategy::Lazy) { 181351278Sdim DeletedBBs.insert(DelBB); 182351278Sdim return; 183351278Sdim } 184351278Sdim 185351278Sdim DelBB->removeFromParent(); 186351278Sdim eraseDelBBNode(DelBB); 187351278Sdim delete DelBB; 188351278Sdim} 189351278Sdim 190351278Sdimvoid DomTreeUpdater::callbackDeleteBB( 191351278Sdim BasicBlock *DelBB, std::function<void(BasicBlock *)> Callback) { 192351278Sdim validateDeleteBB(DelBB); 193351278Sdim if (Strategy == UpdateStrategy::Lazy) { 194351278Sdim Callbacks.push_back(CallBackOnDeletion(DelBB, Callback)); 195351278Sdim DeletedBBs.insert(DelBB); 196351278Sdim return; 197351278Sdim } 198351278Sdim 199351278Sdim DelBB->removeFromParent(); 200351278Sdim eraseDelBBNode(DelBB); 201351278Sdim Callback(DelBB); 202351278Sdim delete DelBB; 203351278Sdim} 204351278Sdim 205351278Sdimvoid DomTreeUpdater::eraseDelBBNode(BasicBlock *DelBB) { 206351278Sdim if (DT && !IsRecalculatingDomTree) 207351278Sdim if (DT->getNode(DelBB)) 208351278Sdim DT->eraseNode(DelBB); 209351278Sdim 210351278Sdim if (PDT && !IsRecalculatingPostDomTree) 211351278Sdim if (PDT->getNode(DelBB)) 212351278Sdim PDT->eraseNode(DelBB); 213351278Sdim} 214351278Sdim 215351278Sdimvoid DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) { 216351278Sdim assert(DelBB && "Invalid push_back of nullptr DelBB."); 217351278Sdim assert(pred_empty(DelBB) && "DelBB has one or more predecessors."); 218351278Sdim // DelBB is unreachable and all its instructions are dead. 219351278Sdim while (!DelBB->empty()) { 220351278Sdim Instruction &I = DelBB->back(); 221351278Sdim // Replace used instructions with an arbitrary value (undef). 222351278Sdim if (!I.use_empty()) 223351278Sdim I.replaceAllUsesWith(llvm::UndefValue::get(I.getType())); 224351278Sdim DelBB->getInstList().pop_back(); 225351278Sdim } 226351278Sdim // Make sure DelBB has a valid terminator instruction. As long as DelBB is a 227351278Sdim // Child of Function F it must contain valid IR. 228351278Sdim new UnreachableInst(DelBB->getContext(), DelBB); 229351278Sdim} 230351278Sdim 231351278Sdimvoid DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates) { 232351278Sdim if (!DT && !PDT) 233351278Sdim return; 234351278Sdim 235351278Sdim if (Strategy == UpdateStrategy::Lazy) { 236360784Sdim for (const auto &U : Updates) 237351278Sdim if (!isSelfDominance(U)) 238351278Sdim PendUpdates.push_back(U); 239351278Sdim 240351278Sdim return; 241351278Sdim } 242351278Sdim 243351278Sdim if (DT) 244351278Sdim DT->applyUpdates(Updates); 245351278Sdim if (PDT) 246351278Sdim PDT->applyUpdates(Updates); 247351278Sdim} 248351278Sdim 249351278Sdimvoid DomTreeUpdater::applyUpdatesPermissive( 250351278Sdim ArrayRef<DominatorTree::UpdateType> Updates) { 251351278Sdim if (!DT && !PDT) 252351278Sdim return; 253351278Sdim 254351278Sdim SmallSet<std::pair<BasicBlock *, BasicBlock *>, 8> Seen; 255351278Sdim SmallVector<DominatorTree::UpdateType, 8> DeduplicatedUpdates; 256360784Sdim for (const auto &U : Updates) { 257351278Sdim auto Edge = std::make_pair(U.getFrom(), U.getTo()); 258351278Sdim // Because it is illegal to submit updates that have already been applied 259351278Sdim // and updates to an edge need to be strictly ordered, 260351278Sdim // it is safe to infer the existence of an edge from the first update 261351278Sdim // to this edge. 262351278Sdim // If the first update to an edge is "Delete", it means that the edge 263351278Sdim // existed before. If the first update to an edge is "Insert", it means 264351278Sdim // that the edge didn't exist before. 265351278Sdim // 266351278Sdim // For example, if the user submits {{Delete, A, B}, {Insert, A, B}}, 267351278Sdim // because 268351278Sdim // 1. it is illegal to submit updates that have already been applied, 269351278Sdim // i.e., user cannot delete an nonexistent edge, 270351278Sdim // 2. updates to an edge need to be strictly ordered, 271351278Sdim // So, initially edge A -> B existed. 272351278Sdim // We can then safely ignore future updates to this edge and directly 273351278Sdim // inspect the current CFG: 274351278Sdim // a. If the edge still exists, because the user cannot insert an existent 275351278Sdim // edge, so both {Delete, A, B}, {Insert, A, B} actually happened and 276351278Sdim // resulted in a no-op. DTU won't submit any update in this case. 277351278Sdim // b. If the edge doesn't exist, we can then infer that {Delete, A, B} 278351278Sdim // actually happened but {Insert, A, B} was an invalid update which never 279351278Sdim // happened. DTU will submit {Delete, A, B} in this case. 280351278Sdim if (!isSelfDominance(U) && Seen.count(Edge) == 0) { 281351278Sdim Seen.insert(Edge); 282351278Sdim // If the update doesn't appear in the CFG, it means that 283351278Sdim // either the change isn't made or relevant operations 284351278Sdim // result in a no-op. 285351278Sdim if (isUpdateValid(U)) { 286351278Sdim if (isLazy()) 287351278Sdim PendUpdates.push_back(U); 288351278Sdim else 289351278Sdim DeduplicatedUpdates.push_back(U); 290351278Sdim } 291351278Sdim } 292351278Sdim } 293351278Sdim 294351278Sdim if (Strategy == UpdateStrategy::Lazy) 295351278Sdim return; 296351278Sdim 297351278Sdim if (DT) 298351278Sdim DT->applyUpdates(DeduplicatedUpdates); 299351278Sdim if (PDT) 300351278Sdim PDT->applyUpdates(DeduplicatedUpdates); 301351278Sdim} 302351278Sdim 303351278SdimDominatorTree &DomTreeUpdater::getDomTree() { 304351278Sdim assert(DT && "Invalid acquisition of a null DomTree"); 305351278Sdim applyDomTreeUpdates(); 306351278Sdim dropOutOfDateUpdates(); 307351278Sdim return *DT; 308351278Sdim} 309351278Sdim 310351278SdimPostDominatorTree &DomTreeUpdater::getPostDomTree() { 311351278Sdim assert(PDT && "Invalid acquisition of a null PostDomTree"); 312351278Sdim applyPostDomTreeUpdates(); 313351278Sdim dropOutOfDateUpdates(); 314351278Sdim return *PDT; 315351278Sdim} 316351278Sdim 317351278Sdimvoid DomTreeUpdater::insertEdge(BasicBlock *From, BasicBlock *To) { 318351278Sdim 319351278Sdim#ifndef NDEBUG 320351278Sdim assert(isUpdateValid({DominatorTree::Insert, From, To}) && 321351278Sdim "Inserted edge does not appear in the CFG"); 322351278Sdim#endif 323351278Sdim 324351278Sdim if (!DT && !PDT) 325351278Sdim return; 326351278Sdim 327351278Sdim // Won't affect DomTree and PostDomTree; discard update. 328351278Sdim if (From == To) 329351278Sdim return; 330351278Sdim 331351278Sdim if (Strategy == UpdateStrategy::Eager) { 332351278Sdim if (DT) 333351278Sdim DT->insertEdge(From, To); 334351278Sdim if (PDT) 335351278Sdim PDT->insertEdge(From, To); 336351278Sdim return; 337351278Sdim } 338351278Sdim 339351278Sdim PendUpdates.push_back({DominatorTree::Insert, From, To}); 340351278Sdim} 341351278Sdim 342351278Sdimvoid DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) { 343351278Sdim if (From == To) 344351278Sdim return; 345351278Sdim 346351278Sdim if (!DT && !PDT) 347351278Sdim return; 348351278Sdim 349351278Sdim if (!isUpdateValid({DominatorTree::Insert, From, To})) 350351278Sdim return; 351351278Sdim 352351278Sdim if (Strategy == UpdateStrategy::Eager) { 353351278Sdim if (DT) 354351278Sdim DT->insertEdge(From, To); 355351278Sdim if (PDT) 356351278Sdim PDT->insertEdge(From, To); 357351278Sdim return; 358351278Sdim } 359351278Sdim 360351278Sdim PendUpdates.push_back({DominatorTree::Insert, From, To}); 361351278Sdim} 362351278Sdim 363351278Sdimvoid DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) { 364351278Sdim 365351278Sdim#ifndef NDEBUG 366351278Sdim assert(isUpdateValid({DominatorTree::Delete, From, To}) && 367351278Sdim "Deleted edge still exists in the CFG!"); 368351278Sdim#endif 369351278Sdim 370351278Sdim if (!DT && !PDT) 371351278Sdim return; 372351278Sdim 373351278Sdim // Won't affect DomTree and PostDomTree; discard update. 374351278Sdim if (From == To) 375351278Sdim return; 376351278Sdim 377351278Sdim if (Strategy == UpdateStrategy::Eager) { 378351278Sdim if (DT) 379351278Sdim DT->deleteEdge(From, To); 380351278Sdim if (PDT) 381351278Sdim PDT->deleteEdge(From, To); 382351278Sdim return; 383351278Sdim } 384351278Sdim 385351278Sdim PendUpdates.push_back({DominatorTree::Delete, From, To}); 386351278Sdim} 387351278Sdim 388351278Sdimvoid DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) { 389351278Sdim if (From == To) 390351278Sdim return; 391351278Sdim 392351278Sdim if (!DT && !PDT) 393351278Sdim return; 394351278Sdim 395351278Sdim if (!isUpdateValid({DominatorTree::Delete, From, To})) 396351278Sdim return; 397351278Sdim 398351278Sdim if (Strategy == UpdateStrategy::Eager) { 399351278Sdim if (DT) 400351278Sdim DT->deleteEdge(From, To); 401351278Sdim if (PDT) 402351278Sdim PDT->deleteEdge(From, To); 403351278Sdim return; 404351278Sdim } 405351278Sdim 406351278Sdim PendUpdates.push_back({DominatorTree::Delete, From, To}); 407351278Sdim} 408351278Sdim 409351278Sdimvoid DomTreeUpdater::dropOutOfDateUpdates() { 410351278Sdim if (Strategy == DomTreeUpdater::UpdateStrategy::Eager) 411351278Sdim return; 412351278Sdim 413351278Sdim tryFlushDeletedBB(); 414351278Sdim 415351278Sdim // Drop all updates applied by both trees. 416351278Sdim if (!DT) 417351278Sdim PendDTUpdateIndex = PendUpdates.size(); 418351278Sdim if (!PDT) 419351278Sdim PendPDTUpdateIndex = PendUpdates.size(); 420351278Sdim 421351278Sdim const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex); 422351278Sdim const auto B = PendUpdates.begin(); 423351278Sdim const auto E = PendUpdates.begin() + dropIndex; 424351278Sdim assert(B <= E && "Iterator out of range."); 425351278Sdim PendUpdates.erase(B, E); 426351278Sdim // Calculate current index. 427351278Sdim PendDTUpdateIndex -= dropIndex; 428351278Sdim PendPDTUpdateIndex -= dropIndex; 429351278Sdim} 430351278Sdim 431351278Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 432351278SdimLLVM_DUMP_METHOD void DomTreeUpdater::dump() const { 433351278Sdim raw_ostream &OS = llvm::dbgs(); 434351278Sdim 435351278Sdim OS << "Available Trees: "; 436351278Sdim if (DT || PDT) { 437351278Sdim if (DT) 438351278Sdim OS << "DomTree "; 439351278Sdim if (PDT) 440351278Sdim OS << "PostDomTree "; 441351278Sdim OS << "\n"; 442351278Sdim } else 443351278Sdim OS << "None\n"; 444351278Sdim 445351278Sdim OS << "UpdateStrategy: "; 446351278Sdim if (Strategy == UpdateStrategy::Eager) { 447351278Sdim OS << "Eager\n"; 448351278Sdim return; 449351278Sdim } else 450351278Sdim OS << "Lazy\n"; 451351278Sdim int Index = 0; 452351278Sdim 453351278Sdim auto printUpdates = 454351278Sdim [&](ArrayRef<DominatorTree::UpdateType>::const_iterator begin, 455351278Sdim ArrayRef<DominatorTree::UpdateType>::const_iterator end) { 456351278Sdim if (begin == end) 457351278Sdim OS << " None\n"; 458351278Sdim Index = 0; 459351278Sdim for (auto It = begin, ItEnd = end; It != ItEnd; ++It) { 460351278Sdim auto U = *It; 461351278Sdim OS << " " << Index << " : "; 462351278Sdim ++Index; 463351278Sdim if (U.getKind() == DominatorTree::Insert) 464351278Sdim OS << "Insert, "; 465351278Sdim else 466351278Sdim OS << "Delete, "; 467351278Sdim BasicBlock *From = U.getFrom(); 468351278Sdim if (From) { 469351278Sdim auto S = From->getName(); 470351278Sdim if (!From->hasName()) 471351278Sdim S = "(no name)"; 472351278Sdim OS << S << "(" << From << "), "; 473351278Sdim } else { 474351278Sdim OS << "(badref), "; 475351278Sdim } 476351278Sdim BasicBlock *To = U.getTo(); 477351278Sdim if (To) { 478351278Sdim auto S = To->getName(); 479351278Sdim if (!To->hasName()) 480351278Sdim S = "(no_name)"; 481351278Sdim OS << S << "(" << To << ")\n"; 482351278Sdim } else { 483351278Sdim OS << "(badref)\n"; 484351278Sdim } 485351278Sdim } 486351278Sdim }; 487351278Sdim 488351278Sdim if (DT) { 489351278Sdim const auto I = PendUpdates.begin() + PendDTUpdateIndex; 490351278Sdim assert(PendUpdates.begin() <= I && I <= PendUpdates.end() && 491351278Sdim "Iterator out of range."); 492351278Sdim OS << "Applied but not cleared DomTreeUpdates:\n"; 493351278Sdim printUpdates(PendUpdates.begin(), I); 494351278Sdim OS << "Pending DomTreeUpdates:\n"; 495351278Sdim printUpdates(I, PendUpdates.end()); 496351278Sdim } 497351278Sdim 498351278Sdim if (PDT) { 499351278Sdim const auto I = PendUpdates.begin() + PendPDTUpdateIndex; 500351278Sdim assert(PendUpdates.begin() <= I && I <= PendUpdates.end() && 501351278Sdim "Iterator out of range."); 502351278Sdim OS << "Applied but not cleared PostDomTreeUpdates:\n"; 503351278Sdim printUpdates(PendUpdates.begin(), I); 504351278Sdim OS << "Pending PostDomTreeUpdates:\n"; 505351278Sdim printUpdates(I, PendUpdates.end()); 506351278Sdim } 507351278Sdim 508351278Sdim OS << "Pending DeletedBBs:\n"; 509351278Sdim Index = 0; 510351278Sdim for (auto BB : DeletedBBs) { 511351278Sdim OS << " " << Index << " : "; 512351278Sdim ++Index; 513351278Sdim if (BB->hasName()) 514351278Sdim OS << BB->getName() << "("; 515351278Sdim else 516351278Sdim OS << "(no_name)("; 517351278Sdim OS << BB << ")\n"; 518351278Sdim } 519351278Sdim 520351278Sdim OS << "Pending Callbacks:\n"; 521351278Sdim Index = 0; 522351278Sdim for (auto BB : Callbacks) { 523351278Sdim OS << " " << Index << " : "; 524351278Sdim ++Index; 525351278Sdim if (BB->hasName()) 526351278Sdim OS << BB->getName() << "("; 527351278Sdim else 528351278Sdim OS << "(no_name)("; 529351278Sdim OS << BB << ")\n"; 530351278Sdim } 531351278Sdim} 532351278Sdim#endif 533351278Sdim} // namespace llvm 534