← Back to branch summary

~ubuntu-branches/ubuntu/feisty/clamav/feisty

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/CodeGen/RegisterScavenging.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Kees Cook
  • Date: 2007-02-20 10:33:44 UTC
  • mto: This revision was merged to the branch mainline in revision 16.
  • Revision ID: james.westby@ubuntu.com-20070220103344-zgcu2psnx9d98fpa
Tags: upstream-0.90
Import upstream version 0.90

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/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
 
#define DEBUG_TYPE "reg-scavenging"
18
 
#include "llvm/CodeGen/RegisterScavenging.h"
19
 
#include "llvm/CodeGen/MachineFrameInfo.h"
20
 
#include "llvm/CodeGen/MachineFunction.h"
21
 
#include "llvm/CodeGen/MachineBasicBlock.h"
22
 
#include "llvm/CodeGen/MachineInstr.h"
23
 
#include "llvm/CodeGen/MachineRegisterInfo.h"
24
 
#include "llvm/Support/Debug.h"
25
 
#include "llvm/Support/ErrorHandling.h"
26
 
#include "llvm/Support/raw_ostream.h"
27
 
#include "llvm/Target/TargetRegisterInfo.h"
28
 
#include "llvm/Target/TargetInstrInfo.h"
29
 
#include "llvm/Target/TargetMachine.h"
30
 
#include "llvm/ADT/DenseMap.h"
31
 
#include "llvm/ADT/SmallPtrSet.h"
32
 
#include "llvm/ADT/SmallVector.h"
33
 
#include "llvm/ADT/STLExtras.h"
34
 
using namespace llvm;
35
 
 
36
 
/// setUsed - Set the register and its sub-registers as being used.
37
 
void RegScavenger::setUsed(unsigned Reg) {
38
 
  RegsAvailable.reset(Reg);
39
 
 
40
 
  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
41
 
       unsigned SubReg = *SubRegs; ++SubRegs)
42
 
    RegsAvailable.reset(SubReg);
43
 
}
44
 
 
45
 
bool RegScavenger::isAliasUsed(unsigned Reg) const {
46
 
  if (isUsed(Reg))
47
 
    return true;
48
 
  for (const unsigned *R = TRI->getAliasSet(Reg); *R; ++R)
49
 
    if (isUsed(*R))
50
 
      return true;
51
 
  return false;
52
 
}
53
 
 
54
 
void RegScavenger::initRegState() {
55
 
  ScavengedReg = 0;
56
 
  ScavengedRC = NULL;
57
 
  ScavengeRestore = NULL;
58
 
 
59
 
  // All registers started out unused.
60
 
  RegsAvailable.set();
61
 
 
62
 
  // Reserved registers are always used.
63
 
  RegsAvailable ^= ReservedRegs;
64
 
 
65
 
  if (!MBB)
66
 
    return;
67
 
 
68
 
  // Live-in registers are in use.
69
 
  for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(),
70
 
         E = MBB->livein_end(); I != E; ++I)
71
 
    setUsed(*I);
72
 
 
73
 
  // Pristine CSRs are also unavailable.
74
 
  BitVector PR = MBB->getParent()->getFrameInfo()->getPristineRegs(MBB);
75
 
  for (int I = PR.find_first(); I>0; I = PR.find_next(I))
76
 
    setUsed(I);
77
 
}
78
 
 
79
 
void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
80
 
  MachineFunction &MF = *mbb->getParent();
81
 
  const TargetMachine &TM = MF.getTarget();
82
 
  TII = TM.getInstrInfo();
83
 
  TRI = TM.getRegisterInfo();
84
 
  MRI = &MF.getRegInfo();
85
 
 
86
 
  assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) &&
87
 
         "Target changed?");
88
 
 
89
 
  // Self-initialize.
90
 
  if (!MBB) {
91
 
    NumPhysRegs = TRI->getNumRegs();
92
 
    RegsAvailable.resize(NumPhysRegs);
93
 
 
94
 
    // Create reserved registers bitvector.
95
 
    ReservedRegs = TRI->getReservedRegs(MF);
96
 
 
97
 
    // Create callee-saved registers bitvector.
98
 
    CalleeSavedRegs.resize(NumPhysRegs);
99
 
    const unsigned *CSRegs = TRI->getCalleeSavedRegs();
100
 
    if (CSRegs != NULL)
101
 
      for (unsigned i = 0; CSRegs[i]; ++i)
102
 
        CalleeSavedRegs.set(CSRegs[i]);
103
 
  }
104
 
 
105
 
  MBB = mbb;
106
 
  initRegState();
107
 
 
108
 
  Tracking = false;
109
 
}
110
 
 
111
 
void RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) {
112
 
  BV.set(Reg);
113
 
  for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++)
114
 
    BV.set(*R);
115
 
}
116
 
 
117
 
void RegScavenger::addRegWithAliases(BitVector &BV, unsigned Reg) {
118
 
  BV.set(Reg);
119
 
  for (const unsigned *R = TRI->getAliasSet(Reg); *R; R++)
120
 
    BV.set(*R);
121
 
}
122
 
 
123
 
void RegScavenger::forward() {
124
 
  // Move ptr forward.
125
 
  if (!Tracking) {
126
 
    MBBI = MBB->begin();
127
 
    Tracking = true;
128
 
  } else {
129
 
    assert(MBBI != MBB->end() && "Already at the end of the basic block!");
130
 
    MBBI = llvm::next(MBBI);
131
 
  }
132
 
 
133
 
  MachineInstr *MI = MBBI;
134
 
 
135
 
  if (MI == ScavengeRestore) {
136
 
    ScavengedReg = 0;
137
 
    ScavengedRC = NULL;
138
 
    ScavengeRestore = NULL;
139
 
  }
140
 
 
141
 
  if (MI->isDebugValue())
142
 
    return;
143
 
 
144
 
  // Find out which registers are early clobbered, killed, defined, and marked
145
 
  // def-dead in this instruction.
146
 
  // FIXME: The scavenger is not predication aware. If the instruction is
147
 
  // predicated, conservatively assume "kill" markers do not actually kill the
148
 
  // register. Similarly ignores "dead" markers.
149
 
  bool isPred = TII->isPredicated(MI);
150
 
  BitVector EarlyClobberRegs(NumPhysRegs);
151
 
  BitVector KillRegs(NumPhysRegs);
152
 
  BitVector DefRegs(NumPhysRegs);
153
 
  BitVector DeadRegs(NumPhysRegs);
154
 
  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
155
 
    const MachineOperand &MO = MI->getOperand(i);
156
 
    if (!MO.isReg() || MO.isUndef())
157
 
      continue;
158
 
    unsigned Reg = MO.getReg();
159
 
    if (!Reg || isReserved(Reg))
160
 
      continue;
161
 
 
162
 
    if (MO.isUse()) {
163
 
      // Two-address operands implicitly kill.
164
 
      if (!isPred && (MO.isKill() || MI->isRegTiedToDefOperand(i)))
165
 
        addRegWithSubRegs(KillRegs, Reg);
166
 
    } else {
167
 
      assert(MO.isDef());
168
 
      if (!isPred && MO.isDead())
169
 
        addRegWithSubRegs(DeadRegs, Reg);
170
 
      else
171
 
        addRegWithSubRegs(DefRegs, Reg);
172
 
      if (MO.isEarlyClobber())
173
 
        addRegWithAliases(EarlyClobberRegs, Reg);
174
 
    }
175
 
  }
176
 
 
177
 
  // Verify uses and defs.
178
 
  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
179
 
    const MachineOperand &MO = MI->getOperand(i);
180
 
    if (!MO.isReg() || MO.isUndef())
181
 
      continue;
182
 
    unsigned Reg = MO.getReg();
183
 
    if (!Reg || isReserved(Reg))
184
 
      continue;
185
 
    if (MO.isUse()) {
186
 
      if (!isUsed(Reg)) {
187
 
        // Check if it's partial live: e.g.
188
 
        // D0 = insert_subreg D0<undef>, S0
189
 
        // ... D0
190
 
        // The problem is the insert_subreg could be eliminated. The use of
191
 
        // D0 is using a partially undef value. This is not *incorrect* since
192
 
        // S1 is can be freely clobbered.
193
 
        // Ideally we would like a way to model this, but leaving the
194
 
        // insert_subreg around causes both correctness and performance issues.
195
 
        bool SubUsed = false;
196
 
        for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
197
 
             unsigned SubReg = *SubRegs; ++SubRegs)
198
 
          if (isUsed(SubReg)) {
199
 
            SubUsed = true;
200
 
            break;
201
 
          }
202
 
        assert(SubUsed && "Using an undefined register!");
203
 
      }
204
 
      assert((!EarlyClobberRegs.test(Reg) || MI->isRegTiedToDefOperand(i)) &&
205
 
             "Using an early clobbered register!");
206
 
    } else {
207
 
      assert(MO.isDef());
208
 
#if 0
209
 
      // FIXME: Enable this once we've figured out how to correctly transfer
210
 
      // implicit kills during codegen passes like the coalescer.
211
 
      assert((KillRegs.test(Reg) || isUnused(Reg) ||
212
 
              isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
213
 
             "Re-defining a live register!");
214
 
#endif
215
 
    }
216
 
  }
217
 
 
218
 
  // Commit the changes.
219
 
  setUnused(KillRegs);
220
 
  setUnused(DeadRegs);
221
 
  setUsed(DefRegs);
222
 
}
223
 
 
224
 
void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) {
225
 
  if (includeReserved)
226
 
    used = ~RegsAvailable;
227
 
  else
228
 
    used = ~RegsAvailable & ~ReservedRegs;
229
 
}
230
 
 
231
 
unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const {
232
 
  for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
233
 
       I != E; ++I)
234
 
    if (!isAliasUsed(*I)) {
235
 
      DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(*I) <<
236
 
            "\n");
237
 
      return *I;
238
 
    }
239
 
  return 0;
240
 
}
241
 
 
242
 
/// getRegsAvailable - Return all available registers in the register class
243
 
/// in Mask.
244
 
void RegScavenger::getRegsAvailable(const TargetRegisterClass *RC,
245
 
                                    BitVector &Mask) {
246
 
  for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
247
 
       I != E; ++I)
248
 
    if (!isAliasUsed(*I))
249
 
      Mask.set(*I);
250
 
}
251
 
 
252
 
/// findSurvivorReg - Return the candidate register that is unused for the
253
 
/// longest after StargMII. UseMI is set to the instruction where the search
254
 
/// stopped.
255
 
///
256
 
/// No more than InstrLimit instructions are inspected.
257
 
///
258
 
unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI,
259
 
                                       BitVector &Candidates,
260
 
                                       unsigned InstrLimit,
261
 
                                       MachineBasicBlock::iterator &UseMI) {
262
 
  int Survivor = Candidates.find_first();
263
 
  assert(Survivor > 0 && "No candidates for scavenging");
264
 
 
265
 
  MachineBasicBlock::iterator ME = MBB->getFirstTerminator();
266
 
  assert(StartMI != ME && "MI already at terminator");
267
 
  MachineBasicBlock::iterator RestorePointMI = StartMI;
268
 
  MachineBasicBlock::iterator MI = StartMI;
269
 
 
270
 
  bool inVirtLiveRange = false;
271
 
  for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) {
272
 
    if (MI->isDebugValue()) {
273
 
      ++InstrLimit; // Don't count debug instructions
274
 
      continue;
275
 
    }
276
 
    bool isVirtKillInsn = false;
277
 
    bool isVirtDefInsn = false;
278
 
    // Remove any candidates touched by instruction.
279
 
    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
280
 
      const MachineOperand &MO = MI->getOperand(i);
281
 
      if (!MO.isReg() || MO.isUndef() || !MO.getReg())
282
 
        continue;
283
 
      if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
284
 
        if (MO.isDef())
285
 
          isVirtDefInsn = true;
286
 
        else if (MO.isKill())
287
 
          isVirtKillInsn = true;
288
 
        continue;
289
 
      }
290
 
      Candidates.reset(MO.getReg());
291
 
      for (const unsigned *R = TRI->getAliasSet(MO.getReg()); *R; R++)
292
 
        Candidates.reset(*R);
293
 
    }
294
 
    // If we're not in a virtual reg's live range, this is a valid
295
 
    // restore point.
296
 
    if (!inVirtLiveRange) RestorePointMI = MI;
297
 
 
298
 
    // Update whether we're in the live range of a virtual register
299
 
    if (isVirtKillInsn) inVirtLiveRange = false;
300
 
    if (isVirtDefInsn) inVirtLiveRange = true;
301
 
 
302
 
    // Was our survivor untouched by this instruction?
303
 
    if (Candidates.test(Survivor))
304
 
      continue;
305
 
 
306
 
    // All candidates gone?
307
 
    if (Candidates.none())
308
 
      break;
309
 
 
310
 
    Survivor = Candidates.find_first();
311
 
  }
312
 
  // If we ran off the end, that's where we want to restore.
313
 
  if (MI == ME) RestorePointMI = ME;
314
 
  assert (RestorePointMI != StartMI &&
315
 
          "No available scavenger restore location!");
316
 
 
317
 
  // We ran out of candidates, so stop the search.
318
 
  UseMI = RestorePointMI;
319
 
  return Survivor;
320
 
}
321
 
 
322
 
unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
323
 
                                        MachineBasicBlock::iterator I,
324
 
                                        int SPAdj) {
325
 
  // Consider all allocatable registers in the register class initially
326
 
  BitVector Candidates =
327
 
    TRI->getAllocatableSet(*I->getParent()->getParent(), RC);
328
 
 
329
 
  // Exclude all the registers being used by the instruction.
330
 
  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
331
 
    MachineOperand &MO = I->getOperand(i);
332
 
    if (MO.isReg() && MO.getReg() != 0 &&
333
 
        !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
334
 
      Candidates.reset(MO.getReg());
335
 
  }
336
 
 
337
 
  // Try to find a register that's unused if there is one, as then we won't
338
 
  // have to spill.
339
 
  if ((Candidates & RegsAvailable).any())
340
 
     Candidates &= RegsAvailable;
341
 
 
342
 
  // Find the register whose use is furthest away.
343
 
  MachineBasicBlock::iterator UseMI;
344
 
  unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI);
345
 
 
346
 
  // If we found an unused register there is no reason to spill it.
347
 
  if (!isAliasUsed(SReg)) {
348
 
    DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n");
349
 
    return SReg;
350
 
  }
351
 
 
352
 
  assert(ScavengedReg == 0 &&
353
 
         "Scavenger slot is live, unable to scavenge another register!");
354
 
 
355
 
  // Avoid infinite regress
356
 
  ScavengedReg = SReg;
357
 
 
358
 
  // If the target knows how to save/restore the register, let it do so;
359
 
  // otherwise, use the emergency stack spill slot.
360
 
  if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) {
361
 
    // Spill the scavenged register before I.
362
 
    assert(ScavengingFrameIndex >= 0 &&
363
 
           "Cannot scavenge register without an emergency spill slot!");
364
 
    TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC,TRI);
365
 
    MachineBasicBlock::iterator II = prior(I);
366
 
    TRI->eliminateFrameIndex(II, SPAdj, this);
367
 
 
368
 
    // Restore the scavenged register before its use (or first terminator).
369
 
    TII->loadRegFromStackSlot(*MBB, UseMI, SReg, ScavengingFrameIndex, RC, TRI);
370
 
    II = prior(UseMI);
371
 
    TRI->eliminateFrameIndex(II, SPAdj, this);
372
 
  }
373
 
 
374
 
  ScavengeRestore = prior(UseMI);
375
 
 
376
 
  // Doing this here leads to infinite regress.
377
 
  // ScavengedReg = SReg;
378
 
  ScavengedRC = RC;
379
 
 
380
 
  DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) <<
381
 
        "\n");
382
 
 
383
 
  return SReg;
384
 
}