diff options
| -rw-r--r-- | llvm/include/llvm/CodeGen/LiveInterval.h | 24 | ||||
| -rw-r--r-- | llvm/include/llvm/CodeGen/LiveStackAnalysis.h | 71 | ||||
| -rw-r--r-- | llvm/include/llvm/CodeGen/MachineFrameInfo.h | 22 | ||||
| -rw-r--r-- | llvm/include/llvm/CodeGen/Passes.h | 3 | ||||
| -rw-r--r-- | llvm/lib/CodeGen/LLVMTargetMachine.cpp | 58 | ||||
| -rw-r--r-- | llvm/lib/CodeGen/LiveInterval.cpp | 20 | ||||
| -rw-r--r-- | llvm/lib/CodeGen/LiveIntervalAnalysis.cpp | 18 | ||||
| -rw-r--r-- | llvm/lib/CodeGen/LiveStackAnalysis.cpp | 50 | ||||
| -rw-r--r-- | llvm/lib/CodeGen/RegAllocLinearScan.cpp | 33 | ||||
| -rw-r--r-- | llvm/lib/CodeGen/StackSlotColoring.cpp | 271 |
10 files changed, 523 insertions, 47 deletions
diff --git a/llvm/include/llvm/CodeGen/LiveInterval.h b/llvm/include/llvm/CodeGen/LiveInterval.h index e941a458dfb..b6f38dfc357 100644 --- a/llvm/include/llvm/CodeGen/LiveInterval.h +++ b/llvm/include/llvm/CodeGen/LiveInterval.h @@ -35,6 +35,7 @@ namespace llvm { /// merge point), it contains ~0u,x. If the value number is not in use, it /// contains ~1u,x to indicate that the value # is not used. /// def - Instruction # of the definition. + /// - or reg # of the definition if it's a stack slot liveinterval. /// copy - Copy iff val# is defined by a copy; zero otherwise. /// hasPHIKill - One or more of the kills are PHI nodes. /// kills - Instruction # of the kills. @@ -100,15 +101,16 @@ namespace llvm { typedef SmallVector<LiveRange,4> Ranges; typedef SmallVector<VNInfo*,4> VNInfoList; - unsigned reg; // the register of this interval + bool isSS; // True if this represents a stack slot + unsigned reg; // the register or stack slot of this interval unsigned preference; // preferred register to allocate for this interval float weight; // weight of this interval Ranges ranges; // the ranges in which this register is live VNInfoList valnos; // value#'s public: - LiveInterval(unsigned Reg, float Weight) - : reg(Reg), preference(0), weight(Weight) { + LiveInterval(unsigned Reg, float Weight, bool IsSS = false) + : isSS(IsSS), reg(Reg), preference(0), weight(Weight) { } typedef Ranges::iterator iterator; @@ -139,6 +141,17 @@ namespace llvm { return I; } + /// isStackSlot - Return true if this is a stack slot interval. + /// + bool isStackSlot() const { return isSS; } + + /// getStackSlotIndex - Return stack slot index if this is a stack slot + /// interval. + int getStackSlotIndex() const { + assert(isStackSlot() && "Interval is not a stack slot interval!"); + return reg; + } + bool containsOneValue() const { return valnos.size() == 1; } unsigned getNumValNums() const { return (unsigned)valnos.size(); } @@ -313,6 +326,11 @@ namespace llvm { /// FindLiveRangeContaining - Return an iterator to the live range that /// contains the specified index, or end() if there is none. iterator FindLiveRangeContaining(unsigned Idx); + + /// findDefinedVNInfo - Find the VNInfo that's defined at the specified + /// index (register interval) or defined by the specified register (stack + /// inteval). + VNInfo *findDefinedVNInfo(unsigned DefIdxOrReg) const; /// overlaps - Return true if the intersection of the two live intervals is /// not empty. diff --git a/llvm/include/llvm/CodeGen/LiveStackAnalysis.h b/llvm/include/llvm/CodeGen/LiveStackAnalysis.h new file mode 100644 index 00000000000..87ed67fa000 --- /dev/null +++ b/llvm/include/llvm/CodeGen/LiveStackAnalysis.h @@ -0,0 +1,71 @@ +//===-- LiveStackAnalysis.h - Live Stack Slot Analysis ----------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the live stack slot analysis pass. It is analogous to +// live interval analysis except it's analyzing liveness of stack slots rather +// than registers. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_LIVESTACK_ANALYSIS_H +#define LLVM_CODEGEN_LIVESTACK_ANALYSIS_H + +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/LiveInterval.h" +#include "llvm/Support/Allocator.h" +#include <map> + +namespace llvm { + + class LiveStacks : public MachineFunctionPass { + /// Special pool allocator for VNInfo's (LiveInterval val#). + /// + BumpPtrAllocator VNInfoAllocator; + + /// s2iMap - Stack slot indices to live interval mapping. + /// + typedef std::map<int, LiveInterval> SS2IntervalMap; + SS2IntervalMap s2iMap; + + public: + static char ID; // Pass identification, replacement for typeid + LiveStacks() : MachineFunctionPass((intptr_t)&ID) {} + + typedef SS2IntervalMap::iterator iterator; + typedef SS2IntervalMap::const_iterator const_iterator; + const_iterator begin() const { return s2iMap.begin(); } + const_iterator end() const { return s2iMap.end(); } + iterator begin() { return s2iMap.begin(); } + iterator end() { return s2iMap.end(); } + unsigned getNumIntervals() const { return (unsigned)s2iMap.size(); } + + LiveInterval &getOrCreateInterval(int Slot) { + SS2IntervalMap::iterator I = s2iMap.find(Slot); + if (I == s2iMap.end()) + I = s2iMap.insert(I,std::make_pair(Slot,LiveInterval(Slot,0.0F,true))); + return I->second; + } + + BumpPtrAllocator& getVNInfoAllocator() { return VNInfoAllocator; } + + virtual void getAnalysisUsage(AnalysisUsage &AU) const; + virtual void releaseMemory(); + + /// runOnMachineFunction - pass entry point + virtual bool runOnMachineFunction(MachineFunction&); + + /// print - Implement the dump method. + virtual void print(std::ostream &O, const Module* = 0) const; + void print(std::ostream *O, const Module* M = 0) const { + if (O) print(*O, M); + } + }; +} + +#endif /* LLVM_CODEGEN_LIVESTACK_ANALYSIS_H */ diff --git a/llvm/include/llvm/CodeGen/MachineFrameInfo.h b/llvm/include/llvm/CodeGen/MachineFrameInfo.h index 0f40550544a..b47ef6738f1 100644 --- a/llvm/include/llvm/CodeGen/MachineFrameInfo.h +++ b/llvm/include/llvm/CodeGen/MachineFrameInfo.h @@ -195,6 +195,13 @@ public: /// int getObjectIndexEnd() const { return (int)Objects.size()-NumFixedObjects; } + /// getNumFixedObjects() - Return the number of fixed objects. + unsigned getNumFixedObjects() const { return NumFixedObjects; } + + /// getNumObjects() - Return the number of objects. + /// + unsigned getNumObjects() const { return Objects.size(); } + /// getObjectSize - Return the size of the specified object /// int64_t getObjectSize(int ObjectIdx) const { @@ -203,6 +210,13 @@ public: return Objects[ObjectIdx+NumFixedObjects].Size; } + // setObjectSize - Change the size of the specified stack object... + void setObjectSize(int ObjectIdx, int64_t Size) { + assert(unsigned(ObjectIdx+NumFixedObjects) < Objects.size() && + "Invalid Object Idx!"); + Objects[ObjectIdx+NumFixedObjects].Size = Size; + } + /// getObjectAlignment - Return the alignment of the specified stack object... unsigned getObjectAlignment(int ObjectIdx) const { assert(unsigned(ObjectIdx+NumFixedObjects) < Objects.size() && @@ -324,12 +338,8 @@ public: /// RemoveStackObject - Remove or mark dead a statically sized stack object. /// void RemoveStackObject(int ObjectIdx) { - if (ObjectIdx == (int)(Objects.size()-NumFixedObjects-1)) - // Last object, simply pop it off the list. - Objects.pop_back(); - else - // Mark it dead. - Objects[ObjectIdx+NumFixedObjects].Size = ~0ULL; + // Mark it dead. + Objects[ObjectIdx+NumFixedObjects].Size = ~0ULL; } /// CreateVariableSizedObject - Notify the MachineFrameInfo object that a diff --git a/llvm/include/llvm/CodeGen/Passes.h b/llvm/include/llvm/CodeGen/Passes.h index 898416a9184..dd677fa5b13 100644 --- a/llvm/include/llvm/CodeGen/Passes.h +++ b/llvm/include/llvm/CodeGen/Passes.h @@ -172,6 +172,9 @@ namespace llvm { /// createMachineSinkingPass - This pass performs sinking on machine /// instructions. FunctionPass *createMachineSinkingPass(); + + /// createStackSlotColoringPass - This pass performs stack slot coloring. + FunctionPass *createStackSlotColoringPass(); } // End llvm namespace diff --git a/llvm/lib/CodeGen/LLVMTargetMachine.cpp b/llvm/lib/CodeGen/LLVMTargetMachine.cpp index e4ad8720941..73f2902d9a0 100644 --- a/llvm/lib/CodeGen/LLVMTargetMachine.cpp +++ b/llvm/lib/CodeGen/LLVMTargetMachine.cpp @@ -38,12 +38,13 @@ static cl::opt<bool> EnableSinking("enable-sinking", cl::init(false), cl::Hidden, cl::desc("Perform sinking on machine code")); static cl::opt<bool> -AlignLoops("align-loops", cl::init(true), cl::Hidden, - cl::desc("Align loop headers")); +EnableStackColoring("stack-coloring", + cl::init(true), cl::Hidden, + cl::desc("Perform stack slot coloring")); static cl::opt<bool> -PerformLICM("machine-licm", - cl::init(false), cl::Hidden, - cl::desc("Perform loop-invariant code motion on machine code")); +EnableLICM("machine-licm", + cl::init(false), cl::Hidden, + cl::desc("Perform loop-invariant code motion on machine code")); // When this works it will be on by default. static cl::opt<bool> @@ -88,7 +89,7 @@ LLVMTargetMachine::addPassesToEmitFile(PassManagerBase &PM, if (PrintMachineCode) PM.add(createMachineFunctionPrinterPass(cerr)); - if (PerformLICM) + if (EnableLICM) PM.add(createMachineLICMPass()); if (EnableSinking) @@ -101,21 +102,28 @@ LLVMTargetMachine::addPassesToEmitFile(PassManagerBase &PM, // Perform register allocation to convert to a concrete x86 representation PM.add(createRegisterAllocator()); - if (PrintMachineCode) + // Perform stack slot coloring. + if (EnableStackColoring) + PM.add(createStackSlotColoringPass()); + + if (PrintMachineCode) // Print the register-allocated code PM.add(createMachineFunctionPrinterPass(cerr)); - - PM.add(createLowerSubregsPass()); - if (PrintMachineCode) // Print the subreg lowered code - PM.add(createMachineFunctionPrinterPass(cerr)); - // Run post-ra passes. if (addPostRegAlloc(PM, Fast) && PrintMachineCode) PM.add(createMachineFunctionPrinterPass(cerr)); + PM.add(createLowerSubregsPass()); + + if (PrintMachineCode) // Print the subreg lowered code + PM.add(createMachineFunctionPrinterPass(cerr)); + // Insert prolog/epilog code. Eliminate abstract frame index references... PM.add(createPrologEpilogCodeInserter()); + if (PrintMachineCode) + PM.add(createMachineFunctionPrinterPass(cerr)); + // Second pass scheduler. if (!Fast && !DisablePostRAScheduler) PM.add(createPostRAScheduler()); @@ -140,7 +148,7 @@ LLVMTargetMachine::addPassesToEmitFile(PassManagerBase &PM, if (addPreEmitPass(PM, Fast) && PrintMachineCode) PM.add(createMachineFunctionPrinterPass(cerr)); - if (AlignLoops && !Fast && !OptimizeForSize) + if (!Fast && !OptimizeForSize) PM.add(createLoopAlignerPass()); switch (FileType) { @@ -218,7 +226,7 @@ bool LLVMTargetMachine::addPassesToEmitMachineCode(PassManagerBase &PM, if (PrintMachineCode) PM.add(createMachineFunctionPrinterPass(cerr)); - if (PerformLICM) + if (EnableLICM) PM.add(createMachineLICMPass()); if (EnableSinking) @@ -228,25 +236,32 @@ bool LLVMTargetMachine::addPassesToEmitMachineCode(PassManagerBase &PM, if (addPreRegAlloc(PM, Fast) && PrintMachineCode) PM.add(createMachineFunctionPrinterPass(cerr)); - // Perform register allocation to convert to a concrete x86 representation + // Perform register allocation. PM.add(createRegisterAllocator()); - + + // Perform stack slot coloring. + if (EnableStackColoring) + PM.add(createStackSlotColoringPass()); + if (PrintMachineCode) PM.add(createMachineFunctionPrinterPass(cerr)); + // Run post-ra passes. + if (addPostRegAlloc(PM, Fast) && PrintMachineCode) + PM.add(createMachineFunctionPrinterPass(cerr)); + + if (PrintMachineCode) // Print the register-allocated code + PM.add(createMachineFunctionPrinterPass(cerr)); + PM.add(createLowerSubregsPass()); if (PrintMachineCode) // Print the subreg lowered code PM.add(createMachineFunctionPrinterPass(cerr)); - // Run post-ra passes. - if (addPostRegAlloc(PM, Fast) && PrintMachineCode) - PM.add(createMachineFunctionPrinterPass(cerr)); - // Insert prolog/epilog code. Eliminate abstract frame index references... PM.add(createPrologEpilogCodeInserter()); - if (PrintMachineCode) // Print the register-allocated code + if (PrintMachineCode) PM.add(createMachineFunctionPrinterPass(cerr)); // Second pass scheduler. @@ -258,6 +273,7 @@ bool LLVMTargetMachine::addPassesToEmitMachineCode(PassManagerBase &PM, PM.add(createBranchFoldingPass(getEnableTailMergeDefault())); PM.add(createGCMachineCodeAnalysisPass()); + if (PrintMachineCode) PM.add(createMachineFunctionPrinterPass(cerr)); diff --git a/llvm/lib/CodeGen/LiveInterval.cpp b/llvm/lib/CodeGen/LiveInterval.cpp index 48c25a14a35..24081b99c0e 100644 --- a/llvm/lib/CodeGen/LiveInterval.cpp +++ b/llvm/lib/CodeGen/LiveInterval.cpp @@ -358,6 +358,20 @@ LiveInterval::FindLiveRangeContaining(unsigned Idx) { return end(); } +/// findDefinedVNInfo - Find the VNInfo that's defined at the specified index +/// (register interval) or defined by the specified register (stack inteval). +VNInfo *LiveInterval::findDefinedVNInfo(unsigned DefIdxOrReg) const { + VNInfo *VNI = NULL; + for (LiveInterval::const_vni_iterator i = vni_begin(), e = vni_end(); + i != e; ++i) + if ((*i)->def == DefIdxOrReg) { + VNI = *i; + break; + } + return VNI; +} + + /// join - Join two live intervals (this, and other) together. This applies /// mappings to the value numbers in the LHS/RHS intervals as specified. If /// the intervals are not joinable, this aborts. @@ -664,7 +678,9 @@ void LiveRange::dump() const { void LiveInterval::print(std::ostream &OS, const TargetRegisterInfo *TRI) const { - if (TRI && TargetRegisterInfo::isPhysicalRegister(reg)) + if (isSS) + OS << "SS#" << reg; + else if (TRI && TargetRegisterInfo::isPhysicalRegister(reg)) OS << TRI->getName(reg); else OS << "%reg" << reg; @@ -672,7 +688,7 @@ void LiveInterval::print(std::ostream &OS, OS << ',' << weight; if (empty()) - OS << "EMPTY"; + OS << " EMPTY"; else { OS << " = "; for (LiveInterval::Ranges::const_iterator I = ranges.begin(), diff --git a/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp b/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp index 54738539fa9..f184191b937 100644 --- a/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -65,6 +65,7 @@ void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { } void LiveIntervals::releaseMemory() { + MBB2IdxMap.clear(); Idx2MBBMap.clear(); mi2iMap_.clear(); i2miMap_.clear(); @@ -229,8 +230,8 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { void LiveIntervals::print(std::ostream &O, const Module* ) const { O << "********** INTERVALS **********\n"; for (const_iterator I = begin(), E = end(); I != E; ++I) { - I->second.print(DOUT, tri_); - DOUT << "\n"; + I->second.print(O, tri_); + O << "\n"; } O << "********** MACHINEINSTRS **********\n"; @@ -1160,17 +1161,6 @@ bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, return false; } -static const VNInfo *findDefinedVNInfo(const LiveInterval &li, unsigned DefIdx) { - const VNInfo *VNI = NULL; - for (LiveInterval::const_vni_iterator i = li.vni_begin(), - e = li.vni_end(); i != e; ++i) - if ((*i)->def == DefIdx) { - VNI = *i; - break; - } - return VNI; -} - /// RewriteInfo - Keep track of machine instrs that will be rewritten /// during spilling. namespace { @@ -1318,7 +1308,7 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index)); else { // If this is a two-address code, then this index starts a new VNInfo. - const VNInfo *VNI = findDefinedVNInfo(li, getDefIndex(index)); + const VNInfo *VNI = li.findDefinedVNInfo(getDefIndex(index)); if (VNI) HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index)); } diff --git a/llvm/lib/CodeGen/LiveStackAnalysis.cpp b/llvm/lib/CodeGen/LiveStackAnalysis.cpp new file mode 100644 index 00000000000..9358c105705 --- /dev/null +++ b/llvm/lib/CodeGen/LiveStackAnalysis.cpp @@ -0,0 +1,50 @@ +//===-- LiveStackAnalysis.cpp - Live Stack Slot Analysis ------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the live stack slot analysis pass. It is analogous to +// live interval analysis except it's analyzing liveness of stack slots rather +// than registers. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "livestacks" +#include "llvm/CodeGen/LiveStackAnalysis.h" +#include "llvm/CodeGen/Passes.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Support/Debug.h" +#include "llvm/ADT/Statistic.h" +using namespace llvm; + +char LiveStacks::ID = 0; +static RegisterPass<LiveStacks> X("livestacks", "Live Stack Slot Analysis"); + +void LiveStacks::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); +} + +void LiveStacks::releaseMemory() { + // Release VNInfo memroy regions after all VNInfo objects are dtor'd. + VNInfoAllocator.Reset(); + s2iMap.clear(); +} + +bool LiveStacks::runOnMachineFunction(MachineFunction &) { + // FIXME: No analysis is being done right now. We are relying on the + // register allocators to provide the information. + return false; +} + +/// print - Implement the dump method. +void LiveStacks::print(std::ostream &O, const Module* ) const { + O << "********** INTERVALS **********\n"; + for (const_iterator I = begin(), E = end(); I != E; ++I) { + I->second.print(O); + O << "\n"; + } +} diff --git a/llvm/lib/CodeGen/RegAllocLinearScan.cpp b/llvm/lib/CodeGen/RegAllocLinearScan.cpp index 456ee6319c1..8bfa8680a7c 100644 --- a/llvm/lib/CodeGen/RegAllocLinearScan.cpp +++ b/llvm/lib/CodeGen/RegAllocLinearScan.cpp @@ -12,10 +12,11 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "regalloc" -#include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "PhysRegTracker.h" #include "VirtRegMap.h" #include "llvm/Function.h" +#include "llvm/CodeGen/LiveIntervalAnalysis.h" +#include "llvm/CodeGen/LiveStackAnalysis.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineLoopInfo.h" @@ -67,6 +68,7 @@ namespace { MachineRegisterInfo *reginfo_; BitVector allocatableRegs_; LiveIntervals* li_; + LiveStacks* ls_; const MachineLoopInfo *loopInfo; /// handled_ - Intervals are added to the handled_ set in the order of their @@ -103,6 +105,8 @@ namespace { // Make sure PassManager knows which analyses to make available // to coalescing and which analyses coalescing invalidates. AU.addRequiredTransitive<RegisterCoalescer>(); + AU.addRequired<LiveStacks>(); + AU.addPreserved<LiveStacks>(); AU.addRequired<MachineLoopInfo>(); AU.addPreserved<MachineLoopInfo>(); AU.addPreservedID(MachineDominatorsID); @@ -171,6 +175,9 @@ namespace { char RALinScan::ID = 0; } +static RegisterPass<RALinScan> +X("linearscan-regalloc", "Linear Scan Register Allocator"); + void RALinScan::ComputeRelatedRegClasses() { const TargetRegisterInfo &TRI = *tri_; @@ -258,6 +265,7 @@ bool RALinScan::runOnMachineFunction(MachineFunction &fn) { reginfo_ = &mf_->getRegInfo(); allocatableRegs_ = tri_->getAllocatableSet(fn); li_ = &getAnalysis<LiveIntervals>(); + ls_ = &getAnalysis<LiveStacks>(); loopInfo = &getAnalysis<MachineLoopInfo>(); // We don't run the coalescer here because we have no reason to @@ -504,6 +512,26 @@ static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V, unsigned Point){ } } +/// addStackInterval - Create a LiveInterval for stack if the specified live +/// interval has been spilled. +static void addStackInterval(LiveInterval *cur, LiveStacks *ls_, + LiveIntervals *li_, VirtRegMap &vrm_) { + int SS = vrm_.getStackSlot(cur->reg); + if (SS == VirtRegMap::NO_STACK_SLOT) + return; + LiveInterval &SI = ls_->getOrCreateInterval(SS); + VNInfo *VNI; + if (SI.getNumValNums()) + VNI = SI.getValNumInfo(0); + else + VNI = SI.getNextValue(~0U, 0, ls_->getVNInfoAllocator()); + + LiveInterval &RI = li_->getInterval(cur->reg); + // FIXME: This may be overly conservative. + SI.MergeRangesInAsValue(RI, VNI); + SI.weight += RI.weight; +} + /// assignRegOrStackSlotAtInterval - assign a register if one is available, or /// spill. void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) @@ -717,6 +745,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) DOUT << "\t\t\tspilling(c): " << *cur << '\n'; std::vector<LiveInterval*> added = li_->addIntervalsForSpills(*cur, loopInfo, *vrm_); + addStackInterval(cur, ls_, li_, *vrm_); if (added.empty()) return; // Early exit if all spills were folded. @@ -769,6 +798,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) earliestStart = std::min(earliestStart, i->first->beginNumber()); std::vector<LiveInterval*> newIs = li_->addIntervalsForSpills(*i->first, loopInfo, *vrm_); + addStackInterval(i->first, ls_, li_, *vrm_); std::copy(newIs.begin(), newIs.end(), std::back_inserter(added)); spilled.insert(reg); } @@ -782,6 +812,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) earliestStart = std::min(earliestStart, i->first->beginNumber()); std::vector<LiveInterval*> newIs = li_->addIntervalsForSpills(*i->first, loopInfo, *vrm_); + addStackInterval(i->first, ls_, li_, *vrm_); std::copy(newIs.begin(), newIs.end(), std::back_inserter(added)); spilled.insert(reg); } diff --git a/llvm/lib/CodeGen/StackSlotColoring.cpp b/llvm/lib/CodeGen/StackSlotColoring.cpp new file mode 100644 index 00000000000..24bd028afda --- /dev/null +++ b/llvm/lib/CodeGen/StackSlotColoring.cpp @@ -0,0 +1,271 @@ +//===-- StackSlotColoring.cpp - Sinking for machine instructions ----------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the stack slot coloring pass. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "stackcoloring" +#include "llvm/CodeGen/LiveStackAnalysis.h" +#include "llvm/CodeGen/MachineFrameInfo.h" +#include "llvm/CodeGen/Passes.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/Debug.h" +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" +#include <vector> +using namespace llvm; + +static cl::opt<bool> +DisableSharing("no-stack-slot-sharing", + cl::init(false), cl::Hidden, + cl::desc("Surpress slot sharing during stack coloring")); + +static cl::opt<int> +DeleteLimit("slot-delete-limit", cl::init(-1), cl::Hidden, + cl::desc("Stack coloring slot deletion limit")); + +STATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring"); + +namespace { + class VISIBILITY_HIDDEN StackSlotColoring : public MachineFunctionPass { + LiveStacks* LS; + MachineFrameInfo *MFI; + + // SSIntervals - Spill slot intervals. + std::vector<LiveInterval*> SSIntervals; + + // OrigAlignments - Alignments of stack objects before coloring. + SmallVector<unsigned, 16> OrigAlignments; + + // OrigSizes - Sizess of stack objects before coloring. + SmallVector<unsigned, 16> OrigSizes; + + // AllColors - If index is set, it's a spill slot, i.e. color. + // FIXME: This assumes PEI locate spill slot with smaller indices + // closest to stack pointer / frame pointer. Therefore, smaller + // index == better color. + BitVector AllColors; + + // NextColor - Next "color" that's not yet used. + int NextColor; + + // UsedColors - "Colors" that have been assigned. + BitVector UsedColors; + + // Assignments - Color to intervals mapping. + SmallVector<SmallVector<LiveInterval*,4>,16> Assignments; + + public: + static char ID; // Pass identification + StackSlotColoring() : MachineFunctionPass((intptr_t)&ID), NextColor(-1) {} + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired<LiveStacks>(); + MachineFunctionPass::getAnalysisUsage(AU); + } + + virtual bool runOnMachineFunction(MachineFunction &MF); + virtual const char* getPassName() const { + return "Stack Slot Coloring"; + } + + private: + bool InitializeSlots(); + bool OverlapWithAssignments(LiveInterval *li, int Color) const; + int ColorSlot(LiveInterval *li); + bool ColorSlots(MachineFunction &MF); + }; +} // end anonymous namespace + +char StackSlotColoring::ID = 0; + +static RegisterPass<StackSlotColoring> +X("stack-slot-coloring", "Stack Slot Coloring"); + +FunctionPass *llvm::createStackSlotColoringPass() { + return new StackSlotColoring(); +} + +namespace { + // IntervalSorter - Comparison predicate that sort live intervals by + // their weight. + struct IntervalSorter { + bool operator()(LiveInterval* LHS, LiveInterval* RHS) const { + return LHS->weight > RHS->weight; + } + }; +} + +/// InitializeSlots - Process all spill stack slot liveintervals and add them +/// to a sorted (by weight) list. +bool StackSlotColoring::InitializeSlots() { + if (LS->getNumIntervals() < 2) + return false; + + int LastFI = MFI->getObjectIndexEnd(); + OrigAlignments.resize(LastFI); + OrigSizes.resize(LastFI); + AllColors.resize(LastFI); + UsedColors.resize(LastFI); + Assignments.resize(LastFI); + + // Gather all spill slots into a list. + for (LiveStacks::iterator i = LS->begin(), e = LS->end(); i != e; ++i) { + LiveInterval &li = i->second; + int FI = li.getStackSlotIndex(); + if (MFI->isDeadObjectIndex(FI)) + continue; + SSIntervals.push_back(&li); + OrigAlignments[FI] = MFI->getObjectAlignment(FI); + OrigSizes[FI] = MFI->getObjectSize(FI); + AllColors.set(FI); + } + + // Sort them by weight. + std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter()); + + // Get first "color". + NextColor = AllColors.find_first(); + return true; +} + +/// OverlapWithAssignments - Return true if LiveInterval overlaps with any +/// LiveIntervals that have already been assigned to the specified color. +bool +StackSlotColoring::OverlapWithAssignments(LiveInterval *li, int Color) const { + const SmallVector<LiveInterval*,4> &OtherLIs = Assignments[Color]; + for (unsigned i = 0, e = OtherLIs.size(); i != e; ++i) { + LiveInterval *OtherLI = OtherLIs[i]; + if (OtherLI->overlaps(*li)) + return true; + } + return false; +} + +/// ColorSlot - Assign a "color" (stack slot) to the specified stack slot. +/// +int StackSlotColoring::ColorSlot(LiveInterval *li) { + int Color = -1; + bool Share = false; + if (!DisableSharing && + (DeleteLimit == -1 || (int)NumEliminated < DeleteLimit)) { + // Check if it's possible to reuse any of the used colors. + Color = UsedColors.find_first(); + while (Color != -1) { + if (!OverlapWithAssignments(li, Color)) { + Share = true; + ++NumEliminated; + break; + } + Color = UsedColors.find_next(Color); + } + } + + // Assign it to the first available color (assumed to be the best) if it's + // not possible to share a used color with other objects. + if (!Share) { + assert(NextColor != -1 && "No more spill slots?"); + Color = NextColor; + UsedColors.set(Color); + NextColor = AllColors.find_next(NextColor); + } + + // Record the assignment. + Assignments[Color].push_back(li); + int FI = li->getStackSlotIndex(); + DOUT << "Assigning fi #" << FI << " to fi #" << Color << "\n"; + + // Change size and alignment of the allocated slot. If there are multiple + // objects sharing the same slot, then make sure the size and alignment + // are large enough for all. + unsigned Align = OrigAlignments[FI]; + if (!Share || Align > MFI->getObjectAlignment(Color)) + MFI->setObjectAlignment(Color, Align); + int64_t Size = OrigSizes[FI]; + if (!Share || Size > MFI->getObjectSize(Color)) + MFI->setObjectSize(Color, Size); + return Color; +} + +/// Colorslots - Color all spill stack slots and rewrite all frameindex machine +/// operands in the function. +bool StackSlotColoring::ColorSlots(MachineFunction &MF) { + unsigned NumObjs = MFI->getObjectIndexEnd(); + std::vector<int> SlotMapping(NumObjs, -1); + SlotMapping.resize(NumObjs, -1); + + bool Changed = false; + for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { + LiveInterval *li = SSIntervals[i]; + int SS = li->getStackSlotIndex(); + int NewSS = ColorSlot(li); + SlotMapping[SS] = NewSS; + Changed |= (SS != NewSS); + } + + if (!Changed) + return false; + + // Rewrite all MO_FrameIndex operands. + // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands. + for (MachineFunction::iterator MBB = MF.begin(), E = MF.end(); + MBB != E; ++MBB) { + for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end(); + MII != EE; ++MII) { + MachineInstr &MI = *MII; + for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { + MachineOperand &MO = MI.getOperand(i); + if (!MO.isFrameIndex()) + continue; + int FI = MO.getIndex(); + if (FI < 0) + continue; + FI = SlotMapping[FI]; + if (FI == -1) + continue; + MO.setIndex(FI); + } + } + } + + // Delete unused stack slots. + while (NextColor != -1) { + DOUT << "Removing unused stack object fi #" << NextColor << "\n"; + MFI->RemoveStackObject(NextColor); + NextColor = AllColors.find_next(NextColor); + } + + return true; +} + +bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) { + DOUT << "******** Stack Slot Coloring ********\n"; + + MFI = MF.getFrameInfo(); + LS = &getAnalysis<LiveStacks>(); + + bool Changed = false; + if (InitializeSlots()) + Changed = ColorSlots(MF); + + NextColor = -1; + SSIntervals.clear(); + OrigAlignments.clear(); + OrigSizes.clear(); + AllColors.clear(); + UsedColors.clear(); + for (unsigned i = 0, e = Assignments.size(); i != e; ++i) + Assignments[i].clear(); + Assignments.clear(); + + return Changed; +} |
