diff options
Diffstat (limited to 'lib/CodeGen/MIRCanonicalizerPass.cpp')
-rw-r--r-- | lib/CodeGen/MIRCanonicalizerPass.cpp | 359 |
1 files changed, 14 insertions, 345 deletions
diff --git a/lib/CodeGen/MIRCanonicalizerPass.cpp b/lib/CodeGen/MIRCanonicalizerPass.cpp index f49bc854e23f..c9bb5461aa3c 100644 --- a/lib/CodeGen/MIRCanonicalizerPass.cpp +++ b/lib/CodeGen/MIRCanonicalizerPass.cpp @@ -23,12 +23,14 @@ // //===----------------------------------------------------------------------===// +#include "MIRVRegNamerUtils.h" #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/Debug.h" #include "llvm/Support/raw_ostream.h" #include <queue> @@ -71,28 +73,6 @@ public: } // 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; @@ -190,7 +170,7 @@ static bool rescheduleCanonically(unsigned &PseudoIdempotentInstCount, if (!MO.isReg()) continue; - if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) + if (Register::isVirtualRegister(MO.getReg())) continue; if (!MO.isDef()) @@ -207,7 +187,7 @@ static bool rescheduleCanonically(unsigned &PseudoIdempotentInstCount, continue; MachineOperand &MO = II->getOperand(0); - if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg())) + if (!MO.isReg() || !Register::isVirtualRegister(MO.getReg())) continue; if (!MO.isDef()) continue; @@ -220,7 +200,7 @@ static bool rescheduleCanonically(unsigned &PseudoIdempotentInstCount, } if (II->getOperand(i).isReg()) { - if (!TargetRegisterInfo::isVirtualRegister(II->getOperand(i).getReg())) + if (!Register::isVirtualRegister(II->getOperand(i).getReg())) if (llvm::find(PhysRegDefs, II->getOperand(i).getReg()) == PhysRegDefs.end()) { continue; @@ -340,12 +320,12 @@ static bool propagateLocalCopies(MachineBasicBlock *MBB) { if (!MI->getOperand(1).isReg()) continue; - const unsigned Dst = MI->getOperand(0).getReg(); - const unsigned Src = MI->getOperand(1).getReg(); + const Register Dst = MI->getOperand(0).getReg(); + const Register Src = MI->getOperand(1).getReg(); - if (!TargetRegisterInfo::isVirtualRegister(Dst)) + if (!Register::isVirtualRegister(Dst)) continue; - if (!TargetRegisterInfo::isVirtualRegister(Src)) + if (!Register::isVirtualRegister(Src)) continue; // Not folding COPY instructions if regbankselect has not set the RCs. // Why are we only considering Register Classes? Because the verifier @@ -370,258 +350,6 @@ static bool propagateLocalCopies(MachineBasicBlock *MBB) { 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 unsigned Dst = MI->getOperand(0).getReg(); - DoesMISideEffect |= !TargetRegisterInfo::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 (TargetRegisterInfo::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 (!TargetRegisterInfo::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) { bool Changed = false; @@ -646,9 +374,7 @@ static bool doDefKillClear(MachineBasicBlock *MBB) { static bool runOnBasicBlock(MachineBasicBlock *MBB, std::vector<StringRef> &bbNames, - std::vector<unsigned> &renamedInOtherBB, - unsigned &basicBlockNum, unsigned &VRegGapIndex, - NamedVRegCursor &NVC) { + unsigned &basicBlockNum, NamedVRegCursor &NVC) { if (CanonicalizeBasicBlockNumber != ~0U) { if (CanonicalizeBasicBlockNumber != basicBlockNum++) @@ -687,74 +413,20 @@ static bool runOnBasicBlock(MachineBasicBlock *MBB, Changed |= rescheduleCanonically(IdempotentInstCount, MBB); LLVM_DEBUG(dbgs() << "MBB After Scheduling:\n"; MBB->dump();); - 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() && TargetRegisterInfo::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); + Changed |= NVC.renameVRegs(MBB); // 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 // them alphabetically. Eventually we wont need SkipVRegs because we will use // named vregs instead. if (IdempotentInstCount) - NVC.SkipVRegs(); + NVC.skipVRegs(); auto MII = MBB->begin(); for (unsigned i = 0; i < IdempotentInstCount && MII != MBB->end(); ++i) { MachineInstr &MI = *MII++; Changed = true; - unsigned vRegToRename = MI.getOperand(0).getReg(); + Register vRegToRename = MI.getOperand(0).getReg(); auto Rename = NVC.createVirtualRegister(vRegToRename); std::vector<MachineOperand *> RenameMOs; @@ -799,9 +471,7 @@ bool MIRCanonicalizer::runOnMachineFunction(MachineFunction &MF) { << "\n\n================================================\n\n";); std::vector<StringRef> BBNames; - std::vector<unsigned> RenamedInOtherBB; - unsigned GapIdx = 0; unsigned BBNum = 0; bool Changed = false; @@ -809,8 +479,7 @@ bool MIRCanonicalizer::runOnMachineFunction(MachineFunction &MF) { MachineRegisterInfo &MRI = MF.getRegInfo(); NamedVRegCursor NVC(MRI); for (auto MBB : RPOList) - Changed |= - runOnBasicBlock(MBB, BBNames, RenamedInOtherBB, BBNum, GapIdx, NVC); + Changed |= runOnBasicBlock(MBB, BBNames, BBNum, NVC); return Changed; } |