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