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