Home | History | Annotate | Download | only in X86 
      1 //===-- X86FixupLEAs.cpp - use or replace LEA instructions -----------===//
      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 //
     10 // This file defines the pass that finds instructions that can be
     11 // re-written as LEA instructions in order to reduce pipeline delays.
     12 // When optimizing for size it replaces suitable LEAs with INC or DEC.
     13 //
     14 //===----------------------------------------------------------------------===//
     15 
     16 #include "X86.h"
     17 #include "X86InstrInfo.h"
     18 #include "X86Subtarget.h"
     19 #include "llvm/ADT/Statistic.h"
     20 #include "llvm/CodeGen/LiveVariables.h"
     21 #include "llvm/CodeGen/MachineFunctionPass.h"
     22 #include "llvm/CodeGen/MachineInstrBuilder.h"
     23 #include "llvm/CodeGen/MachineRegisterInfo.h"
     24 #include "llvm/CodeGen/Passes.h"
     25 #include "llvm/Support/Debug.h"
     26 #include "llvm/Support/raw_ostream.h"
     27 #include "llvm/Target/TargetInstrInfo.h"
     28 using namespace llvm;
     29 
     30 #define DEBUG_TYPE "x86-fixup-LEAs"
     31 
     32 STATISTIC(NumLEAs, "Number of LEA instructions created");
     33 
     34 namespace {
     35 class FixupLEAPass : public MachineFunctionPass {
     36   enum RegUsageState { RU_NotUsed, RU_Write, RU_Read };
     37   static char ID;
     38   /// \brief Loop over all of the instructions in the basic block
     39   /// replacing applicable instructions with LEA instructions,
     40   /// where appropriate.
     41   bool processBasicBlock(MachineFunction &MF, MachineFunction::iterator MFI);
     42 
     43   const char *getPassName() const override { return "X86 LEA Fixup"; }
     44 
     45   /// \brief Given a machine register, look for the instruction
     46   /// which writes it in the current basic block. If found,
     47   /// try to replace it with an equivalent LEA instruction.
     48   /// If replacement succeeds, then also process the newly created
     49   /// instruction.
     50   void seekLEAFixup(MachineOperand &p, MachineBasicBlock::iterator &I,
     51                     MachineFunction::iterator MFI);
     52 
     53   /// \brief Given a memory access or LEA instruction
     54   /// whose address mode uses a base and/or index register, look for
     55   /// an opportunity to replace the instruction which sets the base or index
     56   /// register with an equivalent LEA instruction.
     57   void processInstruction(MachineBasicBlock::iterator &I,
     58                           MachineFunction::iterator MFI);
     59 
     60   /// \brief Given a LEA instruction which is unprofitable
     61   /// on Silvermont try to replace it with an equivalent ADD instruction
     62   void processInstructionForSLM(MachineBasicBlock::iterator &I,
     63                                 MachineFunction::iterator MFI);
     64 
     65   /// \brief Look for LEAs that add 1 to reg or subtract 1 from reg
     66   /// and convert them to INC or DEC respectively.
     67   bool fixupIncDec(MachineBasicBlock::iterator &I,
     68                    MachineFunction::iterator MFI) const;
     69 
     70   /// \brief Determine if an instruction references a machine register
     71   /// and, if so, whether it reads or writes the register.
     72   RegUsageState usesRegister(MachineOperand &p, MachineBasicBlock::iterator I);
     73 
     74   /// \brief Step backwards through a basic block, looking
     75   /// for an instruction which writes a register within
     76   /// a maximum of INSTR_DISTANCE_THRESHOLD instruction latency cycles.
     77   MachineBasicBlock::iterator searchBackwards(MachineOperand &p,
     78                                               MachineBasicBlock::iterator &I,
     79                                               MachineFunction::iterator MFI);
     80 
     81   /// \brief if an instruction can be converted to an
     82   /// equivalent LEA, insert the new instruction into the basic block
     83   /// and return a pointer to it. Otherwise, return zero.
     84   MachineInstr *postRAConvertToLEA(MachineFunction::iterator &MFI,
     85                                    MachineBasicBlock::iterator &MBBI) const;
     86 
     87 public:
     88   FixupLEAPass() : MachineFunctionPass(ID) {}
     89 
     90   /// \brief Loop over all of the basic blocks,
     91   /// replacing instructions by equivalent LEA instructions
     92   /// if needed and when possible.
     93   bool runOnMachineFunction(MachineFunction &MF) override;
     94 
     95 private:
     96   MachineFunction *MF;
     97   const X86InstrInfo *TII; // Machine instruction info.
     98   bool OptIncDec;
     99   bool OptLEA;
    100 };
    101 char FixupLEAPass::ID = 0;
    102 }
    103 
    104 MachineInstr *
    105 FixupLEAPass::postRAConvertToLEA(MachineFunction::iterator &MFI,
    106                                  MachineBasicBlock::iterator &MBBI) const {
    107   MachineInstr *MI = MBBI;
    108   MachineInstr *NewMI;
    109   switch (MI->getOpcode()) {
    110   case X86::MOV32rr:
    111   case X86::MOV64rr: {
    112     const MachineOperand &Src = MI->getOperand(1);
    113     const MachineOperand &Dest = MI->getOperand(0);
    114     NewMI = BuildMI(*MF, MI->getDebugLoc(),
    115                     TII->get(MI->getOpcode() == X86::MOV32rr ? X86::LEA32r
    116                                                              : X86::LEA64r))
    117                 .addOperand(Dest)
    118                 .addOperand(Src)
    119                 .addImm(1)
    120                 .addReg(0)
    121                 .addImm(0)
    122                 .addReg(0);
    123     MFI->insert(MBBI, NewMI); // Insert the new inst
    124     return NewMI;
    125   }
    126   case X86::ADD64ri32:
    127   case X86::ADD64ri8:
    128   case X86::ADD64ri32_DB:
    129   case X86::ADD64ri8_DB:
    130   case X86::ADD32ri:
    131   case X86::ADD32ri8:
    132   case X86::ADD32ri_DB:
    133   case X86::ADD32ri8_DB:
    134   case X86::ADD16ri:
    135   case X86::ADD16ri8:
    136   case X86::ADD16ri_DB:
    137   case X86::ADD16ri8_DB:
    138     if (!MI->getOperand(2).isImm()) {
    139       // convertToThreeAddress will call getImm()
    140       // which requires isImm() to be true
    141       return nullptr;
    142     }
    143     break;
    144   case X86::ADD16rr:
    145   case X86::ADD16rr_DB:
    146     if (MI->getOperand(1).getReg() != MI->getOperand(2).getReg()) {
    147       // if src1 != src2, then convertToThreeAddress will
    148       // need to create a Virtual register, which we cannot do
    149       // after register allocation.
    150       return nullptr;
    151     }
    152   }
    153   return TII->convertToThreeAddress(MFI, MBBI, nullptr);
    154 }
    155 
    156 FunctionPass *llvm::createX86FixupLEAs() { return new FixupLEAPass(); }
    157 
    158 bool FixupLEAPass::runOnMachineFunction(MachineFunction &Func) {
    159   MF = &Func;
    160   const X86Subtarget &ST = Func.getSubtarget<X86Subtarget>();
    161   OptIncDec = !ST.slowIncDec() || Func.getFunction()->optForMinSize();
    162   OptLEA = ST.LEAusesAG() || ST.slowLEA();
    163 
    164   if (!OptLEA && !OptIncDec)
    165     return false;
    166 
    167   TII = ST.getInstrInfo();
    168 
    169   DEBUG(dbgs() << "Start X86FixupLEAs\n";);
    170   // Process all basic blocks.
    171   for (MachineFunction::iterator I = Func.begin(), E = Func.end(); I != E; ++I)
    172     processBasicBlock(Func, I);
    173   DEBUG(dbgs() << "End X86FixupLEAs\n";);
    174 
    175   return true;
    176 }
    177 
    178 FixupLEAPass::RegUsageState
    179 FixupLEAPass::usesRegister(MachineOperand &p, MachineBasicBlock::iterator I) {
    180   RegUsageState RegUsage = RU_NotUsed;
    181   MachineInstr *MI = I;
    182 
    183   for (unsigned int i = 0; i < MI->getNumOperands(); ++i) {
    184     MachineOperand &opnd = MI->getOperand(i);
    185     if (opnd.isReg() && opnd.getReg() == p.getReg()) {
    186       if (opnd.isDef())
    187         return RU_Write;
    188       RegUsage = RU_Read;
    189     }
    190   }
    191   return RegUsage;
    192 }
    193 
    194 /// getPreviousInstr - Given a reference to an instruction in a basic
    195 /// block, return a reference to the previous instruction in the block,
    196 /// wrapping around to the last instruction of the block if the block
    197 /// branches to itself.
    198 static inline bool getPreviousInstr(MachineBasicBlock::iterator &I,
    199                                     MachineFunction::iterator MFI) {
    200   if (I == MFI->begin()) {
    201     if (MFI->isPredecessor(&*MFI)) {
    202       I = --MFI->end();
    203       return true;
    204     } else
    205       return false;
    206   }
    207   --I;
    208   return true;
    209 }
    210 
    211 MachineBasicBlock::iterator
    212 FixupLEAPass::searchBackwards(MachineOperand &p, MachineBasicBlock::iterator &I,
    213                               MachineFunction::iterator MFI) {
    214   int InstrDistance = 1;
    215   MachineBasicBlock::iterator CurInst;
    216   static const int INSTR_DISTANCE_THRESHOLD = 5;
    217 
    218   CurInst = I;
    219   bool Found;
    220   Found = getPreviousInstr(CurInst, MFI);
    221   while (Found && I != CurInst) {
    222     if (CurInst->isCall() || CurInst->isInlineAsm())
    223       break;
    224     if (InstrDistance > INSTR_DISTANCE_THRESHOLD)
    225       break; // too far back to make a difference
    226     if (usesRegister(p, CurInst) == RU_Write) {
    227       return CurInst;
    228     }
    229     InstrDistance += TII->getInstrLatency(
    230         MF->getSubtarget().getInstrItineraryData(), CurInst);
    231     Found = getPreviousInstr(CurInst, MFI);
    232   }
    233   return nullptr;
    234 }
    235 
    236 static inline bool isLEA(const int opcode) {
    237   return opcode == X86::LEA16r || opcode == X86::LEA32r ||
    238          opcode == X86::LEA64r || opcode == X86::LEA64_32r;
    239 }
    240 
    241 /// isLEASimpleIncOrDec - Does this LEA have one these forms:
    242 /// lea  %reg, 1(%reg)
    243 /// lea  %reg, -1(%reg)
    244 static inline bool isLEASimpleIncOrDec(MachineInstr *LEA) {
    245   unsigned SrcReg = LEA->getOperand(1 + X86::AddrBaseReg).getReg();
    246   unsigned DstReg = LEA->getOperand(0).getReg();
    247   unsigned AddrDispOp = 1 + X86::AddrDisp;
    248   return SrcReg == DstReg &&
    249          LEA->getOperand(1 + X86::AddrIndexReg).getReg() == 0 &&
    250          LEA->getOperand(1 + X86::AddrSegmentReg).getReg() == 0 &&
    251          LEA->getOperand(AddrDispOp).isImm() &&
    252          (LEA->getOperand(AddrDispOp).getImm() == 1 ||
    253           LEA->getOperand(AddrDispOp).getImm() == -1);
    254 }
    255 
    256 bool FixupLEAPass::fixupIncDec(MachineBasicBlock::iterator &I,
    257                                MachineFunction::iterator MFI) const {
    258   MachineInstr *MI = I;
    259   int Opcode = MI->getOpcode();
    260   if (!isLEA(Opcode))
    261     return false;
    262 
    263   if (isLEASimpleIncOrDec(MI) && TII->isSafeToClobberEFLAGS(*MFI, I)) {
    264     int NewOpcode;
    265     bool isINC = MI->getOperand(4).getImm() == 1;
    266     switch (Opcode) {
    267     case X86::LEA16r:
    268       NewOpcode = isINC ? X86::INC16r : X86::DEC16r;
    269       break;
    270     case X86::LEA32r:
    271     case X86::LEA64_32r:
    272       NewOpcode = isINC ? X86::INC32r : X86::DEC32r;
    273       break;
    274     case X86::LEA64r:
    275       NewOpcode = isINC ? X86::INC64r : X86::DEC64r;
    276       break;
    277     }
    278 
    279     MachineInstr *NewMI =
    280         BuildMI(*MFI, I, MI->getDebugLoc(), TII->get(NewOpcode))
    281             .addOperand(MI->getOperand(0))
    282             .addOperand(MI->getOperand(1));
    283     MFI->erase(I);
    284     I = static_cast<MachineBasicBlock::iterator>(NewMI);
    285     return true;
    286   }
    287   return false;
    288 }
    289 
    290 void FixupLEAPass::processInstruction(MachineBasicBlock::iterator &I,
    291                                       MachineFunction::iterator MFI) {
    292   // Process a load, store, or LEA instruction.
    293   MachineInstr *MI = I;
    294   int opcode = MI->getOpcode();
    295   const MCInstrDesc &Desc = MI->getDesc();
    296   int AddrOffset = X86II::getMemoryOperandNo(Desc.TSFlags, opcode);
    297   if (AddrOffset >= 0) {
    298     AddrOffset += X86II::getOperandBias(Desc);
    299     MachineOperand &p = MI->getOperand(AddrOffset + X86::AddrBaseReg);
    300     if (p.isReg() && p.getReg() != X86::ESP) {
    301       seekLEAFixup(p, I, MFI);
    302     }
    303     MachineOperand &q = MI->getOperand(AddrOffset + X86::AddrIndexReg);
    304     if (q.isReg() && q.getReg() != X86::ESP) {
    305       seekLEAFixup(q, I, MFI);
    306     }
    307   }
    308 }
    309 
    310 void FixupLEAPass::seekLEAFixup(MachineOperand &p,
    311                                 MachineBasicBlock::iterator &I,
    312                                 MachineFunction::iterator MFI) {
    313   MachineBasicBlock::iterator MBI = searchBackwards(p, I, MFI);
    314   if (MBI) {
    315     MachineInstr *NewMI = postRAConvertToLEA(MFI, MBI);
    316     if (NewMI) {
    317       ++NumLEAs;
    318       DEBUG(dbgs() << "FixLEA: Candidate to replace:"; MBI->dump(););
    319       // now to replace with an equivalent LEA...
    320       DEBUG(dbgs() << "FixLEA: Replaced by: "; NewMI->dump(););
    321       MFI->erase(MBI);
    322       MachineBasicBlock::iterator J =
    323           static_cast<MachineBasicBlock::iterator>(NewMI);
    324       processInstruction(J, MFI);
    325     }
    326   }
    327 }
    328 
    329 void FixupLEAPass::processInstructionForSLM(MachineBasicBlock::iterator &I,
    330                                             MachineFunction::iterator MFI) {
    331   MachineInstr *MI = I;
    332   const int opcode = MI->getOpcode();
    333   if (!isLEA(opcode))
    334     return;
    335   if (MI->getOperand(5).getReg() != 0 || !MI->getOperand(4).isImm() ||
    336       !TII->isSafeToClobberEFLAGS(*MFI, I))
    337     return;
    338   const unsigned DstR = MI->getOperand(0).getReg();
    339   const unsigned SrcR1 = MI->getOperand(1).getReg();
    340   const unsigned SrcR2 = MI->getOperand(3).getReg();
    341   if ((SrcR1 == 0 || SrcR1 != DstR) && (SrcR2 == 0 || SrcR2 != DstR))
    342     return;
    343   if (MI->getOperand(2).getImm() > 1)
    344     return;
    345   int addrr_opcode, addri_opcode;
    346   switch (opcode) {
    347   default:
    348     llvm_unreachable("Unexpected LEA instruction");
    349   case X86::LEA16r:
    350     addrr_opcode = X86::ADD16rr;
    351     addri_opcode = X86::ADD16ri;
    352     break;
    353   case X86::LEA32r:
    354     addrr_opcode = X86::ADD32rr;
    355     addri_opcode = X86::ADD32ri;
    356     break;
    357   case X86::LEA64_32r:
    358   case X86::LEA64r:
    359     addrr_opcode = X86::ADD64rr;
    360     addri_opcode = X86::ADD64ri32;
    361     break;
    362   }
    363   DEBUG(dbgs() << "FixLEA: Candidate to replace:"; I->dump(););
    364   DEBUG(dbgs() << "FixLEA: Replaced by: ";);
    365   MachineInstr *NewMI = nullptr;
    366   const MachineOperand &Dst = MI->getOperand(0);
    367   // Make ADD instruction for two registers writing to LEA's destination
    368   if (SrcR1 != 0 && SrcR2 != 0) {
    369     const MachineOperand &Src1 = MI->getOperand(SrcR1 == DstR ? 1 : 3);
    370     const MachineOperand &Src2 = MI->getOperand(SrcR1 == DstR ? 3 : 1);
    371     NewMI = BuildMI(*MF, MI->getDebugLoc(), TII->get(addrr_opcode))
    372                 .addOperand(Dst)
    373                 .addOperand(Src1)
    374                 .addOperand(Src2);
    375     MFI->insert(I, NewMI);
    376     DEBUG(NewMI->dump(););
    377   }
    378   // Make ADD instruction for immediate
    379   if (MI->getOperand(4).getImm() != 0) {
    380     const MachineOperand &SrcR = MI->getOperand(SrcR1 == DstR ? 1 : 3);
    381     NewMI = BuildMI(*MF, MI->getDebugLoc(), TII->get(addri_opcode))
    382                 .addOperand(Dst)
    383                 .addOperand(SrcR)
    384                 .addImm(MI->getOperand(4).getImm());
    385     MFI->insert(I, NewMI);
    386     DEBUG(NewMI->dump(););
    387   }
    388   if (NewMI) {
    389     MFI->erase(I);
    390     I = static_cast<MachineBasicBlock::iterator>(NewMI);
    391   }
    392 }
    393 
    394 bool FixupLEAPass::processBasicBlock(MachineFunction &MF,
    395                                      MachineFunction::iterator MFI) {
    396 
    397   for (MachineBasicBlock::iterator I = MFI->begin(); I != MFI->end(); ++I) {
    398     if (OptIncDec)
    399       if (fixupIncDec(I, MFI))
    400         continue;
    401 
    402     if (OptLEA) {
    403       if (MF.getSubtarget<X86Subtarget>().isSLM())
    404         processInstructionForSLM(I, MFI);
    405       else
    406         processInstruction(I, MFI);
    407     }
    408   }
    409   return false;
    410 }
    411