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