ProcessImplicitDefs.cpp revision b1aa5e43a2976caed47e21d31823a48bf8324000 
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/SetVector.h"
13#include "llvm/Analysis/AliasAnalysis.h"
14#include "llvm/CodeGen/MachineFunctionPass.h"
15#include "llvm/CodeGen/MachineInstr.h"
16#include "llvm/CodeGen/MachineRegisterInfo.h"
17#include "llvm/CodeGen/Passes.h"
18#include "llvm/Support/Debug.h"
19#include "llvm/Support/raw_ostream.h"
20#include "llvm/Target/TargetInstrInfo.h"
21
22using namespace llvm;
23
24namespace {
25/// Process IMPLICIT_DEF instructions and make sure there is one implicit_def
26/// for each use. Add isUndef marker to implicit_def defs and their uses.
27class ProcessImplicitDefs : public MachineFunctionPass {
28  const TargetInstrInfo *TII;
29  const TargetRegisterInfo *TRI;
30  MachineRegisterInfo *MRI;
31
32  SmallSetVector<MachineInstr*, 16> WorkList;
33
34  void processImplicitDef(MachineInstr *MI);
35  bool canTurnIntoImplicitDef(MachineInstr *MI);
36
37public:
38  static char ID;
39
40  ProcessImplicitDefs() : MachineFunctionPass(ID) {
41    initializeProcessImplicitDefsPass(*PassRegistry::getPassRegistry());
42  }
43
44  virtual void getAnalysisUsage(AnalysisUsage &au) const;
45
46  virtual bool runOnMachineFunction(MachineFunction &fn);
47};
48} // end anonymous namespace
49
50char ProcessImplicitDefs::ID = 0;
51char &llvm::ProcessImplicitDefsID = ProcessImplicitDefs::ID;
52
53INITIALIZE_PASS_BEGIN(ProcessImplicitDefs, "processimpdefs",
54                "Process Implicit Definitions", false, false)
55INITIALIZE_PASS_END(ProcessImplicitDefs, "processimpdefs",
56                "Process Implicit Definitions", false, false)
57
58void ProcessImplicitDefs::getAnalysisUsage(AnalysisUsage &AU) const {
59  AU.setPreservesCFG();
60  AU.addPreserved<AliasAnalysis>();
61  MachineFunctionPass::getAnalysisUsage(AU);
62}
63
64bool ProcessImplicitDefs::canTurnIntoImplicitDef(MachineInstr *MI) {
65  if (!MI->isCopyLike() &&
66      !MI->isInsertSubreg() &&
67      !MI->isRegSequence() &&
68      !MI->isPHI())
69    return false;
70  for (MIOperands MO(MI); MO.isValid(); ++MO)
71    if (MO->isReg() && MO->isUse() && MO->readsReg())
72      return false;
73  return true;
74}
75
76void ProcessImplicitDefs::processImplicitDef(MachineInstr *MI) {
77  DEBUG(dbgs() << "Processing " << *MI);
78  unsigned Reg = MI->getOperand(0).getReg();
79
80  if (TargetRegisterInfo::isVirtualRegister(Reg)) {
81    // For virtual registers, mark all uses as <undef>, and convert users to
82    // implicit-def when possible.
83    for (MachineRegisterInfo::use_nodbg_iterator UI =
84         MRI->use_nodbg_begin(Reg),
85         UE = MRI->use_nodbg_end(); UI != UE; ++UI) {
86      MachineOperand &MO = UI.getOperand();
87      MO.setIsUndef();
88      MachineInstr *UserMI = MO.getParent();
89      if (!canTurnIntoImplicitDef(UserMI))
90        continue;
91      DEBUG(dbgs() << "Converting to IMPLICIT_DEF: " << *UserMI);
92      UserMI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
93      WorkList.insert(UserMI);
94    }
95    MI->eraseFromParent();
96    return;
97  }
98
99  // This is a physreg implicit-def.
100  // Look for the first instruction to use or define an alias.
101  MachineBasicBlock::instr_iterator UserMI = MI;
102  MachineBasicBlock::instr_iterator UserE = MI->getParent()->instr_end();
103  bool Found = false;
104  for (++UserMI; UserMI != UserE; ++UserMI) {
105    for (MIOperands MO(UserMI); MO.isValid(); ++MO) {
106      if (!MO->isReg())
107        continue;
108      unsigned UserReg = MO->getReg();
109      if (!TargetRegisterInfo::isPhysicalRegister(UserReg) ||
110          !TRI->regsOverlap(Reg, UserReg))
111        continue;
112      // UserMI uses or redefines Reg. Set <undef> flags on all uses.
113      Found = true;
114      if (MO->isUse())
115        MO->setIsUndef();
116    }
117    if (Found)
118      break;
119  }
120
121  // If we found the using MI, we can erase the IMPLICIT_DEF.
122  if (Found) {
123    DEBUG(dbgs() << "Physreg user: " << *UserMI);
124    MI->eraseFromParent();
125    return;
126  }
127
128  // Using instr wasn't found, it could be in another block.
129  // Leave the physreg IMPLICIT_DEF, but trim any extra operands.
130  for (unsigned i = MI->getNumOperands() - 1; i; --i)
131    MI->RemoveOperand(i);
132  DEBUG(dbgs() << "Keeping physreg: " << *MI);
133}
134
135/// processImplicitDefs - Process IMPLICIT_DEF instructions and turn them into
136/// <undef> operands.
137bool ProcessImplicitDefs::runOnMachineFunction(MachineFunction &MF) {
138
139  DEBUG(dbgs() << "********** PROCESS IMPLICIT DEFS **********\n"
140               << "********** Function: " << MF.getName() << '\n');
141
142  bool Changed = false;
143
144  TII = MF.getTarget().getInstrInfo();
145  TRI = MF.getTarget().getRegisterInfo();
146  MRI = &MF.getRegInfo();
147  assert(MRI->isSSA() && "ProcessImplicitDefs only works on SSA form.");
148  assert(WorkList.empty() && "Inconsistent worklist state");
149
150  for (MachineFunction::iterator MFI = MF.begin(), MFE = MF.end();
151       MFI != MFE; ++MFI) {
152    // Scan the basic block for implicit defs.
153    for (MachineBasicBlock::instr_iterator MBBI = MFI->instr_begin(),
154         MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI)
155      if (MBBI->isImplicitDef())
156        WorkList.insert(MBBI);
157
158    if (WorkList.empty())
159      continue;
160
161    DEBUG(dbgs() << "BB#" << MFI->getNumber() << " has " << WorkList.size()
162                 << " implicit defs.\n");
163    Changed = true;
164
165    // Drain the WorkList to recursively process any new implicit defs.
166    do processImplicitDef(WorkList.pop_back_val());
167    while (!WorkList.empty());
168  }
169  return Changed;
170}
171