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