1 //===-- Analysis/CFG.h - BasicBlock Analyses --------------------*- 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 family of functions performs analyses on basic blocks, and instructions 10 // contained within basic blocks. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_ANALYSIS_CFG_H 15 #define LLVM_ANALYSIS_CFG_H 16 17 #include "llvm/ADT/GraphTraits.h" 18 #include "llvm/ADT/SmallPtrSet.h" 19 #include <utility> 20 21 namespace llvm { 22 23 class BasicBlock; 24 class DominatorTree; 25 class Function; 26 class Instruction; 27 class LoopInfo; 28 template <typename T> class SmallVectorImpl; 29 30 /// Analyze the specified function to find all of the loop backedges in the 31 /// function and return them. This is a relatively cheap (compared to 32 /// computing dominators and loop info) analysis. 33 /// 34 /// The output is added to Result, as pairs of <from,to> edge info. 35 void FindFunctionBackedges( 36 const Function &F, 37 SmallVectorImpl<std::pair<const BasicBlock *, const BasicBlock *> > & 38 Result); 39 40 /// Search for the specified successor of basic block BB and return its position 41 /// in the terminator instruction's list of successors. It is an error to call 42 /// this with a block that is not a successor. 43 unsigned GetSuccessorNumber(const BasicBlock *BB, const BasicBlock *Succ); 44 45 /// Return true if the specified edge is a critical edge. Critical edges are 46 /// edges from a block with multiple successors to a block with multiple 47 /// predecessors. 48 /// 49 bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, 50 bool AllowIdenticalEdges = false); 51 bool isCriticalEdge(const Instruction *TI, const BasicBlock *Succ, 52 bool AllowIdenticalEdges = false); 53 54 /// Determine whether instruction 'To' is reachable from 'From', without passing 55 /// through any blocks in ExclusionSet, returning true if uncertain. 56 /// 57 /// Determine whether there is a path from From to To within a single function. 58 /// Returns false only if we can prove that once 'From' has been executed then 59 /// 'To' can not be executed. Conservatively returns true. 60 /// 61 /// This function is linear with respect to the number of blocks in the CFG, 62 /// walking down successors from From to reach To, with a fixed threshold. 63 /// Using DT or LI allows us to answer more quickly. LI reduces the cost of 64 /// an entire loop of any number of blocks to be the same as the cost of a 65 /// single block. DT reduces the cost by allowing the search to terminate when 66 /// we find a block that dominates the block containing 'To'. DT is most useful 67 /// on branchy code but not loops, and LI is most useful on code with loops but 68 /// does not help on branchy code outside loops. 69 bool isPotentiallyReachable( 70 const Instruction *From, const Instruction *To, 71 const SmallPtrSetImpl<BasicBlock *> *ExclusionSet = nullptr, 72 const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr); 73 74 /// Determine whether block 'To' is reachable from 'From', returning 75 /// true if uncertain. 76 /// 77 /// Determine whether there is a path from From to To within a single function. 78 /// Returns false only if we can prove that once 'From' has been reached then 79 /// 'To' can not be executed. Conservatively returns true. 80 bool isPotentiallyReachable(const BasicBlock *From, const BasicBlock *To, 81 const DominatorTree *DT = nullptr, 82 const LoopInfo *LI = nullptr); 83 84 /// Determine whether there is at least one path from a block in 85 /// 'Worklist' to 'StopBB', returning true if uncertain. 86 /// 87 /// Determine whether there is a path from at least one block in Worklist to 88 /// StopBB within a single function. Returns false only if we can prove that 89 /// once any block in 'Worklist' has been reached then 'StopBB' can not be 90 /// executed. Conservatively returns true. 91 bool isPotentiallyReachableFromMany(SmallVectorImpl<BasicBlock *> &Worklist, 92 BasicBlock *StopBB, 93 const DominatorTree *DT = nullptr, 94 const LoopInfo *LI = nullptr); 95 96 /// Determine whether there is at least one path from a block in 97 /// 'Worklist' to 'StopBB' without passing through any blocks in 98 /// 'ExclusionSet', returning true if uncertain. 99 /// 100 /// Determine whether there is a path from at least one block in Worklist to 101 /// StopBB within a single function without passing through any of the blocks 102 /// in 'ExclusionSet'. Returns false only if we can prove that once any block 103 /// in 'Worklist' has been reached then 'StopBB' can not be executed. 104 /// Conservatively returns true. 105 bool isPotentiallyReachableFromMany( 106 SmallVectorImpl<BasicBlock *> &Worklist, BasicBlock *StopBB, 107 const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, 108 const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr); 109 110 /// Return true if the control flow in \p RPOTraversal is irreducible. 111 /// 112 /// This is a generic implementation to detect CFG irreducibility based on loop 113 /// info analysis. It can be used for any kind of CFG (Loop, MachineLoop, 114 /// Function, MachineFunction, etc.) by providing an RPO traversal (\p 115 /// RPOTraversal) and the loop info analysis (\p LI) of the CFG. This utility 116 /// function is only recommended when loop info analysis is available. If loop 117 /// info analysis isn't available, please, don't compute it explicitly for this 118 /// purpose. There are more efficient ways to detect CFG irreducibility that 119 /// don't require recomputing loop info analysis (e.g., T1/T2 or Tarjan's 120 /// algorithm). 121 /// 122 /// Requirements: 123 /// 1) GraphTraits must be implemented for NodeT type. It is used to access 124 /// NodeT successors. 125 // 2) \p RPOTraversal must be a valid reverse post-order traversal of the 126 /// target CFG with begin()/end() iterator interfaces. 127 /// 3) \p LI must be a valid LoopInfoBase that contains up-to-date loop 128 /// analysis information of the CFG. 129 /// 130 /// This algorithm uses the information about reducible loop back-edges already 131 /// computed in \p LI. When a back-edge is found during the RPO traversal, the 132 /// algorithm checks whether the back-edge is one of the reducible back-edges in 133 /// loop info. If it isn't, the CFG is irreducible. For example, for the CFG 134 /// below (canonical irreducible graph) loop info won't contain any loop, so the 135 /// algorithm will return that the CFG is irreducible when checking the B <- 136 /// -> C back-edge. 137 /// 138 /// (A->B, A->C, B->C, C->B, C->D) 139 /// A 140 /// / \ 141 /// B<- ->C 142 /// | 143 /// D 144 /// 145 template <class NodeT, class RPOTraversalT, class LoopInfoT, 146 class GT = GraphTraits<NodeT>> 147 bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI) { 148 /// Check whether the edge (\p Src, \p Dst) is a reducible loop backedge 149 /// according to LI. I.e., check if there exists a loop that contains Src and 150 /// where Dst is the loop header. 151 auto isProperBackedge = [&](NodeT Src, NodeT Dst) { 152 for (const auto *Lp = LI.getLoopFor(Src); Lp; Lp = Lp->getParentLoop()) { 153 if (Lp->getHeader() == Dst) 154 return true; 155 } 156 return false; 157 }; 158 159 SmallPtrSet<NodeT, 32> Visited; 160 for (NodeT Node : RPOTraversal) { 161 Visited.insert(Node); 162 for (NodeT Succ : make_range(GT::child_begin(Node), GT::child_end(Node))) { 163 // Succ hasn't been visited yet 164 if (!Visited.count(Succ)) 165 continue; 166 // We already visited Succ, thus Node->Succ must be a backedge. Check that 167 // the head matches what we have in the loop information. Otherwise, we 168 // have an irreducible graph. 169 if (!isProperBackedge(Node, Succ)) 170 return true; 171 } 172 } 173 174 return false; 175 } 176 } // End llvm namespace 177 178 #endif 179