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 : CanonicalizeFunctionNumber("canon-nth-function", cl::Hidden, cl::init(~0u),
47 : cl::value_desc("N"),
48 : cl::desc("Function number to canonicalize."));
49 :
50 : static cl::opt<unsigned> CanonicalizeBasicBlockNumber(
51 : "canon-nth-basicblock", cl::Hidden, cl::init(~0u), cl::value_desc("N"),
52 : cl::desc("BasicBlock number to canonicalize."));
53 :
54 : namespace {
55 :
56 : 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 7 : TypedVReg(unsigned reg) : type(RSE_Reg), reg(reg) {}
82 36 : TypedVReg(VRType type) : type(type), reg(~0U) {
83 : assert(type != RSE_Reg && "Expected a non-register type.");
84 : }
85 :
86 0 : bool isReg() const { return type == RSE_Reg; }
87 0 : bool isFrameIndex() const { return type == RSE_FrameIndex; }
88 0 : bool isCandidate() const { return type == RSE_NewCandidate; }
89 :
90 : VRType getType() const { return type; }
91 0 : unsigned getReg() const {
92 : assert(this->isReg() && "Expected a virtual or physical register.");
93 0 : return reg;
94 : }
95 : };
96 :
97 : char MIRCanonicalizer::ID;
98 :
99 : char &llvm::MIRCanonicalizerID = MIRCanonicalizer::ID;
100 :
101 31780 : INITIALIZE_PASS_BEGIN(MIRCanonicalizer, "mir-canonicalizer",
102 : "Rename Register Operands Canonically", false, false)
103 :
104 85147 : 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 74 : StringInstrMap.push_back({(i == std::string::npos) ? S : S.substr(i), II});
135 : }
136 :
137 : llvm::sort(StringInstrMap,
138 : [](const StringInstrPair &a, const StringInstrPair &b) -> bool {
139 0 : 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 : auto getInstrIdx = [](const MachineInstr &MI) {
165 : unsigned i = 0;
166 : for (auto &CurMI : *MI.getParent()) {
167 : if (&CurMI == &MI)
168 : return i;
169 : 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 78 : for (auto &MI : *MBB) {
178 75 : 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 231 : for (unsigned i = 1; i < II->getNumOperands(); i++) {
186 156 : MachineOperand &MO = II->getOperand(i);
187 156 : if (!MO.isReg())
188 : continue;
189 :
190 132 : if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
191 : continue;
192 :
193 7 : if (!MO.isDef())
194 : 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 52 : continue;
203 74 : if (II->mayLoadOrStore())
204 : continue;
205 :
206 41 : MachineOperand &MO = II->getOperand(0);
207 41 : if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
208 : continue;
209 37 : if (!MO.isDef())
210 : continue;
211 :
212 : bool IsPseudoIdempotent = true;
213 50 : for (unsigned i = 1; i < II->getNumOperands(); i++) {
214 :
215 72 : if (II->getOperand(i).isImm()) {
216 : continue;
217 : }
218 :
219 29 : if (II->getOperand(i).isReg()) {
220 58 : if (!TargetRegisterInfo::isVirtualRegister(II->getOperand(i).getReg()))
221 6 : if (llvm::find(PhysRegDefs, II->getOperand(i).getReg()) ==
222 : PhysRegDefs.end()) {
223 : continue;
224 : }
225 : }
226 :
227 : IsPseudoIdempotent = false;
228 : break;
229 : }
230 :
231 : 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 : continue;
251 31 : if (DefLoc >= UseLoc)
252 : 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 : 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 : 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 654 : [&](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 20 : E.second, MBB, [&]() -> MachineBasicBlock::iterator { return UseI; });
309 : }
310 :
311 6 : PseudoIdempotentInstCount = PseudoIdempotentInstructions.size();
312 : LLVM_DEBUG(
313 : dbgs() << "Rescheduling Idempotent Instructions Lexographically.";);
314 8 : 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 15 : Copies.push_back(&MI);
329 : }
330 :
331 18 : for (MachineInstr *MI : Copies) {
332 :
333 30 : if (!MI->getOperand(0).isReg())
334 : continue;
335 15 : if (!MI->getOperand(1).isReg())
336 : 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 : continue;
343 13 : if (!TargetRegisterInfo::isVirtualRegister(Src))
344 : continue;
345 7 : if (MRI.getRegClass(Dst) != MRI.getRegClass(Src))
346 : continue;
347 :
348 8 : 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 78 : for (auto II = MBB->begin(), IE = MBB->end(); II != IE; ++II) {
371 75 : MachineInstr *MI = &*II;
372 :
373 : bool DoesMISideEffect = false;
374 :
375 75 : 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 167 : 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 75 : 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 100 : if (TReg.isFrameIndex()) {
410 : LLVM_DEBUG(dbgs() << "Popping frame index.\n";);
411 21 : VRegs.push_back(TypedVReg(RSE_FrameIndex));
412 28 : continue;
413 : }
414 :
415 : assert(TReg.isReg() && "Expected vreg or physreg.");
416 79 : unsigned Reg = TReg.getReg();
417 :
418 79 : 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 0 : return TR.isReg() && TR.getReg() == Reg;
427 : })) {
428 56 : 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 127 : 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 0 : [&](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 : continue;
465 50 : 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 0 : void SkipVRegs() {
488 : unsigned VRegGapIndex = 1;
489 : const unsigned VR_GAP = (++VRegGapIndex * 1000);
490 :
491 0 : unsigned I = virtualVRegNumber;
492 0 : const unsigned E = (((I + VR_GAP) / VR_GAP) + 1) * VR_GAP;
493 :
494 0 : virtualVRegNumber = E;
495 0 : }
496 :
497 0 : unsigned getVirtualVReg() const { return virtualVRegNumber; }
498 :
499 0 : unsigned incrementVirtualVReg(unsigned incr = 1) {
500 31 : virtualVRegNumber += incr;
501 0 : return virtualVRegNumber;
502 : }
503 :
504 0 : unsigned createVirtualRegister(const TargetRegisterClass *RC) {
505 : std::string S;
506 0 : raw_string_ostream OS(S);
507 0 : OS << "namedVReg" << (virtualVRegNumber & ~0x80000000);
508 : OS.flush();
509 0 : virtualVRegNumber++;
510 :
511 0 : 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 104 : 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 45 : 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 56 : if (llvm::find(renamedInOtherBB, Reg) != renamedInOtherBB.end()) {
556 : LLVM_DEBUG(dbgs() << "Vreg " << Reg
557 : << " already renamed in other BB.\n";);
558 : 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 127 : 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 78 : for (auto &MI : *MBB) {
617 305 : for (auto &MO : MI.operands()) {
618 230 : if (!MO.isReg())
619 : continue;
620 140 : if (!MO.isDef() && MO.isKill()) {
621 : Changed = true;
622 : MO.setIsKill(false);
623 : }
624 :
625 140 : if (MO.isDef() && MO.isDead()) {
626 : Changed = true;
627 : MO.setIsDead(false);
628 : }
629 : }
630 : }
631 :
632 3 : return Changed;
633 : }
634 :
635 0 : 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 0 : if (CanonicalizeBasicBlockNumber != ~0U) {
642 0 : if (CanonicalizeBasicBlockNumber != basicBlockNum++)
643 0 : return false;
644 : LLVM_DEBUG(dbgs() << "\n Canonicalizing BasicBlock " << MBB->getName()
645 : << "\n";);
646 : }
647 :
648 0 : if (llvm::find(bbNames, MBB->getName()) != bbNames.end()) {
649 : LLVM_DEBUG({
650 : dbgs() << "Found potentially duplicate BasicBlocks: " << MBB->getName()
651 : << "\n";
652 : });
653 0 : 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 0 : MachineFunction &MF = *MBB->getParent();
663 0 : MachineRegisterInfo &MRI = MF.getRegInfo();
664 :
665 0 : 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 0 : 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 0 : unsigned IdempotentInstCount = 0;
675 0 : Changed |= rescheduleCanonically(IdempotentInstCount, MBB);
676 : LLVM_DEBUG(dbgs() << "MBB After Scheduling:\n"; MBB->dump(););
677 :
678 0 : 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 0 : for (auto candidate : Candidates) {
685 0 : 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 0 : for (unsigned i = 1; i < candidate->getNumOperands(); i++) {
694 0 : if (candidate->mayStore() || candidate->isBranch())
695 : break;
696 :
697 0 : MachineOperand &MO = candidate->getOperand(i);
698 0 : if (!(MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg())))
699 0 : continue;
700 :
701 : LLVM_DEBUG(dbgs() << "Enqueue register"; MO.dump(); dbgs() << "\n";);
702 0 : 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 0 : for (unsigned i = 0; i < candidate->getNumOperands(); i++) {
708 :
709 0 : if (!candidate->mayStore() && !candidate->isBranch())
710 : break;
711 :
712 0 : MachineOperand &MO = candidate->getOperand(i);
713 :
714 : // TODO: Do we want to only add vregs here?
715 0 : if (!MO.isReg() && !MO.isFI())
716 0 : continue;
717 :
718 : LLVM_DEBUG(dbgs() << "Enqueue Reg/FI"; MO.dump(); dbgs() << "\n";);
719 :
720 0 : RegQueue.push(MO.isReg() ? TypedVReg(MO.getReg())
721 : : TypedVReg(RSE_FrameIndex));
722 : }
723 :
724 0 : 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 0 : if (VRegs.size() == 0)
730 0 : return Changed;
731 :
732 0 : auto VRegRenameMap = GetVRegRenameMap(VRegs, renamedInOtherBB, MRI, NVC);
733 0 : 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 : auto MII = MBB->begin();
742 0 : for (unsigned i = 0; i < IdempotentInstCount && MII != MBB->end(); ++i) {
743 : MachineInstr &MI = *MII++;
744 : Changed = true;
745 0 : unsigned vRegToRename = MI.getOperand(0).getReg();
746 0 : auto Rename = NVC.createVirtualRegister(MRI.getRegClass(vRegToRename));
747 :
748 : std::vector<MachineOperand *> RenameMOs;
749 0 : for (auto &MO : MRI.reg_operands(vRegToRename)) {
750 0 : RenameMOs.push_back(&MO);
751 : }
752 :
753 0 : for (auto *MO : RenameMOs) {
754 0 : MO->setReg(Rename);
755 : }
756 : }
757 :
758 0 : 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 : }
|
