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