lib/Target/Lanai/LanaiMemAluCombiner.cpp

   1 //===-- LanaiMemAluCombiner.cpp - Pass to combine memory & ALU operations -===//
   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 // Simple pass to combine memory and ALU operations
   9 //
  10 // The Lanai ISA supports instructions where a load/store modifies the base
  11 // register used in the load/store operation. This pass finds suitable
  12 // load/store and ALU instructions and combines them into one instruction.
  13 //
  14 // For example,
  15 //   ld [ %r6 -- ], %r12
  16 // is a supported instruction that is not currently generated by the instruction
  17 // selection pass of this backend. This pass generates these instructions by
  18 // merging
  19 //   add %r6, -4, %r6
  20 // followed by
  21 //   ld [ %r6 ], %r12
  22 // in the same machine basic block into one machine instruction.
  23 //===----------------------------------------------------------------------===//
  24
  25 #include "Lanai.h"
  26 #include "LanaiTargetMachine.h"
  27 #include "llvm/ADT/SmallSet.h"
  28 #include "llvm/ADT/Statistic.h"
  29 #include "llvm/CodeGen/MachineFunctionPass.h"
  30 #include "llvm/CodeGen/MachineInstrBuilder.h"
  31 #include "llvm/CodeGen/RegisterScavenging.h"
  32 #include "llvm/CodeGen/TargetInstrInfo.h"
  33 #include "llvm/Support/CommandLine.h"
  34 using namespace llvm;
  35
  36 #define GET_INSTRMAP_INFO
  37 #include "LanaiGenInstrInfo.inc"
  38
  39 #define DEBUG_TYPE "lanai-mem-alu-combiner"
  40
  41 STATISTIC(NumLdStAluCombined, "Number of memory and ALU instructions combined");
  42
  43 static llvm::cl::opt<bool> DisableMemAluCombiner(
  44     "disable-lanai-mem-alu-combiner", llvm::cl::init(false),
  45     llvm::cl::desc("Do not combine ALU and memory operators"),
  46     llvm::cl::Hidden);
  47
  48 namespace llvm {
  49 void initializeLanaiMemAluCombinerPass(PassRegistry &);
  50 } // namespace llvm
  51
  52 namespace {
  53 typedef MachineBasicBlock::iterator MbbIterator;
  54 typedef MachineFunction::iterator MfIterator;
  55
  56 class LanaiMemAluCombiner : public MachineFunctionPass {
  57 public:
  58   static char ID;
  59   explicit LanaiMemAluCombiner() : MachineFunctionPass(ID) {
  60     initializeLanaiMemAluCombinerPass(*PassRegistry::getPassRegistry());
  61   }
  62
  63   StringRef getPassName() const override {
  64     return "Lanai load / store optimization pass";
  65   }
  66
  67   bool runOnMachineFunction(MachineFunction &F) override;
  68
  69   MachineFunctionProperties getRequiredProperties() const override {
  70     return MachineFunctionProperties().set(
  71         MachineFunctionProperties::Property::NoVRegs);
  72   }
  73
  74 private:
  75   MbbIterator findClosestSuitableAluInstr(MachineBasicBlock *BB,
  76                                           const MbbIterator &MemInstr,
  77                                           bool Decrement);
  78   void insertMergedInstruction(MachineBasicBlock *BB,
  79                                const MbbIterator &MemInstr,
  80                                const MbbIterator &AluInstr, bool Before);
  81   bool combineMemAluInBasicBlock(MachineBasicBlock *BB);
  82
  83   // Target machine description which we query for register names, data
  84   // layout, etc.
  85   const TargetInstrInfo *TII;
  86 };
  87 } // namespace
  88
  89 char LanaiMemAluCombiner::ID = 0;
  90
  91 INITIALIZE_PASS(LanaiMemAluCombiner, DEBUG_TYPE,
  92                 "Lanai memory ALU combiner pass", false, false)
  93
  94 namespace {
  95 bool isSpls(uint16_t Opcode) { return Lanai::splsIdempotent(Opcode) == Opcode; }
  96
  97 // Determine the opcode for the merged instruction created by considering the
  98 // old memory operation's opcode and whether the merged opcode will have an
  99 // immediate offset.
 100 unsigned mergedOpcode(unsigned OldOpcode, bool ImmediateOffset) {
 101   switch (OldOpcode) {
 102   case Lanai::LDW_RI:
 103   case Lanai::LDW_RR:
 104     if (ImmediateOffset)
 105       return Lanai::LDW_RI;
 106     return Lanai::LDW_RR;
 107   case Lanai::LDHs_RI:
 108   case Lanai::LDHs_RR:
 109     if (ImmediateOffset)
 110       return Lanai::LDHs_RI;
 111     return Lanai::LDHs_RR;
 112   case Lanai::LDHz_RI:
 113   case Lanai::LDHz_RR:
 114     if (ImmediateOffset)
 115       return Lanai::LDHz_RI;
 116     return Lanai::LDHz_RR;
 117   case Lanai::LDBs_RI:
 118   case Lanai::LDBs_RR:
 119     if (ImmediateOffset)
 120       return Lanai::LDBs_RI;
 121     return Lanai::LDBs_RR;
 122   case Lanai::LDBz_RI:
 123   case Lanai::LDBz_RR:
 124     if (ImmediateOffset)
 125       return Lanai::LDBz_RI;
 126     return Lanai::LDBz_RR;
 127   case Lanai::SW_RI:
 128   case Lanai::SW_RR:
 129     if (ImmediateOffset)
 130       return Lanai::SW_RI;
 131     return Lanai::SW_RR;
 132   case Lanai::STB_RI:
 133   case Lanai::STB_RR:
 134     if (ImmediateOffset)
 135       return Lanai::STB_RI;
 136     return Lanai::STB_RR;
 137   case Lanai::STH_RI:
 138   case Lanai::STH_RR:
 139     if (ImmediateOffset)
 140       return Lanai::STH_RI;
 141     return Lanai::STH_RR;
 142   default:
 143     return 0;
 144   }
 145 }
 146
 147 // Check if the machine instruction has non-volatile memory operands of the type
 148 // supported for combining with ALU instructions.
 149 bool isNonVolatileMemoryOp(const MachineInstr &MI) {
 150   if (!MI.hasOneMemOperand())
 151     return false;
 152
 153   // Determine if the machine instruction is a supported memory operation by
 154   // testing if the computed merge opcode is a valid memory operation opcode.
 155   if (mergedOpcode(MI.getOpcode(), false) == 0)
 156     return false;
 157
 158   const MachineMemOperand *MemOperand = *MI.memoperands_begin();
 159
 160   // Don't move volatile memory accesses
 161   if (MemOperand->isVolatile())
 162     return false;
 163
 164   return true;
 165 }
 166
 167 // Test to see if two machine operands are of the same type. This test is less
 168 // strict than the MachineOperand::isIdenticalTo function.
 169 bool isSameOperand(const MachineOperand &Op1, const MachineOperand &Op2) {
 170   if (Op1.getType() != Op2.getType())
 171     return false;
 172
 173   switch (Op1.getType()) {
 174   case MachineOperand::MO_Register:
 175     return Op1.getReg() == Op2.getReg();
 176   case MachineOperand::MO_Immediate:
 177     return Op1.getImm() == Op2.getImm();
 178   default:
 179     return false;
 180   }
 181 }
 182
 183 bool isZeroOperand(const MachineOperand &Op) {
 184   return ((Op.isReg() && Op.getReg() == Lanai::R0) ||
 185           (Op.isImm() && Op.getImm() == 0));
 186 }
 187
 188 // Determines whether a register is used by an instruction.
 189 bool InstrUsesReg(const MbbIterator &Instr, const MachineOperand *Reg) {
 190   for (MachineInstr::const_mop_iterator Mop = Instr->operands_begin();
 191        Mop != Instr->operands_end(); ++Mop) {
 192     if (isSameOperand(*Mop, *Reg))
 193       return true;
 194   }
 195   return false;
 196 }
 197
 198 // Converts between machine opcode and AluCode.
 199 // Flag using/modifying ALU operations should not be considered for merging and
 200 // are omitted from this list.
 201 LPAC::AluCode mergedAluCode(unsigned AluOpcode) {
 202   switch (AluOpcode) {
 203   case Lanai::ADD_I_LO:
 204   case Lanai::ADD_R:
 205     return LPAC::ADD;
 206   case Lanai::SUB_I_LO:
 207   case Lanai::SUB_R:
 208     return LPAC::SUB;
 209   case Lanai::AND_I_LO:
 210   case Lanai::AND_R:
 211     return LPAC::AND;
 212   case Lanai::OR_I_LO:
 213   case Lanai::OR_R:
 214     return LPAC::OR;
 215   case Lanai::XOR_I_LO:
 216   case Lanai::XOR_R:
 217     return LPAC::XOR;
 218   case Lanai::SHL_R:
 219     return LPAC::SHL;
 220   case Lanai::SRL_R:
 221     return LPAC::SRL;
 222   case Lanai::SRA_R:
 223     return LPAC::SRA;
 224   case Lanai::SA_I:
 225   case Lanai::SL_I:
 226   default:
 227     return LPAC::UNKNOWN;
 228   }
 229 }
 230
 231 // Insert a new combined memory and ALU operation instruction.
 232 //
 233 // This function builds a new machine instruction using the MachineInstrBuilder
 234 // class and inserts it before the memory instruction.
 235 void LanaiMemAluCombiner::insertMergedInstruction(MachineBasicBlock *BB,
 236                                                   const MbbIterator &MemInstr,
 237                                                   const MbbIterator &AluInstr,
 238                                                   bool Before) {
 239   // Insert new combined load/store + alu operation
 240   MachineOperand Dest = MemInstr->getOperand(0);
 241   MachineOperand Base = MemInstr->getOperand(1);
 242   MachineOperand MemOffset = MemInstr->getOperand(2);
 243   MachineOperand AluOffset = AluInstr->getOperand(2);
 244
 245   // Abort if ALU offset is not a register or immediate
 246   assert((AluOffset.isReg() || AluOffset.isImm()) &&
 247          "Unsupported operand type in merge");
 248
 249   // Determined merged instructions opcode and ALU code
 250   LPAC::AluCode AluOpcode = mergedAluCode(AluInstr->getOpcode());
 251   unsigned NewOpc = mergedOpcode(MemInstr->getOpcode(), AluOffset.isImm());
 252
 253   assert(AluOpcode != LPAC::UNKNOWN && "Unknown ALU code in merging");
 254   assert(NewOpc != 0 && "Unknown merged node opcode");
 255
 256   // Build and insert new machine instruction
 257   MachineInstrBuilder InstrBuilder =
 258       BuildMI(*BB, MemInstr, MemInstr->getDebugLoc(), TII->get(NewOpc));
 259   InstrBuilder.addReg(Dest.getReg(), getDefRegState(true));
 260   InstrBuilder.addReg(Base.getReg(), getKillRegState(true));
 261
 262   // Add offset to machine instruction
 263   if (AluOffset.isReg())
 264     InstrBuilder.addReg(AluOffset.getReg());
 265   else if (AluOffset.isImm())
 266     InstrBuilder.addImm(AluOffset.getImm());
 267   else
 268     llvm_unreachable("Unsupported ld/st ALU merge.");
 269
 270   // Create a pre-op if the ALU operation preceded the memory operation or the
 271   // MemOffset is non-zero (i.e. the memory value should be adjusted before
 272   // accessing it), else create a post-op.
 273   if (Before || !isZeroOperand(MemOffset))
 274     InstrBuilder.addImm(LPAC::makePreOp(AluOpcode));
 275   else
 276     InstrBuilder.addImm(LPAC::makePostOp(AluOpcode));
 277
 278   // Transfer memory operands.
 279   InstrBuilder.setMemRefs(MemInstr->memoperands());
 280 }
 281
 282 // Function determines if ALU operation (in alu_iter) can be combined with
 283 // a load/store with base and offset.
 284 bool isSuitableAluInstr(bool IsSpls, const MbbIterator &AluIter,
 285                         const MachineOperand &Base,
 286                         const MachineOperand &Offset) {
 287   // ALU operations have 3 operands
 288   if (AluIter->getNumOperands() != 3)
 289     return false;
 290
 291   MachineOperand &Dest = AluIter->getOperand(0);
 292   MachineOperand &Op1 = AluIter->getOperand(1);
 293   MachineOperand &Op2 = AluIter->getOperand(2);
 294
 295   // Only match instructions using the base register as destination and with the
 296   // base and first operand equal
 297   if (!isSameOperand(Dest, Base) || !isSameOperand(Dest, Op1))
 298     return false;
 299
 300   if (Op2.isImm()) {
 301     // It is not a match if the 2nd operand in the ALU operation is an
 302     // immediate but the ALU operation is not an addition.
 303     if (AluIter->getOpcode() != Lanai::ADD_I_LO)
 304       return false;
 305
 306     if (Offset.isReg() && Offset.getReg() == Lanai::R0)
 307       return true;
 308
 309     if (Offset.isImm() &&
 310         ((Offset.getImm() == 0 &&
 311           // Check that the Op2 would fit in the immediate field of the
 312           // memory operation.
 313           ((IsSpls && isInt<10>(Op2.getImm())) ||
 314            (!IsSpls && isInt<16>(Op2.getImm())))) ||
 315          Offset.getImm() == Op2.getImm()))
 316       return true;
 317   } else if (Op2.isReg()) {
 318     // The Offset and 2nd operand are both registers and equal
 319     if (Offset.isReg() && Op2.getReg() == Offset.getReg())
 320       return true;
 321   } else
 322     // Only consider operations with register or immediate values
 323     return false;
 324
 325   return false;
 326 }
 327
 328 MbbIterator LanaiMemAluCombiner::findClosestSuitableAluInstr(
 329     MachineBasicBlock *BB, const MbbIterator &MemInstr, const bool Decrement) {
 330   MachineOperand *Base = &MemInstr->getOperand(1);
 331   MachineOperand *Offset = &MemInstr->getOperand(2);
 332   bool IsSpls = isSpls(MemInstr->getOpcode());
 333
 334   MbbIterator First = MemInstr;
 335   MbbIterator Last = Decrement ? BB->begin() : BB->end();
 336
 337   while (First != Last) {
 338     Decrement ? --First : ++First;
 339
 340     if (First == Last)
 341       break;
 342
 343     // Skip over debug instructions
 344     if (First->isDebugInstr())
 345       continue;
 346
 347     if (isSuitableAluInstr(IsSpls, First, *Base, *Offset)) {
 348       return First;
 349     }
 350
 351     // Usage of the base or offset register is not a form suitable for merging.
 352     if (First != Last) {
 353       if (InstrUsesReg(First, Base))
 354         break;
 355       if (Offset->isReg() && InstrUsesReg(First, Offset))
 356         break;
 357     }
 358   }
 359
 360   return MemInstr;
 361 }
 362
 363 bool LanaiMemAluCombiner::combineMemAluInBasicBlock(MachineBasicBlock *BB) {
 364   bool Modified = false;
 365
 366   MbbIterator MBBIter = BB->begin(), End = BB->end();
 367   while (MBBIter != End) {
 368     bool IsMemOp = isNonVolatileMemoryOp(*MBBIter);
 369
 370     if (IsMemOp) {
 371       MachineOperand AluOperand = MBBIter->getOperand(3);
 372       unsigned int DestReg = MBBIter->getOperand(0).getReg(),
 373                    BaseReg = MBBIter->getOperand(1).getReg();
 374       assert(AluOperand.isImm() && "Unexpected memory operator type");
 375       LPAC::AluCode AluOpcode = static_cast<LPAC::AluCode>(AluOperand.getImm());
 376
 377       // Skip memory operations that already modify the base register or if
 378       // the destination and base register are the same
 379       if (!LPAC::modifiesOp(AluOpcode) && DestReg != BaseReg) {
 380         for (int Inc = 0; Inc <= 1; ++Inc) {
 381           MbbIterator AluIter =
 382               findClosestSuitableAluInstr(BB, MBBIter, Inc == 0);
 383           if (AluIter != MBBIter) {
 384             insertMergedInstruction(BB, MBBIter, AluIter, Inc == 0);
 385
 386             ++NumLdStAluCombined;
 387             Modified = true;
 388
 389             // Erase the matching ALU instruction
 390             BB->erase(AluIter);
 391             // Erase old load/store instruction
 392             BB->erase(MBBIter++);
 393             break;
 394           }
 395         }
 396       }
 397     }
 398     if (MBBIter == End)
 399       break;
 400     ++MBBIter;
 401   }
 402
 403   return Modified;
 404 }
 405
 406 // Driver function that iterates over the machine basic building blocks of a
 407 // machine function
 408 bool LanaiMemAluCombiner::runOnMachineFunction(MachineFunction &MF) {
 409   if (DisableMemAluCombiner)
 410     return false;
 411
 412   TII = MF.getSubtarget<LanaiSubtarget>().getInstrInfo();
 413   bool Modified = false;
 414   for (MfIterator MFI = MF.begin(); MFI != MF.end(); ++MFI) {
 415     Modified |= combineMemAluInBasicBlock(&*MFI);
 416   }
 417   return Modified;
 418 }
 419 } // namespace
 420
 421 FunctionPass *llvm::createLanaiMemAluCombinerPass() {
 422   return new LanaiMemAluCombiner();
 423 }