Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

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