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/CodeGen/ProcessImplicitDefs.h"
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/TargetInstrInfo.h"
16#include "llvm/CodeGen/TargetSubtargetInfo.h"
17#include "llvm/InitializePasses.h"
18#include "llvm/Pass.h"
19#include "llvm/PassRegistry.h"
20#include "llvm/Support/Debug.h"
21#include "llvm/Support/raw_ostream.h"
22
23using namespace llvm;
24
25#define DEBUG_TYPE "processimpdefs"
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 ProcessImplicitDefsLegacy : public MachineFunctionPass {
31public:
32 static char ID;
33
34 ProcessImplicitDefsLegacy() : MachineFunctionPass(ID) {}
35
36 void getAnalysisUsage(AnalysisUsage &AU) const override;
37
38 bool runOnMachineFunction(MachineFunction &MF) override;
39
40 MachineFunctionProperties getRequiredProperties() const override {
41 return MachineFunctionProperties().setIsSSA();
42 }
43};
44
45class ProcessImplicitDefs {
46 const TargetInstrInfo *TII = nullptr;
47 const TargetRegisterInfo *TRI = nullptr;
48 MachineRegisterInfo *MRI = nullptr;
49
50 SmallSetVector<MachineInstr *, 16> WorkList;
51
52 void processImplicitDef(MachineInstr *MI);
53 bool canTurnIntoImplicitDef(MachineInstr *MI);
54
55public:
56 bool run(MachineFunction &MF);
57};
58} // end anonymous namespace
59
60char ProcessImplicitDefsLegacy::ID = 0;
61char &llvm::ProcessImplicitDefsID = ProcessImplicitDefsLegacy::ID;
62
63INITIALIZE_PASS(ProcessImplicitDefsLegacy, DEBUG_TYPE,
64 "Process Implicit Definitions", false, false)
65
66void ProcessImplicitDefsLegacy::getAnalysisUsage(AnalysisUsage &AU) const {
67 AU.setPreservesCFG();
68 AU.addPreserved<AAResultsWrapperPass>();
69 MachineFunctionPass::getAnalysisUsage(AU);
70}
71
72bool ProcessImplicitDefs::canTurnIntoImplicitDef(MachineInstr *MI) {
73 if (!MI->isCopyLike() &&
74 !MI->isInsertSubreg() &&
75 !MI->isRegSequence() &&
76 !MI->isPHI())
77 return false;
78 for (const MachineOperand &MO : MI->all_uses())
79 if (MO.readsReg())
80 return false;
81 return true;
82}
83
84void ProcessImplicitDefs::processImplicitDef(MachineInstr *MI) {
85 LLVM_DEBUG(dbgs() << "Processing " << *MI);
86 Register Reg = MI->getOperand(i: 0).getReg();
87
88 if (Reg.isVirtual()) {
89 // For virtual registers, mark all uses as <undef>, and convert users to
90 // implicit-def when possible.
91 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
92 MO.setIsUndef();
93 MachineInstr *UserMI = MO.getParent();
94 if (!canTurnIntoImplicitDef(MI: UserMI))
95 continue;
96 LLVM_DEBUG(dbgs() << "Converting to IMPLICIT_DEF: " << *UserMI);
97 UserMI->setDesc(TII->get(Opcode: TargetOpcode::IMPLICIT_DEF));
98 WorkList.insert(X: UserMI);
99 }
100 MI->eraseFromParent();
101 return;
102 }
103
104 // This is a physreg implicit-def.
105 // Trim any extra operands.
106 for (unsigned i = MI->getNumOperands() - 1; i; --i)
107 MI->removeOperand(OpNo: i);
108
109 // Try to add undef flag to all uses. If all uses are updated remove
110 // implicit-def.
111 MachineBasicBlock::instr_iterator SearchMI = MI->getIterator();
112 MachineBasicBlock::instr_iterator SearchE = MI->getParent()->instr_end();
113 bool ImplicitDefIsDead = false;
114 bool SearchedWholeBlock = true;
115 constexpr unsigned SearchLimit = 35;
116 unsigned Count = 0;
117 for (++SearchMI; SearchMI != SearchE; ++SearchMI) {
118 if (SearchMI->isDebugInstr())
119 continue;
120 if (++Count > SearchLimit) {
121 SearchedWholeBlock = false;
122 break;
123 }
124 for (MachineOperand &MO : SearchMI->operands()) {
125 if (!MO.isReg())
126 continue;
127 Register SearchReg = MO.getReg();
128 if (!SearchReg.isPhysical() || !TRI->regsOverlap(RegA: Reg, RegB: SearchReg))
129 continue;
130 // SearchMI uses or redefines Reg. Set <undef> flags on all uses.
131 if (MO.isUse()) {
132 if (TRI->isSubRegisterEq(RegA: Reg, RegB: SearchReg)) {
133 MO.setIsUndef();
134 } else {
135 // Use is larger than Reg. It is not safe to add undef to this use.
136 return;
137 }
138 }
139 if (MO.isDef()) {
140 if (TRI->isSubRegisterEq(RegA: SearchReg, RegB: Reg)) {
141 ImplicitDefIsDead = true;
142 } else {
143 // Reg is larger than definition. It is not safe to add undef to any
144 // subsequent uses of Reg.
145 return;
146 }
147 }
148 }
149 if (ImplicitDefIsDead) {
150 LLVM_DEBUG(dbgs() << "Physreg redefine: " << *SearchMI);
151 break;
152 }
153 }
154
155 // If we have added an undef flag to all uses (i.e. we have found a redefining
156 // MI or there are no successors), we can erase the IMPLICIT_DEF.
157 if (ImplicitDefIsDead ||
158 (SearchedWholeBlock && MI->getParent()->succ_empty())) {
159 MI->eraseFromParent();
160 LLVM_DEBUG(dbgs() << "Deleting implicit-def: " << *MI);
161 }
162}
163
164bool ProcessImplicitDefsLegacy::runOnMachineFunction(MachineFunction &MF) {
165 return ProcessImplicitDefs().run(MF);
166}
167
168PreservedAnalyses
169ProcessImplicitDefsPass::run(MachineFunction &MF,
170 MachineFunctionAnalysisManager &MFAM) {
171 if (!ProcessImplicitDefs().run(MF))
172 return PreservedAnalyses::all();
173
174 return getMachineFunctionPassPreservedAnalyses()
175 .preserveSet<CFGAnalyses>()
176 .preserve<AAManager>();
177}
178
179/// processImplicitDefs - Process IMPLICIT_DEF instructions and turn them into
180/// <undef> operands.
181bool ProcessImplicitDefs::run(MachineFunction &MF) {
182
183 LLVM_DEBUG(dbgs() << "********** PROCESS IMPLICIT DEFS **********\n"
184 << "********** Function: " << MF.getName() << '\n');
185
186 bool Changed = false;
187
188 TII = MF.getSubtarget().getInstrInfo();
189 TRI = MF.getSubtarget().getRegisterInfo();
190 MRI = &MF.getRegInfo();
191 assert(WorkList.empty() && "Inconsistent worklist state");
192
193 for (MachineBasicBlock &MBB : MF) {
194 // Scan the basic block for implicit defs.
195 for (MachineInstr &MI : MBB)
196 if (MI.isImplicitDef())
197 WorkList.insert(X: &MI);
198
199 if (WorkList.empty())
200 continue;
201
202 LLVM_DEBUG(dbgs() << printMBBReference(MBB) << " has " << WorkList.size()
203 << " implicit defs.\n");
204 Changed = true;
205
206 // Drain the WorkList to recursively process any new implicit defs.
207 do processImplicitDef(MI: WorkList.pop_back_val());
208 while (!WorkList.empty());
209 }
210 return Changed;
211}
212