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 
107  if (MF.empty())
108  return {};
110  std::vector<MachineBasicBlock *> RPOList;
111  for (auto MBB : RPOT) {
112  RPOList.push_back(MBB);
113  }
114 
115  return RPOList;
116 }
117 
118 static bool
119 rescheduleLexographically(std::vector<MachineInstr *> instructions,
120  MachineBasicBlock *MBB,
122 
123  bool Changed = false;
124  using StringInstrPair = std::pair<std::string, MachineInstr *>;
125  std::vector<StringInstrPair> StringInstrMap;
126 
127  for (auto *II : instructions) {
128  std::string S;
129  raw_string_ostream OS(S);
130  II->print(OS);
131  OS.flush();
132 
133  // Trim the assignment, or start from the begining in the case of a store.
134  const size_t i = S.find("=");
135  StringInstrMap.push_back({(i == std::string::npos) ? S : S.substr(i), II});
136  }
137 
138  llvm::sort(StringInstrMap,
139  [](const StringInstrPair &a, const StringInstrPair &b) -> bool {
140  return (a.first < b.first);
141  });
142 
143  for (auto &II : StringInstrMap) {
144 
145  LLVM_DEBUG({
146  dbgs() << "Splicing ";
147  II.second->dump();
148  dbgs() << " right before: ";
149  getPos()->dump();
150  });
151 
152  Changed = true;
153  MBB->splice(getPos(), MBB, II.second);
154  }
155 
156  return Changed;
157 }
158 
159 static bool rescheduleCanonically(unsigned &PseudoIdempotentInstCount,
160  MachineBasicBlock *MBB) {
161 
162  bool Changed = false;
163 
164  // Calculates the distance of MI from the begining of its parent BB.
165  auto getInstrIdx = [](const MachineInstr &MI) {
166  unsigned i = 0;
167  for (auto &CurMI : *MI.getParent()) {
168  if (&CurMI == &MI)
169  return i;
170  i++;
171  }
172  return ~0U;
173  };
174 
175  // Pre-Populate vector of instructions to reschedule so that we don't
176  // clobber the iterator.
177  std::vector<MachineInstr *> Instructions;
178  for (auto &MI : *MBB) {
179  Instructions.push_back(&MI);
180  }
181 
182  std::map<MachineInstr *, std::vector<MachineInstr *>> MultiUsers;
183  std::map<unsigned, MachineInstr *> MultiUserLookup;
184  unsigned UseToBringDefCloserToCount = 0;
185  std::vector<MachineInstr *> PseudoIdempotentInstructions;
186  std::vector<unsigned> PhysRegDefs;
187  for (auto *II : Instructions) {
188  for (unsigned i = 1; i < II->getNumOperands(); i++) {
189  MachineOperand &MO = II->getOperand(i);
190  if (!MO.isReg())
191  continue;
192 
194  continue;
195 
196  if (!MO.isDef())
197  continue;
198 
199  PhysRegDefs.push_back(MO.getReg());
200  }
201  }
202 
203  for (auto *II : Instructions) {
204  if (II->getNumOperands() == 0)
205  continue;
206  if (II->mayLoadOrStore())
207  continue;
208 
209  MachineOperand &MO = II->getOperand(0);
211  continue;
212  if (!MO.isDef())
213  continue;
214 
215  bool IsPseudoIdempotent = true;
216  for (unsigned i = 1; i < II->getNumOperands(); i++) {
217 
218  if (II->getOperand(i).isImm()) {
219  continue;
220  }
221 
222  if (II->getOperand(i).isReg()) {
223  if (!TargetRegisterInfo::isVirtualRegister(II->getOperand(i).getReg()))
224  if (llvm::find(PhysRegDefs, II->getOperand(i).getReg()) ==
225  PhysRegDefs.end()) {
226  continue;
227  }
228  }
229 
230  IsPseudoIdempotent = false;
231  break;
232  }
233 
234  if (IsPseudoIdempotent) {
235  PseudoIdempotentInstructions.push_back(II);
236  continue;
237  }
238 
239  LLVM_DEBUG(dbgs() << "Operand " << 0 << " of "; II->dump(); MO.dump(););
240 
241  MachineInstr *Def = II;
242  unsigned Distance = ~0U;
243  MachineInstr *UseToBringDefCloserTo = nullptr;
244  MachineRegisterInfo *MRI = &MBB->getParent()->getRegInfo();
245  for (auto &UO : MRI->use_nodbg_operands(MO.getReg())) {
246  MachineInstr *UseInst = UO.getParent();
247 
248  const unsigned DefLoc = getInstrIdx(*Def);
249  const unsigned UseLoc = getInstrIdx(*UseInst);
250  const unsigned Delta = (UseLoc - DefLoc);
251 
252  if (UseInst->getParent() != Def->getParent())
253  continue;
254  if (DefLoc >= UseLoc)
255  continue;
256 
257  if (Delta < Distance) {
258  Distance = Delta;
259  UseToBringDefCloserTo = UseInst;
260  MultiUserLookup[UseToBringDefCloserToCount++] = UseToBringDefCloserTo;
261  }
262  }
263 
264  const auto BBE = MBB->instr_end();
265  MachineBasicBlock::iterator DefI = BBE;
266  MachineBasicBlock::iterator UseI = BBE;
267 
268  for (auto BBI = MBB->instr_begin(); BBI != BBE; ++BBI) {
269 
270  if (DefI != BBE && UseI != BBE)
271  break;
272 
273  if (&*BBI == Def) {
274  DefI = BBI;
275  continue;
276  }
277 
278  if (&*BBI == UseToBringDefCloserTo) {
279  UseI = BBI;
280  continue;
281  }
282  }
283 
284  if (DefI == BBE || UseI == BBE)
285  continue;
286 
287  LLVM_DEBUG({
288  dbgs() << "Splicing ";
289  DefI->dump();
290  dbgs() << " right before: ";
291  UseI->dump();
292  });
293 
294  MultiUsers[UseToBringDefCloserTo].push_back(Def);
295  Changed = true;
296  MBB->splice(UseI, MBB, DefI);
297  }
298 
299  // Sort the defs for users of multiple defs lexographically.
300  for (const auto &E : MultiUserLookup) {
301 
302  auto UseI =
303  std::find_if(MBB->instr_begin(), MBB->instr_end(),
304  [&](MachineInstr &MI) -> bool { return &MI == E.second; });
305 
306  if (UseI == MBB->instr_end())
307  continue;
308 
309  LLVM_DEBUG(
310  dbgs() << "Rescheduling Multi-Use Instructions Lexographically.";);
311  Changed |= rescheduleLexographically(
312  MultiUsers[E.second], MBB,
313  [&]() -> MachineBasicBlock::iterator { return UseI; });
314  }
315 
316  PseudoIdempotentInstCount = PseudoIdempotentInstructions.size();
317  LLVM_DEBUG(
318  dbgs() << "Rescheduling Idempotent Instructions Lexographically.";);
319  Changed |= rescheduleLexographically(
320  PseudoIdempotentInstructions, MBB,
321  [&]() -> MachineBasicBlock::iterator { return MBB->begin(); });
322 
323  return Changed;
324 }
325 
327  bool Changed = false;
329 
330  std::vector<MachineInstr *> Copies;
331  for (MachineInstr &MI : MBB->instrs()) {
332  if (MI.isCopy())
333  Copies.push_back(&MI);
334  }
335 
336  for (MachineInstr *MI : Copies) {
337 
338  if (!MI->getOperand(0).isReg())
339  continue;
340  if (!MI->getOperand(1).isReg())
341  continue;
342 
343  const unsigned Dst = MI->getOperand(0).getReg();
344  const unsigned Src = MI->getOperand(1).getReg();
345 
347  continue;
349  continue;
350  // Not folding COPY instructions if regbankselect has not set the RCs.
351  // Why are we only considering Register Classes? Because the verifier
352  // sometimes gets upset if the register classes don't match even if the
353  // types do. A future patch might add COPY folding for matching types in
354  // pre-registerbankselect code.
355  if (!MRI.getRegClassOrNull(Dst))
356  continue;
357  if (MRI.getRegClass(Dst) != MRI.getRegClass(Src))
358  continue;
359 
360  std::vector<MachineOperand *> Uses;
361  for (auto UI = MRI.use_begin(Dst); UI != MRI.use_end(); ++UI)
362  Uses.push_back(&*UI);
363  for (auto *MO : Uses)
364  MO->setReg(Src);
365 
366  Changed = true;
367  MI->eraseFromParent();
368  }
369 
370  return Changed;
371 }
372 
373 /// Here we find our candidates. What makes an interesting candidate?
374 /// An candidate for a canonicalization tree root is normally any kind of
375 /// instruction that causes side effects such as a store to memory or a copy to
376 /// a physical register or a return instruction. We use these as an expression
377 /// tree root that we walk inorder to build a canonical walk which should result
378 /// in canoncal vreg renaming.
379 static std::vector<MachineInstr *> populateCandidates(MachineBasicBlock *MBB) {
380  std::vector<MachineInstr *> Candidates;
382 
383  for (auto II = MBB->begin(), IE = MBB->end(); II != IE; ++II) {
384  MachineInstr *MI = &*II;
385 
386  bool DoesMISideEffect = false;
387 
388  if (MI->getNumOperands() > 0 && MI->getOperand(0).isReg()) {
389  const unsigned Dst = MI->getOperand(0).getReg();
390  DoesMISideEffect |= !TargetRegisterInfo::isVirtualRegister(Dst);
391 
392  for (auto UI = MRI.use_begin(Dst); UI != MRI.use_end(); ++UI) {
393  if (DoesMISideEffect)
394  break;
395  DoesMISideEffect |= (UI->getParent()->getParent() != MI->getParent());
396  }
397  }
398 
399  if (!MI->mayStore() && !MI->isBranch() && !DoesMISideEffect)
400  continue;
401 
402  LLVM_DEBUG(dbgs() << "Found Candidate: "; MI->dump(););
403  Candidates.push_back(MI);
404  }
405 
406  return Candidates;
407 }
408 
409 static void doCandidateWalk(std::vector<TypedVReg> &VRegs,
410  std::queue<TypedVReg> &RegQueue,
411  std::vector<MachineInstr *> &VisitedMIs,
412  const MachineBasicBlock *MBB) {
413 
414  const MachineFunction &MF = *MBB->getParent();
415  const MachineRegisterInfo &MRI = MF.getRegInfo();
416 
417  while (!RegQueue.empty()) {
418 
419  auto TReg = RegQueue.front();
420  RegQueue.pop();
421 
422  if (TReg.isFrameIndex()) {
423  LLVM_DEBUG(dbgs() << "Popping frame index.\n";);
424  VRegs.push_back(TypedVReg(RSE_FrameIndex));
425  continue;
426  }
427 
428  assert(TReg.isReg() && "Expected vreg or physreg.");
429  unsigned Reg = TReg.getReg();
430 
432  LLVM_DEBUG({
433  dbgs() << "Popping vreg ";
434  MRI.def_begin(Reg)->dump();
435  dbgs() << "\n";
436  });
437 
438  if (!llvm::any_of(VRegs, [&](const TypedVReg &TR) {
439  return TR.isReg() && TR.getReg() == Reg;
440  })) {
441  VRegs.push_back(TypedVReg(Reg));
442  }
443  } else {
444  LLVM_DEBUG(dbgs() << "Popping physreg.\n";);
445  VRegs.push_back(TypedVReg(Reg));
446  continue;
447  }
448 
449  for (auto RI = MRI.def_begin(Reg), RE = MRI.def_end(); RI != RE; ++RI) {
450  MachineInstr *Def = RI->getParent();
451 
452  if (Def->getParent() != MBB)
453  continue;
454 
455  if (llvm::any_of(VisitedMIs,
456  [&](const MachineInstr *VMI) { return Def == VMI; })) {
457  break;
458  }
459 
460  LLVM_DEBUG({
461  dbgs() << "\n========================\n";
462  dbgs() << "Visited MI: ";
463  Def->dump();
464  dbgs() << "BB Name: " << Def->getParent()->getName() << "\n";
465  dbgs() << "\n========================\n";
466  });
467  VisitedMIs.push_back(Def);
468  for (unsigned I = 1, E = Def->getNumOperands(); I != E; ++I) {
469 
470  MachineOperand &MO = Def->getOperand(I);
471  if (MO.isFI()) {
472  LLVM_DEBUG(dbgs() << "Pushing frame index.\n";);
473  RegQueue.push(TypedVReg(RSE_FrameIndex));
474  }
475 
476  if (!MO.isReg())
477  continue;
478  RegQueue.push(TypedVReg(MO.getReg()));
479  }
480  }
481  }
482 }
483 
484 namespace {
485 class NamedVRegCursor {
487  unsigned virtualVRegNumber;
488 
489 public:
490  NamedVRegCursor(MachineRegisterInfo &MRI) : MRI(MRI), virtualVRegNumber(0) {}
491 
492  void SkipVRegs() {
493  unsigned VRegGapIndex = 1;
494  if (!virtualVRegNumber) {
495  VRegGapIndex = 0;
496  virtualVRegNumber = MRI.createIncompleteVirtualRegister();
497  }
498  const unsigned VR_GAP = (++VRegGapIndex * 1000);
499 
500  unsigned I = virtualVRegNumber;
501  const unsigned E = (((I + VR_GAP) / VR_GAP) + 1) * VR_GAP;
502 
503  virtualVRegNumber = E;
504  }
505 
506  unsigned getVirtualVReg() const { return virtualVRegNumber; }
507 
508  unsigned incrementVirtualVReg(unsigned incr = 1) {
509  virtualVRegNumber += incr;
510  return virtualVRegNumber;
511  }
512 
513  unsigned createVirtualRegister(unsigned VReg) {
514  if (!virtualVRegNumber)
515  SkipVRegs();
516  std::string S;
517  raw_string_ostream OS(S);
518  OS << "namedVReg" << (virtualVRegNumber & ~0x80000000);
519  OS.flush();
520  virtualVRegNumber++;
521  if (auto RC = MRI.getRegClassOrNull(VReg))
522  return MRI.createVirtualRegister(RC, OS.str());
523  return MRI.createGenericVirtualRegister(MRI.getType(VReg), OS.str());
524  }
525 };
526 } // namespace
527 
528 static std::map<unsigned, unsigned>
529 GetVRegRenameMap(const std::vector<TypedVReg> &VRegs,
530  const std::vector<unsigned> &renamedInOtherBB,
531  MachineRegisterInfo &MRI, NamedVRegCursor &NVC) {
532  std::map<unsigned, unsigned> VRegRenameMap;
533  bool FirstCandidate = true;
534 
535  for (auto &vreg : VRegs) {
536  if (vreg.isFrameIndex()) {
537  // We skip one vreg for any frame index because there is a good chance
538  // (especially when comparing SelectionDAG to GlobalISel generated MIR)
539  // that in the other file we are just getting an incoming vreg that comes
540  // from a copy from a frame index. So it's safe to skip by one.
541  unsigned LastRenameReg = NVC.incrementVirtualVReg();
542  (void)LastRenameReg;
543  LLVM_DEBUG(dbgs() << "Skipping rename for FI " << LastRenameReg << "\n";);
544  continue;
545  } else if (vreg.isCandidate()) {
546 
547  // After the first candidate, for every subsequent candidate, we skip mod
548  // 10 registers so that the candidates are more likely to start at the
549  // same vreg number making it more likely that the canonical walk from the
550  // candidate insruction. We don't need to skip from the first candidate of
551  // the BasicBlock because we already skip ahead several vregs for each BB.
552  unsigned LastRenameReg = NVC.getVirtualVReg();
553  if (FirstCandidate)
554  NVC.incrementVirtualVReg(LastRenameReg % 10);
555  FirstCandidate = false;
556  continue;
557  } else if (!TargetRegisterInfo::isVirtualRegister(vreg.getReg())) {
558  unsigned LastRenameReg = NVC.incrementVirtualVReg();
559  (void)LastRenameReg;
560  LLVM_DEBUG({
561  dbgs() << "Skipping rename for Phys Reg " << LastRenameReg << "\n";
562  });
563  continue;
564  }
565 
566  auto Reg = vreg.getReg();
567  if (llvm::find(renamedInOtherBB, Reg) != renamedInOtherBB.end()) {
568  LLVM_DEBUG(dbgs() << "Vreg " << Reg
569  << " already renamed in other BB.\n";);
570  continue;
571  }
572 
573  auto Rename = NVC.createVirtualRegister(Reg);
574 
575  if (VRegRenameMap.find(Reg) == VRegRenameMap.end()) {
576  LLVM_DEBUG(dbgs() << "Mapping vreg ";);
577  if (MRI.reg_begin(Reg) != MRI.reg_end()) {
578  LLVM_DEBUG(auto foo = &*MRI.reg_begin(Reg); foo->dump(););
579  } else {
580  LLVM_DEBUG(dbgs() << Reg;);
581  }
582  LLVM_DEBUG(dbgs() << " to ";);
583  if (MRI.reg_begin(Rename) != MRI.reg_end()) {
584  LLVM_DEBUG(auto foo = &*MRI.reg_begin(Rename); foo->dump(););
585  } else {
586  LLVM_DEBUG(dbgs() << Rename;);
587  }
588  LLVM_DEBUG(dbgs() << "\n";);
589 
590  VRegRenameMap.insert(std::pair<unsigned, unsigned>(Reg, Rename));
591  }
592  }
593 
594  return VRegRenameMap;
595 }
596 
597 static bool doVRegRenaming(std::vector<unsigned> &RenamedInOtherBB,
598  const std::map<unsigned, unsigned> &VRegRenameMap,
600  bool Changed = false;
601  for (auto I = VRegRenameMap.begin(), E = VRegRenameMap.end(); I != E; ++I) {
602 
603  auto VReg = I->first;
604  auto Rename = I->second;
605 
606  RenamedInOtherBB.push_back(Rename);
607 
608  std::vector<MachineOperand *> RenameMOs;
609  for (auto &MO : MRI.reg_operands(VReg)) {
610  RenameMOs.push_back(&MO);
611  }
612 
613  for (auto *MO : RenameMOs) {
614  Changed = true;
615  MO->setReg(Rename);
616 
617  if (!MO->isDef())
618  MO->setIsKill(false);
619  }
620  }
621 
622  return Changed;
623 }
624 
626  bool Changed = false;
627 
628  for (auto &MI : *MBB) {
629  for (auto &MO : MI.operands()) {
630  if (!MO.isReg())
631  continue;
632  if (!MO.isDef() && MO.isKill()) {
633  Changed = true;
634  MO.setIsKill(false);
635  }
636 
637  if (MO.isDef() && MO.isDead()) {
638  Changed = true;
639  MO.setIsDead(false);
640  }
641  }
642  }
643 
644  return Changed;
645 }
646 
648  std::vector<StringRef> &bbNames,
649  std::vector<unsigned> &renamedInOtherBB,
650  unsigned &basicBlockNum, unsigned &VRegGapIndex,
651  NamedVRegCursor &NVC) {
652 
653  if (CanonicalizeBasicBlockNumber != ~0U) {
654  if (CanonicalizeBasicBlockNumber != basicBlockNum++)
655  return false;
656  LLVM_DEBUG(dbgs() << "\n Canonicalizing BasicBlock " << MBB->getName()
657  << "\n";);
658  }
659 
660  if (llvm::find(bbNames, MBB->getName()) != bbNames.end()) {
661  LLVM_DEBUG({
662  dbgs() << "Found potentially duplicate BasicBlocks: " << MBB->getName()
663  << "\n";
664  });
665  return false;
666  }
667 
668  LLVM_DEBUG({
669  dbgs() << "\n\n NEW BASIC BLOCK: " << MBB->getName() << " \n\n";
670  dbgs() << "\n\n================================================\n\n";
671  });
672 
673  bool Changed = false;
674  MachineFunction &MF = *MBB->getParent();
676 
677  bbNames.push_back(MBB->getName());
678  LLVM_DEBUG(dbgs() << "\n\n NEW BASIC BLOCK: " << MBB->getName() << "\n\n";);
679 
680  LLVM_DEBUG(dbgs() << "MBB Before Canonical Copy Propagation:\n";
681  MBB->dump(););
682  Changed |= propagateLocalCopies(MBB);
683  LLVM_DEBUG(dbgs() << "MBB After Canonical Copy Propagation:\n"; MBB->dump(););
684 
685  LLVM_DEBUG(dbgs() << "MBB Before Scheduling:\n"; MBB->dump(););
686  unsigned IdempotentInstCount = 0;
687  Changed |= rescheduleCanonically(IdempotentInstCount, MBB);
688  LLVM_DEBUG(dbgs() << "MBB After Scheduling:\n"; MBB->dump(););
689 
690  std::vector<MachineInstr *> Candidates = populateCandidates(MBB);
691  std::vector<MachineInstr *> VisitedMIs;
692  llvm::copy(Candidates, std::back_inserter(VisitedMIs));
693 
694  std::vector<TypedVReg> VRegs;
695  for (auto candidate : Candidates) {
696  VRegs.push_back(TypedVReg(RSE_NewCandidate));
697 
698  std::queue<TypedVReg> RegQueue;
699 
700  // Here we walk the vreg operands of a non-root node along our walk.
701  // The root nodes are the original candidates (stores normally).
702  // These are normally not the root nodes (except for the case of copies to
703  // physical registers).
704  for (unsigned i = 1; i < candidate->getNumOperands(); i++) {
705  if (candidate->mayStore() || candidate->isBranch())
706  break;
707 
708  MachineOperand &MO = candidate->getOperand(i);
710  continue;
711 
712  LLVM_DEBUG(dbgs() << "Enqueue register"; MO.dump(); dbgs() << "\n";);
713  RegQueue.push(TypedVReg(MO.getReg()));
714  }
715 
716  // Here we walk the root candidates. We start from the 0th operand because
717  // the root is normally a store to a vreg.
718  for (unsigned i = 0; i < candidate->getNumOperands(); i++) {
719 
720  if (!candidate->mayStore() && !candidate->isBranch())
721  break;
722 
723  MachineOperand &MO = candidate->getOperand(i);
724 
725  // TODO: Do we want to only add vregs here?
726  if (!MO.isReg() && !MO.isFI())
727  continue;
728 
729  LLVM_DEBUG(dbgs() << "Enqueue Reg/FI"; MO.dump(); dbgs() << "\n";);
730 
731  RegQueue.push(MO.isReg() ? TypedVReg(MO.getReg())
733  }
734 
735  doCandidateWalk(VRegs, RegQueue, VisitedMIs, MBB);
736  }
737 
738  // If we have populated no vregs to rename then bail.
739  // The rest of this function does the vreg remaping.
740  if (VRegs.size() == 0)
741  return Changed;
742 
743  auto VRegRenameMap = GetVRegRenameMap(VRegs, renamedInOtherBB, MRI, NVC);
744  Changed |= doVRegRenaming(renamedInOtherBB, VRegRenameMap, MRI);
745 
746  // Here we renumber the def vregs for the idempotent instructions from the top
747  // of the MachineBasicBlock so that they are named in the order that we sorted
748  // them alphabetically. Eventually we wont need SkipVRegs because we will use
749  // named vregs instead.
750  if (IdempotentInstCount)
751  NVC.SkipVRegs();
752 
753  auto MII = MBB->begin();
754  for (unsigned i = 0; i < IdempotentInstCount && MII != MBB->end(); ++i) {
755  MachineInstr &MI = *MII++;
756  Changed = true;
757  unsigned vRegToRename = MI.getOperand(0).getReg();
758  auto Rename = NVC.createVirtualRegister(vRegToRename);
759 
760  std::vector<MachineOperand *> RenameMOs;
761  for (auto &MO : MRI.reg_operands(vRegToRename)) {
762  RenameMOs.push_back(&MO);
763  }
764 
765  for (auto *MO : RenameMOs) {
766  MO->setReg(Rename);
767  }
768  }
769 
770  Changed |= doDefKillClear(MBB);
771 
772  LLVM_DEBUG(dbgs() << "Updated MachineBasicBlock:\n"; MBB->dump();
773  dbgs() << "\n";);
774  LLVM_DEBUG(
775  dbgs() << "\n\n================================================\n\n");
776  return Changed;
777 }
778 
779 bool MIRCanonicalizer::runOnMachineFunction(MachineFunction &MF) {
780 
781  static unsigned functionNum = 0;
782  if (CanonicalizeFunctionNumber != ~0U) {
783  if (CanonicalizeFunctionNumber != functionNum++)
784  return false;
785  LLVM_DEBUG(dbgs() << "\n Canonicalizing Function " << MF.getName()
786  << "\n";);
787  }
788 
789  // we need a valid vreg to create a vreg type for skipping all those
790  // stray vreg numbers so reach alignment/canonical vreg values.
791  std::vector<MachineBasicBlock *> RPOList = GetRPOList(MF);
792 
793  LLVM_DEBUG(
794  dbgs() << "\n\n NEW MACHINE FUNCTION: " << MF.getName() << " \n\n";
795  dbgs() << "\n\n================================================\n\n";
796  dbgs() << "Total Basic Blocks: " << RPOList.size() << "\n";
797  for (auto MBB
798  : RPOList) { dbgs() << MBB->getName() << "\n"; } dbgs()
799  << "\n\n================================================\n\n";);
800 
801  std::vector<StringRef> BBNames;
802  std::vector<unsigned> RenamedInOtherBB;
803 
804  unsigned GapIdx = 0;
805  unsigned BBNum = 0;
806 
807  bool Changed = false;
808 
810  NamedVRegCursor NVC(MRI);
811  for (auto MBB : RPOList)
812  Changed |=
813  runOnBasicBlock(MBB, BBNames, RenamedInOtherBB, BBNum, GapIdx, NVC);
814 
815  return Changed;
816 }
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
LLT getType(unsigned Reg) const
Get the low-level type of Reg or LLT{} if Reg is not a generic (target independent) virtual register...
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:413
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:658
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:821
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:1199
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:1220
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:1213
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:1122
unsigned createGenericVirtualRegister(LLT Ty, StringRef Name="")
Create and return a new generic virtual register with low-level type Ty.
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:255
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
#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.
const TargetRegisterClass * getRegClassOrNull(unsigned Reg) const
Return the register class of Reg, or null if Reg has not been assigned a register class yet...
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:415
OutputIt copy(R &&Range, OutputIt Out)
Definition: STLExtras.h:1244
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)