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 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 *
postRAConvertToLEA(MachineFunction::iterator & MFI,MachineBasicBlock::iterator & MBBI) const105 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
createX86FixupLEAs()156 FunctionPass *llvm::createX86FixupLEAs() { return new FixupLEAPass(); }
157
runOnMachineFunction(MachineFunction & Func)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
usesRegister(MachineOperand & p,MachineBasicBlock::iterator I)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.
getPreviousInstr(MachineBasicBlock::iterator & I,MachineFunction::iterator MFI)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
searchBackwards(MachineOperand & p,MachineBasicBlock::iterator & I,MachineFunction::iterator MFI)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
isLEA(const int opcode)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)
isLEASimpleIncOrDec(MachineInstr * LEA)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
fixupIncDec(MachineBasicBlock::iterator & I,MachineFunction::iterator MFI) const256 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
processInstruction(MachineBasicBlock::iterator & I,MachineFunction::iterator MFI)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
seekLEAFixup(MachineOperand & p,MachineBasicBlock::iterator & I,MachineFunction::iterator MFI)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
processInstructionForSLM(MachineBasicBlock::iterator & I,MachineFunction::iterator MFI)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
processBasicBlock(MachineFunction & MF,MachineFunction::iterator MFI)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