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"
28using namespace llvm;
29
30#define DEBUG_TYPE "x86-fixup-LEAs"
31
32STATISTIC(NumLEAs, "Number of LEA instructions created");
33
34namespace {
35class 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
87public:
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
95private:
96  MachineFunction *MF;
97  const X86InstrInfo *TII; // Machine instruction info.
98  bool OptIncDec;
99  bool OptLEA;
100};
101char FixupLEAPass::ID = 0;
102}
103
104MachineInstr *
105FixupLEAPass::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
156FunctionPass *llvm::createX86FixupLEAs() { return new FixupLEAPass(); }
157
158bool 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
178FixupLEAPass::RegUsageState
179FixupLEAPass::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.
198static 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
211MachineBasicBlock::iterator
212FixupLEAPass::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
236static 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)
244static 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
256bool 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
290void 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
310void 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
329void 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
394bool 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