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