From 9353421ecd12d071a27a0f05948113a45888f16b Mon Sep 17 00:00:00 2001 From: Kristof Umann Date: Tue, 2 Jul 2019 11:30:12 +0000 Subject: [PATCH] [IDF] Generalize IDFCalculator to be used with Clang's CFG I'm currently working on a GSoC project that aims to improve the the bug reports of the analyzer. The main heuristic I plan to use is to explain values that are a control dependency of the bug location better. 01 bool b = messyComputation(); 02 int i = 0; 03 if (b) // control dependency of the bug site, let's explain why we assume val 04 // to be true 05 10 / i; // warn: division by zero Because of this, I'd like to generalize IDFCalculator so that I could use it for Clang's CFG: D62883. In detail: * Rename IDFCalculator to IDFCalculatorBase, make it take a general CFG node type as a template argument rather then strictly BasicBlock (but preserve ForwardIDFCalculator and ReverseIDFCalculator) * Move IDFCalculatorBase from llvm/include/llvm/Analysis to llvm/include/llvm/Support (but leave the BasicBlock variants in llvm/include/llvm/Analysis) * clang-format the file since this patch messes up git blame anyways * Change typedef to using * Add the new type ChildrenGetterTy, and store an instance of it in IDFCalculatorBase. This is important because I'll have to specialize it for Clang's CFG to filter out nullpointer successors, similarly to D62507. Differential Revision: https://reviews.llvm.org/D63389 llvm-svn: 364911 --- .../llvm/Analysis/IteratedDominanceFrontier.h | 151 +++++++-------- .../Support/GenericIteratedDominanceFrontier.h | 210 +++++++++++++++++++++ llvm/lib/Analysis/CMakeLists.txt | 1 - llvm/lib/Analysis/IteratedDominanceFrontier.cpp | 104 ---------- 4 files changed, 282 insertions(+), 184 deletions(-) create mode 100644 llvm/include/llvm/Support/GenericIteratedDominanceFrontier.h delete mode 100644 llvm/lib/Analysis/IteratedDominanceFrontier.cpp diff --git a/llvm/include/llvm/Analysis/IteratedDominanceFrontier.h b/llvm/include/llvm/Analysis/IteratedDominanceFrontier.h index e7d19d1..90e096f 100644 --- a/llvm/include/llvm/Analysis/IteratedDominanceFrontier.h +++ b/llvm/include/llvm/Analysis/IteratedDominanceFrontier.h @@ -5,96 +5,89 @@ // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// -/// \file -/// Compute iterated dominance frontiers using a linear time algorithm. -/// -/// The algorithm used here is based on: -/// -/// Sreedhar and Gao. A linear time algorithm for placing phi-nodes. -/// In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of -/// Programming Languages -/// POPL '95. ACM, New York, NY, 62-73. -/// -/// It has been modified to not explicitly use the DJ graph data structure and -/// to directly compute pruned SSA using per-variable liveness information. -// -//===----------------------------------------------------------------------===// #ifndef LLVM_ANALYSIS_IDF_H #define LLVM_ANALYSIS_IDF_H -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFGDiff.h" -#include "llvm/IR/Dominators.h" +#include "llvm/Support/GenericIteratedDominanceFrontier.h" namespace llvm { -/// Determine the iterated dominance frontier, given a set of defining -/// blocks, and optionally, a set of live-in blocks. -/// -/// In turn, the results can be used to place phi nodes. -/// -/// This algorithm is a linear time computation of Iterated Dominance Frontiers, -/// pruned using the live-in set. -/// By default, liveness is not used to prune the IDF computation. -/// The template parameters should be either BasicBlock* or Inverse, depending on if you want the forward or reverse IDF. -template -class IDFCalculator { - public: - IDFCalculator(DominatorTreeBase &DT) - : DT(DT), GD(nullptr), useLiveIn(false) {} - - IDFCalculator(DominatorTreeBase &DT, - const GraphDiff *GD) - : DT(DT), GD(GD), useLiveIn(false) {} - - /// Give the IDF calculator the set of blocks in which the value is - /// defined. This is equivalent to the set of starting blocks it should be - /// calculating the IDF for (though later gets pruned based on liveness). - /// - /// Note: This set *must* live for the entire lifetime of the IDF calculator. - void setDefiningBlocks(const SmallPtrSetImpl &Blocks) { - DefBlocks = &Blocks; - } - - /// Give the IDF calculator the set of blocks in which the value is - /// live on entry to the block. This is used to prune the IDF calculation to - /// not include blocks where any phi insertion would be dead. - /// - /// Note: This set *must* live for the entire lifetime of the IDF calculator. - - void setLiveInBlocks(const SmallPtrSetImpl &Blocks) { - LiveInBlocks = &Blocks; - useLiveIn = true; - } +class BasicBlock; + +namespace IDFCalculatorDetail { - /// Reset the live-in block set to be empty, and tell the IDF - /// calculator to not use liveness anymore. - void resetLiveInBlocks() { - LiveInBlocks = nullptr; - useLiveIn = false; +/// Specialization for BasicBlock for the optional use of GraphDiff. +template struct ChildrenGetterTy { + using NodeRef = BasicBlock *; + using ChildrenTy = SmallVector; + + ChildrenGetterTy() = default; + ChildrenGetterTy(const GraphDiff *GD) : GD(GD) { + assert(GD); } - /// Calculate iterated dominance frontiers - /// - /// This uses the linear-time phi algorithm based on DJ-graphs mentioned in - /// the file-level comment. It performs DF->IDF pruning using the live-in - /// set, to avoid computing the IDF for blocks where an inserted PHI node - /// would be dead. - void calculate(SmallVectorImpl &IDFBlocks); - -private: - DominatorTreeBase &DT; - const GraphDiff *GD; - bool useLiveIn; - const SmallPtrSetImpl *LiveInBlocks; - const SmallPtrSetImpl *DefBlocks; + ChildrenTy get(const NodeRef &N); + + const GraphDiff *GD = nullptr; +}; + +} // end of namespace IDFCalculatorDetail + +template +class IDFCalculator final : public IDFCalculatorBase { +public: + using IDFCalculatorBase = + typename llvm::IDFCalculatorBase; + using ChildrenGetterTy = typename IDFCalculatorBase::ChildrenGetterTy; + + IDFCalculator(DominatorTreeBase &DT) + : IDFCalculatorBase(DT) {} + + IDFCalculator(DominatorTreeBase &DT, + const GraphDiff *GD) + : IDFCalculatorBase(DT, ChildrenGetterTy(GD)) { + assert(GD); + } }; -typedef IDFCalculator ForwardIDFCalculator; -typedef IDFCalculator, true> ReverseIDFCalculator; + +using ForwardIDFCalculator = IDFCalculator; +using ReverseIDFCalculator = IDFCalculator; + +//===----------------------------------------------------------------------===// +// Implementation. +//===----------------------------------------------------------------------===// + +namespace IDFCalculatorDetail { + +template +using BBChildrenGetterTy = ChildrenGetterTy; + +template +typename BBChildrenGetterTy::ChildrenTy +BBChildrenGetterTy::get( + const BBChildrenGetterTy::NodeRef &N) { + + using OrderedNodeTy = + typename IDFCalculatorBase::OrderedNodeTy; + + if (!GD) { + auto Children = children(N); + return {Children.begin(), Children.end()}; + } + + using SnapShotBBPairTy = + std::pair *, OrderedNodeTy>; + + ChildrenTy Ret; + for (const auto &SnapShotBBPair : children({GD, N})) + Ret.emplace_back(SnapShotBBPair.second); + return Ret; } + +} // end of namespace IDFCalculatorDetail + +} // end of namespace llvm + #endif diff --git a/llvm/include/llvm/Support/GenericIteratedDominanceFrontier.h b/llvm/include/llvm/Support/GenericIteratedDominanceFrontier.h new file mode 100644 index 0000000..975ebaf --- /dev/null +++ b/llvm/include/llvm/Support/GenericIteratedDominanceFrontier.h @@ -0,0 +1,210 @@ +//===- IteratedDominanceFrontier.h - Calculate IDF --------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +/// \file +/// Compute iterated dominance frontiers using a linear time algorithm. +/// +/// The algorithm used here is based on: +/// +/// Sreedhar and Gao. A linear time algorithm for placing phi-nodes. +/// In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of +/// Programming Languages +/// POPL '95. ACM, New York, NY, 62-73. +/// +/// It has been modified to not explicitly use the DJ graph data structure and +/// to directly compute pruned SSA using per-variable liveness information. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_SUPPORT_GENERIC_IDF_H +#define LLVM_SUPPORT_GENERIC_IDF_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/GenericDomTree.h" +#include + +namespace llvm { + +namespace IDFCalculatorDetail { + +/// Generic utility class used for getting the children of a basic block. +/// May be specialized if, for example, one wouldn't like to return nullpointer +/// successors. +template struct ChildrenGetterTy { + using NodeRef = typename GraphTraits::NodeRef; + using ChildrenTy = SmallVector; + + ChildrenTy get(const NodeRef &N); +}; + +} // end of namespace IDFCalculatorDetail + +/// Determine the iterated dominance frontier, given a set of defining +/// blocks, and optionally, a set of live-in blocks. +/// +/// In turn, the results can be used to place phi nodes. +/// +/// This algorithm is a linear time computation of Iterated Dominance Frontiers, +/// pruned using the live-in set. +/// By default, liveness is not used to prune the IDF computation. +/// The template parameters should be of a CFG block type. +template class IDFCalculatorBase { +public: + using OrderedNodeTy = + typename std::conditional, NodeTy *>::type; + using ChildrenGetterTy = + IDFCalculatorDetail::ChildrenGetterTy; + + IDFCalculatorBase(DominatorTreeBase &DT) : DT(DT) {} + + IDFCalculatorBase(DominatorTreeBase &DT, + const ChildrenGetterTy &C) + : DT(DT), ChildrenGetter(C) {} + + /// Give the IDF calculator the set of blocks in which the value is + /// defined. This is equivalent to the set of starting blocks it should be + /// calculating the IDF for (though later gets pruned based on liveness). + /// + /// Note: This set *must* live for the entire lifetime of the IDF calculator. + void setDefiningBlocks(const SmallPtrSetImpl &Blocks) { + DefBlocks = &Blocks; + } + + /// Give the IDF calculator the set of blocks in which the value is + /// live on entry to the block. This is used to prune the IDF calculation to + /// not include blocks where any phi insertion would be dead. + /// + /// Note: This set *must* live for the entire lifetime of the IDF calculator. + void setLiveInBlocks(const SmallPtrSetImpl &Blocks) { + LiveInBlocks = &Blocks; + useLiveIn = true; + } + + /// Reset the live-in block set to be empty, and tell the IDF + /// calculator to not use liveness anymore. + void resetLiveInBlocks() { + LiveInBlocks = nullptr; + useLiveIn = false; + } + + /// Calculate iterated dominance frontiers + /// + /// This uses the linear-time phi algorithm based on DJ-graphs mentioned in + /// the file-level comment. It performs DF->IDF pruning using the live-in + /// set, to avoid computing the IDF for blocks where an inserted PHI node + /// would be dead. + void calculate(SmallVectorImpl &IDFBlocks); + +private: + DominatorTreeBase &DT; + ChildrenGetterTy ChildrenGetter; + bool useLiveIn = false; + const SmallPtrSetImpl *LiveInBlocks; + const SmallPtrSetImpl *DefBlocks; +}; + +//===----------------------------------------------------------------------===// +// Implementation. +//===----------------------------------------------------------------------===// + +namespace IDFCalculatorDetail { + +template +typename ChildrenGetterTy::ChildrenTy +ChildrenGetterTy::get( + const ChildrenGetterTy::NodeRef &N) { + using OrderedNodeTy = + typename IDFCalculatorBase::OrderedNodeTy; + + auto Children = children(N); + return {Children.begin(), Children.end()}; +}; + +} // end of namespace IDFCalculatorDetail + +template +void IDFCalculatorBase::calculate( + SmallVectorImpl &PHIBlocks) { + // Use a priority queue keyed on dominator tree level so that inserted nodes + // are handled from the bottom of the dominator tree upwards. We also augment + // the level with a DFS number to ensure that the blocks are ordered in a + // deterministic way. + using DomTreeNodePair = + std::pair *, std::pair>; + using IDFPriorityQueue = + std::priority_queue, + less_second>; + + IDFPriorityQueue PQ; + + DT.updateDFSNumbers(); + + for (NodeTy *BB : *DefBlocks) { + if (DomTreeNodeBase *Node = DT.getNode(BB)) + PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())}); + } + + SmallVector *, 32> Worklist; + SmallPtrSet *, 32> VisitedPQ; + SmallPtrSet *, 32> VisitedWorklist; + + while (!PQ.empty()) { + DomTreeNodePair RootPair = PQ.top(); + PQ.pop(); + DomTreeNodeBase *Root = RootPair.first; + unsigned RootLevel = RootPair.second.first; + + // Walk all dominator tree children of Root, inspecting their CFG edges with + // targets elsewhere on the dominator tree. Only targets whose level is at + // most Root's level are added to the iterated dominance frontier of the + // definition set. + + Worklist.clear(); + Worklist.push_back(Root); + VisitedWorklist.insert(Root); + + while (!Worklist.empty()) { + DomTreeNodeBase *Node = Worklist.pop_back_val(); + NodeTy *BB = Node->getBlock(); + // Succ is the successor in the direction we are calculating IDF, so it is + // successor for IDF, and predecessor for Reverse IDF. + auto DoWork = [&](NodeTy *Succ) { + DomTreeNodeBase *SuccNode = DT.getNode(Succ); + + const unsigned SuccLevel = SuccNode->getLevel(); + if (SuccLevel > RootLevel) + return; + + if (!VisitedPQ.insert(SuccNode).second) + return; + + NodeTy *SuccBB = SuccNode->getBlock(); + if (useLiveIn && !LiveInBlocks->count(SuccBB)) + return; + + PHIBlocks.emplace_back(SuccBB); + if (!DefBlocks->count(SuccBB)) + PQ.push(std::make_pair( + SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn()))); + }; + + for (auto Succ : ChildrenGetter.get(BB)) + DoWork(Succ); + + for (auto DomChild : *Node) { + if (VisitedWorklist.insert(DomChild).second) + Worklist.push_back(DomChild); + } + } + } +} + +} // end of namespace llvm + +#endif diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt index 3cc9fe3..dd5d625 100644 --- a/llvm/lib/Analysis/CMakeLists.txt +++ b/llvm/lib/Analysis/CMakeLists.txt @@ -41,7 +41,6 @@ add_llvm_library(LLVMAnalysis InstructionSimplify.cpp Interval.cpp IntervalPartition.cpp - IteratedDominanceFrontier.cpp LazyBranchProbabilityInfo.cpp LazyBlockFrequencyInfo.cpp LazyCallGraph.cpp diff --git a/llvm/lib/Analysis/IteratedDominanceFrontier.cpp b/llvm/lib/Analysis/IteratedDominanceFrontier.cpp deleted file mode 100644 index 8925712..0000000 --- a/llvm/lib/Analysis/IteratedDominanceFrontier.cpp +++ /dev/null @@ -1,104 +0,0 @@ -//===- IteratedDominanceFrontier.cpp - Compute IDF ------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -// -// Compute iterated dominance frontiers using a linear time algorithm. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/IteratedDominanceFrontier.h" -#include "llvm/IR/CFG.h" -#include "llvm/IR/Dominators.h" -#include - -namespace llvm { - -template -void IDFCalculator::calculate( - SmallVectorImpl &PHIBlocks) { - // Use a priority queue keyed on dominator tree level so that inserted nodes - // are handled from the bottom of the dominator tree upwards. We also augment - // the level with a DFS number to ensure that the blocks are ordered in a - // deterministic way. - typedef std::pair> - DomTreeNodePair; - typedef std::priority_queue, - less_second> IDFPriorityQueue; - IDFPriorityQueue PQ; - - DT.updateDFSNumbers(); - - for (BasicBlock *BB : *DefBlocks) { - if (DomTreeNode *Node = DT.getNode(BB)) - PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())}); - } - - SmallVector Worklist; - SmallPtrSet VisitedPQ; - SmallPtrSet VisitedWorklist; - - while (!PQ.empty()) { - DomTreeNodePair RootPair = PQ.top(); - PQ.pop(); - DomTreeNode *Root = RootPair.first; - unsigned RootLevel = RootPair.second.first; - - // Walk all dominator tree children of Root, inspecting their CFG edges with - // targets elsewhere on the dominator tree. Only targets whose level is at - // most Root's level are added to the iterated dominance frontier of the - // definition set. - - Worklist.clear(); - Worklist.push_back(Root); - VisitedWorklist.insert(Root); - - while (!Worklist.empty()) { - DomTreeNode *Node = Worklist.pop_back_val(); - BasicBlock *BB = Node->getBlock(); - // Succ is the successor in the direction we are calculating IDF, so it is - // successor for IDF, and predecessor for Reverse IDF. - auto DoWork = [&](BasicBlock *Succ) { - DomTreeNode *SuccNode = DT.getNode(Succ); - - const unsigned SuccLevel = SuccNode->getLevel(); - if (SuccLevel > RootLevel) - return; - - if (!VisitedPQ.insert(SuccNode).second) - return; - - BasicBlock *SuccBB = SuccNode->getBlock(); - if (useLiveIn && !LiveInBlocks->count(SuccBB)) - return; - - PHIBlocks.emplace_back(SuccBB); - if (!DefBlocks->count(SuccBB)) - PQ.push(std::make_pair( - SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn()))); - }; - - if (GD) { - for (auto Pair : children< - std::pair *, NodeTy>>( - {GD, BB})) - DoWork(Pair.second); - } else { - for (auto *Succ : children(BB)) - DoWork(Succ); - } - - for (auto DomChild : *Node) { - if (VisitedWorklist.insert(DomChild).second) - Worklist.push_back(DomChild); - } - } - } -} - -template class IDFCalculator; -template class IDFCalculator, true>; -} -- 2.7.4