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