← Back to branch summary

~louis/ubuntu/trusty/clamav/lp799623_fix_logrotate

« back to all changes in this revision

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

  • Committer: Bazaar Package Importer
  • Author(s): Scott Kitterman
  • Date: 2010-03-12 11:30:04 UTC
  • mfrom: (0.41.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20100312113004-b0fop4bkycszdd0z
Tags: 0.96~rc1+dfsg-0ubuntu1
https://launchpad.net/bugs/537636
* New upstream RC - FFE (LP: #537636):
  - Add OfficialDatabaseOnly option to clamav-base.postinst.in
  - Add LocalSocketGroup option to clamav-base.postinst.in
  - Add LocalSocketMode option to clamav-base.postinst.in
  - Add CrossFilesystems option to clamav-base.postinst.in
  - Add ClamukoScannerCount option to clamav-base.postinst.in
  - Add BytecodeSecurity opiton to clamav-base.postinst.in
  - Add DetectionStatsHostID option to clamav-freshclam.postinst.in
  - Add Bytecode option to clamav-freshclam.postinst.in
  - Add MilterSocketGroup option to clamav-milter.postinst.in
  - Add MilterSocketMode option to clamav-milter.postinst.in
  - Add ReportHostname option to clamav-milter.postinst.in
  - Bump libclamav SO version to 6.1.0 in libclamav6.install
  - Drop clamdmon from clamav.examples (no longer shipped by upstream)
  - Drop libclamav.a from libclamav-dev.install (not built by upstream)
  - Update SO version for lintian override for libclamav6
  - Add new Bytecode Testing Tool, usr/bin/clambc, to clamav.install
  - Add build-depends on python and python-setuptools for new test suite
  - Update debian/copyright for the embedded copy of llvm (using the system
    llvm is not currently feasible)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/CodeGen/LiveVariables.cpp
 
1
//===-- LiveVariables.cpp - Live Variable Analysis for Machine Code -------===//
 
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 LiveVariable analysis pass.  For each machine
 
11
// instruction in the function, this pass calculates the set of registers that
 
12
// are immediately dead after the instruction (i.e., the instruction calculates
 
13
// the value, but it is never used) and the set of registers that are used by
 
14
// the instruction, but are never used after the instruction (i.e., they are
 
15
// killed).
 
16
//
 
17
// This class computes live variables using are sparse implementation based on
 
18
// the machine code SSA form.  This class computes live variable information for
 
19
// each virtual and _register allocatable_ physical register in a function.  It
 
20
// uses the dominance properties of SSA form to efficiently compute live
 
21
// variables for virtual registers, and assumes that physical registers are only
 
22
// live within a single basic block (allowing it to do a single local analysis
 
23
// to resolve physical register lifetimes in each basic block).  If a physical
 
24
// register is not register allocatable, it is not tracked.  This is useful for
 
25
// things like the stack pointer and condition codes.
 
26
//
 
27
//===----------------------------------------------------------------------===//
 
28
 
 
29
#include "llvm/CodeGen/LiveVariables.h"
 
30
#include "llvm/CodeGen/MachineInstr.h"
 
31
#include "llvm/CodeGen/MachineRegisterInfo.h"
 
32
#include "llvm/CodeGen/Passes.h"
 
33
#include "llvm/Support/Debug.h"
 
34
#include "llvm/Target/TargetRegisterInfo.h"
 
35
#include "llvm/Target/TargetInstrInfo.h"
 
36
#include "llvm/Target/TargetMachine.h"
 
37
#include "llvm/ADT/DepthFirstIterator.h"
 
38
#include "llvm/ADT/SmallPtrSet.h"
 
39
#include "llvm/ADT/SmallSet.h"
 
40
#include "llvm/ADT/STLExtras.h"
 
41
#include <algorithm>
 
42
using namespace llvm;
 
43
 
 
44
char LiveVariables::ID = 0;
 
45
static RegisterPass<LiveVariables> X("livevars", "Live Variable Analysis");
 
46
 
 
47
 
 
48
void LiveVariables::getAnalysisUsage(AnalysisUsage &AU) const {
 
49
  AU.addRequiredID(UnreachableMachineBlockElimID);
 
50
  AU.setPreservesAll();
 
51
  MachineFunctionPass::getAnalysisUsage(AU);
 
52
}
 
53
 
 
54
MachineInstr *
 
55
LiveVariables::VarInfo::findKill(const MachineBasicBlock *MBB) const {
 
56
  for (unsigned i = 0, e = Kills.size(); i != e; ++i)
 
57
    if (Kills[i]->getParent() == MBB)
 
58
      return Kills[i];
 
59
  return NULL;
 
60
}
 
61
 
 
62
void LiveVariables::VarInfo::dump() const {
 
63
  dbgs() << "  Alive in blocks: ";
 
64
  for (SparseBitVector<>::iterator I = AliveBlocks.begin(),
 
65
           E = AliveBlocks.end(); I != E; ++I)
 
66
    dbgs() << *I << ", ";
 
67
  dbgs() << "\n  Killed by:";
 
68
  if (Kills.empty())
 
69
    dbgs() << " No instructions.\n";
 
70
  else {
 
71
    for (unsigned i = 0, e = Kills.size(); i != e; ++i)
 
72
      dbgs() << "\n    #" << i << ": " << *Kills[i];
 
73
    dbgs() << "\n";
 
74
  }
 
75
}
 
76
 
 
77
/// getVarInfo - Get (possibly creating) a VarInfo object for the given vreg.
 
78
LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) {
 
79
  assert(TargetRegisterInfo::isVirtualRegister(RegIdx) &&
 
80
         "getVarInfo: not a virtual register!");
 
81
  RegIdx -= TargetRegisterInfo::FirstVirtualRegister;
 
82
  if (RegIdx >= VirtRegInfo.size()) {
 
83
    if (RegIdx >= 2*VirtRegInfo.size())
 
84
      VirtRegInfo.resize(RegIdx*2);
 
85
    else
 
86
      VirtRegInfo.resize(2*VirtRegInfo.size());
 
87
  }
 
88
  return VirtRegInfo[RegIdx];
 
89
}
 
90
 
 
91
void LiveVariables::MarkVirtRegAliveInBlock(VarInfo& VRInfo,
 
92
                                            MachineBasicBlock *DefBlock,
 
93
                                            MachineBasicBlock *MBB,
 
94
                                    std::vector<MachineBasicBlock*> &WorkList) {
 
95
  unsigned BBNum = MBB->getNumber();
 
96
  
 
97
  // Check to see if this basic block is one of the killing blocks.  If so,
 
98
  // remove it.
 
99
  for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i)
 
100
    if (VRInfo.Kills[i]->getParent() == MBB) {
 
101
      VRInfo.Kills.erase(VRInfo.Kills.begin()+i);  // Erase entry
 
102
      break;
 
103
    }
 
104
  
 
105
  if (MBB == DefBlock) return;  // Terminate recursion
 
106
 
 
107
  if (VRInfo.AliveBlocks.test(BBNum))
 
108
    return;  // We already know the block is live
 
109
 
 
110
  // Mark the variable known alive in this bb
 
111
  VRInfo.AliveBlocks.set(BBNum);
 
112
 
 
113
  for (MachineBasicBlock::const_pred_reverse_iterator PI = MBB->pred_rbegin(),
 
114
         E = MBB->pred_rend(); PI != E; ++PI)
 
115
    WorkList.push_back(*PI);
 
116
}
 
117
 
 
118
void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo,
 
119
                                            MachineBasicBlock *DefBlock,
 
120
                                            MachineBasicBlock *MBB) {
 
121
  std::vector<MachineBasicBlock*> WorkList;
 
122
  MarkVirtRegAliveInBlock(VRInfo, DefBlock, MBB, WorkList);
 
123
 
 
124
  while (!WorkList.empty()) {
 
125
    MachineBasicBlock *Pred = WorkList.back();
 
126
    WorkList.pop_back();
 
127
    MarkVirtRegAliveInBlock(VRInfo, DefBlock, Pred, WorkList);
 
128
  }
 
129
}
 
130
 
 
131
void LiveVariables::HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB,
 
132
                                     MachineInstr *MI) {
 
133
  assert(MRI->getVRegDef(reg) && "Register use before def!");
 
134
 
 
135
  unsigned BBNum = MBB->getNumber();
 
136
 
 
137
  VarInfo& VRInfo = getVarInfo(reg);
 
138
  VRInfo.NumUses++;
 
139
 
 
140
  // Check to see if this basic block is already a kill block.
 
141
  if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) {
 
142
    // Yes, this register is killed in this basic block already. Increase the
 
143
    // live range by updating the kill instruction.
 
144
    VRInfo.Kills.back() = MI;
 
145
    return;
 
146
  }
 
147
 
 
148
#ifndef NDEBUG
 
149
  for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i)
 
150
    assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!");
 
151
#endif
 
152
 
 
153
  // This situation can occur:
 
154
  //
 
155
  //     ,------.
 
156
  //     |      |
 
157
  //     |      v
 
158
  //     |   t2 = phi ... t1 ...
 
159
  //     |      |
 
160
  //     |      v
 
161
  //     |   t1 = ...
 
162
  //     |  ... = ... t1 ...
 
163
  //     |      |
 
164
  //     `------'
 
165
  //
 
166
  // where there is a use in a PHI node that's a predecessor to the defining
 
167
  // block. We don't want to mark all predecessors as having the value "alive"
 
168
  // in this case.
 
169
  if (MBB == MRI->getVRegDef(reg)->getParent()) return;
 
170
 
 
171
  // Add a new kill entry for this basic block. If this virtual register is
 
172
  // already marked as alive in this basic block, that means it is alive in at
 
173
  // least one of the successor blocks, it's not a kill.
 
174
  if (!VRInfo.AliveBlocks.test(BBNum))
 
175
    VRInfo.Kills.push_back(MI);
 
176
 
 
177
  // Update all dominating blocks to mark them as "known live".
 
178
  for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
 
179
         E = MBB->pred_end(); PI != E; ++PI)
 
180
    MarkVirtRegAliveInBlock(VRInfo, MRI->getVRegDef(reg)->getParent(), *PI);
 
181
}
 
182
 
 
183
void LiveVariables::HandleVirtRegDef(unsigned Reg, MachineInstr *MI) {
 
184
  VarInfo &VRInfo = getVarInfo(Reg);
 
185
 
 
186
  if (VRInfo.AliveBlocks.empty())
 
187
    // If vr is not alive in any block, then defaults to dead.
 
188
    VRInfo.Kills.push_back(MI);
 
189
}
 
190
 
 
191
/// FindLastPartialDef - Return the last partial def of the specified register.
 
192
/// Also returns the sub-registers that're defined by the instruction.
 
193
MachineInstr *LiveVariables::FindLastPartialDef(unsigned Reg,
 
194
                                            SmallSet<unsigned,4> &PartDefRegs) {
 
195
  unsigned LastDefReg = 0;
 
196
  unsigned LastDefDist = 0;
 
197
  MachineInstr *LastDef = NULL;
 
198
  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
 
199
       unsigned SubReg = *SubRegs; ++SubRegs) {
 
200
    MachineInstr *Def = PhysRegDef[SubReg];
 
201
    if (!Def)
 
202
      continue;
 
203
    unsigned Dist = DistanceMap[Def];
 
204
    if (Dist > LastDefDist) {
 
205
      LastDefReg  = SubReg;
 
206
      LastDef     = Def;
 
207
      LastDefDist = Dist;
 
208
    }
 
209
  }
 
210
 
 
211
  if (!LastDef)
 
212
    return 0;
 
213
 
 
214
  PartDefRegs.insert(LastDefReg);
 
215
  for (unsigned i = 0, e = LastDef->getNumOperands(); i != e; ++i) {
 
216
    MachineOperand &MO = LastDef->getOperand(i);
 
217
    if (!MO.isReg() || !MO.isDef() || MO.getReg() == 0)
 
218
      continue;
 
219
    unsigned DefReg = MO.getReg();
 
220
    if (TRI->isSubRegister(Reg, DefReg)) {
 
221
      PartDefRegs.insert(DefReg);
 
222
      for (const unsigned *SubRegs = TRI->getSubRegisters(DefReg);
 
223
           unsigned SubReg = *SubRegs; ++SubRegs)
 
224
        PartDefRegs.insert(SubReg);
 
225
    }
 
226
  }
 
227
  return LastDef;
 
228
}
 
229
 
 
230
/// HandlePhysRegUse - Turn previous partial def's into read/mod/writes. Add
 
231
/// implicit defs to a machine instruction if there was an earlier def of its
 
232
/// super-register.
 
233
void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) {
 
234
  MachineInstr *LastDef = PhysRegDef[Reg];
 
235
  // If there was a previous use or a "full" def all is well.
 
236
  if (!LastDef && !PhysRegUse[Reg]) {
 
237
    // Otherwise, the last sub-register def implicitly defines this register.
 
238
    // e.g.
 
239
    // AH =
 
240
    // AL = ... <imp-def EAX>, <imp-kill AH>
 
241
    //    = AH
 
242
    // ...
 
243
    //    = EAX
 
244
    // All of the sub-registers must have been defined before the use of Reg!
 
245
    SmallSet<unsigned, 4> PartDefRegs;
 
246
    MachineInstr *LastPartialDef = FindLastPartialDef(Reg, PartDefRegs);
 
247
    // If LastPartialDef is NULL, it must be using a livein register.
 
248
    if (LastPartialDef) {
 
249
      LastPartialDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/,
 
250
                                                           true/*IsImp*/));
 
251
      PhysRegDef[Reg] = LastPartialDef;
 
252
      SmallSet<unsigned, 8> Processed;
 
253
      for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
 
254
           unsigned SubReg = *SubRegs; ++SubRegs) {
 
255
        if (Processed.count(SubReg))
 
256
          continue;
 
257
        if (PartDefRegs.count(SubReg))
 
258
          continue;
 
259
        // This part of Reg was defined before the last partial def. It's killed
 
260
        // here.
 
261
        LastPartialDef->addOperand(MachineOperand::CreateReg(SubReg,
 
262
                                                             false/*IsDef*/,
 
263
                                                             true/*IsImp*/));
 
264
        PhysRegDef[SubReg] = LastPartialDef;
 
265
        for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS)
 
266
          Processed.insert(*SS);
 
267
      }
 
268
    }
 
269
  }
 
270
  else if (LastDef && !PhysRegUse[Reg] &&
 
271
           !LastDef->findRegisterDefOperand(Reg))
 
272
    // Last def defines the super register, add an implicit def of reg.
 
273
    LastDef->addOperand(MachineOperand::CreateReg(Reg,
 
274
                                                 true/*IsDef*/, true/*IsImp*/));
 
275
 
 
276
  // Remember this use.
 
277
  PhysRegUse[Reg]  = MI;
 
278
  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
 
279
       unsigned SubReg = *SubRegs; ++SubRegs)
 
280
    PhysRegUse[SubReg] =  MI;
 
281
}
 
282
 
 
283
/// FindLastRefOrPartRef - Return the last reference or partial reference of
 
284
/// the specified register.
 
285
MachineInstr *LiveVariables::FindLastRefOrPartRef(unsigned Reg) {
 
286
  MachineInstr *LastDef = PhysRegDef[Reg];
 
287
  MachineInstr *LastUse = PhysRegUse[Reg];
 
288
  if (!LastDef && !LastUse)
 
289
    return false;
 
290
 
 
291
  MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef;
 
292
  unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
 
293
  unsigned LastPartDefDist = 0;
 
294
  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
 
295
       unsigned SubReg = *SubRegs; ++SubRegs) {
 
296
    MachineInstr *Def = PhysRegDef[SubReg];
 
297
    if (Def && Def != LastDef) {
 
298
      // There was a def of this sub-register in between. This is a partial
 
299
      // def, keep track of the last one.
 
300
      unsigned Dist = DistanceMap[Def];
 
301
      if (Dist > LastPartDefDist)
 
302
        LastPartDefDist = Dist;
 
303
    } else if (MachineInstr *Use = PhysRegUse[SubReg]) {
 
304
      unsigned Dist = DistanceMap[Use];
 
305
      if (Dist > LastRefOrPartRefDist) {
 
306
        LastRefOrPartRefDist = Dist;
 
307
        LastRefOrPartRef = Use;
 
308
      }
 
309
    }
 
310
  }
 
311
 
 
312
  return LastRefOrPartRef;
 
313
}
 
314
 
 
315
bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *MI) {
 
316
  MachineInstr *LastDef = PhysRegDef[Reg];
 
317
  MachineInstr *LastUse = PhysRegUse[Reg];
 
318
  if (!LastDef && !LastUse)
 
319
    return false;
 
320
 
 
321
  MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef;
 
322
  unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
 
323
  // The whole register is used.
 
324
  // AL =
 
325
  // AH =
 
326
  //
 
327
  //    = AX
 
328
  //    = AL, AX<imp-use, kill>
 
329
  // AX =
 
330
  //
 
331
  // Or whole register is defined, but not used at all.
 
332
  // AX<dead> =
 
333
  // ...
 
334
  // AX =
 
335
  //
 
336
  // Or whole register is defined, but only partly used.
 
337
  // AX<dead> = AL<imp-def>
 
338
  //    = AL<kill>
 
339
  // AX = 
 
340
  MachineInstr *LastPartDef = 0;
 
341
  unsigned LastPartDefDist = 0;
 
342
  SmallSet<unsigned, 8> PartUses;
 
343
  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
 
344
       unsigned SubReg = *SubRegs; ++SubRegs) {
 
345
    MachineInstr *Def = PhysRegDef[SubReg];
 
346
    if (Def && Def != LastDef) {
 
347
      // There was a def of this sub-register in between. This is a partial
 
348
      // def, keep track of the last one.
 
349
      unsigned Dist = DistanceMap[Def];
 
350
      if (Dist > LastPartDefDist) {
 
351
        LastPartDefDist = Dist;
 
352
        LastPartDef = Def;
 
353
      }
 
354
      continue;
 
355
    }
 
356
    if (MachineInstr *Use = PhysRegUse[SubReg]) {
 
357
      PartUses.insert(SubReg);
 
358
      for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS)
 
359
        PartUses.insert(*SS);
 
360
      unsigned Dist = DistanceMap[Use];
 
361
      if (Dist > LastRefOrPartRefDist) {
 
362
        LastRefOrPartRefDist = Dist;
 
363
        LastRefOrPartRef = Use;
 
364
      }
 
365
    }
 
366
  }
 
367
 
 
368
  if (!PhysRegUse[Reg]) {
 
369
    // Partial uses. Mark register def dead and add implicit def of
 
370
    // sub-registers which are used.
 
371
    // EAX<dead>  = op  AL<imp-def>
 
372
    // That is, EAX def is dead but AL def extends pass it.
 
373
    PhysRegDef[Reg]->addRegisterDead(Reg, TRI, true);
 
374
    for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
 
375
         unsigned SubReg = *SubRegs; ++SubRegs) {
 
376
      if (!PartUses.count(SubReg))
 
377
        continue;
 
378
      bool NeedDef = true;
 
379
      if (PhysRegDef[Reg] == PhysRegDef[SubReg]) {
 
380
        MachineOperand *MO = PhysRegDef[Reg]->findRegisterDefOperand(SubReg);
 
381
        if (MO) {
 
382
          NeedDef = false;
 
383
          assert(!MO->isDead());
 
384
        }
 
385
      }
 
386
      if (NeedDef)
 
387
        PhysRegDef[Reg]->addOperand(MachineOperand::CreateReg(SubReg,
 
388
                                                 true/*IsDef*/, true/*IsImp*/));
 
389
      MachineInstr *LastSubRef = FindLastRefOrPartRef(SubReg);
 
390
      if (LastSubRef)
 
391
        LastSubRef->addRegisterKilled(SubReg, TRI, true);
 
392
      else {
 
393
        LastRefOrPartRef->addRegisterKilled(SubReg, TRI, true);
 
394
        PhysRegUse[SubReg] = LastRefOrPartRef;
 
395
        for (const unsigned *SSRegs = TRI->getSubRegisters(SubReg);
 
396
             unsigned SSReg = *SSRegs; ++SSRegs)
 
397
          PhysRegUse[SSReg] = LastRefOrPartRef;
 
398
      }
 
399
      for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS)
 
400
        PartUses.erase(*SS);
 
401
    }
 
402
  } else if (LastRefOrPartRef == PhysRegDef[Reg] && LastRefOrPartRef != MI) {
 
403
    if (LastPartDef)
 
404
      // The last partial def kills the register.
 
405
      LastPartDef->addOperand(MachineOperand::CreateReg(Reg, false/*IsDef*/,
 
406
                                                true/*IsImp*/, true/*IsKill*/));
 
407
    else {
 
408
      MachineOperand *MO =
 
409
        LastRefOrPartRef->findRegisterDefOperand(Reg, false, TRI);
 
410
      bool NeedEC = MO->isEarlyClobber() && MO->getReg() != Reg;
 
411
      // If the last reference is the last def, then it's not used at all.
 
412
      // That is, unless we are currently processing the last reference itself.
 
413
      LastRefOrPartRef->addRegisterDead(Reg, TRI, true);
 
414
      if (NeedEC) {
 
415
        // If we are adding a subreg def and the superreg def is marked early
 
416
        // clobber, add an early clobber marker to the subreg def.
 
417
        MO = LastRefOrPartRef->findRegisterDefOperand(Reg);
 
418
        if (MO)
 
419
          MO->setIsEarlyClobber();
 
420
      }
 
421
    }
 
422
  } else
 
423
    LastRefOrPartRef->addRegisterKilled(Reg, TRI, true);
 
424
  return true;
 
425
}
 
426
 
 
427
void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI,
 
428
                                     SmallVector<unsigned, 4> &Defs) {
 
429
  // What parts of the register are previously defined?
 
430
  SmallSet<unsigned, 32> Live;
 
431
  if (PhysRegDef[Reg] || PhysRegUse[Reg]) {
 
432
    Live.insert(Reg);
 
433
    for (const unsigned *SS = TRI->getSubRegisters(Reg); *SS; ++SS)
 
434
      Live.insert(*SS);
 
435
  } else {
 
436
    for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
 
437
         unsigned SubReg = *SubRegs; ++SubRegs) {
 
438
      // If a register isn't itself defined, but all parts that make up of it
 
439
      // are defined, then consider it also defined.
 
440
      // e.g.
 
441
      // AL =
 
442
      // AH =
 
443
      //    = AX
 
444
      if (Live.count(SubReg))
 
445
        continue;
 
446
      if (PhysRegDef[SubReg] || PhysRegUse[SubReg]) {
 
447
        Live.insert(SubReg);
 
448
        for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS)
 
449
          Live.insert(*SS);
 
450
      }
 
451
    }
 
452
  }
 
453
 
 
454
  // Start from the largest piece, find the last time any part of the register
 
455
  // is referenced.
 
456
  HandlePhysRegKill(Reg, MI);
 
457
  // Only some of the sub-registers are used.
 
458
  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
 
459
       unsigned SubReg = *SubRegs; ++SubRegs) {
 
460
    if (!Live.count(SubReg))
 
461
      // Skip if this sub-register isn't defined.
 
462
      continue;
 
463
    HandlePhysRegKill(SubReg, MI);
 
464
  }
 
465
 
 
466
  if (MI)
 
467
    Defs.push_back(Reg);  // Remember this def.
 
468
}
 
469
 
 
470
void LiveVariables::UpdatePhysRegDefs(MachineInstr *MI,
 
471
                                      SmallVector<unsigned, 4> &Defs) {
 
472
  while (!Defs.empty()) {
 
473
    unsigned Reg = Defs.back();
 
474
    Defs.pop_back();
 
475
    PhysRegDef[Reg]  = MI;
 
476
    PhysRegUse[Reg]  = NULL;
 
477
    for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
 
478
         unsigned SubReg = *SubRegs; ++SubRegs) {
 
479
      PhysRegDef[SubReg]  = MI;
 
480
      PhysRegUse[SubReg]  = NULL;
 
481
    }
 
482
  }
 
483
}
 
484
 
 
485
namespace {
 
486
  struct RegSorter {
 
487
    const TargetRegisterInfo *TRI;
 
488
 
 
489
    RegSorter(const TargetRegisterInfo *tri) : TRI(tri) { }
 
490
    bool operator()(unsigned A, unsigned B) {
 
491
      if (TRI->isSubRegister(A, B))
 
492
        return true;
 
493
      else if (TRI->isSubRegister(B, A))
 
494
        return false;
 
495
      return A < B;
 
496
    }
 
497
  };
 
498
}
 
499
 
 
500
bool LiveVariables::runOnMachineFunction(MachineFunction &mf) {
 
501
  MF = &mf;
 
502
  MRI = &mf.getRegInfo();
 
503
  TRI = MF->getTarget().getRegisterInfo();
 
504
 
 
505
  ReservedRegisters = TRI->getReservedRegs(mf);
 
506
 
 
507
  unsigned NumRegs = TRI->getNumRegs();
 
508
  PhysRegDef  = new MachineInstr*[NumRegs];
 
509
  PhysRegUse  = new MachineInstr*[NumRegs];
 
510
  PHIVarInfo = new SmallVector<unsigned, 4>[MF->getNumBlockIDs()];
 
511
  std::fill(PhysRegDef,  PhysRegDef  + NumRegs, (MachineInstr*)0);
 
512
  std::fill(PhysRegUse,  PhysRegUse  + NumRegs, (MachineInstr*)0);
 
513
  PHIJoins.clear();
 
514
 
 
515
  /// Get some space for a respectable number of registers.
 
516
  VirtRegInfo.resize(64);
 
517
 
 
518
  analyzePHINodes(mf);
 
519
 
 
520
  // Calculate live variable information in depth first order on the CFG of the
 
521
  // function.  This guarantees that we will see the definition of a virtual
 
522
  // register before its uses due to dominance properties of SSA (except for PHI
 
523
  // nodes, which are treated as a special case).
 
524
  MachineBasicBlock *Entry = MF->begin();
 
525
  SmallPtrSet<MachineBasicBlock*,16> Visited;
 
526
 
 
527
  for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> >
 
528
         DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited);
 
529
       DFI != E; ++DFI) {
 
530
    MachineBasicBlock *MBB = *DFI;
 
531
 
 
532
    // Mark live-in registers as live-in.
 
533
    SmallVector<unsigned, 4> Defs;
 
534
    for (MachineBasicBlock::const_livein_iterator II = MBB->livein_begin(),
 
535
           EE = MBB->livein_end(); II != EE; ++II) {
 
536
      assert(TargetRegisterInfo::isPhysicalRegister(*II) &&
 
537
             "Cannot have a live-in virtual register!");
 
538
      HandlePhysRegDef(*II, 0, Defs);
 
539
    }
 
540
 
 
541
    // Loop over all of the instructions, processing them.
 
542
    DistanceMap.clear();
 
543
    unsigned Dist = 0;
 
544
    for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
 
545
         I != E; ++I) {
 
546
      MachineInstr *MI = I;
 
547
      if (MI->isDebugValue())
 
548
        continue;
 
549
      DistanceMap.insert(std::make_pair(MI, Dist++));
 
550
 
 
551
      // Process all of the operands of the instruction...
 
552
      unsigned NumOperandsToProcess = MI->getNumOperands();
 
553
 
 
554
      // Unless it is a PHI node.  In this case, ONLY process the DEF, not any
 
555
      // of the uses.  They will be handled in other basic blocks.
 
556
      if (MI->isPHI())
 
557
        NumOperandsToProcess = 1;
 
558
 
 
559
      SmallVector<unsigned, 4> UseRegs;
 
560
      SmallVector<unsigned, 4> DefRegs;
 
561
      for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
 
562
        const MachineOperand &MO = MI->getOperand(i);
 
563
        if (!MO.isReg() || MO.getReg() == 0)
 
564
          continue;
 
565
        unsigned MOReg = MO.getReg();
 
566
        if (MO.isUse())
 
567
          UseRegs.push_back(MOReg);
 
568
        if (MO.isDef())
 
569
          DefRegs.push_back(MOReg);
 
570
      }
 
571
 
 
572
      // Process all uses.
 
573
      for (unsigned i = 0, e = UseRegs.size(); i != e; ++i) {
 
574
        unsigned MOReg = UseRegs[i];
 
575
        if (TargetRegisterInfo::isVirtualRegister(MOReg))
 
576
          HandleVirtRegUse(MOReg, MBB, MI);
 
577
        else if (!ReservedRegisters[MOReg])
 
578
          HandlePhysRegUse(MOReg, MI);
 
579
      }
 
580
 
 
581
      // Process all defs.
 
582
      for (unsigned i = 0, e = DefRegs.size(); i != e; ++i) {
 
583
        unsigned MOReg = DefRegs[i];
 
584
        if (TargetRegisterInfo::isVirtualRegister(MOReg))
 
585
          HandleVirtRegDef(MOReg, MI);
 
586
        else if (!ReservedRegisters[MOReg])
 
587
          HandlePhysRegDef(MOReg, MI, Defs);
 
588
      }
 
589
      UpdatePhysRegDefs(MI, Defs);
 
590
    }
 
591
 
 
592
    // Handle any virtual assignments from PHI nodes which might be at the
 
593
    // bottom of this basic block.  We check all of our successor blocks to see
 
594
    // if they have PHI nodes, and if so, we simulate an assignment at the end
 
595
    // of the current block.
 
596
    if (!PHIVarInfo[MBB->getNumber()].empty()) {
 
597
      SmallVector<unsigned, 4>& VarInfoVec = PHIVarInfo[MBB->getNumber()];
 
598
 
 
599
      for (SmallVector<unsigned, 4>::iterator I = VarInfoVec.begin(),
 
600
             E = VarInfoVec.end(); I != E; ++I)
 
601
        // Mark it alive only in the block we are representing.
 
602
        MarkVirtRegAliveInBlock(getVarInfo(*I),MRI->getVRegDef(*I)->getParent(),
 
603
                                MBB);
 
604
    }
 
605
 
 
606
    // Finally, if the last instruction in the block is a return, make sure to
 
607
    // mark it as using all of the live-out values in the function.
 
608
    if (!MBB->empty() && MBB->back().getDesc().isReturn()) {
 
609
      MachineInstr *Ret = &MBB->back();
 
610
 
 
611
      for (MachineRegisterInfo::liveout_iterator
 
612
           I = MF->getRegInfo().liveout_begin(),
 
613
           E = MF->getRegInfo().liveout_end(); I != E; ++I) {
 
614
        assert(TargetRegisterInfo::isPhysicalRegister(*I) &&
 
615
               "Cannot have a live-out virtual register!");
 
616
        HandlePhysRegUse(*I, Ret);
 
617
 
 
618
        // Add live-out registers as implicit uses.
 
619
        if (!Ret->readsRegister(*I))
 
620
          Ret->addOperand(MachineOperand::CreateReg(*I, false, true));
 
621
      }
 
622
    }
 
623
 
 
624
    // Loop over PhysRegDef / PhysRegUse, killing any registers that are
 
625
    // available at the end of the basic block.
 
626
    for (unsigned i = 0; i != NumRegs; ++i)
 
627
      if (PhysRegDef[i] || PhysRegUse[i])
 
628
        HandlePhysRegDef(i, 0, Defs);
 
629
 
 
630
    std::fill(PhysRegDef,  PhysRegDef  + NumRegs, (MachineInstr*)0);
 
631
    std::fill(PhysRegUse,  PhysRegUse  + NumRegs, (MachineInstr*)0);
 
632
  }
 
633
 
 
634
  // Convert and transfer the dead / killed information we have gathered into
 
635
  // VirtRegInfo onto MI's.
 
636
  for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i)
 
637
    for (unsigned j = 0, e2 = VirtRegInfo[i].Kills.size(); j != e2; ++j)
 
638
      if (VirtRegInfo[i].Kills[j] ==
 
639
          MRI->getVRegDef(i + TargetRegisterInfo::FirstVirtualRegister))
 
640
        VirtRegInfo[i]
 
641
          .Kills[j]->addRegisterDead(i +
 
642
                                     TargetRegisterInfo::FirstVirtualRegister,
 
643
                                     TRI);
 
644
      else
 
645
        VirtRegInfo[i]
 
646
          .Kills[j]->addRegisterKilled(i +
 
647
                                       TargetRegisterInfo::FirstVirtualRegister,
 
648
                                       TRI);
 
649
 
 
650
  // Check to make sure there are no unreachable blocks in the MC CFG for the
 
651
  // function.  If so, it is due to a bug in the instruction selector or some
 
652
  // other part of the code generator if this happens.
 
653
#ifndef NDEBUG
 
654
  for(MachineFunction::iterator i = MF->begin(), e = MF->end(); i != e; ++i)
 
655
    assert(Visited.count(&*i) != 0 && "unreachable basic block found");
 
656
#endif
 
657
 
 
658
  delete[] PhysRegDef;
 
659
  delete[] PhysRegUse;
 
660
  delete[] PHIVarInfo;
 
661
 
 
662
  return false;
 
663
}
 
664
 
 
665
/// replaceKillInstruction - Update register kill info by replacing a kill
 
666
/// instruction with a new one.
 
667
void LiveVariables::replaceKillInstruction(unsigned Reg, MachineInstr *OldMI,
 
668
                                           MachineInstr *NewMI) {
 
669
  VarInfo &VI = getVarInfo(Reg);
 
670
  std::replace(VI.Kills.begin(), VI.Kills.end(), OldMI, NewMI);
 
671
}
 
672
 
 
673
/// removeVirtualRegistersKilled - Remove all killed info for the specified
 
674
/// instruction.
 
675
void LiveVariables::removeVirtualRegistersKilled(MachineInstr *MI) {
 
676
  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 
677
    MachineOperand &MO = MI->getOperand(i);
 
678
    if (MO.isReg() && MO.isKill()) {
 
679
      MO.setIsKill(false);
 
680
      unsigned Reg = MO.getReg();
 
681
      if (TargetRegisterInfo::isVirtualRegister(Reg)) {
 
682
        bool removed = getVarInfo(Reg).removeKill(MI);
 
683
        assert(removed && "kill not in register's VarInfo?");
 
684
        removed = true;
 
685
      }
 
686
    }
 
687
  }
 
688
}
 
689
 
 
690
/// analyzePHINodes - Gather information about the PHI nodes in here. In
 
691
/// particular, we want to map the variable information of a virtual register
 
692
/// which is used in a PHI node. We map that to the BB the vreg is coming from.
 
693
///
 
694
void LiveVariables::analyzePHINodes(const MachineFunction& Fn) {
 
695
  for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end();
 
696
       I != E; ++I)
 
697
    for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end();
 
698
         BBI != BBE && BBI->isPHI(); ++BBI)
 
699
      for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
 
700
        PHIVarInfo[BBI->getOperand(i + 1).getMBB()->getNumber()]
 
701
          .push_back(BBI->getOperand(i).getReg());
 
702
}
 
703
 
 
704
bool LiveVariables::VarInfo::isLiveIn(const MachineBasicBlock &MBB,
 
705
                                      unsigned Reg,
 
706
                                      MachineRegisterInfo &MRI) {
 
707
  unsigned Num = MBB.getNumber();
 
708
 
 
709
  // Reg is live-through.
 
710
  if (AliveBlocks.test(Num))
 
711
    return true;
 
712
 
 
713
  // Registers defined in MBB cannot be live in.
 
714
  const MachineInstr *Def = MRI.getVRegDef(Reg);
 
715
  if (Def && Def->getParent() == &MBB)
 
716
    return false;
 
717
 
 
718
 // Reg was not defined in MBB, was it killed here?
 
719
  return findKill(&MBB);
 
720
}
 
721
 
 
722
bool LiveVariables::isLiveOut(unsigned Reg, const MachineBasicBlock &MBB) {
 
723
  LiveVariables::VarInfo &VI = getVarInfo(Reg);
 
724
 
 
725
  // Loop over all of the successors of the basic block, checking to see if
 
726
  // the value is either live in the block, or if it is killed in the block.
 
727
  std::vector<MachineBasicBlock*> OpSuccBlocks;
 
728
  for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(),
 
729
         E = MBB.succ_end(); SI != E; ++SI) {
 
730
    MachineBasicBlock *SuccMBB = *SI;
 
731
 
 
732
    // Is it alive in this successor?
 
733
    unsigned SuccIdx = SuccMBB->getNumber();
 
734
    if (VI.AliveBlocks.test(SuccIdx))
 
735
      return true;
 
736
    OpSuccBlocks.push_back(SuccMBB);
 
737
  }
 
738
 
 
739
  // Check to see if this value is live because there is a use in a successor
 
740
  // that kills it.
 
741
  switch (OpSuccBlocks.size()) {
 
742
  case 1: {
 
743
    MachineBasicBlock *SuccMBB = OpSuccBlocks[0];
 
744
    for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i)
 
745
      if (VI.Kills[i]->getParent() == SuccMBB)
 
746
        return true;
 
747
    break;
 
748
  }
 
749
  case 2: {
 
750
    MachineBasicBlock *SuccMBB1 = OpSuccBlocks[0], *SuccMBB2 = OpSuccBlocks[1];
 
751
    for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i)
 
752
      if (VI.Kills[i]->getParent() == SuccMBB1 ||
 
753
          VI.Kills[i]->getParent() == SuccMBB2)
 
754
        return true;
 
755
    break;
 
756
  }
 
757
  default:
 
758
    std::sort(OpSuccBlocks.begin(), OpSuccBlocks.end());
 
759
    for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i)
 
760
      if (std::binary_search(OpSuccBlocks.begin(), OpSuccBlocks.end(),
 
761
                             VI.Kills[i]->getParent()))
 
762
        return true;
 
763
  }
 
764
  return false;
 
765
}
 
766
 
 
767
/// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All
 
768
/// variables that are live out of DomBB will be marked as passing live through
 
769
/// BB.
 
770
void LiveVariables::addNewBlock(MachineBasicBlock *BB,
 
771
                                MachineBasicBlock *DomBB,
 
772
                                MachineBasicBlock *SuccBB) {
 
773
  const unsigned NumNew = BB->getNumber();
 
774
 
 
775
  // All registers used by PHI nodes in SuccBB must be live through BB.
 
776
  for (MachineBasicBlock::const_iterator BBI = SuccBB->begin(),
 
777
         BBE = SuccBB->end(); BBI != BBE && BBI->isPHI(); ++BBI)
 
778
    for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
 
779
      if (BBI->getOperand(i+1).getMBB() == BB)
 
780
        getVarInfo(BBI->getOperand(i).getReg()).AliveBlocks.set(NumNew);
 
781
 
 
782
  // Update info for all live variables
 
783
  for (unsigned Reg = TargetRegisterInfo::FirstVirtualRegister,
 
784
         E = MRI->getLastVirtReg()+1; Reg != E; ++Reg) {
 
785
    VarInfo &VI = getVarInfo(Reg);
 
786
    if (!VI.AliveBlocks.test(NumNew) && VI.isLiveIn(*SuccBB, Reg, *MRI))
 
787
      VI.AliveBlocks.set(NumNew);
 
788
  }
 
789
}