1//===-------------- MIRCanonicalizer.cpp - MIR Canonicalizer --------------===//
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// The purpose of this pass is to employ a canonical code transformation so
10// that code compiled with slightly different IR passes can be diffed more
11// effectively than otherwise. This is done by renaming vregs in a given
12// LiveRange in a canonical way. This pass also does a pseudo-scheduling to
13// move defs closer to their use inorder to reduce diffs caused by slightly
14// different schedules.
15//
16// Basic Usage:
17//
18// llc -o - -run-pass mir-canonicalizer example.mir
19//
20// Reorders instructions canonically.
21// Renames virtual register operands canonically.
22// Strips certain MIR artifacts (optionally).
23//
24//===----------------------------------------------------------------------===//
25
26#include "CodeGenOptions.h"
27#include "MIRVRegNamerUtils.h"
28#include "llvm/ADT/PostOrderIterator.h"
29#include "llvm/ADT/STLExtras.h"
30#include "llvm/CodeGen/MachineFunctionPass.h"
31#include "llvm/CodeGen/MachineRegisterInfo.h"
32#include "llvm/InitializePasses.h"
33#include "llvm/Pass.h"
34#include "llvm/Support/Debug.h"
35#include "llvm/Support/raw_ostream.h"
36
37using namespace llvm;
38
39#define DEBUG_TYPE "mir-canonicalizer"
40
41namespace {
42
43class MIRCanonicalizer : public MachineFunctionPass {
44public:
45 static char ID;
46 MIRCanonicalizer() : MachineFunctionPass(ID) {}
47
48 StringRef getPassName() const override {
49 return "Rename register operands in a canonical ordering.";
50 }
51
52 void getAnalysisUsage(AnalysisUsage &AU) const override {
53 AU.setPreservesCFG();
54 MachineFunctionPass::getAnalysisUsage(AU);
55 }
56
57 bool runOnMachineFunction(MachineFunction &MF) override;
58};
59
60} // end anonymous namespace
61
62char MIRCanonicalizer::ID;
63
64char &llvm::MIRCanonicalizerID = MIRCanonicalizer::ID;
65
66INITIALIZE_PASS_BEGIN(MIRCanonicalizer, "mir-canonicalizer",
67 "Rename Register Operands Canonically", false, false)
68
69INITIALIZE_PASS_END(MIRCanonicalizer, "mir-canonicalizer",
70 "Rename Register Operands Canonically", false, false)
71
72static std::vector<MachineBasicBlock *> GetRPOList(MachineFunction &MF) {
73 if (MF.empty())
74 return {};
75 ReversePostOrderTraversal<MachineBasicBlock *> RPOT(&*MF.begin());
76 std::vector<MachineBasicBlock *> RPOList;
77 append_range(C&: RPOList, R&: RPOT);
78
79 return RPOList;
80}
81
82static bool
83rescheduleLexographically(std::vector<MachineInstr *> instructions,
84 MachineBasicBlock *MBB,
85 std::function<MachineBasicBlock::iterator()> getPos) {
86
87 bool Changed = false;
88 using StringInstrPair = std::pair<std::string, MachineInstr *>;
89 std::vector<StringInstrPair> StringInstrMap;
90
91 for (auto *II : instructions) {
92 std::string S;
93 raw_string_ostream OS(S);
94 II->print(OS);
95
96 // Trim the assignment, or start from the beginning in the case of a store.
97 const size_t i = S.find(c: '=');
98 StringInstrMap.push_back(x: {(i == std::string::npos) ? S : S.substr(pos: i), II});
99 }
100
101 llvm::sort(C&: StringInstrMap, Comp: llvm::less_first());
102
103 for (auto &II : StringInstrMap) {
104
105 LLVM_DEBUG({
106 dbgs() << "Splicing ";
107 II.second->dump();
108 dbgs() << " right before: ";
109 getPos()->dump();
110 });
111
112 Changed = true;
113 MBB->splice(Where: getPos(), Other: MBB, From: II.second);
114 }
115
116 return Changed;
117}
118
119static bool rescheduleCanonically(unsigned &PseudoIdempotentInstCount,
120 MachineBasicBlock *MBB) {
121
122 bool Changed = false;
123
124 // Calculates the distance of MI from the beginning of its parent BB.
125 auto getInstrIdx = [](const MachineInstr &MI) {
126 unsigned i = 0;
127 for (const auto &CurMI : *MI.getParent()) {
128 if (&CurMI == &MI)
129 return i;
130 i++;
131 }
132 return ~0U;
133 };
134
135 // Pre-Populate vector of instructions to reschedule so that we don't
136 // clobber the iterator.
137 std::vector<MachineInstr *> Instructions;
138 for (auto &MI : *MBB) {
139 Instructions.push_back(x: &MI);
140 }
141
142 std::map<MachineInstr *, std::vector<MachineInstr *>> MultiUsers;
143 std::map<unsigned, MachineInstr *> MultiUserLookup;
144 unsigned UseToBringDefCloserToCount = 0;
145 std::vector<MachineInstr *> PseudoIdempotentInstructions;
146 std::vector<MCRegister> PhysRegDefs;
147 for (auto *II : Instructions) {
148 for (unsigned i = 1; i < II->getNumOperands(); i++) {
149 MachineOperand &MO = II->getOperand(i);
150 if (!MO.isReg())
151 continue;
152
153 if (MO.getReg().isVirtual())
154 continue;
155
156 if (!MO.isDef())
157 continue;
158
159 PhysRegDefs.push_back(x: MO.getReg());
160 }
161 }
162
163 for (auto *II : Instructions) {
164 if (II->getNumOperands() == 0)
165 continue;
166 if (II->mayLoadOrStore())
167 continue;
168
169 MachineOperand &MO = II->getOperand(i: 0);
170 if (!MO.isReg() || !MO.getReg().isVirtual())
171 continue;
172 if (!MO.isDef())
173 continue;
174
175 bool IsPseudoIdempotent = true;
176 for (unsigned i = 1; i < II->getNumOperands(); i++) {
177
178 if (II->getOperand(i).isImm()) {
179 continue;
180 }
181
182 if (II->getOperand(i).isReg()) {
183 if (!II->getOperand(i).getReg().isVirtual())
184 if (!llvm::is_contained(Range&: PhysRegDefs,
185 Element: II->getOperand(i).getReg().asMCReg())) {
186 continue;
187 }
188 }
189
190 IsPseudoIdempotent = false;
191 break;
192 }
193
194 if (IsPseudoIdempotent) {
195 PseudoIdempotentInstructions.push_back(x: II);
196 continue;
197 }
198
199 LLVM_DEBUG(dbgs() << "Operand " << 0 << " of "; II->dump(); MO.dump(););
200
201 MachineInstr *Def = II;
202 unsigned Distance = ~0U;
203 MachineInstr *UseToBringDefCloserTo = nullptr;
204 MachineRegisterInfo *MRI = &MBB->getParent()->getRegInfo();
205 for (auto &UO : MRI->use_nodbg_operands(Reg: MO.getReg())) {
206 MachineInstr *UseInst = UO.getParent();
207
208 const unsigned DefLoc = getInstrIdx(*Def);
209 const unsigned UseLoc = getInstrIdx(*UseInst);
210 const unsigned Delta = (UseLoc - DefLoc);
211
212 if (UseInst->getParent() != Def->getParent())
213 continue;
214 if (DefLoc >= UseLoc)
215 continue;
216
217 if (Delta < Distance) {
218 Distance = Delta;
219 UseToBringDefCloserTo = UseInst;
220 MultiUserLookup[UseToBringDefCloserToCount++] = UseToBringDefCloserTo;
221 }
222 }
223
224 const auto BBE = MBB->instr_end();
225 MachineBasicBlock::iterator DefI = BBE;
226 MachineBasicBlock::iterator UseI = BBE;
227
228 for (auto BBI = MBB->instr_begin(); BBI != BBE; ++BBI) {
229
230 if (DefI != BBE && UseI != BBE)
231 break;
232
233 if (&*BBI == Def) {
234 DefI = BBI;
235 continue;
236 }
237
238 if (&*BBI == UseToBringDefCloserTo) {
239 UseI = BBI;
240 continue;
241 }
242 }
243
244 if (DefI == BBE || UseI == BBE)
245 continue;
246
247 LLVM_DEBUG({
248 dbgs() << "Splicing ";
249 DefI->dump();
250 dbgs() << " right before: ";
251 UseI->dump();
252 });
253
254 MultiUsers[UseToBringDefCloserTo].push_back(x: Def);
255 Changed = true;
256 MBB->splice(Where: UseI, Other: MBB, From: DefI);
257 }
258
259 // Sort the defs for users of multiple defs lexographically.
260 for (const auto &E : MultiUserLookup) {
261
262 auto UseI = llvm::find_if(Range: MBB->instrs(), P: [&](MachineInstr &MI) -> bool {
263 return &MI == E.second;
264 });
265
266 if (UseI == MBB->instr_end())
267 continue;
268
269 LLVM_DEBUG(
270 dbgs() << "Rescheduling Multi-Use Instructions Lexographically.");
271 Changed |= rescheduleLexographically(
272 instructions: MultiUsers[E.second], MBB,
273 getPos: [&]() -> MachineBasicBlock::iterator { return UseI; });
274 }
275
276 PseudoIdempotentInstCount = PseudoIdempotentInstructions.size();
277 LLVM_DEBUG(dbgs() << "Rescheduling Idempotent Instructions Lexographically.");
278 Changed |= rescheduleLexographically(
279 instructions: PseudoIdempotentInstructions, MBB,
280 getPos: [&]() -> MachineBasicBlock::iterator { return MBB->begin(); });
281
282 return Changed;
283}
284
285static bool propagateLocalCopies(MachineBasicBlock *MBB) {
286 bool Changed = false;
287 MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo();
288
289 std::vector<MachineInstr *> Copies;
290 for (MachineInstr &MI : MBB->instrs()) {
291 if (MI.isCopy())
292 Copies.push_back(x: &MI);
293 }
294
295 for (MachineInstr *MI : Copies) {
296
297 if (!MI->getOperand(i: 0).isReg())
298 continue;
299 if (!MI->getOperand(i: 1).isReg())
300 continue;
301
302 const Register Dst = MI->getOperand(i: 0).getReg();
303 const Register Src = MI->getOperand(i: 1).getReg();
304
305 if (!Dst.isVirtual())
306 continue;
307 if (!Src.isVirtual())
308 continue;
309 // Not folding COPY instructions if regbankselect has not set the RCs.
310 // Why are we only considering Register Classes? Because the verifier
311 // sometimes gets upset if the register classes don't match even if the
312 // types do. A future patch might add COPY folding for matching types in
313 // pre-registerbankselect code.
314 if (!MRI.getRegClassOrNull(Reg: Dst))
315 continue;
316 if (MRI.getRegClass(Reg: Dst) != MRI.getRegClass(Reg: Src))
317 continue;
318
319 std::vector<MachineOperand *> Uses;
320 for (MachineOperand &MO : MRI.use_operands(Reg: Dst))
321 Uses.push_back(x: &MO);
322 for (auto *MO : Uses)
323 MO->setReg(Src);
324
325 Changed = true;
326 MI->eraseFromParent();
327 }
328
329 return Changed;
330}
331
332static bool doDefKillClear(MachineBasicBlock *MBB) {
333 bool Changed = false;
334
335 for (auto &MI : *MBB) {
336 for (auto &MO : MI.operands()) {
337 if (!MO.isReg())
338 continue;
339 if (!MO.isDef() && MO.isKill()) {
340 Changed = true;
341 MO.setIsKill(false);
342 }
343
344 if (MO.isDef() && MO.isDead()) {
345 Changed = true;
346 MO.setIsDead(false);
347 }
348 }
349 }
350
351 return Changed;
352}
353
354static bool runOnBasicBlock(MachineBasicBlock *MBB,
355 unsigned BasicBlockNum, VRegRenamer &Renamer) {
356 LLVM_DEBUG({
357 dbgs() << "\n\n NEW BASIC BLOCK: " << MBB->getName() << " \n\n";
358 dbgs() << "\n\n================================================\n\n";
359 });
360
361 bool Changed = false;
362
363 LLVM_DEBUG(dbgs() << "\n\n NEW BASIC BLOCK: " << MBB->getName() << "\n\n");
364
365 LLVM_DEBUG(dbgs() << "MBB Before Canonical Copy Propagation:\n";
366 MBB->dump(););
367 Changed |= propagateLocalCopies(MBB);
368 LLVM_DEBUG(dbgs() << "MBB After Canonical Copy Propagation:\n"; MBB->dump(););
369
370 LLVM_DEBUG(dbgs() << "MBB Before Scheduling:\n"; MBB->dump(););
371 unsigned IdempotentInstCount = 0;
372 Changed |= rescheduleCanonically(PseudoIdempotentInstCount&: IdempotentInstCount, MBB);
373 LLVM_DEBUG(dbgs() << "MBB After Scheduling:\n"; MBB->dump(););
374
375 Changed |= Renamer.renameVRegs(MBB, BBNum: BasicBlockNum);
376
377 // TODO: Consider dropping this. Dropping kill defs is probably not
378 // semantically sound.
379 Changed |= doDefKillClear(MBB);
380
381 LLVM_DEBUG(dbgs() << "Updated MachineBasicBlock:\n"; MBB->dump();
382 dbgs() << "\n");
383 LLVM_DEBUG(
384 dbgs() << "\n\n================================================\n\n");
385 return Changed;
386}
387
388bool MIRCanonicalizer::runOnMachineFunction(MachineFunction &MF) {
389
390 static unsigned functionNum = 0;
391 const CodeGenOptions &Opts = getCodeGenOptions(MF);
392 if (Opts.mir_canonicalizer_nth_function != ~0U) {
393 if (Opts.mir_canonicalizer_nth_function != functionNum++)
394 return false;
395 LLVM_DEBUG(dbgs() << "\n Canonicalizing Function " << MF.getName()
396 << "\n";);
397 }
398
399 // we need a valid vreg to create a vreg type for skipping all those
400 // stray vreg numbers so reach alignment/canonical vreg values.
401 std::vector<MachineBasicBlock *> RPOList = GetRPOList(MF);
402
403 LLVM_DEBUG(
404 dbgs() << "\n\n NEW MACHINE FUNCTION: " << MF.getName() << " \n\n";
405 dbgs() << "\n\n================================================\n\n";
406 dbgs() << "Total Basic Blocks: " << RPOList.size() << "\n";
407 for (auto MBB
408 : RPOList) { dbgs() << MBB->getName() << "\n"; } dbgs()
409 << "\n\n================================================\n\n";);
410
411 unsigned BBNum = 0;
412 bool Changed = false;
413 MachineRegisterInfo &MRI = MF.getRegInfo();
414 VRegRenamer Renamer(Opts, MRI);
415 for (auto *MBB : RPOList)
416 Changed |= runOnBasicBlock(MBB, BasicBlockNum: BBNum++, Renamer);
417
418 return Changed;
419}
420