diff options
author | Chris Lattner <sabre@nondot.org> | 2001-06-20 19:26:12 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2001-06-20 19:26:12 +0000 |
commit | 564de7d79bd0e7c3b42988b112f325f15cd575ea (patch) | |
tree | d22bc946568abb2f7fadedbbb66c655e2270f244 /include/llvm/Analysis | |
parent | 1ffbbf4fc9ecbf70f69784da8bd835f4aa6c2ccb (diff) | |
download | llvm-564de7d79bd0e7c3b42988b112f325f15cd575ea.tar.gz llvm-564de7d79bd0e7c3b42988b112f325f15cd575ea.tar.bz2 llvm-564de7d79bd0e7c3b42988b112f325f15cd575ea.tar.xz |
New file: Interval analysis support
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@34 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'include/llvm/Analysis')
-rw-r--r-- | include/llvm/Analysis/Interval.h | 112 |
1 files changed, 112 insertions, 0 deletions
diff --git a/include/llvm/Analysis/Interval.h b/include/llvm/Analysis/Interval.h new file mode 100644 index 0000000000..a17e655c9e --- /dev/null +++ b/include/llvm/Analysis/Interval.h @@ -0,0 +1,112 @@ +//===- llvm/Analysis/Intervals.h - Interval partition Calculation-*- C++ -*--=// +// +// This file contains the declaration of the cfg::IntervalPartition class, which +// calculates and represent the interval partition of a method. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_INTERVALS_H +#define LLVM_INTERVALS_H + +#include <vector> +#include <map> +#include <algorithm> + +class Method; +class BasicBlock; + +namespace cfg { + +class IntervalPartition; + +// 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; +public: + typedef vector<BasicBlock*>::iterator succ_iterator; + typedef vector<BasicBlock*>::iterator pred_iterator; + typedef vector<BasicBlock*>::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; + + // Nodes - The basic blocks in this interval. + // + vector<BasicBlock*> 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<BasicBlock*> Successors; + + // Predecessors - List of BasicBlocks that have this Interval's header block + // as one of their successors. + // + vector<BasicBlock*> Predecessors; + + inline bool contains(BasicBlock *BB) { + return find(Nodes.begin(), Nodes.end(), BB) != Nodes.end(); + } + + inline bool isSuccessor(BasicBlock *BB) { + return find(Successors.begin(), Successors.end(), BB) != Successors.end(); + } + +private: // Only accessable by IntervalPartition class + inline Interval(BasicBlock *Header) : HeaderNode(Header) { + Nodes.push_back(Header); + } +}; + + +// 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<BasicBlock*, Interval*> IntervalMapTy; + IntervalMapTy IntervalMap; + + typedef vector<Interval*> IntervalListTy; + IntervalListTy IntervalList; + Interval *RootInterval; + +public: + typedef IntervalListTy::iterator iterator; + +public: + // IntervalPartition ctor - Build the partition for the specified method + IntervalPartition(Method *M); + + // getRootInterval() - Return the root interval that contains the starting + // block of the method + inline Interval *getRootInterval() { return RootInterval; } + + inline Interval *getBlockInterval(BasicBlock *BB) { + IntervalMapTy::iterator I = IntervalMap.find(BB); + if (I != IntervalMap.end()) + return I->second; + else + return 0; + } + + // Iterators to iterate over all of the intervals in the method + inline iterator begin() { return IntervalList.begin(); } + inline iterator end() { return IntervalList.end(); } + +private: + void ProcessInterval(BasicBlock *Header); + void ProcessBasicBlock(Interval *I, BasicBlock *BB); + void UpdateSuccessors(Interval *Int); +}; + +} // End namespace cfg + +#endif |