Coverage Report

Created: 2018-07-20 23:04

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/Interval.h
Line
Count
Source (jump to first uncovered line)
1
//===- llvm/Analysis/Interval.h - Interval Class Declaration ----*- 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 file contains the declaration of the Interval class, which
11
// represents a set of CFG nodes and is a portion of an interval partition.
12
//
13
// Intervals have some interesting and useful properties, including the
14
// following:
15
//    1. The header node of an interval dominates all of the elements of the
16
//       interval
17
//
18
//===----------------------------------------------------------------------===//
19
20
#ifndef LLVM_ANALYSIS_INTERVAL_H
21
#define LLVM_ANALYSIS_INTERVAL_H
22
23
#include "llvm/ADT/GraphTraits.h"
24
#include <vector>
25
26
namespace llvm {
27
28
class BasicBlock;
29
class raw_ostream;
30
31
//===----------------------------------------------------------------------===//
32
//
33
/// Interval Class - An Interval is a set of nodes defined such that every node
34
/// in the interval has all of its predecessors in the interval (except for the
35
/// header)
36
///
37
class Interval {
38
  /// HeaderNode - The header BasicBlock, which dominates all BasicBlocks in this
39
  /// interval.  Also, any loops in this interval must go through the HeaderNode.
40
  ///
41
  BasicBlock *HeaderNode;
42
43
public:
44
  using succ_iterator = std::vector<BasicBlock*>::iterator;
45
  using pred_iterator = std::vector<BasicBlock*>::iterator;
46
  using node_iterator = std::vector<BasicBlock*>::iterator;
47
48
0
  inline Interval(BasicBlock *Header) : HeaderNode(Header) {
49
0
    Nodes.push_back(Header);
50
0
  }
51
52
0
  inline BasicBlock *getHeaderNode() const { return HeaderNode; }
53
54
  /// Nodes - The basic blocks in this interval.
55
  std::vector<BasicBlock*> Nodes;
56
57
  /// Successors - List of BasicBlocks that are reachable directly from nodes in
58
  /// this interval, but are not in the interval themselves.
59
  /// These nodes necessarily must be header nodes for other intervals.
60
  std::vector<BasicBlock*> Successors;
61
62
  /// Predecessors - List of BasicBlocks that have this Interval's header block
63
  /// as one of their successors.
64
  std::vector<BasicBlock*> Predecessors;
65
66
  /// contains - Find out if a basic block is in this interval
67
0
  inline bool contains(BasicBlock *BB) const {
68
0
    for (BasicBlock *Node : Nodes)
69
0
      if (Node == BB)
70
0
        return true;
71
0
    return false;
72
0
    // I don't want the dependency on <algorithm>
73
0
    //return find(Nodes.begin(), Nodes.end(), BB) != Nodes.end();
74
0
  }
75
76
  /// isSuccessor - find out if a basic block is a successor of this Interval
77
0
  inline bool isSuccessor(BasicBlock *BB) const {
78
0
    for (BasicBlock *Successor : Successors)
79
0
      if (Successor == BB)
80
0
        return true;
81
0
    return false;
82
0
    // I don't want the dependency on <algorithm>
83
0
    //return find(Successors.begin(), Successors.end(), BB) != Successors.end();
84
0
  }
85
86
  /// Equality operator.  It is only valid to compare two intervals from the
87
  /// same partition, because of this, all we have to check is the header node
88
  /// for equality.
89
  inline bool operator==(const Interval &I) const {
90
    return HeaderNode == I.HeaderNode;
91
  }
92
93
  /// isLoop - Find out if there is a back edge in this interval...
94
  bool isLoop() const;
95
96
  /// print - Show contents in human readable format...
97
  void print(raw_ostream &O) const;
98
};
99
100
/// succ_begin/succ_end - define methods so that Intervals may be used
101
/// just like BasicBlocks can with the succ_* functions, and *::succ_iterator.
102
///
103
0
inline Interval::succ_iterator succ_begin(Interval *I) {
104
0
  return I->Successors.begin();
105
0
}
106
0
inline Interval::succ_iterator succ_end(Interval *I)   {
107
0
  return I->Successors.end();
108
0
}
109
110
/// pred_begin/pred_end - define methods so that Intervals may be used
111
/// just like BasicBlocks can with the pred_* functions, and *::pred_iterator.
112
///
113
0
inline Interval::pred_iterator pred_begin(Interval *I) {
114
0
  return I->Predecessors.begin();
115
0
}
116
0
inline Interval::pred_iterator pred_end(Interval *I)   {
117
0
  return I->Predecessors.end();
118
0
}
119
120
template <> struct GraphTraits<Interval*> {
121
  using NodeRef = Interval *;
122
  using ChildIteratorType = Interval::succ_iterator;
123
124
  static NodeRef getEntryNode(Interval *I) { return I; }
125
126
  /// nodes_iterator/begin/end - Allow iteration over all nodes in the graph
127
0
  static ChildIteratorType child_begin(NodeRef N) { return succ_begin(N); }
128
0
  static ChildIteratorType child_end(NodeRef N) { return succ_end(N); }
129
};
130
131
template <> struct GraphTraits<Inverse<Interval*>> {
132
  using NodeRef = Interval *;
133
  using ChildIteratorType = Interval::pred_iterator;
134
135
  static NodeRef getEntryNode(Inverse<Interval *> G) { return G.Graph; }
136
0
  static ChildIteratorType child_begin(NodeRef N) { return pred_begin(N); }
137
0
  static ChildIteratorType child_end(NodeRef N) { return pred_end(N); }
138
};
139
140
} // end namespace llvm
141
142
#endif // LLVM_ANALYSIS_INTERVAL_H