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/LiveStackAnalysis.h"
  16 #include "llvm/CodeGen/MachineFrameInfo.h"
  17 #include "llvm/CodeGen/MachineFunction.h"
  18 #include "llvm/CodeGen/MachineRegisterInfo.h"
  19 #include "llvm/Target/TargetMachine.h"
  20 #include "llvm/Target/TargetInstrInfo.h"
  21 #include "llvm/Support/Debug.h"
  22 #include "llvm/Support/raw_ostream.h"
  23
  24 using namespace llvm;
  25
  26 Spiller::~Spiller() {}
  27
  28 namespace {
  29
  30 /// Utility class for spillers.
  31 class SpillerBase : public Spiller {
  32 protected:
  33
  34   MachineFunction *mf;
  35   LiveIntervals *lis;
  36   LiveStacks *ls;
  37   MachineFrameInfo *mfi;
  38   MachineRegisterInfo *mri;
  39   const TargetInstrInfo *tii;
  40   VirtRegMap *vrm;
  41
  42   /// Construct a spiller base.
  43   SpillerBase(MachineFunction *mf, LiveIntervals *lis, LiveStacks *ls,
  44               VirtRegMap *vrm) :
  45     mf(mf), lis(lis), ls(ls), vrm(vrm)
  46   {
  47     mfi = mf->getFrameInfo();
  48     mri = &mf->getRegInfo();
  49     tii = mf->getTarget().getInstrInfo();
  50   }
  51
  52   /// Ensures there is space before the given machine instruction, returns the
  53   /// instruction's new number.
  54   unsigned makeSpaceBefore(MachineInstr *mi) {
  55     if (!lis->hasGapBeforeInstr(lis->getInstructionIndex(mi))) {
  56       lis->scaleNumbering(2);
  57       ls->scaleNumbering(2);
  58     }
  59
  60     unsigned miIdx = lis->getInstructionIndex(mi);
  61
  62     assert(lis->hasGapBeforeInstr(miIdx));
  63
  64     return miIdx;
  65   }
  66
  67   /// Ensure there is space after the given machine instruction, returns the
  68   /// instruction's new number.
  69   unsigned makeSpaceAfter(MachineInstr *mi) {
  70     if (!lis->hasGapAfterInstr(lis->getInstructionIndex(mi))) {
  71       lis->scaleNumbering(2);
  72       ls->scaleNumbering(2);
  73     }
  74
  75     unsigned miIdx = lis->getInstructionIndex(mi);
  76
  77     assert(lis->hasGapAfterInstr(miIdx));
  78
  79     return miIdx;
  80   }
  81
  82   /// Insert a store of the given vreg to the given stack slot immediately
  83   /// after the given instruction. Returns the base index of the inserted
  84   /// instruction. The caller is responsible for adding an appropriate
  85   /// LiveInterval to the LiveIntervals analysis.
  86   unsigned insertStoreAfter(MachineInstr *mi, unsigned ss,
  87                           unsigned vreg,
  88                           const TargetRegisterClass *trc) {
  89
  90     MachineBasicBlock::iterator nextInstItr(next(mi));
  91
  92     unsigned miIdx = makeSpaceAfter(mi);
  93
  94     tii->storeRegToStackSlot(*mi->getParent(), nextInstItr, vreg,
  95                              true, ss, trc);
  96     MachineBasicBlock::iterator storeInstItr(next(mi));
  97     MachineInstr *storeInst = &*storeInstItr;
  98     unsigned storeInstIdx = miIdx + LiveInterval::InstrSlots::NUM;
  99
 100     assert(lis->getInstructionFromIndex(storeInstIdx) == 0 &&
 101            "Store inst index already in use.");
 102
 103     lis->InsertMachineInstrInMaps(storeInst, storeInstIdx);
 104
 105     return storeInstIdx;
 106   }
 107
 108   /// Insert a store of the given vreg to the given stack slot immediately
 109   /// before the given instructnion. Returns the base index of the inserted
 110   /// Instruction.
 111   unsigned insertStoreBefore(MachineInstr *mi, unsigned ss,
 112                             unsigned vreg,
 113                             const TargetRegisterClass *trc) {
 114     unsigned miIdx = makeSpaceBefore(mi);
 115
 116     tii->storeRegToStackSlot(*mi->getParent(), mi, vreg, true, ss, trc);
 117     MachineBasicBlock::iterator storeInstItr(prior(mi));
 118     MachineInstr *storeInst = &*storeInstItr;
 119     unsigned storeInstIdx = miIdx - LiveInterval::InstrSlots::NUM;
 120
 121     assert(lis->getInstructionFromIndex(storeInstIdx) == 0 &&
 122            "Store inst index already in use.");
 123
 124     lis->InsertMachineInstrInMaps(storeInst, storeInstIdx);
 125
 126     return storeInstIdx;
 127   }
 128
 129   void insertStoreAfterInstOnInterval(LiveInterval *li,
 130                                       MachineInstr *mi, unsigned ss,
 131                                       unsigned vreg,
 132                                       const TargetRegisterClass *trc) {
 133
 134     unsigned storeInstIdx = insertStoreAfter(mi, ss, vreg, trc);
 135     unsigned start = lis->getDefIndex(lis->getInstructionIndex(mi)),
 136              end = lis->getUseIndex(storeInstIdx);
 137
 138     VNInfo *vni =
 139       li->getNextValue(storeInstIdx, 0, true, lis->getVNInfoAllocator());
 140     li->addKill(vni, storeInstIdx, false);
 141     DEBUG(errs() << "    Inserting store range: [" << start
 142                  << ", " << end << ")\n");
 143     LiveRange lr(start, end, vni);
 144
 145     li->addRange(lr);
 146   }
 147
 148   /// Insert a load of the given vreg from the given stack slot immediately
 149   /// after the given instruction. Returns the base index of the inserted
 150   /// instruction. The caller is responsibel for adding/removing an appropriate
 151   /// range vreg's LiveInterval.
 152   unsigned insertLoadAfter(MachineInstr *mi, unsigned ss,
 153                           unsigned vreg,
 154                           const TargetRegisterClass *trc) {
 155
 156     MachineBasicBlock::iterator nextInstItr(next(mi));
 157
 158     unsigned miIdx = makeSpaceAfter(mi);
 159
 160     tii->loadRegFromStackSlot(*mi->getParent(), nextInstItr, vreg, ss, trc);
 161     MachineBasicBlock::iterator loadInstItr(next(mi));
 162     MachineInstr *loadInst = &*loadInstItr;
 163     unsigned loadInstIdx = miIdx + LiveInterval::InstrSlots::NUM;
 164
 165     assert(lis->getInstructionFromIndex(loadInstIdx) == 0 &&
 166            "Store inst index already in use.");
 167
 168     lis->InsertMachineInstrInMaps(loadInst, loadInstIdx);
 169
 170     return loadInstIdx;
 171   }
 172
 173   /// Insert a load of the given vreg from the given stack slot immediately
 174   /// before the given instruction. Returns the base index of the inserted
 175   /// instruction. The caller is responsible for adding an appropriate
 176   /// LiveInterval to the LiveIntervals analysis.
 177   unsigned insertLoadBefore(MachineInstr *mi, unsigned ss,
 178                             unsigned vreg,
 179                             const TargetRegisterClass *trc) {
 180     unsigned miIdx = makeSpaceBefore(mi);
 181
 182     tii->loadRegFromStackSlot(*mi->getParent(), mi, vreg, ss, trc);
 183     MachineBasicBlock::iterator loadInstItr(prior(mi));
 184     MachineInstr *loadInst = &*loadInstItr;
 185     unsigned loadInstIdx = miIdx - LiveInterval::InstrSlots::NUM;
 186
 187     assert(lis->getInstructionFromIndex(loadInstIdx) == 0 &&
 188            "Load inst index already in use.");
 189
 190     lis->InsertMachineInstrInMaps(loadInst, loadInstIdx);
 191
 192     return loadInstIdx;
 193   }
 194
 195   void insertLoadBeforeInstOnInterval(LiveInterval *li,
 196                                       MachineInstr *mi, unsigned ss,
 197                                       unsigned vreg,
 198                                       const TargetRegisterClass *trc) {
 199
 200     unsigned loadInstIdx = insertLoadBefore(mi, ss, vreg, trc);
 201     unsigned start = lis->getDefIndex(loadInstIdx),
 202              end = lis->getUseIndex(lis->getInstructionIndex(mi));
 203
 204     VNInfo *vni =
 205       li->getNextValue(loadInstIdx, 0, true, lis->getVNInfoAllocator());
 206     li->addKill(vni, lis->getInstructionIndex(mi), false);
 207     DEBUG(errs() << "    Intserting load range: [" << start
 208                  << ", " << end << ")\n");
 209     LiveRange lr(start, end, vni);
 210
 211     li->addRange(lr);
 212   }
 213
 214
 215
 216   /// Add spill ranges for every use/def of the live interval, inserting loads
 217   /// immediately before each use, and stores after each def. No folding is
 218   /// attempted.
 219   std::vector<LiveInterval*> trivialSpillEverywhere(LiveInterval *li) {
 220     DEBUG(errs() << "Spilling everywhere " << *li << "\n");
 221
 222     assert(li->weight != HUGE_VALF &&
 223            "Attempting to spill already spilled value.");
 224
 225     assert(!li->isStackSlot() &&
 226            "Trying to spill a stack slot.");
 227
 228     DEBUG(errs() << "Trivial spill everywhere of reg" << li->reg << "\n");
 229
 230     std::vector<LiveInterval*> added;
 231
 232     const TargetRegisterClass *trc = mri->getRegClass(li->reg);
 233     unsigned ss = vrm->assignVirt2StackSlot(li->reg);
 234
 235     for (MachineRegisterInfo::reg_iterator
 236          regItr = mri->reg_begin(li->reg); regItr != mri->reg_end();) {
 237
 238       MachineInstr *mi = &*regItr;
 239
 240       DEBUG(errs() << "  Processing " << *mi);
 241
 242       do {
 243         ++regItr;
 244       } while (regItr != mri->reg_end() && (&*regItr == mi));
 245
 246       SmallVector<unsigned, 2> indices;
 247       bool hasUse = false;
 248       bool hasDef = false;
 249
 250       for (unsigned i = 0; i != mi->getNumOperands(); ++i) {
 251         MachineOperand &op = mi->getOperand(i);
 252
 253         if (!op.isReg() || op.getReg() != li->reg)
 254           continue;
 255
 256         hasUse |= mi->getOperand(i).isUse();
 257         hasDef |= mi->getOperand(i).isDef();
 258
 259         indices.push_back(i);
 260       }
 261
 262       unsigned newVReg = mri->createVirtualRegister(trc);
 263       vrm->grow();
 264       vrm->assignVirt2StackSlot(newVReg, ss);
 265
 266       LiveInterval *newLI = &lis->getOrCreateInterval(newVReg);
 267       newLI->weight = HUGE_VALF;
 268
 269       for (unsigned i = 0; i < indices.size(); ++i) {
 270         mi->getOperand(indices[i]).setReg(newVReg);
 271
 272         if (mi->getOperand(indices[i]).isUse()) {
 273           mi->getOperand(indices[i]).setIsKill(true);
 274         }
 275       }
 276
 277       assert(hasUse || hasDef);
 278
 279       if (hasUse) {
 280         insertLoadBeforeInstOnInterval(newLI, mi, ss, newVReg, trc);
 281       }
 282
 283       if (hasDef) {
 284         insertStoreAfterInstOnInterval(newLI, mi, ss, newVReg, trc);
 285       }
 286
 287       added.push_back(newLI);
 288     }
 289
 290     return added;
 291   }
 292
 293 };
 294
 295
 296 /// Spills any live range using the spill-everywhere method with no attempt at
 297 /// folding.
 298 class TrivialSpiller : public SpillerBase {
 299 public:
 300
 301   TrivialSpiller(MachineFunction *mf, LiveIntervals *lis, LiveStacks *ls,
 302                  VirtRegMap *vrm) :
 303     SpillerBase(mf, lis, ls, vrm) {}
 304
 305   std::vector<LiveInterval*> spill(LiveInterval *li) {
 306     return trivialSpillEverywhere(li);
 307   }
 308
 309   std::vector<LiveInterval*> intraBlockSplit(LiveInterval *li, VNInfo *valno)  {
 310     std::vector<LiveInterval*> spillIntervals;
 311
 312     if (!valno->isDefAccurate() && !valno->isPHIDef()) {
 313       // Early out for values which have no well defined def point.
 314       return spillIntervals;
 315     }
 316
 317     // Ok.. we should be able to proceed...
 318     const TargetRegisterClass *trc = mri->getRegClass(li->reg);
 319     unsigned ss = vrm->assignVirt2StackSlot(li->reg);
 320     vrm->grow();
 321     vrm->assignVirt2StackSlot(li->reg, ss);
 322
 323     MachineInstr *mi = 0;
 324     unsigned storeIdx = 0;
 325
 326     if (valno->isDefAccurate()) {
 327       // If we have an accurate def we can just grab an iterator to the instr
 328       // after the def.
 329       mi = lis->getInstructionFromIndex(valno->def);
 330       storeIdx = insertStoreAfter(mi, ss, li->reg, trc) +
 331         LiveInterval::InstrSlots::DEF;
 332     } else {
 333       // if we get here we have a PHI def.
 334       mi = &lis->getMBBFromIndex(valno->def)->front();
 335       storeIdx = insertStoreBefore(mi, ss, li->reg, trc) +
 336         LiveInterval::InstrSlots::DEF;
 337     }
 338
 339     MachineBasicBlock *defBlock = mi->getParent();
 340     unsigned loadIdx = 0;
 341
 342     // Now we need to find the load...
 343     MachineBasicBlock::iterator useItr(mi);
 344     for (; !useItr->readsRegister(li->reg); ++useItr) {}
 345
 346     if (useItr != defBlock->end()) {
 347       MachineInstr *loadInst = useItr;
 348       loadIdx = insertLoadBefore(loadInst, ss, li->reg, trc) +
 349         LiveInterval::InstrSlots::USE;
 350     }
 351     else {
 352       MachineInstr *loadInst = &defBlock->back();
 353       loadIdx = insertLoadAfter(loadInst, ss, li->reg, trc) +
 354         LiveInterval::InstrSlots::USE;
 355     }
 356
 357     li->removeRange(storeIdx, loadIdx, true);
 358
 359     return spillIntervals;
 360   }
 361
 362 };
 363
 364 }
 365
 366 llvm::Spiller* llvm::createSpiller(MachineFunction *mf, LiveIntervals *lis,
 367                                    LiveStacks *ls, VirtRegMap *vrm) {
 368   return new TrivialSpiller(mf, lis, ls, vrm);
 369 }