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/ADT/BitVector.h" 17 #include "llvm/ADT/PostOrderIterator.h" 18 #include "llvm/ADT/Statistic.h" 19 #include "llvm/CodeGen/MachineBasicBlock.h" 20 #include "llvm/CodeGen/MachineFunction.h" 21 #include "llvm/CodeGen/MachineFunctionPass.h" 22 #include "llvm/CodeGen/MachineInstr.h" 23 #include "llvm/CodeGen/MachineOperand.h" 24 #include "llvm/CodeGen/TargetInstrInfo.h" 25 #include "llvm/CodeGen/TargetRegisterInfo.h" 26 #include "llvm/CodeGen/TargetSubtargetInfo.h" 27 #include "llvm/InitializePasses.h" 28 #include "llvm/Pass.h" 29 #include "llvm/Support/Debug.h" 30 31 using namespace llvm; 32 33 #define DEBUG_TYPE "machine-latecleanup" 34 35 STATISTIC(NumRemoved, "Number of redundant instructions removed."); 36 37 namespace { 38 39 class MachineLateInstrsCleanup : public MachineFunctionPass { 40 const TargetRegisterInfo *TRI = nullptr; 41 const TargetInstrInfo *TII = nullptr; 42 43 // Data structures to map regs to their definitions and kills per MBB. 44 struct Reg2MIMap : public SmallDenseMap<Register, MachineInstr *> { 45 bool hasIdentical(Register Reg, MachineInstr *ArgMI) { 46 MachineInstr *MI = lookup(Reg); 47 return MI && MI->isIdenticalTo(*ArgMI); 48 } 49 }; 50 51 std::vector<Reg2MIMap> RegDefs; 52 std::vector<Reg2MIMap> RegKills; 53 54 // Walk through the instructions in MBB and remove any redundant 55 // instructions. 56 bool processBlock(MachineBasicBlock *MBB); 57 58 void removeRedundantDef(MachineInstr *MI); 59 void clearKillsForDef(Register Reg, MachineBasicBlock *MBB, 60 BitVector &VisitedPreds); 61 62 public: 63 static char ID; // Pass identification, replacement for typeid 64 65 MachineLateInstrsCleanup() : MachineFunctionPass(ID) { 66 initializeMachineLateInstrsCleanupPass(*PassRegistry::getPassRegistry()); 67 } 68 69 void getAnalysisUsage(AnalysisUsage &AU) const override { 70 AU.setPreservesCFG(); 71 MachineFunctionPass::getAnalysisUsage(AU); 72 } 73 74 bool runOnMachineFunction(MachineFunction &MF) override; 75 76 MachineFunctionProperties getRequiredProperties() const override { 77 return MachineFunctionProperties().set( 78 MachineFunctionProperties::Property::NoVRegs); 79 } 80 }; 81 82 } // end anonymous namespace 83 84 char MachineLateInstrsCleanup::ID = 0; 85 86 char &llvm::MachineLateInstrsCleanupID = MachineLateInstrsCleanup::ID; 87 88 INITIALIZE_PASS(MachineLateInstrsCleanup, DEBUG_TYPE, 89 "Machine Late Instructions Cleanup Pass", false, false) 90 91 bool MachineLateInstrsCleanup::runOnMachineFunction(MachineFunction &MF) { 92 if (skipFunction(MF.getFunction())) 93 return false; 94 95 TRI = MF.getSubtarget().getRegisterInfo(); 96 TII = MF.getSubtarget().getInstrInfo(); 97 98 RegDefs.clear(); 99 RegDefs.resize(MF.getNumBlockIDs()); 100 RegKills.clear(); 101 RegKills.resize(MF.getNumBlockIDs()); 102 103 // Visit all MBBs in an order that maximises the reuse from predecessors. 104 bool Changed = false; 105 ReversePostOrderTraversal<MachineFunction *> RPOT(&MF); 106 for (MachineBasicBlock *MBB : RPOT) 107 Changed |= processBlock(MBB); 108 109 return Changed; 110 } 111 112 // Clear any preceding kill flag on Reg after removing a redundant 113 // definition. 114 void MachineLateInstrsCleanup::clearKillsForDef(Register Reg, 115 MachineBasicBlock *MBB, 116 BitVector &VisitedPreds) { 117 VisitedPreds.set(MBB->getNumber()); 118 119 // Kill flag in MBB 120 if (MachineInstr *KillMI = RegKills[MBB->getNumber()].lookup(Reg)) { 121 KillMI->clearRegisterKills(Reg, TRI); 122 return; 123 } 124 125 // Def in MBB (missing kill flag) 126 if (MachineInstr *DefMI = RegDefs[MBB->getNumber()].lookup(Reg)) 127 if (DefMI->getParent() == MBB) 128 return; 129 130 // If an earlier def is not in MBB, continue in predecessors. 131 if (!MBB->isLiveIn(Reg)) 132 MBB->addLiveIn(Reg); 133 assert(!MBB->pred_empty() && "Predecessor def not found!"); 134 for (MachineBasicBlock *Pred : MBB->predecessors()) 135 if (!VisitedPreds.test(Pred->getNumber())) 136 clearKillsForDef(Reg, Pred, VisitedPreds); 137 } 138 139 void MachineLateInstrsCleanup::removeRedundantDef(MachineInstr *MI) { 140 Register Reg = MI->getOperand(0).getReg(); 141 BitVector VisitedPreds(MI->getMF()->getNumBlockIDs()); 142 clearKillsForDef(Reg, MI->getParent(), VisitedPreds); 143 MI->eraseFromParent(); 144 ++NumRemoved; 145 } 146 147 // Return true if MI is a potential candidate for reuse/removal and if so 148 // also the register it defines in DefedReg. A candidate is a simple 149 // instruction that does not touch memory, has only one register definition 150 // and the only reg it may use is FrameReg. Typically this is an immediate 151 // load or a load-address instruction. 152 static bool isCandidate(const MachineInstr *MI, Register &DefedReg, 153 Register FrameReg) { 154 DefedReg = MCRegister::NoRegister; 155 bool SawStore = true; 156 if (!MI->isSafeToMove(SawStore) || MI->isImplicitDef() || MI->isInlineAsm()) 157 return false; 158 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 159 const MachineOperand &MO = MI->getOperand(i); 160 if (MO.isReg()) { 161 if (MO.isDef()) { 162 if (i == 0 && !MO.isImplicit() && !MO.isDead()) 163 DefedReg = MO.getReg(); 164 else 165 return false; 166 } else if (MO.getReg() && MO.getReg() != FrameReg) 167 return false; 168 } else if (!(MO.isImm() || MO.isCImm() || MO.isFPImm() || MO.isCPI() || 169 MO.isGlobal() || MO.isSymbol())) 170 return false; 171 } 172 return DefedReg.isValid(); 173 } 174 175 bool MachineLateInstrsCleanup::processBlock(MachineBasicBlock *MBB) { 176 bool Changed = false; 177 Reg2MIMap &MBBDefs = RegDefs[MBB->getNumber()]; 178 Reg2MIMap &MBBKills = RegKills[MBB->getNumber()]; 179 180 // Find reusable definitions in the predecessor(s). 181 if (!MBB->pred_empty() && !MBB->isEHPad() && 182 !MBB->isInlineAsmBrIndirectTarget()) { 183 MachineBasicBlock *FirstPred = *MBB->pred_begin(); 184 for (auto [Reg, DefMI] : RegDefs[FirstPred->getNumber()]) 185 if (llvm::all_of( 186 drop_begin(MBB->predecessors()), 187 [&, &Reg = Reg, &DefMI = DefMI](const MachineBasicBlock *Pred) { 188 return RegDefs[Pred->getNumber()].hasIdentical(Reg, DefMI); 189 })) { 190 MBBDefs[Reg] = DefMI; 191 LLVM_DEBUG(dbgs() << "Reusable instruction from pred(s): in " 192 << printMBBReference(*MBB) << ": " << *DefMI); 193 } 194 } 195 196 // Process MBB. 197 MachineFunction *MF = MBB->getParent(); 198 const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo(); 199 Register FrameReg = TRI->getFrameRegister(*MF); 200 for (MachineInstr &MI : llvm::make_early_inc_range(*MBB)) { 201 // If FrameReg is modified, no previous load-address instructions (using 202 // it) are valid. 203 if (MI.modifiesRegister(FrameReg, TRI)) { 204 MBBDefs.clear(); 205 MBBKills.clear(); 206 continue; 207 } 208 209 Register DefedReg; 210 bool IsCandidate = isCandidate(&MI, DefedReg, FrameReg); 211 212 // Check for an earlier identical and reusable instruction. 213 if (IsCandidate && MBBDefs.hasIdentical(DefedReg, &MI)) { 214 LLVM_DEBUG(dbgs() << "Removing redundant instruction in " 215 << printMBBReference(*MBB) << ": " << MI); 216 removeRedundantDef(&MI); 217 Changed = true; 218 continue; 219 } 220 221 // Clear any entries in map that MI clobbers. 222 for (auto DefI : llvm::make_early_inc_range(MBBDefs)) { 223 Register Reg = DefI.first; 224 if (MI.modifiesRegister(Reg, TRI)) { 225 MBBDefs.erase(Reg); 226 MBBKills.erase(Reg); 227 } else if (MI.findRegisterUseOperandIdx(Reg, TRI, true /*isKill*/) != -1) 228 // Keep track of register kills. 229 MBBKills[Reg] = &MI; 230 } 231 232 // Record this MI for potential later reuse. 233 if (IsCandidate) { 234 LLVM_DEBUG(dbgs() << "Found interesting instruction in " 235 << printMBBReference(*MBB) << ": " << MI); 236 MBBDefs[DefedReg] = &MI; 237 assert(!MBBKills.count(DefedReg) && "Should already have been removed."); 238 } 239 } 240 241 return Changed; 242 } 243