From ceadc01e9101329cd820ee687f85c012e9609ab1 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Wed, 15 Dec 2010 23:41:23 +0000 Subject: Add MachineLoopRanges analysis. A MachineLoopRange contains the intervals of slot indexes covered by the blocks in a loop. This representation of the loop blocks is more efficient to compare against interfering registers during register coalescing. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121917 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineLoopRanges.cpp | 85 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 85 insertions(+) create mode 100644 lib/CodeGen/MachineLoopRanges.cpp (limited to 'lib/CodeGen/MachineLoopRanges.cpp') diff --git a/lib/CodeGen/MachineLoopRanges.cpp b/lib/CodeGen/MachineLoopRanges.cpp new file mode 100644 index 0000000..9af49b0 --- /dev/null +++ b/lib/CodeGen/MachineLoopRanges.cpp @@ -0,0 +1,85 @@ +//===- MachineLoopRanges.cpp - Ranges of machine loops --------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file provides the implementation of the MachineLoopRanges analysis. +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/MachineLoopRanges.h" +#include "llvm/CodeGen/MachineLoopInfo.h" +#include "llvm/CodeGen/Passes.h" + +using namespace llvm; + +char MachineLoopRanges::ID = 0; +INITIALIZE_PASS_BEGIN(MachineLoopRanges, "machine-loop-ranges", + "Machine Loop Ranges", true, true) +INITIALIZE_PASS_DEPENDENCY(SlotIndexes) +INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) +INITIALIZE_PASS_END(MachineLoopRanges, "machine-loop-ranges", + "Machine Loop Ranges", true, true) + +char &llvm::MachineLoopRangesID = MachineLoopRanges::ID; + +void MachineLoopRanges::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequiredTransitive(); + AU.addRequiredTransitive(); + MachineFunctionPass::getAnalysisUsage(AU); +} + +/// runOnMachineFunction - Don't do much, loop ranges are computed on demand. +bool MachineLoopRanges::runOnMachineFunction(MachineFunction &) { + releaseMemory(); + Indexes = &getAnalysis(); + return false; +} + +void MachineLoopRanges::releaseMemory() { + DeleteContainerSeconds(Cache); + Cache.clear(); +} + +MachineLoopRange *MachineLoopRanges::getLoopRange(const MachineLoop *Loop) { + MachineLoopRange *&Range = Cache[Loop]; + if (!Range) + Range = new MachineLoopRange(Loop, Allocator, *Indexes); + return Range; +} + +/// Create a MachineLoopRange, only accessible to MachineLoopRanges. +MachineLoopRange::MachineLoopRange(const MachineLoop *loop, + MachineLoopRange::Allocator &alloc, + SlotIndexes &Indexes) + : Loop(loop), Intervals(alloc) { + // Compute loop coverage. + for (MachineLoop::block_iterator I = Loop->block_begin(), + E = Loop->block_end(); I != E; ++I) { + const std::pair &Range = Indexes.getMBBRange(*I); + Intervals.insert(Range.first, Range.second, 1u); + } +} + +/// overlaps - Return true if this loop overlaps the given range of machine +/// instructions. +bool MachineLoopRange::overlaps(SlotIndex Start, SlotIndex Stop) { + RangeMap::const_iterator I = Intervals.find(Start); + return I.valid() && Stop > I.start(); +} + +void MachineLoopRange::print(raw_ostream &OS) const { + OS << "Loop#" << Loop->getHeader()->getNumber() << " ="; + for (RangeMap::const_iterator I = Intervals.begin(); I.valid(); ++I) + OS << " [" << I.start() << ';' << I.stop() << ')'; +} + +raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineLoopRange &MLR) { + MLR.print(OS); + return OS; +} -- cgit v1.1 From ff2e9b4225ab55ee049b33158a9cce1ef138c2f7 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Fri, 17 Dec 2010 04:09:47 +0000 Subject: Provide LiveIntervalUnion::Query::checkLoopInterference. This is a three-way interval list intersection between a virtual register, a live interval union, and a loop. It will be used to identify interference-free loops for live range splitting. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122034 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineLoopRanges.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib/CodeGen/MachineLoopRanges.cpp') diff --git a/lib/CodeGen/MachineLoopRanges.cpp b/lib/CodeGen/MachineLoopRanges.cpp index 9af49b0..9ee6c5b 100644 --- a/lib/CodeGen/MachineLoopRanges.cpp +++ b/lib/CodeGen/MachineLoopRanges.cpp @@ -69,13 +69,13 @@ MachineLoopRange::MachineLoopRange(const MachineLoop *loop, /// overlaps - Return true if this loop overlaps the given range of machine /// instructions. bool MachineLoopRange::overlaps(SlotIndex Start, SlotIndex Stop) { - RangeMap::const_iterator I = Intervals.find(Start); + Map::const_iterator I = Intervals.find(Start); return I.valid() && Stop > I.start(); } void MachineLoopRange::print(raw_ostream &OS) const { OS << "Loop#" << Loop->getHeader()->getNumber() << " ="; - for (RangeMap::const_iterator I = Intervals.begin(); I.valid(); ++I) + for (Map::const_iterator I = Intervals.begin(); I.valid(); ++I) OS << " [" << I.start() << ';' << I.stop() << ')'; } -- cgit v1.1 From 090100fdb166e87bc539e3e4048d18c721c187d0 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Fri, 17 Dec 2010 18:13:52 +0000 Subject: Add MachineLoopRange comparators for sorting loop lists by number and by area. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122073 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineLoopRanges.cpp | 35 +++++++++++++++++++++++++++++++++-- 1 file changed, 33 insertions(+), 2 deletions(-) (limited to 'lib/CodeGen/MachineLoopRanges.cpp') diff --git a/lib/CodeGen/MachineLoopRanges.cpp b/lib/CodeGen/MachineLoopRanges.cpp index 9ee6c5b..17fe67f 100644 --- a/lib/CodeGen/MachineLoopRanges.cpp +++ b/lib/CodeGen/MachineLoopRanges.cpp @@ -57,12 +57,13 @@ MachineLoopRange *MachineLoopRanges::getLoopRange(const MachineLoop *Loop) { MachineLoopRange::MachineLoopRange(const MachineLoop *loop, MachineLoopRange::Allocator &alloc, SlotIndexes &Indexes) - : Loop(loop), Intervals(alloc) { + : Loop(loop), Intervals(alloc), Area(0) { // Compute loop coverage. for (MachineLoop::block_iterator I = Loop->block_begin(), E = Loop->block_end(); I != E; ++I) { const std::pair &Range = Indexes.getMBBRange(*I); Intervals.insert(Range.first, Range.second, 1u); + Area += Range.first.distance(Range.second); } } @@ -73,8 +74,38 @@ bool MachineLoopRange::overlaps(SlotIndex Start, SlotIndex Stop) { return I.valid() && Stop > I.start(); } +unsigned MachineLoopRange::getNumber() const { + return Loop->getHeader()->getNumber(); +} + +/// byNumber - Comparator for array_pod_sort that sorts a list of +/// MachineLoopRange pointers by number. +int MachineLoopRange::byNumber(const void *pa, const void *pb) { + const MachineLoopRange *a = *static_cast(pa); + const MachineLoopRange *b = *static_cast(pb); + unsigned na = a->getNumber(); + unsigned nb = b->getNumber(); + if (na < nb) + return -1; + if (na > nb) + return 1; + return 0; +} + +/// byAreaDesc - Comparator for array_pod_sort that sorts a list of +/// MachineLoopRange pointers by: +/// 1. Descending area. +/// 2. Ascending number. +int MachineLoopRange::byAreaDesc(const void *pa, const void *pb) { + const MachineLoopRange *a = *static_cast(pa); + const MachineLoopRange *b = *static_cast(pb); + if (a->getArea() != b->getArea()) + return a->getArea() > b->getArea() ? -1 : 1; + return byNumber(pa, pb); +} + void MachineLoopRange::print(raw_ostream &OS) const { - OS << "Loop#" << Loop->getHeader()->getNumber() << " ="; + OS << "Loop#" << getNumber() << " ="; for (Map::const_iterator I = Intervals.begin(); I.valid(); ++I) OS << " [" << I.start() << ';' << I.stop() << ')'; } -- cgit v1.1