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