llvm/Analysis/GenericDomTreeUpdaterImpl.h

0001 //===- GenericDomTreeUpdaterImpl.h ------------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file implements the GenericDomTreeUpdater class. This file should only
0010 // be included by files that implement a specialization of the relevant
0011 // templates. Currently these are:
0012 // - llvm/lib/Analysis/DomTreeUpdater.cpp
0013 // - llvm/lib/CodeGen/MachineDomTreeUpdater.cpp
0014 //
0015 //===----------------------------------------------------------------------===//
0016 #ifndef LLVM_ANALYSIS_GENERICDOMTREEUPDATERIMPL_H
0017 #define LLVM_ANALYSIS_GENERICDOMTREEUPDATERIMPL_H
0018
0019 #include "llvm/ADT/SmallBitVector.h"
0020 #include "llvm/Analysis/GenericDomTreeUpdater.h"
0021 #include "llvm/Support/Debug.h"
0022 #include "llvm/Support/raw_ostream.h"
0023
0024 namespace llvm {
0025
0026 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
0027 template <typename FuncT>
0028 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::recalculate(
0029     FuncT &F) {
0030   if (Strategy == UpdateStrategy::Eager) {
0031     if (DT)
0032       DT->recalculate(F);
0033     if (PDT)
0034       PDT->recalculate(F);
0035     return;
0036   }
0037
0038   // There is little performance gain if we pend the recalculation under
0039   // Lazy UpdateStrategy so we recalculate available trees immediately.
0040
0041   // Prevent forceFlushDeletedBB() from erasing DomTree or PostDomTree nodes.
0042   IsRecalculatingDomTree = IsRecalculatingPostDomTree = true;
0043
0044   // Because all trees are going to be up-to-date after recalculation,
0045   // flush awaiting deleted BasicBlocks.
0046   derived().forceFlushDeletedBB();
0047   if (DT)
0048     DT->recalculate(F);
0049   if (PDT)
0050     PDT->recalculate(F);
0051
0052   // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
0053   IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
0054   PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
0055   dropOutOfDateUpdates();
0056 }
0057
0058 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
0059 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::applyUpdates(
0060     ArrayRef<UpdateT> Updates) {
0061   if (!DT && !PDT)
0062     return;
0063
0064   if (Strategy == UpdateStrategy::Lazy) {
0065     PendUpdates.reserve(PendUpdates.size() + Updates.size());
0066     for (const auto &U : Updates)
0067       if (!isSelfDominance(U))
0068         PendUpdates.push_back(U);
0069
0070     return;
0071   }
0072
0073   if (DT)
0074     DT->applyUpdates(Updates);
0075   if (PDT)
0076     PDT->applyUpdates(Updates);
0077 }
0078
0079 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
0080 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::
0081     applyUpdatesPermissive(ArrayRef<UpdateT> Updates) {
0082   if (!DT && !PDT)
0083     return;
0084
0085   SmallSet<std::pair<BasicBlockT *, BasicBlockT *>, 8> Seen;
0086   SmallVector<UpdateT, 8> DeduplicatedUpdates;
0087   for (const auto &U : Updates) {
0088     auto Edge = std::make_pair(U.getFrom(), U.getTo());
0089     // Because it is illegal to submit updates that have already been applied
0090     // and updates to an edge need to be strictly ordered,
0091     // it is safe to infer the existence of an edge from the first update
0092     // to this edge.
0093     // If the first update to an edge is "Delete", it means that the edge
0094     // existed before. If the first update to an edge is "Insert", it means
0095     // that the edge didn't exist before.
0096     //
0097     // For example, if the user submits {{Delete, A, B}, {Insert, A, B}},
0098     // because
0099     // 1. it is illegal to submit updates that have already been applied,
0100     // i.e., user cannot delete an nonexistent edge,
0101     // 2. updates to an edge need to be strictly ordered,
0102     // So, initially edge A -> B existed.
0103     // We can then safely ignore future updates to this edge and directly
0104     // inspect the current CFG:
0105     // a. If the edge still exists, because the user cannot insert an existent
0106     // edge, so both {Delete, A, B}, {Insert, A, B} actually happened and
0107     // resulted in a no-op. DTU won't submit any update in this case.
0108     // b. If the edge doesn't exist, we can then infer that {Delete, A, B}
0109     // actually happened but {Insert, A, B} was an invalid update which never
0110     // happened. DTU will submit {Delete, A, B} in this case.
0111     if (!isSelfDominance(U) && Seen.insert(Edge).second) {
0112       // If the update doesn't appear in the CFG, it means that
0113       // either the change isn't made or relevant operations
0114       // result in a no-op.
0115       if (isUpdateValid(U)) {
0116         if (isLazy())
0117           PendUpdates.push_back(U);
0118         else
0119           DeduplicatedUpdates.push_back(U);
0120       }
0121     }
0122   }
0123
0124   if (Strategy == UpdateStrategy::Lazy)
0125     return;
0126
0127   if (DT)
0128     DT->applyUpdates(DeduplicatedUpdates);
0129   if (PDT)
0130     PDT->applyUpdates(DeduplicatedUpdates);
0131 }
0132
0133 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
0134 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::splitCriticalEdge(
0135     BasicBlockT *FromBB, BasicBlockT *ToBB, BasicBlockT *NewBB) {
0136   if (!DT && !PDT)
0137     return;
0138
0139   CriticalEdge E = {FromBB, ToBB, NewBB};
0140   if (Strategy == UpdateStrategy::Lazy) {
0141     PendUpdates.push_back(E);
0142     return;
0143   }
0144
0145   if (DT)
0146     splitDTCriticalEdges(E);
0147   if (PDT)
0148     splitPDTCriticalEdges(E);
0149 }
0150
0151 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
0152 DomTreeT &
0153 GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::getDomTree() {
0154   assert(DT && "Invalid acquisition of a null DomTree");
0155   applyDomTreeUpdates();
0156   dropOutOfDateUpdates();
0157   return *DT;
0158 }
0159
0160 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
0161 PostDomTreeT &
0162 GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::getPostDomTree() {
0163   assert(PDT && "Invalid acquisition of a null PostDomTree");
0164   applyPostDomTreeUpdates();
0165   dropOutOfDateUpdates();
0166   return *PDT;
0167 }
0168
0169 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
0170 LLVM_DUMP_METHOD void
0171 GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::dump() const {
0172 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
0173   raw_ostream &OS = llvm::dbgs();
0174
0175   OS << "Available Trees: ";
0176   if (DT || PDT) {
0177     if (DT)
0178       OS << "DomTree ";
0179     if (PDT)
0180       OS << "PostDomTree ";
0181     OS << "\n";
0182   } else
0183     OS << "None\n";
0184
0185   OS << "UpdateStrategy: ";
0186   if (Strategy == UpdateStrategy::Eager) {
0187     OS << "Eager\n";
0188     return;
0189   } else
0190     OS << "Lazy\n";
0191   int Index = 0;
0192
0193   auto printBlockInfo = [&](BasicBlockT *BB, StringRef Ending) {
0194     if (BB) {
0195       auto S = BB->getName();
0196       if (!BB->hasName())
0197         S = "(no name)";
0198       OS << S << "(" << BB << ")" << Ending;
0199     } else {
0200       OS << "(badref)" << Ending;
0201     }
0202   };
0203
0204   auto printUpdates =
0205       [&](typename ArrayRef<DomTreeUpdate>::const_iterator begin,
0206           typename ArrayRef<DomTreeUpdate>::const_iterator end) {
0207         if (begin == end)
0208           OS << "  None\n";
0209         Index = 0;
0210         for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {
0211           if (!It->IsCriticalEdgeSplit) {
0212             auto U = It->Update;
0213             OS << "  " << Index << " : ";
0214             ++Index;
0215             if (U.getKind() == DomTreeT::Insert)
0216               OS << "Insert, ";
0217             else
0218               OS << "Delete, ";
0219             printBlockInfo(U.getFrom(), ", ");
0220             printBlockInfo(U.getTo(), "\n");
0221           } else {
0222             const auto &Edge = It->EdgeSplit;
0223             OS << "  " << Index++ << " : Split critical edge, ";
0224             printBlockInfo(Edge.FromBB, ", ");
0225             printBlockInfo(Edge.ToBB, ", ");
0226             printBlockInfo(Edge.NewBB, "\n");
0227           }
0228         }
0229       };
0230
0231   if (DT) {
0232     const auto I = PendUpdates.begin() + PendDTUpdateIndex;
0233     assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
0234            "Iterator out of range.");
0235     OS << "Applied but not cleared DomTreeUpdates:\n";
0236     printUpdates(PendUpdates.begin(), I);
0237     OS << "Pending DomTreeUpdates:\n";
0238     printUpdates(I, PendUpdates.end());
0239   }
0240
0241   if (PDT) {
0242     const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
0243     assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
0244            "Iterator out of range.");
0245     OS << "Applied but not cleared PostDomTreeUpdates:\n";
0246     printUpdates(PendUpdates.begin(), I);
0247     OS << "Pending PostDomTreeUpdates:\n";
0248     printUpdates(I, PendUpdates.end());
0249   }
0250
0251   OS << "Pending DeletedBBs:\n";
0252   Index = 0;
0253   for (const auto *BB : DeletedBBs) {
0254     OS << "  " << Index << " : ";
0255     ++Index;
0256     if (BB->hasName())
0257       OS << BB->getName() << "(";
0258     else
0259       OS << "(no name)(";
0260     OS << BB << ")\n";
0261   }
0262 #endif
0263 }
0264
0265 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
0266 template <bool IsForward>
0267 void GenericDomTreeUpdater<DerivedT, DomTreeT,
0268                            PostDomTreeT>::applyUpdatesImpl() {
0269   auto *DomTree = [&]() {
0270     if constexpr (IsForward)
0271       return DT;
0272     else
0273       return PDT;
0274   }();
0275   // No pending DomTreeUpdates.
0276   if (Strategy != UpdateStrategy::Lazy || !DomTree)
0277     return;
0278   size_t &PendUpdateIndex = IsForward ? PendDTUpdateIndex : PendPDTUpdateIndex;
0279
0280   // Only apply updates not are applied by (Post)DomTree.
0281   while (IsForward ? hasPendingDomTreeUpdates()
0282                    : hasPendingPostDomTreeUpdates()) {
0283     auto I = PendUpdates.begin() + PendUpdateIndex;
0284     const auto E = PendUpdates.end();
0285     assert(I < E && "Iterator range invalid; there should be DomTree updates.");
0286     if (!I->IsCriticalEdgeSplit) {
0287       SmallVector<UpdateT, 32> NormalUpdates;
0288       for (; I != E && !I->IsCriticalEdgeSplit; ++I)
0289         NormalUpdates.push_back(I->Update);
0290       DomTree->applyUpdates(NormalUpdates);
0291       PendUpdateIndex += NormalUpdates.size();
0292     } else {
0293       SmallVector<CriticalEdge> CriticalEdges;
0294       for (; I != E && I->IsCriticalEdgeSplit; ++I)
0295         CriticalEdges.push_back(I->EdgeSplit);
0296       IsForward ? splitDTCriticalEdges(CriticalEdges)
0297                 : splitPDTCriticalEdges(CriticalEdges);
0298       PendUpdateIndex += CriticalEdges.size();
0299     }
0300   }
0301 }
0302
0303 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
0304 bool GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::isUpdateValid(
0305     UpdateT Update) const {
0306   const auto *From = Update.getFrom();
0307   const auto *To = Update.getTo();
0308   const auto Kind = Update.getKind();
0309
0310   // Discard updates by inspecting the current state of successors of From.
0311   // Since isUpdateValid() must be called *after* the Terminator of From is
0312   // altered we can determine if the update is unnecessary for batch updates
0313   // or invalid for a single update.
0314   const bool HasEdge = llvm::is_contained(successors(From), To);
0315
0316   // If the IR does not match the update,
0317   // 1. In batch updates, this update is unnecessary.
0318   // 2. When called by insertEdge*()/deleteEdge*(), this update is invalid.
0319   // Edge does not exist in IR.
0320   if (Kind == DomTreeT::Insert && !HasEdge)
0321     return false;
0322
0323   // Edge exists in IR.
0324   if (Kind == DomTreeT::Delete && HasEdge)
0325     return false;
0326
0327   return true;
0328 }
0329
0330 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
0331 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::eraseDelBBNode(
0332     BasicBlockT *DelBB) {
0333   if (DT && !IsRecalculatingDomTree)
0334     if (DT->getNode(DelBB))
0335       DT->eraseNode(DelBB);
0336
0337   if (PDT && !IsRecalculatingPostDomTree)
0338     if (PDT->getNode(DelBB))
0339       PDT->eraseNode(DelBB);
0340 }
0341
0342 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
0343 void GenericDomTreeUpdater<DerivedT, DomTreeT,
0344                            PostDomTreeT>::tryFlushDeletedBB() {
0345   if (!hasPendingUpdates())
0346     derived().forceFlushDeletedBB();
0347 }
0348
0349 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
0350 void GenericDomTreeUpdater<DerivedT, DomTreeT,
0351                            PostDomTreeT>::dropOutOfDateUpdates() {
0352   if (Strategy == UpdateStrategy::Eager)
0353     return;
0354
0355   tryFlushDeletedBB();
0356
0357   // Drop all updates applied by both trees.
0358   if (!DT)
0359     PendDTUpdateIndex = PendUpdates.size();
0360   if (!PDT)
0361     PendPDTUpdateIndex = PendUpdates.size();
0362
0363   const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
0364   const auto B = PendUpdates.begin();
0365   const auto E = PendUpdates.begin() + dropIndex;
0366   assert(B <= E && "Iterator out of range.");
0367   PendUpdates.erase(B, E);
0368   // Calculate current index.
0369   PendDTUpdateIndex -= dropIndex;
0370   PendPDTUpdateIndex -= dropIndex;
0371 }
0372
0373 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
0374 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::
0375     splitDTCriticalEdges(ArrayRef<CriticalEdge> Edges) {
0376   // Bail out early if there is nothing to do.
0377   if (!DT || Edges.empty())
0378     return;
0379
0380   // Remember all the basic blocks that are inserted during
0381   // edge splitting.
0382   // Invariant: NewBBs == all the basic blocks contained in the NewBB
0383   // field of all the elements of Edges.
0384   // I.e., forall elt in Edges, it exists BB in NewBBs
0385   // such as BB == elt.NewBB.
0386   SmallSet<BasicBlockT *, 32> NewBBs;
0387   for (auto &Edge : Edges)
0388     NewBBs.insert(Edge.NewBB);
0389   // For each element in Edges, remember whether or not element
0390   // is the new immediate domminator of its successor. The mapping is done by
0391   // index, i.e., the information for the ith element of Edges is
0392   // the ith element of IsNewIDom.
0393   SmallBitVector IsNewIDom(Edges.size(), true);
0394
0395   // Collect all the dominance properties info, before invalidating
0396   // the underlying DT.
0397   for (const auto &[Idx, Edge] : enumerate(Edges)) {
0398     // Update dominator information.
0399     BasicBlockT *Succ = Edge.ToBB;
0400     auto *SuccDTNode = DT->getNode(Succ);
0401
0402     for (BasicBlockT *PredBB : predecessors(Succ)) {
0403       if (PredBB == Edge.NewBB)
0404         continue;
0405       // If we are in this situation:
0406       // FromBB1        FromBB2
0407       //    +              +
0408       //   + +            + +
0409       //  +   +          +   +
0410       // ...  Split1  Split2 ...
0411       //           +   +
0412       //            + +
0413       //             +
0414       //            Succ
0415       // Instead of checking the domiance property with Split2, we check it
0416       // with FromBB2 since Split2 is still unknown of the underlying DT
0417       // structure.
0418       if (NewBBs.contains(PredBB)) {
0419         assert(pred_size(PredBB) == 1 && "A basic block resulting from a "
0420                                          "critical edge split has more "
0421                                          "than one predecessor!");
0422         PredBB = *pred_begin(PredBB);
0423       }
0424       if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) {
0425         IsNewIDom[Idx] = false;
0426         break;
0427       }
0428     }
0429   }
0430
0431   // Now, update DT with the collected dominance properties info.
0432   for (const auto &[Idx, Edge] : enumerate(Edges)) {
0433     // We know FromBB dominates NewBB.
0434     auto *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB);
0435
0436     // If all the other predecessors of "Succ" are dominated by "Succ" itself
0437     // then the new block is the new immediate dominator of "Succ". Otherwise,
0438     // the new block doesn't dominate anything.
0439     if (IsNewIDom[Idx])
0440       DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
0441   }
0442 }
0443
0444 // Post dominator tree is different, the new basic block in critical edge
0445 // may become the new root.
0446 template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
0447 void GenericDomTreeUpdater<DerivedT, DomTreeT, PostDomTreeT>::
0448     splitPDTCriticalEdges(ArrayRef<CriticalEdge> Edges) {
0449   // Bail out early if there is nothing to do.
0450   if (!PDT || Edges.empty())
0451     return;
0452
0453   std::vector<UpdateT> Updates;
0454   for (const auto &Edge : Edges) {
0455     Updates.push_back({PostDomTreeT::Insert, Edge.FromBB, Edge.NewBB});
0456     Updates.push_back({PostDomTreeT::Insert, Edge.NewBB, Edge.ToBB});
0457     if (!llvm::is_contained(successors(Edge.FromBB), Edge.ToBB))
0458       Updates.push_back({PostDomTreeT::Delete, Edge.FromBB, Edge.ToBB});
0459   }
0460   PDT->applyUpdates(Updates);
0461 }
0462
0463 } // namespace llvm
0464
0465 #endif // LLVM_ANALYSIS_GENERICDOMTREEUPDATERIMPL_H