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/CodeGen/MachineLateInstrsCleanup.h"
17#include "llvm/ADT/BitVector.h"
18#include "llvm/ADT/PostOrderIterator.h"
19#include "llvm/ADT/Statistic.h"
20#include "llvm/CodeGen/MachineBasicBlock.h"
21#include "llvm/CodeGen/MachineFunction.h"
22#include "llvm/CodeGen/MachineFunctionPass.h"
23#include "llvm/CodeGen/MachineInstr.h"
24#include "llvm/CodeGen/MachineOperand.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 {
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 typedef SmallDenseMap<Register, TinyPtrVector<MachineInstr *>> Reg2MIVecMap;
52 std::vector<Reg2MIMap> RegDefs;
53 std::vector<Reg2MIVecMap> 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 BitVector &VisitedPreds, MachineInstr *ToRemoveMI);
62
63public:
64 bool run(MachineFunction &MF);
65};
66
67class MachineLateInstrsCleanupLegacy : public MachineFunctionPass {
68public:
69 static char ID; // Pass identification, replacement for typeid
70
71 MachineLateInstrsCleanupLegacy() : MachineFunctionPass(ID) {
72 initializeMachineLateInstrsCleanupLegacyPass(
73 *PassRegistry::getPassRegistry());
74 }
75
76 void getAnalysisUsage(AnalysisUsage &AU) const override {
77 AU.setPreservesCFG();
78 MachineFunctionPass::getAnalysisUsage(AU);
79 }
80
81 bool runOnMachineFunction(MachineFunction &MF) override;
82
83 MachineFunctionProperties getRequiredProperties() const override {
84 return MachineFunctionProperties().setNoVRegs();
85 }
86};
87
88} // end anonymous namespace
89
90char MachineLateInstrsCleanupLegacy::ID = 0;
91
92char &llvm::MachineLateInstrsCleanupID = MachineLateInstrsCleanupLegacy::ID;
93
94INITIALIZE_PASS(MachineLateInstrsCleanupLegacy, DEBUG_TYPE,
95 "Machine Late Instructions Cleanup Pass", false, false)
96
97bool MachineLateInstrsCleanupLegacy::runOnMachineFunction(MachineFunction &MF) {
98 if (skipFunction(F: MF.getFunction()))
99 return false;
100
101 return MachineLateInstrsCleanup().run(MF);
102}
103
104PreservedAnalyses
105MachineLateInstrsCleanupPass::run(MachineFunction &MF,
106 MachineFunctionAnalysisManager &MFAM) {
107 MFPropsModifier _(*this, MF);
108 if (!MachineLateInstrsCleanup().run(MF))
109 return PreservedAnalyses::all();
110 auto PA = getMachineFunctionPassPreservedAnalyses();
111 PA.preserveSet<CFGAnalyses>();
112 return PA;
113}
114
115bool MachineLateInstrsCleanup::run(MachineFunction &MF) {
116 TRI = MF.getSubtarget().getRegisterInfo();
117 TII = MF.getSubtarget().getInstrInfo();
118
119 RegDefs.clear();
120 RegDefs.resize(new_size: MF.getNumBlockIDs());
121 RegKills.clear();
122 RegKills.resize(new_size: MF.getNumBlockIDs());
123
124 // Visit all MBBs in an order that maximises the reuse from predecessors.
125 bool Changed = false;
126 ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
127 for (MachineBasicBlock *MBB : RPOT)
128 Changed |= processBlock(MBB);
129
130 return Changed;
131}
132
133// Clear any preceding kill flag on Reg after removing a redundant
134// definition.
135void MachineLateInstrsCleanup::clearKillsForDef(Register Reg,
136 MachineBasicBlock *MBB,
137 BitVector &VisitedPreds,
138 MachineInstr *ToRemoveMI) {
139 VisitedPreds.set(MBB->getNumber());
140
141 // Clear kill flag(s) in MBB, that have been seen after the preceding
142 // definition. If Reg or one of its subregs was killed, it would actually
143 // be ok to stop after removing that (and any other) kill-flag, but it
144 // doesn't seem noticeably faster while it would be a bit more complicated.
145 Reg2MIVecMap &MBBKills = RegKills[MBB->getNumber()];
146 if (auto Kills = MBBKills.find(Val: Reg); Kills != MBBKills.end())
147 for (auto *KillMI : Kills->second)
148 KillMI->clearRegisterKills(Reg, RegInfo: TRI);
149
150 // Definition in current MBB: done.
151 Reg2MIMap &MBBDefs = RegDefs[MBB->getNumber()];
152 MachineInstr *DefMI = MBBDefs[Reg];
153 assert(DefMI->isIdenticalTo(*ToRemoveMI) && "Previous def not identical?");
154 if (DefMI->getParent() == MBB)
155 return;
156
157 // If an earlier def is not in MBB, continue in predecessors.
158 if (!MBB->isLiveIn(Reg))
159 MBB->addLiveIn(PhysReg: Reg);
160 assert(!MBB->pred_empty() && "Predecessor def not found!");
161 for (MachineBasicBlock *Pred : MBB->predecessors())
162 if (!VisitedPreds.test(Idx: Pred->getNumber()))
163 clearKillsForDef(Reg, MBB: Pred, VisitedPreds, ToRemoveMI);
164}
165
166void MachineLateInstrsCleanup::removeRedundantDef(MachineInstr *MI) {
167 Register Reg = MI->getOperand(i: 0).getReg();
168 BitVector VisitedPreds(MI->getMF()->getNumBlockIDs());
169 clearKillsForDef(Reg, MBB: MI->getParent(), VisitedPreds, ToRemoveMI: MI);
170 MI->eraseFromParent();
171 ++NumRemoved;
172}
173
174// Return true if MI is a potential candidate for reuse/removal and if so
175// also the register it defines in DefedReg. A candidate is a simple
176// instruction that does not touch memory, has only one register definition
177// and the only reg it may use is FrameReg. Typically this is an immediate
178// load or a load-address instruction.
179static bool isCandidate(const MachineInstr *MI, Register &DefedReg,
180 Register FrameReg) {
181 DefedReg = MCRegister::NoRegister;
182 bool SawStore = true;
183 if (!MI->isSafeToMove(SawStore) || MI->isImplicitDef() || MI->isInlineAsm())
184 return false;
185 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
186 const MachineOperand &MO = MI->getOperand(i);
187 if (MO.isReg()) {
188 if (MO.isDef()) {
189 if (i == 0 && !MO.isImplicit() && !MO.isDead())
190 DefedReg = MO.getReg();
191 else
192 return false;
193 } else if (MO.getReg() && MO.getReg() != FrameReg)
194 return false;
195 } else if (!(MO.isImm() || MO.isCImm() || MO.isFPImm() || MO.isCPI() ||
196 MO.isGlobal() || MO.isSymbol()))
197 return false;
198 }
199 return DefedReg.isValid();
200}
201
202bool MachineLateInstrsCleanup::processBlock(MachineBasicBlock *MBB) {
203 bool Changed = false;
204 Reg2MIMap &MBBDefs = RegDefs[MBB->getNumber()];
205 Reg2MIVecMap &MBBKills = RegKills[MBB->getNumber()];
206
207 // Find reusable definitions in the predecessor(s).
208 if (!MBB->pred_empty() && !MBB->isEHPad() &&
209 !MBB->isInlineAsmBrIndirectTarget()) {
210 MachineBasicBlock *FirstPred = *MBB->pred_begin();
211 for (auto [Reg, DefMI] : RegDefs[FirstPred->getNumber()])
212 if (llvm::all_of(
213 Range: drop_begin(RangeOrContainer: MBB->predecessors()),
214 P: [&, &Reg = Reg, &DefMI = DefMI](const MachineBasicBlock *Pred) {
215 return RegDefs[Pred->getNumber()].hasIdentical(Reg, ArgMI: DefMI);
216 })) {
217 MBBDefs[Reg] = DefMI;
218 LLVM_DEBUG(dbgs() << "Reusable instruction from pred(s): in "
219 << printMBBReference(*MBB) << ": " << *DefMI);
220 }
221 }
222
223 // Process MBB.
224 MachineFunction *MF = MBB->getParent();
225 const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
226 Register FrameReg = TRI->getFrameRegister(MF: *MF);
227 for (MachineInstr &MI : llvm::make_early_inc_range(Range&: *MBB)) {
228 // If FrameReg is modified, no previous load-address instructions (using
229 // it) are valid.
230 if (MI.modifiesRegister(Reg: FrameReg, TRI)) {
231 MBBDefs.clear();
232 MBBKills.clear();
233 continue;
234 }
235
236 Register DefedReg;
237 bool IsCandidate = isCandidate(MI: &MI, DefedReg, FrameReg);
238
239 // Check for an earlier identical and reusable instruction.
240 if (IsCandidate && MBBDefs.hasIdentical(Reg: DefedReg, ArgMI: &MI)) {
241 LLVM_DEBUG(dbgs() << "Removing redundant instruction in "
242 << printMBBReference(*MBB) << ": " << MI);
243 removeRedundantDef(MI: &MI);
244 Changed = true;
245 continue;
246 }
247
248 // Clear any entries in map that MI clobbers.
249 for (auto DefI : llvm::make_early_inc_range(Range&: MBBDefs)) {
250 Register Reg = DefI.first;
251 if (MI.modifiesRegister(Reg, TRI)) {
252 MBBDefs.erase(Val: Reg);
253 MBBKills.erase(Val: Reg);
254 } else if (MI.findRegisterUseOperandIdx(Reg, TRI, isKill: true /*isKill*/) != -1)
255 // Keep track of all instructions that fully or partially kills Reg.
256 MBBKills[Reg].push_back(NewVal: &MI);
257 }
258
259 // Record this MI for potential later reuse.
260 if (IsCandidate) {
261 LLVM_DEBUG(dbgs() << "Found interesting instruction in "
262 << printMBBReference(*MBB) << ": " << MI);
263 MBBDefs[DefedReg] = &MI;
264 assert(!MBBKills.count(DefedReg) && "Should already have been removed.");
265 }
266 }
267
268 return Changed;
269}
270