lib/CodeGen/Spiller.cpp

   1 //===-- llvm/CodeGen/Spiller.cpp -  Spiller -------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #define DEBUG_TYPE "spiller"
  11
  12 #include "Spiller.h"
  13 #include "VirtRegMap.h"
  14 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  15 #include "llvm/CodeGen/MachineFrameInfo.h"
  16 #include "llvm/CodeGen/MachineFunction.h"
  17 #include "llvm/CodeGen/MachineRegisterInfo.h"
  18 #include "llvm/Target/TargetMachine.h"
  19 #include "llvm/Target/TargetInstrInfo.h"
  20 #include "llvm/Support/CommandLine.h"
  21 #include "llvm/Support/Debug.h"
  22 #include "llvm/Support/raw_ostream.h"
  23
  24 using namespace llvm;
  25
  26 namespace {
  27   enum SpillerName { trivial, standard };
  28 }
  29
  30 static cl::opt<SpillerName>
  31 spillerOpt("spiller",
  32            cl::desc("Spiller to use: (default: standard)"),
  33            cl::Prefix,
  34            cl::values(clEnumVal(trivial, "trivial spiller"),
  35                       clEnumVal(standard, "default spiller"),
  36                       clEnumValEnd),
  37            cl::init(standard));
  38
  39 Spiller::~Spiller() {}
  40
  41 namespace {
  42
  43 /// Utility class for spillers.
  44 class SpillerBase : public Spiller {
  45 protected:
  46
  47   MachineFunction *mf;
  48   LiveIntervals *lis;
  49   MachineFrameInfo *mfi;
  50   MachineRegisterInfo *mri;
  51   const TargetInstrInfo *tii;
  52   VirtRegMap *vrm;
  53
  54   /// Construct a spiller base.
  55   SpillerBase(MachineFunction *mf, LiveIntervals *lis, VirtRegMap *vrm)
  56     : mf(mf), lis(lis), vrm(vrm)
  57   {
  58     mfi = mf->getFrameInfo();
  59     mri = &mf->getRegInfo();
  60     tii = mf->getTarget().getInstrInfo();
  61   }
  62
  63   /// Add spill ranges for every use/def of the live interval, inserting loads
  64   /// immediately before each use, and stores after each def. No folding or
  65   /// remat is attempted.
  66   std::vector<LiveInterval*> trivialSpillEverywhere(LiveInterval *li) {
  67     DEBUG(errs() << "Spilling everywhere " << *li << "\n");
  68
  69     assert(li->weight != HUGE_VALF &&
  70            "Attempting to spill already spilled value.");
  71
  72     assert(!li->isStackSlot() &&
  73            "Trying to spill a stack slot.");
  74
  75     DEBUG(errs() << "Trivial spill everywhere of reg" << li->reg << "\n");
  76
  77     std::vector<LiveInterval*> added;
  78
  79     const TargetRegisterClass *trc = mri->getRegClass(li->reg);
  80     unsigned ss = vrm->assignVirt2StackSlot(li->reg);
  81
  82     // Iterate over reg uses/defs.
  83     for (MachineRegisterInfo::reg_iterator
  84          regItr = mri->reg_begin(li->reg); regItr != mri->reg_end();) {
  85
  86       // Grab the use/def instr.
  87       MachineInstr *mi = &*regItr;
  88
  89       DEBUG(errs() << "  Processing " << *mi);
  90
  91       // Step regItr to the next use/def instr.
  92       do {
  93         ++regItr;
  94       } while (regItr != mri->reg_end() && (&*regItr == mi));
  95
  96       // Collect uses & defs for this instr.
  97       SmallVector<unsigned, 2> indices;
  98       bool hasUse = false;
  99       bool hasDef = false;
 100       for (unsigned i = 0; i != mi->getNumOperands(); ++i) {
 101         MachineOperand &op = mi->getOperand(i);
 102         if (!op.isReg() || op.getReg() != li->reg)
 103           continue;
 104         hasUse |= mi->getOperand(i).isUse();
 105         hasDef |= mi->getOperand(i).isDef();
 106         indices.push_back(i);
 107       }
 108
 109       // Create a new vreg & interval for this instr.
 110       unsigned newVReg = mri->createVirtualRegister(trc);
 111       vrm->grow();
 112       vrm->assignVirt2StackSlot(newVReg, ss);
 113       LiveInterval *newLI = &lis->getOrCreateInterval(newVReg);
 114       newLI->weight = HUGE_VALF;
 115
 116       // Update the reg operands & kill flags.
 117       for (unsigned i = 0; i < indices.size(); ++i) {
 118         unsigned mopIdx = indices[i];
 119         MachineOperand &mop = mi->getOperand(mopIdx);
 120         mop.setReg(newVReg);
 121         if (mop.isUse() && !mi->isRegTiedToDefOperand(mopIdx)) {
 122           mop.setIsKill(true);
 123         }
 124       }
 125       assert(hasUse || hasDef);
 126
 127       // Insert reload if necessary.
 128       MachineBasicBlock::iterator miItr(mi);
 129       if (hasUse) {
 130         tii->loadRegFromStackSlot(*mi->getParent(), miItr, newVReg, ss, trc);
 131         MachineInstr *loadInstr(prior(miItr));
 132         SlotIndex loadIndex =
 133           lis->InsertMachineInstrInMaps(loadInstr).getDefIndex();
 134         SlotIndex endIndex = loadIndex.getNextIndex();
 135         VNInfo *loadVNI =
 136           newLI->getNextValue(loadIndex, 0, true, lis->getVNInfoAllocator());
 137         loadVNI->addKill(endIndex);
 138         newLI->addRange(LiveRange(loadIndex, endIndex, loadVNI));
 139       }
 140
 141       // Insert store if necessary.
 142       if (hasDef) {
 143         tii->storeRegToStackSlot(*mi->getParent(), llvm::next(miItr), newVReg, true,
 144                                  ss, trc);
 145         MachineInstr *storeInstr(llvm::next(miItr));
 146         SlotIndex storeIndex =
 147           lis->InsertMachineInstrInMaps(storeInstr).getDefIndex();
 148         SlotIndex beginIndex = storeIndex.getPrevIndex();
 149         VNInfo *storeVNI =
 150           newLI->getNextValue(beginIndex, 0, true, lis->getVNInfoAllocator());
 151         storeVNI->addKill(storeIndex);
 152         newLI->addRange(LiveRange(beginIndex, storeIndex, storeVNI));
 153       }
 154
 155       added.push_back(newLI);
 156     }
 157
 158     return added;
 159   }
 160
 161 };
 162
 163
 164 /// Spills any live range using the spill-everywhere method with no attempt at
 165 /// folding.
 166 class TrivialSpiller : public SpillerBase {
 167 public:
 168
 169   TrivialSpiller(MachineFunction *mf, LiveIntervals *lis, VirtRegMap *vrm)
 170     : SpillerBase(mf, lis, vrm) {}
 171
 172   std::vector<LiveInterval*> spill(LiveInterval *li,
 173                                    SmallVectorImpl<LiveInterval*> &spillIs) {
 174     // Ignore spillIs - we don't use it.
 175     return trivialSpillEverywhere(li);
 176   }
 177
 178 };
 179
 180 /// Falls back on LiveIntervals::addIntervalsForSpills.
 181 class StandardSpiller : public Spiller {
 182 private:
 183   LiveIntervals *lis;
 184   const MachineLoopInfo *loopInfo;
 185   VirtRegMap *vrm;
 186 public:
 187   StandardSpiller(MachineFunction *mf, LiveIntervals *lis,
 188                   const MachineLoopInfo *loopInfo, VirtRegMap *vrm)
 189     : lis(lis), loopInfo(loopInfo), vrm(vrm) {}
 190
 191   /// Falls back on LiveIntervals::addIntervalsForSpills.
 192   std::vector<LiveInterval*> spill(LiveInterval *li,
 193                                    SmallVectorImpl<LiveInterval*> &spillIs) {
 194     return lis->addIntervalsForSpills(*li, spillIs, loopInfo, *vrm);
 195   }
 196
 197 };
 198
 199 }
 200
 201 llvm::Spiller* llvm::createSpiller(MachineFunction *mf, LiveIntervals *lis,
 202                                    const MachineLoopInfo *loopInfo,
 203                                    VirtRegMap *vrm) {
 204   switch (spillerOpt) {
 205     case trivial: return new TrivialSpiller(mf, lis, vrm); break;
 206     case standard: return new StandardSpiller(mf, lis, loopInfo, vrm); break;
 207     default: llvm_unreachable("Unreachable!"); break;
 208   }
 209 }