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 25namespace llvm { 26 27class BasicBlock; 28class 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/// 36class 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 42public: 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 { 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/// 99inline Interval::succ_iterator succ_begin(Interval *I) { 100 return I->Successors.begin(); 101} 102inline 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/// 109inline Interval::pred_iterator pred_begin(Interval *I) { 110 return I->Predecessors.begin(); 111} 112inline Interval::pred_iterator pred_end(Interval *I) { 113 return I->Predecessors.end(); 114} 115 116template <> 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(N); } 124 static ChildIteratorType child_end(NodeRef N) { return succ_end(N); } 125}; 126 127template <> 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(N); } 133 static ChildIteratorType child_end(NodeRef N) { return pred_end(N); } 134}; 135 136} // end namespace llvm 137 138#endif // LLVM_ANALYSIS_INTERVAL_H 139