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