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 = &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 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 } 308