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/Debug.h"
27#include "llvm/Support/raw_ostream.h"
28using namespace llvm;
29
30#define FIXUPLEA_DESC "X86 LEA Fixup"
31#define FIXUPLEA_NAME "x86-fixup-leas"
32
33#define DEBUG_TYPE FIXUPLEA_NAME
34
35STATISTIC(NumLEAs, "Number of LEA instructions created");
36
37namespace {
38class FixupLEAsImpl {
39 enum RegUsageState { RU_NotUsed, RU_Write, RU_Read };
40
41 /// Given a machine register, look for the instruction
42 /// which writes it in the current basic block. If found,
43 /// try to replace it with an equivalent LEA instruction.
44 /// If replacement succeeds, then also process the newly created
45 /// instruction.
46 void seekLEAFixup(MachineOperand &p, MachineBasicBlock::iterator &I,
47 MachineBasicBlock &MBB);
48
49 /// Given a memory access or LEA instruction
50 /// whose address mode uses a base and/or index register, look for
51 /// an opportunity to replace the instruction which sets the base or index
52 /// register with an equivalent LEA instruction.
53 void processInstruction(MachineBasicBlock::iterator &I,
54 MachineBasicBlock &MBB);
55
56 /// Given a LEA instruction which is unprofitable
57 /// on SlowLEA targets try to replace it with an equivalent ADD instruction.
58 void processInstructionForSlowLEA(MachineBasicBlock::iterator &I,
59 MachineBasicBlock &MBB);
60
61 /// Given a LEA instruction which is unprofitable
62 /// on SNB+ try to replace it with other instructions.
63 /// According to Intel's Optimization Reference Manual:
64 /// " For LEA instructions with three source operands and some specific
65 /// situations, instruction latency has increased to 3 cycles, and must
66 /// dispatch via port 1:
67 /// - LEA that has all three source operands: base, index, and offset
68 /// - LEA that uses base and index registers where the base is EBP, RBP,
69 /// or R13
70 /// - LEA that uses RIP relative addressing mode
71 /// - LEA that uses 16-bit addressing mode "
72 /// This function currently handles the first 2 cases only.
73 void processInstrForSlow3OpLEA(MachineBasicBlock::iterator &I,
74 MachineBasicBlock &MBB, bool OptIncDec);
75
76 /// Look for LEAs that are really two address LEAs that we might be able to
77 /// turn into regular ADD instructions.
78 bool optTwoAddrLEA(MachineBasicBlock::iterator &I,
79 MachineBasicBlock &MBB, bool OptIncDec,
80 bool UseLEAForSP) const;
81
82 /// Look for and transform the sequence
83 /// lea (reg1, reg2), reg3
84 /// sub reg3, reg4
85 /// to
86 /// sub reg1, reg4
87 /// sub reg2, reg4
88 /// It can also optimize the sequence lea/add similarly.
89 bool optLEAALU(MachineBasicBlock::iterator &I, MachineBasicBlock &MBB) const;
90
91 /// Step forwards in MBB, looking for an ADD/SUB instruction which uses
92 /// the dest register of LEA instruction I.
93 MachineBasicBlock::iterator searchALUInst(MachineBasicBlock::iterator &I,
94 MachineBasicBlock &MBB) const;
95
96 /// Check instructions between LeaI and AluI (exclusively).
97 /// Set BaseIndexDef to true if base or index register from LeaI is defined.
98 /// Set AluDestRef to true if the dest register of AluI is used or defined.
99 /// *KilledBase is set to the killed base register usage.
100 /// *KilledIndex is set to the killed index register usage.
101 void checkRegUsage(MachineBasicBlock::iterator &LeaI,
102 MachineBasicBlock::iterator &AluI, bool &BaseIndexDef,
103 bool &AluDestRef, MachineOperand **KilledBase,
104 MachineOperand **KilledIndex) const;
105
106 /// Determine if an instruction references a machine register
107 /// and, if so, whether it reads or writes the register.
108 RegUsageState usesRegister(MachineOperand &p, MachineBasicBlock::iterator I);
109
110 /// Step backwards through a basic block, looking
111 /// for an instruction which writes a register within
112 /// a maximum of INSTR_DISTANCE_THRESHOLD instruction latency cycles.
113 MachineBasicBlock::iterator searchBackwards(MachineOperand &p,
114 MachineBasicBlock::iterator &I,
115 MachineBasicBlock &MBB);
116
117 /// if an instruction can be converted to an
118 /// equivalent LEA, insert the new instruction into the basic block
119 /// and return a pointer to it. Otherwise, return zero.
120 MachineInstr *postRAConvertToLEA(MachineBasicBlock &MBB,
121 MachineBasicBlock::iterator &MBBI) const;
122
123public:
124 FixupLEAsImpl(ProfileSummaryInfo *PSI, MachineBlockFrequencyInfo *MBFI)
125 : PSI(PSI), MBFI(MBFI) {}
126
127 /// Loop over all of the basic blocks,
128 /// replacing instructions by equivalent LEA instructions
129 /// if needed and when possible.
130 bool runOnMachineFunction(MachineFunction &MF);
131
132private:
133 TargetSchedModel TSM;
134 const X86InstrInfo *TII = nullptr;
135 const X86RegisterInfo *TRI = nullptr;
136 ProfileSummaryInfo *PSI;
137 MachineBlockFrequencyInfo *MBFI;
138};
139
140class FixupLEAsLegacy : public MachineFunctionPass {
141public:
142 static char ID;
143
144 StringRef getPassName() const override { return FIXUPLEA_DESC; }
145
146 FixupLEAsLegacy() : MachineFunctionPass(ID) {}
147
148 bool runOnMachineFunction(MachineFunction &MF) override;
149
150 // This pass runs after regalloc and doesn't support VReg operands.
151 MachineFunctionProperties getRequiredProperties() const override {
152 return MachineFunctionProperties().setNoVRegs();
153 }
154
155 void getAnalysisUsage(AnalysisUsage &AU) const override {
156 AU.addRequired<ProfileSummaryInfoWrapperPass>();
157 AU.addRequired<LazyMachineBlockFrequencyInfoPass>();
158 MachineFunctionPass::getAnalysisUsage(AU);
159 }
160};
161}
162
163char FixupLEAsLegacy::ID = 0;
164
165INITIALIZE_PASS(FixupLEAsLegacy, FIXUPLEA_NAME, FIXUPLEA_DESC, false, false)
166
167MachineInstr *
168FixupLEAsImpl::postRAConvertToLEA(MachineBasicBlock &MBB,
169 MachineBasicBlock::iterator &MBBI) const {
170 MachineInstr &MI = *MBBI;
171 switch (MI.getOpcode()) {
172 case X86::MOV32rr:
173 case X86::MOV64rr: {
174 const MachineOperand &Src = MI.getOperand(i: 1);
175 const MachineOperand &Dest = MI.getOperand(i: 0);
176 MachineInstr *NewMI =
177 BuildMI(BB&: MBB, I: MBBI, MIMD: MI.getDebugLoc(),
178 MCID: TII->get(Opcode: MI.getOpcode() == X86::MOV32rr ? X86::LEA32r
179 : X86::LEA64r))
180 .add(MO: Dest)
181 .add(MO: Src)
182 .addImm(Val: 1)
183 .addReg(RegNo: 0)
184 .addImm(Val: 0)
185 .addReg(RegNo: 0);
186 return NewMI;
187 }
188 }
189
190 if (!MI.isConvertibleTo3Addr())
191 return nullptr;
192
193 switch (MI.getOpcode()) {
194 default:
195 // Only convert instructions that we've verified are safe.
196 return nullptr;
197 case X86::ADD64ri32:
198 case X86::ADD64ri32_DB:
199 case X86::ADD32ri:
200 case X86::ADD32ri_DB:
201 if (!MI.getOperand(i: 2).isImm()) {
202 // convertToThreeAddress will call getImm()
203 // which requires isImm() to be true
204 return nullptr;
205 }
206 break;
207 case X86::SHL64ri:
208 case X86::SHL32ri:
209 case X86::INC64r:
210 case X86::INC32r:
211 case X86::DEC64r:
212 case X86::DEC32r:
213 case X86::ADD64rr:
214 case X86::ADD64rr_DB:
215 case X86::ADD32rr:
216 case X86::ADD32rr_DB:
217 // These instructions are all fine to convert.
218 break;
219 }
220 return TII->convertToThreeAddress(MI, LV: nullptr, LIS: nullptr);
221}
222
223FunctionPass *llvm::createX86FixupLEAsLegacyPass() {
224 return new FixupLEAsLegacy();
225}
226
227static bool isLEA(unsigned Opcode) {
228 return Opcode == X86::LEA32r || Opcode == X86::LEA64r ||
229 Opcode == X86::LEA64_32r;
230}
231
232bool FixupLEAsImpl::runOnMachineFunction(MachineFunction &MF) {
233 const X86Subtarget &ST = MF.getSubtarget<X86Subtarget>();
234 bool IsSlowLEA = ST.slowLEA();
235 bool IsSlow3OpsLEA = ST.slow3OpsLEA();
236 bool LEAUsesAG = ST.leaUsesAG();
237
238 bool OptIncDec = !ST.slowIncDec() || MF.getFunction().hasOptSize();
239 bool UseLEAForSP = ST.useLeaForSP();
240
241 TSM.init(TSInfo: &ST);
242 TII = ST.getInstrInfo();
243 TRI = ST.getRegisterInfo();
244
245 LLVM_DEBUG(dbgs() << "Start X86FixupLEAs\n";);
246 for (MachineBasicBlock &MBB : MF) {
247 // First pass. Try to remove or optimize existing LEAs.
248 bool OptIncDecPerBB =
249 OptIncDec || llvm::shouldOptimizeForSize(MBB: &MBB, PSI, MBFI);
250 for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) {
251 if (!isLEA(Opcode: I->getOpcode()))
252 continue;
253
254 if (optTwoAddrLEA(I, MBB, OptIncDec: OptIncDecPerBB, UseLEAForSP))
255 continue;
256
257 if (IsSlowLEA)
258 processInstructionForSlowLEA(I, MBB);
259 else if (IsSlow3OpsLEA)
260 processInstrForSlow3OpLEA(I, MBB, OptIncDec: OptIncDecPerBB);
261 }
262
263 // Second pass for creating LEAs. This may reverse some of the
264 // transformations above.
265 if (LEAUsesAG) {
266 for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I)
267 processInstruction(I, MBB);
268 }
269 }
270
271 LLVM_DEBUG(dbgs() << "End X86FixupLEAs\n";);
272
273 return true;
274}
275
276FixupLEAsImpl::RegUsageState
277FixupLEAsImpl::usesRegister(MachineOperand &p, MachineBasicBlock::iterator I) {
278 RegUsageState RegUsage = RU_NotUsed;
279 MachineInstr &MI = *I;
280
281 for (const MachineOperand &MO : MI.operands()) {
282 if (MO.isReg() && MO.getReg() == p.getReg()) {
283 if (MO.isDef())
284 return RU_Write;
285 RegUsage = RU_Read;
286 }
287 }
288 return RegUsage;
289}
290
291/// getPreviousInstr - Given a reference to an instruction in a basic
292/// block, return a reference to the previous instruction in the block,
293/// wrapping around to the last instruction of the block if the block
294/// branches to itself.
295static inline bool getPreviousInstr(MachineBasicBlock::iterator &I,
296 MachineBasicBlock &MBB) {
297 if (I == MBB.begin()) {
298 if (MBB.isPredecessor(MBB: &MBB)) {
299 I = --MBB.end();
300 return true;
301 } else
302 return false;
303 }
304 --I;
305 return true;
306}
307
308MachineBasicBlock::iterator FixupLEAsImpl::searchBackwards(
309 MachineOperand &p, MachineBasicBlock::iterator &I, MachineBasicBlock &MBB) {
310 int InstrDistance = 1;
311 MachineBasicBlock::iterator CurInst;
312 static const int INSTR_DISTANCE_THRESHOLD = 5;
313
314 CurInst = I;
315 bool Found;
316 Found = getPreviousInstr(I&: CurInst, MBB);
317 while (Found && I != CurInst) {
318 if (CurInst->isCall() || CurInst->isInlineAsm())
319 break;
320 if (InstrDistance > INSTR_DISTANCE_THRESHOLD)
321 break; // too far back to make a difference
322 if (usesRegister(p, I: CurInst) == RU_Write) {
323 return CurInst;
324 }
325 InstrDistance += TSM.computeInstrLatency(MI: &*CurInst);
326 Found = getPreviousInstr(I&: CurInst, MBB);
327 }
328 return MachineBasicBlock::iterator();
329}
330
331static inline bool isInefficientLEAReg(Register Reg) {
332 return Reg == X86::EBP || Reg == X86::RBP ||
333 Reg == X86::R13D || Reg == X86::R13;
334}
335
336/// Returns true if this LEA uses base and index registers, and the base
337/// register is known to be inefficient for the subtarget.
338// TODO: use a variant scheduling class to model the latency profile
339// of LEA instructions, and implement this logic as a scheduling predicate.
340static inline bool hasInefficientLEABaseReg(const MachineOperand &Base,
341 const MachineOperand &Index) {
342 return Base.isReg() && isInefficientLEAReg(Reg: Base.getReg()) && Index.isReg() &&
343 Index.getReg().isValid();
344}
345
346// Returns true if this operand may have a non-zero offset.
347static inline bool mayHaveOffset(const MachineOperand &Offset) {
348 return !(Offset.isImm() && Offset.getImm() == 0);
349}
350
351static inline unsigned getADDrrFromLEA(unsigned LEAOpcode) {
352 switch (LEAOpcode) {
353 default:
354 llvm_unreachable("Unexpected LEA instruction");
355 case X86::LEA32r:
356 case X86::LEA64_32r:
357 return X86::ADD32rr;
358 case X86::LEA64r:
359 return X86::ADD64rr;
360 }
361}
362
363static inline unsigned getSUBrrFromLEA(unsigned LEAOpcode) {
364 switch (LEAOpcode) {
365 default:
366 llvm_unreachable("Unexpected LEA instruction");
367 case X86::LEA32r:
368 case X86::LEA64_32r:
369 return X86::SUB32rr;
370 case X86::LEA64r:
371 return X86::SUB64rr;
372 }
373}
374
375static inline unsigned getADDriFromLEA(unsigned LEAOpcode,
376 const MachineOperand &Offset) {
377 switch (LEAOpcode) {
378 default:
379 llvm_unreachable("Unexpected LEA instruction");
380 case X86::LEA32r:
381 case X86::LEA64_32r:
382 return X86::ADD32ri;
383 case X86::LEA64r:
384 return X86::ADD64ri32;
385 }
386}
387
388static inline unsigned getSUBriFromLEA(unsigned LEAOpcode) {
389 switch (LEAOpcode) {
390 default:
391 llvm_unreachable("Unexpected LEA instruction");
392 case X86::LEA32r:
393 case X86::LEA64_32r:
394 return X86::SUB32ri;
395 case X86::LEA64r:
396 return X86::SUB64ri32;
397 }
398}
399
400static inline unsigned getINCDECFromLEA(unsigned LEAOpcode, bool IsINC) {
401 switch (LEAOpcode) {
402 default:
403 llvm_unreachable("Unexpected LEA instruction");
404 case X86::LEA32r:
405 case X86::LEA64_32r:
406 return IsINC ? X86::INC32r : X86::DEC32r;
407 case X86::LEA64r:
408 return IsINC ? X86::INC64r : X86::DEC64r;
409 }
410}
411
412MachineBasicBlock::iterator
413FixupLEAsImpl::searchALUInst(MachineBasicBlock::iterator &I,
414 MachineBasicBlock &MBB) const {
415 const int InstrDistanceThreshold = 5;
416 int InstrDistance = 1;
417 MachineBasicBlock::iterator CurInst = std::next(x: I);
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 while (CurInst != MBB.end()) {
425 if (CurInst->isCall() || CurInst->isInlineAsm())
426 break;
427 if (InstrDistance > InstrDistanceThreshold)
428 break;
429
430 // Check if the lea dest register is used in an add/sub instruction only.
431 for (unsigned I = 0, E = CurInst->getNumOperands(); I != E; ++I) {
432 MachineOperand &Opnd = CurInst->getOperand(i: I);
433 if (Opnd.isReg()) {
434 if (Opnd.getReg() == DestReg) {
435 if (Opnd.isDef() || !Opnd.isKill())
436 return MachineBasicBlock::iterator();
437
438 unsigned AluOpcode = CurInst->getOpcode();
439 if (AluOpcode != AddOpcode && AluOpcode != SubOpcode)
440 return MachineBasicBlock::iterator();
441
442 MachineOperand &Opnd2 = CurInst->getOperand(i: 3 - I);
443 MachineOperand AluDest = CurInst->getOperand(i: 0);
444 if (Opnd2.getReg() != AluDest.getReg())
445 return MachineBasicBlock::iterator();
446
447 // X - (Y + Z) may generate different flags than (X - Y) - Z when
448 // there is overflow. So we can't change the alu instruction if the
449 // flags register is live.
450 if (!CurInst->registerDefIsDead(Reg: X86::EFLAGS, TRI))
451 return MachineBasicBlock::iterator();
452
453 return CurInst;
454 }
455 if (TRI->regsOverlap(RegA: DestReg, RegB: Opnd.getReg()))
456 return MachineBasicBlock::iterator();
457 }
458 }
459
460 InstrDistance++;
461 ++CurInst;
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