← 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/ProcessImplicitDefs.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/ProcessImplicitDefs.cpp
1
 
//===---------------------- ProcessImplicitDefs.cpp -----------------------===//
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 "processimplicitdefs"
11
 
 
12
 
#include "llvm/CodeGen/ProcessImplicitDefs.h"
13
 
 
14
 
#include "llvm/ADT/DepthFirstIterator.h"
15
 
#include "llvm/ADT/SmallSet.h"
16
 
#include "llvm/Analysis/AliasAnalysis.h"
17
 
#include "llvm/CodeGen/LiveVariables.h"
18
 
#include "llvm/CodeGen/MachineInstr.h"
19
 
#include "llvm/CodeGen/MachineRegisterInfo.h"
20
 
#include "llvm/CodeGen/Passes.h"
21
 
#include "llvm/Support/Debug.h"
22
 
#include "llvm/Target/TargetInstrInfo.h"
23
 
#include "llvm/Target/TargetRegisterInfo.h"
24
 
 
25
 
 
26
 
using namespace llvm;
27
 
 
28
 
char ProcessImplicitDefs::ID = 0;
29
 
INITIALIZE_PASS(ProcessImplicitDefs, "processimpdefs",
30
 
                "Process Implicit Definitions.", false, false);
31
 
 
32
 
void ProcessImplicitDefs::getAnalysisUsage(AnalysisUsage &AU) const {
33
 
  AU.setPreservesCFG();
34
 
  AU.addPreserved<AliasAnalysis>();
35
 
  AU.addPreserved<LiveVariables>();
36
 
  AU.addRequired<LiveVariables>();
37
 
  AU.addPreservedID(MachineLoopInfoID);
38
 
  AU.addPreservedID(MachineDominatorsID);
39
 
  AU.addPreservedID(TwoAddressInstructionPassID);
40
 
  AU.addPreservedID(PHIEliminationID);
41
 
  MachineFunctionPass::getAnalysisUsage(AU);
42
 
}
43
 
 
44
 
bool
45
 
ProcessImplicitDefs::CanTurnIntoImplicitDef(MachineInstr *MI,
46
 
                                            unsigned Reg, unsigned OpIdx,
47
 
                                            const TargetInstrInfo *tii_,
48
 
                                            SmallSet<unsigned, 8> &ImpDefRegs) {
49
 
  switch(OpIdx) {
50
 
  case 1:
51
 
    return MI->isCopy() && (MI->getOperand(0).getSubReg() == 0 ||
52
 
                            ImpDefRegs.count(MI->getOperand(0).getReg()));
53
 
  case 2:
54
 
    return MI->isSubregToReg() && (MI->getOperand(0).getSubReg() == 0 ||
55
 
                                  ImpDefRegs.count(MI->getOperand(0).getReg()));
56
 
  default: return false;
57
 
  }
58
 
}
59
 
 
60
 
static bool isUndefCopy(MachineInstr *MI, unsigned Reg,
61
 
                        const TargetInstrInfo *tii_,
62
 
                        SmallSet<unsigned, 8> &ImpDefRegs) {
63
 
  if (MI->isCopy()) {
64
 
    MachineOperand &MO0 = MI->getOperand(0);
65
 
    MachineOperand &MO1 = MI->getOperand(1);
66
 
    if (MO1.getReg() != Reg)
67
 
      return false;
68
 
    if (!MO0.getSubReg() || ImpDefRegs.count(MO0.getReg()))
69
 
      return true;
70
 
    return false;
71
 
  }
72
 
  return false;
73
 
}
74
 
 
75
 
/// processImplicitDefs - Process IMPLICIT_DEF instructions and make sure
76
 
/// there is one implicit_def for each use. Add isUndef marker to
77
 
/// implicit_def defs and their uses.
78
 
bool ProcessImplicitDefs::runOnMachineFunction(MachineFunction &fn) {
79
 
 
80
 
  DEBUG(dbgs() << "********** PROCESS IMPLICIT DEFS **********\n"
81
 
               << "********** Function: "
82
 
               << ((Value*)fn.getFunction())->getName() << '\n');
83
 
 
84
 
  bool Changed = false;
85
 
 
86
 
  const TargetInstrInfo *tii_ = fn.getTarget().getInstrInfo();
87
 
  const TargetRegisterInfo *tri_ = fn.getTarget().getRegisterInfo();
88
 
  MachineRegisterInfo *mri_ = &fn.getRegInfo();
89
 
 
90
 
  LiveVariables *lv_ = &getAnalysis<LiveVariables>();
91
 
 
92
 
  SmallSet<unsigned, 8> ImpDefRegs;
93
 
  SmallVector<MachineInstr*, 8> ImpDefMIs;
94
 
  SmallVector<MachineInstr*, 4> RUses;
95
 
  SmallPtrSet<MachineBasicBlock*,16> Visited;
96
 
  SmallPtrSet<MachineInstr*, 8> ModInsts;
97
 
 
98
 
  MachineBasicBlock *Entry = fn.begin();
99
 
  for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> >
100
 
         DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited);
101
 
       DFI != E; ++DFI) {
102
 
    MachineBasicBlock *MBB = *DFI;
103
 
    for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
104
 
         I != E; ) {
105
 
      MachineInstr *MI = &*I;
106
 
      ++I;
107
 
      if (MI->isImplicitDef()) {
108
 
        if (MI->getOperand(0).getSubReg())
109
 
          continue;
110
 
        unsigned Reg = MI->getOperand(0).getReg();
111
 
        ImpDefRegs.insert(Reg);
112
 
        if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
113
 
          for (const unsigned *SS = tri_->getSubRegisters(Reg); *SS; ++SS)
114
 
            ImpDefRegs.insert(*SS);
115
 
        }
116
 
        ImpDefMIs.push_back(MI);
117
 
        continue;
118
 
      }
119
 
 
120
 
      // Eliminate %reg1032:sub<def> = COPY undef.
121
 
      if (MI->isCopy() && MI->getOperand(0).getSubReg()) {
122
 
        MachineOperand &MO = MI->getOperand(1);
123
 
        if (MO.isUndef() || ImpDefRegs.count(MO.getReg())) {
124
 
          if (MO.isKill()) {
125
 
            LiveVariables::VarInfo& vi = lv_->getVarInfo(MO.getReg());
126
 
            vi.removeKill(MI);
127
 
          }
128
 
          MI->eraseFromParent();
129
 
          Changed = true;
130
 
          continue;
131
 
        }
132
 
      }
133
 
 
134
 
      bool ChangedToImpDef = false;
135
 
      for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
136
 
        MachineOperand& MO = MI->getOperand(i);
137
 
        if (!MO.isReg() || (MO.isDef() && !MO.getSubReg()) || MO.isUndef())
138
 
          continue;
139
 
        unsigned Reg = MO.getReg();
140
 
        if (!Reg)
141
 
          continue;
142
 
        if (!ImpDefRegs.count(Reg))
143
 
          continue;
144
 
        // Use is a copy, just turn it into an implicit_def.
145
 
        if (CanTurnIntoImplicitDef(MI, Reg, i, tii_, ImpDefRegs)) {
146
 
          bool isKill = MO.isKill();
147
 
          MI->setDesc(tii_->get(TargetOpcode::IMPLICIT_DEF));
148
 
          for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j)
149
 
            MI->RemoveOperand(j);
150
 
          if (isKill) {
151
 
            ImpDefRegs.erase(Reg);
152
 
            LiveVariables::VarInfo& vi = lv_->getVarInfo(Reg);
153
 
            vi.removeKill(MI);
154
 
          }
155
 
          ChangedToImpDef = true;
156
 
          Changed = true;
157
 
          break;
158
 
        }
159
 
 
160
 
        Changed = true;
161
 
        MO.setIsUndef();
162
 
        // This is a partial register redef of an implicit def.
163
 
        // Make sure the whole register is defined by the instruction.
164
 
        if (MO.isDef()) {
165
 
          MI->addRegisterDefined(Reg);
166
 
          continue;
167
 
        }
168
 
        if (MO.isKill() || MI->isRegTiedToDefOperand(i)) {
169
 
          // Make sure other uses of 
170
 
          for (unsigned j = i+1; j != e; ++j) {
171
 
            MachineOperand &MOJ = MI->getOperand(j);
172
 
            if (MOJ.isReg() && MOJ.isUse() && MOJ.getReg() == Reg)
173
 
              MOJ.setIsUndef();
174
 
          }
175
 
          ImpDefRegs.erase(Reg);
176
 
        }
177
 
      }
178
 
 
179
 
      if (ChangedToImpDef) {
180
 
        // Backtrack to process this new implicit_def.
181
 
        --I;
182
 
      } else {
183
 
        for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
184
 
          MachineOperand& MO = MI->getOperand(i);
185
 
          if (!MO.isReg() || !MO.isDef())
186
 
            continue;
187
 
          ImpDefRegs.erase(MO.getReg());
188
 
        }
189
 
      }
190
 
    }
191
 
 
192
 
    // Any outstanding liveout implicit_def's?
193
 
    for (unsigned i = 0, e = ImpDefMIs.size(); i != e; ++i) {
194
 
      MachineInstr *MI = ImpDefMIs[i];
195
 
      unsigned Reg = MI->getOperand(0).getReg();
196
 
      if (TargetRegisterInfo::isPhysicalRegister(Reg) ||
197
 
          !ImpDefRegs.count(Reg)) {
198
 
        // Delete all "local" implicit_def's. That include those which define
199
 
        // physical registers since they cannot be liveout.
200
 
        MI->eraseFromParent();
201
 
        Changed = true;
202
 
        continue;
203
 
      }
204
 
 
205
 
      // If there are multiple defs of the same register and at least one
206
 
      // is not an implicit_def, do not insert implicit_def's before the
207
 
      // uses.
208
 
      bool Skip = false;
209
 
      SmallVector<MachineInstr*, 4> DeadImpDefs;
210
 
      for (MachineRegisterInfo::def_iterator DI = mri_->def_begin(Reg),
211
 
             DE = mri_->def_end(); DI != DE; ++DI) {
212
 
        MachineInstr *DeadImpDef = &*DI;
213
 
        if (!DeadImpDef->isImplicitDef()) {
214
 
          Skip = true;
215
 
          break;
216
 
        }
217
 
        DeadImpDefs.push_back(DeadImpDef);
218
 
      }
219
 
      if (Skip)
220
 
        continue;
221
 
 
222
 
      // The only implicit_def which we want to keep are those that are live
223
 
      // out of its block.
224
 
      for (unsigned j = 0, ee = DeadImpDefs.size(); j != ee; ++j)
225
 
        DeadImpDefs[j]->eraseFromParent();
226
 
      Changed = true;
227
 
 
228
 
      // Process each use instruction once.
229
 
      for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg),
230
 
             UE = mri_->use_end(); UI != UE; ++UI) {
231
 
        if (UI.getOperand().isUndef())
232
 
          continue;
233
 
        MachineInstr *RMI = &*UI;
234
 
        if (ModInsts.insert(RMI))
235
 
          RUses.push_back(RMI);
236
 
      }
237
 
 
238
 
      for (unsigned i = 0, e = RUses.size(); i != e; ++i) {
239
 
        MachineInstr *RMI = RUses[i];
240
 
 
241
 
        // Turn a copy use into an implicit_def.
242
 
        if (isUndefCopy(RMI, Reg, tii_, ImpDefRegs)) {
243
 
          RMI->setDesc(tii_->get(TargetOpcode::IMPLICIT_DEF));
244
 
 
245
 
          bool isKill = false;
246
 
          SmallVector<unsigned, 4> Ops;
247
 
          for (unsigned j = 0, ee = RMI->getNumOperands(); j != ee; ++j) {
248
 
            MachineOperand &RRMO = RMI->getOperand(j);
249
 
            if (RRMO.isReg() && RRMO.getReg() == Reg) {
250
 
              Ops.push_back(j);
251
 
              if (RRMO.isKill())
252
 
                isKill = true;
253
 
            }
254
 
          }
255
 
          // Leave the other operands along.
256
 
          for (unsigned j = 0, ee = Ops.size(); j != ee; ++j) {
257
 
            unsigned OpIdx = Ops[j];
258
 
            RMI->RemoveOperand(OpIdx-j);
259
 
          }
260
 
 
261
 
          // Update LiveVariables varinfo if the instruction is a kill.
262
 
          if (isKill) {
263
 
            LiveVariables::VarInfo& vi = lv_->getVarInfo(Reg);
264
 
            vi.removeKill(RMI);
265
 
          }
266
 
          continue;
267
 
        }
268
 
 
269
 
        // Replace Reg with a new vreg that's marked implicit.
270
 
        const TargetRegisterClass* RC = mri_->getRegClass(Reg);
271
 
        unsigned NewVReg = mri_->createVirtualRegister(RC);
272
 
        bool isKill = true;
273
 
        for (unsigned j = 0, ee = RMI->getNumOperands(); j != ee; ++j) {
274
 
          MachineOperand &RRMO = RMI->getOperand(j);
275
 
          if (RRMO.isReg() && RRMO.getReg() == Reg) {
276
 
            RRMO.setReg(NewVReg);
277
 
            RRMO.setIsUndef();
278
 
            if (isKill) {
279
 
              // Only the first operand of NewVReg is marked kill.
280
 
              RRMO.setIsKill();
281
 
              isKill = false;
282
 
            }
283
 
          }
284
 
        }
285
 
      }
286
 
      RUses.clear();
287
 
      ModInsts.clear();
288
 
    }
289
 
    ImpDefRegs.clear();
290
 
    ImpDefMIs.clear();
291
 
  }
292
 
 
293
 
  return Changed;
294
 
}
295