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