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