270 lines · cpp
1//==--- MachineLateInstrsCleanup.cpp - Late Instructions Cleanup Pass -----===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This simple pass removes any identical and redundant immediate or address10// loads to the same register. The immediate loads removed can originally be11// the result of rematerialization, while the addresses are redundant frame12// addressing anchor points created during Frame Indices elimination.13//14//===----------------------------------------------------------------------===//15 16#include "llvm/CodeGen/MachineLateInstrsCleanup.h"17#include "llvm/ADT/BitVector.h"18#include "llvm/ADT/PostOrderIterator.h"19#include "llvm/ADT/Statistic.h"20#include "llvm/CodeGen/MachineBasicBlock.h"21#include "llvm/CodeGen/MachineFunction.h"22#include "llvm/CodeGen/MachineFunctionPass.h"23#include "llvm/CodeGen/MachineInstr.h"24#include "llvm/CodeGen/MachineOperand.h"25#include "llvm/CodeGen/TargetInstrInfo.h"26#include "llvm/CodeGen/TargetRegisterInfo.h"27#include "llvm/CodeGen/TargetSubtargetInfo.h"28#include "llvm/InitializePasses.h"29#include "llvm/Pass.h"30#include "llvm/Support/Debug.h"31 32using namespace llvm;33 34#define DEBUG_TYPE "machine-latecleanup"35 36STATISTIC(NumRemoved, "Number of redundant instructions removed.");37 38namespace {39 40class MachineLateInstrsCleanup {41 const TargetRegisterInfo *TRI = nullptr;42 const TargetInstrInfo *TII = nullptr;43 44 // Data structures to map regs to their definitions and kills per MBB.45 struct Reg2MIMap : public SmallDenseMap<Register, MachineInstr *> {46 bool hasIdentical(Register Reg, MachineInstr *ArgMI) {47 MachineInstr *MI = lookup(Reg);48 return MI && MI->isIdenticalTo(*ArgMI);49 }50 };51 typedef SmallDenseMap<Register, TinyPtrVector<MachineInstr *>> Reg2MIVecMap;52 std::vector<Reg2MIMap> RegDefs;53 std::vector<Reg2MIVecMap> RegKills;54 55 // Walk through the instructions in MBB and remove any redundant56 // instructions.57 bool processBlock(MachineBasicBlock *MBB);58 59 void removeRedundantDef(MachineInstr *MI);60 void clearKillsForDef(Register Reg, MachineBasicBlock *MBB,61 BitVector &VisitedPreds, MachineInstr *ToRemoveMI);62 63public:64 bool run(MachineFunction &MF);65};66 67class MachineLateInstrsCleanupLegacy : public MachineFunctionPass {68public:69 static char ID; // Pass identification, replacement for typeid70 71 MachineLateInstrsCleanupLegacy() : MachineFunctionPass(ID) {72 initializeMachineLateInstrsCleanupLegacyPass(73 *PassRegistry::getPassRegistry());74 }75 76 void getAnalysisUsage(AnalysisUsage &AU) const override {77 AU.setPreservesCFG();78 MachineFunctionPass::getAnalysisUsage(AU);79 }80 81 bool runOnMachineFunction(MachineFunction &MF) override;82 83 MachineFunctionProperties getRequiredProperties() const override {84 return MachineFunctionProperties().setNoVRegs();85 }86};87 88} // end anonymous namespace89 90char MachineLateInstrsCleanupLegacy::ID = 0;91 92char &llvm::MachineLateInstrsCleanupID = MachineLateInstrsCleanupLegacy::ID;93 94INITIALIZE_PASS(MachineLateInstrsCleanupLegacy, DEBUG_TYPE,95 "Machine Late Instructions Cleanup Pass", false, false)96 97bool MachineLateInstrsCleanupLegacy::runOnMachineFunction(MachineFunction &MF) {98 if (skipFunction(MF.getFunction()))99 return false;100 101 return MachineLateInstrsCleanup().run(MF);102}103 104PreservedAnalyses105MachineLateInstrsCleanupPass::run(MachineFunction &MF,106 MachineFunctionAnalysisManager &MFAM) {107 MFPropsModifier _(*this, MF);108 if (!MachineLateInstrsCleanup().run(MF))109 return PreservedAnalyses::all();110 auto PA = getMachineFunctionPassPreservedAnalyses();111 PA.preserveSet<CFGAnalyses>();112 return PA;113}114 115bool MachineLateInstrsCleanup::run(MachineFunction &MF) {116 TRI = MF.getSubtarget().getRegisterInfo();117 TII = MF.getSubtarget().getInstrInfo();118 119 RegDefs.clear();120 RegDefs.resize(MF.getNumBlockIDs());121 RegKills.clear();122 RegKills.resize(MF.getNumBlockIDs());123 124 // Visit all MBBs in an order that maximises the reuse from predecessors.125 bool Changed = false;126 ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);127 for (MachineBasicBlock *MBB : RPOT)128 Changed |= processBlock(MBB);129 130 return Changed;131}132 133// Clear any preceding kill flag on Reg after removing a redundant134// definition.135void MachineLateInstrsCleanup::clearKillsForDef(Register Reg,136 MachineBasicBlock *MBB,137 BitVector &VisitedPreds,138 MachineInstr *ToRemoveMI) {139 VisitedPreds.set(MBB->getNumber());140 141 // Clear kill flag(s) in MBB, that have been seen after the preceding142 // definition. If Reg or one of its subregs was killed, it would actually143 // be ok to stop after removing that (and any other) kill-flag, but it144 // doesn't seem noticeably faster while it would be a bit more complicated.145 Reg2MIVecMap &MBBKills = RegKills[MBB->getNumber()];146 if (auto Kills = MBBKills.find(Reg); Kills != MBBKills.end())147 for (auto *KillMI : Kills->second)148 KillMI->clearRegisterKills(Reg, TRI);149 150 // Definition in current MBB: done.151 Reg2MIMap &MBBDefs = RegDefs[MBB->getNumber()];152 MachineInstr *DefMI = MBBDefs[Reg];153 assert(DefMI->isIdenticalTo(*ToRemoveMI) && "Previous def not identical?");154 if (DefMI->getParent() == MBB)155 return;156 157 // If an earlier def is not in MBB, continue in predecessors.158 if (!MBB->isLiveIn(Reg))159 MBB->addLiveIn(Reg);160 assert(!MBB->pred_empty() && "Predecessor def not found!");161 for (MachineBasicBlock *Pred : MBB->predecessors())162 if (!VisitedPreds.test(Pred->getNumber()))163 clearKillsForDef(Reg, Pred, VisitedPreds, ToRemoveMI);164}165 166void MachineLateInstrsCleanup::removeRedundantDef(MachineInstr *MI) {167 Register Reg = MI->getOperand(0).getReg();168 BitVector VisitedPreds(MI->getMF()->getNumBlockIDs());169 clearKillsForDef(Reg, MI->getParent(), VisitedPreds, MI);170 MI->eraseFromParent();171 ++NumRemoved;172}173 174// Return true if MI is a potential candidate for reuse/removal and if so175// also the register it defines in DefedReg. A candidate is a simple176// instruction that does not touch memory, has only one register definition177// and the only reg it may use is FrameReg. Typically this is an immediate178// load or a load-address instruction.179static bool isCandidate(const MachineInstr *MI, Register &DefedReg,180 Register FrameReg) {181 DefedReg = MCRegister::NoRegister;182 bool SawStore = true;183 if (!MI->isSafeToMove(SawStore) || MI->isImplicitDef() || MI->isInlineAsm())184 return false;185 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {186 const MachineOperand &MO = MI->getOperand(i);187 if (MO.isReg()) {188 if (MO.isDef()) {189 if (i == 0 && !MO.isImplicit() && !MO.isDead())190 DefedReg = MO.getReg();191 else192 return false;193 } else if (MO.getReg() && MO.getReg() != FrameReg)194 return false;195 } else if (!(MO.isImm() || MO.isCImm() || MO.isFPImm() || MO.isCPI() ||196 MO.isGlobal() || MO.isSymbol()))197 return false;198 }199 return DefedReg.isValid();200}201 202bool MachineLateInstrsCleanup::processBlock(MachineBasicBlock *MBB) {203 bool Changed = false;204 Reg2MIMap &MBBDefs = RegDefs[MBB->getNumber()];205 Reg2MIVecMap &MBBKills = RegKills[MBB->getNumber()];206 207 // Find reusable definitions in the predecessor(s).208 if (!MBB->pred_empty() && !MBB->isEHPad() &&209 !MBB->isInlineAsmBrIndirectTarget()) {210 MachineBasicBlock *FirstPred = *MBB->pred_begin();211 for (auto [Reg, DefMI] : RegDefs[FirstPred->getNumber()])212 if (llvm::all_of(213 drop_begin(MBB->predecessors()),214 [&, &Reg = Reg, &DefMI = DefMI](const MachineBasicBlock *Pred) {215 return RegDefs[Pred->getNumber()].hasIdentical(Reg, DefMI);216 })) {217 MBBDefs[Reg] = DefMI;218 LLVM_DEBUG(dbgs() << "Reusable instruction from pred(s): in "219 << printMBBReference(*MBB) << ": " << *DefMI);220 }221 }222 223 // Process MBB.224 MachineFunction *MF = MBB->getParent();225 const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();226 Register FrameReg = TRI->getFrameRegister(*MF);227 for (MachineInstr &MI : llvm::make_early_inc_range(*MBB)) {228 // If FrameReg is modified, no previous load-address instructions (using229 // it) are valid.230 if (MI.modifiesRegister(FrameReg, TRI)) {231 MBBDefs.clear();232 MBBKills.clear();233 continue;234 }235 236 Register DefedReg;237 bool IsCandidate = isCandidate(&MI, DefedReg, FrameReg);238 239 // Check for an earlier identical and reusable instruction.240 if (IsCandidate && MBBDefs.hasIdentical(DefedReg, &MI)) {241 LLVM_DEBUG(dbgs() << "Removing redundant instruction in "242 << printMBBReference(*MBB) << ": " << MI);243 removeRedundantDef(&MI);244 Changed = true;245 continue;246 }247 248 // Clear any entries in map that MI clobbers.249 for (auto DefI : llvm::make_early_inc_range(MBBDefs)) {250 Register Reg = DefI.first;251 if (MI.modifiesRegister(Reg, TRI)) {252 MBBDefs.erase(Reg);253 MBBKills.erase(Reg);254 } else if (MI.findRegisterUseOperandIdx(Reg, TRI, true /*isKill*/) != -1)255 // Keep track of all instructions that fully or partially kills Reg.256 MBBKills[Reg].push_back(&MI);257 }258 259 // Record this MI for potential later reuse.260 if (IsCandidate) {261 LLVM_DEBUG(dbgs() << "Found interesting instruction in "262 << printMBBReference(*MBB) << ": " << MI);263 MBBDefs[DefedReg] = &MI;264 assert(!MBBKills.count(DefedReg) && "Should already have been removed.");265 }266 }267 268 return Changed;269}270