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