1193323Sed//===- llvm/Analysis/Interval.h - Interval Class Declaration ----*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file contains the declaration of the Interval class, which 11193323Sed// represents a set of CFG nodes and is a portion of an interval partition. 12193323Sed// 13193323Sed// Intervals have some interesting and useful properties, including the 14193323Sed// following: 15193323Sed// 1. The header node of an interval dominates all of the elements of the 16193323Sed// interval 17193323Sed// 18193323Sed//===----------------------------------------------------------------------===// 19193323Sed 20249423Sdim#ifndef LLVM_ANALYSIS_INTERVAL_H 21249423Sdim#define LLVM_ANALYSIS_INTERVAL_H 22193323Sed 23193323Sed#include "llvm/ADT/GraphTraits.h" 24193323Sed#include <vector> 25193323Sed 26193323Sednamespace llvm { 27193323Sed 28193323Sedclass BasicBlock; 29198090Srdivackyclass raw_ostream; 30193323Sed 31193323Sed//===----------------------------------------------------------------------===// 32193323Sed// 33193323Sed/// Interval Class - An Interval is a set of nodes defined such that every node 34193323Sed/// in the interval has all of its predecessors in the interval (except for the 35193323Sed/// header) 36193323Sed/// 37193323Sedclass Interval { 38193323Sed /// HeaderNode - The header BasicBlock, which dominates all BasicBlocks in this 39193323Sed /// interval. Also, any loops in this interval must go through the HeaderNode. 40193323Sed /// 41193323Sed BasicBlock *HeaderNode; 42193323Sedpublic: 43193323Sed typedef std::vector<BasicBlock*>::iterator succ_iterator; 44193323Sed typedef std::vector<BasicBlock*>::iterator pred_iterator; 45193323Sed typedef std::vector<BasicBlock*>::iterator node_iterator; 46193323Sed 47193323Sed inline Interval(BasicBlock *Header) : HeaderNode(Header) { 48193323Sed Nodes.push_back(Header); 49193323Sed } 50193323Sed 51193323Sed inline Interval(const Interval &I) // copy ctor 52193323Sed : HeaderNode(I.HeaderNode), Nodes(I.Nodes), Successors(I.Successors) {} 53193323Sed 54193323Sed inline BasicBlock *getHeaderNode() const { return HeaderNode; } 55193323Sed 56193323Sed /// Nodes - The basic blocks in this interval. 57193323Sed /// 58193323Sed std::vector<BasicBlock*> Nodes; 59193323Sed 60193323Sed /// Successors - List of BasicBlocks that are reachable directly from nodes in 61193323Sed /// this interval, but are not in the interval themselves. 62193323Sed /// These nodes necessarily must be header nodes for other intervals. 63193323Sed /// 64193323Sed std::vector<BasicBlock*> Successors; 65193323Sed 66193323Sed /// Predecessors - List of BasicBlocks that have this Interval's header block 67193323Sed /// as one of their successors. 68193323Sed /// 69193323Sed std::vector<BasicBlock*> Predecessors; 70193323Sed 71193323Sed /// contains - Find out if a basic block is in this interval 72193323Sed inline bool contains(BasicBlock *BB) const { 73193323Sed for (unsigned i = 0; i < Nodes.size(); ++i) 74193323Sed if (Nodes[i] == BB) return true; 75193323Sed return false; 76193323Sed // I don't want the dependency on <algorithm> 77193323Sed //return find(Nodes.begin(), Nodes.end(), BB) != Nodes.end(); 78193323Sed } 79193323Sed 80193323Sed /// isSuccessor - find out if a basic block is a successor of this Interval 81193323Sed inline bool isSuccessor(BasicBlock *BB) const { 82193323Sed for (unsigned i = 0; i < Successors.size(); ++i) 83193323Sed if (Successors[i] == BB) return true; 84193323Sed return false; 85193323Sed // I don't want the dependency on <algorithm> 86193323Sed //return find(Successors.begin(), Successors.end(), BB) != Successors.end(); 87193323Sed } 88193323Sed 89193323Sed /// Equality operator. It is only valid to compare two intervals from the 90193323Sed /// same partition, because of this, all we have to check is the header node 91193323Sed /// for equality. 92193323Sed /// 93193323Sed inline bool operator==(const Interval &I) const { 94193323Sed return HeaderNode == I.HeaderNode; 95193323Sed } 96193323Sed 97193323Sed /// isLoop - Find out if there is a back edge in this interval... 98193323Sed bool isLoop() const; 99193323Sed 100193323Sed /// print - Show contents in human readable format... 101198090Srdivacky void print(raw_ostream &O) const; 102193323Sed}; 103193323Sed 104193323Sed/// succ_begin/succ_end - define methods so that Intervals may be used 105193323Sed/// just like BasicBlocks can with the succ_* functions, and *::succ_iterator. 106193323Sed/// 107193323Sedinline Interval::succ_iterator succ_begin(Interval *I) { 108193323Sed return I->Successors.begin(); 109193323Sed} 110193323Sedinline Interval::succ_iterator succ_end(Interval *I) { 111193323Sed return I->Successors.end(); 112193323Sed} 113193323Sed 114193323Sed/// pred_begin/pred_end - define methods so that Intervals may be used 115193323Sed/// just like BasicBlocks can with the pred_* functions, and *::pred_iterator. 116193323Sed/// 117193323Sedinline Interval::pred_iterator pred_begin(Interval *I) { 118193323Sed return I->Predecessors.begin(); 119193323Sed} 120193323Sedinline Interval::pred_iterator pred_end(Interval *I) { 121193323Sed return I->Predecessors.end(); 122193323Sed} 123193323Sed 124193323Sedtemplate <> struct GraphTraits<Interval*> { 125193323Sed typedef Interval NodeType; 126193323Sed typedef Interval::succ_iterator ChildIteratorType; 127193323Sed 128193323Sed static NodeType *getEntryNode(Interval *I) { return I; } 129193323Sed 130193323Sed /// nodes_iterator/begin/end - Allow iteration over all nodes in the graph 131193323Sed static inline ChildIteratorType child_begin(NodeType *N) { 132193323Sed return succ_begin(N); 133193323Sed } 134193323Sed static inline ChildIteratorType child_end(NodeType *N) { 135193323Sed return succ_end(N); 136193323Sed } 137193323Sed}; 138193323Sed 139193323Sedtemplate <> struct GraphTraits<Inverse<Interval*> > { 140193323Sed typedef Interval NodeType; 141193323Sed typedef Interval::pred_iterator ChildIteratorType; 142193323Sed static NodeType *getEntryNode(Inverse<Interval *> G) { return G.Graph; } 143193323Sed static inline ChildIteratorType child_begin(NodeType *N) { 144193323Sed return pred_begin(N); 145193323Sed } 146193323Sed static inline ChildIteratorType child_end(NodeType *N) { 147193323Sed return pred_end(N); 148193323Sed } 149193323Sed}; 150193323Sed 151193323Sed} // End llvm namespace 152193323Sed 153193323Sed#endif 154