Home | History | Annotate | Download | only in CodeGen 
      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 }
    117