LLVM  14.0.0git
M68kCollapseMOVEMPass.cpp
Go to the documentation of this file.
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 
27 #include "llvm/IR/GlobalValue.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 {
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 
76  assert(Begin != nullptr);
77  return Begin;
78  }
79 
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 
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() ||
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 = &static_cast<const M68kSubtarget &>(MF.getSubtarget());
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.
306  return new M68kCollapseMOVEM();
307 }
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:105
MathExtras.h
llvm::MachineInstrBuilder::addImm
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
Definition: MachineInstrBuilder.h:131
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
Reg
unsigned Reg
Definition: MachineSink.cpp:1563
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::M68kRegisterInfo
Definition: M68kRegisterInfo.h:30
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:236
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:227
EHPersonalities.h
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:80
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::M68kSubtarget::getRegisterInfo
const M68kRegisterInfo * getRegisterInfo() const override
Definition: M68kSubtarget.h:155
llvm::BitmaskEnumDetail::Mask
std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1564
MachineRegisterInfo.h
llvm::MachineBasicBlock::erase
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
Definition: MachineBasicBlock.cpp:1298
M68k.h
M68kInstrInfo.h
GlobalValue.h
llvm::M68kSubtarget::getInstrInfo
const M68kInstrInfo * getInstrInfo() const override
Definition: M68kSubtarget.h:149
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MachineFunction::getInfo
Ty * getInfo()
getInfo - Keep track of various per-function pieces of information for backends that would like to do...
Definition: MachineFunction.h:739
llvm::createM68kCollapseMOVEMPass
FunctionPass * createM68kCollapseMOVEMPass()
Finds sequential MOVEM instruction and collapse them into a single one.
Definition: M68kCollapseMOVEMPass.cpp:305
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:127
LoopDeletionResult::Modified
@ Modified
llvm::None
const NoneType None
Definition: None.h:23
M68kFrameLowering.h
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::M68kSubtarget
Definition: M68kSubtarget.h:45
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:641
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:206
llvm::isUInt< 16 >
constexpr bool isUInt< 16 >(uint64_t x)
Definition: MathExtras.h:408
llvm::TargetRegisterInfo::getFrameRegister
virtual Register getFrameRegister(const MachineFunction &MF) const =0
Debug information queries.
MachineFunctionPass.h
llvm::M68kSubtarget::getFrameLowering
const M68kFrameLowering * getFrameLowering() const override
Definition: M68kSubtarget.h:151
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:229
llvm::MachineInstrBuilder::addReg
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Definition: MachineInstrBuilder.h:97
isStore
static bool isStore(int Opcode)
Definition: ARCInstrInfo.cpp:58
llvm::MachineFunction
Definition: MachineFunction.h:241
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
isLoad
static bool isLoad(int Opcode)
Definition: ARCInstrInfo.cpp:53
llvm::M68kMachineFunctionInfo
Definition: M68kMachineFunction.h:23
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::M68kFrameLowering
Definition: M68kFrameLowering.h:28
llvm::M68kInstrInfo
Definition: M68kInstrInfo.h:237
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
M68kMachineFunction.h
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:272
MachineInstrBuilder.h
llvm::BuildMI
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
Definition: MachineInstrBuilder.h:328
M68kSubtarget.h
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::MachineInstrBundleIterator< MachineInstr >
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:274
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38