1 //===- ReduceInstructionsMIR.cpp - Specialized Delta 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 file implements a function which calls the Generic Delta pass in order 10 // to reduce uninteresting MachineInstr from the MachineFunction. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "ReduceInstructionsMIR.h" 15 #include "Delta.h" 16 17 #include "llvm/ADT/SetVector.h" 18 #include "llvm/CodeGen/MachineDominators.h" 19 #include "llvm/CodeGen/MachineFunction.h" 20 #include "llvm/CodeGen/MachineFunctionPass.h" 21 #include "llvm/CodeGen/MachineModuleInfo.h" 22 #include "llvm/CodeGen/MachineRegisterInfo.h" 23 #include "llvm/CodeGen/TargetInstrInfo.h" 24 25 using namespace llvm; 26 27 static Register getPrevDefOfRCInMBB(MachineBasicBlock &MBB, 28 MachineBasicBlock::reverse_iterator &RI, 29 const RegClassOrRegBank &RC, LLT Ty, 30 SetVector<MachineInstr *> &ExcludeMIs) { 31 auto MRI = &MBB.getParent()->getRegInfo(); 32 for (MachineBasicBlock::reverse_instr_iterator E = MBB.instr_rend(); RI != E; 33 ++RI) { 34 auto &MI = *RI; 35 // All Def operands explicit and implicit. 36 for (auto &MO : MI.operands()) { 37 if (!MO.isReg() || !MO.isDef() || MO.isDead()) 38 continue; 39 auto Reg = MO.getReg(); 40 if (Reg.isPhysical()) 41 continue; 42 43 if (MRI->getRegClassOrRegBank(Reg) == RC && MRI->getType(Reg) == Ty && 44 !ExcludeMIs.count(MO.getParent())) 45 return Reg; 46 } 47 } 48 return 0; 49 } 50 51 static bool shouldNotRemoveInstruction(const TargetInstrInfo &TII, 52 const MachineInstr &MI) { 53 if (MI.isTerminator()) 54 return true; 55 56 // The MIR is almost certainly going to be invalid if frame instructions are 57 // deleted individually since they need to come in balanced pairs, so don't 58 // try to delete them. 59 if (MI.getOpcode() == TII.getCallFrameSetupOpcode() || 60 MI.getOpcode() == TII.getCallFrameDestroyOpcode()) 61 return true; 62 63 return false; 64 } 65 66 static void extractInstrFromFunction(Oracle &O, MachineFunction &MF) { 67 MachineDominatorTree MDT; 68 MDT.recalculate(MF); 69 70 auto MRI = &MF.getRegInfo(); 71 SetVector<MachineInstr *> ToDelete; 72 73 const TargetSubtargetInfo &STI = MF.getSubtarget(); 74 const TargetInstrInfo *TII = STI.getInstrInfo(); 75 MachineBasicBlock *EntryMBB = &*MF.begin(); 76 MachineBasicBlock::iterator EntryInsPt = 77 EntryMBB->SkipPHIsLabelsAndDebug(EntryMBB->begin()); 78 79 // Mark MIs for deletion according to some criteria. 80 for (auto &MBB : MF) { 81 for (auto &MI : MBB) { 82 if (shouldNotRemoveInstruction(*TII, MI)) 83 continue; 84 if (!O.shouldKeep()) 85 ToDelete.insert(&MI); 86 } 87 } 88 89 // For each MI to be deleted update users of regs defined by that MI to use 90 // some other dominating definition (that is not to be deleted). 91 for (auto *MI : ToDelete) { 92 for (auto &MO : MI->operands()) { 93 if (!MO.isReg() || !MO.isDef() || MO.isDead()) 94 continue; 95 auto Reg = MO.getReg(); 96 if (Reg.isPhysical()) 97 continue; 98 auto UI = MRI->use_begin(Reg); 99 auto UE = MRI->use_end(); 100 101 const auto &RegRC = MRI->getRegClassOrRegBank(Reg); 102 LLT RegTy = MRI->getType(Reg); 103 104 Register NewReg = 0; 105 // If this is not a physical register and there are some uses. 106 if (UI != UE) { 107 MachineBasicBlock::reverse_iterator RI(*MI); 108 MachineBasicBlock *BB = MI->getParent(); 109 ++RI; 110 111 if (MDT.isReachableFromEntry(BB)) { 112 while (NewReg == 0 && BB) { 113 NewReg = getPrevDefOfRCInMBB(*BB, RI, RegRC, RegTy, ToDelete); 114 // Prepare for idom(BB). 115 if (auto *IDM = MDT.getNode(BB)->getIDom()) { 116 BB = IDM->getBlock(); 117 RI = BB->rbegin(); 118 } else { 119 BB = nullptr; 120 } 121 } 122 } 123 } 124 125 // If no dominating definition was found then add an implicit def to the 126 // top of the entry block. 127 if (!NewReg) { 128 NewReg = MRI->cloneVirtualRegister(Reg); 129 bool IsGeneric = MRI->getRegClassOrNull(Reg) == nullptr; 130 unsigned ImpDef = IsGeneric ? TargetOpcode::G_IMPLICIT_DEF 131 : TargetOpcode::IMPLICIT_DEF; 132 133 unsigned State = getRegState(MO); 134 if (MO.getSubReg()) 135 State |= RegState::Undef; 136 137 BuildMI(*EntryMBB, EntryInsPt, DebugLoc(), TII->get(ImpDef)) 138 .addReg(NewReg, State, MO.getSubReg()); 139 } 140 141 // Update all uses. 142 while (UI != UE) { 143 auto &UMO = *UI++; 144 UMO.setReg(NewReg); 145 } 146 } 147 } 148 149 // Finally delete the MIs. 150 for (auto *MI : ToDelete) 151 MI->eraseFromParent(); 152 } 153 154 static void extractInstrFromModule(Oracle &O, ReducerWorkItem &WorkItem) { 155 for (const Function &F : WorkItem.getModule()) { 156 if (MachineFunction *MF = WorkItem.MMI->getMachineFunction(F)) 157 extractInstrFromFunction(O, *MF); 158 } 159 } 160 161 void llvm::reduceInstructionsMIRDeltaPass(TestRunner &Test) { 162 runDeltaPass(Test, extractInstrFromModule, "Reducing Instructions"); 163 } 164