Diff 218557

llvm/lib/CodeGen/CMakeLists.txt

Show First 20 Lines • Show All 115 Lines • ▼ Show 20 Lines	add_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/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()) {
▲ Show 20 Lines • Show All 49 Lines • ▼ Show 20 Lines	static 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 \|= renameVRegs(MBB, renamedInOtherBB, NVC);
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();

▲ Show 20 Lines • Show All 64 Lines • Show Last 20 Lines

llvm/lib/CodeGen/MIRVRegNamerUtils.h

This file was added.

				//===------------ 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
				paquetteUnsubmitted Done Reply Inline Actions 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. paquette: I guess from the name, in concept it's obvious what this class is, but it would be nice to…
				plotfiAuthorUnsubmitted Done Reply Inline Actions Actually at second glance, I dont think these need to be exposed outside of the .cpp file. plotfi: Actually at second glance, I dont think these need to be exposed outside of the .cpp file.
				/// from the previous.
				paquetteUnsubmitted Done Reply Inline Actions While we're here, might as well rename things to fit the style guide? e.g. `Type`, `Reg`, etc. paquette: While we're here, might as well rename things to fit the style guide? e.g. `Type`, `Reg`, etc.
				class NamedVRegCursor {
				paquetteUnsubmitted Done Reply Inline Actions Use `Register` instead of `unsigned`? Or is this your own thing? (We started using `Register` instead of unsigned for registers recently.) paquette: Use `Register` instead of `unsigned`? Or is this your own thing? (We started using `Register`…
				MachineRegisterInfo &MRI;
				unsigned virtualVRegNumber;
				const unsigned SkipGapSize;

				paquetteUnsubmitted Done Reply Inline Actions 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? paquette: Judging by the SkipGapSize comment below, I think you wanted to document this? I guess it's…
				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 VRegGapIndex = 1;
				paquetteUnsubmitted Done Reply Inline Actions s/SkipGapSize/skipVRegs/ paquette: s/SkipGapSize/skipVRegs/
				if (!virtualVRegNumber) {
				VRegGapIndex = 0;
				virtualVRegNumber = MRI.createIncompleteVirtualRegister();
				}
				paquetteUnsubmitted Done Reply Inline Actions This class could use a Doxygen comment as well. It's a little less obvious what it does. paquette: This class could use a Doxygen comment as well. It's a little less obvious what it does.
				const unsigned VR_GAP = (++VRegGapIndex * SkipGapSize);

				unsigned I = virtualVRegNumber;
				const unsigned E = (((I + VR_GAP) / VR_GAP) + 1) * VR_GAP;

				virtualVRegNumber = E;
				}
				paquetteUnsubmitted Done Reply Inline Actions `skipVRegs` paquette: `skipVRegs`

				unsigned getVirtualVReg() const { return virtualVRegNumber; }

				unsigned incrementVirtualVReg(unsigned incr = 1) {
				virtualVRegNumber += incr;
				return virtualVRegNumber;
				paquetteUnsubmitted Done Reply Inline Actions Why 1000? paquette: Why 1000?
				plotfiAuthorUnsubmitted Done Reply Inline Actions 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. plotfi: It's used as a default value for skipping indices between BBs and side-effect tree roots. I've…
				}

				/// createVirtualRegister - Given an existing vreg, create a named vreg to
				/// take its place.
				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());
				}
				};

				bool renameVRegs(MachineBasicBlock *MBB,
				std::vector<unsigned> &renamedInOtherBB, NamedVRegCursor &NVC);
				paquetteUnsubmitted Done Reply Inline Actions `getVRegRenameMap` paquette: `getVRegRenameMap`

llvm/lib/CodeGen/MIRVRegNamerUtils.cpp

This file was added.

				//===---------- 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.
				paquetteUnsubmitted Done Reply Inline Actions Move Doxygen comment to the header? s/An/A/ paquette: - Move Doxygen comment to the header? - s/An/A/
				enum VRType { RSE_Reg = 0, RSE_FrameIndex, RSE_NewCandidate };
				paquetteUnsubmitted Done Reply Inline Actions 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? paquette: Now that this isn't fully tied to the canonicalizer, I think it would make sense to give it a…
				plotfiAuthorUnsubmitted Done Reply Inline Actions I've decided to isolate these from the header file. So for now the names can remain without confusion. plotfi: I've decided to isolate these from the header file. So for now the names can remain without…
				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;
				}
				};

				/// 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();
				paquetteUnsubmitted Done Reply Inline Actions 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.) paquette: Same thing here? Basically, anything with "candidate" makes less sense outside the context of a…
				plotfiAuthorUnsubmitted Done Reply Inline Actions 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: Agreed. I can consider changing everything named "candidate" to something else, but I'd rather…

				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.");
				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()));
				}
				}
				}
				}

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

				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;
				}
				} // anonymous namespace

				bool renameVRegs(MachineBasicBlock *MBB,
				std::vector<unsigned> &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;
				}

This is an archive of the discontinued LLVM Phabricator instance.

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

Details

Diff Detail

Event Timeline

Revision Contents

Diff 218557

llvm/lib/CodeGen/CMakeLists.txt

llvm/lib/CodeGen/MIRCanonicalizerPass.cpp

llvm/lib/CodeGen/MIRVRegNamerUtils.h

llvm/lib/CodeGen/MIRVRegNamerUtils.cpp

This is an archive of the discontinued LLVM Phabricator instance.

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

Details

Diff Detail

Event Timeline

Revision Contents

Diff 218557

llvm/lib/CodeGen/CMakeLists.txt

llvm/lib/CodeGen/MIRCanonicalizerPass.cpp

llvm/lib/CodeGen/MIRVRegNamerUtils.h

llvm/lib/CodeGen/MIRVRegNamerUtils.cpp

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