llvm/lib/Target/M68k/M68kCollapseMOVEMPass.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-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 }