LCOV - code coverage report
Current view: top level - lib/CodeGen - MIRCanonicalizerPass.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 258 270 95.6 %
Date: 2018-07-13 00:08:38 Functions: 21 22 95.5 %
Legend: Lines: hit not hit

          Line data    Source code
       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             : 
      27             : #include "llvm/ADT/PostOrderIterator.h"
      28             : #include "llvm/ADT/STLExtras.h"
      29             : #include "llvm/CodeGen/MachineFunctionPass.h"
      30             : #include "llvm/CodeGen/MachineInstrBuilder.h"
      31             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      32             : #include "llvm/CodeGen/Passes.h"
      33             : #include "llvm/Support/raw_ostream.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      299229 :     CanonicalizeFunctionNumber("canon-nth-function", cl::Hidden, cl::init(~0u),
      47       99743 :                                cl::value_desc("N"),
      48      199486 :                                cl::desc("Function number to canonicalize."));
      49             : 
      50       99743 : static cl::opt<unsigned> CanonicalizeBasicBlockNumber(
      51      199486 :     "canon-nth-basicblock", cl::Hidden, cl::init(~0u), cl::value_desc("N"),
      52      199486 :     cl::desc("BasicBlock number to canonicalize."));
      53             : 
      54             : namespace {
      55             : 
      56           3 : class MIRCanonicalizer : public MachineFunctionPass {
      57             : public:
      58             :   static char ID;
      59           3 :   MIRCanonicalizer() : MachineFunctionPass(ID) {}
      60             : 
      61           3 :   StringRef getPassName() const override {
      62           3 :     return "Rename register operands in a canonical ordering.";
      63             :   }
      64             : 
      65           3 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
      66           3 :     AU.setPreservesCFG();
      67           3 :     MachineFunctionPass::getAnalysisUsage(AU);
      68           3 :   }
      69             : 
      70             :   bool runOnMachineFunction(MachineFunction &MF) override;
      71             : };
      72             : 
      73             : } // end anonymous namespace
      74             : 
      75             : enum VRType { RSE_Reg = 0, RSE_FrameIndex, RSE_NewCandidate };
      76             : class TypedVReg {
      77             :   VRType type;
      78             :   unsigned reg;
      79             : 
      80             : public:
      81         142 :   TypedVReg(unsigned reg) : type(RSE_Reg), reg(reg) {}
      82          59 :   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             : 
      97             : char MIRCanonicalizer::ID;
      98             : 
      99             : char &llvm::MIRCanonicalizerID = MIRCanonicalizer::ID;
     100             : 
     101       26316 : INITIALIZE_PASS_BEGIN(MIRCanonicalizer, "mir-canonicalizer",
     102             :                       "Rename Register Operands Canonically", false, false)
     103             : 
     104      146610 : INITIALIZE_PASS_END(MIRCanonicalizer, "mir-canonicalizer",
     105             :                     "Rename Register Operands Canonically", false, false)
     106             : 
     107           3 : static std::vector<MachineBasicBlock *> GetRPOList(MachineFunction &MF) {
     108             :   ReversePostOrderTraversal<MachineBasicBlock *> RPOT(&*MF.begin());
     109             :   std::vector<MachineBasicBlock *> RPOList;
     110           6 :   for (auto MBB : RPOT) {
     111           3 :     RPOList.push_back(MBB);
     112             :   }
     113             : 
     114           3 :   return RPOList;
     115             : }
     116             : 
     117             : static bool
     118          23 : rescheduleLexographically(std::vector<MachineInstr *> instructions,
     119             :                           MachineBasicBlock *MBB,
     120             :                           std::function<MachineBasicBlock::iterator()> getPos) {
     121             : 
     122             :   bool Changed = false;
     123             :   using StringInstrPair = std::pair<std::string, MachineInstr *>;
     124          23 :   std::vector<StringInstrPair> StringInstrMap;
     125             : 
     126          60 :   for (auto *II : instructions) {
     127             :     std::string S;
     128          37 :     raw_string_ostream OS(S);
     129          37 :     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         148 :     StringInstrMap.push_back({(i == std::string::npos) ? S : S.substr(i), II});
     135             :   }
     136             : 
     137             :   std::sort(StringInstrMap.begin(), StringInstrMap.end(),
     138             :             [](const StringInstrPair &a, const StringInstrPair &b) -> bool {
     139          29 :               return (a.first < b.first);
     140             :             });
     141             : 
     142          60 :   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          74 :     MBB->splice(getPos(), MBB, II.second);
     153             :   }
     154             : 
     155          23 :   return Changed;
     156             : }
     157             : 
     158           3 : 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          62 :   auto getInstrIdx = [](const MachineInstr &MI) {
     165             :     unsigned i = 0;
     166        1915 :     for (auto &CurMI : *MI.getParent()) {
     167        1791 :       if (&CurMI == &MI)
     168          62 :         return i;
     169        1729 :       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          84 :   for (auto &MI : *MBB) {
     178         150 :     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          78 :   for (auto *II : Instructions) {
     185         387 :     for (unsigned i = 1; i < II->getNumOperands(); i++) {
     186         156 :       MachineOperand &MO = II->getOperand(i);
     187         156 :       if (!MO.isReg())
     188          90 :         continue;
     189             : 
     190         132 :       if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
     191          59 :         continue;
     192             : 
     193           7 :       if (!MO.isDef())
     194           7 :         continue;
     195             : 
     196           0 :       PhysRegDefs.push_back(MO.getReg());
     197             :     }
     198             :   }
     199             : 
     200          78 :   for (auto *II : Instructions) {
     201          75 :     if (II->getNumOperands() == 0)
     202          53 :       continue;
     203          74 :     if (II->mayLoadOrStore())
     204          33 :       continue;
     205             : 
     206          41 :     MachineOperand &MO = II->getOperand(0);
     207          82 :     if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
     208           4 :       continue;
     209          37 :     if (!MO.isDef())
     210           0 :       continue;
     211             : 
     212             :     bool IsPseudoIdempotent = true;
     213          63 :     for (unsigned i = 1; i < II->getNumOperands(); i++) {
     214             : 
     215          72 :       if (II->getOperand(i).isImm()) {
     216           7 :         continue;
     217             :       }
     218             : 
     219          29 :       if (II->getOperand(i).isReg()) {
     220          58 :         if (!TargetRegisterInfo::isVirtualRegister(II->getOperand(i).getReg()))
     221          12 :           if (llvm::find(PhysRegDefs, II->getOperand(i).getReg()) ==
     222             :               PhysRegDefs.end()) {
     223           6 :             continue;
     224             :           }
     225             :       }
     226             : 
     227             :       IsPseudoIdempotent = false;
     228             :       break;
     229             :     }
     230             : 
     231          14 :     if (IsPseudoIdempotent) {
     232          14 :       PseudoIdempotentInstructions.push_back(II);
     233          14 :       continue;
     234             :     }
     235             : 
     236             :     LLVM_DEBUG(dbgs() << "Operand " << 0 << " of "; II->dump(); MO.dump(););
     237             : 
     238          23 :     MachineInstr *Def = II;
     239             :     unsigned Distance = ~0U;
     240          23 :     MachineInstr *UseToBringDefCloserTo = nullptr;
     241          23 :     MachineRegisterInfo *MRI = &MBB->getParent()->getRegInfo();
     242          77 :     for (auto &UO : MRI->use_nodbg_operands(MO.getReg())) {
     243          31 :       MachineInstr *UseInst = UO.getParent();
     244             : 
     245          31 :       const unsigned DefLoc = getInstrIdx(*Def);
     246          31 :       const unsigned UseLoc = getInstrIdx(*UseInst);
     247          31 :       const unsigned Delta = (UseLoc - DefLoc);
     248             : 
     249          31 :       if (UseInst->getParent() != Def->getParent())
     250           0 :         continue;
     251          31 :       if (DefLoc >= UseLoc)
     252           0 :         continue;
     253             : 
     254          31 :       if (Delta < Distance) {
     255             :         Distance = Delta;
     256          23 :         UseToBringDefCloserTo = UseInst;
     257             :       }
     258             :     }
     259             : 
     260          23 :     const auto BBE = MBB->instr_end();
     261             :     MachineBasicBlock::iterator DefI = BBE;
     262             :     MachineBasicBlock::iterator UseI = BBE;
     263             : 
     264         708 :     for (auto BBI = MBB->instr_begin(); BBI != BBE; ++BBI) {
     265             : 
     266         708 :       if (DefI != BBE && UseI != BBE)
     267             :         break;
     268             : 
     269         685 :       if (&*BBI == Def) {
     270             :         DefI = BBI;
     271          23 :         continue;
     272             :       }
     273             : 
     274         662 :       if (&*BBI == UseToBringDefCloserTo) {
     275             :         UseI = BBI;
     276          23 :         continue;
     277             :       }
     278             :     }
     279             : 
     280          23 :     if (DefI == BBE || UseI == BBE)
     281           0 :       continue;
     282             : 
     283             :     LLVM_DEBUG({
     284             :       dbgs() << "Splicing ";
     285             :       DefI->dump();
     286             :       dbgs() << " right before: ";
     287             :       UseI->dump();
     288             :     });
     289             : 
     290          23 :     MultiUsers[UseToBringDefCloserTo].push_back(Def);
     291             :     Changed = true;
     292          23 :     MBB->splice(UseI, MBB, DefI);
     293             :   }
     294             : 
     295             :   // Sort the defs for users of multiple defs lexographically.
     296          23 :   for (const auto &E : MultiUsers) {
     297             : 
     298             :     auto UseI =
     299             :         std::find_if(MBB->instr_begin(), MBB->instr_end(),
     300         674 :                      [&](MachineInstr &MI) -> bool { return &MI == E.first; });
     301             : 
     302          20 :     if (UseI == MBB->instr_end())
     303           0 :       continue;
     304             : 
     305             :     LLVM_DEBUG(
     306             :         dbgs() << "Rescheduling Multi-Use Instructions Lexographically.";);
     307          60 :     Changed |= rescheduleLexographically(
     308          23 :         E.second, MBB, [&]() -> MachineBasicBlock::iterator { return UseI; });
     309             :   }
     310             : 
     311           6 :   PseudoIdempotentInstCount = PseudoIdempotentInstructions.size();
     312             :   LLVM_DEBUG(
     313             :       dbgs() << "Rescheduling Idempotent Instructions Lexographically.";);
     314           9 :   Changed |= rescheduleLexographically(
     315             :       PseudoIdempotentInstructions, MBB,
     316          14 :       [&]() -> MachineBasicBlock::iterator { return MBB->begin(); });
     317             : 
     318           3 :   return Changed;
     319             : }
     320             : 
     321           3 : static bool propagateLocalCopies(MachineBasicBlock *MBB) {
     322             :   bool Changed = false;
     323           3 :   MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo();
     324             : 
     325             :   std::vector<MachineInstr *> Copies;
     326          82 :   for (MachineInstr &MI : MBB->instrs()) {
     327          79 :     if (MI.isCopy())
     328          30 :       Copies.push_back(&MI);
     329             :   }
     330             : 
     331          18 :   for (MachineInstr *MI : Copies) {
     332             : 
     333          30 :     if (!MI->getOperand(0).isReg())
     334           0 :       continue;
     335          15 :     if (!MI->getOperand(1).isReg())
     336           0 :       continue;
     337             : 
     338          15 :     const unsigned Dst = MI->getOperand(0).getReg();
     339          15 :     const unsigned Src = MI->getOperand(1).getReg();
     340             : 
     341          15 :     if (!TargetRegisterInfo::isVirtualRegister(Dst))
     342           2 :       continue;
     343          13 :     if (!TargetRegisterInfo::isVirtualRegister(Src))
     344           6 :       continue;
     345           7 :     if (MRI.getRegClass(Dst) != MRI.getRegClass(Src))
     346           3 :       continue;
     347             : 
     348           4 :     for (auto UI = MRI.use_begin(Dst); UI != MRI.use_end(); ++UI) {
     349             :       MachineOperand *MO = &*UI;
     350           4 :       MO->setReg(Src);
     351             :       Changed = true;
     352             :     }
     353             : 
     354           4 :     MI->eraseFromParent();
     355             :   }
     356             : 
     357           3 :   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           3 : static std::vector<MachineInstr *> populateCandidates(MachineBasicBlock *MBB) {
     367             :   std::vector<MachineInstr *> Candidates;
     368           3 :   MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo();
     369             : 
     370          81 :   for (auto II = MBB->begin(), IE = MBB->end(); II != IE; ++II) {
     371          75 :     MachineInstr *MI = &*II;
     372             : 
     373             :     bool DoesMISideEffect = false;
     374             : 
     375         149 :     if (MI->getNumOperands() > 0 && MI->getOperand(0).isReg()) {
     376          74 :       const unsigned Dst = MI->getOperand(0).getReg();
     377          74 :       DoesMISideEffect |= !TargetRegisterInfo::isVirtualRegister(Dst);
     378             : 
     379          74 :       for (auto UI = MRI.use_begin(Dst); UI != MRI.use_end(); ++UI) {
     380          97 :         if (DoesMISideEffect)
     381             :           break;
     382          93 :         DoesMISideEffect |= (UI->getParent()->getParent() != MI->getParent());
     383             :       }
     384             :     }
     385             : 
     386         195 :     if (!MI->mayStore() && !MI->isBranch() && !DoesMISideEffect)
     387          58 :       continue;
     388             : 
     389             :     LLVM_DEBUG(dbgs() << "Found Candidate:  "; MI->dump(););
     390          17 :     Candidates.push_back(MI);
     391             :   }
     392             : 
     393           3 :   return Candidates;
     394             : }
     395             : 
     396          17 : static void doCandidateWalk(std::vector<TypedVReg> &VRegs,
     397             :                             std::queue<TypedVReg> &RegQueue,
     398             :                             std::vector<MachineInstr *> &VisitedMIs,
     399             :                             const MachineBasicBlock *MBB) {
     400             : 
     401          17 :   const MachineFunction &MF = *MBB->getParent();
     402          17 :   const MachineRegisterInfo &MRI = MF.getRegInfo();
     403             : 
     404         117 :   while (!RegQueue.empty()) {
     405             : 
     406         100 :     auto TReg = RegQueue.front();
     407             :     RegQueue.pop();
     408             : 
     409         121 :     if (TReg.isFrameIndex()) {
     410             :       LLVM_DEBUG(dbgs() << "Popping frame index.\n";);
     411          21 :       VRegs.push_back(TypedVReg(RSE_FrameIndex));
     412          49 :       continue;
     413             :     }
     414             : 
     415             :     assert(TReg.isReg() && "Expected vreg or physreg.");
     416          79 :     unsigned Reg = TReg.getReg();
     417             : 
     418          86 :     if (TargetRegisterInfo::isVirtualRegister(Reg)) {
     419             :       LLVM_DEBUG({
     420             :         dbgs() << "Popping vreg ";
     421             :         MRI.def_begin(Reg)->dump();
     422             :         dbgs() << "\n";
     423             :       });
     424             : 
     425          72 :       if (!llvm::any_of(VRegs, [&](const TypedVReg &TR) {
     426        2575 :             return TR.isReg() && TR.getReg() == Reg;
     427             :           })) {
     428         112 :         VRegs.push_back(TypedVReg(Reg));
     429             :       }
     430             :     } else {
     431             :       LLVM_DEBUG(dbgs() << "Popping physreg.\n";);
     432           7 :       VRegs.push_back(TypedVReg(Reg));
     433           7 :       continue;
     434             :     }
     435             : 
     436          72 :     for (auto RI = MRI.def_begin(Reg), RE = MRI.def_end(); RI != RE; ++RI) {
     437          71 :       MachineInstr *Def = RI->getParent();
     438             : 
     439          71 :       if (Def->getParent() != MBB)
     440           0 :         continue;
     441             : 
     442          71 :       if (llvm::any_of(VisitedMIs,
     443         582 :                        [&](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          55 :       VisitedMIs.push_back(Def);
     455         165 :       for (unsigned I = 1, E = Def->getNumOperands(); I != E; ++I) {
     456             : 
     457         110 :         MachineOperand &MO = Def->getOperand(I);
     458         110 :         if (MO.isFI()) {
     459             :           LLVM_DEBUG(dbgs() << "Pushing frame index.\n";);
     460          15 :           RegQueue.push(TypedVReg(RSE_FrameIndex));
     461             :         }
     462             : 
     463         110 :         if (!MO.isReg())
     464          60 :           continue;
     465         100 :         RegQueue.push(TypedVReg(MO.getReg()));
     466             :       }
     467             :     }
     468             :   }
     469          17 : }
     470             : 
     471             : namespace {
     472             : class NamedVRegCursor {
     473             :   MachineRegisterInfo &MRI;
     474             :   unsigned virtualVRegNumber;
     475             : 
     476             : public:
     477           3 :   NamedVRegCursor(MachineRegisterInfo &MRI) : MRI(MRI) {
     478             :     unsigned VRegGapIndex = 0;
     479             :     const unsigned VR_GAP = (++VRegGapIndex * 1000);
     480             : 
     481           3 :     unsigned I = MRI.createIncompleteVirtualRegister();
     482           3 :     const unsigned E = (((I + VR_GAP) / VR_GAP) + 1) * VR_GAP;
     483             : 
     484           3 :     virtualVRegNumber = E;
     485           3 :   }
     486             : 
     487             :   void SkipVRegs() {
     488             :     unsigned VRegGapIndex = 1;
     489             :     const unsigned VR_GAP = (++VRegGapIndex * 1000);
     490             : 
     491           3 :     unsigned I = virtualVRegNumber;
     492           3 :     const unsigned E = (((I + VR_GAP) / VR_GAP) + 1) * VR_GAP;
     493             : 
     494           3 :     virtualVRegNumber = E;
     495             :   }
     496             : 
     497             :   unsigned getVirtualVReg() const { return virtualVRegNumber; }
     498             : 
     499             :   unsigned incrementVirtualVReg(unsigned incr = 1) {
     500          31 :     virtualVRegNumber += incr;
     501             :     return virtualVRegNumber;
     502             :   }
     503             : 
     504          70 :   unsigned createVirtualRegister(const TargetRegisterClass *RC) {
     505             :     std::string S;
     506          70 :     raw_string_ostream OS(S);
     507          70 :     OS << "namedVReg" << (virtualVRegNumber & ~0x80000000);
     508             :     OS.flush();
     509          70 :     virtualVRegNumber++;
     510             : 
     511         210 :     return MRI.createVirtualRegister(RC, OS.str());
     512             :   }
     513             : };
     514             : } // namespace
     515             : 
     516             : static std::map<unsigned, unsigned>
     517           3 : 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           3 :   for (auto &vreg : VRegs) {
     524         101 :     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          66 :       continue;
     533          80 :     } 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          17 :       unsigned LastRenameReg = NVC.getVirtualVReg();
     541          17 :       if (FirstCandidate)
     542           3 :         NVC.incrementVirtualVReg(LastRenameReg % 10);
     543             :       FirstCandidate = false;
     544          17 :       continue;
     545         126 :     } 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           7 :       continue;
     552             :     }
     553             : 
     554          56 :     auto Reg = vreg.getReg();
     555         112 :     if (llvm::find(renamedInOtherBB, Reg) != renamedInOtherBB.end()) {
     556             :       LLVM_DEBUG(dbgs() << "Vreg " << Reg
     557             :                         << " already renamed in other BB.\n";);
     558           0 :       continue;
     559             :     }
     560             : 
     561         112 :     auto Rename = NVC.createVirtualRegister(MRI.getRegClass(Reg));
     562             : 
     563          56 :     if (VRegRenameMap.find(Reg) == VRegRenameMap.end()) {
     564             :       LLVM_DEBUG(dbgs() << "Mapping vreg ";);
     565          56 :       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          56 :       VRegRenameMap.insert(std::pair<unsigned, unsigned>(Reg, Rename));
     579             :     }
     580             :   }
     581             : 
     582           3 :   return VRegRenameMap;
     583             : }
     584             : 
     585           3 : static bool doVRegRenaming(std::vector<unsigned> &RenamedInOtherBB,
     586             :                            const std::map<unsigned, unsigned> &VRegRenameMap,
     587             :                            MachineRegisterInfo &MRI) {
     588             :   bool Changed = false;
     589          59 :   for (auto I = VRegRenameMap.begin(), E = VRegRenameMap.end(); I != E; ++I) {
     590             : 
     591          56 :     auto VReg = I->first;
     592          56 :     auto Rename = I->second;
     593             : 
     594          56 :     RenamedInOtherBB.push_back(Rename);
     595             : 
     596             :     std::vector<MachineOperand *> RenameMOs;
     597         183 :     for (auto &MO : MRI.reg_operands(VReg)) {
     598         254 :       RenameMOs.push_back(&MO);
     599             :     }
     600             : 
     601         183 :     for (auto *MO : RenameMOs) {
     602             :       Changed = true;
     603         127 :       MO->setReg(Rename);
     604             : 
     605         127 :       if (!MO->isDef())
     606             :         MO->setIsKill(false);
     607             :     }
     608             :   }
     609             : 
     610           3 :   return Changed;
     611             : }
     612             : 
     613           3 : static bool doDefKillClear(MachineBasicBlock *MBB) {
     614             :   bool Changed = false;
     615             : 
     616          81 :   for (auto &MI : *MBB) {
     617         535 :     for (auto &MO : MI.operands()) {
     618         230 :       if (!MO.isReg())
     619          90 :         continue;
     620         221 :       if (!MO.isDef() && MO.isKill()) {
     621             :         Changed = true;
     622             :         MO.setIsKill(false);
     623             :       }
     624             : 
     625         199 :       if (MO.isDef() && MO.isDead()) {
     626             :         Changed = true;
     627             :         MO.setIsDead(false);
     628             :       }
     629             :     }
     630             :   }
     631             : 
     632           3 :   return Changed;
     633             : }
     634             : 
     635           3 : static bool runOnBasicBlock(MachineBasicBlock *MBB,
     636             :                             std::vector<StringRef> &bbNames,
     637             :                             std::vector<unsigned> &renamedInOtherBB,
     638             :                             unsigned &basicBlockNum, unsigned &VRegGapIndex,
     639             :                             NamedVRegCursor &NVC) {
     640             : 
     641           3 :   if (CanonicalizeBasicBlockNumber != ~0U) {
     642           0 :     if (CanonicalizeBasicBlockNumber != basicBlockNum++)
     643             :       return false;
     644             :     LLVM_DEBUG(dbgs() << "\n Canonicalizing BasicBlock " << MBB->getName()
     645             :                       << "\n";);
     646             :   }
     647             : 
     648           6 :   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           3 :   MachineFunction &MF = *MBB->getParent();
     663           3 :   MachineRegisterInfo &MRI = MF.getRegInfo();
     664             : 
     665           6 :   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           3 :   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           3 :   unsigned IdempotentInstCount = 0;
     675           3 :   Changed |= rescheduleCanonically(IdempotentInstCount, MBB);
     676             :   LLVM_DEBUG(dbgs() << "MBB After Scheduling:\n"; MBB->dump(););
     677             : 
     678           3 :   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          20 :   for (auto candidate : Candidates) {
     685          17 :     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          21 :     for (unsigned i = 1; i < candidate->getNumOperands(); i++) {
     694          17 :       if (candidate->mayStore() || candidate->isBranch())
     695             :         break;
     696             : 
     697           2 :       MachineOperand &MO = candidate->getOperand(i);
     698           4 :       if (!(MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg())))
     699             :         continue;
     700             : 
     701             :       LLVM_DEBUG(dbgs() << "Enqueue register"; MO.dump(); dbgs() << "\n";);
     702           2 :       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         127 :     for (unsigned i = 0; i < candidate->getNumOperands(); i++) {
     708             : 
     709          63 :       if (!candidate->mayStore() && !candidate->isBranch())
     710             :         break;
     711             : 
     712          55 :       MachineOperand &MO = candidate->getOperand(i);
     713             : 
     714             :       // TODO: Do we want to only add vregs here?
     715          77 :       if (!MO.isReg() && !MO.isFI())
     716             :         continue;
     717             : 
     718             :       LLVM_DEBUG(dbgs() << "Enqueue Reg/FI"; MO.dump(); dbgs() << "\n";);
     719             : 
     720          93 :       RegQueue.push(MO.isReg() ? TypedVReg(MO.getReg())
     721             :                                : TypedVReg(RSE_FrameIndex));
     722             :     }
     723             : 
     724          17 :     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           6 :   if (VRegs.size() == 0)
     730             :     return Changed;
     731             : 
     732           3 :   auto VRegRenameMap = GetVRegRenameMap(VRegs, renamedInOtherBB, MRI, NVC);
     733           3 :   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           3 :   auto MII = MBB->begin();
     742          45 :   for (unsigned i = 0; i < IdempotentInstCount && MII != MBB->end(); ++i) {
     743             :     MachineInstr &MI = *MII++;
     744             :     Changed = true;
     745          14 :     unsigned vRegToRename = MI.getOperand(0).getReg();
     746          14 :     auto Rename = NVC.createVirtualRegister(MRI.getRegClass(vRegToRename));
     747             : 
     748             :     std::vector<MachineOperand *> RenameMOs;
     749          45 :     for (auto &MO : MRI.reg_operands(vRegToRename)) {
     750          62 :       RenameMOs.push_back(&MO);
     751             :     }
     752             : 
     753          45 :     for (auto *MO : RenameMOs) {
     754          31 :       MO->setReg(Rename);
     755             :     }
     756             :   }
     757             : 
     758           3 :   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           3 : bool MIRCanonicalizer::runOnMachineFunction(MachineFunction &MF) {
     768             : 
     769             :   static unsigned functionNum = 0;
     770           3 :   if (CanonicalizeFunctionNumber != ~0U) {
     771           0 :     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           3 :   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           3 :   unsigned BBNum = 0;
     794             : 
     795             :   bool Changed = false;
     796             : 
     797           3 :   MachineRegisterInfo &MRI = MF.getRegInfo();
     798           3 :   NamedVRegCursor NVC(MRI);
     799           6 :   for (auto MBB : RPOList)
     800           3 :     Changed |=
     801           3 :         runOnBasicBlock(MBB, BBNames, RenamedInOtherBB, BBNum, GapIdx, NVC);
     802             : 
     803             :   return Changed;
     804      299229 : }

Generated by: LCOV version 1.13