lib/Analysis/DomTreeUpdater.cpp

   1 //===- DomTreeUpdater.cpp - DomTree/Post DomTree Updater --------*- 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 DomTreeUpdater class, which provides a uniform way
  10 // to update dominator tree related data structures.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Analysis/DomTreeUpdater.h"
  15 #include "llvm/Analysis/PostDominators.h"
  16 #include "llvm/IR/Dominators.h"
  17 #include "llvm/Support/GenericDomTree.h"
  18 #include <algorithm>
  19 #include <functional>
  20
  21 namespace llvm {
  22
  23 bool DomTreeUpdater::isUpdateValid(
  24     const DominatorTree::UpdateType Update) const {
  25   const auto *From = Update.getFrom();
  26   const auto *To = Update.getTo();
  27   const auto Kind = Update.getKind();
  28
  29   // Discard updates by inspecting the current state of successors of From.
  30   // Since isUpdateValid() must be called *after* the Terminator of From is
  31   // altered we can determine if the update is unnecessary for batch updates
  32   // or invalid for a single update.
  33   const bool HasEdge = llvm::any_of(
  34       successors(From), [To](const BasicBlock *B) { return B == To; });
  35
  36   // If the IR does not match the update,
  37   // 1. In batch updates, this update is unnecessary.
  38   // 2. When called by insertEdge*()/deleteEdge*(), this update is invalid.
  39   // Edge does not exist in IR.
  40   if (Kind == DominatorTree::Insert && !HasEdge)
  41     return false;
  42
  43   // Edge exists in IR.
  44   if (Kind == DominatorTree::Delete && HasEdge)
  45     return false;
  46
  47   return true;
  48 }
  49
  50 bool DomTreeUpdater::isSelfDominance(
  51     const DominatorTree::UpdateType Update) const {
  52   // Won't affect DomTree and PostDomTree.
  53   return Update.getFrom() == Update.getTo();
  54 }
  55
  56 bool DomTreeUpdater::applyLazyUpdate(DominatorTree::UpdateKind Kind,
  57                                      BasicBlock *From, BasicBlock *To) {
  58   assert((DT || PDT) &&
  59          "Call applyLazyUpdate() when both DT and PDT are nullptrs.");
  60   assert(Strategy == DomTreeUpdater::UpdateStrategy::Lazy &&
  61          "Call applyLazyUpdate() with Eager strategy error");
  62   // Analyze pending updates to determine if the update is unnecessary.
  63   const DominatorTree::UpdateType Update = {Kind, From, To};
  64   const DominatorTree::UpdateType Invert = {Kind != DominatorTree::Insert
  65                                                 ? DominatorTree::Insert
  66                                                 : DominatorTree::Delete,
  67                                             From, To};
  68   // Only check duplicates in updates that are not applied by both trees.
  69   auto I =
  70       PendUpdates.begin() + std::max(PendDTUpdateIndex, PendPDTUpdateIndex);
  71   const auto E = PendUpdates.end();
  72
  73   assert(I <= E && "Iterator out of range.");
  74
  75   for (; I != E; ++I) {
  76     if (Update == *I)
  77       return false; // Discard duplicate updates.
  78
  79     if (Invert == *I) {
  80       // Update and Invert are both valid (equivalent to a no-op). Remove
  81       // Invert from PendUpdates and discard the Update.
  82       PendUpdates.erase(I);
  83       return false;
  84     }
  85   }
  86
  87   PendUpdates.push_back(Update); // Save the valid update.
  88   return true;
  89 }
  90
  91 void DomTreeUpdater::applyDomTreeUpdates() {
  92   // No pending DomTreeUpdates.
  93   if (Strategy != UpdateStrategy::Lazy || !DT)
  94     return;
  95
  96   // Only apply updates not are applied by DomTree.
  97   if (hasPendingDomTreeUpdates()) {
  98     const auto I = PendUpdates.begin() + PendDTUpdateIndex;
  99     const auto E = PendUpdates.end();
 100     assert(I < E && "Iterator range invalid; there should be DomTree updates.");
 101     DT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
 102     PendDTUpdateIndex = PendUpdates.size();
 103   }
 104 }
 105
 106 void DomTreeUpdater::flush() {
 107   applyDomTreeUpdates();
 108   applyPostDomTreeUpdates();
 109   dropOutOfDateUpdates();
 110 }
 111
 112 void DomTreeUpdater::applyPostDomTreeUpdates() {
 113   // No pending PostDomTreeUpdates.
 114   if (Strategy != UpdateStrategy::Lazy || !PDT)
 115     return;
 116
 117   // Only apply updates not are applied by PostDomTree.
 118   if (hasPendingPostDomTreeUpdates()) {
 119     const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
 120     const auto E = PendUpdates.end();
 121     assert(I < E &&
 122            "Iterator range invalid; there should be PostDomTree updates.");
 123     PDT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
 124     PendPDTUpdateIndex = PendUpdates.size();
 125   }
 126 }
 127
 128 void DomTreeUpdater::tryFlushDeletedBB() {
 129   if (!hasPendingUpdates())
 130     forceFlushDeletedBB();
 131 }
 132
 133 bool DomTreeUpdater::forceFlushDeletedBB() {
 134   if (DeletedBBs.empty())
 135     return false;
 136
 137   for (auto *BB : DeletedBBs) {
 138     // After calling deleteBB or callbackDeleteBB under Lazy UpdateStrategy,
 139     // validateDeleteBB() removes all instructions of DelBB and adds an
 140     // UnreachableInst as its terminator. So we check whether the BasicBlock to
 141     // delete only has an UnreachableInst inside.
 142     assert(BB->getInstList().size() == 1 &&
 143            isa<UnreachableInst>(BB->getTerminator()) &&
 144            "DelBB has been modified while awaiting deletion.");
 145     BB->removeFromParent();
 146     eraseDelBBNode(BB);
 147     delete BB;
 148   }
 149   DeletedBBs.clear();
 150   Callbacks.clear();
 151   return true;
 152 }
 153
 154 void DomTreeUpdater::recalculate(Function &F) {
 155
 156   if (Strategy == UpdateStrategy::Eager) {
 157     if (DT)
 158       DT->recalculate(F);
 159     if (PDT)
 160       PDT->recalculate(F);
 161     return;
 162   }
 163
 164   // There is little performance gain if we pend the recalculation under
 165   // Lazy UpdateStrategy so we recalculate available trees immediately.
 166
 167   // Prevent forceFlushDeletedBB() from erasing DomTree or PostDomTree nodes.
 168   IsRecalculatingDomTree = IsRecalculatingPostDomTree = true;
 169
 170   // Because all trees are going to be up-to-date after recalculation,
 171   // flush awaiting deleted BasicBlocks.
 172   forceFlushDeletedBB();
 173   if (DT)
 174     DT->recalculate(F);
 175   if (PDT)
 176     PDT->recalculate(F);
 177
 178   // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
 179   IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
 180   PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
 181   dropOutOfDateUpdates();
 182 }
 183
 184 bool DomTreeUpdater::hasPendingUpdates() const {
 185   return hasPendingDomTreeUpdates() || hasPendingPostDomTreeUpdates();
 186 }
 187
 188 bool DomTreeUpdater::hasPendingDomTreeUpdates() const {
 189   if (!DT)
 190     return false;
 191   return PendUpdates.size() != PendDTUpdateIndex;
 192 }
 193
 194 bool DomTreeUpdater::hasPendingPostDomTreeUpdates() const {
 195   if (!PDT)
 196     return false;
 197   return PendUpdates.size() != PendPDTUpdateIndex;
 198 }
 199
 200 bool DomTreeUpdater::isBBPendingDeletion(llvm::BasicBlock *DelBB) const {
 201   if (Strategy == UpdateStrategy::Eager || DeletedBBs.empty())
 202     return false;
 203   return DeletedBBs.count(DelBB) != 0;
 204 }
 205
 206 // The DT and PDT require the nodes related to updates
 207 // are not deleted when update functions are called.
 208 // So BasicBlock deletions must be pended when the
 209 // UpdateStrategy is Lazy. When the UpdateStrategy is
 210 // Eager, the BasicBlock will be deleted immediately.
 211 void DomTreeUpdater::deleteBB(BasicBlock *DelBB) {
 212   validateDeleteBB(DelBB);
 213   if (Strategy == UpdateStrategy::Lazy) {
 214     DeletedBBs.insert(DelBB);
 215     return;
 216   }
 217
 218   DelBB->removeFromParent();
 219   eraseDelBBNode(DelBB);
 220   delete DelBB;
 221 }
 222
 223 void DomTreeUpdater::callbackDeleteBB(
 224     BasicBlock *DelBB, std::function<void(BasicBlock *)> Callback) {
 225   validateDeleteBB(DelBB);
 226   if (Strategy == UpdateStrategy::Lazy) {
 227     Callbacks.push_back(CallBackOnDeletion(DelBB, Callback));
 228     DeletedBBs.insert(DelBB);
 229     return;
 230   }
 231
 232   DelBB->removeFromParent();
 233   eraseDelBBNode(DelBB);
 234   Callback(DelBB);
 235   delete DelBB;
 236 }
 237
 238 void DomTreeUpdater::eraseDelBBNode(BasicBlock *DelBB) {
 239   if (DT && !IsRecalculatingDomTree)
 240     if (DT->getNode(DelBB))
 241       DT->eraseNode(DelBB);
 242
 243   if (PDT && !IsRecalculatingPostDomTree)
 244     if (PDT->getNode(DelBB))
 245       PDT->eraseNode(DelBB);
 246 }
 247
 248 void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) {
 249   assert(DelBB && "Invalid push_back of nullptr DelBB.");
 250   assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
 251   // DelBB is unreachable and all its instructions are dead.
 252   while (!DelBB->empty()) {
 253     Instruction &I = DelBB->back();
 254     // Replace used instructions with an arbitrary value (undef).
 255     if (!I.use_empty())
 256       I.replaceAllUsesWith(llvm::UndefValue::get(I.getType()));
 257     DelBB->getInstList().pop_back();
 258   }
 259   // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
 260   // Child of Function F it must contain valid IR.
 261   new UnreachableInst(DelBB->getContext(), DelBB);
 262 }
 263
 264 void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
 265                                   bool ForceRemoveDuplicates) {
 266   if (!DT && !PDT)
 267     return;
 268
 269   if (Strategy == UpdateStrategy::Lazy || ForceRemoveDuplicates) {
 270     SmallVector<DominatorTree::UpdateType, 8> Seen;
 271     for (const auto U : Updates)
 272       // For Lazy UpdateStrategy, avoid duplicates to applyLazyUpdate() to save
 273       // on analysis.
 274       if (llvm::none_of(
 275               Seen,
 276               [U](const DominatorTree::UpdateType S) { return S == U; }) &&
 277           isUpdateValid(U) && !isSelfDominance(U)) {
 278         Seen.push_back(U);
 279         if (Strategy == UpdateStrategy::Lazy)
 280           applyLazyUpdate(U.getKind(), U.getFrom(), U.getTo());
 281       }
 282     if (Strategy == UpdateStrategy::Lazy)
 283       return;
 284
 285     if (DT)
 286       DT->applyUpdates(Seen);
 287     if (PDT)
 288       PDT->applyUpdates(Seen);
 289     return;
 290   }
 291
 292   if (DT)
 293     DT->applyUpdates(Updates);
 294   if (PDT)
 295     PDT->applyUpdates(Updates);
 296 }
 297
 298 DominatorTree &DomTreeUpdater::getDomTree() {
 299   assert(DT && "Invalid acquisition of a null DomTree");
 300   applyDomTreeUpdates();
 301   dropOutOfDateUpdates();
 302   return *DT;
 303 }
 304
 305 PostDominatorTree &DomTreeUpdater::getPostDomTree() {
 306   assert(PDT && "Invalid acquisition of a null PostDomTree");
 307   applyPostDomTreeUpdates();
 308   dropOutOfDateUpdates();
 309   return *PDT;
 310 }
 311
 312 void DomTreeUpdater::insertEdge(BasicBlock *From, BasicBlock *To) {
 313
 314 #ifndef NDEBUG
 315   assert(isUpdateValid({DominatorTree::Insert, From, To}) &&
 316          "Inserted edge does not appear in the CFG");
 317 #endif
 318
 319   if (!DT && !PDT)
 320     return;
 321
 322   // Won't affect DomTree and PostDomTree; discard update.
 323   if (From == To)
 324     return;
 325
 326   if (Strategy == UpdateStrategy::Eager) {
 327     if (DT)
 328       DT->insertEdge(From, To);
 329     if (PDT)
 330       PDT->insertEdge(From, To);
 331     return;
 332   }
 333
 334   applyLazyUpdate(DominatorTree::Insert, From, To);
 335 }
 336
 337 void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
 338   if (From == To)
 339     return;
 340
 341   if (!DT && !PDT)
 342     return;
 343
 344   if (!isUpdateValid({DominatorTree::Insert, From, To}))
 345     return;
 346
 347   if (Strategy == UpdateStrategy::Eager) {
 348     if (DT)
 349       DT->insertEdge(From, To);
 350     if (PDT)
 351       PDT->insertEdge(From, To);
 352     return;
 353   }
 354
 355   applyLazyUpdate(DominatorTree::Insert, From, To);
 356 }
 357
 358 void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) {
 359
 360 #ifndef NDEBUG
 361   assert(isUpdateValid({DominatorTree::Delete, From, To}) &&
 362          "Deleted edge still exists in the CFG!");
 363 #endif
 364
 365   if (!DT && !PDT)
 366     return;
 367
 368   // Won't affect DomTree and PostDomTree; discard update.
 369   if (From == To)
 370     return;
 371
 372   if (Strategy == UpdateStrategy::Eager) {
 373     if (DT)
 374       DT->deleteEdge(From, To);
 375     if (PDT)
 376       PDT->deleteEdge(From, To);
 377     return;
 378   }
 379
 380   applyLazyUpdate(DominatorTree::Delete, From, To);
 381 }
 382
 383 void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
 384   if (From == To)
 385     return;
 386
 387   if (!DT && !PDT)
 388     return;
 389
 390   if (!isUpdateValid({DominatorTree::Delete, From, To}))
 391     return;
 392
 393   if (Strategy == UpdateStrategy::Eager) {
 394     if (DT)
 395       DT->deleteEdge(From, To);
 396     if (PDT)
 397       PDT->deleteEdge(From, To);
 398     return;
 399   }
 400
 401   applyLazyUpdate(DominatorTree::Delete, From, To);
 402 }
 403
 404 void DomTreeUpdater::dropOutOfDateUpdates() {
 405   if (Strategy == DomTreeUpdater::UpdateStrategy::Eager)
 406     return;
 407
 408   tryFlushDeletedBB();
 409
 410   // Drop all updates applied by both trees.
 411   if (!DT)
 412     PendDTUpdateIndex = PendUpdates.size();
 413   if (!PDT)
 414     PendPDTUpdateIndex = PendUpdates.size();
 415
 416   const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
 417   const auto B = PendUpdates.begin();
 418   const auto E = PendUpdates.begin() + dropIndex;
 419   assert(B <= E && "Iterator out of range.");
 420   PendUpdates.erase(B, E);
 421   // Calculate current index.
 422   PendDTUpdateIndex -= dropIndex;
 423   PendPDTUpdateIndex -= dropIndex;
 424 }
 425
 426 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 427 LLVM_DUMP_METHOD void DomTreeUpdater::dump() const {
 428   raw_ostream &OS = llvm::dbgs();
 429
 430   OS << "Available Trees: ";
 431   if (DT || PDT) {
 432     if (DT)
 433       OS << "DomTree ";
 434     if (PDT)
 435       OS << "PostDomTree ";
 436     OS << "\n";
 437   } else
 438     OS << "None\n";
 439
 440   OS << "UpdateStrategy: ";
 441   if (Strategy == UpdateStrategy::Eager) {
 442     OS << "Eager\n";
 443     return;
 444   } else
 445     OS << "Lazy\n";
 446   int Index = 0;
 447
 448   auto printUpdates =
 449       [&](ArrayRef<DominatorTree::UpdateType>::const_iterator begin,
 450           ArrayRef<DominatorTree::UpdateType>::const_iterator end) {
 451         if (begin == end)
 452           OS << "  None\n";
 453         Index = 0;
 454         for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {
 455           auto U = *It;
 456           OS << "  " << Index << " : ";
 457           ++Index;
 458           if (U.getKind() == DominatorTree::Insert)
 459             OS << "Insert, ";
 460           else
 461             OS << "Delete, ";
 462           BasicBlock *From = U.getFrom();
 463           if (From) {
 464             auto S = From->getName();
 465             if (!From->hasName())
 466               S = "(no name)";
 467             OS << S << "(" << From << "), ";
 468           } else {
 469             OS << "(badref), ";
 470           }
 471           BasicBlock *To = U.getTo();
 472           if (To) {
 473             auto S = To->getName();
 474             if (!To->hasName())
 475               S = "(no_name)";
 476             OS << S << "(" << To << ")\n";
 477           } else {
 478             OS << "(badref)\n";
 479           }
 480         }
 481       };
 482
 483   if (DT) {
 484     const auto I = PendUpdates.begin() + PendDTUpdateIndex;
 485     assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
 486            "Iterator out of range.");
 487     OS << "Applied but not cleared DomTreeUpdates:\n";
 488     printUpdates(PendUpdates.begin(), I);
 489     OS << "Pending DomTreeUpdates:\n";
 490     printUpdates(I, PendUpdates.end());
 491   }
 492
 493   if (PDT) {
 494     const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
 495     assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
 496            "Iterator out of range.");
 497     OS << "Applied but not cleared PostDomTreeUpdates:\n";
 498     printUpdates(PendUpdates.begin(), I);
 499     OS << "Pending PostDomTreeUpdates:\n";
 500     printUpdates(I, PendUpdates.end());
 501   }
 502
 503   OS << "Pending DeletedBBs:\n";
 504   Index = 0;
 505   for (auto BB : DeletedBBs) {
 506     OS << "  " << Index << " : ";
 507     ++Index;
 508     if (BB->hasName())
 509       OS << BB->getName() << "(";
 510     else
 511       OS << "(no_name)(";
 512     OS << BB << ")\n";
 513   }
 514
 515   OS << "Pending Callbacks:\n";
 516   Index = 0;
 517   for (auto BB : Callbacks) {
 518     OS << "  " << Index << " : ";
 519     ++Index;
 520     if (BB->hasName())
 521       OS << BB->getName() << "(";
 522     else
 523       OS << "(no_name)(";
 524     OS << BB << ")\n";
 525   }
 526 }
 527 #endif
 528 } // namespace llvm