This is an archive of the discontinued LLVM Phabricator instance.

Differential D67114

[mir-canon][NFC] Move MIR Vreg renaming code to separate file for better reuse.
ClosedPublic

Authored by plotfi on Sep 3 2019, 10:41 AM.

Details

Reviewers
compnerd
paquette
Commits
rG028061d4ebeb: [mir-canon][NFC] Move MIR vreg renaming code to separate file for better reuse.
rL370985: [mir-canon][NFC] Move MIR vreg renaming code to separate file for better reuse.
Summary

This change is actually NFC. I will post a pass that uses the virtual register naming code from MIRCanonicalizatioPass to only rename vregs for the purposes of making MIR tests more readable.

Diff Detail

Repository
rL LLVM

Event Timeline

plotfi created this revision.Sep 3 2019, 10:41 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 3 2019, 10:41 AM
Herald added subscribers: llvm-commits, hiraditya, mgorny. · View Herald Transcript
paquette added a comment.Sep 3 2019, 11:25 AM

This is just code movement, but still a couple of nits/questions.

Only thing I think that I'd really like to see here is some documentation in the header file for functions, classes, etc. If this is going to be shared between some passes, I think it makes sense to document what each thing does, and how these things fit together.

And, since we're moving it all anyway, I guess it'd be worth making function/variable names fit the standard style while we're here.

llvm/lib/CodeGen/MIRVRegNamerUtils.cpp
15–20 ↗(On Diff #218488)
  • Move Doxygen comment to the header?
  • s/An/A/
21 ↗(On Diff #218488)

Now that this isn't fully tied to the canonicalizer, I think it would make sense to give it a more descriptive name?

E.g. findInstructionsWithSideEffects or something?

51 ↗(On Diff #218488)

Same thing here? Basically, anything with "candidate" makes less sense outside the context of a specific pass.

(Maybe it would make sense to pack all of this into a Renamer struct/class or something. I don't have any strong opinions there though.)

llvm/lib/CodeGen/MIRVRegNamerUtils.h
29 ↗(On Diff #218488)

I guess from the name, in concept it's obvious what this class *is*, but it would be nice to have a Doxygen comment documenting what its purpose is etc.

30 ↗(On Diff #218488)

While we're here, might as well rename things to fit the style guide?

e.g. Type, Reg, etc.

31 ↗(On Diff #218488)

Use Register instead of unsigned? Or is this your own thing? (We started using Register instead of unsigned for registers recently.)

50 ↗(On Diff #218488)

This class could use a Doxygen comment as well. It's a little less obvious what it does.

57 ↗(On Diff #218488)

skipVRegs

63 ↗(On Diff #218488)

Why 1000?

100 ↗(On Diff #218488)

getVRegRenameMap

plotfi marked an inline comment as done.Sep 3 2019, 2:17 PM
plotfi added inline comments.
llvm/lib/CodeGen/MIRVRegNamerUtils.h
29 ↗(On Diff #218488)

Actually at second glance, I dont think these need to be exposed outside of the .cpp file.

plotfi updated this revision to Diff 218532.Sep 3 2019, 2:18 PM

Moving the guts of the candidate walk loop into the reusable MIRVRegNamer.cpp library

plotfi marked an inline comment as done.Sep 3 2019, 3:25 PM
plotfi updated this revision to Diff 218557.Sep 3 2019, 3:40 PM
plotfi marked 5 inline comments as done.
plotfi added inline comments.
llvm/lib/CodeGen/MIRVRegNamerUtils.cpp
21 ↗(On Diff #218488)

I've decided to isolate these from the header file. So for now the names can remain without confusion.

51 ↗(On Diff #218488)

Agreed. I can consider changing everything named "candidate" to something else, but I'd rather do it in another commit. I've wrapped most of the functions into an anonymous namespace in the cpp file at this point.

plotfi updated this revision to Diff 218559.Sep 3 2019, 4:06 PM
plotfi marked 5 inline comments as done.

addressing @paquette's suggestions.

plotfi updated this revision to Diff 218560.Sep 3 2019, 4:08 PM
plotfi marked 2 inline comments as done.
plotfi updated this revision to Diff 218566.Sep 3 2019, 4:39 PM
plotfi added inline comments.
llvm/lib/CodeGen/MIRVRegNamerUtils.h
63 ↗(On Diff #218488)

It's used as a default value for skipping indices between BBs and side-effect tree roots. I've made it an optional parameter of the NamedVRegCursor.

paquette accepted this revision.Sep 4 2019, 10:34 AM

LGTM with some nits on comments.

llvm/lib/CodeGen/MIRVRegNamerUtils.h
35 ↗(On Diff #218566)

Judging by the SkipGapSize comment below, I think you wanted to document this?

I guess it's probably a good idea anyway, considering you can initialize it etc?

45–46 ↗(On Diff #218566)

s/SkipGapSize/skipVRegs/

This revision is now accepted and ready to land.Sep 4 2019, 10:34 AM
plotfi updated this revision to Diff 218774.Sep 4 2019, 12:57 PM
plotfi marked 4 inline comments as done.

More comments.

Closed by commit rL370985: [mir-canon][NFC] Move MIR vreg renaming code to separate file for better reuse. (authored by zer0). · Explain WhySep 4 2019, 2:30 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents

PathSize
llvm/
trunk/
lib/
CodeGen/
1 line
342 lines
83 lines
347 lines

Diff 218791

llvm/trunk/lib/CodeGen/CMakeLists.txt

Show First 20 Lines • Show All 115 Lines • ▼ Show 20 Linesadd_llvm_library(LLVMCodeGen
RegAllocFast.cpp RegAllocFast.cpp
RegAllocGreedy.cpp RegAllocGreedy.cpp
RegAllocPBQP.cpp RegAllocPBQP.cpp
RegisterClassInfo.cpp RegisterClassInfo.cpp
RegisterCoalescer.cpp RegisterCoalescer.cpp
RegisterPressure.cpp RegisterPressure.cpp
RegisterScavenging.cpp RegisterScavenging.cpp
RenameIndependentSubregs.cpp RenameIndependentSubregs.cpp
MIRVRegNamerUtils.cpp
MIRCanonicalizerPass.cpp MIRCanonicalizerPass.cpp
RegisterUsageInfo.cpp RegisterUsageInfo.cpp
RegUsageInfoCollector.cpp RegUsageInfoCollector.cpp
RegUsageInfoPropagate.cpp RegUsageInfoPropagate.cpp
ResetMachineFunctionPass.cpp ResetMachineFunctionPass.cpp
SafeStack.cpp SafeStack.cpp
SafeStackColoring.cpp SafeStackColoring.cpp
SafeStackLayout.cpp SafeStackLayout.cpp
▲ Show 20 Lines • Show All 51 Lines • Show Last 20 Lines

llvm/trunk/lib/CodeGen/MIRCanonicalizerPass.cpp

Show All 17 Lines
// llc -o - -run-pass mir-canonicalizer example.mir // llc -o - -run-pass mir-canonicalizer example.mir
// //
// Reorders instructions canonically. // Reorders instructions canonically.
// Renames virtual register operands canonically. // Renames virtual register operands canonically.
// Strips certain MIR artifacts (optionally). // Strips certain MIR artifacts (optionally).
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#include "MIRVRegNamerUtils.h"
#include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/STLExtras.h"
#include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/Passes.h"
#include "llvm/Support/raw_ostream.h" #include "llvm/Support/raw_ostream.h"
Show All 32 Lines void getAnalysisUsage(AnalysisUsage &AU) const override {
MachineFunctionPass::getAnalysisUsage(AU); MachineFunctionPass::getAnalysisUsage(AU);
} }
bool runOnMachineFunction(MachineFunction &MF) override; bool runOnMachineFunction(MachineFunction &MF) override;
}; };
} // end anonymous namespace } // end anonymous namespace
enum VRType { RSE_Reg = 0, RSE_FrameIndex, RSE_NewCandidate };
class TypedVReg {
VRType type;
unsigned reg;
public:
TypedVReg(unsigned reg) : type(RSE_Reg), reg(reg) {}
TypedVReg(VRType type) : type(type), reg(~0U) {
assert(type != RSE_Reg && "Expected a non-register type.");
}
bool isReg() const { return type == RSE_Reg; }
bool isFrameIndex() const { return type == RSE_FrameIndex; }
bool isCandidate() const { return type == RSE_NewCandidate; }
VRType getType() const { return type; }
unsigned getReg() const {
assert(this->isReg() && "Expected a virtual or physical register.");
return reg;
}
};
char MIRCanonicalizer::ID; char MIRCanonicalizer::ID;
char &llvm::MIRCanonicalizerID = MIRCanonicalizer::ID; char &llvm::MIRCanonicalizerID = MIRCanonicalizer::ID;
INITIALIZE_PASS_BEGIN(MIRCanonicalizer, "mir-canonicalizer", INITIALIZE_PASS_BEGIN(MIRCanonicalizer, "mir-canonicalizer",
"Rename Register Operands Canonically", false, false) "Rename Register Operands Canonically", false, false)
INITIALIZE_PASS_END(MIRCanonicalizer, "mir-canonicalizer", INITIALIZE_PASS_END(MIRCanonicalizer, "mir-canonicalizer",
▲ Show 20 Lines • Show All 261 Lines • ▼ Show 20 Lines for (MachineInstr *MI : Copies) {
Changed = true; Changed = true;
MI->eraseFromParent(); MI->eraseFromParent();
} }
return Changed; return Changed;
} }
/// Here we find our candidates. What makes an interesting candidate?
/// An candidate for a canonicalization tree root is normally any kind of
/// instruction that causes side effects such as a store to memory or a copy to
/// a physical register or a return instruction. We use these as an expression
/// tree root that we walk inorder to build a canonical walk which should result
/// in canoncal vreg renaming.
static std::vector<MachineInstr *> populateCandidates(MachineBasicBlock *MBB) {
std::vector<MachineInstr *> Candidates;
MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo();
for (auto II = MBB->begin(), IE = MBB->end(); II != IE; ++II) {
MachineInstr *MI = &*II;
bool DoesMISideEffect = false;
if (MI->getNumOperands() > 0 && MI->getOperand(0).isReg()) {
const Register Dst = MI->getOperand(0).getReg();
DoesMISideEffect |= !Register::isVirtualRegister(Dst);
for (auto UI = MRI.use_begin(Dst); UI != MRI.use_end(); ++UI) {
if (DoesMISideEffect)
break;
DoesMISideEffect |= (UI->getParent()->getParent() != MI->getParent());
}
}
if (!MI->mayStore() && !MI->isBranch() && !DoesMISideEffect)
continue;
LLVM_DEBUG(dbgs() << "Found Candidate: "; MI->dump(););
Candidates.push_back(MI);
}
return Candidates;
}
static void doCandidateWalk(std::vector<TypedVReg> &VRegs,
std::queue<TypedVReg> &RegQueue,
std::vector<MachineInstr *> &VisitedMIs,
const MachineBasicBlock *MBB) {
const MachineFunction &MF = *MBB->getParent();
const MachineRegisterInfo &MRI = MF.getRegInfo();
while (!RegQueue.empty()) {
auto TReg = RegQueue.front();
RegQueue.pop();
if (TReg.isFrameIndex()) {
LLVM_DEBUG(dbgs() << "Popping frame index.\n";);
VRegs.push_back(TypedVReg(RSE_FrameIndex));
continue;
}
assert(TReg.isReg() && "Expected vreg or physreg.");
unsigned Reg = TReg.getReg();
if (Register::isVirtualRegister(Reg)) {
LLVM_DEBUG({
dbgs() << "Popping vreg ";
MRI.def_begin(Reg)->dump();
dbgs() << "\n";
});
if (!llvm::any_of(VRegs, [&](const TypedVReg &TR) {
return TR.isReg() && TR.getReg() == Reg;
})) {
VRegs.push_back(TypedVReg(Reg));
}
} else {
LLVM_DEBUG(dbgs() << "Popping physreg.\n";);
VRegs.push_back(TypedVReg(Reg));
continue;
}
for (auto RI = MRI.def_begin(Reg), RE = MRI.def_end(); RI != RE; ++RI) {
MachineInstr *Def = RI->getParent();
if (Def->getParent() != MBB)
continue;
if (llvm::any_of(VisitedMIs,
[&](const MachineInstr *VMI) { return Def == VMI; })) {
break;
}
LLVM_DEBUG({
dbgs() << "\n========================\n";
dbgs() << "Visited MI: ";
Def->dump();
dbgs() << "BB Name: " << Def->getParent()->getName() << "\n";
dbgs() << "\n========================\n";
});
VisitedMIs.push_back(Def);
for (unsigned I = 1, E = Def->getNumOperands(); I != E; ++I) {
MachineOperand &MO = Def->getOperand(I);
if (MO.isFI()) {
LLVM_DEBUG(dbgs() << "Pushing frame index.\n";);
RegQueue.push(TypedVReg(RSE_FrameIndex));
}
if (!MO.isReg())
continue;
RegQueue.push(TypedVReg(MO.getReg()));
}
}
}
}
namespace {
class NamedVRegCursor {
MachineRegisterInfo &MRI;
unsigned virtualVRegNumber;
public:
NamedVRegCursor(MachineRegisterInfo &MRI) : MRI(MRI), virtualVRegNumber(0) {}
void SkipVRegs() {
unsigned VRegGapIndex = 1;
if (!virtualVRegNumber) {
VRegGapIndex = 0;
virtualVRegNumber = MRI.createIncompleteVirtualRegister();
}
const unsigned VR_GAP = (++VRegGapIndex * 1000);
unsigned I = virtualVRegNumber;
const unsigned E = (((I + VR_GAP) / VR_GAP) + 1) * VR_GAP;
virtualVRegNumber = E;
}
unsigned getVirtualVReg() const { return virtualVRegNumber; }
unsigned incrementVirtualVReg(unsigned incr = 1) {
virtualVRegNumber += incr;
return virtualVRegNumber;
}
unsigned createVirtualRegister(unsigned VReg) {
if (!virtualVRegNumber)
SkipVRegs();
std::string S;
raw_string_ostream OS(S);
OS << "namedVReg" << (virtualVRegNumber & ~0x80000000);
OS.flush();
virtualVRegNumber++;
if (auto RC = MRI.getRegClassOrNull(VReg))
return MRI.createVirtualRegister(RC, OS.str());
return MRI.createGenericVirtualRegister(MRI.getType(VReg), OS.str());
}
};
} // namespace
static std::map<unsigned, unsigned>
GetVRegRenameMap(const std::vector<TypedVReg> &VRegs,
const std::vector<unsigned> &renamedInOtherBB,
MachineRegisterInfo &MRI, NamedVRegCursor &NVC) {
std::map<unsigned, unsigned> VRegRenameMap;
bool FirstCandidate = true;
for (auto &vreg : VRegs) {
if (vreg.isFrameIndex()) {
// We skip one vreg for any frame index because there is a good chance
// (especially when comparing SelectionDAG to GlobalISel generated MIR)
// that in the other file we are just getting an incoming vreg that comes
// from a copy from a frame index. So it's safe to skip by one.
unsigned LastRenameReg = NVC.incrementVirtualVReg();
(void)LastRenameReg;
LLVM_DEBUG(dbgs() << "Skipping rename for FI " << LastRenameReg << "\n";);
continue;
} else if (vreg.isCandidate()) {
// After the first candidate, for every subsequent candidate, we skip mod
// 10 registers so that the candidates are more likely to start at the
// same vreg number making it more likely that the canonical walk from the
// candidate insruction. We don't need to skip from the first candidate of
// the BasicBlock because we already skip ahead several vregs for each BB.
unsigned LastRenameReg = NVC.getVirtualVReg();
if (FirstCandidate)
NVC.incrementVirtualVReg(LastRenameReg % 10);
FirstCandidate = false;
continue;
} else if (!Register::isVirtualRegister(vreg.getReg())) {
unsigned LastRenameReg = NVC.incrementVirtualVReg();
(void)LastRenameReg;
LLVM_DEBUG({
dbgs() << "Skipping rename for Phys Reg " << LastRenameReg << "\n";
});
continue;
}
auto Reg = vreg.getReg();
if (llvm::find(renamedInOtherBB, Reg) != renamedInOtherBB.end()) {
LLVM_DEBUG(dbgs() << "Vreg " << Reg
<< " already renamed in other BB.\n";);
continue;
}
auto Rename = NVC.createVirtualRegister(Reg);
if (VRegRenameMap.find(Reg) == VRegRenameMap.end()) {
LLVM_DEBUG(dbgs() << "Mapping vreg ";);
if (MRI.reg_begin(Reg) != MRI.reg_end()) {
LLVM_DEBUG(auto foo = &*MRI.reg_begin(Reg); foo->dump(););
} else {
LLVM_DEBUG(dbgs() << Reg;);
}
LLVM_DEBUG(dbgs() << " to ";);
if (MRI.reg_begin(Rename) != MRI.reg_end()) {
LLVM_DEBUG(auto foo = &*MRI.reg_begin(Rename); foo->dump(););
} else {
LLVM_DEBUG(dbgs() << Rename;);
}
LLVM_DEBUG(dbgs() << "\n";);
VRegRenameMap.insert(std::pair<unsigned, unsigned>(Reg, Rename));
}
}
return VRegRenameMap;
}
static bool doVRegRenaming(std::vector<unsigned> &RenamedInOtherBB,
const std::map<unsigned, unsigned> &VRegRenameMap,
MachineRegisterInfo &MRI) {
bool Changed = false;
for (auto I = VRegRenameMap.begin(), E = VRegRenameMap.end(); I != E; ++I) {
auto VReg = I->first;
auto Rename = I->second;
RenamedInOtherBB.push_back(Rename);
std::vector<MachineOperand *> RenameMOs;
for (auto &MO : MRI.reg_operands(VReg)) {
RenameMOs.push_back(&MO);
}
for (auto *MO : RenameMOs) {
Changed = true;
MO->setReg(Rename);
if (!MO->isDef())
MO->setIsKill(false);
}
}
return Changed;
}
static bool doDefKillClear(MachineBasicBlock *MBB) { static bool doDefKillClear(MachineBasicBlock *MBB) {
bool Changed = false; bool Changed = false;
for (auto &MI : *MBB) { for (auto &MI : *MBB) {
for (auto &MO : MI.operands()) { for (auto &MO : MI.operands()) {
if (!MO.isReg()) if (!MO.isReg())
continue; continue;
if (!MO.isDef() && MO.isKill()) { if (!MO.isDef() && MO.isKill()) {
Changed = true; Changed = true;
MO.setIsKill(false); MO.setIsKill(false);
} }
if (MO.isDef() && MO.isDead()) { if (MO.isDef() && MO.isDead()) {
Changed = true; Changed = true;
MO.setIsDead(false); MO.setIsDead(false);
} }
} }
} }
return Changed; return Changed;
} }
static bool runOnBasicBlock(MachineBasicBlock *MBB, static bool runOnBasicBlock(MachineBasicBlock *MBB,
std::vector<StringRef> &bbNames, std::vector<StringRef> &bbNames,
std::vector<unsigned> &renamedInOtherBB, unsigned &basicBlockNum, NamedVRegCursor &NVC) {
unsigned &basicBlockNum, unsigned &VRegGapIndex,
NamedVRegCursor &NVC) {
if (CanonicalizeBasicBlockNumber != ~0U) { if (CanonicalizeBasicBlockNumber != ~0U) {
if (CanonicalizeBasicBlockNumber != basicBlockNum++) if (CanonicalizeBasicBlockNumber != basicBlockNum++)
return false; return false;
LLVM_DEBUG(dbgs() << "\n Canonicalizing BasicBlock " << MBB->getName() LLVM_DEBUG(dbgs() << "\n Canonicalizing BasicBlock " << MBB->getName()
<< "\n";); << "\n";);
} }
Show All 22 Linesstatic bool runOnBasicBlock(MachineBasicBlock *MBB,
Changed |= propagateLocalCopies(MBB); Changed |= propagateLocalCopies(MBB);
LLVM_DEBUG(dbgs() << "MBB After Canonical Copy Propagation:\n"; MBB->dump();); LLVM_DEBUG(dbgs() << "MBB After Canonical Copy Propagation:\n"; MBB->dump(););
LLVM_DEBUG(dbgs() << "MBB Before Scheduling:\n"; MBB->dump();); LLVM_DEBUG(dbgs() << "MBB Before Scheduling:\n"; MBB->dump(););
unsigned IdempotentInstCount = 0; unsigned IdempotentInstCount = 0;
Changed |= rescheduleCanonically(IdempotentInstCount, MBB); Changed |= rescheduleCanonically(IdempotentInstCount, MBB);
LLVM_DEBUG(dbgs() << "MBB After Scheduling:\n"; MBB->dump();); LLVM_DEBUG(dbgs() << "MBB After Scheduling:\n"; MBB->dump(););
std::vector<MachineInstr *> Candidates = populateCandidates(MBB); Changed |= NVC.renameVRegs(MBB);
std::vector<MachineInstr *> VisitedMIs;
llvm::copy(Candidates, std::back_inserter(VisitedMIs));
std::vector<TypedVReg> VRegs;
for (auto candidate : Candidates) {
VRegs.push_back(TypedVReg(RSE_NewCandidate));
std::queue<TypedVReg> RegQueue;
// Here we walk the vreg operands of a non-root node along our walk.
// The root nodes are the original candidates (stores normally).
// These are normally not the root nodes (except for the case of copies to
// physical registers).
for (unsigned i = 1; i < candidate->getNumOperands(); i++) {
if (candidate->mayStore() || candidate->isBranch())
break;
MachineOperand &MO = candidate->getOperand(i);
if (!(MO.isReg() && Register::isVirtualRegister(MO.getReg())))
continue;
LLVM_DEBUG(dbgs() << "Enqueue register"; MO.dump(); dbgs() << "\n";);
RegQueue.push(TypedVReg(MO.getReg()));
}
// Here we walk the root candidates. We start from the 0th operand because
// the root is normally a store to a vreg.
for (unsigned i = 0; i < candidate->getNumOperands(); i++) {
if (!candidate->mayStore() && !candidate->isBranch())
break;
MachineOperand &MO = candidate->getOperand(i);
// TODO: Do we want to only add vregs here?
if (!MO.isReg() && !MO.isFI())
continue;
LLVM_DEBUG(dbgs() << "Enqueue Reg/FI"; MO.dump(); dbgs() << "\n";);
RegQueue.push(MO.isReg() ? TypedVReg(MO.getReg())
: TypedVReg(RSE_FrameIndex));
}
doCandidateWalk(VRegs, RegQueue, VisitedMIs, MBB);
}
// If we have populated no vregs to rename then bail.
// The rest of this function does the vreg remaping.
if (VRegs.size() == 0)
return Changed;
auto VRegRenameMap = GetVRegRenameMap(VRegs, renamedInOtherBB, MRI, NVC);
Changed |= doVRegRenaming(renamedInOtherBB, VRegRenameMap, MRI);
// Here we renumber the def vregs for the idempotent instructions from the top // Here we renumber the def vregs for the idempotent instructions from the top
// of the MachineBasicBlock so that they are named in the order that we sorted // of the MachineBasicBlock so that they are named in the order that we sorted
// them alphabetically. Eventually we wont need SkipVRegs because we will use // them alphabetically. Eventually we wont need SkipVRegs because we will use
// named vregs instead. // named vregs instead.
if (IdempotentInstCount) if (IdempotentInstCount)
NVC.SkipVRegs(); NVC.skipVRegs();
auto MII = MBB->begin(); auto MII = MBB->begin();
for (unsigned i = 0; i < IdempotentInstCount && MII != MBB->end(); ++i) { for (unsigned i = 0; i < IdempotentInstCount && MII != MBB->end(); ++i) {
MachineInstr &MI = *MII++; MachineInstr &MI = *MII++;
Changed = true; Changed = true;
Register vRegToRename = MI.getOperand(0).getReg(); Register vRegToRename = MI.getOperand(0).getReg();
auto Rename = NVC.createVirtualRegister(vRegToRename); auto Rename = NVC.createVirtualRegister(vRegToRename);
Show All 34 Lines LLVM_DEBUG(
dbgs() << "\n\n NEW MACHINE FUNCTION: " << MF.getName() << " \n\n"; dbgs() << "\n\n NEW MACHINE FUNCTION: " << MF.getName() << " \n\n";
dbgs() << "\n\n================================================\n\n"; dbgs() << "\n\n================================================\n\n";
dbgs() << "Total Basic Blocks: " << RPOList.size() << "\n"; dbgs() << "Total Basic Blocks: " << RPOList.size() << "\n";
for (auto MBB for (auto MBB
: RPOList) { dbgs() << MBB->getName() << "\n"; } dbgs() : RPOList) { dbgs() << MBB->getName() << "\n"; } dbgs()
<< "\n\n================================================\n\n";); << "\n\n================================================\n\n";);
std::vector<StringRef> BBNames; std::vector<StringRef> BBNames;
std::vector<unsigned> RenamedInOtherBB;
unsigned GapIdx = 0;
unsigned BBNum = 0; unsigned BBNum = 0;
bool Changed = false; bool Changed = false;
MachineRegisterInfo &MRI = MF.getRegInfo(); MachineRegisterInfo &MRI = MF.getRegInfo();
NamedVRegCursor NVC(MRI); NamedVRegCursor NVC(MRI);
for (auto MBB : RPOList) for (auto MBB : RPOList)
Changed |= Changed |= runOnBasicBlock(MBB, BBNames, BBNum, NVC);
runOnBasicBlock(MBB, BBNames, RenamedInOtherBB, BBNum, GapIdx, NVC);
return Changed; return Changed;
} }

llvm/trunk/lib/CodeGen/MIRVRegNamerUtils.h

//===------------ MIRVRegNamerUtils.h - MIR VReg Renaming Utilities -------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// The purpose of these utilities is to abstract out parts of the MIRCanon pass
// that are responsible for renaming virtual registers with the purpose of
// sharing code with a MIRVRegNamer pass that could be the analog of the
// opt -instnamer pass.
//
//===----------------------------------------------------------------------===//
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/Support/raw_ostream.h"
#include <queue>
using namespace llvm;
/// NamedVRegCursor - The cursor is an object that keeps track of what the next
/// vreg name should be. It does book keeping to determine when to skip the
/// index value and by how much, or if the next vreg name should be an increment
/// from the previous.
class NamedVRegCursor {
MachineRegisterInfo &MRI;
/// virtualVRegNumber - Book keeping of the last vreg position.
unsigned virtualVRegNumber;
/// SkipGapSize - Used to calculate a modulo amount to skip by after every
/// sequence of instructions starting from a given side-effecting
/// MachineInstruction for a given MachineBasicBlock. The general idea is that
/// for a given program compiled with two different opt pipelines, there
/// shouldn't be greater than SkipGapSize difference in how many vregs are in
/// play between the two and for every def-use graph of vregs we rename we
/// will round up to the next SkipGapSize'th number so that we have a high
/// change of landing on the same name for two given matching side-effects
/// for the two compilation outcomes.
const unsigned SkipGapSize;
/// RenamedInOtherBB - VRegs that we already renamed: ie breadcrumbs.
std::vector<Register> RenamedInOtherBB;
public:
NamedVRegCursor() = delete;
/// 1000 for the SkipGapSize was a good heuristic at the time of the writing
/// of the MIRCanonicalizerPass. Adjust as needed.
NamedVRegCursor(MachineRegisterInfo &MRI, unsigned SkipGapSize = 1000)
: MRI(MRI), virtualVRegNumber(0), SkipGapSize(SkipGapSize) {}
/// SkipGapSize - Skips modulo a gap value of indices. Indices are used to
/// produce the next vreg name.
void skipVRegs();
unsigned getVirtualVReg() const { return virtualVRegNumber; }
/// incrementVirtualVReg - This increments an index value that us used to
/// create a new vreg name. This is not a Register.
unsigned incrementVirtualVReg(unsigned incr = 1) {
virtualVRegNumber += incr;
return virtualVRegNumber;
}
/// createVirtualRegister - Given an existing vreg, create a named vreg to
/// take its place.
unsigned createVirtualRegister(unsigned VReg);
/// 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. This method maintains book keeping for which vregs
/// were already renamed in RenamedInOtherBB.
// @return changed
bool renameVRegs(MachineBasicBlock *MBB);
};

llvm/trunk/lib/CodeGen/MIRVRegNamerUtils.cpp

//===---------- MIRVRegNamerUtils.cpp - MIR VReg Renaming Utilities -------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#include "MIRVRegNamerUtils.h"
using namespace llvm;
#define DEBUG_TYPE "mir-vregnamer-utils"
namespace {
// TypedVReg and VRType are used to tell the renamer what to do at points in a
// sequence of values to be renamed. A TypedVReg can either contain
// an actual VReg, a FrameIndex, or it could just be a barrier for the next
// candidate (side-effecting instruction). This tells the renamer to increment
// to the next vreg name, or to skip modulo some skip-gap value.
enum VRType { RSE_Reg = 0, RSE_FrameIndex, RSE_NewCandidate };
class TypedVReg {
VRType Type;
Register Reg;
public:
TypedVReg(Register Reg) : Type(RSE_Reg), Reg(Reg) {}
TypedVReg(VRType Type) : Type(Type), Reg(~0U) {
assert(Type != RSE_Reg && "Expected a non-Register Type.");
}
bool isReg() const { return Type == RSE_Reg; }
bool isFrameIndex() const { return Type == RSE_FrameIndex; }
bool isCandidate() const { return Type == RSE_NewCandidate; }
VRType getType() const { return Type; }
Register getReg() const {
assert(this->isReg() && "Expected a virtual or physical Register.");
return Reg;
}
};
/// Here we find our candidates. What makes an interesting candidate?
/// A candidate for a canonicalization tree root is normally any kind of
/// instruction that causes side effects such as a store to memory or a copy to
/// a physical register or a return instruction. We use these as an expression
/// tree root that we walk in order to build a canonical walk which should
/// result in canonical vreg renaming.
std::vector<MachineInstr *> populateCandidates(MachineBasicBlock *MBB) {
std::vector<MachineInstr *> Candidates;
MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo();
for (auto II = MBB->begin(), IE = MBB->end(); II != IE; ++II) {
MachineInstr *MI = &*II;
bool DoesMISideEffect = false;
if (MI->getNumOperands() > 0 && MI->getOperand(0).isReg()) {
const Register Dst = MI->getOperand(0).getReg();
DoesMISideEffect |= !Register::isVirtualRegister(Dst);
for (auto UI = MRI.use_begin(Dst); UI != MRI.use_end(); ++UI) {
if (DoesMISideEffect)
break;
DoesMISideEffect |= (UI->getParent()->getParent() != MI->getParent());
}
}
if (!MI->mayStore() && !MI->isBranch() && !DoesMISideEffect)
continue;
LLVM_DEBUG(dbgs() << "Found Candidate: "; MI->dump(););
Candidates.push_back(MI);
}
return Candidates;
}
void doCandidateWalk(std::vector<TypedVReg> &VRegs,
std::queue<TypedVReg> &RegQueue,
std::vector<MachineInstr *> &VisitedMIs,
const MachineBasicBlock *MBB) {
const MachineFunction &MF = *MBB->getParent();
const MachineRegisterInfo &MRI = MF.getRegInfo();
while (!RegQueue.empty()) {
auto TReg = RegQueue.front();
RegQueue.pop();
if (TReg.isFrameIndex()) {
LLVM_DEBUG(dbgs() << "Popping frame index.\n";);
VRegs.push_back(TypedVReg(RSE_FrameIndex));
continue;
}
assert(TReg.isReg() && "Expected vreg or physreg.");
Register Reg = TReg.getReg();
if (Register::isVirtualRegister(Reg)) {
LLVM_DEBUG({
dbgs() << "Popping vreg ";
MRI.def_begin(Reg)->dump();
dbgs() << "\n";
});
if (!llvm::any_of(VRegs, [&](const TypedVReg &TR) {
return TR.isReg() && TR.getReg() == Reg;
})) {
VRegs.push_back(TypedVReg(Reg));
}
} else {
LLVM_DEBUG(dbgs() << "Popping physreg.\n";);
VRegs.push_back(TypedVReg(Reg));
continue;
}
for (auto RI = MRI.def_begin(Reg), RE = MRI.def_end(); RI != RE; ++RI) {
MachineInstr *Def = RI->getParent();
if (Def->getParent() != MBB)
continue;
if (llvm::any_of(VisitedMIs,
[&](const MachineInstr *VMI) { return Def == VMI; })) {
break;
}
LLVM_DEBUG({
dbgs() << "\n========================\n";
dbgs() << "Visited MI: ";
Def->dump();
dbgs() << "BB Name: " << Def->getParent()->getName() << "\n";
dbgs() << "\n========================\n";
});
VisitedMIs.push_back(Def);
for (unsigned I = 1, E = Def->getNumOperands(); I != E; ++I) {
MachineOperand &MO = Def->getOperand(I);
if (MO.isFI()) {
LLVM_DEBUG(dbgs() << "Pushing frame index.\n";);
RegQueue.push(TypedVReg(RSE_FrameIndex));
}
if (!MO.isReg())
continue;
RegQueue.push(TypedVReg(MO.getReg()));
}
}
}
}
std::map<unsigned, unsigned>
getVRegRenameMap(const std::vector<TypedVReg> &VRegs,
const std::vector<Register> &renamedInOtherBB,
MachineRegisterInfo &MRI, NamedVRegCursor &NVC) {
std::map<unsigned, unsigned> VRegRenameMap;
bool FirstCandidate = true;
for (auto &vreg : VRegs) {
if (vreg.isFrameIndex()) {
// We skip one vreg for any frame index because there is a good chance
// (especially when comparing SelectionDAG to GlobalISel generated MIR)
// that in the other file we are just getting an incoming vreg that comes
// from a copy from a frame index. So it's safe to skip by one.
unsigned LastRenameReg = NVC.incrementVirtualVReg();
(void)LastRenameReg;
LLVM_DEBUG(dbgs() << "Skipping rename for FI " << LastRenameReg << "\n";);
continue;
} else if (vreg.isCandidate()) {
// After the first candidate, for every subsequent candidate, we skip mod
// 10 registers so that the candidates are more likely to start at the
// same vreg number making it more likely that the canonical walk from the
// candidate insruction. We don't need to skip from the first candidate of
// the BasicBlock because we already skip ahead several vregs for each BB.
unsigned LastRenameReg = NVC.getVirtualVReg();
if (FirstCandidate)
NVC.incrementVirtualVReg(LastRenameReg % 10);
FirstCandidate = false;
continue;
} else if (!Register::isVirtualRegister(vreg.getReg())) {
unsigned LastRenameReg = NVC.incrementVirtualVReg();
(void)LastRenameReg;
LLVM_DEBUG({
dbgs() << "Skipping rename for Phys Reg " << LastRenameReg << "\n";
});
continue;
}
auto Reg = vreg.getReg();
if (llvm::find(renamedInOtherBB, Reg) != renamedInOtherBB.end()) {
LLVM_DEBUG(dbgs() << "Vreg " << Reg
<< " already renamed in other BB.\n";);
continue;
}
auto Rename = NVC.createVirtualRegister(Reg);
if (VRegRenameMap.find(Reg) == VRegRenameMap.end()) {
LLVM_DEBUG(dbgs() << "Mapping vreg ";);
if (MRI.reg_begin(Reg) != MRI.reg_end()) {
LLVM_DEBUG(auto foo = &*MRI.reg_begin(Reg); foo->dump(););
} else {
LLVM_DEBUG(dbgs() << Reg;);
}
LLVM_DEBUG(dbgs() << " to ";);
if (MRI.reg_begin(Rename) != MRI.reg_end()) {
LLVM_DEBUG(auto foo = &*MRI.reg_begin(Rename); foo->dump(););
} else {
LLVM_DEBUG(dbgs() << Rename;);
}
LLVM_DEBUG(dbgs() << "\n";);
VRegRenameMap.insert(std::pair<unsigned, unsigned>(Reg, Rename));
}
}
return VRegRenameMap;
}
bool doVRegRenaming(std::vector<Register> &renamedInOtherBB,
const std::map<unsigned, unsigned> &VRegRenameMap,
MachineRegisterInfo &MRI) {
bool Changed = false;
for (auto I = VRegRenameMap.begin(), E = VRegRenameMap.end(); I != E; ++I) {
auto VReg = I->first;
auto Rename = I->second;
renamedInOtherBB.push_back(Rename);
std::vector<MachineOperand *> RenameMOs;
for (auto &MO : MRI.reg_operands(VReg)) {
RenameMOs.push_back(&MO);
}
for (auto *MO : RenameMOs) {
Changed = true;
MO->setReg(Rename);
if (!MO->isDef())
MO->setIsKill(false);
}
}
return Changed;
}
bool renameVRegs(MachineBasicBlock *MBB,
std::vector<Register> &renamedInOtherBB,
NamedVRegCursor &NVC) {
bool Changed = false;
MachineFunction &MF = *MBB->getParent();
MachineRegisterInfo &MRI = MF.getRegInfo();
std::vector<MachineInstr *> Candidates = populateCandidates(MBB);
std::vector<MachineInstr *> VisitedMIs;
llvm::copy(Candidates, std::back_inserter(VisitedMIs));
std::vector<TypedVReg> VRegs;
for (auto candidate : Candidates) {
VRegs.push_back(TypedVReg(RSE_NewCandidate));
std::queue<TypedVReg> RegQueue;
// Here we walk the vreg operands of a non-root node along our walk.
// The root nodes are the original candidates (stores normally).
// These are normally not the root nodes (except for the case of copies to
// physical registers).
for (unsigned i = 1; i < candidate->getNumOperands(); i++) {
if (candidate->mayStore() || candidate->isBranch())
break;
MachineOperand &MO = candidate->getOperand(i);
if (!(MO.isReg() && Register::isVirtualRegister(MO.getReg())))
continue;
LLVM_DEBUG(dbgs() << "Enqueue register"; MO.dump(); dbgs() << "\n";);
RegQueue.push(TypedVReg(MO.getReg()));
}
// Here we walk the root candidates. We start from the 0th operand because
// the root is normally a store to a vreg.
for (unsigned i = 0; i < candidate->getNumOperands(); i++) {
if (!candidate->mayStore() && !candidate->isBranch())
break;
MachineOperand &MO = candidate->getOperand(i);
// TODO: Do we want to only add vregs here?
if (!MO.isReg() && !MO.isFI())
continue;
LLVM_DEBUG(dbgs() << "Enqueue Reg/FI"; MO.dump(); dbgs() << "\n";);
RegQueue.push(MO.isReg() ? TypedVReg(MO.getReg())
: TypedVReg(RSE_FrameIndex));
}
doCandidateWalk(VRegs, RegQueue, VisitedMIs, MBB);
}
// If we have populated no vregs to rename then bail.
// The rest of this function does the vreg remaping.
if (VRegs.size() == 0)
return Changed;
auto VRegRenameMap = getVRegRenameMap(VRegs, renamedInOtherBB, MRI, NVC);
Changed |= doVRegRenaming(renamedInOtherBB, VRegRenameMap, MRI);
return Changed;
}
} // anonymous namespace
void NamedVRegCursor::skipVRegs() {
unsigned VRegGapIndex = 1;
if (!virtualVRegNumber) {
VRegGapIndex = 0;
virtualVRegNumber = MRI.createIncompleteVirtualRegister();
}
const unsigned VR_GAP = (++VRegGapIndex * SkipGapSize);
unsigned I = virtualVRegNumber;
const unsigned E = (((I + VR_GAP) / VR_GAP) + 1) * VR_GAP;
virtualVRegNumber = E;
}
unsigned NamedVRegCursor::createVirtualRegister(unsigned VReg) {
if (!virtualVRegNumber)
skipVRegs();
std::string S;
raw_string_ostream OS(S);
OS << "namedVReg" << (virtualVRegNumber & ~0x80000000);
OS.flush();
virtualVRegNumber++;
if (auto RC = MRI.getRegClassOrNull(VReg))
return MRI.createVirtualRegister(RC, OS.str());
return MRI.createGenericVirtualRegister(MRI.getType(VReg), OS.str());
}
bool NamedVRegCursor::renameVRegs(MachineBasicBlock *MBB) {
return ::renameVRegs(MBB, RenamedInOtherBB, *this);
}