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