• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
getPassName() const43   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:
FixupLEAPass()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.
getRequiredProperties() const96   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 *
postRAConvertToLEA(MachineFunction::iterator & MFI,MachineBasicBlock::iterator & MBBI) const111 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 
createX86FixupLEAs()162 FunctionPass *llvm::createX86FixupLEAs() { return new FixupLEAPass(); }
163 
runOnMachineFunction(MachineFunction & Func)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
usesRegister(MachineOperand & p,MachineBasicBlock::iterator I)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.
getPreviousInstr(MachineBasicBlock::iterator & I,MachineFunction::iterator MFI)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
searchBackwards(MachineOperand & p,MachineBasicBlock::iterator & I,MachineFunction::iterator MFI)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 
isLEA(const int opcode)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)
isLEASimpleIncOrDec(MachineInstr & LEA)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 
fixupIncDec(MachineBasicBlock::iterator & I,MachineFunction::iterator MFI) const265 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 
processInstruction(MachineBasicBlock::iterator & I,MachineFunction::iterator MFI)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 
seekLEAFixup(MachineOperand & p,MachineBasicBlock::iterator & I,MachineFunction::iterator MFI)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 
processInstructionForSLM(MachineBasicBlock::iterator & I,MachineFunction::iterator MFI)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 
processBasicBlock(MachineFunction & MF,MachineFunction::iterator MFI)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