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 *; |
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 | inline Interval(BasicBlock *) : HeaderNode(Header) { |
48 | Nodes.push_back(x: Header); |
49 | } |
50 | |
51 | inline BasicBlock *() 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 | inline bool contains(BasicBlock *BB) const { |
67 | for (BasicBlock *Node : Nodes) |
68 | if (Node == BB) |
69 | return true; |
70 | return false; |
71 | // I don't want the dependency on <algorithm> |
72 | //return find(Nodes.begin(), Nodes.end(), BB) != Nodes.end(); |
73 | } |
74 | |
75 | /// isSuccessor - find out if a basic block is a successor of this Interval |
76 | inline bool isSuccessor(BasicBlock *BB) const { |
77 | for (BasicBlock *Successor : Successors) |
78 | if (Successor == BB) |
79 | return true; |
80 | return false; |
81 | // I don't want the dependency on <algorithm> |
82 | //return find(Successors.begin(), Successors.end(), BB) != Successors.end(); |
83 | } |
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 | inline bool operator==(const Interval &I) const { |
89 | return HeaderNode == I.HeaderNode; |
90 | } |
91 | |
92 | /// print - Show contents in human readable format... |
93 | void print(raw_ostream &O) const; |
94 | }; |
95 | |
96 | /// succ_begin/succ_end - define methods so that Intervals may be used |
97 | /// just like BasicBlocks can with the succ_* functions, and *::succ_iterator. |
98 | /// |
99 | inline Interval::succ_iterator succ_begin(Interval *I) { |
100 | return I->Successors.begin(); |
101 | } |
102 | inline Interval::succ_iterator succ_end(Interval *I) { |
103 | return I->Successors.end(); |
104 | } |
105 | |
106 | /// pred_begin/pred_end - define methods so that Intervals may be used |
107 | /// just like BasicBlocks can with the pred_* functions, and *::pred_iterator. |
108 | /// |
109 | inline Interval::pred_iterator pred_begin(Interval *I) { |
110 | return I->Predecessors.begin(); |
111 | } |
112 | inline Interval::pred_iterator pred_end(Interval *I) { |
113 | return I->Predecessors.end(); |
114 | } |
115 | |
116 | template <> struct GraphTraits<Interval*> { |
117 | using NodeRef = Interval *; |
118 | using ChildIteratorType = Interval::succ_iterator; |
119 | |
120 | static NodeRef getEntryNode(Interval *I) { return I; } |
121 | |
122 | /// nodes_iterator/begin/end - Allow iteration over all nodes in the graph |
123 | static ChildIteratorType child_begin(NodeRef N) { return succ_begin(I: N); } |
124 | static ChildIteratorType child_end(NodeRef N) { return succ_end(I: N); } |
125 | }; |
126 | |
127 | template <> struct GraphTraits<Inverse<Interval*>> { |
128 | using NodeRef = Interval *; |
129 | using ChildIteratorType = Interval::pred_iterator; |
130 | |
131 | static NodeRef getEntryNode(Inverse<Interval *> G) { return G.Graph; } |
132 | static ChildIteratorType child_begin(NodeRef N) { return pred_begin(I: N); } |
133 | static ChildIteratorType child_end(NodeRef N) { return pred_end(I: N); } |
134 | }; |
135 | |
136 | } // end namespace llvm |
137 | |
138 | #endif // LLVM_ANALYSIS_INTERVAL_H |
139 | |