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