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/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
  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 {
  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
  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
  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.
 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
 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 = &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.
 305 FunctionPass *llvm::createM68kCollapseMOVEMPass() {
 306   return new M68kCollapseMOVEM();
 307 }