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
18using namespace llvm;
19
20char MachineLoopRanges::ID = 0;
21INITIALIZE_PASS_BEGIN(MachineLoopRanges, "machine-loop-ranges",
22                "Machine Loop Ranges", true, true)
23INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
24INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
25INITIALIZE_PASS_END(MachineLoopRanges, "machine-loop-ranges",
26                "Machine Loop Ranges", true, true)
27
28char &llvm::MachineLoopRangesID = MachineLoopRanges::ID;
29
30void 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.
38bool MachineLoopRanges::runOnMachineFunction(MachineFunction &) {
39  releaseMemory();
40  Indexes = &getAnalysis<SlotIndexes>();
41  return false;
42}
43
44void MachineLoopRanges::releaseMemory() {
45  DeleteContainerSeconds(Cache);
46  Cache.clear();
47}
48
49MachineLoopRange *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.
57MachineLoopRange::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.
72bool MachineLoopRange::overlaps(SlotIndex Start, SlotIndex Stop) {
73  Map::const_iterator I = Intervals.find(Start);
74  return I.valid() && Stop > I.start();
75}
76
77unsigned 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.
83int 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.
99int 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
107void 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
113raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineLoopRange &MLR) {
114  MLR.print(OS);
115  return OS;
116}
117