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