X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FInterval.h;h=01eba3f16c014f13e51335cfcfb2c262bfbb9bfe;hb=00552e3875ee5f382db6c98286a241a7d0efe1b8;hp=b16c7a50391c6441303d21a9133c2c0fcb065954;hpb=2100f8cceddcffff65008db79ac036551a0e4846;p=oota-llvm.git diff --git a/include/llvm/Analysis/Interval.h b/include/llvm/Analysis/Interval.h index b16c7a50391..01eba3f16c0 100644 --- a/include/llvm/Analysis/Interval.h +++ b/include/llvm/Analysis/Interval.h @@ -1,193 +1,150 @@ -//===- llvm/Analysis/Intervals.h - Interval partition Calculation-*- C++ -*--=// +//===- llvm/Analysis/Interval.h - Interval Class Declaration ----*- C++ -*-===// // -// This file contains the declaration of the cfg::IntervalPartition class, which -// calculates and represents the interval partition of a method, or a -// preexisting interval partition. +// The LLVM Compiler Infrastructure // -// In this way, the interval partition may be used to reduce a flow graph down -// to its degenerate single node interval partition (unless it is irreducible). +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file contains the declaration of the Interval class, which +// represents a set of CFG nodes and is a portion of an interval partition. +// +// Intervals have some interesting and useful properties, including the +// following: +// 1. The header node of an interval dominates all of the elements of the +// interval // //===----------------------------------------------------------------------===// -#ifndef LLVM_INTERVALS_H -#define LLVM_INTERVALS_H +#ifndef LLVM_ANALYSIS_INTERVAL_H +#define LLVM_ANALYSIS_INTERVAL_H +#include "llvm/ADT/GraphTraits.h" #include -#include -#include - -class Method; -class BasicBlock; -namespace cfg { +namespace llvm { -class IntervalPartition; +class BasicBlock; +class raw_ostream; -// Interval Class - An Interval is a set of nodes defined such that every node -// in the interval has all of its predecessors in the interval (except for the -// header) +//===----------------------------------------------------------------------===// +// +/// Interval Class - An Interval is a set of nodes defined such that every node +/// in the interval has all of its predecessors in the interval (except for the +/// header) +/// class Interval { - friend class IntervalPartition; + /// HeaderNode - The header BasicBlock, which dominates all BasicBlocks in this + /// interval. Also, any loops in this interval must go through the HeaderNode. + /// + BasicBlock *HeaderNode; public: - typedef vector::iterator succ_iterator; - typedef vector::iterator pred_iterator; - typedef vector::iterator node_iterator; + typedef std::vector::iterator succ_iterator; + typedef std::vector::iterator pred_iterator; + typedef std::vector::iterator node_iterator; - // HeaderNode - The header BasicBlock, which dominates all BasicBlocks in this - // interval. Also, any loops in this interval must go through the HeaderNode. - // - BasicBlock *HeaderNode; + inline Interval(BasicBlock *Header) : HeaderNode(Header) { + Nodes.push_back(Header); + } + + inline BasicBlock *getHeaderNode() const { return HeaderNode; } - // Nodes - The basic blocks in this interval. - // - vector Nodes; + /// Nodes - The basic blocks in this interval. + /// + std::vector Nodes; - // Successors - List of BasicBlocks that are reachable directly from nodes in - // this interval, but are not in the interval themselves. - // These nodes neccesarily must be header nodes for other intervals. - // - vector Successors; + /// Successors - List of BasicBlocks that are reachable directly from nodes in + /// this interval, but are not in the interval themselves. + /// These nodes necessarily must be header nodes for other intervals. + /// + std::vector Successors; - // Predecessors - List of BasicBlocks that have this Interval's header block - // as one of their successors. - // - vector Predecessors; + /// Predecessors - List of BasicBlocks that have this Interval's header block + /// as one of their successors. + /// + std::vector Predecessors; - // contains - Find out if a basic block is in this interval + /// contains - Find out if a basic block is in this interval inline bool contains(BasicBlock *BB) const { - return find(Nodes.begin(), Nodes.end(), BB) != Nodes.end(); + for (unsigned i = 0; i < Nodes.size(); ++i) + if (Nodes[i] == BB) return true; + return false; + // I don't want the dependency on + //return find(Nodes.begin(), Nodes.end(), BB) != Nodes.end(); } - // isSuccessor - find out if a basic block is a successor of this Interval + /// isSuccessor - find out if a basic block is a successor of this Interval inline bool isSuccessor(BasicBlock *BB) const { - return find(Successors.begin(), Successors.end(), BB) != Successors.end(); + for (unsigned i = 0; i < Successors.size(); ++i) + if (Successors[i] == BB) return true; + return false; + // I don't want the dependency on + //return find(Successors.begin(), Successors.end(), BB) != Successors.end(); } - // isLoop - Find out if there is a back edge in this interval... + /// Equality operator. It is only valid to compare two intervals from the + /// same partition, because of this, all we have to check is the header node + /// for equality. + /// + inline bool operator==(const Interval &I) const { + return HeaderNode == I.HeaderNode; + } + + /// isLoop - Find out if there is a back edge in this interval... bool isLoop() const; -private: // Only accessable by IntervalPartition class - inline Interval(BasicBlock *Header) : HeaderNode(Header) { - Nodes.push_back(Header); - } + /// print - Show contents in human readable format... + void print(raw_ostream &O) const; }; - -// succ_begin/succ_end - define global functions so that Intervals may be used -// just like BasicBlocks can with the succ_* functions, and *::succ_iterator. -// -inline 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 succ_* functions, and *::succ_iterator. +/// +inline Interval::succ_iterator succ_begin(Interval *I) { return I->Successors.begin(); } -inline Interval::succ_iterator succ_end(Interval *I) { +inline Interval::succ_iterator succ_end(Interval *I) { return I->Successors.end(); } -// pred_begin/pred_end - define global functions so that Intervals may be used -// just like BasicBlocks can with the pred_* functions, and *::pred_iterator. -// -inline 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 pred_* functions, and *::pred_iterator. +/// +inline Interval::pred_iterator pred_begin(Interval *I) { return I->Predecessors.begin(); } -inline Interval::pred_iterator pred_end(Interval *I) { +inline Interval::pred_iterator pred_end(Interval *I) { return I->Predecessors.end(); } +template <> struct GraphTraits { + typedef Interval NodeType; + typedef Interval::succ_iterator ChildIteratorType; + static NodeType *getEntryNode(Interval *I) { return I; } -// IntervalPartition - This class builds and holds an "interval partition" for -// a method. This partition divides the control flow graph into a set of -// maximal intervals, as defined with the properties above. Intuitively, a -// BasicBlock is a (possibly nonexistent) loop with a "tail" of non looping -// nodes following it. -// -class IntervalPartition { - typedef map IntervalMapTy; - IntervalMapTy IntervalMap; - - typedef vector IntervalListTy; - IntervalListTy IntervalList; - Interval *RootInterval; - -public: - typedef IntervalListTy::iterator iterator; - -public: - // IntervalPartition ctor - Build the partition for the specified method - IntervalPartition(Method *M); - - // IntervalPartition ctor - Build a reduced interval partition from an - // existing interval graph. This takes an additional boolean parameter to - // distinguish it from a copy constructor. Always pass in false for now. - // - IntervalPartition(IntervalPartition &I, bool); - - // Destructor - Free memory - ~IntervalPartition(); - - // getRootInterval() - Return the root interval that contains the starting - // block of the method. - inline Interval *getRootInterval() { return RootInterval; } - - // isDegeneratePartition() - Returns true if the interval partition contains - // a single interval, and thus cannot be simplified anymore. - bool isDegeneratePartition() { return size() == 1; } - - // TODO: isIrreducible - look for triangle graph. - - // getBlockInterval - Return the interval that a basic block exists in. - inline Interval *getBlockInterval(BasicBlock *BB) { - IntervalMapTy::iterator I = IntervalMap.find(BB); - return I != IntervalMap.end() ? I->second : 0; + /// nodes_iterator/begin/end - Allow iteration over all nodes in the graph + static inline ChildIteratorType child_begin(NodeType *N) { + return succ_begin(N); } + static inline ChildIteratorType child_end(NodeType *N) { + return succ_end(N); + } +}; - // Iterators to iterate over all of the intervals in the method - inline iterator begin() { return IntervalList.begin(); } - inline iterator end() { return IntervalList.end(); } - inline unsigned size() { return IntervalList.size(); } - -private: - // ProcessInterval - This method is used during the construction of the - // interval graph. It walks through the source graph, recursively creating - // an interval per invokation until the entire graph is covered. This uses - // the ProcessNode method to add all of the nodes to the interval. - // - // This method is templated because it may operate on two different source - // graphs: a basic block graph, or a preexisting interval graph. - // - template - void ProcessInterval(NodeTy *Node, OrigContainer *OC); - - // ProcessNode - This method is called by ProcessInterval to add nodes to the - // interval being constructed, and it is also called recursively as it walks - // the source graph. A node is added to the current interval only if all of - // its predecessors are already in the graph. This also takes care of keeping - // the successor set of an interval up to date. - // - // This method is templated because it may operate on two different source - // graphs: a basic block graph, or a preexisting interval graph. - // - template - void ProcessNode(Interval *Int, NodeTy *Node, OrigContainer *OC); - - // addNodeToInterval - This method exists to assist the generic ProcessNode - // with the task of adding a node to the new interval, depending on the - // type of the source node. In the case of a CFG source graph (BasicBlock - // case), the BasicBlock itself is added to the interval. In the case of - // an IntervalPartition source graph (Interval case), all of the member - // BasicBlocks are added to the interval. - // - inline void addNodeToInterval(Interval *Int, Interval *I); - inline void addNodeToInterval(Interval *Int, BasicBlock *BB); - - // updatePredecessors - Interval generation only sets the successor fields of - // the interval data structures. After interval generation is complete, - // run through all of the intervals and propogate successor info as - // predecessor info. - // - void updatePredecessors(Interval *Int); +template <> struct GraphTraits > { + typedef Interval NodeType; + typedef Interval::pred_iterator ChildIteratorType; + static NodeType *getEntryNode(Inverse G) { return G.Graph; } + static inline ChildIteratorType child_begin(NodeType *N) { + return pred_begin(N); + } + static inline ChildIteratorType child_end(NodeType *N) { + return pred_end(N); + } }; -} // End namespace cfg +} // End llvm namespace #endif