1 //===- MachineLoopRanges.cpp - Ranges of machine loops --------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file provides the implementation of the MachineLoopRanges analysis.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/MachineLoopRanges.h"
15 #include "llvm/CodeGen/MachineLoopInfo.h"
16 #include "llvm/CodeGen/Passes.h"
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)
28 char &llvm::MachineLoopRangesID
= MachineLoopRanges::ID
;
30 void MachineLoopRanges::getAnalysisUsage(AnalysisUsage
&AU
) const {
32 AU
.addRequiredTransitive
<SlotIndexes
>();
33 AU
.addRequiredTransitive
<MachineLoopInfo
>();
34 MachineFunctionPass::getAnalysisUsage(AU
);
37 /// runOnMachineFunction - Don't do much, loop ranges are computed on demand.
38 bool MachineLoopRanges::runOnMachineFunction(MachineFunction
&) {
40 Indexes
= &getAnalysis
<SlotIndexes
>();
44 void MachineLoopRanges::releaseMemory() {
45 DeleteContainerSeconds(Cache
);
49 MachineLoopRange
*MachineLoopRanges::getLoopRange(const MachineLoop
*Loop
) {
50 MachineLoopRange
*&Range
= Cache
[Loop
];
52 Range
= new MachineLoopRange(Loop
, Allocator
, *Indexes
);
56 /// Create a MachineLoopRange, only accessible to MachineLoopRanges.
57 MachineLoopRange::MachineLoopRange(const MachineLoop
*loop
,
58 MachineLoopRange::Allocator
&alloc
,
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
);
70 /// overlaps - Return true if this loop overlaps the given range of machine
72 bool MachineLoopRange::overlaps(SlotIndex Start
, SlotIndex Stop
) {
73 Map::const_iterator I
= Intervals
.find(Start
);
74 return I
.valid() && Stop
> I
.start();
77 unsigned MachineLoopRange::getNumber() const {
78 return Loop
->getHeader()->getNumber();
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();
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
);
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() << ')';
113 raw_ostream
&llvm::operator<<(raw_ostream
&OS
, const MachineLoopRange
&MLR
) {