← Back to branch summary

~louis/ubuntu/trusty/clamav/lp799623_fix_logrotate

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/include/llvm/CodeGen/LiveVariables.h

  • 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/include/llvm/CodeGen/LiveVariables.h
 
1
//===-- llvm/CodeGen/LiveVariables.h - Live Variable Analysis ---*- C++ -*-===//
 
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 LiveVariables 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 a 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
#ifndef LLVM_CODEGEN_LIVEVARIABLES_H
 
30
#define LLVM_CODEGEN_LIVEVARIABLES_H
 
31
 
 
32
#include "llvm/CodeGen/MachineBasicBlock.h"
 
33
#include "llvm/CodeGen/MachineFunctionPass.h"
 
34
#include "llvm/CodeGen/MachineInstr.h"
 
35
#include "llvm/ADT/BitVector.h"
 
36
#include "llvm/ADT/DenseMap.h"
 
37
#include "llvm/ADT/SmallSet.h"
 
38
#include "llvm/ADT/SmallVector.h"
 
39
#include "llvm/ADT/SparseBitVector.h"
 
40
 
 
41
namespace llvm {
 
42
 
 
43
class MachineRegisterInfo;
 
44
class TargetRegisterInfo;
 
45
 
 
46
class LiveVariables : public MachineFunctionPass {
 
47
public:
 
48
  static char ID; // Pass identification, replacement for typeid
 
49
  LiveVariables() : MachineFunctionPass(&ID) {}
 
50
 
 
51
  /// VarInfo - This represents the regions where a virtual register is live in
 
52
  /// the program.  We represent this with three different pieces of
 
53
  /// information: the set of blocks in which the instruction is live
 
54
  /// throughout, the set of blocks in which the instruction is actually used,
 
55
  /// and the set of non-phi instructions that are the last users of the value.
 
56
  ///
 
57
  /// In the common case where a value is defined and killed in the same block,
 
58
  /// There is one killing instruction, and AliveBlocks is empty.
 
59
  ///
 
60
  /// Otherwise, the value is live out of the block.  If the value is live
 
61
  /// throughout any blocks, these blocks are listed in AliveBlocks.  Blocks
 
62
  /// where the liveness range ends are not included in AliveBlocks, instead
 
63
  /// being captured by the Kills set.  In these blocks, the value is live into
 
64
  /// the block (unless the value is defined and killed in the same block) and
 
65
  /// lives until the specified instruction.  Note that there cannot ever be a
 
66
  /// value whose Kills set contains two instructions from the same basic block.
 
67
  ///
 
68
  /// PHI nodes complicate things a bit.  If a PHI node is the last user of a
 
69
  /// value in one of its predecessor blocks, it is not listed in the kills set,
 
70
  /// but does include the predecessor block in the AliveBlocks set (unless that
 
71
  /// block also defines the value).  This leads to the (perfectly sensical)
 
72
  /// situation where a value is defined in a block, and the last use is a phi
 
73
  /// node in the successor.  In this case, AliveBlocks is empty (the value is
 
74
  /// not live across any  blocks) and Kills is empty (phi nodes are not
 
75
  /// included). This is sensical because the value must be live to the end of
 
76
  /// the block, but is not live in any successor blocks.
 
77
  struct VarInfo {
 
78
    /// AliveBlocks - Set of blocks in which this value is alive completely
 
79
    /// through.  This is a bit set which uses the basic block number as an
 
80
    /// index.
 
81
    ///
 
82
    SparseBitVector<> AliveBlocks;
 
83
 
 
84
    /// NumUses - Number of uses of this register across the entire function.
 
85
    ///
 
86
    unsigned NumUses;
 
87
 
 
88
    /// Kills - List of MachineInstruction's which are the last use of this
 
89
    /// virtual register (kill it) in their basic block.
 
90
    ///
 
91
    std::vector<MachineInstr*> Kills;
 
92
 
 
93
    VarInfo() : NumUses(0) {}
 
94
 
 
95
    /// removeKill - Delete a kill corresponding to the specified
 
96
    /// machine instruction. Returns true if there was a kill
 
97
    /// corresponding to this instruction, false otherwise.
 
98
    bool removeKill(MachineInstr *MI) {
 
99
      std::vector<MachineInstr*>::iterator
 
100
        I = std::find(Kills.begin(), Kills.end(), MI);
 
101
      if (I == Kills.end())
 
102
        return false;
 
103
      Kills.erase(I);
 
104
      return true;
 
105
    }
 
106
 
 
107
    /// findKill - Find a kill instruction in MBB. Return NULL if none is found.
 
108
    MachineInstr *findKill(const MachineBasicBlock *MBB) const;
 
109
 
 
110
    /// isLiveIn - Is Reg live in to MBB? This means that Reg is live through
 
111
    /// MBB, or it is killed in MBB. If Reg is only used by PHI instructions in
 
112
    /// MBB, it is not considered live in.
 
113
    bool isLiveIn(const MachineBasicBlock &MBB,
 
114
                  unsigned Reg,
 
115
                  MachineRegisterInfo &MRI);
 
116
 
 
117
    void dump() const;
 
118
  };
 
119
 
 
120
private:
 
121
  /// VirtRegInfo - This list is a mapping from virtual register number to
 
122
  /// variable information.  FirstVirtualRegister is subtracted from the virtual
 
123
  /// register number before indexing into this list.
 
124
  ///
 
125
  std::vector<VarInfo> VirtRegInfo;
 
126
 
 
127
  /// PHIJoins - list of virtual registers that are PHI joins. These registers
 
128
  /// may have multiple definitions, and they require special handling when
 
129
  /// building live intervals.
 
130
  SparseBitVector<> PHIJoins;
 
131
 
 
132
  /// ReservedRegisters - This vector keeps track of which registers
 
133
  /// are reserved register which are not allocatable by the target machine.
 
134
  /// We can not track liveness for values that are in this set.
 
135
  ///
 
136
  BitVector ReservedRegisters;
 
137
 
 
138
private:   // Intermediate data structures
 
139
  MachineFunction *MF;
 
140
 
 
141
  MachineRegisterInfo* MRI;
 
142
 
 
143
  const TargetRegisterInfo *TRI;
 
144
 
 
145
  // PhysRegInfo - Keep track of which instruction was the last def of a
 
146
  // physical register. This is a purely local property, because all physical
 
147
  // register references are presumed dead across basic blocks.
 
148
  MachineInstr **PhysRegDef;
 
149
 
 
150
  // PhysRegInfo - Keep track of which instruction was the last use of a
 
151
  // physical register. This is a purely local property, because all physical
 
152
  // register references are presumed dead across basic blocks.
 
153
  MachineInstr **PhysRegUse;
 
154
 
 
155
  SmallVector<unsigned, 4> *PHIVarInfo;
 
156
 
 
157
  // DistanceMap - Keep track the distance of a MI from the start of the
 
158
  // current basic block.
 
159
  DenseMap<MachineInstr*, unsigned> DistanceMap;
 
160
 
 
161
  /// HandlePhysRegKill - Add kills of Reg and its sub-registers to the
 
162
  /// uses. Pay special attention to the sub-register uses which may come below
 
163
  /// the last use of the whole register.
 
164
  bool HandlePhysRegKill(unsigned Reg, MachineInstr *MI);
 
165
 
 
166
  void HandlePhysRegUse(unsigned Reg, MachineInstr *MI);
 
167
  void HandlePhysRegDef(unsigned Reg, MachineInstr *MI,
 
168
                        SmallVector<unsigned, 4> &Defs);
 
169
  void UpdatePhysRegDefs(MachineInstr *MI, SmallVector<unsigned, 4> &Defs);
 
170
 
 
171
  /// FindLastRefOrPartRef - Return the last reference or partial reference of
 
172
  /// the specified register.
 
173
  MachineInstr *FindLastRefOrPartRef(unsigned Reg);
 
174
 
 
175
  /// FindLastPartialDef - Return the last partial def of the specified
 
176
  /// register. Also returns the sub-registers that're defined by the
 
177
  /// instruction.
 
178
  MachineInstr *FindLastPartialDef(unsigned Reg,
 
179
                                   SmallSet<unsigned,4> &PartDefRegs);
 
180
 
 
181
  /// analyzePHINodes - Gather information about the PHI nodes in here. In
 
182
  /// particular, we want to map the variable information of a virtual
 
183
  /// register which is used in a PHI node. We map that to the BB the vreg
 
184
  /// is coming from.
 
185
  void analyzePHINodes(const MachineFunction& Fn);
 
186
public:
 
187
 
 
188
  virtual bool runOnMachineFunction(MachineFunction &MF);
 
189
 
 
190
  /// RegisterDefIsDead - Return true if the specified instruction defines the
 
191
  /// specified register, but that definition is dead.
 
192
  bool RegisterDefIsDead(MachineInstr *MI, unsigned Reg) const;
 
193
 
 
194
  //===--------------------------------------------------------------------===//
 
195
  //  API to update live variable information
 
196
 
 
197
  /// replaceKillInstruction - Update register kill info by replacing a kill
 
198
  /// instruction with a new one.
 
199
  void replaceKillInstruction(unsigned Reg, MachineInstr *OldMI,
 
200
                              MachineInstr *NewMI);
 
201
 
 
202
  /// addVirtualRegisterKilled - Add information about the fact that the
 
203
  /// specified register is killed after being used by the specified
 
204
  /// instruction. If AddIfNotFound is true, add a implicit operand if it's
 
205
  /// not found.
 
206
  void addVirtualRegisterKilled(unsigned IncomingReg, MachineInstr *MI,
 
207
                                bool AddIfNotFound = false) {
 
208
    if (MI->addRegisterKilled(IncomingReg, TRI, AddIfNotFound))
 
209
      getVarInfo(IncomingReg).Kills.push_back(MI); 
 
210
  }
 
211
 
 
212
  /// removeVirtualRegisterKilled - Remove the specified kill of the virtual
 
213
  /// register from the live variable information. Returns true if the
 
214
  /// variable was marked as killed by the specified instruction,
 
215
  /// false otherwise.
 
216
  bool removeVirtualRegisterKilled(unsigned reg, MachineInstr *MI) {
 
217
    if (!getVarInfo(reg).removeKill(MI))
 
218
      return false;
 
219
 
 
220
    bool Removed = false;
 
221
    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 
222
      MachineOperand &MO = MI->getOperand(i);
 
223
      if (MO.isReg() && MO.isKill() && MO.getReg() == reg) {
 
224
        MO.setIsKill(false);
 
225
        Removed = true;
 
226
        break;
 
227
      }
 
228
    }
 
229
 
 
230
    assert(Removed && "Register is not used by this instruction!");
 
231
    return true;
 
232
  }
 
233
 
 
234
  /// removeVirtualRegistersKilled - Remove all killed info for the specified
 
235
  /// instruction.
 
236
  void removeVirtualRegistersKilled(MachineInstr *MI);
 
237
 
 
238
  /// addVirtualRegisterDead - Add information about the fact that the specified
 
239
  /// register is dead after being used by the specified instruction. If
 
240
  /// AddIfNotFound is true, add a implicit operand if it's not found.
 
241
  void addVirtualRegisterDead(unsigned IncomingReg, MachineInstr *MI,
 
242
                              bool AddIfNotFound = false) {
 
243
    if (MI->addRegisterDead(IncomingReg, TRI, AddIfNotFound))
 
244
      getVarInfo(IncomingReg).Kills.push_back(MI);
 
245
  }
 
246
 
 
247
  /// removeVirtualRegisterDead - Remove the specified kill of the virtual
 
248
  /// register from the live variable information. Returns true if the
 
249
  /// variable was marked dead at the specified instruction, false
 
250
  /// otherwise.
 
251
  bool removeVirtualRegisterDead(unsigned reg, MachineInstr *MI) {
 
252
    if (!getVarInfo(reg).removeKill(MI))
 
253
      return false;
 
254
 
 
255
    bool Removed = false;
 
256
    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 
257
      MachineOperand &MO = MI->getOperand(i);
 
258
      if (MO.isReg() && MO.isDef() && MO.getReg() == reg) {
 
259
        MO.setIsDead(false);
 
260
        Removed = true;
 
261
        break;
 
262
      }
 
263
    }
 
264
    assert(Removed && "Register is not defined by this instruction!");
 
265
    return true;
 
266
  }
 
267
  
 
268
  void getAnalysisUsage(AnalysisUsage &AU) const;
 
269
 
 
270
  virtual void releaseMemory() {
 
271
    VirtRegInfo.clear();
 
272
  }
 
273
 
 
274
  /// getVarInfo - Return the VarInfo structure for the specified VIRTUAL
 
275
  /// register.
 
276
  VarInfo &getVarInfo(unsigned RegIdx);
 
277
 
 
278
  void MarkVirtRegAliveInBlock(VarInfo& VRInfo, MachineBasicBlock* DefBlock,
 
279
                               MachineBasicBlock *BB);
 
280
  void MarkVirtRegAliveInBlock(VarInfo& VRInfo, MachineBasicBlock* DefBlock,
 
281
                               MachineBasicBlock *BB,
 
282
                               std::vector<MachineBasicBlock*> &WorkList);
 
283
  void HandleVirtRegDef(unsigned reg, MachineInstr *MI);
 
284
  void HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB,
 
285
                        MachineInstr *MI);
 
286
 
 
287
  bool isLiveIn(unsigned Reg, const MachineBasicBlock &MBB) {
 
288
    return getVarInfo(Reg).isLiveIn(MBB, Reg, *MRI);
 
289
  }
 
290
 
 
291
  /// isLiveOut - Determine if Reg is live out from MBB, when not considering
 
292
  /// PHI nodes. This means that Reg is either killed by a successor block or
 
293
  /// passed through one.
 
294
  bool isLiveOut(unsigned Reg, const MachineBasicBlock &MBB);
 
295
 
 
296
  /// addNewBlock - Add a new basic block BB between DomBB and SuccBB. All
 
297
  /// variables that are live out of DomBB and live into SuccBB will be marked
 
298
  /// as passing live through BB. This method assumes that the machine code is
 
299
  /// still in SSA form.
 
300
  void addNewBlock(MachineBasicBlock *BB,
 
301
                   MachineBasicBlock *DomBB,
 
302
                   MachineBasicBlock *SuccBB);
 
303
 
 
304
  /// isPHIJoin - Return true if Reg is a phi join register.
 
305
  bool isPHIJoin(unsigned Reg) { return PHIJoins.test(Reg); }
 
306
 
 
307
  /// setPHIJoin - Mark Reg as a phi join register.
 
308
  void setPHIJoin(unsigned Reg) { PHIJoins.set(Reg); }
 
309
};
 
310
 
 
311
} // End llvm namespace
 
312
 
 
313
#endif