lib/IR/DomTreeUpdater.cpp

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