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(M);
108     if (Type == Intermixed)
109       return false;
110     if (Start == INT_MIN) {
111       Start = Stop = O;
112       updateMask(M);
113       return true;
114     } else if (Type == Descending && O == Start - 4) {
115       Start -= 4;
116       updateMask(M);
117       return true;
118     } else if (Type == Ascending && O == Stop + 4) {
119       Stop += 4;
120       updateMask(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(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(MI);
183       MBB.erase(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(Offset, 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(*MBB.getParent())) {
225       State.setBegin(MI);
226       State.setBase(Reg);
227       State.update(Offset, 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(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(1).getImm();
264           Reg = MI->getOperand(0).getReg();
265           Offset = 0;
266           Modified |= ProcessMI(MBB, MI, State, Mask, Offset, Reg, true);
267           break;
268         case M68k::MOVM32pm:
269           Mask = MI->getOperand(2).getImm();
270           Reg = MI->getOperand(1).getReg();
271           Offset = MI->getOperand(0).getImm();
272           Modified |= ProcessMI(MBB, MI, State, Mask, Offset, Reg, true);
273           break;
274         case M68k::MOVM32mj:
275           Mask = MI->getOperand(0).getImm();
276           Reg = MI->getOperand(1).getReg();
277           Offset = 0;
278           Modified |= ProcessMI(MBB, MI, State, Mask, Offset, Reg, false);
279           break;
280         case M68k::MOVM32mp:
281           Mask = MI->getOperand(0).getImm();
282           Reg = MI->getOperand(2).getReg();
283           Offset = MI->getOperand(1).getImm();
284           Modified |= ProcessMI(MBB, MI, State, Mask, Offset, Reg, 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