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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This simple pass removes any identical and redundant immediate or address 10 // loads to the same register. The immediate loads removed can originally be 11 // the result of rematerialization, while the addresses are redundant frame 12 // 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 32 using namespace llvm; 33 34 #define DEBUG_TYPE "machine-latecleanup" 35 36 STATISTIC(NumRemoved, "Number of redundant instructions removed."); 37 38 namespace { 39 40 class 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 redundant 56 // 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 63 public: 64 bool run(MachineFunction &MF); 65 }; 66 67 class MachineLateInstrsCleanupLegacy : public MachineFunctionPass { 68 public: 69 static char ID; // Pass identification, replacement for typeid 70 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 namespace 89 90 char MachineLateInstrsCleanupLegacy::ID = 0; 91 92 char &llvm::MachineLateInstrsCleanupID = MachineLateInstrsCleanupLegacy::ID; 93 94 INITIALIZE_PASS(MachineLateInstrsCleanupLegacy, DEBUG_TYPE, 95 "Machine Late Instructions Cleanup Pass", false, false) 96 97 bool MachineLateInstrsCleanupLegacy::runOnMachineFunction(MachineFunction &MF) { 98 if (skipFunction(MF.getFunction())) 99 return false; 100 101 return MachineLateInstrsCleanup().run(MF); 102 } 103 104 PreservedAnalyses 105 MachineLateInstrsCleanupPass::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 115 bool 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 redundant 134 // definition. 135 void 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 preceding 142 // definition. If Reg or one of its subregs was killed, it would actually 143 // be ok to stop after removing that (and any other) kill-flag, but it 144 // 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 166 void 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 so 175 // also the register it defines in DefedReg. A candidate is a simple 176 // instruction that does not touch memory, has only one register definition 177 // and the only reg it may use is FrameReg. Typically this is an immediate 178 // load or a load-address instruction. 179 static 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 else 192 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 202 bool 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 (using 229 // 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