LLVM  14.0.0git
Interval.h
Go to the documentation of this file.
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  inline Interval(BasicBlock *Header) : HeaderNode(Header) {
48  Nodes.push_back(Header);
49  }
50 
51  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  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 {
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 ///
100  return I->Successors.begin();
101 }
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 ///
110  return I->Predecessors.begin();
111 }
113  return I->Predecessors.end();
114 }
115 
116 template <> struct GraphTraits<Interval*> {
117  using NodeRef = Interval *;
119 
120  static NodeRef getEntryNode(Interval *I) { return I; }
121 
122  /// nodes_iterator/begin/end - Allow iteration over all nodes in the graph
125 };
126 
127 template <> struct GraphTraits<Inverse<Interval*>> {
128  using NodeRef = Interval *;
130 
131  static NodeRef getEntryNode(Inverse<Interval *> G) { return G.Graph; }
134 };
135 
136 } // end namespace llvm
137 
138 #endif // LLVM_ANALYSIS_INTERVAL_H
llvm::GraphTraits< Inverse< Interval * > >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: Interval.h:132
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::Interval::contains
bool contains(BasicBlock *BB) const
contains - Find out if a basic block is in this interval
Definition: Interval.h:66
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
llvm::Interval::print
void print(raw_ostream &O) const
print - Show contents in human readable format...
Definition: Interval.cpp:25
llvm::Interval::getHeaderNode
BasicBlock * getHeaderNode() const
Definition: Interval.h:51
llvm::Interval::Interval
Interval(BasicBlock *Header)
Definition: Interval.h:47
llvm::GraphTraits< Interval * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: Interval.h:124
llvm::GraphTraits< Inverse< Interval * > >::getEntryNode
static NodeRef getEntryNode(Inverse< Interval * > G)
Definition: Interval.h:131
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
GraphTraits.h
llvm::GraphTraits< Interval * >::getEntryNode
static NodeRef getEntryNode(Interval *I)
Definition: Interval.h:120
llvm::Interval::operator==
bool operator==(const Interval &I) const
Equality operator.
Definition: Interval.h:88
llvm::GraphTraits< Inverse< Interval * > >::ChildIteratorType
Interval::pred_iterator ChildIteratorType
Definition: Interval.h:129
llvm::Interval::pred_iterator
std::vector< BasicBlock * >::iterator pred_iterator
Definition: Interval.h:44
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::GraphTraits< Interval * >::ChildIteratorType
Interval::succ_iterator ChildIteratorType
Definition: Interval.h:118
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
llvm::Interval::node_iterator
std::vector< BasicBlock * >::iterator node_iterator
Definition: Interval.h:45
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:197
llvm::Interval::Successors
std::vector< BasicBlock * > Successors
Successors - List of BasicBlocks that are reachable directly from nodes in this interval,...
Definition: Interval.h:59
llvm::Interval::isSuccessor
bool isSuccessor(BasicBlock *BB) const
isSuccessor - find out if a basic block is a successor of this Interval
Definition: Interval.h:76
llvm::Interval
Interval Class - An Interval is a set of nodes defined such that every node in the interval has all o...
Definition: Interval.h:36
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::succ_begin
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::Interval::Nodes
std::vector< BasicBlock * > Nodes
Nodes - The basic blocks in this interval.
Definition: Interval.h:54
Node
Definition: ItaniumDemangle.h:235
llvm::GraphTraits< Interval * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
nodes_iterator/begin/end - Allow iteration over all nodes in the graph
Definition: Interval.h:123
llvm::GraphTraits< Inverse< Interval * > >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: Interval.h:133
llvm::Successor
@ Successor
Definition: SIMachineScheduler.h:35
llvm::pred_end
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
llvm::Interval::succ_iterator
std::vector< BasicBlock * >::iterator succ_iterator
Definition: Interval.h:43
llvm::Inverse
Definition: GraphTraits.h:95
llvm::pred_begin
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:109
N
#define N
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::GraphTraits
Definition: GraphTraits.h:35
llvm::Interval::Predecessors
std::vector< BasicBlock * > Predecessors
Predecessors - List of BasicBlocks that have this Interval's header block as one of their successors.
Definition: Interval.h:63