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