1//==--- MachineLateInstrsCleanup.cpp - Late Instructions Cleanup Pass -----===//
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// This simple pass removes any identical and redundant immediate or address
10// loads to the same register. The immediate loads removed can originally be
11// the result of rematerialization, while the addresses are redundant frame
12// addressing anchor points created during Frame Indices elimination.
13//
14//===----------------------------------------------------------------------===//
15
16#include "llvm/ADT/BitVector.h"
17#include "llvm/ADT/PostOrderIterator.h"
18#include "llvm/ADT/Statistic.h"
19#include "llvm/CodeGen/MachineBasicBlock.h"
20#include "llvm/CodeGen/MachineFunction.h"
21#include "llvm/CodeGen/MachineFunctionPass.h"
22#include "llvm/CodeGen/MachineInstr.h"
23#include "llvm/CodeGen/MachineOperand.h"
24#include "llvm/CodeGen/MachineRegisterInfo.h"
25#include "llvm/CodeGen/TargetInstrInfo.h"
26#include "llvm/CodeGen/TargetRegisterInfo.h"
27#include "llvm/CodeGen/TargetSubtargetInfo.h"
28#include "llvm/InitializePasses.h"
29#include "llvm/Pass.h"
30#include "llvm/Support/Debug.h"
31
32using namespace llvm;
33
34#define DEBUG_TYPE "machine-latecleanup"
35
36STATISTIC(NumRemoved, "Number of redundant instructions removed.");
37
38namespace {
39
40class MachineLateInstrsCleanup : public MachineFunctionPass {
41 const TargetRegisterInfo *TRI = nullptr;
42 const TargetInstrInfo *TII = nullptr;
43
44 // Data structures to map regs to their definitions and kills per MBB.
45 struct Reg2MIMap : public SmallDenseMap<Register, MachineInstr *> {
46 bool hasIdentical(Register Reg, MachineInstr *ArgMI) {
47 MachineInstr *MI = lookup(Val: Reg);
48 return MI && MI->isIdenticalTo(Other: *ArgMI);
49 }
50 };
51
52 std::vector<Reg2MIMap> RegDefs;
53 std::vector<Reg2MIMap> RegKills;
54
55 // Walk through the instructions in MBB and remove any redundant
56 // instructions.
57 bool processBlock(MachineBasicBlock *MBB);
58
59 void removeRedundantDef(MachineInstr *MI);
60 void clearKillsForDef(Register Reg, MachineBasicBlock *MBB,
61 MachineBasicBlock::iterator I,
62 BitVector &VisitedPreds);
63
64public:
65 static char ID; // Pass identification, replacement for typeid
66
67 MachineLateInstrsCleanup() : MachineFunctionPass(ID) {
68 initializeMachineLateInstrsCleanupPass(*PassRegistry::getPassRegistry());
69 }
70
71 void getAnalysisUsage(AnalysisUsage &AU) const override {
72 AU.setPreservesCFG();
73 MachineFunctionPass::getAnalysisUsage(AU);
74 }
75
76 bool runOnMachineFunction(MachineFunction &MF) override;
77
78 MachineFunctionProperties getRequiredProperties() const override {
79 return MachineFunctionProperties().set(
80 MachineFunctionProperties::Property::NoVRegs);
81 }
82};
83
84} // end anonymous namespace
85
86char MachineLateInstrsCleanup::ID = 0;
87
88char &llvm::MachineLateInstrsCleanupID = MachineLateInstrsCleanup::ID;
89
90INITIALIZE_PASS(MachineLateInstrsCleanup, DEBUG_TYPE,
91 "Machine Late Instructions Cleanup Pass", false, false)
92
93bool MachineLateInstrsCleanup::runOnMachineFunction(MachineFunction &MF) {
94 if (skipFunction(F: MF.getFunction()))
95 return false;
96
97 TRI = MF.getSubtarget().getRegisterInfo();
98 TII = MF.getSubtarget().getInstrInfo();
99
100 RegDefs.clear();
101 RegDefs.resize(new_size: MF.getNumBlockIDs());
102 RegKills.clear();
103 RegKills.resize(new_size: MF.getNumBlockIDs());
104
105 // Visit all MBBs in an order that maximises the reuse from predecessors.
106 bool Changed = false;
107 ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
108 for (MachineBasicBlock *MBB : RPOT)
109 Changed |= processBlock(MBB);
110
111 return Changed;
112}
113
114// Clear any previous kill flag on Reg found before I in MBB. Walk backwards
115// in MBB and if needed continue in predecessors until a use/def of Reg is
116// encountered. This seems to be faster in practice than tracking kill flags
117// in a map.
118void MachineLateInstrsCleanup::
119clearKillsForDef(Register Reg, MachineBasicBlock *MBB,
120 MachineBasicBlock::iterator I,
121 BitVector &VisitedPreds) {
122 VisitedPreds.set(MBB->getNumber());
123
124 // Kill flag in MBB
125 if (MachineInstr *KillMI = RegKills[MBB->getNumber()].lookup(Val: Reg)) {
126 KillMI->clearRegisterKills(Reg, RegInfo: TRI);
127 return;
128 }
129
130 // Def in MBB (missing kill flag)
131 if (MachineInstr *DefMI = RegDefs[MBB->getNumber()].lookup(Val: Reg))
132 if (DefMI->getParent() == MBB)
133 return;
134
135 // If an earlier def is not in MBB, continue in predecessors.
136 if (!MBB->isLiveIn(Reg))
137 MBB->addLiveIn(PhysReg: Reg);
138 assert(!MBB->pred_empty() && "Predecessor def not found!");
139 for (MachineBasicBlock *Pred : MBB->predecessors())
140 if (!VisitedPreds.test(Idx: Pred->getNumber()))
141 clearKillsForDef(Reg, MBB: Pred, I: Pred->end(), VisitedPreds);
142}
143
144void MachineLateInstrsCleanup::removeRedundantDef(MachineInstr *MI) {
145 Register Reg = MI->getOperand(i: 0).getReg();
146 BitVector VisitedPreds(MI->getMF()->getNumBlockIDs());
147 clearKillsForDef(Reg, MBB: MI->getParent(), I: MI->getIterator(), VisitedPreds);
148 MI->eraseFromParent();
149 ++NumRemoved;
150}
151
152// Return true if MI is a potential candidate for reuse/removal and if so
153// also the register it defines in DefedReg. A candidate is a simple
154// instruction that does not touch memory, has only one register definition
155// and the only reg it may use is FrameReg. Typically this is an immediate
156// load or a load-address instruction.
157static bool isCandidate(const MachineInstr *MI, Register &DefedReg,
158 Register FrameReg) {
159 DefedReg = MCRegister::NoRegister;
160 bool SawStore = true;
161 if (!MI->isSafeToMove(AA: nullptr, SawStore) || MI->isImplicitDef() ||
162 MI->isInlineAsm())
163 return false;
164 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
165 const MachineOperand &MO = MI->getOperand(i);
166 if (MO.isReg()) {
167 if (MO.isDef()) {
168 if (i == 0 && !MO.isImplicit() && !MO.isDead())
169 DefedReg = MO.getReg();
170 else
171 return false;
172 } else if (MO.getReg() && MO.getReg() != FrameReg)
173 return false;
174 } else if (!(MO.isImm() || MO.isCImm() || MO.isFPImm() || MO.isCPI() ||
175 MO.isGlobal() || MO.isSymbol()))
176 return false;
177 }
178 return DefedReg.isValid();
179}
180
181bool MachineLateInstrsCleanup::processBlock(MachineBasicBlock *MBB) {
182 bool Changed = false;
183 Reg2MIMap &MBBDefs = RegDefs[MBB->getNumber()];
184 Reg2MIMap &MBBKills = RegKills[MBB->getNumber()];
185
186 // Find reusable definitions in the predecessor(s).
187 if (!MBB->pred_empty() && !MBB->isEHPad() &&
188 !MBB->isInlineAsmBrIndirectTarget()) {
189 MachineBasicBlock *FirstPred = *MBB->pred_begin();
190 for (auto [Reg, DefMI] : RegDefs[FirstPred->getNumber()])
191 if (llvm::all_of(
192 Range: drop_begin(RangeOrContainer: MBB->predecessors()),
193 P: [&, &Reg = Reg, &DefMI = DefMI](const MachineBasicBlock *Pred) {
194 return RegDefs[Pred->getNumber()].hasIdentical(Reg, ArgMI: DefMI);
195 })) {
196 MBBDefs[Reg] = DefMI;
197 LLVM_DEBUG(dbgs() << "Reusable instruction from pred(s): in "
198 << printMBBReference(*MBB) << ": " << *DefMI;);
199 }
200 }
201
202 // Process MBB.
203 MachineFunction *MF = MBB->getParent();
204 const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
205 Register FrameReg = TRI->getFrameRegister(MF: *MF);
206 for (MachineInstr &MI : llvm::make_early_inc_range(Range&: *MBB)) {
207 // If FrameReg is modified, no previous load-address instructions (using
208 // it) are valid.
209 if (MI.modifiesRegister(Reg: FrameReg, TRI)) {
210 MBBDefs.clear();
211 MBBKills.clear();
212 continue;
213 }
214
215 Register DefedReg;
216 bool IsCandidate = isCandidate(MI: &MI, DefedReg, FrameReg);
217
218 // Check for an earlier identical and reusable instruction.
219 if (IsCandidate && MBBDefs.hasIdentical(Reg: DefedReg, ArgMI: &MI)) {
220 LLVM_DEBUG(dbgs() << "Removing redundant instruction in "
221 << printMBBReference(*MBB) << ": " << MI;);
222 removeRedundantDef(MI: &MI);
223 Changed = true;
224 continue;
225 }
226
227 // Clear any entries in map that MI clobbers.
228 for (auto DefI : llvm::make_early_inc_range(Range&: MBBDefs)) {
229 Register Reg = DefI.first;
230 if (MI.modifiesRegister(Reg, TRI)) {
231 MBBDefs.erase(Val: Reg);
232 MBBKills.erase(Val: Reg);
233 } else if (MI.findRegisterUseOperandIdx(Reg, TRI, isKill: true /*isKill*/) != -1)
234 // Keep track of register kills.
235 MBBKills[Reg] = &MI;
236 }
237
238 // Record this MI for potential later reuse.
239 if (IsCandidate) {
240 LLVM_DEBUG(dbgs() << "Found interesting instruction in "
241 << printMBBReference(*MBB) << ": " << MI;);
242 MBBDefs[DefedReg] = &MI;
243 assert(!MBBKills.count(DefedReg) && "Should already have been removed.");
244 }
245 }
246
247 return Changed;
248}
249