LCOV - code coverage report
Current view: top level - lib/IR - DomTreeUpdater.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 181 185 97.8 %
Date: 2018-10-20 13:21:21 Functions: 25 25 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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      135291 : bool DomTreeUpdater::isUpdateValid(
      25             :     const DominatorTree::UpdateType Update) const {
      26      135291 :   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      135291 :   const bool HasEdge = llvm::any_of(
      35      135291 :       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      135291 :   if (Kind == DominatorTree::Insert && !HasEdge)
      42             :     return false;
      43             : 
      44             :   // Edge exists in IR.
      45      135262 :   if (Kind == DominatorTree::Delete && HasEdge)
      46          40 :     return false;
      47             : 
      48             :   return true;
      49             : }
      50             : 
      51      132146 : bool DomTreeUpdater::isSelfDominance(
      52             :     const DominatorTree::UpdateType Update) const {
      53             :   // Won't affect DomTree and PostDomTree.
      54      264292 :   return Update.getFrom() == Update.getTo();
      55             : }
      56             : 
      57      120944 : 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      120944 :                                             From, To};
      69             :   // Only check duplicates in updates that are not applied by both trees.
      70             :   auto I =
      71      120944 :       PendUpdates.begin() + std::max(PendDTUpdateIndex, PendPDTUpdateIndex);
      72             :   const auto E = PendUpdates.end();
      73             : 
      74             :   assert(I <= E && "Iterator out of range.");
      75             : 
      76     5142572 :   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       17586 :       return false;
      85             :     }
      86             :   }
      87             : 
      88      103358 :   PendUpdates.push_back(Update); // Save the valid update.
      89      103358 :   return true;
      90             : }
      91             : 
      92      357325 : void DomTreeUpdater::applyDomTreeUpdates() {
      93             :   // No pending DomTreeUpdates.
      94      357325 :   if (Strategy != UpdateStrategy::Lazy || !DT)
      95             :     return;
      96             : 
      97             :   // Only apply updates not are applied by DomTree.
      98      267497 :   if (hasPendingDomTreeUpdates()) {
      99        6700 :     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        6700 :     DT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
     103       13400 :     PendDTUpdateIndex = PendUpdates.size();
     104             :   }
     105             : }
     106             : 
     107      180171 : void DomTreeUpdater::flush() {
     108      180171 :   applyDomTreeUpdates();
     109      180171 :   applyPostDomTreeUpdates();
     110      180171 :   dropOutOfDateUpdates();
     111      180171 : }
     112             : 
     113      180216 : void DomTreeUpdater::applyPostDomTreeUpdates() {
     114             :   // No pending PostDomTreeUpdates.
     115      180216 :   if (Strategy != UpdateStrategy::Lazy || !PDT)
     116             :     return;
     117             : 
     118             :   // Only apply updates not are applied by PostDomTree.
     119          49 :   if (hasPendingPostDomTreeUpdates()) {
     120           6 :     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           6 :     PDT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
     125          12 :     PendPDTUpdateIndex = PendUpdates.size();
     126             :   }
     127             : }
     128             : 
     129      268483 : void DomTreeUpdater::tryFlushDeletedBB() {
     130      268483 :   if (!hasPendingUpdates())
     131      268479 :     forceFlushDeletedBB();
     132      268483 : }
     133             : 
     134      269437 : bool DomTreeUpdater::forceFlushDeletedBB() {
     135      269437 :   if (DeletedBBs.empty())
     136             :     return false;
     137             : 
     138       36643 :   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       29011 :     BB->removeFromParent();
     147       29011 :     eraseDelBBNode(BB);
     148       29011 :     delete BB;
     149             :   }
     150        7632 :   DeletedBBs.clear();
     151             :   Callbacks.clear();
     152             :   return true;
     153             : }
     154             : 
     155         989 : void DomTreeUpdater::recalculate(Function &F) {
     156             : 
     157         989 :   if (Strategy == UpdateStrategy::Eager) {
     158          31 :     if (DT)
     159          27 :       DT->recalculate(F);
     160          31 :     if (PDT)
     161           3 :       PDT->recalculate(F);
     162          31 :     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         958 :   IsRecalculatingDomTree = IsRecalculatingPostDomTree = true;
     170             : 
     171             :   // Because all trees are going to be up-to-date after recalculation,
     172             :   // flush awaiting deleted BasicBlocks.
     173         958 :   forceFlushDeletedBB();
     174         958 :   if (DT)
     175         957 :     DT->recalculate(F);
     176         958 :   if (PDT)
     177           3 :     PDT->recalculate(F);
     178             : 
     179             :   // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
     180         958 :   IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
     181         958 :   PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
     182         958 :   dropOutOfDateUpdates();
     183             : }
     184             : 
     185      268489 : bool DomTreeUpdater::hasPendingUpdates() const {
     186      268489 :   return hasPendingDomTreeUpdates() || hasPendingPostDomTreeUpdates();
     187             : }
     188             : 
     189      871593 : bool DomTreeUpdater::hasPendingDomTreeUpdates() const {
     190      871593 :   if (!DT)
     191             :     return false;
     192     1743174 :   return PendUpdates.size() != PendDTUpdateIndex;
     193             : }
     194             : 
     195      268541 : bool DomTreeUpdater::hasPendingPostDomTreeUpdates() const {
     196      268541 :   if (!PDT)
     197             :     return false;
     198         266 :   return PendUpdates.size() != PendPDTUpdateIndex;
     199             : }
     200             : 
     201     1687124 : bool DomTreeUpdater::isBBPendingDeletion(llvm::BasicBlock *DelBB) const {
     202     1687124 :   if (Strategy == UpdateStrategy::Eager || DeletedBBs.empty())
     203             :     return false;
     204     1019632 :   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       31995 : void DomTreeUpdater::deleteBB(BasicBlock *DelBB) {
     213       31995 :   validateDeleteBB(DelBB);
     214       31995 :   if (Strategy == UpdateStrategy::Lazy) {
     215       29009 :     DeletedBBs.insert(DelBB);
     216       29009 :     return;
     217             :   }
     218             : 
     219        2986 :   DelBB->removeFromParent();
     220        2986 :   eraseDelBBNode(DelBB);
     221        2986 :   delete DelBB;
     222             : }
     223             : 
     224           4 : void DomTreeUpdater::callbackDeleteBB(
     225             :     BasicBlock *DelBB, std::function<void(BasicBlock *)> Callback) {
     226           4 :   validateDeleteBB(DelBB);
     227           4 :   if (Strategy == UpdateStrategy::Lazy) {
     228           9 :     Callbacks.push_back(CallBackOnDeletion(DelBB, Callback));
     229           3 :     DeletedBBs.insert(DelBB);
     230           3 :     return;
     231             :   }
     232             : 
     233           1 :   DelBB->removeFromParent();
     234           1 :   eraseDelBBNode(DelBB);
     235           1 :   Callback(DelBB);
     236           1 :   delete DelBB;
     237             : }
     238             : 
     239       31998 : void DomTreeUpdater::eraseDelBBNode(BasicBlock *DelBB) {
     240       31998 :   if (DT && !IsRecalculatingDomTree)
     241           2 :     if (DT->getNode(DelBB))
     242           2 :       DT->eraseNode(DelBB);
     243             : 
     244       31998 :   if (PDT && !IsRecalculatingPostDomTree)
     245          16 :     if (PDT->getNode(DelBB))
     246          16 :       PDT->eraseNode(DelBB);
     247       31998 : }
     248             : 
     249       31999 : 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       67090 :   while (!DelBB->empty()) {
     254             :     Instruction &I = DelBB->back();
     255             :     // Replace used instructions with an arbitrary value (undef).
     256       35091 :     if (!I.use_empty())
     257           0 :       I.replaceAllUsesWith(llvm::UndefValue::get(I.getType()));
     258       35091 :     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       63998 :   new UnreachableInst(DelBB->getContext(), DelBB);
     263       31999 : }
     264             : 
     265       35879 : void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
     266             :                                   bool ForceRemoveDuplicates) {
     267       35879 :   if (!DT && !PDT)
     268             :     return;
     269             : 
     270       35879 :   if (Strategy == UpdateStrategy::Lazy || ForceRemoveDuplicates) {
     271             :     SmallVector<DominatorTree::UpdateType, 8> Seen;
     272      168693 :     for (const auto U : Updates)
     273             :       // For Lazy UpdateStrategy, avoid duplicates to applyLazyUpdate() to save
     274             :       // on analysis.
     275      132858 :       if (llvm::none_of(
     276             :               Seen,
     277      132207 :               [U](const DominatorTree::UpdateType S) { return S == U; }) &&
     278      265004 :           isUpdateValid(U) && !isSelfDominance(U)) {
     279      131425 :         Seen.push_back(U);
     280      131425 :         if (Strategy == UpdateStrategy::Lazy)
     281      235738 :           applyLazyUpdate(U.getKind(), U.getFrom(), U.getTo());
     282             :       }
     283       35835 :     if (Strategy == UpdateStrategy::Lazy)
     284             :       return;
     285             : 
     286        2992 :     if (DT)
     287        2990 :       DT->applyUpdates(Seen);
     288        2992 :     if (PDT)
     289          18 :       PDT->applyUpdates(Seen);
     290        2992 :     return;
     291             :   }
     292             : 
     293          44 :   if (DT)
     294          11 :     DT->applyUpdates(Updates);
     295          44 :   if (PDT)
     296          34 :     PDT->applyUpdates(Updates);
     297             : }
     298             : 
     299      177154 : DominatorTree &DomTreeUpdater::getDomTree() {
     300             :   assert(DT && "Invalid acquisition of a null DomTree");
     301      177154 :   applyDomTreeUpdates();
     302      177154 :   dropOutOfDateUpdates();
     303      177154 :   return *DT;
     304             : }
     305             : 
     306          45 : PostDominatorTree &DomTreeUpdater::getPostDomTree() {
     307             :   assert(PDT && "Invalid acquisition of a null PostDomTree");
     308          45 :   applyPostDomTreeUpdates();
     309          45 :   dropOutOfDateUpdates();
     310          45 :   return *PDT;
     311             : }
     312             : 
     313         277 : 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         277 :   if (!DT && !PDT)
     321             :     return;
     322             : 
     323             :   // Won't affect DomTree and PostDomTree; discard update.
     324         273 :   if (From == To)
     325             :     return;
     326             : 
     327         270 :   if (Strategy == UpdateStrategy::Eager) {
     328         269 :     if (DT)
     329         269 :       DT->insertEdge(From, To);
     330         269 :     if (PDT)
     331           0 :       PDT->insertEdge(From, To);
     332         269 :     return;
     333             :   }
     334             : 
     335           1 :   applyLazyUpdate(DominatorTree::Insert, From, To);
     336             : }
     337             : 
     338           3 : void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
     339           3 :   if (From == To)
     340             :     return;
     341             : 
     342           2 :   if (!DT && !PDT)
     343             :     return;
     344             : 
     345           2 :   if (!isUpdateValid({DominatorTree::Insert, From, To}))
     346             :     return;
     347             : 
     348           1 :   if (Strategy == UpdateStrategy::Eager) {
     349           1 :     if (DT)
     350           1 :       DT->insertEdge(From, To);
     351           1 :     if (PDT)
     352           1 :       PDT->insertEdge(From, To);
     353           1 :     return;
     354             :   }
     355             : 
     356           0 :   applyLazyUpdate(DominatorTree::Insert, From, To);
     357             : }
     358             : 
     359         265 : 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         265 :   if (!DT && !PDT)
     367             :     return;
     368             : 
     369             :   // Won't affect DomTree and PostDomTree; discard update.
     370         264 :   if (From == To)
     371             :     return;
     372             : 
     373         262 :   if (Strategy == UpdateStrategy::Eager) {
     374         259 :     if (DT)
     375         259 :       DT->deleteEdge(From, To);
     376         259 :     if (PDT)
     377           0 :       PDT->deleteEdge(From, To);
     378         259 :     return;
     379             :   }
     380             : 
     381           3 :   applyLazyUpdate(DominatorTree::Delete, From, To);
     382             : }
     383             : 
     384        3085 : void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
     385        3085 :   if (From == To)
     386             :     return;
     387             : 
     388        3082 :   if (!DT && !PDT)
     389             :     return;
     390             : 
     391        3082 :   if (!isUpdateValid({DominatorTree::Delete, From, To}))
     392             :     return;
     393             : 
     394        3075 :   if (Strategy == UpdateStrategy::Eager) {
     395           4 :     if (DT)
     396           4 :       DT->deleteEdge(From, To);
     397           4 :     if (PDT)
     398           4 :       PDT->deleteEdge(From, To);
     399           4 :     return;
     400             :   }
     401             : 
     402        3071 :   applyLazyUpdate(DominatorTree::Delete, From, To);
     403             : }
     404             : 
     405      358328 : void DomTreeUpdater::dropOutOfDateUpdates() {
     406      358328 :   if (Strategy == DomTreeUpdater::UpdateStrategy::Eager)
     407             :     return;
     408             : 
     409      268483 :   tryFlushDeletedBB();
     410             : 
     411             :   // Drop all updates applied by both trees.
     412      268483 :   if (!DT)
     413          12 :     PendDTUpdateIndex = PendUpdates.size();
     414      268483 :   if (!PDT)
     415      536816 :     PendPDTUpdateIndex = PendUpdates.size();
     416             : 
     417      268486 :   const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
     418             :   const auto B = PendUpdates.begin();
     419      268483 :   const auto E = PendUpdates.begin() + dropIndex;
     420             :   assert(B <= E && "Iterator out of range.");
     421             :   PendUpdates.erase(B, E);
     422             :   // Calculate current index.
     423      268483 :   PendDTUpdateIndex -= dropIndex;
     424      268483 :   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

Generated by: LCOV version 1.13