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