← Back to branch summary

~pali/+junk/llvm-toolchain-3.7

« back to all changes in this revision

Viewing changes to lib/CodeGen/RegisterScavenging.cpp

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2015-07-15 17:51:08 UTC
  • Revision ID: package-import@ubuntu.com-20150715175108-l8mynwovkx4zx697
Tags: upstream-3.7~+rc2
Import upstream version 3.7~+rc2

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/CodeGen/RegisterScavenging.cpp
 
1
//===-- RegisterScavenging.cpp - Machine register scavenging --------------===//
 
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
// This file implements the machine register scavenger. It can provide
 
11
// information, such as unused registers, at any point in a machine basic block.
 
12
// It also provides a mechanism to make registers available by evicting them to
 
13
// spill slots.
 
14
//
 
15
//===----------------------------------------------------------------------===//
 
16
 
 
17
#include "llvm/CodeGen/RegisterScavenging.h"
 
18
#include "llvm/CodeGen/MachineBasicBlock.h"
 
19
#include "llvm/CodeGen/MachineFrameInfo.h"
 
20
#include "llvm/CodeGen/MachineFunction.h"
 
21
#include "llvm/CodeGen/MachineInstr.h"
 
22
#include "llvm/CodeGen/MachineRegisterInfo.h"
 
23
#include "llvm/Support/Debug.h"
 
24
#include "llvm/Support/ErrorHandling.h"
 
25
#include "llvm/Support/raw_ostream.h"
 
26
#include "llvm/Target/TargetInstrInfo.h"
 
27
#include "llvm/Target/TargetRegisterInfo.h"
 
28
#include "llvm/Target/TargetSubtargetInfo.h"
 
29
using namespace llvm;
 
30
 
 
31
#define DEBUG_TYPE "reg-scavenging"
 
32
 
 
33
/// setUsed - Set the register units of this register as used.
 
34
void RegScavenger::setRegUsed(unsigned Reg) {
 
35
  for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI)
 
36
    RegUnitsAvailable.reset(*RUI);
 
37
}
 
38
 
 
39
void RegScavenger::initRegState() {
 
40
  for (SmallVectorImpl<ScavengedInfo>::iterator I = Scavenged.begin(),
 
41
         IE = Scavenged.end(); I != IE; ++I) {
 
42
    I->Reg = 0;
 
43
    I->Restore = nullptr;
 
44
  }
 
45
 
 
46
  // All register units start out unused.
 
47
  RegUnitsAvailable.set();
 
48
 
 
49
  if (!MBB)
 
50
    return;
 
51
 
 
52
  // Live-in registers are in use.
 
53
  for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(),
 
54
         E = MBB->livein_end(); I != E; ++I)
 
55
    setRegUsed(*I);
 
56
 
 
57
  // Pristine CSRs are also unavailable.
 
58
  const MachineFunction &MF = *MBB->getParent();
 
59
  BitVector PR = MF.getFrameInfo()->getPristineRegs(MF);
 
60
  for (int I = PR.find_first(); I>0; I = PR.find_next(I))
 
61
    setRegUsed(I);
 
62
}
 
63
 
 
64
void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
 
65
  MachineFunction &MF = *mbb->getParent();
 
66
  TII = MF.getSubtarget().getInstrInfo();
 
67
  TRI = MF.getSubtarget().getRegisterInfo();
 
68
  MRI = &MF.getRegInfo();
 
69
 
 
70
  assert((NumRegUnits == 0 || NumRegUnits == TRI->getNumRegUnits()) &&
 
71
         "Target changed?");
 
72
 
 
73
  // It is not possible to use the register scavenger after late optimization
 
74
  // passes that don't preserve accurate liveness information.
 
75
  assert(MRI->tracksLiveness() &&
 
76
         "Cannot use register scavenger with inaccurate liveness");
 
77
 
 
78
  // Self-initialize.
 
79
  if (!MBB) {
 
80
    NumRegUnits = TRI->getNumRegUnits();
 
81
    RegUnitsAvailable.resize(NumRegUnits);
 
82
    KillRegUnits.resize(NumRegUnits);
 
83
    DefRegUnits.resize(NumRegUnits);
 
84
    TmpRegUnits.resize(NumRegUnits);
 
85
  }
 
86
 
 
87
  MBB = mbb;
 
88
  initRegState();
 
89
 
 
90
  Tracking = false;
 
91
}
 
92
 
 
93
void RegScavenger::addRegUnits(BitVector &BV, unsigned Reg) {
 
94
  for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI)
 
95
    BV.set(*RUI);
 
96
}
 
97
 
 
98
void RegScavenger::determineKillsAndDefs() {
 
99
  assert(Tracking && "Must be tracking to determine kills and defs");
 
100
 
 
101
  MachineInstr *MI = MBBI;
 
102
  assert(!MI->isDebugValue() && "Debug values have no kills or defs");
 
103
 
 
104
  // Find out which registers are early clobbered, killed, defined, and marked
 
105
  // def-dead in this instruction.
 
106
  KillRegUnits.reset();
 
107
  DefRegUnits.reset();
 
108
  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 
109
    const MachineOperand &MO = MI->getOperand(i);
 
110
    if (MO.isRegMask()) {
 
111
      
 
112
      TmpRegUnits.clear();
 
113
      for (unsigned RU = 0, RUEnd = TRI->getNumRegUnits(); RU != RUEnd; ++RU) {
 
114
        for (MCRegUnitRootIterator RURI(RU, TRI); RURI.isValid(); ++RURI) {
 
115
          if (MO.clobbersPhysReg(*RURI)) {
 
116
            TmpRegUnits.set(RU);
 
117
            break;
 
118
          }
 
119
        }
 
120
      }
 
121
      
 
122
      // Apply the mask.
 
123
      KillRegUnits |= TmpRegUnits;
 
124
    }
 
125
    if (!MO.isReg())
 
126
      continue;
 
127
    unsigned Reg = MO.getReg();
 
128
    if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) || isReserved(Reg))
 
129
      continue;
 
130
 
 
131
    if (MO.isUse()) {
 
132
      // Ignore undef uses.
 
133
      if (MO.isUndef())
 
134
        continue;
 
135
      if (MO.isKill())
 
136
        addRegUnits(KillRegUnits, Reg);
 
137
    } else {
 
138
      assert(MO.isDef());
 
139
      if (MO.isDead())
 
140
        addRegUnits(KillRegUnits, Reg);
 
141
      else
 
142
        addRegUnits(DefRegUnits, Reg);
 
143
    }
 
144
  }
 
145
}
 
146
 
 
147
void RegScavenger::unprocess() {
 
148
  assert(Tracking && "Cannot unprocess because we're not tracking");
 
149
 
 
150
  MachineInstr *MI = MBBI;
 
151
  if (!MI->isDebugValue()) {
 
152
    determineKillsAndDefs();
 
153
 
 
154
    // Commit the changes.
 
155
    setUsed(KillRegUnits);
 
156
    setUnused(DefRegUnits);
 
157
  }
 
158
 
 
159
  if (MBBI == MBB->begin()) {
 
160
    MBBI = MachineBasicBlock::iterator(nullptr);
 
161
    Tracking = false;
 
162
  } else
 
163
    --MBBI;
 
164
}
 
165
 
 
166
void RegScavenger::forward() {
 
167
  // Move ptr forward.
 
168
  if (!Tracking) {
 
169
    MBBI = MBB->begin();
 
170
    Tracking = true;
 
171
  } else {
 
172
    assert(MBBI != MBB->end() && "Already past the end of the basic block!");
 
173
    MBBI = std::next(MBBI);
 
174
  }
 
175
  assert(MBBI != MBB->end() && "Already at the end of the basic block!");
 
176
 
 
177
  MachineInstr *MI = MBBI;
 
178
 
 
179
  for (SmallVectorImpl<ScavengedInfo>::iterator I = Scavenged.begin(),
 
180
         IE = Scavenged.end(); I != IE; ++I) {
 
181
    if (I->Restore != MI)
 
182
      continue;
 
183
 
 
184
    I->Reg = 0;
 
185
    I->Restore = nullptr;
 
186
  }
 
187
 
 
188
  if (MI->isDebugValue())
 
189
    return;
 
190
 
 
191
  determineKillsAndDefs();
 
192
 
 
193
  // Verify uses and defs.
 
194
#ifndef NDEBUG
 
195
  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 
196
    const MachineOperand &MO = MI->getOperand(i);
 
197
    if (!MO.isReg())
 
198
      continue;
 
199
    unsigned Reg = MO.getReg();
 
200
    if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) || isReserved(Reg))
 
201
      continue;
 
202
    if (MO.isUse()) {
 
203
      if (MO.isUndef())
 
204
        continue;
 
205
      if (!isRegUsed(Reg)) {
 
206
        // Check if it's partial live: e.g.
 
207
        // D0 = insert_subreg D0<undef>, S0
 
208
        // ... D0
 
209
        // The problem is the insert_subreg could be eliminated. The use of
 
210
        // D0 is using a partially undef value. This is not *incorrect* since
 
211
        // S1 is can be freely clobbered.
 
212
        // Ideally we would like a way to model this, but leaving the
 
213
        // insert_subreg around causes both correctness and performance issues.
 
214
        bool SubUsed = false;
 
215
        for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
 
216
          if (isRegUsed(*SubRegs)) {
 
217
            SubUsed = true;
 
218
            break;
 
219
          }
 
220
        bool SuperUsed = false;
 
221
        for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR) {
 
222
          if (isRegUsed(*SR)) {
 
223
            SuperUsed = true;
 
224
            break;
 
225
          }
 
226
        }
 
227
        if (!SubUsed && !SuperUsed) {
 
228
          MBB->getParent()->verify(nullptr, "In Register Scavenger");
 
229
          llvm_unreachable("Using an undefined register!");
 
230
        }
 
231
        (void)SubUsed;
 
232
        (void)SuperUsed;
 
233
      }
 
234
    } else {
 
235
      assert(MO.isDef());
 
236
#if 0
 
237
      // FIXME: Enable this once we've figured out how to correctly transfer
 
238
      // implicit kills during codegen passes like the coalescer.
 
239
      assert((KillRegs.test(Reg) || isUnused(Reg) ||
 
240
              isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
 
241
             "Re-defining a live register!");
 
242
#endif
 
243
    }
 
244
  }
 
245
#endif // NDEBUG
 
246
 
 
247
  // Commit the changes.
 
248
  setUnused(KillRegUnits);
 
249
  setUsed(DefRegUnits);
 
250
}
 
251
 
 
252
bool RegScavenger::isRegUsed(unsigned Reg, bool includeReserved) const {
 
253
  if (includeReserved && isReserved(Reg))
 
254
    return true;
 
255
  for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI)
 
256
    if (!RegUnitsAvailable.test(*RUI))
 
257
      return true;
 
258
  return false;
 
259
}
 
260
 
 
261
unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const {
 
262
  for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
 
263
       I != E; ++I)
 
264
    if (!isRegUsed(*I)) {
 
265
      DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(*I) <<
 
266
            "\n");
 
267
      return *I;
 
268
    }
 
269
  return 0;
 
270
}
 
271
 
 
272
/// getRegsAvailable - Return all available registers in the register class
 
273
/// in Mask.
 
274
BitVector RegScavenger::getRegsAvailable(const TargetRegisterClass *RC) {
 
275
  BitVector Mask(TRI->getNumRegs());
 
276
  for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
 
277
       I != E; ++I)
 
278
    if (!isRegUsed(*I))
 
279
      Mask.set(*I);
 
280
  return Mask;
 
281
}
 
282
 
 
283
/// findSurvivorReg - Return the candidate register that is unused for the
 
284
/// longest after StartMII. UseMI is set to the instruction where the search
 
285
/// stopped.
 
286
///
 
287
/// No more than InstrLimit instructions are inspected.
 
288
///
 
289
unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI,
 
290
                                       BitVector &Candidates,
 
291
                                       unsigned InstrLimit,
 
292
                                       MachineBasicBlock::iterator &UseMI) {
 
293
  int Survivor = Candidates.find_first();
 
294
  assert(Survivor > 0 && "No candidates for scavenging");
 
295
 
 
296
  MachineBasicBlock::iterator ME = MBB->getFirstTerminator();
 
297
  assert(StartMI != ME && "MI already at terminator");
 
298
  MachineBasicBlock::iterator RestorePointMI = StartMI;
 
299
  MachineBasicBlock::iterator MI = StartMI;
 
300
 
 
301
  bool inVirtLiveRange = false;
 
302
  for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) {
 
303
    if (MI->isDebugValue()) {
 
304
      ++InstrLimit; // Don't count debug instructions
 
305
      continue;
 
306
    }
 
307
    bool isVirtKillInsn = false;
 
308
    bool isVirtDefInsn = false;
 
309
    // Remove any candidates touched by instruction.
 
310
    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 
311
      const MachineOperand &MO = MI->getOperand(i);
 
312
      if (MO.isRegMask())
 
313
        Candidates.clearBitsNotInMask(MO.getRegMask());
 
314
      if (!MO.isReg() || MO.isUndef() || !MO.getReg())
 
315
        continue;
 
316
      if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
 
317
        if (MO.isDef())
 
318
          isVirtDefInsn = true;
 
319
        else if (MO.isKill())
 
320
          isVirtKillInsn = true;
 
321
        continue;
 
322
      }
 
323
      for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI)
 
324
        Candidates.reset(*AI);
 
325
    }
 
326
    // If we're not in a virtual reg's live range, this is a valid
 
327
    // restore point.
 
328
    if (!inVirtLiveRange) RestorePointMI = MI;
 
329
 
 
330
    // Update whether we're in the live range of a virtual register
 
331
    if (isVirtKillInsn) inVirtLiveRange = false;
 
332
    if (isVirtDefInsn) inVirtLiveRange = true;
 
333
 
 
334
    // Was our survivor untouched by this instruction?
 
335
    if (Candidates.test(Survivor))
 
336
      continue;
 
337
 
 
338
    // All candidates gone?
 
339
    if (Candidates.none())
 
340
      break;
 
341
 
 
342
    Survivor = Candidates.find_first();
 
343
  }
 
344
  // If we ran off the end, that's where we want to restore.
 
345
  if (MI == ME) RestorePointMI = ME;
 
346
  assert (RestorePointMI != StartMI &&
 
347
          "No available scavenger restore location!");
 
348
 
 
349
  // We ran out of candidates, so stop the search.
 
350
  UseMI = RestorePointMI;
 
351
  return Survivor;
 
352
}
 
353
 
 
354
static unsigned getFrameIndexOperandNum(MachineInstr *MI) {
 
355
  unsigned i = 0;
 
356
  while (!MI->getOperand(i).isFI()) {
 
357
    ++i;
 
358
    assert(i < MI->getNumOperands() &&
 
359
           "Instr doesn't have FrameIndex operand!");
 
360
  }
 
361
  return i;
 
362
}
 
363
 
 
364
unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
 
365
                                        MachineBasicBlock::iterator I,
 
366
                                        int SPAdj) {
 
367
  // Consider all allocatable registers in the register class initially
 
368
  BitVector Candidates =
 
369
    TRI->getAllocatableSet(*I->getParent()->getParent(), RC);
 
370
 
 
371
  // Exclude all the registers being used by the instruction.
 
372
  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 
373
    MachineOperand &MO = I->getOperand(i);
 
374
    if (MO.isReg() && MO.getReg() != 0 && !(MO.isUse() && MO.isUndef()) &&
 
375
        !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
 
376
      Candidates.reset(MO.getReg());
 
377
  }
 
378
 
 
379
  // Try to find a register that's unused if there is one, as then we won't
 
380
  // have to spill.
 
381
  BitVector Available = getRegsAvailable(RC);
 
382
  Available &= Candidates;
 
383
  if (Available.any())
 
384
    Candidates = Available;
 
385
 
 
386
  // Find the register whose use is furthest away.
 
387
  MachineBasicBlock::iterator UseMI;
 
388
  unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI);
 
389
 
 
390
  // If we found an unused register there is no reason to spill it.
 
391
  if (!isRegUsed(SReg)) {
 
392
    DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n");
 
393
    return SReg;
 
394
  }
 
395
 
 
396
  // Find an available scavenging slot.
 
397
  unsigned SI;
 
398
  for (SI = 0; SI < Scavenged.size(); ++SI)
 
399
    if (Scavenged[SI].Reg == 0)
 
400
      break;
 
401
 
 
402
  if (SI == Scavenged.size()) {
 
403
    // We need to scavenge a register but have no spill slot, the target
 
404
    // must know how to do it (if not, we'll assert below).
 
405
    Scavenged.push_back(ScavengedInfo());
 
406
  }
 
407
 
 
408
  // Avoid infinite regress
 
409
  Scavenged[SI].Reg = SReg;
 
410
 
 
411
  // If the target knows how to save/restore the register, let it do so;
 
412
  // otherwise, use the emergency stack spill slot.
 
413
  if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) {
 
414
    // Spill the scavenged register before I.
 
415
    assert(Scavenged[SI].FrameIndex >= 0 &&
 
416
           "Cannot scavenge register without an emergency spill slot!");
 
417
    TII->storeRegToStackSlot(*MBB, I, SReg, true, Scavenged[SI].FrameIndex,
 
418
                             RC, TRI);
 
419
    MachineBasicBlock::iterator II = std::prev(I);
 
420
 
 
421
    unsigned FIOperandNum = getFrameIndexOperandNum(II);
 
422
    TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
 
423
 
 
424
    // Restore the scavenged register before its use (or first terminator).
 
425
    TII->loadRegFromStackSlot(*MBB, UseMI, SReg, Scavenged[SI].FrameIndex,
 
426
                              RC, TRI);
 
427
    II = std::prev(UseMI);
 
428
 
 
429
    FIOperandNum = getFrameIndexOperandNum(II);
 
430
    TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
 
431
  }
 
432
 
 
433
  Scavenged[SI].Restore = std::prev(UseMI);
 
434
 
 
435
  // Doing this here leads to infinite regress.
 
436
  // Scavenged[SI].Reg = SReg;
 
437
 
 
438
  DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) <<
 
439
        "\n");
 
440
 
 
441
  return SReg;
 
442
}