From e22de4e46d1dd1aacc3a7060d24bcbe89908ba6c Mon Sep 17 00:00:00 2001 From: Alina Sbirlea Date: Fri, 24 Jul 2020 18:36:18 -0700 Subject: [PATCH] [DominatorTree] Simplify ChildrenGetter. Summary: Simplify ChildrenGetter to a simple wrapper around a GraphDiff call. GraphDiff already handles nullptr in children, so the special casing in clang can also be removed. Reviewers: kuhar, dblaikie Subscribers: llvm-commits, cfe-commits Tags: #clang, #llvm Differential Revision: https://reviews.llvm.org/D84713 --- clang/include/clang/Analysis/Analyses/Dominators.h | 70 ---------------------- .../llvm/Support/GenericDomTreeConstruction.h | 42 ++++--------- 2 files changed, 11 insertions(+), 101 deletions(-) diff --git a/clang/include/clang/Analysis/Analyses/Dominators.h b/clang/include/clang/Analysis/Analyses/Dominators.h index 95a6611..25a5ba9 100644 --- a/clang/include/clang/Analysis/Analyses/Dominators.h +++ b/clang/include/clang/Analysis/Analyses/Dominators.h @@ -273,76 +273,6 @@ public: namespace llvm { -/// Clang's CFG contains nullpointers for unreachable succesors, e.g. when an -/// if statement's condition is always false, it's 'then' branch is represented -/// with a nullptr. This however will result in a nullpointer derefernece for -/// dominator tree calculation. -/// -/// To circumvent this, let's just crudely specialize the children getters -/// used in LLVM's dominator tree builder. -namespace DomTreeBuilder { - -using ClangCFGDomChildrenGetter = -SemiNCAInfo::ChildrenGetter< - /*Inverse=*/false>; - -template <> -template <> -inline ClangCFGDomChildrenGetter::ResultTy ClangCFGDomChildrenGetter::Get( - clang::CFGBlock *N, std::integral_constant) { - auto RChildren = reverse(children(N)); - ResultTy Ret(RChildren.begin(), RChildren.end()); - Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end()); - return Ret; -} - -using ClangCFGDomReverseChildrenGetter = -SemiNCAInfo::ChildrenGetter< - /*Inverse=*/true>; - -template <> -template <> -inline ClangCFGDomReverseChildrenGetter::ResultTy -ClangCFGDomReverseChildrenGetter::Get( - clang::CFGBlock *N, std::integral_constant) { - auto IChildren = inverse_children(N); - ResultTy Ret(IChildren.begin(), IChildren.end()); - Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end()); - return Ret; -} - -using ClangCFGPostDomChildrenGetter = -SemiNCAInfo::ChildrenGetter< - /*Inverse=*/false>; - -template <> -template <> -inline ClangCFGPostDomChildrenGetter::ResultTy -ClangCFGPostDomChildrenGetter::Get( - clang::CFGBlock *N, std::integral_constant) { - auto RChildren = reverse(children(N)); - ResultTy Ret(RChildren.begin(), RChildren.end()); - Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end()); - return Ret; -} - -using ClangCFGPostDomReverseChildrenGetter = -SemiNCAInfo::ChildrenGetter< - /*Inverse=*/true>; - -template <> -template <> -inline ClangCFGPostDomReverseChildrenGetter::ResultTy -ClangCFGPostDomReverseChildrenGetter::Get( - clang::CFGBlock *N, std::integral_constant) { - auto IChildren = inverse_children(N); - ResultTy Ret(IChildren.begin(), IChildren.end()); - Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end()); - return Ret; -} - -} // end of namespace DomTreeBuilder - //===------------------------------------- /// DominatorTree GraphTraits specialization so the DominatorTree can be /// iterable by generic graph iterators. diff --git a/llvm/include/llvm/Support/GenericDomTreeConstruction.h b/llvm/include/llvm/Support/GenericDomTreeConstruction.h index 5a1f03c..6a9d38b 100644 --- a/llvm/include/llvm/Support/GenericDomTreeConstruction.h +++ b/llvm/include/llvm/Support/GenericDomTreeConstruction.h @@ -103,31 +103,13 @@ struct SemiNCAInfo { // in progress, we need this information to continue it. } - template struct ChildrenGetter { - using ResultTy = SmallVector; - - static ResultTy Get(NodePtr N, std::integral_constant) { - auto RChildren = reverse(children(N)); - return ResultTy(RChildren.begin(), RChildren.end()); - } - - static ResultTy Get(NodePtr N, std::integral_constant) { - auto IChildren = inverse_children(N); - return ResultTy(IChildren.begin(), IChildren.end()); - } - - using Tag = std::integral_constant; - - // The function below is the core part of the batch updater. It allows the - // Depth Based Search algorithm to perform incremental updates in lockstep - // with updates to the CFG. We emulated lockstep CFG updates by getting its - // next snapshots by reverse-applying future updates. - static ResultTy Get(NodePtr N, BatchUpdatePtr BUI) { - if (!BUI) - return Get(N, Tag()); + template + static SmallVector getChildren(NodePtr N, BatchUpdatePtr BUI) { + if (BUI) return BUI->PreViewCFG.template getChildren(N); - } - }; + GraphDiffT GD; + return GD.template getChildren(N); + } NodePtr getIDom(NodePtr BB) const { auto InfoIt = NodeToInfo.find(BB); @@ -194,8 +176,7 @@ struct SemiNCAInfo { NumToNode.push_back(BB); constexpr bool Direction = IsReverse != IsPostDom; // XOR. - for (const NodePtr Succ : - ChildrenGetter::Get(BB, BatchUpdates)) { + for (const NodePtr Succ : getChildren(BB, BatchUpdates)) { const auto SIT = NodeToInfo.find(Succ); // Don't visit nodes more than once but remember to collect // ReverseChildren. @@ -330,7 +311,7 @@ struct SemiNCAInfo { // to CFG nodes within infinite loops. static bool HasForwardSuccessors(const NodePtr N, BatchUpdatePtr BUI) { assert(N && "N must be a valid node"); - return !ChildrenGetter::Get(N, BUI).empty(); + return !getChildren(N, BUI).empty(); } static NodePtr GetEntryNode(const DomTreeT &DT) { @@ -748,8 +729,7 @@ struct SemiNCAInfo { // // Invariant: there is an optimal path from `To` to TN with the minimum // depth being CurrentLevel. - for (const NodePtr Succ : - ChildrenGetter::Get(TN->getBlock(), BUI)) { + for (const NodePtr Succ : getChildren(TN->getBlock(), BUI)) { const TreeNodePtr SuccTN = DT.getNode(Succ); assert(SuccTN && "Unreachable successor found at reachable insertion"); @@ -879,7 +859,7 @@ struct SemiNCAInfo { // the DomTree about it. // The check is O(N), so run it only in debug configuration. auto IsSuccessor = [BUI](const NodePtr SuccCandidate, const NodePtr Of) { - auto Successors = ChildrenGetter::Get(Of, BUI); + auto Successors = getChildren(Of, BUI); return llvm::find(Successors, SuccCandidate) != Successors.end(); }; (void)IsSuccessor; @@ -967,7 +947,7 @@ struct SemiNCAInfo { LLVM_DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN) << "\n"); auto TNB = TN->getBlock(); - for (const NodePtr Pred : ChildrenGetter::Get(TNB, BUI)) { + for (const NodePtr Pred : getChildren(TNB, BUI)) { LLVM_DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n"); if (!DT.getNode(Pred)) continue; -- 2.7.4