diff options
author | Lang Hames <lhames@gmail.com> | 2009-05-18 19:03:16 +0000 |
---|---|---|
committer | Lang Hames <lhames@gmail.com> | 2009-05-18 19:03:16 +0000 |
commit | e2b201bac382464496758d789cddefa50690fbe3 (patch) | |
tree | d666c209dae6bb7d4c8720a3f06cccd9a6b17ec7 /lib | |
parent | 16899a205638b81be8537526e34ad35ce3472299 (diff) | |
download | external_llvm-e2b201bac382464496758d789cddefa50690fbe3.zip external_llvm-e2b201bac382464496758d789cddefa50690fbe3.tar.gz external_llvm-e2b201bac382464496758d789cddefa50690fbe3.tar.bz2 |
New Spiller interface and trivial implementation.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72030 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib')
-rw-r--r-- | lib/CodeGen/RegAllocLinearScan.cpp | 26 | ||||
-rw-r--r-- | lib/CodeGen/Spiller.cpp | 206 | ||||
-rw-r--r-- | lib/CodeGen/Spiller.h | 32 |
3 files changed, 262 insertions, 2 deletions
diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index c5ce455..ac6ab32 100644 --- a/lib/CodeGen/RegAllocLinearScan.cpp +++ b/lib/CodeGen/RegAllocLinearScan.cpp @@ -14,6 +14,7 @@ #define DEBUG_TYPE "regalloc" #include "VirtRegMap.h" #include "VirtRegRewriter.h" +#include "Spiller.h" #include "llvm/Function.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/LiveStackAnalysis.h" @@ -56,6 +57,11 @@ PreSplitIntervals("pre-alloc-split", cl::desc("Pre-register allocation live interval splitting"), cl::init(false), cl::Hidden); +static cl::opt<bool> +NewSpillFramework("new-spill-framework", + cl::desc("New spilling framework"), + cl::init(false), cl::Hidden); + static RegisterRegAlloc linearscanRegAlloc("linearscan", "linear scan register allocator", createLinearScanRegisterAllocator); @@ -127,6 +133,8 @@ namespace { std::auto_ptr<VirtRegRewriter> rewriter_; + std::auto_ptr<Spiller> spiller_; + public: virtual const char* getPassName() const { return "Linear Scan Register Allocator"; @@ -420,6 +428,13 @@ bool RALinScan::runOnMachineFunction(MachineFunction &fn) { vrm_ = &getAnalysis<VirtRegMap>(); if (!rewriter_.get()) rewriter_.reset(createVirtRegRewriter()); + + if (NewSpillFramework) { + spiller_.reset(createSpiller(mf_, li_, vrm_)); + } + else { + spiller_.reset(0); + } initIntervalSets(); @@ -1108,8 +1123,15 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) if (cur->weight != HUGE_VALF && cur->weight <= minWeight) { DOUT << "\t\t\tspilling(c): " << *cur << '\n'; SmallVector<LiveInterval*, 8> spillIs; - std::vector<LiveInterval*> added = - li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_); + std::vector<LiveInterval*> added; + + if (!NewSpillFramework) { + added = li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_); + } + else { + added = spiller_->spill(cur); + } + std::sort(added.begin(), added.end(), LISorter()); addStackInterval(cur, ls_, li_, mri_, *vrm_); if (added.empty()) diff --git a/lib/CodeGen/Spiller.cpp b/lib/CodeGen/Spiller.cpp new file mode 100644 index 0000000..eb2a8a1 --- /dev/null +++ b/lib/CodeGen/Spiller.cpp @@ -0,0 +1,206 @@ +//===-- llvm/CodeGen/Spiller.cpp - Spiller -------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "spiller" + +#include "Spiller.h" +#include "VirtRegMap.h" +#include "llvm/CodeGen/LiveIntervalAnalysis.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/MachineFrameInfo.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Support/Debug.h" + +#include <algorithm> +#include <map> + +using namespace llvm; + +Spiller::~Spiller() {} + +namespace { + +class TrivialSpiller : public Spiller { +public: + TrivialSpiller(MachineFunction *mf, LiveIntervals *lis, VirtRegMap *vrm) : + mf(mf), lis(lis), vrm(vrm) + { + mfi = mf->getFrameInfo(); + mri = &mf->getRegInfo(); + tii = mf->getTarget().getInstrInfo(); + } + + std::vector<LiveInterval*> spill(LiveInterval *li) { + + DOUT << "Trivial spiller spilling " << *li << "\n"; + + assert(li->weight != HUGE_VALF && + "Attempting to spill already spilled value."); + + assert(!li->isStackSlot() && + "Trying to spill a stack slot."); + + std::vector<LiveInterval*> added; + + const TargetRegisterClass *trc = mri->getRegClass(li->reg); + /*unsigned ss = mfi->CreateStackObject(trc->getSize(), + trc->getAlignment());*/ + unsigned ss = vrm->assignVirt2StackSlot(li->reg); + + MachineRegisterInfo::reg_iterator regItr = mri->reg_begin(li->reg); + + while (regItr != mri->reg_end()) { + + MachineInstr *mi = &*regItr; + + SmallVector<unsigned, 2> indices; + bool hasUse = false; + bool hasDef = false; + + for (unsigned i = 0; i != mi->getNumOperands(); ++i) { + MachineOperand &op = mi->getOperand(i); + + if (!op.isReg() || op.getReg() != li->reg) + continue; + + hasUse |= mi->getOperand(i).isUse(); + hasDef |= mi->getOperand(i).isDef(); + + indices.push_back(i); + } + + unsigned newVReg = mri->createVirtualRegister(trc); + LiveInterval *newLI = &lis->getOrCreateInterval(newVReg); + newLI->weight = HUGE_VALF; + + vrm->grow(); + vrm->assignVirt2StackSlot(newVReg, ss); + + for (unsigned i = 0; i < indices.size(); ++i) { + mi->getOperand(indices[i]).setReg(newVReg); + + if (mi->getOperand(indices[i]).isUse()) { + mi->getOperand(indices[i]).setIsKill(true); + } + } + + if (hasUse) { + unsigned loadInstIdx = insertLoadFor(mi, ss, newVReg, trc); + unsigned start = lis->getDefIndex(loadInstIdx), + end = lis->getUseIndex(lis->getInstructionIndex(mi)); + + VNInfo *vni = + newLI->getNextValue(loadInstIdx, 0, lis->getVNInfoAllocator()); + vni->kills.push_back(lis->getInstructionIndex(mi)); + LiveRange lr(start, end, vni); + + newLI->addRange(lr); + added.push_back(newLI); + } + + if (hasDef) { + unsigned storeInstIdx = insertStoreFor(mi, ss, newVReg, trc); + unsigned start = lis->getDefIndex(lis->getInstructionIndex(mi)), + end = lis->getUseIndex(storeInstIdx); + + VNInfo *vni = + newLI->getNextValue(storeInstIdx, 0, lis->getVNInfoAllocator()); + vni->kills.push_back(storeInstIdx); + LiveRange lr(start, end, vni); + + newLI->addRange(lr); + added.push_back(newLI); + } + + regItr = mri->reg_begin(li->reg); + } + + + return added; + } + + +private: + + MachineFunction *mf; + LiveIntervals *lis; + MachineFrameInfo *mfi; + MachineRegisterInfo *mri; + const TargetInstrInfo *tii; + VirtRegMap *vrm; + + + + void makeRoomForInsertBefore(MachineInstr *mi) { + if (!lis->hasGapBeforeInstr(lis->getInstructionIndex(mi))) { + lis->computeNumbering(); + } + + assert(lis->hasGapBeforeInstr(lis->getInstructionIndex(mi))); + } + + unsigned insertStoreFor(MachineInstr *mi, unsigned ss, + unsigned newVReg, + const TargetRegisterClass *trc) { + MachineBasicBlock::iterator nextInstItr(mi); + ++nextInstItr; + + makeRoomForInsertBefore(&*nextInstItr); + + unsigned miIdx = lis->getInstructionIndex(mi); + + tii->storeRegToStackSlot(*mi->getParent(), nextInstItr, newVReg, + true, ss, trc); + MachineBasicBlock::iterator storeInstItr(mi); + ++storeInstItr; + MachineInstr *storeInst = &*storeInstItr; + unsigned storeInstIdx = miIdx + LiveIntervals::InstrSlots::NUM; + + assert(lis->getInstructionFromIndex(storeInstIdx) == 0 && + "Store inst index already in use."); + + lis->InsertMachineInstrInMaps(storeInst, storeInstIdx); + + return storeInstIdx; + } + + unsigned insertLoadFor(MachineInstr *mi, unsigned ss, + unsigned newVReg, + const TargetRegisterClass *trc) { + MachineBasicBlock::iterator useInstItr(mi); + + makeRoomForInsertBefore(mi); + + unsigned miIdx = lis->getInstructionIndex(mi); + + tii->loadRegFromStackSlot(*mi->getParent(), useInstItr, newVReg, ss, trc); + MachineBasicBlock::iterator loadInstItr(mi); + --loadInstItr; + MachineInstr *loadInst = &*loadInstItr; + unsigned loadInstIdx = miIdx - LiveIntervals::InstrSlots::NUM; + + assert(lis->getInstructionFromIndex(loadInstIdx) == 0 && + "Load inst index already in use."); + + lis->InsertMachineInstrInMaps(loadInst, loadInstIdx); + + return loadInstIdx; + } + +}; + +} + + +llvm::Spiller* llvm::createSpiller(MachineFunction *mf, LiveIntervals *lis, + VirtRegMap *vrm) { + return new TrivialSpiller(mf, lis, vrm); +} diff --git a/lib/CodeGen/Spiller.h b/lib/CodeGen/Spiller.h new file mode 100644 index 0000000..f17a0b5 --- /dev/null +++ b/lib/CodeGen/Spiller.h @@ -0,0 +1,32 @@ +//===-- llvm/CodeGen/Spiller.h - Spiller -*- C++ -*------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_SPILLER_H +#define LLVM_CODEGEN_SPILLER_H + +#include <vector> + +namespace llvm { + + /// Spiller interface. + /// + /// Implementations are utility classes which insert spill or remat code on + /// demand. + class Spiller { + public: + virtual ~Spiller() = 0; + virtual std::vector<class LiveInterval*> spill(class LiveInterval *li) = 0; + }; + + /// Create and return a spiller object, as specified on the command line. + Spiller* createSpiller(class MachineFunction *mf, class LiveIntervals *li, + class VirtRegMap *vrm); +} + +#endif |