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