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/Dominators.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::any_of(
  36       successors(From), [To](const BasicBlock *B) { return B == To; });
  37
  38   // If the IR does not match the update,
  39   // 1. In batch updates, this update is unnecessary.
  40   // 2. When called by insertEdge*()/deleteEdge*(), this update is invalid.
  41   // Edge does not exist in IR.
  42   if (Kind == DominatorTree::Insert && !HasEdge)
  43     return false;
  44
  45   // Edge exists in IR.
  46   if (Kind == DominatorTree::Delete && HasEdge)
  47     return false;
  48
  49   return true;
  50 }
  51
  52 bool DomTreeUpdater::isSelfDominance(
  53     const DominatorTree::UpdateType Update) const {
  54   // Won't affect DomTree and PostDomTree.
  55   return Update.getFrom() == Update.getTo();
  56 }
  57
  58 void DomTreeUpdater::applyDomTreeUpdates() {
  59   // No pending DomTreeUpdates.
  60   if (Strategy != UpdateStrategy::Lazy || !DT)
  61     return;
  62
  63   // Only apply updates not are applied by DomTree.
  64   if (hasPendingDomTreeUpdates()) {
  65     const auto I = PendUpdates.begin() + PendDTUpdateIndex;
  66     const auto E = PendUpdates.end();
  67     assert(I < E && "Iterator range invalid; there should be DomTree updates.");
  68     DT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
  69     PendDTUpdateIndex = PendUpdates.size();
  70   }
  71 }
  72
  73 void DomTreeUpdater::flush() {
  74   applyDomTreeUpdates();
  75   applyPostDomTreeUpdates();
  76   dropOutOfDateUpdates();
  77 }
  78
  79 void DomTreeUpdater::applyPostDomTreeUpdates() {
  80   // No pending PostDomTreeUpdates.
  81   if (Strategy != UpdateStrategy::Lazy || !PDT)
  82     return;
  83
  84   // Only apply updates not are applied by PostDomTree.
  85   if (hasPendingPostDomTreeUpdates()) {
  86     const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
  87     const auto E = PendUpdates.end();
  88     assert(I < E &&
  89            "Iterator range invalid; there should be PostDomTree updates.");
  90     PDT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
  91     PendPDTUpdateIndex = PendUpdates.size();
  92   }
  93 }
  94
  95 void DomTreeUpdater::tryFlushDeletedBB() {
  96   if (!hasPendingUpdates())
  97     forceFlushDeletedBB();
  98 }
  99
 100 bool DomTreeUpdater::forceFlushDeletedBB() {
 101   if (DeletedBBs.empty())
 102     return false;
 103
 104   for (auto *BB : DeletedBBs) {
 105     // After calling deleteBB or callbackDeleteBB under Lazy UpdateStrategy,
 106     // validateDeleteBB() removes all instructions of DelBB and adds an
 107     // UnreachableInst as its terminator. So we check whether the BasicBlock to
 108     // delete only has an UnreachableInst inside.
 109     assert(BB->getInstList().size() == 1 &&
 110            isa<UnreachableInst>(BB->getTerminator()) &&
 111            "DelBB has been modified while awaiting deletion.");
 112     BB->removeFromParent();
 113     eraseDelBBNode(BB);
 114     delete BB;
 115   }
 116   DeletedBBs.clear();
 117   Callbacks.clear();
 118   return true;
 119 }
 120
 121 void DomTreeUpdater::recalculate(Function &F) {
 122
 123   if (Strategy == UpdateStrategy::Eager) {
 124     if (DT)
 125       DT->recalculate(F);
 126     if (PDT)
 127       PDT->recalculate(F);
 128     return;
 129   }
 130
 131   // There is little performance gain if we pend the recalculation under
 132   // Lazy UpdateStrategy so we recalculate available trees immediately.
 133
 134   // Prevent forceFlushDeletedBB() from erasing DomTree or PostDomTree nodes.
 135   IsRecalculatingDomTree = IsRecalculatingPostDomTree = true;
 136
 137   // Because all trees are going to be up-to-date after recalculation,
 138   // flush awaiting deleted BasicBlocks.
 139   forceFlushDeletedBB();
 140   if (DT)
 141     DT->recalculate(F);
 142   if (PDT)
 143     PDT->recalculate(F);
 144
 145   // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
 146   IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
 147   PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
 148   dropOutOfDateUpdates();
 149 }
 150
 151 bool DomTreeUpdater::hasPendingUpdates() const {
 152   return hasPendingDomTreeUpdates() || hasPendingPostDomTreeUpdates();
 153 }
 154
 155 bool DomTreeUpdater::hasPendingDomTreeUpdates() const {
 156   if (!DT)
 157     return false;
 158   return PendUpdates.size() != PendDTUpdateIndex;
 159 }
 160
 161 bool DomTreeUpdater::hasPendingPostDomTreeUpdates() const {
 162   if (!PDT)
 163     return false;
 164   return PendUpdates.size() != PendPDTUpdateIndex;
 165 }
 166
 167 bool DomTreeUpdater::isBBPendingDeletion(llvm::BasicBlock *DelBB) const {
 168   if (Strategy == UpdateStrategy::Eager || DeletedBBs.empty())
 169     return false;
 170   return DeletedBBs.count(DelBB) != 0;
 171 }
 172
 173 // The DT and PDT require the nodes related to updates
 174 // are not deleted when update functions are called.
 175 // So BasicBlock deletions must be pended when the
 176 // UpdateStrategy is Lazy. When the UpdateStrategy is
 177 // Eager, the BasicBlock will be deleted immediately.
 178 void DomTreeUpdater::deleteBB(BasicBlock *DelBB) {
 179   validateDeleteBB(DelBB);
 180   if (Strategy == UpdateStrategy::Lazy) {
 181     DeletedBBs.insert(DelBB);
 182     return;
 183   }
 184
 185   DelBB->removeFromParent();
 186   eraseDelBBNode(DelBB);
 187   delete DelBB;
 188 }
 189
 190 void DomTreeUpdater::callbackDeleteBB(
 191     BasicBlock *DelBB, std::function<void(BasicBlock *)> Callback) {
 192   validateDeleteBB(DelBB);
 193   if (Strategy == UpdateStrategy::Lazy) {
 194     Callbacks.push_back(CallBackOnDeletion(DelBB, Callback));
 195     DeletedBBs.insert(DelBB);
 196     return;
 197   }
 198
 199   DelBB->removeFromParent();
 200   eraseDelBBNode(DelBB);
 201   Callback(DelBB);
 202   delete DelBB;
 203 }
 204
 205 void DomTreeUpdater::eraseDelBBNode(BasicBlock *DelBB) {
 206   if (DT && !IsRecalculatingDomTree)
 207     if (DT->getNode(DelBB))
 208       DT->eraseNode(DelBB);
 209
 210   if (PDT && !IsRecalculatingPostDomTree)
 211     if (PDT->getNode(DelBB))
 212       PDT->eraseNode(DelBB);
 213 }
 214
 215 void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) {
 216   assert(DelBB && "Invalid push_back of nullptr DelBB.");
 217   assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
 218   // DelBB is unreachable and all its instructions are dead.
 219   while (!DelBB->empty()) {
 220     Instruction &I = DelBB->back();
 221     // Replace used instructions with an arbitrary value (undef).
 222     if (!I.use_empty())
 223       I.replaceAllUsesWith(llvm::UndefValue::get(I.getType()));
 224     DelBB->getInstList().pop_back();
 225   }
 226   // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
 227   // Child of Function F it must contain valid IR.
 228   new UnreachableInst(DelBB->getContext(), DelBB);
 229 }
 230
 231 void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates) {
 232   if (!DT && !PDT)
 233     return;
 234
 235   if (Strategy == UpdateStrategy::Lazy) {
 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 (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 (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