Line data    Source code

       1             : //===- IntervalPartition.h - Interval partition Calculation -----*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file contains the declaration of the IntervalPartition class, which
      11             : // calculates and represents the interval partition of a function, or a
      12             : // preexisting interval partition.
      13             : //
      14             : // In this way, the interval partition may be used to reduce a flow graph down
      15             : // to its degenerate single node interval partition (unless it is irreducible).
      16             : //
      17             : // TODO: The IntervalPartition class should take a bool parameter that tells
      18             : // whether it should add the "tails" of an interval to an interval itself or if
      19             : // they should be represented as distinct intervals.
      20             : //
      21             : //===----------------------------------------------------------------------===//
      22             : 
      23             : #ifndef LLVM_ANALYSIS_INTERVALPARTITION_H
      24             : #define LLVM_ANALYSIS_INTERVALPARTITION_H
      25             : 
      26             : #include "llvm/Pass.h"
      27             : #include <map>
      28             : #include <vector>
      29             : 
      30             : namespace llvm {
      31             : 
      32             : class BasicBlock;
      33             : class Interval;
      34             : 
      35             : //===----------------------------------------------------------------------===//
      36             : //
      37             : // IntervalPartition - This class builds and holds an "interval partition" for
      38             : // a function.  This partition divides the control flow graph into a set of
      39             : // maximal intervals, as defined with the properties above.  Intuitively, an
      40             : // interval is a (possibly nonexistent) loop with a "tail" of non-looping
      41             : // nodes following it.
      42             : //
      43             : class IntervalPartition : public FunctionPass {
      44             :   using IntervalMapTy = std::map<BasicBlock *, Interval *>;
      45             :   IntervalMapTy IntervalMap;
      46             : 
      47             :   using IntervalListTy = std::vector<Interval *>;
      48             :   Interval *RootInterval = nullptr;
      49             :   std::vector<Interval *> Intervals;
      50             : 
      51             : public:
      52             :   static char ID; // Pass identification, replacement for typeid
      53             : 
      54           0 :   IntervalPartition() : FunctionPass(ID) {
      55           0 :     initializeIntervalPartitionPass(*PassRegistry::getPassRegistry());
      56           0 :   }
      57             : 
      58             :   // run - Calculate the interval partition for this function
      59             :   bool runOnFunction(Function &F) override;
      60             : 
      61             :   // IntervalPartition ctor - Build a reduced interval partition from an
      62             :   // existing interval graph.  This takes an additional boolean parameter to
      63             :   // distinguish it from a copy constructor.  Always pass in false for now.
      64             :   IntervalPartition(IntervalPartition &I, bool);
      65             : 
      66             :   // print - Show contents in human readable format...
      67             :   void print(raw_ostream &O, const Module* = nullptr) const override;
      68             : 
      69             :   // getRootInterval() - Return the root interval that contains the starting
      70             :   // block of the function.
      71           0 :   inline Interval *getRootInterval() { return RootInterval; }
      72             : 
      73             :   // isDegeneratePartition() - Returns true if the interval partition contains
      74             :   // a single interval, and thus cannot be simplified anymore.
      75             :   bool isDegeneratePartition() { return Intervals.size() == 1; }
      76             : 
      77             :   // TODO: isIrreducible - look for triangle graph.
      78             : 
      79             :   // getBlockInterval - Return the interval that a basic block exists in.
      80             :   inline Interval *getBlockInterval(BasicBlock *BB) {
      81             :     IntervalMapTy::iterator I = IntervalMap.find(BB);
      82           0 :     return I != IntervalMap.end() ? I->second : nullptr;
      83             :   }
      84             : 
      85             :   // getAnalysisUsage - Implement the Pass API
      86           0 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
      87             :     AU.setPreservesAll();
      88           0 :   }
      89             : 
      90             :   // Interface to Intervals vector...
      91             :   const std::vector<Interval*> &getIntervals() const { return Intervals; }
      92             : 
      93             :   // releaseMemory - Reset state back to before function was analyzed
      94             :   void releaseMemory() override;
      95             : 
      96             : private:
      97             :   // addIntervalToPartition - Add an interval to the internal list of intervals,
      98             :   // and then add mappings from all of the basic blocks in the interval to the
      99             :   // interval itself (in the IntervalMap).
     100             :   void addIntervalToPartition(Interval *I);
     101             : 
     102             :   // updatePredecessors - Interval generation only sets the successor fields of
     103             :   // the interval data structures.  After interval generation is complete,
     104             :   // run through all of the intervals and propagate successor info as
     105             :   // predecessor info.
     106             :   void updatePredecessors(Interval *Int);
     107             : };
     108             : 
     109             : } // end namespace llvm
     110             : 
     111             : #endif // LLVM_ANALYSIS_INTERVALPARTITION_H