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