contrib/llvm/lib/Target/Lanai/LanaiMemAluCombiner.cpp

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