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