lib/CodeGen/MIRVRegNamerUtils.cpp

   1 //===---------- MIRVRegNamerUtils.cpp - MIR VReg Renaming Utilities -------===//
   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 #include "MIRVRegNamerUtils.h"
  10
  11 using namespace llvm;
  12
  13 #define DEBUG_TYPE "mir-vregnamer-utils"
  14
  15 namespace {
  16
  17 // TypedVReg and VRType are used to tell the renamer what to do at points in a
  18 // sequence of values to be renamed. A TypedVReg can either contain
  19 // an actual VReg, a FrameIndex, or it could just be a barrier for the next
  20 // candidate (side-effecting instruction). This tells the renamer to increment
  21 // to the next vreg name, or to skip modulo some skip-gap value.
  22 enum VRType { RSE_Reg = 0, RSE_FrameIndex, RSE_NewCandidate };
  23 class TypedVReg {
  24   VRType Type;
  25   Register Reg;
  26
  27 public:
  28   TypedVReg(Register Reg) : Type(RSE_Reg), Reg(Reg) {}
  29   TypedVReg(VRType Type) : Type(Type), Reg(~0U) {
  30     assert(Type != RSE_Reg && "Expected a non-Register Type.");
  31   }
  32
  33   bool isReg() const { return Type == RSE_Reg; }
  34   bool isFrameIndex() const { return Type == RSE_FrameIndex; }
  35   bool isCandidate() const { return Type == RSE_NewCandidate; }
  36
  37   VRType getType() const { return Type; }
  38   Register getReg() const {
  39     assert(this->isReg() && "Expected a virtual or physical Register.");
  40     return Reg;
  41   }
  42 };
  43
  44 /// Here we find our candidates. What makes an interesting candidate?
  45 /// A candidate for a canonicalization tree root is normally any kind of
  46 /// instruction that causes side effects such as a store to memory or a copy to
  47 /// a physical register or a return instruction. We use these as an expression
  48 /// tree root that we walk in order to build a canonical walk which should
  49 /// result in canonical vreg renaming.
  50 std::vector<MachineInstr *> populateCandidates(MachineBasicBlock *MBB) {
  51   std::vector<MachineInstr *> Candidates;
  52   MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo();
  53
  54   for (auto II = MBB->begin(), IE = MBB->end(); II != IE; ++II) {
  55     MachineInstr *MI = &*II;
  56
  57     bool DoesMISideEffect = false;
  58
  59     if (MI->getNumOperands() > 0 && MI->getOperand(0).isReg()) {
  60       const Register Dst = MI->getOperand(0).getReg();
  61       DoesMISideEffect |= !Register::isVirtualRegister(Dst);
  62
  63       for (auto UI = MRI.use_begin(Dst); UI != MRI.use_end(); ++UI) {
  64         if (DoesMISideEffect)
  65           break;
  66         DoesMISideEffect |= (UI->getParent()->getParent() != MI->getParent());
  67       }
  68     }
  69
  70     if (!MI->mayStore() && !MI->isBranch() && !DoesMISideEffect)
  71       continue;
  72
  73     LLVM_DEBUG(dbgs() << "Found Candidate:  "; MI->dump(););
  74     Candidates.push_back(MI);
  75   }
  76
  77   return Candidates;
  78 }
  79
  80 void doCandidateWalk(std::vector<TypedVReg> &VRegs,
  81                      std::queue<TypedVReg> &RegQueue,
  82                      std::vector<MachineInstr *> &VisitedMIs,
  83                      const MachineBasicBlock *MBB) {
  84
  85   const MachineFunction &MF = *MBB->getParent();
  86   const MachineRegisterInfo &MRI = MF.getRegInfo();
  87
  88   while (!RegQueue.empty()) {
  89
  90     auto TReg = RegQueue.front();
  91     RegQueue.pop();
  92
  93     if (TReg.isFrameIndex()) {
  94       LLVM_DEBUG(dbgs() << "Popping frame index.\n";);
  95       VRegs.push_back(TypedVReg(RSE_FrameIndex));
  96       continue;
  97     }
  98
  99     assert(TReg.isReg() && "Expected vreg or physreg.");
 100     Register Reg = TReg.getReg();
 101
 102     if (Register::isVirtualRegister(Reg)) {
 103       LLVM_DEBUG({
 104         dbgs() << "Popping vreg ";
 105         MRI.def_begin(Reg)->dump();
 106         dbgs() << "\n";
 107       });
 108
 109       if (!llvm::any_of(VRegs, [&](const TypedVReg &TR) {
 110             return TR.isReg() && TR.getReg() == Reg;
 111           })) {
 112         VRegs.push_back(TypedVReg(Reg));
 113       }
 114     } else {
 115       LLVM_DEBUG(dbgs() << "Popping physreg.\n";);
 116       VRegs.push_back(TypedVReg(Reg));
 117       continue;
 118     }
 119
 120     for (auto RI = MRI.def_begin(Reg), RE = MRI.def_end(); RI != RE; ++RI) {
 121       MachineInstr *Def = RI->getParent();
 122
 123       if (Def->getParent() != MBB)
 124         continue;
 125
 126       if (llvm::any_of(VisitedMIs,
 127                        [&](const MachineInstr *VMI) { return Def == VMI; })) {
 128         break;
 129       }
 130
 131       LLVM_DEBUG({
 132         dbgs() << "\n========================\n";
 133         dbgs() << "Visited MI: ";
 134         Def->dump();
 135         dbgs() << "BB Name: " << Def->getParent()->getName() << "\n";
 136         dbgs() << "\n========================\n";
 137       });
 138       VisitedMIs.push_back(Def);
 139       for (unsigned I = 1, E = Def->getNumOperands(); I != E; ++I) {
 140
 141         MachineOperand &MO = Def->getOperand(I);
 142         if (MO.isFI()) {
 143           LLVM_DEBUG(dbgs() << "Pushing frame index.\n";);
 144           RegQueue.push(TypedVReg(RSE_FrameIndex));
 145         }
 146
 147         if (!MO.isReg())
 148           continue;
 149         RegQueue.push(TypedVReg(MO.getReg()));
 150       }
 151     }
 152   }
 153 }
 154
 155 std::map<unsigned, unsigned>
 156 getVRegRenameMap(const std::vector<TypedVReg> &VRegs,
 157                  const std::vector<Register> &renamedInOtherBB,
 158                  MachineRegisterInfo &MRI, NamedVRegCursor &NVC) {
 159   std::map<unsigned, unsigned> VRegRenameMap;
 160   bool FirstCandidate = true;
 161
 162   for (auto &vreg : VRegs) {
 163     if (vreg.isFrameIndex()) {
 164       // We skip one vreg for any frame index because there is a good chance
 165       // (especially when comparing SelectionDAG to GlobalISel generated MIR)
 166       // that in the other file we are just getting an incoming vreg that comes
 167       // from a copy from a frame index. So it's safe to skip by one.
 168       unsigned LastRenameReg = NVC.incrementVirtualVReg();
 169       (void)LastRenameReg;
 170       LLVM_DEBUG(dbgs() << "Skipping rename for FI " << LastRenameReg << "\n";);
 171       continue;
 172     } else if (vreg.isCandidate()) {
 173
 174       // After the first candidate, for every subsequent candidate, we skip mod
 175       // 10 registers so that the candidates are more likely to start at the
 176       // same vreg number making it more likely that the canonical walk from the
 177       // candidate insruction. We don't need to skip from the first candidate of
 178       // the BasicBlock because we already skip ahead several vregs for each BB.
 179       unsigned LastRenameReg = NVC.getVirtualVReg();
 180       if (FirstCandidate)
 181         NVC.incrementVirtualVReg(LastRenameReg % 10);
 182       FirstCandidate = false;
 183       continue;
 184     } else if (!Register::isVirtualRegister(vreg.getReg())) {
 185       unsigned LastRenameReg = NVC.incrementVirtualVReg();
 186       (void)LastRenameReg;
 187       LLVM_DEBUG({
 188         dbgs() << "Skipping rename for Phys Reg " << LastRenameReg << "\n";
 189       });
 190       continue;
 191     }
 192
 193     auto Reg = vreg.getReg();
 194     if (llvm::find(renamedInOtherBB, Reg) != renamedInOtherBB.end()) {
 195       LLVM_DEBUG(dbgs() << "Vreg " << Reg
 196                         << " already renamed in other BB.\n";);
 197       continue;
 198     }
 199
 200     auto Rename = NVC.createVirtualRegister(Reg);
 201
 202     if (VRegRenameMap.find(Reg) == VRegRenameMap.end()) {
 203       LLVM_DEBUG(dbgs() << "Mapping vreg ";);
 204       if (MRI.reg_begin(Reg) != MRI.reg_end()) {
 205         LLVM_DEBUG(auto foo = &*MRI.reg_begin(Reg); foo->dump(););
 206       } else {
 207         LLVM_DEBUG(dbgs() << Reg;);
 208       }
 209       LLVM_DEBUG(dbgs() << " to ";);
 210       if (MRI.reg_begin(Rename) != MRI.reg_end()) {
 211         LLVM_DEBUG(auto foo = &*MRI.reg_begin(Rename); foo->dump(););
 212       } else {
 213         LLVM_DEBUG(dbgs() << Rename;);
 214       }
 215       LLVM_DEBUG(dbgs() << "\n";);
 216
 217       VRegRenameMap.insert(std::pair<unsigned, unsigned>(Reg, Rename));
 218     }
 219   }
 220
 221   return VRegRenameMap;
 222 }
 223
 224 bool doVRegRenaming(std::vector<Register> &renamedInOtherBB,
 225                     const std::map<unsigned, unsigned> &VRegRenameMap,
 226                     MachineRegisterInfo &MRI) {
 227   bool Changed = false;
 228   for (auto I = VRegRenameMap.begin(), E = VRegRenameMap.end(); I != E; ++I) {
 229
 230     auto VReg = I->first;
 231     auto Rename = I->second;
 232
 233     renamedInOtherBB.push_back(Rename);
 234
 235     std::vector<MachineOperand *> RenameMOs;
 236     for (auto &MO : MRI.reg_operands(VReg)) {
 237       RenameMOs.push_back(&MO);
 238     }
 239
 240     for (auto *MO : RenameMOs) {
 241       Changed = true;
 242       MO->setReg(Rename);
 243
 244       if (!MO->isDef())
 245         MO->setIsKill(false);
 246     }
 247   }
 248
 249   return Changed;
 250 }
 251
 252 bool renameVRegs(MachineBasicBlock *MBB,
 253                  std::vector<Register> &renamedInOtherBB,
 254                  NamedVRegCursor &NVC) {
 255   bool Changed = false;
 256   MachineFunction &MF = *MBB->getParent();
 257   MachineRegisterInfo &MRI = MF.getRegInfo();
 258
 259   std::vector<MachineInstr *> Candidates = populateCandidates(MBB);
 260   std::vector<MachineInstr *> VisitedMIs;
 261   llvm::copy(Candidates, std::back_inserter(VisitedMIs));
 262
 263   std::vector<TypedVReg> VRegs;
 264   for (auto candidate : Candidates) {
 265     VRegs.push_back(TypedVReg(RSE_NewCandidate));
 266
 267     std::queue<TypedVReg> RegQueue;
 268
 269     // Here we walk the vreg operands of a non-root node along our walk.
 270     // The root nodes are the original candidates (stores normally).
 271     // These are normally not the root nodes (except for the case of copies to
 272     // physical registers).
 273     for (unsigned i = 1; i < candidate->getNumOperands(); i++) {
 274       if (candidate->mayStore() || candidate->isBranch())
 275         break;
 276
 277       MachineOperand &MO = candidate->getOperand(i);
 278       if (!(MO.isReg() && Register::isVirtualRegister(MO.getReg())))
 279         continue;
 280
 281       LLVM_DEBUG(dbgs() << "Enqueue register"; MO.dump(); dbgs() << "\n";);
 282       RegQueue.push(TypedVReg(MO.getReg()));
 283     }
 284
 285     // Here we walk the root candidates. We start from the 0th operand because
 286     // the root is normally a store to a vreg.
 287     for (unsigned i = 0; i < candidate->getNumOperands(); i++) {
 288
 289       if (!candidate->mayStore() && !candidate->isBranch())
 290         break;
 291
 292       MachineOperand &MO = candidate->getOperand(i);
 293
 294       // TODO: Do we want to only add vregs here?
 295       if (!MO.isReg() && !MO.isFI())
 296         continue;
 297
 298       LLVM_DEBUG(dbgs() << "Enqueue Reg/FI"; MO.dump(); dbgs() << "\n";);
 299
 300       RegQueue.push(MO.isReg() ? TypedVReg(MO.getReg())
 301                                : TypedVReg(RSE_FrameIndex));
 302     }
 303
 304     doCandidateWalk(VRegs, RegQueue, VisitedMIs, MBB);
 305   }
 306
 307   // If we have populated no vregs to rename then bail.
 308   // The rest of this function does the vreg remaping.
 309   if (VRegs.size() == 0)
 310     return Changed;
 311
 312   auto VRegRenameMap = getVRegRenameMap(VRegs, renamedInOtherBB, MRI, NVC);
 313   Changed |= doVRegRenaming(renamedInOtherBB, VRegRenameMap, MRI);
 314   return Changed;
 315 }
 316 } // anonymous namespace
 317
 318 void NamedVRegCursor::skipVRegs() {
 319   unsigned VRegGapIndex = 1;
 320   if (!virtualVRegNumber) {
 321     VRegGapIndex = 0;
 322     virtualVRegNumber = MRI.createIncompleteVirtualRegister();
 323   }
 324   const unsigned VR_GAP = (++VRegGapIndex * SkipGapSize);
 325
 326   unsigned I = virtualVRegNumber;
 327   const unsigned E = (((I + VR_GAP) / VR_GAP) + 1) * VR_GAP;
 328
 329   virtualVRegNumber = E;
 330 }
 331
 332 unsigned NamedVRegCursor::createVirtualRegister(unsigned VReg) {
 333   if (!virtualVRegNumber)
 334     skipVRegs();
 335   std::string S;
 336   raw_string_ostream OS(S);
 337   OS << "namedVReg" << (virtualVRegNumber & ~0x80000000);
 338   OS.flush();
 339   virtualVRegNumber++;
 340   if (auto RC = MRI.getRegClassOrNull(VReg))
 341     return MRI.createVirtualRegister(RC, OS.str());
 342   return MRI.createGenericVirtualRegister(MRI.getType(VReg), OS.str());
 343 }
 344
 345 bool NamedVRegCursor::renameVRegs(MachineBasicBlock *MBB) {
 346   return ::renameVRegs(MBB, RenamedInOtherBB, *this);
 347 }