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