diff --git a/llvm/lib/CodeGen/CMakeLists.txt b/llvm/lib/CodeGen/CMakeLists.txt --- a/llvm/lib/CodeGen/CMakeLists.txt +++ b/llvm/lib/CodeGen/CMakeLists.txt @@ -121,6 +121,7 @@ RegisterPressure.cpp RegisterScavenging.cpp RenameIndependentSubregs.cpp + MIRVRegNamerUtils.cpp MIRCanonicalizerPass.cpp RegisterUsageInfo.cpp RegUsageInfoCollector.cpp diff --git a/llvm/lib/CodeGen/MIRCanonicalizerPass.cpp b/llvm/lib/CodeGen/MIRCanonicalizerPass.cpp --- a/llvm/lib/CodeGen/MIRCanonicalizerPass.cpp +++ b/llvm/lib/CodeGen/MIRCanonicalizerPass.cpp @@ -30,6 +30,7 @@ #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" #include "llvm/Support/raw_ostream.h" +#include "MIRVRegNamerUtils.h" #include @@ -71,28 +72,6 @@ } // 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 &llvm::MIRCanonicalizerID = MIRCanonicalizer::ID; @@ -370,258 +349,6 @@ 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 populateCandidates(MachineBasicBlock *MBB) { - std::vector 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 &VRegs, - std::queue &RegQueue, - std::vector &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 -GetVRegRenameMap(const std::vector &VRegs, - const std::vector &renamedInOtherBB, - MachineRegisterInfo &MRI, NamedVRegCursor &NVC) { - std::map 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(Reg, Rename)); - } - } - - return VRegRenameMap; -} - -static bool doVRegRenaming(std::vector &RenamedInOtherBB, - const std::map &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 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) { bool Changed = false; diff --git a/llvm/lib/CodeGen/MIRVRegNamerUtils.h b/llvm/lib/CodeGen/MIRVRegNamerUtils.h new file mode 100644 --- /dev/null +++ b/llvm/lib/CodeGen/MIRVRegNamerUtils.h @@ -0,0 +1,106 @@ +//===------------ 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 + +using namespace llvm; + +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; + } +}; + +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()); + } +}; + +std::vector populateCandidates(MachineBasicBlock *MBB); + +void doCandidateWalk(std::vector &VRegs, + std::queue &RegQueue, + std::vector &VisitedMIs, + const MachineBasicBlock *MBB); + +std::map +GetVRegRenameMap(const std::vector &VRegs, + const std::vector &renamedInOtherBB, + MachineRegisterInfo &MRI, NamedVRegCursor &NVC); + +bool doVRegRenaming(std::vector &RenamedInOtherBB, + const std::map &VRegRenameMap, + MachineRegisterInfo &MRI); diff --git a/llvm/lib/CodeGen/MIRVRegNamerUtils.cpp b/llvm/lib/CodeGen/MIRVRegNamerUtils.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/CodeGen/MIRVRegNamerUtils.cpp @@ -0,0 +1,221 @@ +//===---------- 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" + +/// 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. +std::vector populateCandidates(MachineBasicBlock *MBB) { + std::vector 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 &VRegs, + std::queue &RegQueue, + std::vector &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 +GetVRegRenameMap(const std::vector &VRegs, + const std::vector &renamedInOtherBB, + MachineRegisterInfo &MRI, NamedVRegCursor &NVC) { + std::map 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(Reg, Rename)); + } + } + + return VRegRenameMap; +} + +bool doVRegRenaming(std::vector &RenamedInOtherBB, + const std::map &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 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; +}