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
32 using namespace llvm;
33
34 #define DEBUG_TYPE "machine-latecleanup"
35
36 STATISTIC(NumRemoved, "Number of redundant instructions removed.");
37
38 namespace {
39
40 class 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 *> {
hasIdentical__anon95a8ee9a0111::MachineLateInstrsCleanup::Reg2MIMap46 bool hasIdentical(Register Reg, MachineInstr *ArgMI) {
47 MachineInstr *MI = lookup(Reg);
48 return MI && MI->isIdenticalTo(*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
64 public:
65 static char ID; // Pass identification, replacement for typeid
66
MachineLateInstrsCleanup()67 MachineLateInstrsCleanup() : MachineFunctionPass(ID) {
68 initializeMachineLateInstrsCleanupPass(*PassRegistry::getPassRegistry());
69 }
70
getAnalysisUsage(AnalysisUsage & AU) const71 void getAnalysisUsage(AnalysisUsage &AU) const override {
72 AU.setPreservesCFG();
73 MachineFunctionPass::getAnalysisUsage(AU);
74 }
75
76 bool runOnMachineFunction(MachineFunction &MF) override;
77
getRequiredProperties() const78 MachineFunctionProperties getRequiredProperties() const override {
79 return MachineFunctionProperties().set(
80 MachineFunctionProperties::Property::NoVRegs);
81 }
82 };
83
84 } // end anonymous namespace
85
86 char MachineLateInstrsCleanup::ID = 0;
87
88 char &llvm::MachineLateInstrsCleanupID = MachineLateInstrsCleanup::ID;
89
90 INITIALIZE_PASS(MachineLateInstrsCleanup, DEBUG_TYPE,
91 "Machine Late Instructions Cleanup Pass", false, false)
92
runOnMachineFunction(MachineFunction & MF)93 bool MachineLateInstrsCleanup::runOnMachineFunction(MachineFunction &MF) {
94 if (skipFunction(MF.getFunction()))
95 return false;
96
97 TRI = MF.getSubtarget().getRegisterInfo();
98 TII = MF.getSubtarget().getInstrInfo();
99
100 RegDefs.clear();
101 RegDefs.resize(MF.getNumBlockIDs());
102 RegKills.clear();
103 RegKills.resize(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.
118 void MachineLateInstrsCleanup::
clearKillsForDef(Register Reg,MachineBasicBlock * MBB,MachineBasicBlock::iterator I,BitVector & VisitedPreds)119 clearKillsForDef(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(Reg)) {
126 KillMI->clearRegisterKills(Reg, TRI);
127 return;
128 }
129
130 // Def in MBB (missing kill flag)
131 if (MachineInstr *DefMI = RegDefs[MBB->getNumber()].lookup(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(Reg);
138 assert(!MBB->pred_empty() && "Predecessor def not found!");
139 for (MachineBasicBlock *Pred : MBB->predecessors())
140 if (!VisitedPreds.test(Pred->getNumber()))
141 clearKillsForDef(Reg, Pred, Pred->end(), VisitedPreds);
142 }
143
removeRedundantDef(MachineInstr * MI)144 void MachineLateInstrsCleanup::removeRedundantDef(MachineInstr *MI) {
145 Register Reg = MI->getOperand(0).getReg();
146 BitVector VisitedPreds(MI->getMF()->getNumBlockIDs());
147 clearKillsForDef(Reg, MI->getParent(), 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.
isCandidate(const MachineInstr * MI,Register & DefedReg,Register FrameReg)157 static bool isCandidate(const MachineInstr *MI, Register &DefedReg,
158 Register FrameReg) {
159 DefedReg = MCRegister::NoRegister;
160 bool SawStore = true;
161 if (!MI->isSafeToMove(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
processBlock(MachineBasicBlock * MBB)181 bool 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 drop_begin(MBB->predecessors()),
193 [&, &Reg = Reg, &DefMI = DefMI](const MachineBasicBlock *Pred) {
194 return RegDefs[Pred->getNumber()].hasIdentical(Reg, 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);
206 for (MachineInstr &MI : llvm::make_early_inc_range(*MBB)) {
207 // If FrameReg is modified, no previous load-address instructions (using
208 // it) are valid.
209 if (MI.modifiesRegister(FrameReg, TRI)) {
210 MBBDefs.clear();
211 MBBKills.clear();
212 continue;
213 }
214
215 Register DefedReg;
216 bool IsCandidate = isCandidate(&MI, DefedReg, FrameReg);
217
218 // Check for an earlier identical and reusable instruction.
219 if (IsCandidate && MBBDefs.hasIdentical(DefedReg, &MI)) {
220 LLVM_DEBUG(dbgs() << "Removing redundant instruction in "
221 << printMBBReference(*MBB) << ": " << MI;);
222 removeRedundantDef(&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(MBBDefs)) {
229 Register Reg = DefI.first;
230 if (MI.modifiesRegister(Reg, TRI)) {
231 MBBDefs.erase(Reg);
232 MBBKills.erase(Reg);
233 } else if (MI.findRegisterUseOperandIdx(Reg, TRI, 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