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 
16 #include "llvm/CodeGen/MachineDominators.h"
17 #include "llvm/CodeGen/MachineFunction.h"
18 #include "llvm/CodeGen/MachineFunctionPass.h"
19 #include "llvm/CodeGen/MachineRegisterInfo.h"
20 #include "llvm/CodeGen/TargetInstrInfo.h"
21 
22 using namespace llvm;
23 
24 static Register getPrevDefOfRCInMBB(MachineBasicBlock &MBB,
25                                     MachineBasicBlock::reverse_iterator &RI,
26                                     const RegClassOrRegBank &RC, LLT Ty,
27                                     SetVector<MachineInstr *> &ExcludeMIs) {
28   auto MRI = &MBB.getParent()->getRegInfo();
29   for (MachineBasicBlock::reverse_instr_iterator E = MBB.instr_rend(); RI != E;
30        ++RI) {
31     auto &MI = *RI;
32     // All Def operands explicit and implicit.
33     for (auto &MO : MI.operands()) {
34       if (!MO.isReg() || !MO.isDef())
35         continue;
36       auto Reg = MO.getReg();
37       if (Register::isPhysicalRegister(Reg))
38         continue;
39 
40       if (MRI->getRegClassOrRegBank(Reg) == RC && MRI->getType(Reg) == Ty &&
41           !ExcludeMIs.count(MO.getParent()))
42         return Reg;
43     }
44   }
45   return 0;
46 }
47 
48 static void extractInstrFromFunction(Oracle &O, MachineFunction &MF) {
49   MachineDominatorTree MDT;
50   MDT.runOnMachineFunction(MF);
51 
52   auto MRI = &MF.getRegInfo();
53   SetVector<MachineInstr *> ToDelete;
54 
55   MachineInstr *TopMI = nullptr;
56 
57   // Mark MIs for deletion according to some criteria.
58   for (auto &MBB : MF) {
59     for (auto &MI : MBB) {
60       if (MI.isTerminator())
61         continue;
62       if (MBB.isEntryBlock() && !TopMI) {
63         TopMI = &MI;
64         continue;
65       }
66       if (!O.shouldKeep())
67         ToDelete.insert(&MI);
68     }
69   }
70 
71   // For each MI to be deleted update users of regs defined by that MI to use
72   // some other dominating definition (that is not to be deleted).
73   for (auto *MI : ToDelete) {
74     for (auto &MO : MI->operands()) {
75       if (!MO.isReg() || !MO.isDef())
76         continue;
77       auto Reg = MO.getReg();
78       if (Register::isPhysicalRegister(Reg))
79         continue;
80       auto UI = MRI->use_begin(Reg);
81       auto UE = MRI->use_end();
82 
83       const auto &RegRC = MRI->getRegClassOrRegBank(Reg);
84       LLT RegTy = MRI->getType(Reg);
85 
86       Register NewReg = 0;
87       // If this is not a physical register and there are some uses.
88       if (UI != UE) {
89         MachineBasicBlock::reverse_iterator RI(*MI);
90         MachineBasicBlock *BB = MI->getParent();
91         ++RI;
92         while (NewReg == 0 && BB) {
93           NewReg = getPrevDefOfRCInMBB(*BB, RI, RegRC, RegTy, ToDelete);
94           // Prepare for idom(BB).
95           if (auto *IDM = MDT.getNode(BB)->getIDom()) {
96             BB = IDM->getBlock();
97             RI = BB->rbegin();
98           } else {
99             BB = nullptr;
100           }
101         }
102       }
103 
104       // If no dominating definition was found then add an implicit one to the
105       // first instruction in the entry block.
106 
107       // FIXME: This should really insert IMPLICIT_DEF or G_IMPLICIT_DEF. We
108       // need to refine the reduction quality metric from number of serialized
109       // bytes to continue progressing if we're going to introduce new
110       // instructions.
111       if (!NewReg && TopMI) {
112         NewReg = MRI->cloneVirtualRegister(Reg);
113         TopMI->addOperand(MachineOperand::CreateReg(
114             NewReg, true /*IsDef*/, true /*IsImp*/, false /*IsKill*/,
115             MO.isDead(), MO.isUndef(), MO.isEarlyClobber(), MO.getSubReg(),
116             /*IsDebug*/ false, MO.isInternalRead()));
117       }
118 
119       // Update all uses.
120       while (UI != UE) {
121         auto &UMO = *UI++;
122         UMO.setReg(NewReg);
123       }
124     }
125   }
126 
127   // Finally delete the MIs.
128   for (auto *MI : ToDelete)
129     MI->eraseFromParent();
130 }
131 
132 static void extractInstrFromModule(Oracle &O, ReducerWorkItem &WorkItem) {
133   for (const Function &F : WorkItem.getModule()) {
134     if (MachineFunction *MF = WorkItem.MMI->getMachineFunction(F))
135       extractInstrFromFunction(O, *MF);
136   }
137 }
138 
139 void llvm::reduceInstructionsMIRDeltaPass(TestRunner &Test) {
140   outs() << "*** Reducing Instructions...\n";
141   runDeltaPass(Test, extractInstrFromModule);
142 }
143