Coverage Report

Created: 2018-09-19 20:53

/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
//                     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
class TerminatorInst;
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 TerminatorInst *TI, unsigned SuccNum,
50
                    bool AllowIdenticalEdges = false);
51
52
/// Determine whether instruction 'To' is reachable from 'From',
53
/// returning true if uncertain.
54
///
55
/// Determine whether there is a path from From to To within a single function.
56
/// Returns false only if we can prove that once 'From' has been executed then
57
/// 'To' can not be executed. Conservatively returns true.
58
///
59
/// This function is linear with respect to the number of blocks in the CFG,
60
/// walking down successors from From to reach To, with a fixed threshold.
61
/// Using DT or LI allows us to answer more quickly. LI reduces the cost of
62
/// an entire loop of any number of blocks to be the same as the cost of a
63
/// single block. DT reduces the cost by allowing the search to terminate when
64
/// we find a block that dominates the block containing 'To'. DT is most useful
65
/// on branchy code but not loops, and LI is most useful on code with loops but
66
/// does not help on branchy code outside loops.
67
bool isPotentiallyReachable(const Instruction *From, const Instruction *To,
68
                            const DominatorTree *DT = nullptr,
69
                            const LoopInfo *LI = nullptr);
70
71
/// Determine whether block 'To' is reachable from 'From', returning
72
/// true if uncertain.
73
///
74
/// Determine whether there is a path from From to To within a single function.
75
/// Returns false only if we can prove that once 'From' has been reached then
76
/// 'To' can not be executed. Conservatively returns true.
77
bool isPotentiallyReachable(const BasicBlock *From, const BasicBlock *To,
78
                            const DominatorTree *DT = nullptr,
79
                            const LoopInfo *LI = nullptr);
80
81
/// Determine whether there is at least one path from a block in
82
/// 'Worklist' to 'StopBB', returning true if uncertain.
83
///
84
/// Determine whether there is a path from at least one block in Worklist to
85
/// StopBB within a single function. Returns false only if we can prove that
86
/// once any block in 'Worklist' has been reached then 'StopBB' can not be
87
/// executed. Conservatively returns true.
88
bool isPotentiallyReachableFromMany(SmallVectorImpl<BasicBlock *> &Worklist,
89
                                    BasicBlock *StopBB,
90
                                    const DominatorTree *DT = nullptr,
91
                                    const LoopInfo *LI = nullptr);
92
93
/// Return true if the control flow in \p RPOTraversal is irreducible.
94
///
95
/// This is a generic implementation to detect CFG irreducibility based on loop
96
/// info analysis. It can be used for any kind of CFG (Loop, MachineLoop,
97
/// Function, MachineFunction, etc.) by providing an RPO traversal (\p
98
/// RPOTraversal) and the loop info analysis (\p LI) of the CFG. This utility
99
/// function is only recommended when loop info analysis is available. If loop
100
/// info analysis isn't available, please, don't compute it explicitly for this
101
/// purpose. There are more efficient ways to detect CFG irreducibility that
102
/// don't require recomputing loop info analysis (e.g., T1/T2 or Tarjan's
103
/// algorithm).
104
///
105
/// Requirements:
106
///   1) GraphTraits must be implemented for NodeT type. It is used to access
107
///      NodeT successors.
108
//    2) \p RPOTraversal must be a valid reverse post-order traversal of the
109
///      target CFG with begin()/end() iterator interfaces.
110
///   3) \p LI must be a valid LoopInfoBase that contains up-to-date loop
111
///      analysis information of the CFG.
112
///
113
/// This algorithm uses the information about reducible loop back-edges already
114
/// computed in \p LI. When a back-edge is found during the RPO traversal, the
115
/// algorithm checks whether the back-edge is one of the reducible back-edges in
116
/// loop info. If it isn't, the CFG is irreducible. For example, for the CFG
117
/// below (canonical irreducible graph) loop info won't contain any loop, so the
118
/// algorithm will return that the CFG is irreducible when checking the B <-
119
/// -> C back-edge.
120
///
121
/// (A->B, A->C, B->C, C->B, C->D)
122
///    A
123
///  /   \
124
/// B<- ->C
125
///       |
126
///       D
127
///
128
template <class NodeT, class RPOTraversalT, class LoopInfoT,
129
          class GT = GraphTraits<NodeT>>
130
419k
bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI) {
131
419k
  /// Check whether the edge (\p Src, \p Dst) is a reducible loop backedge
132
419k
  /// according to LI. I.e., check if there exists a loop that contains Src and
133
419k
  /// where Dst is the loop header.
134
419k
  auto isProperBackedge = [&](NodeT Src, NodeT Dst) {
135
354k
    for (const auto *Lp = LI.getLoopFor(Src); Lp; 
Lp = Lp->getParentLoop()70
) {
136
354k
      if (Lp->getHeader() == Dst)
137
354k
        return true;
138
354k
    }
139
354k
    
return false33
;
140
354k
  };
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
134
145k
  auto isProperBackedge = [&](NodeT Src, NodeT Dst) {
135
145k
    for (const auto *Lp = LI.getLoopFor(Src); Lp; 
Lp = Lp->getParentLoop()1
) {
136
145k
      if (Lp->getHeader() == Dst)
137
145k
        return true;
138
145k
    }
139
145k
    
return false1
;
140
145k
  };
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
134
209k
  auto isProperBackedge = [&](NodeT Src, NodeT Dst) {
135
209k
    for (const auto *Lp = LI.getLoopFor(Src); Lp; 
Lp = Lp->getParentLoop()69
) {
136
209k
      if (Lp->getHeader() == Dst)
137
209k
        return true;
138
209k
    }
139
209k
    
return false32
;
140
209k
  };
141
419k
142
419k
  SmallPtrSet<NodeT, 32> Visited;
143
2.98M
  for (NodeT Node : RPOTraversal) {
144
2.98M
    Visited.insert(Node);
145
4.13M
    for (NodeT Succ : make_range(GT::child_begin(Node), GT::child_end(Node))) {
146
4.13M
      // Succ hasn't been visited yet
147
4.13M
      if (!Visited.count(Succ))
148
3.77M
        continue;
149
354k
      // We already visited Succ, thus Node->Succ must be a backedge. Check that
150
354k
      // the head matches what we have in the loop information. Otherwise, we
151
354k
      // have an irreducible graph.
152
354k
      if (!isProperBackedge(Node, Succ))
153
33
        return true;
154
354k
    }
155
2.98M
  }
156
419k
157
419k
  
return false419k
;
158
419k
}
bool llvm::containsIrreducibleCFG<llvm::BasicBlock const*, llvm::LoopBlocksRPO, llvm::LoopInfo, llvm::GraphTraits<llvm::BasicBlock const*> >(llvm::LoopBlocksRPO&, llvm::LoopInfo const&)
Line
Count
Source
130
145k
bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI) {
131
145k
  /// Check whether the edge (\p Src, \p Dst) is a reducible loop backedge
132
145k
  /// according to LI. I.e., check if there exists a loop that contains Src and
133
145k
  /// where Dst is the loop header.
134
145k
  auto isProperBackedge = [&](NodeT Src, NodeT Dst) {
135
145k
    for (const auto *Lp = LI.getLoopFor(Src); Lp; Lp = Lp->getParentLoop()) {
136
145k
      if (Lp->getHeader() == Dst)
137
145k
        return true;
138
145k
    }
139
145k
    return false;
140
145k
  };
141
145k
142
145k
  SmallPtrSet<NodeT, 32> Visited;
143
349k
  for (NodeT Node : RPOTraversal) {
144
349k
    Visited.insert(Node);
145
636k
    for (NodeT Succ : make_range(GT::child_begin(Node), GT::child_end(Node))) {
146
636k
      // Succ hasn't been visited yet
147
636k
      if (!Visited.count(Succ))
148
491k
        continue;
149
145k
      // We already visited Succ, thus Node->Succ must be a backedge. Check that
150
145k
      // the head matches what we have in the loop information. Otherwise, we
151
145k
      // have an irreducible graph.
152
145k
      if (!isProperBackedge(Node, Succ))
153
1
        return true;
154
145k
    }
155
349k
  }
156
145k
157
145k
  
return false145k
;
158
145k
}
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
130
273k
bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI) {
131
273k
  /// Check whether the edge (\p Src, \p Dst) is a reducible loop backedge
132
273k
  /// according to LI. I.e., check if there exists a loop that contains Src and
133
273k
  /// where Dst is the loop header.
134
273k
  auto isProperBackedge = [&](NodeT Src, NodeT Dst) {
135
273k
    for (const auto *Lp = LI.getLoopFor(Src); Lp; Lp = Lp->getParentLoop()) {
136
273k
      if (Lp->getHeader() == Dst)
137
273k
        return true;
138
273k
    }
139
273k
    return false;
140
273k
  };
141
273k
142
273k
  SmallPtrSet<NodeT, 32> Visited;
143
2.63M
  for (NodeT Node : RPOTraversal) {
144
2.63M
    Visited.insert(Node);
145
3.49M
    for (NodeT Succ : make_range(GT::child_begin(Node), GT::child_end(Node))) {
146
3.49M
      // Succ hasn't been visited yet
147
3.49M
      if (!Visited.count(Succ))
148
3.28M
        continue;
149
209k
      // We already visited Succ, thus Node->Succ must be a backedge. Check that
150
209k
      // the head matches what we have in the loop information. Otherwise, we
151
209k
      // have an irreducible graph.
152
209k
      if (!isProperBackedge(Node, Succ))
153
32
        return true;
154
209k
    }
155
2.63M
  }
156
273k
157
273k
  
return false273k
;
158
273k
}
159
} // End llvm namespace
160
161
#endif