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