309 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8///9/// \file10/// `MOVEM` is an instruction that moves multiple registers a time according to11/// the given mask. Thus sometimes it's pretty expensive.12/// This file contains a pass that collapses sequential MOVEM instructions into13/// 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 30using namespace llvm;31 32#define DEBUG_TYPE "m68k-collapse-movem"33#define PASS_NAME "M68k MOVEM collapser pass"34 35namespace {36 37enum UpdateType { Ascending, Descending, Intermixed };38 39/// An abtraction of the MOVEM chain currently processing40class 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 54public: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 update94 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 instructions150/// that are chained together and record each of the151/// instruction's properties like register mask and data152/// access type into a `MOVEState` instance.153/// Then we perform reduction / collapsing on this `MOVEMState`154/// representation before creating a new `MOVEM` instruction155/// based on the collapsed result, as well as removing156/// redundant `MOVEM` instructions.157class M68kCollapseMOVEM : public MachineFunctionPass {158public: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 instruction175 if (std::next(MI) == End) {176 State = MOVEMState();177 return;178 }179 180 // Delete all the MOVEM instruction till the end181 while (MI != End) {182 auto Next = std::next(MI);183 MBB.erase(MI);184 MI = Next;185 }186 187 // Add a unified one188 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 then208 // merge in the state209 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 and214 // start a new one215 } 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 State222 } 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 first253 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 300char M68kCollapseMOVEM::ID = 0;301} // anonymous namespace.302 303INITIALIZE_PASS(M68kCollapseMOVEM, DEBUG_TYPE, PASS_NAME, false, false)304 305/// Returns an instance of the pseudo instruction expansion pass.306FunctionPass *llvm::createM68kCollapseMOVEMPass() {307 return new M68kCollapseMOVEM();308}309