1a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block//===-- llvm/CodeGen/Spiller.cpp - Spiller -------------------------------===// 2a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// 3a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// The LLVM Compiler Infrastructure 4a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// 5a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// This file is distributed under the University of Illinois Open Source 6a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// License. See LICENSE.TXT for details. 7a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// 8a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block//===----------------------------------------------------------------------===// 9a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 10a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#define DEBUG_TYPE "spiller" 11a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 12a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#include "Spiller.h" 13a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#include "VirtRegMap.h" 14a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#include "llvm/CodeGen/LiveIntervalAnalysis.h" 15a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#include "llvm/CodeGen/LiveRangeEdit.h" 16a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#include "llvm/CodeGen/LiveStackAnalysis.h" 17a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#include "llvm/CodeGen/MachineFrameInfo.h" 18a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#include "llvm/CodeGen/MachineFunction.h" 19a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#include "llvm/CodeGen/MachineInstrBuilder.h" 20a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#include "llvm/CodeGen/MachineLoopInfo.h" 21a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#include "llvm/CodeGen/MachineRegisterInfo.h" 22a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#include "llvm/Target/TargetMachine.h" 23a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#include "llvm/Target/TargetInstrInfo.h" 24a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#include "llvm/Support/CommandLine.h" 25a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#include "llvm/Support/Debug.h" 26a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#include "llvm/Support/ErrorHandling.h" 27a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#include "llvm/Support/raw_ostream.h" 28a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 29a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockusing namespace llvm; 30a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 31a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocknamespace { 32a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block enum SpillerName { trivial, inline_ }; 33589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch} 3469a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 3569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdochstatic cl::opt<SpillerName> 36a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockspillerOpt("spiller", 37a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block cl::desc("Spiller to use: (default: standard)"), 38a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block cl::Prefix, 39a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block cl::values(clEnumVal(trivial, "trivial spiller"), 40a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block clEnumValN(inline_, "inline", "inline spiller"), 41a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block clEnumValEnd), 42a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block cl::init(trivial)); 43a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 44a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Spiller virtual destructor implementation. 45a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockSpiller::~Spiller() {} 46a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 47a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocknamespace { 48a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 49a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/// Utility class for spillers. 50a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockclass SpillerBase : public Spiller { 51a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockprotected: 52a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block MachineFunctionPass *pass; 53a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block MachineFunction *mf; 54a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block VirtRegMap *vrm; 55a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block LiveIntervals *lis; 56a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block MachineFrameInfo *mfi; 573ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch MachineRegisterInfo *mri; 583ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch const TargetInstrInfo *tii; 59a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block const TargetRegisterInfo *tri; 60a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 6169a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch /// Construct a spiller base. 6269a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch SpillerBase(MachineFunctionPass &pass, MachineFunction &mf, VirtRegMap &vrm) 63a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block : pass(&pass), mf(&mf), vrm(&vrm) 64a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block { 6569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch lis = &pass.getAnalysis<LiveIntervals>(); 66a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block mfi = mf.getFrameInfo(); 6769a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch mri = &mf.getRegInfo(); 68589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch tii = mf.getTarget().getInstrInfo(); 6969a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch tri = mf.getTarget().getRegisterInfo(); 703ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 7169a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 723ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch /// Add spill ranges for every use/def of the live interval, inserting loads 7369a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch /// immediately before each use, and stores after each def. No folding or 743ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch /// remat is attempted. 7569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch void trivialSpillEverywhere(LiveRangeEdit& LRE) { 763ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveInterval* li = &LRE.getParent(); 7769a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 783ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch DEBUG(dbgs() << "Spilling everywhere " << *li << "\n"); 793ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 8069a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch assert(li->weight != HUGE_VALF && 813ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch "Attempting to spill already spilled value."); 823ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 8369a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch assert(!TargetRegisterInfo::isStackSlot(li->reg) && 843ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch "Trying to spill a stack slot."); 853ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 8669a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch DEBUG(dbgs() << "Trivial spill everywhere of reg" << li->reg << "\n"); 873ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 883ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch const TargetRegisterClass *trc = mri->getRegClass(li->reg); 893ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch unsigned ss = vrm->assignVirt2StackSlot(li->reg); 903ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 913ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Iterate over reg uses/defs. 923ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch for (MachineRegisterInfo::reg_iterator 9369a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch regItr = mri->reg_begin(li->reg); regItr != mri->reg_end();) { 943ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 9569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch // Grab the use/def instr. 963ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch MachineInstr *mi = &*regItr; 973ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 983ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch DEBUG(dbgs() << " Processing " << *mi); 993ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1003ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Step regItr to the next use/def instr. 1013ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch do { 10269a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch ++regItr; 10369a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch } while (regItr != mri->reg_end() && (&*regItr == mi)); 1043ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 10569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch // Collect uses & defs for this instr. 1063ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch SmallVector<unsigned, 2> indices; 1073ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch bool hasUse = false; 1083ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch bool hasDef = false; 10969a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch for (unsigned i = 0; i != mi->getNumOperands(); ++i) { 110a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block MachineOperand &op = mi->getOperand(i); 1113ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!op.isReg() || op.getReg() != li->reg) 1123ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch continue; 113a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block hasUse |= mi->getOperand(i).isUse(); 11469a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch hasDef |= mi->getOperand(i).isDef(); 11569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch indices.push_back(i); 11669a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch } 117a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 11869a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch // Create a new vreg & interval for this instr. 11969a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch LiveInterval *newLI = &LRE.create(); 12069a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch newLI->weight = HUGE_VALF; 12169a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 12269a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch // Update the reg operands & kill flags. 12369a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch for (unsigned i = 0; i < indices.size(); ++i) { 12469a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch unsigned mopIdx = indices[i]; 12569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch MachineOperand &mop = mi->getOperand(mopIdx); 12669a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch mop.setReg(newLI->reg); 12769a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch if (mop.isUse() && !mi->isRegTiedToDefOperand(mopIdx)) { 12869a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch mop.setIsKill(true); 12969a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch } 13069a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch } 13169a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch assert(hasUse || hasDef); 13269a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 13369a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch // Insert reload if necessary. 13469a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch MachineBasicBlock::iterator miItr(mi); 13569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch if (hasUse) { 136a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tii->loadRegFromStackSlot(*mi->getParent(), miItr, newLI->reg, ss, trc, 13769a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch tri); 13869a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch MachineInstr *loadInstr(prior(miItr)); 13969a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch SlotIndex loadIndex = 14069a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch lis->InsertMachineInstrInMaps(loadInstr).getRegSlot(); 14169a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch SlotIndex endIndex = loadIndex.getNextIndex(); 14269a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch VNInfo *loadVNI = 14369a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch newLI->getNextValue(loadIndex, lis->getVNInfoAllocator()); 14469a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch newLI->addRange(LiveRange(loadIndex, endIndex, loadVNI)); 14569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch } 146a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 14769a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch // Insert store if necessary. 14869a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch if (hasDef) { 1493ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch tii->storeRegToStackSlot(*mi->getParent(), llvm::next(miItr),newLI->reg, 1503ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch true, ss, trc, tri); 1513ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch MachineInstr *storeInstr(llvm::next(miItr)); 1523ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch SlotIndex storeIndex = 1533ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch lis->InsertMachineInstrInMaps(storeInstr).getRegSlot(); 1543ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch SlotIndex beginIndex = storeIndex.getPrevIndex(); 1553ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch VNInfo *storeVNI = 1563ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch newLI->getNextValue(beginIndex, lis->getVNInfoAllocator()); 1573ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch newLI->addRange(LiveRange(beginIndex, storeIndex, storeVNI)); 1583ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 1593ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 1603ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 1613ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch}; 1623ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1633ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch} // end anonymous namespace 1643ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1653ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochnamespace { 1663ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1673ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch/// Spills any live range using the spill-everywhere method with no attempt at 1683ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch/// folding. 1693ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochclass TrivialSpiller : public SpillerBase { 1703ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochpublic: 1713ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1723ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch TrivialSpiller(MachineFunctionPass &pass, MachineFunction &mf, 1733ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch VirtRegMap &vrm) 1743ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch : SpillerBase(pass, mf, vrm) {} 1753ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1763ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch void spill(LiveRangeEdit &LRE) { 1773ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Ignore spillIs - we don't use it. 1783ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch trivialSpillEverywhere(LRE); 1793ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 1803ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch}; 1813ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1823ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch} // end anonymous namespace 1833ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1843ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid Spiller::anchor() { } 18569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 18669a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdochllvm::Spiller* llvm::createSpiller(MachineFunctionPass &pass, 187a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block MachineFunction &mf, 188a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block VirtRegMap &vrm) { 189 switch (spillerOpt) { 190 case trivial: return new TrivialSpiller(pass, mf, vrm); 191 case inline_: return createInlineSpiller(pass, mf, vrm); 192 } 193 llvm_unreachable("Invalid spiller optimization"); 194} 195