1//===-- M68kCollapseMOVEMPass.cpp - Expand MOVEM pass -----------*- C++ -*-===//
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/// \file
10/// `MOVEM` is an instruction that moves multiple registers a time according to
11/// the given mask. Thus sometimes it's pretty expensive.
12/// This file contains a pass that collapses sequential MOVEM instructions into
13/// a single one.
14///
15//===----------------------------------------------------------------------===//
16
17#include "M68k.h"
18#include "M68kFrameLowering.h"
19#include "M68kInstrInfo.h"
20#include "M68kMachineFunction.h"
21#include "M68kSubtarget.h"
22
23#include "llvm/CodeGen/MachineFunctionPass.h"
24#include "llvm/CodeGen/MachineInstrBuilder.h"
25#include "llvm/CodeGen/MachineRegisterInfo.h"
26#include "llvm/IR/EHPersonalities.h"
27#include "llvm/IR/GlobalValue.h"
28#include "llvm/Support/MathExtras.h"
29
30using namespace llvm;
31
32#define DEBUG_TYPE "m68k-collapse-movem"
33#define PASS_NAME "M68k MOVEM collapser pass"
34
35namespace {
36
37enum UpdateType { Ascending, Descending, Intermixed };
38
39/// An abtraction of the MOVEM chain currently processing
40class MOVEMState {
41 MachineBasicBlock::iterator Begin;
42 MachineBasicBlock::iterator End;
43
44 unsigned Base;
45
46 int Start;
47 int Stop;
48
49 unsigned Mask;
50
51 enum class AccessTy { None, Load, Store };
52 AccessTy Access;
53
54public:
55 MOVEMState()
56 : Begin(nullptr), End(nullptr), Base(0), Start(INT_MIN), Stop(INT_MAX),
57 Mask(0), Access(AccessTy::None) {}
58
59 void setBegin(MachineBasicBlock::iterator &MI) {
60 assert(Begin == nullptr);
61 Begin = MI;
62 }
63
64 void setEnd(MachineBasicBlock::iterator &MI) {
65 assert(End == nullptr);
66 End = MI;
67 }
68
69 bool hasBase() const { return Base != 0; }
70
71 unsigned getBase() const {
72 assert(Base);
73 return Base;
74 }
75
76 MachineBasicBlock::iterator begin() {
77 assert(Begin != nullptr);
78 return Begin;
79 }
80
81 MachineBasicBlock::iterator end() {
82 assert(End != nullptr);
83 return End;
84 }
85
86 unsigned getMask() const { return Mask; }
87
88 void setBase(int Value) {
89 assert(!hasBase());
90 Base = Value;
91 }
92
93 // You need to call this before Mask update
94 UpdateType classifyUpdateByMask(unsigned NewMask) const {
95 assert(NewMask && "Mask needs to select at least one register");
96
97 if (NewMask > Mask) {
98 return Ascending;
99 } else if (NewMask < Mask) {
100 return Descending;
101 }
102
103 return Intermixed;
104 }
105
106 bool update(int O, int M) {
107 UpdateType Type = classifyUpdateByMask(NewMask: M);
108 if (Type == Intermixed)
109 return false;
110 if (Start == INT_MIN) {
111 Start = Stop = O;
112 updateMask(Value: M);
113 return true;
114 } else if (Type == Descending && O == Start - 4) {
115 Start -= 4;
116 updateMask(Value: M);
117 return true;
118 } else if (Type == Ascending && O == Stop + 4) {
119 Stop += 4;
120 updateMask(Value: M);
121 return true;
122 }
123
124 return false;
125 }
126
127 int getFinalOffset() const {
128 assert(
129 Start != INT_MIN &&
130 "MOVEM in control mode should increment the address in each iteration");
131 return Start;
132 }
133
134 bool updateMask(unsigned Value) {
135 assert(isUInt<16>(Value) && "Mask must fit 16 bit");
136 assert(!(Value & Mask) &&
137 "This is weird, there should be no intersections");
138 Mask |= Value;
139 return true;
140 }
141
142 void setLoad() { Access = AccessTy::Load; }
143 void setStore() { Access = AccessTy::Store; }
144
145 bool isLoad() const { return Access == AccessTy::Load; }
146 bool isStore() const { return Access == AccessTy::Store; }
147};
148
149/// This Pass first walks through all the MOVEM instructions
150/// that are chained together and record each of the
151/// instruction's properties like register mask and data
152/// access type into a `MOVEState` instance.
153/// Then we perform reduction / collapsing on this `MOVEMState`
154/// representation before creating a new `MOVEM` instruction
155/// based on the collapsed result, as well as removing
156/// redundant `MOVEM` instructions.
157class M68kCollapseMOVEM : public MachineFunctionPass {
158public:
159 static char ID;
160
161 const M68kSubtarget *STI;
162 const M68kInstrInfo *TII;
163 const M68kRegisterInfo *TRI;
164 const M68kMachineFunctionInfo *MFI;
165 const M68kFrameLowering *FL;
166
167 M68kCollapseMOVEM() : MachineFunctionPass(ID) {}
168
169 void Finish(MachineBasicBlock &MBB, MOVEMState &State) {
170 auto MI = State.begin();
171 auto End = State.end();
172 DebugLoc DL = MI->getDebugLoc();
173
174 // No need to delete then add a single instruction
175 if (std::next(x: MI) == End) {
176 State = MOVEMState();
177 return;
178 }
179
180 // Delete all the MOVEM instruction till the end
181 while (MI != End) {
182 auto Next = std::next(x: MI);
183 MBB.erase(I: MI);
184 MI = Next;
185 }
186
187 // Add a unified one
188 if (State.isLoad()) {
189 BuildMI(MBB, End, DL, TII->get(M68k::MOVM32mp))
190 .addImm(State.getMask())
191 .addImm(State.getFinalOffset())
192 .addReg(State.getBase());
193 } else {
194 BuildMI(MBB, End, DL, TII->get(M68k::MOVM32pm))
195 .addImm(State.getFinalOffset())
196 .addReg(State.getBase())
197 .addImm(State.getMask());
198 }
199
200 State = MOVEMState();
201 }
202
203 bool ProcessMI(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
204 MOVEMState &State, unsigned Mask, int Offset, unsigned Reg,
205 bool IsStore = false) {
206 if (State.hasBase()) {
207 // If current Type, Reg, Offset and Mask is in proper order then
208 // merge in the state
209 MOVEMState Temp = State;
210 if (State.isStore() == IsStore && State.getBase() == Reg &&
211 State.update(O: Offset, M: Mask)) {
212 return true;
213 // Otherwise we Finish processing of the current MOVEM sequance and
214 // start a new one
215 } else {
216 State = Temp;
217 State.setEnd(MI);
218 Finish(MBB, State);
219 return ProcessMI(MBB, MI, State, Mask, Offset, Reg, IsStore);
220 }
221 // If this is the first instruction is sequance then initialize the State
222 } else if (Reg == TRI->getStackRegister() ||
223 Reg == TRI->getBaseRegister() ||
224 Reg == TRI->getFrameRegister(MF: *MBB.getParent())) {
225 State.setBegin(MI);
226 State.setBase(Reg);
227 State.update(O: Offset, M: Mask);
228 IsStore ? State.setStore() : State.setLoad();
229 return true;
230 }
231 return false;
232 }
233
234 bool runOnMachineFunction(MachineFunction &MF) override {
235 STI = &MF.getSubtarget<M68kSubtarget>();
236 TII = STI->getInstrInfo();
237 TRI = STI->getRegisterInfo();
238 MFI = MF.getInfo<M68kMachineFunctionInfo>();
239 FL = STI->getFrameLowering();
240
241 bool Modified = false;
242
243 MOVEMState State;
244
245 unsigned Mask = 0;
246 unsigned Reg = 0;
247 int Offset = 0;
248
249 for (auto &MBB : MF) {
250 auto MI = MBB.begin(), E = MBB.end();
251 while (MI != E) {
252 // Processing might change current instruction, save next first
253 auto NMI = std::next(x: MI);
254 switch (MI->getOpcode()) {
255 default:
256 if (State.hasBase()) {
257 State.setEnd(MI);
258 Finish(MBB, State);
259 Modified = true;
260 }
261 break;
262 case M68k::MOVM32jm:
263 Mask = MI->getOperand(i: 1).getImm();
264 Reg = MI->getOperand(i: 0).getReg();
265 Offset = 0;
266 Modified |= ProcessMI(MBB, MI, State, Mask, Offset, Reg, IsStore: true);
267 break;
268 case M68k::MOVM32pm:
269 Mask = MI->getOperand(i: 2).getImm();
270 Reg = MI->getOperand(i: 1).getReg();
271 Offset = MI->getOperand(i: 0).getImm();
272 Modified |= ProcessMI(MBB, MI, State, Mask, Offset, Reg, IsStore: true);
273 break;
274 case M68k::MOVM32mj:
275 Mask = MI->getOperand(i: 0).getImm();
276 Reg = MI->getOperand(i: 1).getReg();
277 Offset = 0;
278 Modified |= ProcessMI(MBB, MI, State, Mask, Offset, Reg, IsStore: false);
279 break;
280 case M68k::MOVM32mp:
281 Mask = MI->getOperand(i: 0).getImm();
282 Reg = MI->getOperand(i: 2).getReg();
283 Offset = MI->getOperand(i: 1).getImm();
284 Modified |= ProcessMI(MBB, MI, State, Mask, Offset, Reg, IsStore: false);
285 break;
286 }
287 MI = NMI;
288 }
289
290 if (State.hasBase()) {
291 State.setEnd(MI);
292 Finish(MBB, State);
293 }
294 }
295
296 return Modified;
297 }
298};
299
300char M68kCollapseMOVEM::ID = 0;
301} // anonymous namespace.
302
303INITIALIZE_PASS(M68kCollapseMOVEM, DEBUG_TYPE, PASS_NAME, false, false)
304
305/// Returns an instance of the pseudo instruction expansion pass.
306FunctionPass *llvm::createM68kCollapseMOVEMPass() {
307 return new M68kCollapseMOVEM();
308}
309

source code of llvm/lib/Target/M68k/M68kCollapseMOVEMPass.cpp