1//===-- X86FixupLEAs.cpp - use or replace LEA instructions -----------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines the pass that finds instructions that can be
10// re-written as LEA instructions in order to reduce pipeline delays.
11// It replaces LEAs with ADD/INC/DEC when that is better for size/speed.
12//
13//===----------------------------------------------------------------------===//
14
15#include "X86.h"
16#include "X86InstrInfo.h"
17#include "X86Subtarget.h"
18#include "llvm/ADT/Statistic.h"
19#include "llvm/Analysis/ProfileSummaryInfo.h"
20#include "llvm/CodeGen/LazyMachineBlockFrequencyInfo.h"
21#include "llvm/CodeGen/MachineFunctionPass.h"
22#include "llvm/CodeGen/MachineInstrBuilder.h"
23#include "llvm/CodeGen/MachineSizeOpts.h"
24#include "llvm/CodeGen/Passes.h"
25#include "llvm/CodeGen/TargetSchedule.h"
26#include "llvm/Support/CommandLine.h"
27#include "llvm/Support/Debug.h"
28#include "llvm/Support/raw_ostream.h"
29using namespace llvm;
30
31#define FIXUPLEA_DESC "X86 LEA Fixup"
32#define FIXUPLEA_NAME "x86-fixup-leas"
33
34#define DEBUG_TYPE FIXUPLEA_NAME
35
36STATISTIC(NumLEAs, "Number of LEA instructions created");
37
38namespace {
39class FixupLEAsImpl {
40 enum RegUsageState { RU_NotUsed, RU_Write, RU_Read };
41
42 /// Given a machine register, look for the instruction
43 /// which writes it in the current basic block. If found,
44 /// try to replace it with an equivalent LEA instruction.
45 /// If replacement succeeds, then also process the newly created
46 /// instruction.
47 void seekLEAFixup(MachineOperand &p, MachineBasicBlock::iterator &I,
48 MachineBasicBlock &MBB);
49
50 /// Given a memory access or LEA instruction
51 /// whose address mode uses a base and/or index register, look for
52 /// an opportunity to replace the instruction which sets the base or index
53 /// register with an equivalent LEA instruction.
54 void processInstruction(MachineBasicBlock::iterator &I,
55 MachineBasicBlock &MBB);
56
57 /// Given a LEA instruction which is unprofitable
58 /// on SlowLEA targets try to replace it with an equivalent ADD instruction.
59 void processInstructionForSlowLEA(MachineBasicBlock::iterator &I,
60 MachineBasicBlock &MBB);
61
62 /// Given a LEA instruction which is unprofitable
63 /// on SNB+ try to replace it with other instructions.
64 /// According to Intel's Optimization Reference Manual:
65 /// " For LEA instructions with three source operands and some specific
66 /// situations, instruction latency has increased to 3 cycles, and must
67 /// dispatch via port 1:
68 /// - LEA that has all three source operands: base, index, and offset
69 /// - LEA that uses base and index registers where the base is EBP, RBP,
70 /// or R13
71 /// - LEA that uses RIP relative addressing mode
72 /// - LEA that uses 16-bit addressing mode "
73 /// This function currently handles the first 2 cases only.
74 void processInstrForSlow3OpLEA(MachineBasicBlock::iterator &I,
75 MachineBasicBlock &MBB, bool OptIncDec);
76
77 /// Look for LEAs that are really two address LEAs that we might be able to
78 /// turn into regular ADD instructions.
79 bool optTwoAddrLEA(MachineBasicBlock::iterator &I,
80 MachineBasicBlock &MBB, bool OptIncDec,
81 bool UseLEAForSP) const;
82
83 /// Look for and transform the sequence
84 /// lea (reg1, reg2), reg3
85 /// sub reg3, reg4
86 /// to
87 /// sub reg1, reg4
88 /// sub reg2, reg4
89 /// It can also optimize the sequence lea/add similarly.
90 bool optLEAALU(MachineBasicBlock::iterator &I, MachineBasicBlock &MBB) const;
91
92 /// Step forwards in MBB, looking for an ADD/SUB instruction which uses
93 /// the dest register of LEA instruction I.
94 MachineBasicBlock::iterator searchALUInst(MachineBasicBlock::iterator &I,
95 MachineBasicBlock &MBB) const;
96
97 /// Check instructions between LeaI and AluI (exclusively).
98 /// Set BaseIndexDef to true if base or index register from LeaI is defined.
99 /// Set AluDestRef to true if the dest register of AluI is used or defined.
100 /// *KilledBase is set to the killed base register usage.
101 /// *KilledIndex is set to the killed index register usage.
102 void checkRegUsage(MachineBasicBlock::iterator &LeaI,
103 MachineBasicBlock::iterator &AluI, bool &BaseIndexDef,
104 bool &AluDestRef, MachineOperand **KilledBase,
105 MachineOperand **KilledIndex) const;
106
107 /// Determine if an instruction references a machine register
108 /// and, if so, whether it reads or writes the register.
109 RegUsageState usesRegister(MachineOperand &p, MachineBasicBlock::iterator I);
110
111 /// Step backwards through a basic block, looking
112 /// for an instruction which writes a register within
113 /// a maximum of INSTR_DISTANCE_THRESHOLD instruction latency cycles.
114 MachineBasicBlock::iterator searchBackwards(MachineOperand &p,
115 MachineBasicBlock::iterator &I,
116 MachineBasicBlock &MBB);
117
118 /// if an instruction can be converted to an
119 /// equivalent LEA, insert the new instruction into the basic block
120 /// and return a pointer to it. Otherwise, return zero.
121 MachineInstr *postRAConvertToLEA(MachineBasicBlock &MBB,
122 MachineBasicBlock::iterator &MBBI) const;
123
124public:
125 FixupLEAsImpl(ProfileSummaryInfo *PSI, MachineBlockFrequencyInfo *MBFI)
126 : PSI(PSI), MBFI(MBFI) {}
127
128 /// Loop over all of the basic blocks,
129 /// replacing instructions by equivalent LEA instructions
130 /// if needed and when possible.
131 bool runOnMachineFunction(MachineFunction &MF);
132
133private:
134 TargetSchedModel TSM;
135 const X86InstrInfo *TII = nullptr;
136 const X86RegisterInfo *TRI = nullptr;
137 ProfileSummaryInfo *PSI;
138 MachineBlockFrequencyInfo *MBFI;
139};
140
141class FixupLEAsLegacy : public MachineFunctionPass {
142public:
143 static char ID;
144
145 StringRef getPassName() const override { return FIXUPLEA_DESC; }
146
147 FixupLEAsLegacy() : MachineFunctionPass(ID) {}
148
149 bool runOnMachineFunction(MachineFunction &MF) override;
150
151 // This pass runs after regalloc and doesn't support VReg operands.
152 MachineFunctionProperties getRequiredProperties() const override {
153 return MachineFunctionProperties().setNoVRegs();
154 }
155
156 void getAnalysisUsage(AnalysisUsage &AU) const override {
157 AU.addRequired<ProfileSummaryInfoWrapperPass>();
158 AU.addRequired<LazyMachineBlockFrequencyInfoPass>();
159 MachineFunctionPass::getAnalysisUsage(AU);
160 }
161};
162}
163
164char FixupLEAsLegacy::ID = 0;
165
166INITIALIZE_PASS(FixupLEAsLegacy, FIXUPLEA_NAME, FIXUPLEA_DESC, false, false)
167
168MachineInstr *
169FixupLEAsImpl::postRAConvertToLEA(MachineBasicBlock &MBB,
170 MachineBasicBlock::iterator &MBBI) const {
171 MachineInstr &MI = *MBBI;
172 switch (MI.getOpcode()) {
173 case X86::MOV32rr:
174 case X86::MOV64rr: {
175 const MachineOperand &Src = MI.getOperand(i: 1);
176 const MachineOperand &Dest = MI.getOperand(i: 0);
177 MachineInstr *NewMI =
178 BuildMI(BB&: MBB, I: MBBI, MIMD: MI.getDebugLoc(),
179 MCID: TII->get(Opcode: MI.getOpcode() == X86::MOV32rr ? X86::LEA32r
180 : X86::LEA64r))
181 .add(MO: Dest)
182 .add(MO: Src)
183 .addImm(Val: 1)
184 .addReg(RegNo: 0)
185 .addImm(Val: 0)
186 .addReg(RegNo: 0);
187 return NewMI;
188 }
189 }
190
191 if (!MI.isConvertibleTo3Addr())
192 return nullptr;
193
194 switch (MI.getOpcode()) {
195 default:
196 // Only convert instructions that we've verified are safe.
197 return nullptr;
198 case X86::ADD64ri32:
199 case X86::ADD64ri32_DB:
200 case X86::ADD32ri:
201 case X86::ADD32ri_DB:
202 if (!MI.getOperand(i: 2).isImm()) {
203 // convertToThreeAddress will call getImm()
204 // which requires isImm() to be true
205 return nullptr;
206 }
207 break;
208 case X86::SHL64ri:
209 case X86::SHL32ri:
210 case X86::INC64r:
211 case X86::INC32r:
212 case X86::DEC64r:
213 case X86::DEC32r:
214 case X86::ADD64rr:
215 case X86::ADD64rr_DB:
216 case X86::ADD32rr:
217 case X86::ADD32rr_DB:
218 // These instructions are all fine to convert.
219 break;
220 }
221 return TII->convertToThreeAddress(MI, /*LIS=*/nullptr);
222}
223
224FunctionPass *llvm::createX86FixupLEAsLegacyPass() {
225 return new FixupLEAsLegacy();
226}
227
228static bool isLEA(unsigned Opcode) {
229 return Opcode == X86::LEA32r || Opcode == X86::LEA64r ||
230 Opcode == X86::LEA64_32r;
231}
232
233bool FixupLEAsImpl::runOnMachineFunction(MachineFunction &MF) {
234 const X86Subtarget &ST = MF.getSubtarget<X86Subtarget>();
235 bool IsSlowLEA = ST.slowLEA();
236 bool IsSlow3OpsLEA = ST.slow3OpsLEA();
237 bool LEAUsesAG = ST.leaUsesAG();
238
239 bool OptIncDec = !ST.slowIncDec() || MF.getFunction().hasOptSize();
240 bool UseLEAForSP = ST.useLeaForSP();
241
242 TSM.init(TSInfo: &ST);
243 TII = ST.getInstrInfo();
244 TRI = ST.getRegisterInfo();
245
246 LLVM_DEBUG(dbgs() << "Start X86FixupLEAs\n";);
247 for (MachineBasicBlock &MBB : MF) {
248 // First pass. Try to remove or optimize existing LEAs.
249 bool OptIncDecPerBB =
250 OptIncDec || llvm::shouldOptimizeForSize(MBB: &MBB, PSI, MBFI);
251 for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) {
252 if (!isLEA(Opcode: I->getOpcode()))
253 continue;
254
255 if (optTwoAddrLEA(I, MBB, OptIncDec: OptIncDecPerBB, UseLEAForSP))
256 continue;
257
258 if (IsSlowLEA)
259 processInstructionForSlowLEA(I, MBB);
260 else if (IsSlow3OpsLEA)
261 processInstrForSlow3OpLEA(I, MBB, OptIncDec: OptIncDecPerBB);
262 }
263
264 // Second pass for creating LEAs. This may reverse some of the
265 // transformations above.
266 if (LEAUsesAG) {
267 for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I)
268 processInstruction(I, MBB);
269 }
270 }
271
272 LLVM_DEBUG(dbgs() << "End X86FixupLEAs\n";);
273
274 return true;
275}
276
277FixupLEAsImpl::RegUsageState
278FixupLEAsImpl::usesRegister(MachineOperand &p, MachineBasicBlock::iterator I) {
279 RegUsageState RegUsage = RU_NotUsed;
280 MachineInstr &MI = *I;
281
282 for (const MachineOperand &MO : MI.operands()) {
283 if (MO.isReg() && MO.getReg() == p.getReg()) {
284 if (MO.isDef())
285 return RU_Write;
286 RegUsage = RU_Read;
287 }
288 }
289 return RegUsage;
290}
291
292/// getPreviousInstr - Given a reference to an instruction in a basic
293/// block, return a reference to the previous instruction in the block,
294/// wrapping around to the last instruction of the block if the block
295/// branches to itself.
296static inline bool getPreviousInstr(MachineBasicBlock::iterator &I,
297 MachineBasicBlock &MBB) {
298 if (I == MBB.begin()) {
299 if (MBB.isPredecessor(MBB: &MBB)) {
300 I = --MBB.end();
301 return true;
302 } else
303 return false;
304 }
305 --I;
306 return true;
307}
308
309MachineBasicBlock::iterator FixupLEAsImpl::searchBackwards(
310 MachineOperand &p, MachineBasicBlock::iterator &I, MachineBasicBlock &MBB) {
311 int InstrDistance = 1;
312 MachineBasicBlock::iterator CurInst;
313 static const int INSTR_DISTANCE_THRESHOLD = 5;
314
315 CurInst = I;
316 bool Found;
317 Found = getPreviousInstr(I&: CurInst, MBB);
318 while (Found && I != CurInst) {
319 if (CurInst->isCall() || CurInst->isInlineAsm())
320 break;
321 if (InstrDistance > INSTR_DISTANCE_THRESHOLD)
322 break; // too far back to make a difference
323 if (usesRegister(p, I: CurInst) == RU_Write) {
324 return CurInst;
325 }
326 InstrDistance += TSM.computeInstrLatency(MI: &*CurInst);
327 Found = getPreviousInstr(I&: CurInst, MBB);
328 }
329 return MachineBasicBlock::iterator();
330}
331
332static inline bool isInefficientLEAReg(Register Reg) {
333 return Reg == X86::EBP || Reg == X86::RBP ||
334 Reg == X86::R13D || Reg == X86::R13;
335}
336
337/// Returns true if this LEA uses base and index registers, and the base
338/// register is known to be inefficient for the subtarget.
339// TODO: use a variant scheduling class to model the latency profile
340// of LEA instructions, and implement this logic as a scheduling predicate.
341static inline bool hasInefficientLEABaseReg(const MachineOperand &Base,
342 const MachineOperand &Index) {
343 return Base.isReg() && isInefficientLEAReg(Reg: Base.getReg()) && Index.isReg() &&
344 Index.getReg().isValid();
345}
346
347// Returns true if this operand may have a non-zero offset.
348static inline bool mayHaveOffset(const MachineOperand &Offset) {
349 return !(Offset.isImm() && Offset.getImm() == 0);
350}
351
352static inline unsigned getADDrrFromLEA(unsigned LEAOpcode) {
353 switch (LEAOpcode) {
354 default:
355 llvm_unreachable("Unexpected LEA instruction");
356 case X86::LEA32r:
357 case X86::LEA64_32r:
358 return X86::ADD32rr;
359 case X86::LEA64r:
360 return X86::ADD64rr;
361 }
362}
363
364static inline unsigned getSUBrrFromLEA(unsigned LEAOpcode) {
365 switch (LEAOpcode) {
366 default:
367 llvm_unreachable("Unexpected LEA instruction");
368 case X86::LEA32r:
369 case X86::LEA64_32r:
370 return X86::SUB32rr;
371 case X86::LEA64r:
372 return X86::SUB64rr;
373 }
374}
375
376static inline unsigned getADDriFromLEA(unsigned LEAOpcode,
377 const MachineOperand &Offset) {
378 switch (LEAOpcode) {
379 default:
380 llvm_unreachable("Unexpected LEA instruction");
381 case X86::LEA32r:
382 case X86::LEA64_32r:
383 return X86::ADD32ri;
384 case X86::LEA64r:
385 return X86::ADD64ri32;
386 }
387}
388
389static inline unsigned getSUBriFromLEA(unsigned LEAOpcode) {
390 switch (LEAOpcode) {
391 default:
392 llvm_unreachable("Unexpected LEA instruction");
393 case X86::LEA32r:
394 case X86::LEA64_32r:
395 return X86::SUB32ri;
396 case X86::LEA64r:
397 return X86::SUB64ri32;
398 }
399}
400
401static inline unsigned getINCDECFromLEA(unsigned LEAOpcode, bool IsINC) {
402 switch (LEAOpcode) {
403 default:
404 llvm_unreachable("Unexpected LEA instruction");
405 case X86::LEA32r:
406 case X86::LEA64_32r:
407 return IsINC ? X86::INC32r : X86::DEC32r;
408 case X86::LEA64r:
409 return IsINC ? X86::INC64r : X86::DEC64r;
410 }
411}
412
413MachineBasicBlock::iterator
414FixupLEAsImpl::searchALUInst(MachineBasicBlock::iterator &I,
415 MachineBasicBlock &MBB) const {
416 const X86Subtarget &ST = MBB.getParent()->getSubtarget<X86Subtarget>();
417 unsigned InstrDistance = 1;
418
419 unsigned LEAOpcode = I->getOpcode();
420 unsigned AddOpcode = getADDrrFromLEA(LEAOpcode);
421 unsigned SubOpcode = getSUBrrFromLEA(LEAOpcode);
422 Register DestReg = I->getOperand(i: 0).getReg();
423
424 for (MachineInstr &CurInst : instructionsWithoutDebug(
425 It: std::next(x: I), End: MBB.end(), /*SkipPseudoOp=*/false)) {
426 if (CurInst.isCall() || CurInst.isInlineAsm())
427 break;
428 if (InstrDistance > ST.getCLOpts().fixup_leas_search_distance_threshold)
429 break;
430
431 // Check if the lea dest register is used in an add/sub instruction only.
432 for (unsigned I = 0, E = CurInst.getNumOperands(); I != E; ++I) {
433 MachineOperand &Opnd = CurInst.getOperand(i: I);
434 if (Opnd.isReg()) {
435 if (Opnd.getReg() == DestReg) {
436 if (Opnd.isDef() || !Opnd.isKill())
437 return MachineBasicBlock::iterator();
438
439 unsigned AluOpcode = CurInst.getOpcode();
440 if (AluOpcode != AddOpcode && AluOpcode != SubOpcode)
441 return MachineBasicBlock::iterator();
442
443 MachineOperand &Opnd2 = CurInst.getOperand(i: 3 - I);
444 MachineOperand AluDest = CurInst.getOperand(i: 0);
445 if (Opnd2.getReg() != AluDest.getReg())
446 return MachineBasicBlock::iterator();
447
448 // X - (Y + Z) may generate different flags than (X - Y) - Z when
449 // there is overflow. So we can't change the alu instruction if the
450 // flags register is live.
451 if (!CurInst.registerDefIsDead(Reg: X86::EFLAGS, TRI))
452 return MachineBasicBlock::iterator();
453
454 return CurInst.getIterator();
455 }
456 if (TRI->regsOverlap(RegA: DestReg, RegB: Opnd.getReg()))
457 return MachineBasicBlock::iterator();
458 }
459 }
460
461 InstrDistance++;
462 }
463 return MachineBasicBlock::iterator();
464}
465
466void FixupLEAsImpl::checkRegUsage(MachineBasicBlock::iterator &LeaI,
467 MachineBasicBlock::iterator &AluI,
468 bool &BaseIndexDef, bool &AluDestRef,
469 MachineOperand **KilledBase,
470 MachineOperand **KilledIndex) const {
471 BaseIndexDef = AluDestRef = false;
472 *KilledBase = *KilledIndex = nullptr;
473 Register BaseReg = LeaI->getOperand(i: 1 + X86::AddrBaseReg).getReg();
474 Register IndexReg = LeaI->getOperand(i: 1 + X86::AddrIndexReg).getReg();
475 Register AluDestReg = AluI->getOperand(i: 0).getReg();
476
477 for (MachineInstr &CurInst : llvm::make_range(x: std::next(x: LeaI), y: AluI)) {
478 for (MachineOperand &Opnd : CurInst.operands()) {
479 if (!Opnd.isReg())
480 continue;
481 Register Reg = Opnd.getReg();
482 if (TRI->regsOverlap(RegA: Reg, RegB: AluDestReg))
483 AluDestRef = true;
484 if (TRI->regsOverlap(RegA: Reg, RegB: BaseReg)) {
485 if (Opnd.isDef())
486 BaseIndexDef = true;
487 else if (Opnd.isKill())
488 *KilledBase = &Opnd;
489 }
490 if (TRI->regsOverlap(RegA: Reg, RegB: IndexReg)) {
491 if (Opnd.isDef())
492 BaseIndexDef = true;
493 else if (Opnd.isKill())
494 *KilledIndex = &Opnd;
495 }
496 }
497 }
498}
499
500bool FixupLEAsImpl::optLEAALU(MachineBasicBlock::iterator &I,
501 MachineBasicBlock &MBB) const {
502 // Look for an add/sub instruction which uses the result of lea.
503 MachineBasicBlock::iterator AluI = searchALUInst(I, MBB);
504 if (AluI == MachineBasicBlock::iterator())
505 return false;
506
507 // Check if there are any related register usage between lea and alu.
508 bool BaseIndexDef, AluDestRef;
509 MachineOperand *KilledBase, *KilledIndex;
510 checkRegUsage(LeaI&: I, AluI, BaseIndexDef, AluDestRef, KilledBase: &KilledBase, KilledIndex: &KilledIndex);
511
512 MachineBasicBlock::iterator InsertPos = AluI;
513 if (BaseIndexDef) {
514 if (AluDestRef)
515 return false;
516 InsertPos = I;
517 KilledBase = KilledIndex = nullptr;
518 }
519
520 // Check if there are same registers.
521 Register AluDestReg = AluI->getOperand(i: 0).getReg();
522 Register BaseReg = I->getOperand(i: 1 + X86::AddrBaseReg).getReg();
523 Register IndexReg = I->getOperand(i: 1 + X86::AddrIndexReg).getReg();
524 if (I->getOpcode() == X86::LEA64_32r) {
525 BaseReg = TRI->getSubReg(Reg: BaseReg, Idx: X86::sub_32bit);
526 IndexReg = TRI->getSubReg(Reg: IndexReg, Idx: X86::sub_32bit);
527 }
528 if (AluDestReg == IndexReg) {
529 if (BaseReg == IndexReg)
530 return false;
531 std::swap(a&: BaseReg, b&: IndexReg);
532 std::swap(a&: KilledBase, b&: KilledIndex);
533 }
534 if (BaseReg == IndexReg)
535 KilledBase = nullptr;
536
537 // Now it's safe to change instructions.
538 MachineInstr *NewMI1, *NewMI2;
539 unsigned NewOpcode = AluI->getOpcode();
540 NewMI1 = BuildMI(BB&: MBB, I: InsertPos, MIMD: AluI->getDebugLoc(), MCID: TII->get(Opcode: NewOpcode),
541 DestReg: AluDestReg)
542 .addReg(RegNo: AluDestReg, Flags: RegState::Kill)
543 .addReg(RegNo: BaseReg, Flags: getKillRegState(B: KilledBase));
544 NewMI1->addRegisterDead(Reg: X86::EFLAGS, RegInfo: TRI);
545 NewMI2 = BuildMI(BB&: MBB, I: InsertPos, MIMD: AluI->getDebugLoc(), MCID: TII->get(Opcode: NewOpcode),
546 DestReg: AluDestReg)
547 .addReg(RegNo: AluDestReg, Flags: RegState::Kill)
548 .addReg(RegNo: IndexReg, Flags: getKillRegState(B: KilledIndex));
549 NewMI2->addRegisterDead(Reg: X86::EFLAGS, RegInfo: TRI);
550
551 // Clear the old Kill flags.
552 if (KilledBase)
553 KilledBase->setIsKill(false);
554 if (KilledIndex)
555 KilledIndex->setIsKill(false);
556
557 MBB.getParent()->substituteDebugValuesForInst(Old: *AluI, New&: *NewMI2, MaxOperand: 1);
558 MBB.erase(I);
559 MBB.erase(I: AluI);
560 I = NewMI1;
561 return true;
562}
563
564bool FixupLEAsImpl::optTwoAddrLEA(MachineBasicBlock::iterator &I,
565 MachineBasicBlock &MBB, bool OptIncDec,
566 bool UseLEAForSP) const {
567 MachineInstr &MI = *I;
568
569 const MachineOperand &Base = MI.getOperand(i: 1 + X86::AddrBaseReg);
570 const MachineOperand &Scale = MI.getOperand(i: 1 + X86::AddrScaleAmt);
571 const MachineOperand &Index = MI.getOperand(i: 1 + X86::AddrIndexReg);
572 const MachineOperand &Disp = MI.getOperand(i: 1 + X86::AddrDisp);
573 const MachineOperand &Segment = MI.getOperand(i: 1 + X86::AddrSegmentReg);
574
575 if (Segment.getReg().isValid() || !Disp.isImm() || Scale.getImm() > 1 ||
576 MBB.computeRegisterLiveness(TRI, Reg: X86::EFLAGS, Before: I) !=
577 MachineBasicBlock::LQR_Dead)
578 return false;
579
580 Register DestReg = MI.getOperand(i: 0).getReg();
581 Register BaseReg = Base.getReg();
582 Register IndexReg = Index.getReg();
583
584 // Don't change stack adjustment LEAs.
585 if (UseLEAForSP && (DestReg == X86::ESP || DestReg == X86::RSP))
586 return false;
587
588 // LEA64_32 has 64-bit operands but 32-bit result.
589 if (MI.getOpcode() == X86::LEA64_32r) {
590 if (BaseReg)
591 BaseReg = TRI->getSubReg(Reg: BaseReg, Idx: X86::sub_32bit);
592 if (IndexReg)
593 IndexReg = TRI->getSubReg(Reg: IndexReg, Idx: X86::sub_32bit);
594 }
595
596 MachineInstr *NewMI = nullptr;
597
598 // Case 1.
599 // Look for lea(%reg1, %reg2), %reg1 or lea(%reg2, %reg1), %reg1
600 // which can be turned into add %reg2, %reg1
601 if (BaseReg.isValid() && IndexReg.isValid() && Disp.getImm() == 0 &&
602 (DestReg == BaseReg || DestReg == IndexReg)) {
603 unsigned NewOpcode = getADDrrFromLEA(LEAOpcode: MI.getOpcode());
604 if (DestReg != BaseReg)
605 std::swap(a&: BaseReg, b&: IndexReg);
606
607 if (MI.getOpcode() == X86::LEA64_32r) {
608 // TODO: Do we need the super register implicit use?
609 NewMI = BuildMI(BB&: MBB, I, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: NewOpcode), DestReg)
610 .addReg(RegNo: BaseReg).addReg(RegNo: IndexReg)
611 .addReg(RegNo: Base.getReg(), Flags: RegState::Implicit)
612 .addReg(RegNo: Index.getReg(), Flags: RegState::Implicit);
613 } else {
614 NewMI = BuildMI(BB&: MBB, I, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: NewOpcode), DestReg)
615 .addReg(RegNo: BaseReg).addReg(RegNo: IndexReg);
616 }
617 } else if (DestReg == BaseReg && !IndexReg) {
618 // Case 2.
619 // This is an LEA with only a base register and a displacement,
620 // We can use ADDri or INC/DEC.
621
622 // Does this LEA have one these forms:
623 // lea %reg, 1(%reg)
624 // lea %reg, -1(%reg)
625 if (OptIncDec && (Disp.getImm() == 1 || Disp.getImm() == -1)) {
626 bool IsINC = Disp.getImm() == 1;
627 unsigned NewOpcode = getINCDECFromLEA(LEAOpcode: MI.getOpcode(), IsINC);
628
629 if (MI.getOpcode() == X86::LEA64_32r) {
630 // TODO: Do we need the super register implicit use?
631 NewMI = BuildMI(BB&: MBB, I, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: NewOpcode), DestReg)
632 .addReg(RegNo: BaseReg).addReg(RegNo: Base.getReg(), Flags: RegState::Implicit);
633 } else {
634 NewMI = BuildMI(BB&: MBB, I, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: NewOpcode), DestReg)
635 .addReg(RegNo: BaseReg);
636 }
637 } else {
638 unsigned NewOpcode = getADDriFromLEA(LEAOpcode: MI.getOpcode(), Offset: Disp);
639 if (MI.getOpcode() == X86::LEA64_32r) {
640 // TODO: Do we need the super register implicit use?
641 NewMI = BuildMI(BB&: MBB, I, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: NewOpcode), DestReg)
642 .addReg(RegNo: BaseReg).addImm(Val: Disp.getImm())
643 .addReg(RegNo: Base.getReg(), Flags: RegState::Implicit);
644 } else {
645 NewMI = BuildMI(BB&: MBB, I, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: NewOpcode), DestReg)
646 .addReg(RegNo: BaseReg).addImm(Val: Disp.getImm());
647 }
648 }
649 } else if (BaseReg.isValid() && IndexReg.isValid() && Disp.getImm() == 0) {
650 // Case 3.
651 // Look for and transform the sequence
652 // lea (reg1, reg2), reg3
653 // sub reg3, reg4
654 return optLEAALU(I, MBB);
655 } else
656 return false;
657
658 MBB.getParent()->substituteDebugValuesForInst(Old: *I, New&: *NewMI, MaxOperand: 1);
659 MBB.erase(I);
660 I = NewMI;
661 return true;
662}
663
664void FixupLEAsImpl::processInstruction(MachineBasicBlock::iterator &I,
665 MachineBasicBlock &MBB) {
666 // Process a load, store, or LEA instruction.
667 MachineInstr &MI = *I;
668 int AddrOffset = X86II::getMemoryOperandIdx(Desc: MI.getDesc());
669 if (AddrOffset >= 0) {
670 MachineOperand &p = MI.getOperand(i: AddrOffset + X86::AddrBaseReg);
671 if (p.isReg() && p.getReg() != X86::ESP) {
672 seekLEAFixup(p, I, MBB);
673 }
674 MachineOperand &q = MI.getOperand(i: AddrOffset + X86::AddrIndexReg);
675 if (q.isReg() && q.getReg() != X86::ESP) {
676 seekLEAFixup(p&: q, I, MBB);
677 }
678 }
679}
680
681void FixupLEAsImpl::seekLEAFixup(MachineOperand &p,
682 MachineBasicBlock::iterator &I,
683 MachineBasicBlock &MBB) {
684 MachineBasicBlock::iterator MBI = searchBackwards(p, I, MBB);
685 if (MBI != MachineBasicBlock::iterator()) {
686 MachineInstr *NewMI = postRAConvertToLEA(MBB, MBBI&: MBI);
687 if (NewMI) {
688 ++NumLEAs;
689 LLVM_DEBUG(dbgs() << "FixLEA: Candidate to replace:"; MBI->dump(););
690 // now to replace with an equivalent LEA...
691 LLVM_DEBUG(dbgs() << "FixLEA: Replaced by: "; NewMI->dump(););
692 MBB.getParent()->substituteDebugValuesForInst(Old: *MBI, New&: *NewMI, MaxOperand: 1);
693 MBB.erase(I: MBI);
694 MachineBasicBlock::iterator J =
695 static_cast<MachineBasicBlock::iterator>(NewMI);
696 processInstruction(I&: J, MBB);
697 }
698 }
699}
700
701void FixupLEAsImpl::processInstructionForSlowLEA(MachineBasicBlock::iterator &I,
702 MachineBasicBlock &MBB) {
703 MachineInstr &MI = *I;
704 const unsigned Opcode = MI.getOpcode();
705
706 const MachineOperand &Dst = MI.getOperand(i: 0);
707 const MachineOperand &Base = MI.getOperand(i: 1 + X86::AddrBaseReg);
708 const MachineOperand &Scale = MI.getOperand(i: 1 + X86::AddrScaleAmt);
709 const MachineOperand &Index = MI.getOperand(i: 1 + X86::AddrIndexReg);
710 const MachineOperand &Offset = MI.getOperand(i: 1 + X86::AddrDisp);
711 const MachineOperand &Segment = MI.getOperand(i: 1 + X86::AddrSegmentReg);
712
713 if (Segment.getReg().isValid() || !Offset.isImm() ||
714 MBB.computeRegisterLiveness(TRI, Reg: X86::EFLAGS, Before: I, Neighborhood: 4) !=
715 MachineBasicBlock::LQR_Dead)
716 return;
717 const Register DstR = Dst.getReg();
718 const Register SrcR1 = Base.getReg();
719 const Register SrcR2 = Index.getReg();
720 if ((!SrcR1 || SrcR1 != DstR) && (!SrcR2 || SrcR2 != DstR))
721 return;
722 if (Scale.getImm() > 1)
723 return;
724 LLVM_DEBUG(dbgs() << "FixLEA: Candidate to replace:"; I->dump(););
725 LLVM_DEBUG(dbgs() << "FixLEA: Replaced by: ";);
726 MachineInstr *NewMI = nullptr;
727 // Make ADD instruction for two registers writing to LEA's destination
728 if (SrcR1 && SrcR2) {
729 const MCInstrDesc &ADDrr = TII->get(Opcode: getADDrrFromLEA(LEAOpcode: Opcode));
730 const MachineOperand &Src = SrcR1 == DstR ? Index : Base;
731 NewMI =
732 BuildMI(BB&: MBB, I, MIMD: MI.getDebugLoc(), MCID: ADDrr, DestReg: DstR).addReg(RegNo: DstR).add(MO: Src);
733 LLVM_DEBUG(NewMI->dump(););
734 }
735 // Make ADD instruction for immediate
736 if (Offset.getImm() != 0) {
737 const MCInstrDesc &ADDri =
738 TII->get(Opcode: getADDriFromLEA(LEAOpcode: Opcode, Offset));
739 const MachineOperand &SrcR = SrcR1 == DstR ? Base : Index;
740 NewMI = BuildMI(BB&: MBB, I, MIMD: MI.getDebugLoc(), MCID: ADDri, DestReg: DstR)
741 .add(MO: SrcR)
742 .addImm(Val: Offset.getImm());
743 LLVM_DEBUG(NewMI->dump(););
744 }
745 if (NewMI) {
746 MBB.getParent()->substituteDebugValuesForInst(Old: *I, New&: *NewMI, MaxOperand: 1);
747 MBB.erase(I);
748 I = NewMI;
749 }
750}
751
752void FixupLEAsImpl::processInstrForSlow3OpLEA(MachineBasicBlock::iterator &I,
753 MachineBasicBlock &MBB,
754 bool OptIncDec) {
755 MachineInstr &MI = *I;
756 const unsigned LEAOpcode = MI.getOpcode();
757
758 const MachineOperand &Dest = MI.getOperand(i: 0);
759 const MachineOperand &Base = MI.getOperand(i: 1 + X86::AddrBaseReg);
760 const MachineOperand &Scale = MI.getOperand(i: 1 + X86::AddrScaleAmt);
761 const MachineOperand &Index = MI.getOperand(i: 1 + X86::AddrIndexReg);
762 const MachineOperand &Offset = MI.getOperand(i: 1 + X86::AddrDisp);
763 const MachineOperand &Segment = MI.getOperand(i: 1 + X86::AddrSegmentReg);
764
765 if (!(TII->isThreeOperandsLEA(MI) || hasInefficientLEABaseReg(Base, Index)) ||
766 MBB.computeRegisterLiveness(TRI, Reg: X86::EFLAGS, Before: I, Neighborhood: 4) !=
767 MachineBasicBlock::LQR_Dead ||
768 Segment.getReg().isValid())
769 return;
770
771 Register DestReg = Dest.getReg();
772 Register BaseReg = Base.getReg();
773 Register IndexReg = Index.getReg();
774
775 if (MI.getOpcode() == X86::LEA64_32r) {
776 if (BaseReg)
777 BaseReg = TRI->getSubReg(Reg: BaseReg, Idx: X86::sub_32bit);
778 if (IndexReg)
779 IndexReg = TRI->getSubReg(Reg: IndexReg, Idx: X86::sub_32bit);
780 }
781
782 bool IsScale1 = Scale.getImm() == 1;
783 bool IsInefficientBase = isInefficientLEAReg(Reg: BaseReg);
784 bool IsInefficientIndex = isInefficientLEAReg(Reg: IndexReg);
785
786 // Skip these cases since it takes more than 2 instructions
787 // to replace the LEA instruction.
788 if (IsInefficientBase && DestReg == BaseReg && !IsScale1)
789 return;
790
791 LLVM_DEBUG(dbgs() << "FixLEA: Candidate to replace:"; MI.dump(););
792 LLVM_DEBUG(dbgs() << "FixLEA: Replaced by: ";);
793
794 MachineInstr *NewMI = nullptr;
795 bool BaseOrIndexIsDst = DestReg == BaseReg || DestReg == IndexReg;
796 // First try and remove the base while sticking with LEA iff base == index and
797 // scale == 1. We can handle:
798 // 1. lea D(%base,%index,1) -> lea D(,%index,2)
799 // 2. lea D(%r13/%rbp,%index) -> lea D(,%index,2)
800 // Only do this if the LEA would otherwise be split into 2-instruction
801 // (either it has a an Offset or neither base nor index are dst)
802 if (IsScale1 && BaseReg == IndexReg &&
803 (mayHaveOffset(Offset) || (IsInefficientBase && !BaseOrIndexIsDst))) {
804 NewMI = BuildMI(BB&: MBB, I&: MI, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: LEAOpcode))
805 .add(MO: Dest)
806 .addReg(RegNo: 0)
807 .addImm(Val: 2)
808 .add(MO: Index)
809 .add(MO: Offset)
810 .add(MO: Segment);
811 LLVM_DEBUG(NewMI->dump(););
812
813 MBB.getParent()->substituteDebugValuesForInst(Old: *I, New&: *NewMI, MaxOperand: 1);
814 MBB.erase(I);
815 I = NewMI;
816 return;
817 } else if (IsScale1 && BaseOrIndexIsDst) {
818 // Try to replace LEA with one or two (for the 3-op LEA case)
819 // add instructions:
820 // 1.lea (%base,%index,1), %base => add %index,%base
821 // 2.lea (%base,%index,1), %index => add %base,%index
822
823 unsigned NewOpc = getADDrrFromLEA(LEAOpcode: MI.getOpcode());
824 if (DestReg != BaseReg)
825 std::swap(a&: BaseReg, b&: IndexReg);
826
827 if (MI.getOpcode() == X86::LEA64_32r) {
828 // TODO: Do we need the super register implicit use?
829 NewMI = BuildMI(BB&: MBB, I, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: NewOpc), DestReg)
830 .addReg(RegNo: BaseReg)
831 .addReg(RegNo: IndexReg)
832 .addReg(RegNo: Base.getReg(), Flags: RegState::Implicit)
833 .addReg(RegNo: Index.getReg(), Flags: RegState::Implicit);
834 } else {
835 NewMI = BuildMI(BB&: MBB, I, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: NewOpc), DestReg)
836 .addReg(RegNo: BaseReg)
837 .addReg(RegNo: IndexReg);
838 }
839 } else if (!IsInefficientBase || (!IsInefficientIndex && IsScale1)) {
840 // If the base is inefficient try switching the index and base operands,
841 // otherwise just break the 3-Ops LEA inst into 2-Ops LEA + ADD instruction:
842 // lea offset(%base,%index,scale),%dst =>
843 // lea (%base,%index,scale); add offset,%dst
844 NewMI = BuildMI(BB&: MBB, I&: MI, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: LEAOpcode))
845 .add(MO: Dest)
846 .add(MO: IsInefficientBase ? Index : Base)
847 .add(MO: Scale)
848 .add(MO: IsInefficientBase ? Base : Index)
849 .addImm(Val: 0)
850 .add(MO: Segment);
851 LLVM_DEBUG(NewMI->dump(););
852 }
853
854 // If either replacement succeeded above, add the offset if needed, then
855 // replace the instruction.
856 if (NewMI) {
857 // Create ADD instruction for the Offset in case of 3-Ops LEA.
858 if (mayHaveOffset(Offset)) {
859 if (OptIncDec && Offset.isImm() &&
860 (Offset.getImm() == 1 || Offset.getImm() == -1)) {
861 unsigned NewOpc =
862 getINCDECFromLEA(LEAOpcode: MI.getOpcode(), IsINC: Offset.getImm() == 1);
863 NewMI = BuildMI(BB&: MBB, I, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: NewOpc), DestReg)
864 .addReg(RegNo: DestReg);
865 LLVM_DEBUG(NewMI->dump(););
866 } else if (Offset.isImm() && Offset.getImm() == 128) {
867 // ADD of +128 needs a 32-bit immediate, while SUB of -128 fits the
868 // sign-extended 8-bit form, three bytes shorter. EFLAGS was proved
869 // dead above, so the different flag results don't matter.
870 unsigned NewOpc = getSUBriFromLEA(LEAOpcode: MI.getOpcode());
871 NewMI = BuildMI(BB&: MBB, I, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: NewOpc), DestReg)
872 .addReg(RegNo: DestReg)
873 .addImm(Val: -128);
874 LLVM_DEBUG(NewMI->dump(););
875 } else {
876 unsigned NewOpc = getADDriFromLEA(LEAOpcode: MI.getOpcode(), Offset);
877 NewMI = BuildMI(BB&: MBB, I, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: NewOpc), DestReg)
878 .addReg(RegNo: DestReg)
879 .add(MO: Offset);
880 LLVM_DEBUG(NewMI->dump(););
881 }
882 }
883
884 MBB.getParent()->substituteDebugValuesForInst(Old: *I, New&: *NewMI, MaxOperand: 1);
885 MBB.erase(I);
886 I = NewMI;
887 return;
888 }
889
890 // Handle the rest of the cases with inefficient base register:
891 assert(DestReg != BaseReg && "DestReg == BaseReg should be handled already!");
892 assert(IsInefficientBase && "efficient base should be handled already!");
893
894 // FIXME: Handle LEA64_32r.
895 if (LEAOpcode == X86::LEA64_32r)
896 return;
897
898 // lea (%base,%index,1), %dst => mov %base,%dst; add %index,%dst
899 if (IsScale1 && !mayHaveOffset(Offset)) {
900 bool BIK = Base.isKill() && BaseReg != IndexReg;
901 TII->copyPhysReg(MBB, MI, DL: MI.getDebugLoc(), DestReg, SrcReg: BaseReg, KillSrc: BIK);
902 LLVM_DEBUG(MI.getPrevNode()->dump(););
903
904 unsigned NewOpc = getADDrrFromLEA(LEAOpcode: MI.getOpcode());
905 NewMI = BuildMI(BB&: MBB, I&: MI, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: NewOpc), DestReg)
906 .addReg(RegNo: DestReg)
907 .add(MO: Index);
908 LLVM_DEBUG(NewMI->dump(););
909
910 MBB.getParent()->substituteDebugValuesForInst(Old: *I, New&: *NewMI, MaxOperand: 1);
911 MBB.erase(I);
912 I = NewMI;
913 return;
914 }
915
916 // lea offset(%base,%index,scale), %dst =>
917 // lea offset( ,%index,scale), %dst; add %base,%dst
918 NewMI = BuildMI(BB&: MBB, I&: MI, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: LEAOpcode))
919 .add(MO: Dest)
920 .addReg(RegNo: 0)
921 .add(MO: Scale)
922 .add(MO: Index)
923 .add(MO: Offset)
924 .add(MO: Segment);
925 LLVM_DEBUG(NewMI->dump(););
926
927 unsigned NewOpc = getADDrrFromLEA(LEAOpcode: MI.getOpcode());
928 NewMI = BuildMI(BB&: MBB, I&: MI, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: NewOpc), DestReg)
929 .addReg(RegNo: DestReg)
930 .add(MO: Base);
931 LLVM_DEBUG(NewMI->dump(););
932
933 MBB.getParent()->substituteDebugValuesForInst(Old: *I, New&: *NewMI, MaxOperand: 1);
934 MBB.erase(I);
935 I = NewMI;
936}
937
938bool FixupLEAsLegacy::runOnMachineFunction(MachineFunction &MF) {
939 if (skipFunction(F: MF.getFunction()))
940 return false;
941
942 auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
943 auto *MBFI = (PSI && PSI->hasProfileSummary())
944 ? &getAnalysis<LazyMachineBlockFrequencyInfoPass>().getBFI()
945 : nullptr;
946 FixupLEAsImpl PassImpl(PSI, MBFI);
947 return PassImpl.runOnMachineFunction(MF);
948}
949
950PreservedAnalyses X86FixupLEAsPass::run(MachineFunction &MF,
951 MachineFunctionAnalysisManager &MFAM) {
952 ProfileSummaryInfo *PSI =
953 MFAM.getResult<ModuleAnalysisManagerMachineFunctionProxy>(IR&: MF)
954 .getCachedResult<ProfileSummaryAnalysis>(
955 IR&: *MF.getFunction().getParent());
956 if (!PSI)
957 report_fatal_error(reason: "x86-fixup-leas requires ProfileSummaryAnalysis", gen_crash_diag: false);
958 MachineBlockFrequencyInfo *MBFI =
959 &MFAM.getResult<MachineBlockFrequencyAnalysis>(IR&: MF);
960
961 FixupLEAsImpl PassImpl(PSI, MBFI);
962 bool Changed = PassImpl.runOnMachineFunction(MF);
963 if (!Changed)
964 return PreservedAnalyses::all();
965 PreservedAnalyses PA = getMachineFunctionPassPreservedAnalyses();
966 PA.preserveSet<CFGAnalyses>();
967 return PA;
968}
969