From 7fa6784296e6bc1aa4e8ec3664e58247893c21a2 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Fri, 22 Jun 2012 20:37:52 +0000 Subject: [PATCH] Store live intervals in an IndexedMap. It is both smaller and faster than DenseMap. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159029 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/LiveIntervalAnalysis.h | 54 ++++++++++----------- lib/CodeGen/LiveIntervalAnalysis.cpp | 22 +++------ 2 files changed, 34 insertions(+), 42 deletions(-) diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 2e539fa4c7b..a941cc0bbaf 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -20,12 +20,13 @@ #ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H #define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H +#include "llvm/Target/TargetRegisterInfo.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/LiveInterval.h" #include "llvm/CodeGen/SlotIndexes.h" #include "llvm/ADT/BitVector.h" -#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/IndexedMap.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Support/Allocator.h" @@ -61,8 +62,8 @@ namespace llvm { /// VNInfo::Allocator VNInfoAllocator; - typedef DenseMap Reg2IntervalMap; - Reg2IntervalMap R2IMap; + /// Live interval pointers for all the virtual registers. + IndexedMap VirtRegIntervals; /// AllocatableRegs - A bit vector of allocatable registers. BitVector AllocatableRegs; @@ -108,22 +109,20 @@ namespace llvm { // Calculate the spill weight to assign to a single instruction. static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth); - unsigned getNumIntervals() const { return (unsigned)R2IMap.size(); } + unsigned getNumIntervals() const { return (unsigned)VirtRegIntervals.size(); } - LiveInterval &getInterval(unsigned reg) { - Reg2IntervalMap::iterator I = R2IMap.find(reg); - assert(I != R2IMap.end() && "Interval does not exist for register"); - return *I->second; + LiveInterval &getInterval(unsigned Reg) { + LiveInterval *LI = VirtRegIntervals[Reg]; + assert(LI && "Interval does not exist for virtual register"); + return *LI; } - const LiveInterval &getInterval(unsigned reg) const { - Reg2IntervalMap::const_iterator I = R2IMap.find(reg); - assert(I != R2IMap.end() && "Interval does not exist for register"); - return *I->second; + const LiveInterval &getInterval(unsigned Reg) const { + return const_cast(this)->getInterval(Reg); } - bool hasInterval(unsigned reg) const { - return R2IMap.count(reg); + bool hasInterval(unsigned Reg) const { + return VirtRegIntervals.inBounds(Reg) && VirtRegIntervals[Reg]; } /// isAllocatable - is the physical register reg allocatable in the current @@ -138,12 +137,19 @@ namespace llvm { return ReservedRegs.test(reg); } - // Interval creation - LiveInterval &getOrCreateInterval(unsigned reg) { - Reg2IntervalMap::iterator I = R2IMap.find(reg); - if (I == R2IMap.end()) - I = R2IMap.insert(std::make_pair(reg, createInterval(reg))).first; - return *I->second; + // Interval creation. + LiveInterval &getOrCreateInterval(unsigned Reg) { + if (!hasInterval(Reg)) { + VirtRegIntervals.grow(Reg); + VirtRegIntervals[Reg] = createInterval(Reg); + } + return getInterval(Reg); + } + + // Interval removal. + void removeInterval(unsigned Reg) { + delete VirtRegIntervals[Reg]; + VirtRegIntervals[Reg] = 0; } /// addLiveRangeToEndOfBlock - Given a register and an instruction, @@ -161,14 +167,6 @@ namespace llvm { bool shrinkToUses(LiveInterval *li, SmallVectorImpl *dead = 0); - // Interval removal - - void removeInterval(unsigned Reg) { - DenseMap::iterator I = R2IMap.find(Reg); - delete I->second; - R2IMap.erase(I); - } - SlotIndexes *getSlotIndexes() const { return Indexes; } diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 92037aa61e1..873edddf8b3 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -76,11 +76,9 @@ LiveIntervals::~LiveIntervals() { void LiveIntervals::releaseMemory() { // Free the live intervals themselves. - for (DenseMap::iterator I = R2IMap.begin(), - E = R2IMap.end(); I != E; ++I) - delete I->second; - - R2IMap.clear(); + for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i) + delete VirtRegIntervals[TargetRegisterInfo::index2VirtReg(i)]; + VirtRegIntervals.clear(); RegMaskSlots.clear(); RegMaskBits.clear(); RegMaskBlocks.clear(); @@ -124,21 +122,17 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { void LiveIntervals::print(raw_ostream &OS, const Module* ) const { OS << "********** INTERVALS **********\n"; - // Dump the physregs. - for (unsigned Reg = 1, RegE = TRI->getNumRegs(); Reg != RegE; ++Reg) - if (const LiveInterval *LI = R2IMap.lookup(Reg)) - OS << PrintReg(Reg, TRI) << '\t' << *LI << '\n'; - // Dump the regunits. for (unsigned i = 0, e = RegUnitIntervals.size(); i != e; ++i) if (LiveInterval *LI = RegUnitIntervals[i]) OS << PrintRegUnit(i, TRI) << " = " << *LI << '\n'; // Dump the virtregs. - for (unsigned Reg = 0, RegE = MRI->getNumVirtRegs(); Reg != RegE; ++Reg) - if (const LiveInterval *LI = - R2IMap.lookup(TargetRegisterInfo::index2VirtReg(Reg))) - OS << PrintReg(LI->reg) << '\t' << *LI << '\n'; + for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { + unsigned Reg = TargetRegisterInfo::index2VirtReg(i); + if (hasInterval(Reg)) + OS << PrintReg(Reg) << " = " << getInterval(Reg) << '\n'; + } printInstrs(OS); } -- 2.34.1