llvm/tools/llvm-reduce/deltas/ReduceInstructionsMIR.cpp

   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.runOnMachineFunction(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 }