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 TargetRegisterClass *RC,
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->getRegClass(Reg) == RC && !ExcludeMIs.count(MO.getParent()))
41         return Reg;
42     }
43   }
44   return 0;
45 }
46 
47 static void extractInstrFromModule(Oracle &O, MachineFunction &MF) {
48   MachineDominatorTree MDT;
49   MDT.runOnMachineFunction(MF);
50 
51   auto MRI = &MF.getRegInfo();
52   SetVector<MachineInstr *> ToDelete;
53 
54   MachineInstr *TopMI = nullptr;
55 
56   // Mark MIs for deletion according to some criteria.
57   for (auto &MBB : MF) {
58     for (auto &MI : MBB) {
59       if (MI.isTerminator())
60         continue;
61       if (MBB.isEntryBlock() && !TopMI) {
62         TopMI = &MI;
63         continue;
64       }
65       if (!O.shouldKeep())
66         ToDelete.insert(&MI);
67     }
68   }
69 
70   // For each MI to be deleted update users of regs defined by that MI to use
71   // some other dominating definition (that is not to be deleted).
72   for (auto *MI : ToDelete) {
73     for (auto &MO : MI->operands()) {
74       if (!MO.isReg() || !MO.isDef())
75         continue;
76       auto Reg = MO.getReg();
77       if (Register::isPhysicalRegister(Reg))
78         continue;
79       auto UI = MRI->use_begin(Reg);
80       auto UE = MRI->use_end();
81 
82       auto RegRC = MRI->getRegClass(Reg);
83       Register NewReg = 0;
84       // If this is not a physical register and there are some uses.
85       if (UI != UE) {
86         MachineBasicBlock::reverse_iterator RI(*MI);
87         MachineBasicBlock *BB = MI->getParent();
88         ++RI;
89         while (NewReg == 0 && BB) {
90           NewReg = getPrevDefOfRCInMBB(*BB, RI, RegRC, ToDelete);
91           // Prepare for idom(BB).
92           if (auto *IDM = MDT.getNode(BB)->getIDom()) {
93             BB = IDM->getBlock();
94             RI = BB->rbegin();
95           } else {
96             BB = nullptr;
97           }
98         }
99       }
100 
101       // If no dominating definition was found then add an implicit one to the
102       // first instruction in the entry block.
103       if (!NewReg && TopMI) {
104         NewReg = MRI->createVirtualRegister(RegRC);
105         TopMI->addOperand(MachineOperand::CreateReg(
106             NewReg, true /*IsDef*/, true /*IsImp*/, false /*IsKill*/));
107       }
108 
109       // Update all uses.
110       while (UI != UE) {
111         auto &UMO = *UI++;
112         UMO.setReg(NewReg);
113       }
114     }
115   }
116 
117   // Finally delete the MIs.
118   for (auto *MI : ToDelete)
119     MI->eraseFromParent();
120 }
121 
122 void llvm::reduceInstructionsMIRDeltaPass(TestRunner &Test) {
123   outs() << "*** Reducing Instructions...\n";
124   runDeltaPass(Test, extractInstrFromModule);
125 }
126