Coverage Report

Created: 2019-07-24 05:18

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