lib/CodeGen/MachineLoopRanges.cpp

   1 //===- MachineLoopRanges.cpp - Ranges of machine loops --------------------===//
   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 provides the implementation of the MachineLoopRanges analysis.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/CodeGen/MachineLoopRanges.h"
  15 #include "llvm/CodeGen/MachineLoopInfo.h"
  16 #include "llvm/CodeGen/Passes.h"
  17
  18 using namespace llvm;
  19
  20 char MachineLoopRanges::ID = 0;
  21 INITIALIZE_PASS_BEGIN(MachineLoopRanges, "machine-loop-ranges",
  22                 "Machine Loop Ranges", true, true)
  23 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
  24 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
  25 INITIALIZE_PASS_END(MachineLoopRanges, "machine-loop-ranges",
  26                 "Machine Loop Ranges", true, true)
  27
  28 char &llvm::MachineLoopRangesID = MachineLoopRanges::ID;
  29
  30 void MachineLoopRanges::getAnalysisUsage(AnalysisUsage &AU) const {
  31   AU.setPreservesAll();
  32   AU.addRequiredTransitive<SlotIndexes>();
  33   AU.addRequiredTransitive<MachineLoopInfo>();
  34   MachineFunctionPass::getAnalysisUsage(AU);
  35 }
  36
  37 /// runOnMachineFunction - Don't do much, loop ranges are computed on demand.
  38 bool MachineLoopRanges::runOnMachineFunction(MachineFunction &) {
  39   releaseMemory();
  40   Indexes = &getAnalysis<SlotIndexes>();
  41   return false;
  42 }
  43
  44 void MachineLoopRanges::releaseMemory() {
  45   DeleteContainerSeconds(Cache);
  46   Cache.clear();
  47 }
  48
  49 MachineLoopRange *MachineLoopRanges::getLoopRange(const MachineLoop *Loop) {
  50   MachineLoopRange *&Range = Cache[Loop];
  51   if (!Range)
  52     Range = new MachineLoopRange(Loop, Allocator, *Indexes);
  53   return Range;
  54 }
  55
  56 /// Create a MachineLoopRange, only accessible to MachineLoopRanges.
  57 MachineLoopRange::MachineLoopRange(const MachineLoop *loop,
  58                                    MachineLoopRange::Allocator &alloc,
  59                                    SlotIndexes &Indexes)
  60   : Loop(loop), Intervals(alloc), Area(0) {
  61   // Compute loop coverage.
  62   for (MachineLoop::block_iterator I = Loop->block_begin(),
  63          E = Loop->block_end(); I != E; ++I) {
  64     const std::pair<SlotIndex, SlotIndex> &Range = Indexes.getMBBRange(*I);
  65     Intervals.insert(Range.first, Range.second, 1u);
  66     Area += Range.first.distance(Range.second);
  67   }
  68 }
  69
  70 /// overlaps - Return true if this loop overlaps the given range of machine
  71 /// instructions.
  72 bool MachineLoopRange::overlaps(SlotIndex Start, SlotIndex Stop) {
  73   Map::const_iterator I = Intervals.find(Start);
  74   return I.valid() && Stop > I.start();
  75 }
  76
  77 unsigned MachineLoopRange::getNumber() const {
  78   return Loop->getHeader()->getNumber();
  79 }
  80
  81 /// byNumber - Comparator for array_pod_sort that sorts a list of
  82 /// MachineLoopRange pointers by number.
  83 int MachineLoopRange::byNumber(const void *pa, const void *pb) {
  84   const MachineLoopRange *a = *static_cast<MachineLoopRange *const *>(pa);
  85   const MachineLoopRange *b = *static_cast<MachineLoopRange *const *>(pb);
  86   unsigned na = a->getNumber();
  87   unsigned nb = b->getNumber();
  88   if (na < nb)
  89     return -1;
  90   if (na > nb)
  91     return 1;
  92   return 0;
  93 }
  94
  95 /// byAreaDesc - Comparator for array_pod_sort that sorts a list of
  96 /// MachineLoopRange pointers by:
  97 /// 1. Descending area.
  98 /// 2. Ascending number.
  99 int MachineLoopRange::byAreaDesc(const void *pa, const void *pb) {
 100   const MachineLoopRange *a = *static_cast<MachineLoopRange *const *>(pa);
 101   const MachineLoopRange *b = *static_cast<MachineLoopRange *const *>(pb);
 102   if (a->getArea() != b->getArea())
 103     return a->getArea() > b->getArea() ? -1 : 1;
 104   return byNumber(pa, pb);
 105 }
 106
 107 void MachineLoopRange::print(raw_ostream &OS) const {
 108   OS << "Loop#" << getNumber() << " =";
 109   for (Map::const_iterator I = Intervals.begin(); I.valid(); ++I)
 110     OS << " [" << I.start() << ';' << I.stop() << ')';
 111 }
 112
 113 raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineLoopRange &MLR) {
 114   MLR.print(OS);
 115   return OS;
 116 }