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/TargetInstrInfo.h"
15#include "llvm/CodeGen/TargetSubtargetInfo.h"
16#include "llvm/InitializePasses.h"
17#include "llvm/Pass.h"
18#include "llvm/PassRegistry.h"
19#include "llvm/Support/Debug.h"
20#include "llvm/Support/raw_ostream.h"
21
22using namespace llvm;
23
24#define DEBUG_TYPE "processimpdefs"
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 ProcessImplicitDefs : public MachineFunctionPass {
30 const TargetInstrInfo *TII = nullptr;
31 const TargetRegisterInfo *TRI = nullptr;
32 MachineRegisterInfo *MRI = nullptr;
33
34 SmallSetVector<MachineInstr*, 16> WorkList;
35
36 void processImplicitDef(MachineInstr *MI);
37 bool canTurnIntoImplicitDef(MachineInstr *MI);
38
39public:
40 static char ID;
41
42 ProcessImplicitDefs() : MachineFunctionPass(ID) {
43 initializeProcessImplicitDefsPass(*PassRegistry::getPassRegistry());
44 }
45
46 void getAnalysisUsage(AnalysisUsage &au) const override;
47
48 bool runOnMachineFunction(MachineFunction &MF) override;
49
50 MachineFunctionProperties getRequiredProperties() const override {
51 return MachineFunctionProperties().set(
52 MachineFunctionProperties::Property::IsSSA);
53 }
54};
55} // end anonymous namespace
56
57char ProcessImplicitDefs::ID = 0;
58char &llvm::ProcessImplicitDefsID = ProcessImplicitDefs::ID;
59
60INITIALIZE_PASS(ProcessImplicitDefs, DEBUG_TYPE,
61 "Process Implicit Definitions", false, false)
62
63void ProcessImplicitDefs::getAnalysisUsage(AnalysisUsage &AU) const {
64 AU.setPreservesCFG();
65 AU.addPreserved<AAResultsWrapperPass>();
66 MachineFunctionPass::getAnalysisUsage(AU);
67}
68
69bool ProcessImplicitDefs::canTurnIntoImplicitDef(MachineInstr *MI) {
70 if (!MI->isCopyLike() &&
71 !MI->isInsertSubreg() &&
72 !MI->isRegSequence() &&
73 !MI->isPHI())
74 return false;
75 for (const MachineOperand &MO : MI->all_uses())
76 if (MO.readsReg())
77 return false;
78 return true;
79}
80
81void ProcessImplicitDefs::processImplicitDef(MachineInstr *MI) {
82 LLVM_DEBUG(dbgs() << "Processing " << *MI);
83 Register Reg = MI->getOperand(i: 0).getReg();
84
85 if (Reg.isVirtual()) {
86 // For virtual registers, mark all uses as <undef>, and convert users to
87 // implicit-def when possible.
88 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
89 MO.setIsUndef();
90 MachineInstr *UserMI = MO.getParent();
91 if (!canTurnIntoImplicitDef(MI: UserMI))
92 continue;
93 LLVM_DEBUG(dbgs() << "Converting to IMPLICIT_DEF: " << *UserMI);
94 UserMI->setDesc(TII->get(Opcode: TargetOpcode::IMPLICIT_DEF));
95 WorkList.insert(X: UserMI);
96 }
97 MI->eraseFromParent();
98 return;
99 }
100
101 // This is a physreg implicit-def.
102 // Look for the first instruction to use or define an alias.
103 MachineBasicBlock::instr_iterator UserMI = MI->getIterator();
104 MachineBasicBlock::instr_iterator UserE = MI->getParent()->instr_end();
105 bool Found = false;
106 for (++UserMI; UserMI != UserE; ++UserMI) {
107 for (MachineOperand &MO : UserMI->operands()) {
108 if (!MO.isReg())
109 continue;
110 Register UserReg = MO.getReg();
111 if (!UserReg.isPhysical() || !TRI->regsOverlap(RegA: Reg, RegB: UserReg))
112 continue;
113 // UserMI uses or redefines Reg. Set <undef> flags on all uses.
114 Found = true;
115 if (MO.isUse())
116 MO.setIsUndef();
117 }
118 if (Found)
119 break;
120 }
121
122 // If we found the using MI, we can erase the IMPLICIT_DEF.
123 if (Found) {
124 LLVM_DEBUG(dbgs() << "Physreg user: " << *UserMI);
125 MI->eraseFromParent();
126 return;
127 }
128
129 // Using instr wasn't found, it could be in another block.
130 // Leave the physreg IMPLICIT_DEF, but trim any extra operands.
131 for (unsigned i = MI->getNumOperands() - 1; i; --i)
132 MI->removeOperand(OpNo: i);
133 LLVM_DEBUG(dbgs() << "Keeping physreg: " << *MI);
134}
135
136/// processImplicitDefs - Process IMPLICIT_DEF instructions and turn them into
137/// <undef> operands.
138bool ProcessImplicitDefs::runOnMachineFunction(MachineFunction &MF) {
139
140 LLVM_DEBUG(dbgs() << "********** PROCESS IMPLICIT DEFS **********\n"
141 << "********** Function: " << MF.getName() << '\n');
142
143 bool Changed = false;
144
145 TII = MF.getSubtarget().getInstrInfo();
146 TRI = MF.getSubtarget().getRegisterInfo();
147 MRI = &MF.getRegInfo();
148 assert(WorkList.empty() && "Inconsistent worklist state");
149
150 for (MachineBasicBlock &MBB : MF) {
151 // Scan the basic block for implicit defs.
152 for (MachineInstr &MI : MBB)
153 if (MI.isImplicitDef())
154 WorkList.insert(X: &MI);
155
156 if (WorkList.empty())
157 continue;
158
159 LLVM_DEBUG(dbgs() << printMBBReference(MBB) << " 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(MI: WorkList.pop_back_val());
165 while (!WorkList.empty());
166 }
167 return Changed;
168}
169