1//===- X86OptimizeLEAs.cpp - optimize usage of 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 performs some optimizations with LEA
10// instructions in order to improve performance and code size.
11// Currently, it does two things:
12// 1) If there are two LEA instructions calculating addresses which only differ
13// by displacement inside a basic block, one of them is removed.
14// 2) Address calculations in load and store instructions are replaced by
15// existing LEA def registers where possible.
16//
17//===----------------------------------------------------------------------===//
18
19#include "MCTargetDesc/X86BaseInfo.h"
20#include "X86.h"
21#include "X86InstrInfo.h"
22#include "X86Subtarget.h"
23#include "llvm/ADT/DenseMap.h"
24#include "llvm/ADT/DenseMapInfo.h"
25#include "llvm/ADT/Hashing.h"
26#include "llvm/ADT/SmallVector.h"
27#include "llvm/ADT/Statistic.h"
28#include "llvm/Analysis/ProfileSummaryInfo.h"
29#include "llvm/CodeGen/LazyMachineBlockFrequencyInfo.h"
30#include "llvm/CodeGen/MachineBasicBlock.h"
31#include "llvm/CodeGen/MachineFunction.h"
32#include "llvm/CodeGen/MachineFunctionPass.h"
33#include "llvm/CodeGen/MachineInstr.h"
34#include "llvm/CodeGen/MachineInstrBuilder.h"
35#include "llvm/CodeGen/MachineOperand.h"
36#include "llvm/CodeGen/MachineRegisterInfo.h"
37#include "llvm/CodeGen/MachineSizeOpts.h"
38#include "llvm/CodeGen/RegisterClassInfo.h"
39#include "llvm/CodeGen/TargetOpcodes.h"
40#include "llvm/CodeGen/TargetRegisterInfo.h"
41#include "llvm/IR/DebugInfoMetadata.h"
42#include "llvm/IR/DebugLoc.h"
43#include "llvm/IR/Function.h"
44#include "llvm/MC/MCInstrDesc.h"
45#include "llvm/Support/Debug.h"
46#include "llvm/Support/ErrorHandling.h"
47#include "llvm/Support/MathExtras.h"
48#include "llvm/Support/raw_ostream.h"
49#include <cassert>
50#include <cstdint>
51#include <iterator>
52
53using namespace llvm;
54
55#define DEBUG_TYPE "x86-optimize-leas"
56
57STATISTIC(NumSubstLEAs, "Number of LEA instruction substitutions");
58STATISTIC(NumRedundantLEAs, "Number of redundant LEA instructions removed");
59
60/// Returns true if two machine operands are identical and they are not
61/// physical registers.
62static inline bool isIdenticalOp(const MachineOperand &MO1,
63 const MachineOperand &MO2);
64
65/// Returns true if two address displacement operands are of the same
66/// type and use the same symbol/index/address regardless of the offset.
67static bool isSimilarDispOp(const MachineOperand &MO1,
68 const MachineOperand &MO2);
69
70/// Returns true if the instruction is LEA.
71static inline bool isLEA(const MachineInstr &MI);
72
73namespace {
74
75/// A key based on instruction's memory operands.
76class MemOpKey {
77public:
78 MemOpKey(const MachineOperand *Base, const MachineOperand *Scale,
79 const MachineOperand *Index, const MachineOperand *Segment,
80 const MachineOperand *Disp)
81 : Disp(Disp) {
82 Operands[0] = Base;
83 Operands[1] = Scale;
84 Operands[2] = Index;
85 Operands[3] = Segment;
86 }
87
88 bool operator==(const MemOpKey &Other) const {
89 // Addresses' bases, scales, indices and segments must be identical.
90 for (int i = 0; i < 4; ++i)
91 if (!isIdenticalOp(MO1: *Operands[i], MO2: *Other.Operands[i]))
92 return false;
93
94 // Addresses' displacements don't have to be exactly the same. It only
95 // matters that they use the same symbol/index/address. Immediates' or
96 // offsets' differences will be taken care of during instruction
97 // substitution.
98 return isSimilarDispOp(MO1: *Disp, MO2: *Other.Disp);
99 }
100
101 // Address' base, scale, index and segment operands.
102 const MachineOperand *Operands[4];
103
104 // Address' displacement operand.
105 const MachineOperand *Disp;
106};
107
108} // end anonymous namespace
109
110namespace llvm {
111
112/// Provide DenseMapInfo for MemOpKey.
113template <> struct DenseMapInfo<MemOpKey> {
114 using PtrInfo = DenseMapInfo<const MachineOperand *>;
115
116 static unsigned getHashValue(const MemOpKey &Val) {
117 hash_code Hash = hash_combine(args: *Val.Operands[0], args: *Val.Operands[1],
118 args: *Val.Operands[2], args: *Val.Operands[3]);
119
120 // If the address displacement is an immediate, it should not affect the
121 // hash so that memory operands which differ only be immediate displacement
122 // would have the same hash. If the address displacement is something else,
123 // we should reflect symbol/index/address in the hash.
124 switch (Val.Disp->getType()) {
125 case MachineOperand::MO_Immediate:
126 break;
127 case MachineOperand::MO_ConstantPoolIndex:
128 case MachineOperand::MO_JumpTableIndex:
129 Hash = hash_combine(args: Hash, args: Val.Disp->getIndex());
130 break;
131 case MachineOperand::MO_ExternalSymbol:
132 Hash = hash_combine(args: Hash, args: Val.Disp->getSymbolName());
133 break;
134 case MachineOperand::MO_GlobalAddress:
135 Hash = hash_combine(args: Hash, args: Val.Disp->getGlobal());
136 break;
137 case MachineOperand::MO_BlockAddress:
138 Hash = hash_combine(args: Hash, args: Val.Disp->getBlockAddress());
139 break;
140 case MachineOperand::MO_MCSymbol:
141 Hash = hash_combine(args: Hash, args: Val.Disp->getMCSymbol());
142 break;
143 case MachineOperand::MO_MachineBasicBlock:
144 Hash = hash_combine(args: Hash, args: Val.Disp->getMBB());
145 break;
146 default:
147 llvm_unreachable("Invalid address displacement operand");
148 }
149
150 return (unsigned)Hash;
151 }
152
153 static bool isEqual(const MemOpKey &LHS, const MemOpKey &RHS) {
154 return LHS == RHS;
155 }
156};
157
158} // end namespace llvm
159
160/// Returns a hash table key based on memory operands of \p MI. The
161/// number of the first memory operand of \p MI is specified through \p N.
162static inline MemOpKey getMemOpKey(const MachineInstr &MI, unsigned N) {
163 assert((isLEA(MI) || MI.mayLoadOrStore()) &&
164 "The instruction must be a LEA, a load or a store");
165 return MemOpKey(&MI.getOperand(i: N + X86::AddrBaseReg),
166 &MI.getOperand(i: N + X86::AddrScaleAmt),
167 &MI.getOperand(i: N + X86::AddrIndexReg),
168 &MI.getOperand(i: N + X86::AddrSegmentReg),
169 &MI.getOperand(i: N + X86::AddrDisp));
170}
171
172static inline bool isIdenticalOp(const MachineOperand &MO1,
173 const MachineOperand &MO2) {
174 return MO1.isIdenticalTo(Other: MO2) && (!MO1.isReg() || !MO1.getReg().isPhysical());
175}
176
177#ifndef NDEBUG
178static bool isValidDispOp(const MachineOperand &MO) {
179 return MO.isImm() || MO.isCPI() || MO.isJTI() || MO.isSymbol() ||
180 MO.isGlobal() || MO.isBlockAddress() || MO.isMCSymbol() || MO.isMBB();
181}
182#endif
183
184static bool isSimilarDispOp(const MachineOperand &MO1,
185 const MachineOperand &MO2) {
186 assert(isValidDispOp(MO1) && isValidDispOp(MO2) &&
187 "Address displacement operand is not valid");
188 return (MO1.isImm() && MO2.isImm()) ||
189 (MO1.isCPI() && MO2.isCPI() && MO1.getIndex() == MO2.getIndex()) ||
190 (MO1.isJTI() && MO2.isJTI() && MO1.getIndex() == MO2.getIndex()) ||
191 (MO1.isSymbol() && MO2.isSymbol() &&
192 MO1.getSymbolName() == MO2.getSymbolName()) ||
193 (MO1.isGlobal() && MO2.isGlobal() &&
194 MO1.getGlobal() == MO2.getGlobal()) ||
195 (MO1.isBlockAddress() && MO2.isBlockAddress() &&
196 MO1.getBlockAddress() == MO2.getBlockAddress()) ||
197 (MO1.isMCSymbol() && MO2.isMCSymbol() &&
198 MO1.getMCSymbol() == MO2.getMCSymbol()) ||
199 (MO1.isMBB() && MO2.isMBB() && MO1.getMBB() == MO2.getMBB());
200}
201
202static inline bool isLEA(const MachineInstr &MI) {
203 unsigned Opcode = MI.getOpcode();
204 return Opcode == X86::LEA16r || Opcode == X86::LEA32r ||
205 Opcode == X86::LEA64r || Opcode == X86::LEA64_32r;
206}
207
208namespace {
209
210class X86OptimizeLEAsImpl {
211public:
212 bool runOnMachineFunction(MachineFunction &MF, ProfileSummaryInfo *PSI,
213 MachineBlockFrequencyInfo *MBFI);
214
215private:
216 using MemOpMap = DenseMap<MemOpKey, SmallVector<MachineInstr *, 16>>;
217
218 /// Returns a distance between two instructions inside one basic block.
219 /// Negative result means, that instructions occur in reverse order.
220 int calcInstrDist(const MachineInstr &First, const MachineInstr &Last);
221
222 /// Choose the best \p LEA instruction from the \p List to replace
223 /// address calculation in \p MI instruction. Return the address displacement
224 /// and the distance between \p MI and the chosen \p BestLEA in
225 /// \p AddrDispShift and \p Dist.
226 bool chooseBestLEA(const SmallVectorImpl<MachineInstr *> &List,
227 const MachineInstr &MI, MachineInstr *&BestLEA,
228 int64_t &AddrDispShift, int &Dist);
229
230 /// Returns the difference between addresses' displacements of \p MI1
231 /// and \p MI2. The numbers of the first memory operands for the instructions
232 /// are specified through \p N1 and \p N2.
233 int64_t getAddrDispShift(const MachineInstr &MI1, unsigned N1,
234 const MachineInstr &MI2, unsigned N2) const;
235
236 /// Returns true if the \p Last LEA instruction can be replaced by the
237 /// \p First. The difference between displacements of the addresses calculated
238 /// by these LEAs is returned in \p AddrDispShift. It'll be used for proper
239 /// replacement of the \p Last LEA's uses with the \p First's def register.
240 bool isReplaceable(const MachineInstr &First, const MachineInstr &Last,
241 int64_t &AddrDispShift) const;
242
243 /// Find all LEA instructions in the basic block. Also, assign position
244 /// numbers to all instructions in the basic block to speed up calculation of
245 /// distance between them.
246 void findLEAs(const MachineBasicBlock &MBB, MemOpMap &LEAs);
247
248 /// Removes redundant address calculations.
249 bool removeRedundantAddrCalc(MemOpMap &LEAs);
250
251 /// Replace debug value MI with a new debug value instruction using register
252 /// VReg with an appropriate offset and DIExpression to incorporate the
253 /// address displacement AddrDispShift. Return new debug value instruction.
254 MachineInstr *replaceDebugValue(MachineInstr &MI, Register OldReg,
255 Register NewReg, int64_t AddrDispShift);
256
257 /// Removes LEAs which calculate similar addresses.
258 bool removeRedundantLEAs(MemOpMap &LEAs);
259
260 DenseMap<const MachineInstr *, unsigned> InstrPos;
261
262 MachineRegisterInfo *MRI = nullptr;
263 const X86InstrInfo *TII = nullptr;
264 const X86RegisterInfo *TRI = nullptr;
265};
266
267class X86OptimizeLEAsLegacy : public MachineFunctionPass {
268public:
269 X86OptimizeLEAsLegacy() : MachineFunctionPass(ID) {}
270
271 StringRef getPassName() const override { return "X86 LEA Optimize"; }
272
273 /// Loop over all of the basic blocks, replacing address
274 /// calculations in load and store instructions, if it's already
275 /// been calculated by LEA. Also, remove redundant LEAs.
276 bool runOnMachineFunction(MachineFunction &MF) override;
277
278 static char ID;
279
280 void getAnalysisUsage(AnalysisUsage &AU) const override {
281 AU.addRequired<ProfileSummaryInfoWrapperPass>();
282 AU.addRequired<LazyMachineBlockFrequencyInfoPass>();
283 AU.addPreserved<MachineRegisterClassInfoWrapperPass>();
284 MachineFunctionPass::getAnalysisUsage(AU);
285 }
286};
287
288} // end anonymous namespace
289
290char X86OptimizeLEAsLegacy::ID = 0;
291
292FunctionPass *llvm::createX86OptimizeLEAsLegacyPass() {
293 return new X86OptimizeLEAsLegacy();
294}
295INITIALIZE_PASS(X86OptimizeLEAsLegacy, DEBUG_TYPE, "X86 optimize LEA pass",
296 false, false)
297
298int X86OptimizeLEAsImpl::calcInstrDist(const MachineInstr &First,
299 const MachineInstr &Last) {
300 // Both instructions must be in the same basic block and they must be
301 // presented in InstrPos.
302 assert(Last.getParent() == First.getParent() &&
303 "Instructions are in different basic blocks");
304 assert(InstrPos.contains(&First) && InstrPos.contains(&Last) &&
305 "Instructions' positions are undefined");
306
307 return InstrPos[&Last] - InstrPos[&First];
308}
309
310// Find the best LEA instruction in the List to replace address recalculation in
311// MI. Such LEA must meet these requirements:
312// 1) The address calculated by the LEA differs only by the displacement from
313// the address used in MI.
314// 2) The register class of the definition of the LEA is compatible with the
315// register class of the address base register of MI.
316// 3) Displacement of the new memory operand should fit in 1 byte if possible.
317// 4) The LEA should be as close to MI as possible, and prior to it if
318// possible.
319bool X86OptimizeLEAsImpl::chooseBestLEA(
320 const SmallVectorImpl<MachineInstr *> &List, const MachineInstr &MI,
321 MachineInstr *&BestLEA, int64_t &AddrDispShift, int &Dist) {
322 const MCInstrDesc &Desc = MI.getDesc();
323 int MemOpNo = X86II::getMemoryOperandIdx(Desc);
324 assert(MemOpNo >= 0 && "Expected a memory operand");
325
326 BestLEA = nullptr;
327
328 // Loop over all LEA instructions.
329 for (auto *DefMI : List) {
330 // Get new address displacement.
331 int64_t AddrDispShiftTemp = getAddrDispShift(MI1: MI, N1: MemOpNo, MI2: *DefMI, N2: 1);
332
333 // Make sure address displacement fits 4 bytes.
334 if (!isInt<32>(x: AddrDispShiftTemp))
335 continue;
336
337 // Check that LEA def register can be used as MI address base. Some
338 // instructions can use a limited set of registers as address base, for
339 // example MOV8mr_NOREX. We could constrain the register class of the LEA
340 // def to suit MI, however since this case is very rare and hard to
341 // reproduce in a test it's just more reliable to skip the LEA.
342 if (TII->getRegClass(MCID: Desc, OpNum: MemOpNo + X86::AddrBaseReg) !=
343 MRI->getRegClass(Reg: DefMI->getOperand(i: 0).getReg()))
344 continue;
345
346 // Choose the closest LEA instruction from the list, prior to MI if
347 // possible. Note that we took into account resulting address displacement
348 // as well. Also note that the list is sorted by the order in which the LEAs
349 // occur, so the break condition is pretty simple.
350 int DistTemp = calcInstrDist(First: *DefMI, Last: MI);
351 assert(DistTemp != 0 &&
352 "The distance between two different instructions cannot be zero");
353 if (DistTemp > 0 || BestLEA == nullptr) {
354 // Do not update return LEA, if the current one provides a displacement
355 // which fits in 1 byte, while the new candidate does not.
356 if (BestLEA != nullptr && !isInt<8>(x: AddrDispShiftTemp) &&
357 isInt<8>(x: AddrDispShift))
358 continue;
359
360 BestLEA = DefMI;
361 AddrDispShift = AddrDispShiftTemp;
362 Dist = DistTemp;
363 }
364
365 // FIXME: Maybe we should not always stop at the first LEA after MI.
366 if (DistTemp < 0)
367 break;
368 }
369
370 return BestLEA != nullptr;
371}
372
373// Get the difference between the addresses' displacements of the two
374// instructions \p MI1 and \p MI2. The numbers of the first memory operands are
375// passed through \p N1 and \p N2.
376int64_t X86OptimizeLEAsImpl::getAddrDispShift(const MachineInstr &MI1,
377 unsigned N1,
378 const MachineInstr &MI2,
379 unsigned N2) const {
380 const MachineOperand &Op1 = MI1.getOperand(i: N1 + X86::AddrDisp);
381 const MachineOperand &Op2 = MI2.getOperand(i: N2 + X86::AddrDisp);
382
383 assert(isSimilarDispOp(Op1, Op2) &&
384 "Address displacement operands are not compatible");
385
386 // After the assert above we can be sure that both operands are of the same
387 // valid type and use the same symbol/index/address, thus displacement shift
388 // calculation is rather simple.
389 if (Op1.isJTI())
390 return 0;
391 return Op1.isImm() ? Op1.getImm() - Op2.getImm()
392 : Op1.getOffset() - Op2.getOffset();
393}
394
395// Check that the Last LEA can be replaced by the First LEA. To be so,
396// these requirements must be met:
397// 1) Addresses calculated by LEAs differ only by displacement.
398// 2) Def registers of LEAs belong to the same class.
399// 3) All uses of the Last LEA def register are replaceable, thus the
400// register is used only as address base.
401bool X86OptimizeLEAsImpl::isReplaceable(const MachineInstr &First,
402 const MachineInstr &Last,
403 int64_t &AddrDispShift) const {
404 assert(isLEA(First) && isLEA(Last) &&
405 "The function works only with LEA instructions");
406
407 // Make sure that LEA def registers belong to the same class. There may be
408 // instructions (like MOV8mr_NOREX) which allow a limited set of registers to
409 // be used as their operands, so we must be sure that replacing one LEA
410 // with another won't lead to putting a wrong register in the instruction.
411 if (MRI->getRegClass(Reg: First.getOperand(i: 0).getReg()) !=
412 MRI->getRegClass(Reg: Last.getOperand(i: 0).getReg()))
413 return false;
414
415 // Get new address displacement.
416 AddrDispShift = getAddrDispShift(MI1: Last, N1: 1, MI2: First, N2: 1);
417
418 // Loop over all uses of the Last LEA to check that its def register is
419 // used only as address base for memory accesses. If so, it can be
420 // replaced, otherwise - no.
421 for (auto &MO : MRI->use_nodbg_operands(Reg: Last.getOperand(i: 0).getReg())) {
422 MachineInstr &MI = *MO.getParent();
423
424 // Get the number of the first memory operand.
425 int MemOpNo = X86II::getMemoryOperandIdx(Desc: MI.getDesc());
426
427 // If the use instruction has no memory operand - the LEA is not
428 // replaceable.
429 if (MemOpNo < 0)
430 return false;
431
432 // If the address base of the use instruction is not the LEA def register -
433 // the LEA is not replaceable.
434 if (!isIdenticalOp(MO1: MI.getOperand(i: MemOpNo + X86::AddrBaseReg), MO2: MO))
435 return false;
436
437 // If the LEA def register is used as any other operand of the use
438 // instruction - the LEA is not replaceable.
439 for (unsigned i = 0; i < MI.getNumOperands(); i++)
440 if (i != (unsigned)(MemOpNo + X86::AddrBaseReg) &&
441 isIdenticalOp(MO1: MI.getOperand(i), MO2: MO))
442 return false;
443
444 // Check that the new address displacement will fit 4 bytes.
445 if (MI.getOperand(i: MemOpNo + X86::AddrDisp).isImm() &&
446 !isInt<32>(x: MI.getOperand(i: MemOpNo + X86::AddrDisp).getImm() +
447 AddrDispShift))
448 return false;
449 }
450
451 return true;
452}
453
454void X86OptimizeLEAsImpl::findLEAs(const MachineBasicBlock &MBB,
455 MemOpMap &LEAs) {
456 unsigned Pos = 0;
457 for (auto &MI : MBB) {
458 // Assign the position number to the instruction. Note that we are going to
459 // move some instructions during the optimization however there will never
460 // be a need to move two instructions before any selected instruction. So to
461 // avoid multiple positions' updates during moves we just increase position
462 // counter by two leaving a free space for instructions which will be moved.
463 InstrPos[&MI] = Pos += 2;
464
465 if (isLEA(MI))
466 LEAs[getMemOpKey(MI, N: 1)].push_back(Elt: const_cast<MachineInstr *>(&MI));
467 }
468}
469
470// Try to find load and store instructions which recalculate addresses already
471// calculated by some LEA and replace their memory operands with its def
472// register.
473bool X86OptimizeLEAsImpl::removeRedundantAddrCalc(MemOpMap &LEAs) {
474 bool Changed = false;
475
476 assert(!LEAs.empty());
477 MachineBasicBlock *MBB = (*LEAs.begin()->second.begin())->getParent();
478
479 // Process all instructions in basic block.
480 for (MachineInstr &MI : llvm::make_early_inc_range(Range&: *MBB)) {
481 // Instruction must be load or store.
482 if (!MI.mayLoadOrStore())
483 continue;
484
485 // Get the number of the first memory operand.
486 int MemOpNo = X86II::getMemoryOperandIdx(Desc: MI.getDesc());
487
488 // If instruction has no memory operand - skip it.
489 if (MemOpNo < 0)
490 continue;
491
492 // Do not call chooseBestLEA if there was no matching LEA
493 auto Insns = LEAs.find(Val: getMemOpKey(MI, N: MemOpNo));
494 if (Insns == LEAs.end())
495 continue;
496
497 // Get the best LEA instruction to replace address calculation.
498 MachineInstr *DefMI;
499 int64_t AddrDispShift;
500 int Dist;
501 if (!chooseBestLEA(List: Insns->second, MI, BestLEA&: DefMI, AddrDispShift, Dist))
502 continue;
503
504 // If LEA occurs before current instruction, we can freely replace
505 // the instruction. If LEA occurs after, we can lift LEA above the
506 // instruction and this way to be able to replace it. Since LEA and the
507 // instruction have similar memory operands (thus, the same def
508 // instructions for these operands), we can always do that, without
509 // worries of using registers before their defs.
510 if (Dist < 0) {
511 DefMI->removeFromParent();
512 MBB->insert(I: MachineBasicBlock::iterator(&MI), MI: DefMI);
513 InstrPos[DefMI] = InstrPos[&MI] - 1;
514
515 // Make sure the instructions' position numbers are sane.
516 assert(((InstrPos[DefMI] == 1 &&
517 MachineBasicBlock::iterator(DefMI) == MBB->begin()) ||
518 InstrPos[DefMI] >
519 InstrPos[&*std::prev(MachineBasicBlock::iterator(DefMI))]) &&
520 "Instruction positioning is broken");
521 }
522
523 // Since we can possibly extend register lifetime, clear kill flags.
524 MRI->clearKillFlags(Reg: DefMI->getOperand(i: 0).getReg());
525
526 ++NumSubstLEAs;
527 LLVM_DEBUG(dbgs() << "OptimizeLEAs: Candidate to replace: "; MI.dump(););
528
529 // Change instruction operands.
530 MI.getOperand(i: MemOpNo + X86::AddrBaseReg)
531 .ChangeToRegister(Reg: DefMI->getOperand(i: 0).getReg(), isDef: false);
532 MI.getOperand(i: MemOpNo + X86::AddrScaleAmt).ChangeToImmediate(ImmVal: 1);
533 MI.getOperand(i: MemOpNo + X86::AddrIndexReg)
534 .ChangeToRegister(Reg: X86::NoRegister, isDef: false);
535 MI.getOperand(i: MemOpNo + X86::AddrDisp).ChangeToImmediate(ImmVal: AddrDispShift);
536 MI.getOperand(i: MemOpNo + X86::AddrSegmentReg)
537 .ChangeToRegister(Reg: X86::NoRegister, isDef: false);
538
539 LLVM_DEBUG(dbgs() << "OptimizeLEAs: Replaced by: "; MI.dump(););
540
541 Changed = true;
542 }
543
544 return Changed;
545}
546
547MachineInstr *X86OptimizeLEAsImpl::replaceDebugValue(MachineInstr &MI,
548 Register OldReg,
549 Register NewReg,
550 int64_t AddrDispShift) {
551 const DIExpression *Expr = MI.getDebugExpression();
552 if (AddrDispShift != 0) {
553 if (MI.isNonListDebugValue()) {
554 Expr =
555 DIExpression::prepend(Expr, Flags: DIExpression::StackValue, Offset: AddrDispShift);
556 } else {
557 // Update the Expression, appending an offset of `AddrDispShift` to the
558 // Op corresponding to `OldReg`.
559 SmallVector<uint64_t, 3> Ops;
560 DIExpression::appendOffset(Ops, Offset: AddrDispShift);
561 for (MachineOperand &Op : MI.getDebugOperandsForReg(Reg: OldReg)) {
562 unsigned OpIdx = MI.getDebugOperandIndex(Op: &Op);
563 Expr = DIExpression::appendOpsToArg(Expr, Ops, ArgNo: OpIdx);
564 }
565 }
566 }
567
568 // Replace DBG_VALUE instruction with modified version.
569 MachineBasicBlock *MBB = MI.getParent();
570 DebugLoc DL = MI.getDebugLoc();
571 bool IsIndirect = MI.isIndirectDebugValue();
572 const MDNode *Var = MI.getDebugVariable();
573 unsigned Opcode = MI.isNonListDebugValue() ? TargetOpcode::DBG_VALUE
574 : TargetOpcode::DBG_VALUE_LIST;
575 if (IsIndirect)
576 assert(MI.getDebugOffset().getImm() == 0 &&
577 "DBG_VALUE with nonzero offset");
578 SmallVector<MachineOperand, 4> NewOps;
579 // If we encounter an operand using the old register, replace it with an
580 // operand that uses the new register; otherwise keep the old operand.
581 auto replaceOldReg = [OldReg, NewReg](const MachineOperand &Op) {
582 if (Op.isReg() && Op.getReg() == OldReg)
583 return MachineOperand::CreateReg(Reg: NewReg, isDef: false, isImp: false, isKill: false, isDead: false,
584 isUndef: false, isEarlyClobber: false, SubReg: false, isDebug: false, isInternalRead: false,
585 /*IsRenamable*/ isRenamable: true);
586 return Op;
587 };
588 for (const MachineOperand &Op : MI.debug_operands())
589 NewOps.push_back(Elt: replaceOldReg(Op));
590 return BuildMI(BB&: *MBB, I: MBB->erase(I: &MI), DL, MCID: TII->get(Opcode), IsIndirect,
591 MOs: NewOps, Variable: Var, Expr);
592}
593
594// Try to find similar LEAs in the list and replace one with another.
595bool X86OptimizeLEAsImpl::removeRedundantLEAs(MemOpMap &LEAs) {
596 bool Changed = false;
597
598 // Loop over all entries in the table.
599 for (auto &E : LEAs) {
600 auto &List = E.second;
601
602 // Loop over all LEA pairs.
603 auto I1 = List.begin();
604 while (I1 != List.end()) {
605 MachineInstr &First = **I1;
606 auto I2 = std::next(x: I1);
607 while (I2 != List.end()) {
608 MachineInstr &Last = **I2;
609 int64_t AddrDispShift;
610
611 // LEAs should be in occurrence order in the list, so we can freely
612 // replace later LEAs with earlier ones.
613 assert(calcInstrDist(First, Last) > 0 &&
614 "LEAs must be in occurrence order in the list");
615
616 // Check that the Last LEA instruction can be replaced by the First.
617 if (!isReplaceable(First, Last, AddrDispShift)) {
618 ++I2;
619 continue;
620 }
621
622 // Loop over all uses of the Last LEA and update their operands. Note
623 // that the correctness of this has already been checked in the
624 // isReplaceable function.
625 Register FirstVReg = First.getOperand(i: 0).getReg();
626 Register LastVReg = Last.getOperand(i: 0).getReg();
627 // We use MRI->use_empty here instead of the combination of
628 // llvm::make_early_inc_range and MRI->use_operands because we could
629 // replace two or more uses in a debug instruction in one iteration, and
630 // that would deeply confuse llvm::make_early_inc_range.
631 while (!MRI->use_empty(RegNo: LastVReg)) {
632 MachineOperand &MO = *MRI->use_begin(RegNo: LastVReg);
633 MachineInstr &MI = *MO.getParent();
634
635 if (MI.isDebugValue()) {
636 // Replace DBG_VALUE instruction with modified version using the
637 // register from the replacing LEA and the address displacement
638 // between the LEA instructions.
639 replaceDebugValue(MI, OldReg: LastVReg, NewReg: FirstVReg, AddrDispShift);
640 continue;
641 }
642
643 // Get the number of the first memory operand.
644 int MemOpNo = X86II::getMemoryOperandIdx(Desc: MI.getDesc());
645 assert(MemOpNo >= 0 && "Expected a memory operand");
646
647 // Update address base.
648 MO.setReg(FirstVReg);
649
650 // Update address disp.
651 MachineOperand &Op = MI.getOperand(i: MemOpNo + X86::AddrDisp);
652 if (Op.isImm())
653 Op.setImm(Op.getImm() + AddrDispShift);
654 else if (!Op.isJTI())
655 Op.setOffset(Op.getOffset() + AddrDispShift);
656 }
657
658 // Since we can possibly extend register lifetime, clear kill flags.
659 MRI->clearKillFlags(Reg: FirstVReg);
660
661 ++NumRedundantLEAs;
662 LLVM_DEBUG(dbgs() << "OptimizeLEAs: Remove redundant LEA: ";
663 Last.dump(););
664
665 // By this moment, all of the Last LEA's uses must be replaced. So we
666 // can freely remove it.
667 assert(MRI->use_empty(LastVReg) &&
668 "The LEA's def register must have no uses");
669 Last.eraseFromParent();
670
671 // Erase removed LEA from the list.
672 I2 = List.erase(CI: I2);
673
674 Changed = true;
675 }
676 ++I1;
677 }
678 }
679
680 return Changed;
681}
682
683bool X86OptimizeLEAsImpl::runOnMachineFunction(
684 MachineFunction &MF, ProfileSummaryInfo *PSI,
685 MachineBlockFrequencyInfo *MBFI) {
686 bool Changed = false;
687
688 const X86Subtarget &ST = MF.getSubtarget<X86Subtarget>();
689 if (ST.getCLOpts().disable_x86_lea_opt)
690 return false;
691
692 MRI = &MF.getRegInfo();
693 TII = ST.getInstrInfo();
694 TRI = ST.getRegisterInfo();
695
696 // Process all basic blocks.
697 for (auto &MBB : MF) {
698 MemOpMap LEAs;
699 InstrPos.clear();
700
701 // Find all LEA instructions in basic block.
702 findLEAs(MBB, LEAs);
703
704 // If current basic block has no LEAs, move on to the next one.
705 if (LEAs.empty())
706 continue;
707
708 // Remove redundant LEA instructions.
709 Changed |= removeRedundantLEAs(LEAs);
710
711 // Remove redundant address calculations. Do it only for -Os/-Oz since only
712 // a code size gain is expected from this part of the pass.
713 if (llvm::shouldOptimizeForSize(MBB: &MBB, PSI, MBFI))
714 Changed |= removeRedundantAddrCalc(LEAs);
715 }
716
717 return Changed;
718}
719
720bool X86OptimizeLEAsLegacy::runOnMachineFunction(MachineFunction &MF) {
721 if (skipFunction(F: MF.getFunction()))
722 return false;
723 ProfileSummaryInfo *PSI =
724 &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
725 MachineBlockFrequencyInfo *MBFI =
726 (PSI && PSI->hasProfileSummary())
727 ? &getAnalysis<LazyMachineBlockFrequencyInfoPass>().getBFI()
728 : nullptr;
729 X86OptimizeLEAsImpl PassImpl;
730 return PassImpl.runOnMachineFunction(MF, PSI, MBFI);
731}
732
733PreservedAnalyses
734X86OptimizeLEAsPass::run(MachineFunction &MF,
735 MachineFunctionAnalysisManager &MFAM) {
736 ProfileSummaryInfo *PSI =
737 MFAM.getResult<ModuleAnalysisManagerMachineFunctionProxy>(IR&: MF)
738 .getCachedResult<ProfileSummaryAnalysis>(
739 IR&: *MF.getFunction().getParent());
740 MachineBlockFrequencyInfo *MBFI =
741 (PSI && PSI->hasProfileSummary())
742 ? &MFAM.getResult<MachineBlockFrequencyAnalysis>(IR&: MF)
743 : nullptr;
744 X86OptimizeLEAsImpl PassImpl;
745 bool Changed = PassImpl.runOnMachineFunction(MF, PSI, MBFI);
746 if (!Changed)
747 return PreservedAnalyses::all();
748 return getMachineFunctionPassPreservedAnalyses().preserveSet<CFGAnalyses>();
749}
750