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 21namespace llvm { 22 23class BasicBlock; 24class DominatorTree; 25class Function; 26class Instruction; 27class LoopInfo; 28template <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. 35void 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. 43unsigned 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/// 49bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, 50 bool AllowIdenticalEdges = false); 51bool 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. 69bool 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. 80bool isPotentiallyReachable( 81 const BasicBlock *From, const BasicBlock *To, 82 const SmallPtrSetImpl<BasicBlock *> *ExclusionSet = nullptr, 83 const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr); 84 85/// Determine whether there is at least one path from a block in 86/// 'Worklist' to 'StopBB' without passing through any blocks in 87/// 'ExclusionSet', returning true if uncertain. 88/// 89/// Determine whether there is a path from at least one block in Worklist to 90/// StopBB within a single function without passing through any of the blocks 91/// in 'ExclusionSet'. Returns false only if we can prove that once any block 92/// in 'Worklist' has been reached then 'StopBB' can not be executed. 93/// Conservatively returns true. 94bool isPotentiallyReachableFromMany( 95 SmallVectorImpl<BasicBlock *> &Worklist, const BasicBlock *StopBB, 96 const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, 97 const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr); 98 99/// Return true if the control flow in \p RPOTraversal is irreducible. 100/// 101/// This is a generic implementation to detect CFG irreducibility based on loop 102/// info analysis. It can be used for any kind of CFG (Loop, MachineLoop, 103/// Function, MachineFunction, etc.) by providing an RPO traversal (\p 104/// RPOTraversal) and the loop info analysis (\p LI) of the CFG. This utility 105/// function is only recommended when loop info analysis is available. If loop 106/// info analysis isn't available, please, don't compute it explicitly for this 107/// purpose. There are more efficient ways to detect CFG irreducibility that 108/// don't require recomputing loop info analysis (e.g., T1/T2 or Tarjan's 109/// algorithm). 110/// 111/// Requirements: 112/// 1) GraphTraits must be implemented for NodeT type. It is used to access 113/// NodeT successors. 114// 2) \p RPOTraversal must be a valid reverse post-order traversal of the 115/// target CFG with begin()/end() iterator interfaces. 116/// 3) \p LI must be a valid LoopInfoBase that contains up-to-date loop 117/// analysis information of the CFG. 118/// 119/// This algorithm uses the information about reducible loop back-edges already 120/// computed in \p LI. When a back-edge is found during the RPO traversal, the 121/// algorithm checks whether the back-edge is one of the reducible back-edges in 122/// loop info. If it isn't, the CFG is irreducible. For example, for the CFG 123/// below (canonical irreducible graph) loop info won't contain any loop, so the 124/// algorithm will return that the CFG is irreducible when checking the B <- 125/// -> C back-edge. 126/// 127/// (A->B, A->C, B->C, C->B, C->D) 128/// A 129/// / \ 130/// B<- ->C 131/// | 132/// D 133/// 134template <class NodeT, class RPOTraversalT, class LoopInfoT, 135 class GT = GraphTraits<NodeT>> 136bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI) { 137 /// Check whether the edge (\p Src, \p Dst) is a reducible loop backedge 138 /// according to LI. I.e., check if there exists a loop that contains Src and 139 /// where Dst is the loop header. 140 auto isProperBackedge = [&](NodeT Src, NodeT Dst) { 141 for (const auto *Lp = LI.getLoopFor(Src); Lp; Lp = Lp->getParentLoop()) { 142 if (Lp->getHeader() == Dst) 143 return true; 144 } 145 return false; 146 }; 147 148 SmallPtrSet<NodeT, 32> Visited; 149 for (NodeT Node : RPOTraversal) { 150 Visited.insert(Node); 151 for (NodeT Succ : make_range(GT::child_begin(Node), GT::child_end(Node))) { 152 // Succ hasn't been visited yet 153 if (!Visited.count(Succ)) 154 continue; 155 // We already visited Succ, thus Node->Succ must be a backedge. Check that 156 // the head matches what we have in the loop information. Otherwise, we 157 // have an irreducible graph. 158 if (!isProperBackedge(Node, Succ)) 159 return true; 160 } 161 } 162 163 return false; 164} 165} // End llvm namespace 166 167#endif 168