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
25using namespace llvm;
26
27static 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(key: MO.getParent()))
45 return Reg;
46 }
47 }
48 return 0;
49}
50
51static 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
66static void extractInstrFromFunction(Oracle &O, MachineFunction &MF) {
67 MachineDominatorTree MDT;
68 MDT.calculate(F&: 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(I: 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: *TII, MI))
83 continue;
84 if (!O.shouldKeep())
85 ToDelete.insert(X: &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(RegNo: 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(A: BB)) {
112 while (NewReg == 0 && BB) {
113 NewReg = getPrevDefOfRCInMBB(MBB&: *BB, RI, RC: RegRC, Ty: RegTy, ExcludeMIs&: 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(VReg: 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(RegOp: MO);
134 if (MO.getSubReg())
135 State |= RegState::Undef;
136
137 BuildMI(BB&: *EntryMBB, I: EntryInsPt, MIMD: DebugLoc(), MCID: TII->get(Opcode: ImpDef))
138 .addReg(RegNo: NewReg, flags: State, SubReg: 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
154static 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&: *MF);
158 }
159}
160
161void llvm::reduceInstructionsMIRDeltaPass(TestRunner &Test) {
162 runDeltaPass(Test, ExtractChunksFromModule: extractInstrFromModule, Message: "Reducing Instructions");
163}
164