Home | History | Annotate | Download | only in Lanai 
      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 }
    426