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/MachineFunction.h"
  16 #include "llvm/CodeGen/MachineRegisterInfo.h"
  17 #include "llvm/CodeGen/MachineFrameInfo.h"
  18 #include "llvm/Target/TargetMachine.h"
  19 #include "llvm/Target/TargetInstrInfo.h"
  20 #include "llvm/Support/Debug.h"
  21
  22 #include <algorithm>
  23 #include <map>
  24
  25 using namespace llvm;
  26
  27 Spiller::~Spiller() {}
  28
  29 namespace {
  30
  31 class TrivialSpiller : public Spiller {
  32 public:
  33   TrivialSpiller(MachineFunction *mf, LiveIntervals *lis, VirtRegMap *vrm) :
  34     mf(mf), lis(lis), vrm(vrm)
  35   {
  36     mfi = mf->getFrameInfo();
  37     mri = &mf->getRegInfo();
  38     tii = mf->getTarget().getInstrInfo();
  39   }
  40
  41   std::vector<LiveInterval*> spill(LiveInterval *li) {
  42
  43     DOUT << "Trivial spiller spilling " << *li << "\n";
  44
  45     assert(li->weight != HUGE_VALF &&
  46            "Attempting to spill already spilled value.");
  47
  48     assert(!li->isStackSlot() &&
  49            "Trying to spill a stack slot.");
  50
  51     std::vector<LiveInterval*> added;
  52
  53     const TargetRegisterClass *trc = mri->getRegClass(li->reg);
  54     /*unsigned ss = mfi->CreateStackObject(trc->getSize(),
  55                                          trc->getAlignment());*/
  56     unsigned ss = vrm->assignVirt2StackSlot(li->reg);
  57
  58     MachineRegisterInfo::reg_iterator regItr = mri->reg_begin(li->reg);
  59
  60     while (regItr != mri->reg_end()) {
  61
  62       MachineInstr *mi = &*regItr;
  63
  64       SmallVector<unsigned, 2> indices;
  65       bool hasUse = false;
  66       bool hasDef = false;
  67
  68       for (unsigned i = 0; i != mi->getNumOperands(); ++i) {
  69         MachineOperand &op = mi->getOperand(i);
  70
  71         if (!op.isReg() || op.getReg() != li->reg)
  72           continue;
  73
  74         hasUse |= mi->getOperand(i).isUse();
  75         hasDef |= mi->getOperand(i).isDef();
  76
  77         indices.push_back(i);
  78       }
  79
  80       unsigned newVReg = mri->createVirtualRegister(trc);
  81       LiveInterval *newLI = &lis->getOrCreateInterval(newVReg);
  82       newLI->weight = HUGE_VALF;
  83
  84       vrm->grow();
  85       vrm->assignVirt2StackSlot(newVReg, ss);
  86
  87       for (unsigned i = 0; i < indices.size(); ++i) {
  88         mi->getOperand(indices[i]).setReg(newVReg);
  89
  90         if (mi->getOperand(indices[i]).isUse()) {
  91           mi->getOperand(indices[i]).setIsKill(true);
  92         }
  93       }
  94
  95       if (hasUse) {
  96         unsigned loadInstIdx = insertLoadFor(mi, ss, newVReg, trc);
  97         unsigned start = lis->getDefIndex(loadInstIdx),
  98                  end = lis->getUseIndex(lis->getInstructionIndex(mi));
  99
 100         VNInfo *vni =
 101           newLI->getNextValue(loadInstIdx, 0, lis->getVNInfoAllocator());
 102         vni->kills.push_back(lis->getInstructionIndex(mi));
 103         LiveRange lr(start, end, vni);
 104
 105         newLI->addRange(lr);
 106         added.push_back(newLI);
 107       }
 108
 109       if (hasDef) {
 110         unsigned storeInstIdx = insertStoreFor(mi, ss, newVReg, trc);
 111         unsigned start = lis->getDefIndex(lis->getInstructionIndex(mi)),
 112                  end = lis->getUseIndex(storeInstIdx);
 113
 114         VNInfo *vni =
 115           newLI->getNextValue(storeInstIdx, 0, lis->getVNInfoAllocator());
 116         vni->kills.push_back(storeInstIdx);
 117         LiveRange lr(start, end, vni);
 118
 119         newLI->addRange(lr);
 120         added.push_back(newLI);
 121       }
 122
 123       regItr = mri->reg_begin(li->reg);
 124     }
 125
 126
 127     return added;
 128   }
 129
 130
 131 private:
 132
 133   MachineFunction *mf;
 134   LiveIntervals *lis;
 135   MachineFrameInfo *mfi;
 136   MachineRegisterInfo *mri;
 137   const TargetInstrInfo *tii;
 138   VirtRegMap *vrm;
 139
 140
 141
 142   void makeRoomForInsertBefore(MachineInstr *mi) {
 143     if (!lis->hasGapBeforeInstr(lis->getInstructionIndex(mi))) {
 144       lis->computeNumbering();
 145     }
 146
 147     assert(lis->hasGapBeforeInstr(lis->getInstructionIndex(mi)));
 148   }
 149
 150   unsigned insertStoreFor(MachineInstr *mi, unsigned ss,
 151                           unsigned newVReg,
 152                           const TargetRegisterClass *trc) {
 153     MachineBasicBlock::iterator nextInstItr(mi);
 154     ++nextInstItr;
 155
 156     makeRoomForInsertBefore(&*nextInstItr);
 157
 158     unsigned miIdx = lis->getInstructionIndex(mi);
 159
 160     tii->storeRegToStackSlot(*mi->getParent(), nextInstItr, newVReg,
 161                              true, ss, trc);
 162     MachineBasicBlock::iterator storeInstItr(mi);
 163     ++storeInstItr;
 164     MachineInstr *storeInst = &*storeInstItr;
 165     unsigned storeInstIdx = miIdx + LiveIntervals::InstrSlots::NUM;
 166
 167     assert(lis->getInstructionFromIndex(storeInstIdx) == 0 &&
 168            "Store inst index already in use.");
 169
 170     lis->InsertMachineInstrInMaps(storeInst, storeInstIdx);
 171
 172     return storeInstIdx;
 173   }
 174
 175   unsigned insertLoadFor(MachineInstr *mi, unsigned ss,
 176                          unsigned newVReg,
 177                          const TargetRegisterClass *trc) {
 178     MachineBasicBlock::iterator useInstItr(mi);
 179
 180     makeRoomForInsertBefore(mi);
 181
 182     unsigned miIdx = lis->getInstructionIndex(mi);
 183
 184     tii->loadRegFromStackSlot(*mi->getParent(), useInstItr, newVReg, ss, trc);
 185     MachineBasicBlock::iterator loadInstItr(mi);
 186     --loadInstItr;
 187     MachineInstr *loadInst = &*loadInstItr;
 188     unsigned loadInstIdx = miIdx - LiveIntervals::InstrSlots::NUM;
 189
 190     assert(lis->getInstructionFromIndex(loadInstIdx) == 0 &&
 191            "Load inst index already in use.");
 192
 193     lis->InsertMachineInstrInMaps(loadInst, loadInstIdx);
 194
 195     return loadInstIdx;
 196   }
 197
 198 };
 199
 200 }
 201
 202
 203 llvm::Spiller* llvm::createSpiller(MachineFunction *mf, LiveIntervals *lis,
 204                                    VirtRegMap *vrm) {
 205   return new TrivialSpiller(mf, lis, vrm);
 206 }