Spiller.cpp revision 38283e23df5aa748ec3bb5f02f14f1741cf491ce 
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
24using namespace llvm;
25
26Spiller::~Spiller() {}
27
28namespace {
29
30/// Utility class for spillers.
31class SpillerBase : public Spiller {
32protected:
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  /// Add spill ranges for every use/def of the live interval, inserting loads
53  /// immediately before each use, and stores after each def. No folding or
54  /// remat is attempted.
55  std::vector<LiveInterval*> trivialSpillEverywhere(LiveInterval *li) {
56    DEBUG(errs() << "Spilling everywhere " << *li << "\n");
57
58    assert(li->weight != HUGE_VALF &&
59           "Attempting to spill already spilled value.");
60
61    assert(!li->isStackSlot() &&
62           "Trying to spill a stack slot.");
63
64    DEBUG(errs() << "Trivial spill everywhere of reg" << li->reg << "\n");
65
66    std::vector<LiveInterval*> added;
67
68    const TargetRegisterClass *trc = mri->getRegClass(li->reg);
69    unsigned ss = vrm->assignVirt2StackSlot(li->reg);
70
71    // Iterate over reg uses/defs.
72    for (MachineRegisterInfo::reg_iterator
73         regItr = mri->reg_begin(li->reg); regItr != mri->reg_end();) {
74
75      // Grab the use/def instr.
76      MachineInstr *mi = &*regItr;
77
78      DEBUG(errs() << "  Processing " << *mi);
79
80      // Step regItr to the next use/def instr.
81      do {
82        ++regItr;
83      } while (regItr != mri->reg_end() && (&*regItr == mi));
84
85      // Collect uses & defs for this instr.
86      SmallVector<unsigned, 2> indices;
87      bool hasUse = false;
88      bool hasDef = false;
89      for (unsigned i = 0; i != mi->getNumOperands(); ++i) {
90        MachineOperand &op = mi->getOperand(i);
91        if (!op.isReg() || op.getReg() != li->reg)
92          continue;
93        hasUse |= mi->getOperand(i).isUse();
94        hasDef |= mi->getOperand(i).isDef();
95        indices.push_back(i);
96      }
97
98      // Create a new vreg & interval for this instr.
99      unsigned newVReg = mri->createVirtualRegister(trc);
100      vrm->grow();
101      vrm->assignVirt2StackSlot(newVReg, ss);
102      LiveInterval *newLI = &lis->getOrCreateInterval(newVReg);
103      newLI->weight = HUGE_VALF;
104
105      // Update the reg operands & kill flags.
106      for (unsigned i = 0; i < indices.size(); ++i) {
107        unsigned mopIdx = indices[i];
108        MachineOperand &mop = mi->getOperand(mopIdx);
109        mop.setReg(newVReg);
110        if (mop.isUse() && !mi->isRegTiedToDefOperand(mopIdx)) {
111          mop.setIsKill(true);
112        }
113      }
114      assert(hasUse || hasDef);
115
116      // Insert reload if necessary.
117      MachineBasicBlock::iterator miItr(mi);
118      if (hasUse) {
119        tii->loadRegFromStackSlot(*mi->getParent(), miItr, newVReg, ss, trc);
120        MachineInstr *loadInstr(prior(miItr));
121        SlotIndex loadIndex =
122          lis->InsertMachineInstrInMaps(loadInstr).getDefIndex();
123        SlotIndex endIndex = loadIndex.getNextIndex();
124        VNInfo *loadVNI =
125          newLI->getNextValue(loadIndex, 0, true, lis->getVNInfoAllocator());
126        loadVNI->addKill(endIndex);
127        newLI->addRange(LiveRange(loadIndex, endIndex, loadVNI));
128      }
129
130      // Insert store if necessary.
131      if (hasDef) {
132        tii->storeRegToStackSlot(*mi->getParent(), next(miItr), newVReg, true,
133                                 ss, trc);
134        MachineInstr *storeInstr(next(miItr));
135        SlotIndex storeIndex =
136          lis->InsertMachineInstrInMaps(storeInstr).getDefIndex();
137        SlotIndex beginIndex = storeIndex.getPrevIndex();
138        VNInfo *storeVNI =
139          newLI->getNextValue(beginIndex, 0, true, lis->getVNInfoAllocator());
140        storeVNI->addKill(storeIndex);
141        newLI->addRange(LiveRange(beginIndex, storeIndex, storeVNI));
142      }
143
144      added.push_back(newLI);
145    }
146
147    return added;
148  }
149
150};
151
152
153/// Spills any live range using the spill-everywhere method with no attempt at
154/// folding.
155class TrivialSpiller : public SpillerBase {
156public:
157
158  TrivialSpiller(MachineFunction *mf, LiveIntervals *lis, LiveStacks *ls,
159                 VirtRegMap *vrm) :
160    SpillerBase(mf, lis, ls, vrm) {}
161
162  std::vector<LiveInterval*> spill(LiveInterval *li) {
163    return trivialSpillEverywhere(li);
164  }
165
166};
167
168}
169
170llvm::Spiller* llvm::createSpiller(MachineFunction *mf, LiveIntervals *lis,
171                                   LiveStacks *ls, VirtRegMap *vrm) {
172  return new TrivialSpiller(mf, lis, ls, vrm);
173}
174