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