LLVM  9.0.0svn
MIRCanonicalizerPass.cpp
Go to the documentation of this file.
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 
27 #include "llvm/ADT/STLExtras.h"
31 #include "llvm/CodeGen/Passes.h"
33 
34 #include <queue>
35 
36 using namespace llvm;
37 
38 namespace llvm {
39 extern char &MIRCanonicalizerID;
40 } // namespace llvm
41 
42 #define DEBUG_TYPE "mir-canonicalizer"
43 
44 static cl::opt<unsigned>
45  CanonicalizeFunctionNumber("canon-nth-function", cl::Hidden, cl::init(~0u),
46  cl::value_desc("N"),
47  cl::desc("Function number to canonicalize."));
48 
50  "canon-nth-basicblock", cl::Hidden, cl::init(~0u), cl::value_desc("N"),
51  cl::desc("BasicBlock number to canonicalize."));
52 
53 namespace {
54 
55 class MIRCanonicalizer : public MachineFunctionPass {
56 public:
57  static char ID;
58  MIRCanonicalizer() : MachineFunctionPass(ID) {}
59 
60  StringRef getPassName() const override {
61  return "Rename register operands in a canonical ordering.";
62  }
63 
64  void getAnalysisUsage(AnalysisUsage &AU) const override {
65  AU.setPreservesCFG();
67  }
68 
69  bool runOnMachineFunction(MachineFunction &MF) override;
70 };
71 
72 } // end anonymous namespace
73 
75 class TypedVReg {
76  VRType type;
77  unsigned reg;
78 
79 public:
80  TypedVReg(unsigned reg) : type(RSE_Reg), reg(reg) {}
81  TypedVReg(VRType type) : type(type), reg(~0U) {
82  assert(type != RSE_Reg && "Expected a non-register type.");
83  }
84 
85  bool isReg() const { return type == RSE_Reg; }
86  bool isFrameIndex() const { return type == RSE_FrameIndex; }
87  bool isCandidate() const { return type == RSE_NewCandidate; }
88 
89  VRType getType() const { return type; }
90  unsigned getReg() const {
91  assert(this->isReg() && "Expected a virtual or physical register.");
92  return reg;
93  }
94 };
95 
97 
99 
100 INITIALIZE_PASS_BEGIN(MIRCanonicalizer, "mir-canonicalizer",
101  "Rename Register Operands Canonically", false, false)
102 
103 INITIALIZE_PASS_END(MIRCanonicalizer, "mir-canonicalizer",
104  "Rename Register Operands Canonically", false, false)
105 
108  std::vector<MachineBasicBlock *> RPOList;
109  for (auto MBB : RPOT) {
110  RPOList.push_back(MBB);
111  }
112 
113  return RPOList;
114 }
115 
116 static bool
117 rescheduleLexographically(std::vector<MachineInstr *> instructions,
118  MachineBasicBlock *MBB,
120 
121  bool Changed = false;
122  using StringInstrPair = std::pair<std::string, MachineInstr *>;
123  std::vector<StringInstrPair> StringInstrMap;
124 
125  for (auto *II : instructions) {
126  std::string S;
127  raw_string_ostream OS(S);
128  II->print(OS);
129  OS.flush();
130 
131  // Trim the assignment, or start from the begining in the case of a store.
132  const size_t i = S.find("=");
133  StringInstrMap.push_back({(i == std::string::npos) ? S : S.substr(i), II});
134  }
135 
136  llvm::sort(StringInstrMap,
137  [](const StringInstrPair &a, const StringInstrPair &b) -> bool {
138  return (a.first < b.first);
139  });
140 
141  for (auto &II : StringInstrMap) {
142 
143  LLVM_DEBUG({
144  dbgs() << "Splicing ";
145  II.second->dump();
146  dbgs() << " right before: ";
147  getPos()->dump();
148  });
149 
150  Changed = true;
151  MBB->splice(getPos(), MBB, II.second);
152  }
153 
154  return Changed;
155 }
156 
157 static bool rescheduleCanonically(unsigned &PseudoIdempotentInstCount,
158  MachineBasicBlock *MBB) {
159 
160  bool Changed = false;
161 
162  // Calculates the distance of MI from the begining of its parent BB.
163  auto getInstrIdx = [](const MachineInstr &MI) {
164  unsigned i = 0;
165  for (auto &CurMI : *MI.getParent()) {
166  if (&CurMI == &MI)
167  return i;
168  i++;
169  }
170  return ~0U;
171  };
172 
173  // Pre-Populate vector of instructions to reschedule so that we don't
174  // clobber the iterator.
175  std::vector<MachineInstr *> Instructions;
176  for (auto &MI : *MBB) {
177  Instructions.push_back(&MI);
178  }
179 
180  std::map<MachineInstr *, std::vector<MachineInstr *>> MultiUsers;
181  std::vector<MachineInstr *> PseudoIdempotentInstructions;
182  std::vector<unsigned> PhysRegDefs;
183  for (auto *II : Instructions) {
184  for (unsigned i = 1; i < II->getNumOperands(); i++) {
185  MachineOperand &MO = II->getOperand(i);
186  if (!MO.isReg())
187  continue;
188 
190  continue;
191 
192  if (!MO.isDef())
193  continue;
194 
195  PhysRegDefs.push_back(MO.getReg());
196  }
197  }
198 
199  for (auto *II : Instructions) {
200  if (II->getNumOperands() == 0)
201  continue;
202  if (II->mayLoadOrStore())
203  continue;
204 
205  MachineOperand &MO = II->getOperand(0);
207  continue;
208  if (!MO.isDef())
209  continue;
210 
211  bool IsPseudoIdempotent = true;
212  for (unsigned i = 1; i < II->getNumOperands(); i++) {
213 
214  if (II->getOperand(i).isImm()) {
215  continue;
216  }
217 
218  if (II->getOperand(i).isReg()) {
219  if (!TargetRegisterInfo::isVirtualRegister(II->getOperand(i).getReg()))
220  if (llvm::find(PhysRegDefs, II->getOperand(i).getReg()) ==
221  PhysRegDefs.end()) {
222  continue;
223  }
224  }
225 
226  IsPseudoIdempotent = false;
227  break;
228  }
229 
230  if (IsPseudoIdempotent) {
231  PseudoIdempotentInstructions.push_back(II);
232  continue;
233  }
234 
235  LLVM_DEBUG(dbgs() << "Operand " << 0 << " of "; II->dump(); MO.dump(););
236 
237  MachineInstr *Def = II;
238  unsigned Distance = ~0U;
239  MachineInstr *UseToBringDefCloserTo = nullptr;
240  MachineRegisterInfo *MRI = &MBB->getParent()->getRegInfo();
241  for (auto &UO : MRI->use_nodbg_operands(MO.getReg())) {
242  MachineInstr *UseInst = UO.getParent();
243 
244  const unsigned DefLoc = getInstrIdx(*Def);
245  const unsigned UseLoc = getInstrIdx(*UseInst);
246  const unsigned Delta = (UseLoc - DefLoc);
247 
248  if (UseInst->getParent() != Def->getParent())
249  continue;
250  if (DefLoc >= UseLoc)
251  continue;
252 
253  if (Delta < Distance) {
254  Distance = Delta;
255  UseToBringDefCloserTo = UseInst;
256  }
257  }
258 
259  const auto BBE = MBB->instr_end();
260  MachineBasicBlock::iterator DefI = BBE;
261  MachineBasicBlock::iterator UseI = BBE;
262 
263  for (auto BBI = MBB->instr_begin(); BBI != BBE; ++BBI) {
264 
265  if (DefI != BBE && UseI != BBE)
266  break;
267 
268  if (&*BBI == Def) {
269  DefI = BBI;
270  continue;
271  }
272 
273  if (&*BBI == UseToBringDefCloserTo) {
274  UseI = BBI;
275  continue;
276  }
277  }
278 
279  if (DefI == BBE || UseI == BBE)
280  continue;
281 
282  LLVM_DEBUG({
283  dbgs() << "Splicing ";
284  DefI->dump();
285  dbgs() << " right before: ";
286  UseI->dump();
287  });
288 
289  MultiUsers[UseToBringDefCloserTo].push_back(Def);
290  Changed = true;
291  MBB->splice(UseI, MBB, DefI);
292  }
293 
294  // Sort the defs for users of multiple defs lexographically.
295  for (const auto &E : MultiUsers) {
296 
297  auto UseI =
298  std::find_if(MBB->instr_begin(), MBB->instr_end(),
299  [&](MachineInstr &MI) -> bool { return &MI == E.first; });
300 
301  if (UseI == MBB->instr_end())
302  continue;
303 
304  LLVM_DEBUG(
305  dbgs() << "Rescheduling Multi-Use Instructions Lexographically.";);
306  Changed |= rescheduleLexographically(
307  E.second, MBB, [&]() -> MachineBasicBlock::iterator { return UseI; });
308  }
309 
310  PseudoIdempotentInstCount = PseudoIdempotentInstructions.size();
311  LLVM_DEBUG(
312  dbgs() << "Rescheduling Idempotent Instructions Lexographically.";);
313  Changed |= rescheduleLexographically(
314  PseudoIdempotentInstructions, MBB,
315  [&]() -> MachineBasicBlock::iterator { return MBB->begin(); });
316 
317  return Changed;
318 }
319 
321  bool Changed = false;
323 
324  std::vector<MachineInstr *> Copies;
325  for (MachineInstr &MI : MBB->instrs()) {
326  if (MI.isCopy())
327  Copies.push_back(&MI);
328  }
329 
330  for (MachineInstr *MI : Copies) {
331 
332  if (!MI->getOperand(0).isReg())
333  continue;
334  if (!MI->getOperand(1).isReg())
335  continue;
336 
337  const unsigned Dst = MI->getOperand(0).getReg();
338  const unsigned Src = MI->getOperand(1).getReg();
339 
341  continue;
343  continue;
344  if (MRI.getRegClass(Dst) != MRI.getRegClass(Src))
345  continue;
346 
347  for (auto UI = MRI.use_begin(Dst); UI != MRI.use_end(); ++UI) {
348  MachineOperand *MO = &*UI;
349  MO->setReg(Src);
350  Changed = true;
351  }
352 
353  MI->eraseFromParent();
354  }
355 
356  return Changed;
357 }
358 
359 /// Here we find our candidates. What makes an interesting candidate?
360 /// An candidate for a canonicalization tree root is normally any kind of
361 /// instruction that causes side effects such as a store to memory or a copy to
362 /// a physical register or a return instruction. We use these as an expression
363 /// tree root that we walk inorder to build a canonical walk which should result
364 /// in canoncal vreg renaming.
365 static std::vector<MachineInstr *> populateCandidates(MachineBasicBlock *MBB) {
366  std::vector<MachineInstr *> Candidates;
368 
369  for (auto II = MBB->begin(), IE = MBB->end(); II != IE; ++II) {
370  MachineInstr *MI = &*II;
371 
372  bool DoesMISideEffect = false;
373 
374  if (MI->getNumOperands() > 0 && MI->getOperand(0).isReg()) {
375  const unsigned Dst = MI->getOperand(0).getReg();
376  DoesMISideEffect |= !TargetRegisterInfo::isVirtualRegister(Dst);
377 
378  for (auto UI = MRI.use_begin(Dst); UI != MRI.use_end(); ++UI) {
379  if (DoesMISideEffect)
380  break;
381  DoesMISideEffect |= (UI->getParent()->getParent() != MI->getParent());
382  }
383  }
384 
385  if (!MI->mayStore() && !MI->isBranch() && !DoesMISideEffect)
386  continue;
387 
388  LLVM_DEBUG(dbgs() << "Found Candidate: "; MI->dump(););
389  Candidates.push_back(MI);
390  }
391 
392  return Candidates;
393 }
394 
395 static void doCandidateWalk(std::vector<TypedVReg> &VRegs,
396  std::queue<TypedVReg> &RegQueue,
397  std::vector<MachineInstr *> &VisitedMIs,
398  const MachineBasicBlock *MBB) {
399 
400  const MachineFunction &MF = *MBB->getParent();
401  const MachineRegisterInfo &MRI = MF.getRegInfo();
402 
403  while (!RegQueue.empty()) {
404 
405  auto TReg = RegQueue.front();
406  RegQueue.pop();
407 
408  if (TReg.isFrameIndex()) {
409  LLVM_DEBUG(dbgs() << "Popping frame index.\n";);
410  VRegs.push_back(TypedVReg(RSE_FrameIndex));
411  continue;
412  }
413 
414  assert(TReg.isReg() && "Expected vreg or physreg.");
415  unsigned Reg = TReg.getReg();
416 
418  LLVM_DEBUG({
419  dbgs() << "Popping vreg ";
420  MRI.def_begin(Reg)->dump();
421  dbgs() << "\n";
422  });
423 
424  if (!llvm::any_of(VRegs, [&](const TypedVReg &TR) {
425  return TR.isReg() && TR.getReg() == Reg;
426  })) {
427  VRegs.push_back(TypedVReg(Reg));
428  }
429  } else {
430  LLVM_DEBUG(dbgs() << "Popping physreg.\n";);
431  VRegs.push_back(TypedVReg(Reg));
432  continue;
433  }
434 
435  for (auto RI = MRI.def_begin(Reg), RE = MRI.def_end(); RI != RE; ++RI) {
436  MachineInstr *Def = RI->getParent();
437 
438  if (Def->getParent() != MBB)
439  continue;
440 
441  if (llvm::any_of(VisitedMIs,
442  [&](const MachineInstr *VMI) { return Def == VMI; })) {
443  break;
444  }
445 
446  LLVM_DEBUG({
447  dbgs() << "\n========================\n";
448  dbgs() << "Visited MI: ";
449  Def->dump();
450  dbgs() << "BB Name: " << Def->getParent()->getName() << "\n";
451  dbgs() << "\n========================\n";
452  });
453  VisitedMIs.push_back(Def);
454  for (unsigned I = 1, E = Def->getNumOperands(); I != E; ++I) {
455 
456  MachineOperand &MO = Def->getOperand(I);
457  if (MO.isFI()) {
458  LLVM_DEBUG(dbgs() << "Pushing frame index.\n";);
459  RegQueue.push(TypedVReg(RSE_FrameIndex));
460  }
461 
462  if (!MO.isReg())
463  continue;
464  RegQueue.push(TypedVReg(MO.getReg()));
465  }
466  }
467  }
468 }
469 
470 namespace {
471 class NamedVRegCursor {
473  unsigned virtualVRegNumber;
474 
475 public:
476  NamedVRegCursor(MachineRegisterInfo &MRI) : MRI(MRI) {
477  unsigned VRegGapIndex = 0;
478  const unsigned VR_GAP = (++VRegGapIndex * 1000);
479 
480  unsigned I = MRI.createIncompleteVirtualRegister();
481  const unsigned E = (((I + VR_GAP) / VR_GAP) + 1) * VR_GAP;
482 
483  virtualVRegNumber = E;
484  }
485 
486  void SkipVRegs() {
487  unsigned VRegGapIndex = 1;
488  const unsigned VR_GAP = (++VRegGapIndex * 1000);
489 
490  unsigned I = virtualVRegNumber;
491  const unsigned E = (((I + VR_GAP) / VR_GAP) + 1) * VR_GAP;
492 
493  virtualVRegNumber = E;
494  }
495 
496  unsigned getVirtualVReg() const { return virtualVRegNumber; }
497 
498  unsigned incrementVirtualVReg(unsigned incr = 1) {
499  virtualVRegNumber += incr;
500  return virtualVRegNumber;
501  }
502 
503  unsigned createVirtualRegister(const TargetRegisterClass *RC) {
504  std::string S;
505  raw_string_ostream OS(S);
506  OS << "namedVReg" << (virtualVRegNumber & ~0x80000000);
507  OS.flush();
508  virtualVRegNumber++;
509 
510  return MRI.createVirtualRegister(RC, OS.str());
511  }
512 };
513 } // namespace
514 
515 static std::map<unsigned, unsigned>
516 GetVRegRenameMap(const std::vector<TypedVReg> &VRegs,
517  const std::vector<unsigned> &renamedInOtherBB,
518  MachineRegisterInfo &MRI, NamedVRegCursor &NVC) {
519  std::map<unsigned, unsigned> VRegRenameMap;
520  bool FirstCandidate = true;
521 
522  for (auto &vreg : VRegs) {
523  if (vreg.isFrameIndex()) {
524  // We skip one vreg for any frame index because there is a good chance
525  // (especially when comparing SelectionDAG to GlobalISel generated MIR)
526  // that in the other file we are just getting an incoming vreg that comes
527  // from a copy from a frame index. So it's safe to skip by one.
528  unsigned LastRenameReg = NVC.incrementVirtualVReg();
529  (void)LastRenameReg;
530  LLVM_DEBUG(dbgs() << "Skipping rename for FI " << LastRenameReg << "\n";);
531  continue;
532  } else if (vreg.isCandidate()) {
533 
534  // After the first candidate, for every subsequent candidate, we skip mod
535  // 10 registers so that the candidates are more likely to start at the
536  // same vreg number making it more likely that the canonical walk from the
537  // candidate insruction. We don't need to skip from the first candidate of
538  // the BasicBlock because we already skip ahead several vregs for each BB.
539  unsigned LastRenameReg = NVC.getVirtualVReg();
540  if (FirstCandidate)
541  NVC.incrementVirtualVReg(LastRenameReg % 10);
542  FirstCandidate = false;
543  continue;
544  } else if (!TargetRegisterInfo::isVirtualRegister(vreg.getReg())) {
545  unsigned LastRenameReg = NVC.incrementVirtualVReg();
546  (void)LastRenameReg;
547  LLVM_DEBUG({
548  dbgs() << "Skipping rename for Phys Reg " << LastRenameReg << "\n";
549  });
550  continue;
551  }
552 
553  auto Reg = vreg.getReg();
554  if (llvm::find(renamedInOtherBB, Reg) != renamedInOtherBB.end()) {
555  LLVM_DEBUG(dbgs() << "Vreg " << Reg
556  << " already renamed in other BB.\n";);
557  continue;
558  }
559 
560  auto Rename = NVC.createVirtualRegister(MRI.getRegClass(Reg));
561 
562  if (VRegRenameMap.find(Reg) == VRegRenameMap.end()) {
563  LLVM_DEBUG(dbgs() << "Mapping vreg ";);
564  if (MRI.reg_begin(Reg) != MRI.reg_end()) {
565  LLVM_DEBUG(auto foo = &*MRI.reg_begin(Reg); foo->dump(););
566  } else {
567  LLVM_DEBUG(dbgs() << Reg;);
568  }
569  LLVM_DEBUG(dbgs() << " to ";);
570  if (MRI.reg_begin(Rename) != MRI.reg_end()) {
571  LLVM_DEBUG(auto foo = &*MRI.reg_begin(Rename); foo->dump(););
572  } else {
573  LLVM_DEBUG(dbgs() << Rename;);
574  }
575  LLVM_DEBUG(dbgs() << "\n";);
576 
577  VRegRenameMap.insert(std::pair<unsigned, unsigned>(Reg, Rename));
578  }
579  }
580 
581  return VRegRenameMap;
582 }
583 
584 static bool doVRegRenaming(std::vector<unsigned> &RenamedInOtherBB,
585  const std::map<unsigned, unsigned> &VRegRenameMap,
587  bool Changed = false;
588  for (auto I = VRegRenameMap.begin(), E = VRegRenameMap.end(); I != E; ++I) {
589 
590  auto VReg = I->first;
591  auto Rename = I->second;
592 
593  RenamedInOtherBB.push_back(Rename);
594 
595  std::vector<MachineOperand *> RenameMOs;
596  for (auto &MO : MRI.reg_operands(VReg)) {
597  RenameMOs.push_back(&MO);
598  }
599 
600  for (auto *MO : RenameMOs) {
601  Changed = true;
602  MO->setReg(Rename);
603 
604  if (!MO->isDef())
605  MO->setIsKill(false);
606  }
607  }
608 
609  return Changed;
610 }
611 
613  bool Changed = false;
614 
615  for (auto &MI : *MBB) {
616  for (auto &MO : MI.operands()) {
617  if (!MO.isReg())
618  continue;
619  if (!MO.isDef() && MO.isKill()) {
620  Changed = true;
621  MO.setIsKill(false);
622  }
623 
624  if (MO.isDef() && MO.isDead()) {
625  Changed = true;
626  MO.setIsDead(false);
627  }
628  }
629  }
630 
631  return Changed;
632 }
633 
635  std::vector<StringRef> &bbNames,
636  std::vector<unsigned> &renamedInOtherBB,
637  unsigned &basicBlockNum, unsigned &VRegGapIndex,
638  NamedVRegCursor &NVC) {
639 
640  if (CanonicalizeBasicBlockNumber != ~0U) {
641  if (CanonicalizeBasicBlockNumber != basicBlockNum++)
642  return false;
643  LLVM_DEBUG(dbgs() << "\n Canonicalizing BasicBlock " << MBB->getName()
644  << "\n";);
645  }
646 
647  if (llvm::find(bbNames, MBB->getName()) != bbNames.end()) {
648  LLVM_DEBUG({
649  dbgs() << "Found potentially duplicate BasicBlocks: " << MBB->getName()
650  << "\n";
651  });
652  return false;
653  }
654 
655  LLVM_DEBUG({
656  dbgs() << "\n\n NEW BASIC BLOCK: " << MBB->getName() << " \n\n";
657  dbgs() << "\n\n================================================\n\n";
658  });
659 
660  bool Changed = false;
661  MachineFunction &MF = *MBB->getParent();
663 
664  bbNames.push_back(MBB->getName());
665  LLVM_DEBUG(dbgs() << "\n\n NEW BASIC BLOCK: " << MBB->getName() << "\n\n";);
666 
667  LLVM_DEBUG(dbgs() << "MBB Before Canonical Copy Propagation:\n";
668  MBB->dump(););
669  Changed |= propagateLocalCopies(MBB);
670  LLVM_DEBUG(dbgs() << "MBB After Canonical Copy Propagation:\n"; MBB->dump(););
671 
672  LLVM_DEBUG(dbgs() << "MBB Before Scheduling:\n"; MBB->dump(););
673  unsigned IdempotentInstCount = 0;
674  Changed |= rescheduleCanonically(IdempotentInstCount, MBB);
675  LLVM_DEBUG(dbgs() << "MBB After Scheduling:\n"; MBB->dump(););
676 
677  std::vector<MachineInstr *> Candidates = populateCandidates(MBB);
678  std::vector<MachineInstr *> VisitedMIs;
679  llvm::copy(Candidates, std::back_inserter(VisitedMIs));
680 
681  std::vector<TypedVReg> VRegs;
682  for (auto candidate : Candidates) {
683  VRegs.push_back(TypedVReg(RSE_NewCandidate));
684 
685  std::queue<TypedVReg> RegQueue;
686 
687  // Here we walk the vreg operands of a non-root node along our walk.
688  // The root nodes are the original candidates (stores normally).
689  // These are normally not the root nodes (except for the case of copies to
690  // physical registers).
691  for (unsigned i = 1; i < candidate->getNumOperands(); i++) {
692  if (candidate->mayStore() || candidate->isBranch())
693  break;
694 
695  MachineOperand &MO = candidate->getOperand(i);
697  continue;
698 
699  LLVM_DEBUG(dbgs() << "Enqueue register"; MO.dump(); dbgs() << "\n";);
700  RegQueue.push(TypedVReg(MO.getReg()));
701  }
702 
703  // Here we walk the root candidates. We start from the 0th operand because
704  // the root is normally a store to a vreg.
705  for (unsigned i = 0; i < candidate->getNumOperands(); i++) {
706 
707  if (!candidate->mayStore() && !candidate->isBranch())
708  break;
709 
710  MachineOperand &MO = candidate->getOperand(i);
711 
712  // TODO: Do we want to only add vregs here?
713  if (!MO.isReg() && !MO.isFI())
714  continue;
715 
716  LLVM_DEBUG(dbgs() << "Enqueue Reg/FI"; MO.dump(); dbgs() << "\n";);
717 
718  RegQueue.push(MO.isReg() ? TypedVReg(MO.getReg())
720  }
721 
722  doCandidateWalk(VRegs, RegQueue, VisitedMIs, MBB);
723  }
724 
725  // If we have populated no vregs to rename then bail.
726  // The rest of this function does the vreg remaping.
727  if (VRegs.size() == 0)
728  return Changed;
729 
730  auto VRegRenameMap = GetVRegRenameMap(VRegs, renamedInOtherBB, MRI, NVC);
731  Changed |= doVRegRenaming(renamedInOtherBB, VRegRenameMap, MRI);
732 
733  // Here we renumber the def vregs for the idempotent instructions from the top
734  // of the MachineBasicBlock so that they are named in the order that we sorted
735  // them alphabetically. Eventually we wont need SkipVRegs because we will use
736  // named vregs instead.
737  NVC.SkipVRegs();
738 
739  auto MII = MBB->begin();
740  for (unsigned i = 0; i < IdempotentInstCount && MII != MBB->end(); ++i) {
741  MachineInstr &MI = *MII++;
742  Changed = true;
743  unsigned vRegToRename = MI.getOperand(0).getReg();
744  auto Rename = NVC.createVirtualRegister(MRI.getRegClass(vRegToRename));
745 
746  std::vector<MachineOperand *> RenameMOs;
747  for (auto &MO : MRI.reg_operands(vRegToRename)) {
748  RenameMOs.push_back(&MO);
749  }
750 
751  for (auto *MO : RenameMOs) {
752  MO->setReg(Rename);
753  }
754  }
755 
756  Changed |= doDefKillClear(MBB);
757 
758  LLVM_DEBUG(dbgs() << "Updated MachineBasicBlock:\n"; MBB->dump();
759  dbgs() << "\n";);
760  LLVM_DEBUG(
761  dbgs() << "\n\n================================================\n\n");
762  return Changed;
763 }
764 
765 bool MIRCanonicalizer::runOnMachineFunction(MachineFunction &MF) {
766 
767  static unsigned functionNum = 0;
768  if (CanonicalizeFunctionNumber != ~0U) {
769  if (CanonicalizeFunctionNumber != functionNum++)
770  return false;
771  LLVM_DEBUG(dbgs() << "\n Canonicalizing Function " << MF.getName()
772  << "\n";);
773  }
774 
775  // we need a valid vreg to create a vreg type for skipping all those
776  // stray vreg numbers so reach alignment/canonical vreg values.
777  std::vector<MachineBasicBlock *> RPOList = GetRPOList(MF);
778 
779  LLVM_DEBUG(
780  dbgs() << "\n\n NEW MACHINE FUNCTION: " << MF.getName() << " \n\n";
781  dbgs() << "\n\n================================================\n\n";
782  dbgs() << "Total Basic Blocks: " << RPOList.size() << "\n";
783  for (auto MBB
784  : RPOList) { dbgs() << MBB->getName() << "\n"; } dbgs()
785  << "\n\n================================================\n\n";);
786 
787  std::vector<StringRef> BBNames;
788  std::vector<unsigned> RenamedInOtherBB;
789 
790  unsigned GapIdx = 0;
791  unsigned BBNum = 0;
792 
793  bool Changed = false;
794 
796  NamedVRegCursor NVC(MRI);
797  for (auto MBB : RPOList)
798  Changed |=
799  runOnBasicBlock(MBB, BBNames, RenamedInOtherBB, BBNum, GapIdx, NVC);
800 
801  return Changed;
802 }
static bool isReg(const MCInst &MI, unsigned OpNo)
static bool doVRegRenaming(std::vector< unsigned > &RenamedInOtherBB, const std::map< unsigned, unsigned > &VRegRenameMap, MachineRegisterInfo &MRI)
char & MIRCanonicalizerID
static std::vector< MachineInstr * > populateCandidates(MachineBasicBlock *MBB)
Here we find our candidates.
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
iterator_range< use_nodbg_iterator > use_nodbg_operands(unsigned Reg) const
unsigned getReg() const
getReg - Returns the register number.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
unsigned Reg
static bool rescheduleLexographically(std::vector< MachineInstr *> instructions, MachineBasicBlock *MBB, std::function< MachineBasicBlock::iterator()> getPos)
iterator_range< reg_iterator > reg_operands(unsigned Reg) const
unsigned getReg() const
Definition: BitVector.h:937
static use_iterator use_end()
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:411
bool isReg() const
mir Rename Register Operands Canonically
def_iterator def_begin(unsigned RegNo) const
static bool doDefKillClear(MachineBasicBlock *MBB)
static cl::opt< unsigned > CanonicalizeFunctionNumber("canon-nth-function", cl::Hidden, cl::init(~0u), cl::value_desc("N"), cl::desc("Function number to canonicalize."))
static cl::opt< unsigned > CanonicalizeBasicBlockNumber("canon-nth-basicblock", cl::Hidden, cl::init(~0u), cl::value_desc("N"), cl::desc("BasicBlock number to canonicalize."))
TypedVReg(VRType type)
bool isBranch(QueryType Type=AnyInBundle) const
Returns true if this is a conditional, unconditional, or indirect branch.
Definition: MachineInstr.h:656
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
Definition: MachineInstr.h:819
bool isFrameIndex() const
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
unsigned const MachineRegisterInfo * MRI
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
mir Rename Register Operands static false std::vector< MachineBasicBlock * > GetRPOList(MachineFunction &MF)
Represent the analysis usage information of a pass.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1192
static bool rescheduleCanonically(unsigned &PseudoIdempotentInstCount, MachineBasicBlock *MBB)
mir canonicalizer
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1213
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1206
std::string & str()
Flushes the stream contents to the target string and returns the string&#39;s reference.
Definition: raw_ostream.h:498
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1115
unsigned createIncompleteVirtualRegister(StringRef Name="")
Creates a new virtual register that has no register class, register bank or size assigned yet...
MachineOperand class - Representation of each machine instruction operand.
VRType getType() const
SI Lower i1 Copies
Promote Memory to Register
Definition: Mem2Reg.cpp:109
reg_iterator reg_begin(unsigned RegNo) const
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
static bool propagateLocalCopies(MachineBasicBlock *MBB)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
INITIALIZE_PASS_BEGIN(MIRCanonicalizer, "mir-canonicalizer", "Rename Register Operands Canonically", false, false) INITIALIZE_PASS_END(MIRCanonicalizer
static bool runOnBasicBlock(MachineBasicBlock *MBB, std::vector< StringRef > &bbNames, std::vector< unsigned > &renamedInOtherBB, unsigned &basicBlockNum, unsigned &VRegGapIndex, NamedVRegCursor &NVC)
static std::map< unsigned, unsigned > GetVRegRenameMap(const std::vector< TypedVReg > &VRegs, const std::vector< unsigned > &renamedInOtherBB, MachineRegisterInfo &MRI, NamedVRegCursor &NVC)
bool isCandidate() const
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:253
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:63
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB &#39;Other&#39; at the position From, and insert it into this MBB right before &#39;...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
use_iterator use_begin(unsigned RegNo) const
void setReg(unsigned Reg)
Change the register this operand corresponds to.
#define I(x, y, z)
Definition: MD5.cpp:58
bool isFI() const
isFI - Tests if this is a MO_FrameIndex operand.
TypedVReg(unsigned reg)
bool isReg() const
isReg - Tests if this is a MO_Register operand.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static def_iterator def_end()
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:482
print Print MemDeps of function
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
inst_range instructions(Function *F)
Definition: InstIterator.h:133
#define LLVM_DEBUG(X)
Definition: Debug.h:122
static reg_iterator reg_end()
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:413
OutputIt copy(R &&Range, OutputIt Out)
Definition: STLExtras.h:1237
unsigned createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
static void doCandidateWalk(std::vector< TypedVReg > &VRegs, std::queue< TypedVReg > &RegQueue, std::vector< MachineInstr *> &VisitedMIs, const MachineBasicBlock *MBB)