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/Constants.h"
  18 #include "llvm/IR/Instructions.h"
  19 #include "llvm/Support/GenericDomTree.h"
  20 #include <algorithm>
  21 #include <functional>
  22 #include <utility>
  23
  24 namespace llvm {
  25
  26 bool DomTreeUpdater::isUpdateValid(
  27     const DominatorTree::UpdateType Update) const {
  28   const auto *From = Update.getFrom();
  29   const auto *To = Update.getTo();
  30   const auto Kind = Update.getKind();
  31
  32   // Discard updates by inspecting the current state of successors of From.
  33   // Since isUpdateValid() must be called *after* the Terminator of From is
  34   // altered we can determine if the update is unnecessary for batch updates
  35   // or invalid for a single update.
  36   const bool HasEdge = llvm::is_contained(successors(From), 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->size() == 1 && 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 (poison).
 221     if (!I.use_empty())
 222       I.replaceAllUsesWith(PoisonValue::get(I.getType()));
 223     DelBB->back().eraseFromParent();
 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::dropOutOfDateUpdates() {
 318   if (Strategy == DomTreeUpdater::UpdateStrategy::Eager)
 319     return;
 320
 321   tryFlushDeletedBB();
 322
 323   // Drop all updates applied by both trees.
 324   if (!DT)
 325     PendDTUpdateIndex = PendUpdates.size();
 326   if (!PDT)
 327     PendPDTUpdateIndex = PendUpdates.size();
 328
 329   const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
 330   const auto B = PendUpdates.begin();
 331   const auto E = PendUpdates.begin() + dropIndex;
 332   assert(B <= E && "Iterator out of range.");
 333   PendUpdates.erase(B, E);
 334   // Calculate current index.
 335   PendDTUpdateIndex -= dropIndex;
 336   PendPDTUpdateIndex -= dropIndex;
 337 }
 338
 339 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 340 LLVM_DUMP_METHOD void DomTreeUpdater::dump() const {
 341   raw_ostream &OS = llvm::dbgs();
 342
 343   OS << "Available Trees: ";
 344   if (DT || PDT) {
 345     if (DT)
 346       OS << "DomTree ";
 347     if (PDT)
 348       OS << "PostDomTree ";
 349     OS << "\n";
 350   } else
 351     OS << "None\n";
 352
 353   OS << "UpdateStrategy: ";
 354   if (Strategy == UpdateStrategy::Eager) {
 355     OS << "Eager\n";
 356     return;
 357   } else
 358     OS << "Lazy\n";
 359   int Index = 0;
 360
 361   auto printUpdates =
 362       [&](ArrayRef<DominatorTree::UpdateType>::const_iterator begin,
 363           ArrayRef<DominatorTree::UpdateType>::const_iterator end) {
 364         if (begin == end)
 365           OS << "  None\n";
 366         Index = 0;
 367         for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {
 368           auto U = *It;
 369           OS << "  " << Index << " : ";
 370           ++Index;
 371           if (U.getKind() == DominatorTree::Insert)
 372             OS << "Insert, ";
 373           else
 374             OS << "Delete, ";
 375           BasicBlock *From = U.getFrom();
 376           if (From) {
 377             auto S = From->getName();
 378             if (!From->hasName())
 379               S = "(no name)";
 380             OS << S << "(" << From << "), ";
 381           } else {
 382             OS << "(badref), ";
 383           }
 384           BasicBlock *To = U.getTo();
 385           if (To) {
 386             auto S = To->getName();
 387             if (!To->hasName())
 388               S = "(no_name)";
 389             OS << S << "(" << To << ")\n";
 390           } else {
 391             OS << "(badref)\n";
 392           }
 393         }
 394       };
 395
 396   if (DT) {
 397     const auto I = PendUpdates.begin() + PendDTUpdateIndex;
 398     assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
 399            "Iterator out of range.");
 400     OS << "Applied but not cleared DomTreeUpdates:\n";
 401     printUpdates(PendUpdates.begin(), I);
 402     OS << "Pending DomTreeUpdates:\n";
 403     printUpdates(I, PendUpdates.end());
 404   }
 405
 406   if (PDT) {
 407     const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
 408     assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
 409            "Iterator out of range.");
 410     OS << "Applied but not cleared PostDomTreeUpdates:\n";
 411     printUpdates(PendUpdates.begin(), I);
 412     OS << "Pending PostDomTreeUpdates:\n";
 413     printUpdates(I, PendUpdates.end());
 414   }
 415
 416   OS << "Pending DeletedBBs:\n";
 417   Index = 0;
 418   for (const auto *BB : DeletedBBs) {
 419     OS << "  " << Index << " : ";
 420     ++Index;
 421     if (BB->hasName())
 422       OS << BB->getName() << "(";
 423     else
 424       OS << "(no_name)(";
 425     OS << BB << ")\n";
 426   }
 427
 428   OS << "Pending Callbacks:\n";
 429   Index = 0;
 430   for (const auto &BB : Callbacks) {
 431     OS << "  " << Index << " : ";
 432     ++Index;
 433     if (BB->hasName())
 434       OS << BB->getName() << "(";
 435     else
 436       OS << "(no_name)(";
 437     OS << BB << ")\n";
 438   }
 439 }
 440 #endif
 441 } // namespace llvm