LLVM  10.0.0svn
MIRVRegNamerUtils.cpp
Go to the documentation of this file.
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;
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,
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 
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 
347  return ::renameVRegs(MBB, RenamedInOtherBB, *this);
348 }
static bool isReg(const MCInst &MI, unsigned OpNo)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool renameVRegs(MachineBasicBlock *MBB)
renameVRegs - For a given MachineBasicBlock, scan for side-effecting instructions, walk the def-use from each side-effecting root (in sorted root order) and rename the encountered vregs in the def-use graph in a canonical ordering.
unsigned Reg
iterator_range< reg_iterator > reg_operands(unsigned Reg) const
unsigned createVirtualRegister(unsigned VReg)
createVirtualRegister - Given an existing vreg, create a named vreg to take its place.
static use_iterator use_end()
unsigned incrementVirtualVReg(unsigned incr=1)
incrementVirtualVReg - This increments an index value that us used to create a new vreg name...
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:413
def_iterator def_begin(unsigned RegNo) const
bool isBranch(QueryType Type=AnyInBundle) const
Returns true if this is a conditional, unconditional, or indirect branch.
Definition: MachineInstr.h:680
unsigned getVirtualVReg() const
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
Definition: MachineInstr.h:843
unsigned const MachineRegisterInfo * MRI
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void skipVRegs()
SkipGapSize - Skips modulo a gap value of indices.
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:1172
static wasm::ValType getType(const TargetRegisterClass *RC)
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:1186
std::string & str()
Flushes the stream contents to the target string and returns the string&#39;s reference.
Definition: raw_ostream.h:519
MachineOperand class - Representation of each machine instruction operand.
reg_iterator reg_begin(unsigned RegNo) const
NamedVRegCursor - The cursor is an object that keeps track of what the next vreg name should be...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static unsigned getReg(const void *D, unsigned RC, unsigned RegNo)
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.
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.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
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:503
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:69
IRTranslator LLVM IR MI
Register getReg() const
getReg - Returns the register number.
#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:1217
Wrapper class representing virtual and physical registers.
Definition: Register.h:19