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   // This pass runs after regalloc and doesn't support VReg operands.
     96   MachineFunctionProperties getRequiredProperties() const override {
     97     return MachineFunctionProperties().set(
     98         MachineFunctionProperties::Property::AllVRegsAllocated);
     99   }
    100 
    101 private:
    102   MachineFunction *MF;
    103   const X86InstrInfo *TII; // Machine instruction info.
    104   bool OptIncDec;
    105   bool OptLEA;
    106 };
    107 char FixupLEAPass::ID = 0;
    108 }
    109 
    110 MachineInstr *
    111 FixupLEAPass::postRAConvertToLEA(MachineFunction::iterator &MFI,
    112                                  MachineBasicBlock::iterator &MBBI) const {
    113   MachineInstr &MI = *MBBI;
    114   switch (MI.getOpcode()) {
    115   case X86::MOV32rr:
    116   case X86::MOV64rr: {
    117     const MachineOperand &Src = MI.getOperand(1);
    118     const MachineOperand &Dest = MI.getOperand(0);
    119     MachineInstr *NewMI =
    120         BuildMI(*MF, MI.getDebugLoc(),
    121                 TII->get(MI.getOpcode() == X86::MOV32rr ? X86::LEA32r
    122                                                         : X86::LEA64r))
    123             .addOperand(Dest)
    124             .addOperand(Src)
    125             .addImm(1)
    126             .addReg(0)
    127             .addImm(0)
    128             .addReg(0);
    129     MFI->insert(MBBI, NewMI); // Insert the new inst
    130     return NewMI;
    131   }
    132   case X86::ADD64ri32:
    133   case X86::ADD64ri8:
    134   case X86::ADD64ri32_DB:
    135   case X86::ADD64ri8_DB:
    136   case X86::ADD32ri:
    137   case X86::ADD32ri8:
    138   case X86::ADD32ri_DB:
    139   case X86::ADD32ri8_DB:
    140   case X86::ADD16ri:
    141   case X86::ADD16ri8:
    142   case X86::ADD16ri_DB:
    143   case X86::ADD16ri8_DB:
    144     if (!MI.getOperand(2).isImm()) {
    145       // convertToThreeAddress will call getImm()
    146       // which requires isImm() to be true
    147       return nullptr;
    148     }
    149     break;
    150   case X86::ADD16rr:
    151   case X86::ADD16rr_DB:
    152     if (MI.getOperand(1).getReg() != MI.getOperand(2).getReg()) {
    153       // if src1 != src2, then convertToThreeAddress will
    154       // need to create a Virtual register, which we cannot do
    155       // after register allocation.
    156       return nullptr;
    157     }
    158   }
    159   return TII->convertToThreeAddress(MFI, MI, nullptr);
    160 }
    161 
    162 FunctionPass *llvm::createX86FixupLEAs() { return new FixupLEAPass(); }
    163 
    164 bool FixupLEAPass::runOnMachineFunction(MachineFunction &Func) {
    165   if (skipFunction(*Func.getFunction()))
    166     return false;
    167 
    168   MF = &Func;
    169   const X86Subtarget &ST = Func.getSubtarget<X86Subtarget>();
    170   OptIncDec = !ST.slowIncDec() || Func.getFunction()->optForMinSize();
    171   OptLEA = ST.LEAusesAG() || ST.slowLEA();
    172 
    173   if (!OptLEA && !OptIncDec)
    174     return false;
    175 
    176   TII = ST.getInstrInfo();
    177 
    178   DEBUG(dbgs() << "Start X86FixupLEAs\n";);
    179   // Process all basic blocks.
    180   for (MachineFunction::iterator I = Func.begin(), E = Func.end(); I != E; ++I)
    181     processBasicBlock(Func, I);
    182   DEBUG(dbgs() << "End X86FixupLEAs\n";);
    183 
    184   return true;
    185 }
    186 
    187 FixupLEAPass::RegUsageState
    188 FixupLEAPass::usesRegister(MachineOperand &p, MachineBasicBlock::iterator I) {
    189   RegUsageState RegUsage = RU_NotUsed;
    190   MachineInstr &MI = *I;
    191 
    192   for (unsigned int i = 0; i < MI.getNumOperands(); ++i) {
    193     MachineOperand &opnd = MI.getOperand(i);
    194     if (opnd.isReg() && opnd.getReg() == p.getReg()) {
    195       if (opnd.isDef())
    196         return RU_Write;
    197       RegUsage = RU_Read;
    198     }
    199   }
    200   return RegUsage;
    201 }
    202 
    203 /// getPreviousInstr - Given a reference to an instruction in a basic
    204 /// block, return a reference to the previous instruction in the block,
    205 /// wrapping around to the last instruction of the block if the block
    206 /// branches to itself.
    207 static inline bool getPreviousInstr(MachineBasicBlock::iterator &I,
    208                                     MachineFunction::iterator MFI) {
    209   if (I == MFI->begin()) {
    210     if (MFI->isPredecessor(&*MFI)) {
    211       I = --MFI->end();
    212       return true;
    213     } else
    214       return false;
    215   }
    216   --I;
    217   return true;
    218 }
    219 
    220 MachineBasicBlock::iterator
    221 FixupLEAPass::searchBackwards(MachineOperand &p, MachineBasicBlock::iterator &I,
    222                               MachineFunction::iterator MFI) {
    223   int InstrDistance = 1;
    224   MachineBasicBlock::iterator CurInst;
    225   static const int INSTR_DISTANCE_THRESHOLD = 5;
    226 
    227   CurInst = I;
    228   bool Found;
    229   Found = getPreviousInstr(CurInst, MFI);
    230   while (Found && I != CurInst) {
    231     if (CurInst->isCall() || CurInst->isInlineAsm())
    232       break;
    233     if (InstrDistance > INSTR_DISTANCE_THRESHOLD)
    234       break; // too far back to make a difference
    235     if (usesRegister(p, CurInst) == RU_Write) {
    236       return CurInst;
    237     }
    238     InstrDistance += TII->getInstrLatency(
    239         MF->getSubtarget().getInstrItineraryData(), *CurInst);
    240     Found = getPreviousInstr(CurInst, MFI);
    241   }
    242   return MachineBasicBlock::iterator();
    243 }
    244 
    245 static inline bool isLEA(const int opcode) {
    246   return opcode == X86::LEA16r || opcode == X86::LEA32r ||
    247          opcode == X86::LEA64r || opcode == X86::LEA64_32r;
    248 }
    249 
    250 /// isLEASimpleIncOrDec - Does this LEA have one these forms:
    251 /// lea  %reg, 1(%reg)
    252 /// lea  %reg, -1(%reg)
    253 static inline bool isLEASimpleIncOrDec(MachineInstr &LEA) {
    254   unsigned SrcReg = LEA.getOperand(1 + X86::AddrBaseReg).getReg();
    255   unsigned DstReg = LEA.getOperand(0).getReg();
    256   unsigned AddrDispOp = 1 + X86::AddrDisp;
    257   return SrcReg == DstReg &&
    258          LEA.getOperand(1 + X86::AddrIndexReg).getReg() == 0 &&
    259          LEA.getOperand(1 + X86::AddrSegmentReg).getReg() == 0 &&
    260          LEA.getOperand(AddrDispOp).isImm() &&
    261          (LEA.getOperand(AddrDispOp).getImm() == 1 ||
    262           LEA.getOperand(AddrDispOp).getImm() == -1);
    263 }
    264 
    265 bool FixupLEAPass::fixupIncDec(MachineBasicBlock::iterator &I,
    266                                MachineFunction::iterator MFI) const {
    267   MachineInstr &MI = *I;
    268   int Opcode = MI.getOpcode();
    269   if (!isLEA(Opcode))
    270     return false;
    271 
    272   if (isLEASimpleIncOrDec(MI) && TII->isSafeToClobberEFLAGS(*MFI, I)) {
    273     int NewOpcode;
    274     bool isINC = MI.getOperand(4).getImm() == 1;
    275     switch (Opcode) {
    276     case X86::LEA16r:
    277       NewOpcode = isINC ? X86::INC16r : X86::DEC16r;
    278       break;
    279     case X86::LEA32r:
    280     case X86::LEA64_32r:
    281       NewOpcode = isINC ? X86::INC32r : X86::DEC32r;
    282       break;
    283     case X86::LEA64r:
    284       NewOpcode = isINC ? X86::INC64r : X86::DEC64r;
    285       break;
    286     }
    287 
    288     MachineInstr *NewMI =
    289         BuildMI(*MFI, I, MI.getDebugLoc(), TII->get(NewOpcode))
    290             .addOperand(MI.getOperand(0))
    291             .addOperand(MI.getOperand(1));
    292     MFI->erase(I);
    293     I = static_cast<MachineBasicBlock::iterator>(NewMI);
    294     return true;
    295   }
    296   return false;
    297 }
    298 
    299 void FixupLEAPass::processInstruction(MachineBasicBlock::iterator &I,
    300                                       MachineFunction::iterator MFI) {
    301   // Process a load, store, or LEA instruction.
    302   MachineInstr &MI = *I;
    303   const MCInstrDesc &Desc = MI.getDesc();
    304   int AddrOffset = X86II::getMemoryOperandNo(Desc.TSFlags);
    305   if (AddrOffset >= 0) {
    306     AddrOffset += X86II::getOperandBias(Desc);
    307     MachineOperand &p = MI.getOperand(AddrOffset + X86::AddrBaseReg);
    308     if (p.isReg() && p.getReg() != X86::ESP) {
    309       seekLEAFixup(p, I, MFI);
    310     }
    311     MachineOperand &q = MI.getOperand(AddrOffset + X86::AddrIndexReg);
    312     if (q.isReg() && q.getReg() != X86::ESP) {
    313       seekLEAFixup(q, I, MFI);
    314     }
    315   }
    316 }
    317 
    318 void FixupLEAPass::seekLEAFixup(MachineOperand &p,
    319                                 MachineBasicBlock::iterator &I,
    320                                 MachineFunction::iterator MFI) {
    321   MachineBasicBlock::iterator MBI = searchBackwards(p, I, MFI);
    322   if (MBI != MachineBasicBlock::iterator()) {
    323     MachineInstr *NewMI = postRAConvertToLEA(MFI, MBI);
    324     if (NewMI) {
    325       ++NumLEAs;
    326       DEBUG(dbgs() << "FixLEA: Candidate to replace:"; MBI->dump(););
    327       // now to replace with an equivalent LEA...
    328       DEBUG(dbgs() << "FixLEA: Replaced by: "; NewMI->dump(););
    329       MFI->erase(MBI);
    330       MachineBasicBlock::iterator J =
    331           static_cast<MachineBasicBlock::iterator>(NewMI);
    332       processInstruction(J, MFI);
    333     }
    334   }
    335 }
    336 
    337 void FixupLEAPass::processInstructionForSLM(MachineBasicBlock::iterator &I,
    338                                             MachineFunction::iterator MFI) {
    339   MachineInstr &MI = *I;
    340   const int opcode = MI.getOpcode();
    341   if (!isLEA(opcode))
    342     return;
    343   if (MI.getOperand(5).getReg() != 0 || !MI.getOperand(4).isImm() ||
    344       !TII->isSafeToClobberEFLAGS(*MFI, I))
    345     return;
    346   const unsigned DstR = MI.getOperand(0).getReg();
    347   const unsigned SrcR1 = MI.getOperand(1).getReg();
    348   const unsigned SrcR2 = MI.getOperand(3).getReg();
    349   if ((SrcR1 == 0 || SrcR1 != DstR) && (SrcR2 == 0 || SrcR2 != DstR))
    350     return;
    351   if (MI.getOperand(2).getImm() > 1)
    352     return;
    353   int addrr_opcode, addri_opcode;
    354   switch (opcode) {
    355   default:
    356     llvm_unreachable("Unexpected LEA instruction");
    357   case X86::LEA16r:
    358     addrr_opcode = X86::ADD16rr;
    359     addri_opcode = X86::ADD16ri;
    360     break;
    361   case X86::LEA32r:
    362     addrr_opcode = X86::ADD32rr;
    363     addri_opcode = X86::ADD32ri;
    364     break;
    365   case X86::LEA64_32r:
    366   case X86::LEA64r:
    367     addrr_opcode = X86::ADD64rr;
    368     addri_opcode = X86::ADD64ri32;
    369     break;
    370   }
    371   DEBUG(dbgs() << "FixLEA: Candidate to replace:"; I->dump(););
    372   DEBUG(dbgs() << "FixLEA: Replaced by: ";);
    373   MachineInstr *NewMI = nullptr;
    374   const MachineOperand &Dst = MI.getOperand(0);
    375   // Make ADD instruction for two registers writing to LEA's destination
    376   if (SrcR1 != 0 && SrcR2 != 0) {
    377     const MachineOperand &Src1 = MI.getOperand(SrcR1 == DstR ? 1 : 3);
    378     const MachineOperand &Src2 = MI.getOperand(SrcR1 == DstR ? 3 : 1);
    379     NewMI = BuildMI(*MF, MI.getDebugLoc(), TII->get(addrr_opcode))
    380                 .addOperand(Dst)
    381                 .addOperand(Src1)
    382                 .addOperand(Src2);
    383     MFI->insert(I, NewMI);
    384     DEBUG(NewMI->dump(););
    385   }
    386   // Make ADD instruction for immediate
    387   if (MI.getOperand(4).getImm() != 0) {
    388     const MachineOperand &SrcR = MI.getOperand(SrcR1 == DstR ? 1 : 3);
    389     NewMI = BuildMI(*MF, MI.getDebugLoc(), TII->get(addri_opcode))
    390                 .addOperand(Dst)
    391                 .addOperand(SrcR)
    392                 .addImm(MI.getOperand(4).getImm());
    393     MFI->insert(I, NewMI);
    394     DEBUG(NewMI->dump(););
    395   }
    396   if (NewMI) {
    397     MFI->erase(I);
    398     I = static_cast<MachineBasicBlock::iterator>(NewMI);
    399   }
    400 }
    401 
    402 bool FixupLEAPass::processBasicBlock(MachineFunction &MF,
    403                                      MachineFunction::iterator MFI) {
    404 
    405   for (MachineBasicBlock::iterator I = MFI->begin(); I != MFI->end(); ++I) {
    406     if (OptIncDec)
    407       if (fixupIncDec(I, MFI))
    408         continue;
    409 
    410     if (OptLEA) {
    411       if (MF.getSubtarget<X86Subtarget>().isSLM())
    412         processInstructionForSLM(I, MFI);
    413       else
    414         processInstruction(I, MFI);
    415     }
    416   }
    417   return false;
    418 }
    419