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 }
348