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 | |
30 | using namespace llvm; |
31 | |
32 | #define DEBUG_TYPE "m68k-collapse-movem" |
33 | #define PASS_NAME "M68k MOVEM collapser pass" |
34 | |
35 | namespace { |
36 | |
37 | enum UpdateType { Ascending, Descending, Intermixed }; |
38 | |
39 | /// An abtraction of the MOVEM chain currently processing |
40 | class 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 | |
54 | public: |
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. |
157 | class M68kCollapseMOVEM : public MachineFunctionPass { |
158 | public: |
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 | |
300 | char M68kCollapseMOVEM::ID = 0; |
301 | } // anonymous namespace. |
302 | |
303 | INITIALIZE_PASS(M68kCollapseMOVEM, DEBUG_TYPE, PASS_NAME, false, false) |
304 | |
305 | /// Returns an instance of the pseudo instruction expansion pass. |
306 | FunctionPass *llvm::createM68kCollapseMOVEMPass() { |
307 | return new M68kCollapseMOVEM(); |
308 | } |
309 | |