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() || !Register::isPhysicalRegister(MO1.getReg()));
202 }
203 
204 #ifndef NDEBUG
205 static bool isValidDispOp(const MachineOperand &MO) {
206  return MO.isImm() || MO.isCPI() || MO.isJTI() || MO.isSymbol() ||
207  MO.isGlobal() || MO.isBlockAddress() || MO.isMCSymbol() || MO.isMBB();
208 }
209 #endif
210 
211 static bool isSimilarDispOp(const MachineOperand &MO1,
212  const MachineOperand &MO2) {
213  assert(isValidDispOp(MO1) && isValidDispOp(MO2) &&
214  "Address displacement operand is not valid");
215  return (MO1.isImm() && MO2.isImm()) ||
216  (MO1.isCPI() && MO2.isCPI() && MO1.getIndex() == MO2.getIndex()) ||
217  (MO1.isJTI() && MO2.isJTI() && MO1.getIndex() == MO2.getIndex()) ||
218  (MO1.isSymbol() && MO2.isSymbol() &&
219  MO1.getSymbolName() == MO2.getSymbolName()) ||
220  (MO1.isGlobal() && MO2.isGlobal() &&
221  MO1.getGlobal() == MO2.getGlobal()) ||
222  (MO1.isBlockAddress() && MO2.isBlockAddress() &&
223  MO1.getBlockAddress() == MO2.getBlockAddress()) ||
224  (MO1.isMCSymbol() && MO2.isMCSymbol() &&
225  MO1.getMCSymbol() == MO2.getMCSymbol()) ||
226  (MO1.isMBB() && MO2.isMBB() && MO1.getMBB() == MO2.getMBB());
227 }
228 
229 static inline bool isLEA(const MachineInstr &MI) {
230  unsigned Opcode = MI.getOpcode();
231  return Opcode == X86::LEA16r || Opcode == X86::LEA32r ||
232  Opcode == X86::LEA64r || Opcode == X86::LEA64_32r;
233 }
234 
235 namespace {
236 
237 class OptimizeLEAPass : public MachineFunctionPass {
238 public:
239  OptimizeLEAPass() : MachineFunctionPass(ID) {}
240 
241  StringRef getPassName() const override { return "X86 LEA Optimize"; }
242 
243  /// Loop over all of the basic blocks, replacing address
244  /// calculations in load and store instructions, if it's already
245  /// been calculated by LEA. Also, remove redundant LEAs.
246  bool runOnMachineFunction(MachineFunction &MF) override;
247 
248 private:
250 
251  /// Returns a distance between two instructions inside one basic block.
252  /// Negative result means, that instructions occur in reverse order.
253  int calcInstrDist(const MachineInstr &First, const MachineInstr &Last);
254 
255  /// Choose the best \p LEA instruction from the \p List to replace
256  /// address calculation in \p MI instruction. Return the address displacement
257  /// and the distance between \p MI and the chosen \p BestLEA in
258  /// \p AddrDispShift and \p Dist.
259  bool chooseBestLEA(const SmallVectorImpl<MachineInstr *> &List,
260  const MachineInstr &MI, MachineInstr *&BestLEA,
261  int64_t &AddrDispShift, int &Dist);
262 
263  /// Returns the difference between addresses' displacements of \p MI1
264  /// and \p MI2. The numbers of the first memory operands for the instructions
265  /// are specified through \p N1 and \p N2.
266  int64_t getAddrDispShift(const MachineInstr &MI1, unsigned N1,
267  const MachineInstr &MI2, unsigned N2) const;
268 
269  /// Returns true if the \p Last LEA instruction can be replaced by the
270  /// \p First. The difference between displacements of the addresses calculated
271  /// by these LEAs is returned in \p AddrDispShift. It'll be used for proper
272  /// replacement of the \p Last LEA's uses with the \p First's def register.
273  bool isReplaceable(const MachineInstr &First, const MachineInstr &Last,
274  int64_t &AddrDispShift) const;
275 
276  /// Find all LEA instructions in the basic block. Also, assign position
277  /// numbers to all instructions in the basic block to speed up calculation of
278  /// distance between them.
279  void findLEAs(const MachineBasicBlock &MBB, MemOpMap &LEAs);
280 
281  /// Removes redundant address calculations.
282  bool removeRedundantAddrCalc(MemOpMap &LEAs);
283 
284  /// Replace debug value MI with a new debug value instruction using register
285  /// VReg with an appropriate offset and DIExpression to incorporate the
286  /// address displacement AddrDispShift. Return new debug value instruction.
287  MachineInstr *replaceDebugValue(MachineInstr &MI, unsigned VReg,
288  int64_t AddrDispShift);
289 
290  /// Removes LEAs which calculate similar addresses.
291  bool removeRedundantLEAs(MemOpMap &LEAs);
292 
294 
296  const X86InstrInfo *TII;
297  const X86RegisterInfo *TRI;
298 
299  static char ID;
300 };
301 
302 } // end anonymous namespace
303 
304 char OptimizeLEAPass::ID = 0;
305 
306 FunctionPass *llvm::createX86OptimizeLEAs() { return new OptimizeLEAPass(); }
307 
308 int OptimizeLEAPass::calcInstrDist(const MachineInstr &First,
309  const MachineInstr &Last) {
310  // Both instructions must be in the same basic block and they must be
311  // presented in InstrPos.
312  assert(Last.getParent() == First.getParent() &&
313  "Instructions are in different basic blocks");
314  assert(InstrPos.find(&First) != InstrPos.end() &&
315  InstrPos.find(&Last) != InstrPos.end() &&
316  "Instructions' positions are undefined");
317 
318  return InstrPos[&Last] - InstrPos[&First];
319 }
320 
321 // Find the best LEA instruction in the List to replace address recalculation in
322 // MI. Such LEA must meet these requirements:
323 // 1) The address calculated by the LEA differs only by the displacement from
324 // the address used in MI.
325 // 2) The register class of the definition of the LEA is compatible with the
326 // register class of the address base register of MI.
327 // 3) Displacement of the new memory operand should fit in 1 byte if possible.
328 // 4) The LEA should be as close to MI as possible, and prior to it if
329 // possible.
330 bool OptimizeLEAPass::chooseBestLEA(const SmallVectorImpl<MachineInstr *> &List,
331  const MachineInstr &MI,
332  MachineInstr *&BestLEA,
333  int64_t &AddrDispShift, int &Dist) {
334  const MachineFunction *MF = MI.getParent()->getParent();
335  const MCInstrDesc &Desc = MI.getDesc();
336  int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags) +
337  X86II::getOperandBias(Desc);
338 
339  BestLEA = nullptr;
340 
341  // Loop over all LEA instructions.
342  for (auto DefMI : List) {
343  // Get new address displacement.
344  int64_t AddrDispShiftTemp = getAddrDispShift(MI, MemOpNo, *DefMI, 1);
345 
346  // Make sure address displacement fits 4 bytes.
347  if (!isInt<32>(AddrDispShiftTemp))
348  continue;
349 
350  // Check that LEA def register can be used as MI address base. Some
351  // instructions can use a limited set of registers as address base, for
352  // example MOV8mr_NOREX. We could constrain the register class of the LEA
353  // def to suit MI, however since this case is very rare and hard to
354  // reproduce in a test it's just more reliable to skip the LEA.
355  if (TII->getRegClass(Desc, MemOpNo + X86::AddrBaseReg, TRI, *MF) !=
356  MRI->getRegClass(DefMI->getOperand(0).getReg()))
357  continue;
358 
359  // Choose the closest LEA instruction from the list, prior to MI if
360  // possible. Note that we took into account resulting address displacement
361  // as well. Also note that the list is sorted by the order in which the LEAs
362  // occur, so the break condition is pretty simple.
363  int DistTemp = calcInstrDist(*DefMI, MI);
364  assert(DistTemp != 0 &&
365  "The distance between two different instructions cannot be zero");
366  if (DistTemp > 0 || BestLEA == nullptr) {
367  // Do not update return LEA, if the current one provides a displacement
368  // which fits in 1 byte, while the new candidate does not.
369  if (BestLEA != nullptr && !isInt<8>(AddrDispShiftTemp) &&
370  isInt<8>(AddrDispShift))
371  continue;
372 
373  BestLEA = DefMI;
374  AddrDispShift = AddrDispShiftTemp;
375  Dist = DistTemp;
376  }
377 
378  // FIXME: Maybe we should not always stop at the first LEA after MI.
379  if (DistTemp < 0)
380  break;
381  }
382 
383  return BestLEA != nullptr;
384 }
385 
386 // Get the difference between the addresses' displacements of the two
387 // instructions \p MI1 and \p MI2. The numbers of the first memory operands are
388 // passed through \p N1 and \p N2.
389 int64_t OptimizeLEAPass::getAddrDispShift(const MachineInstr &MI1, unsigned N1,
390  const MachineInstr &MI2,
391  unsigned N2) const {
392  const MachineOperand &Op1 = MI1.getOperand(N1 + X86::AddrDisp);
393  const MachineOperand &Op2 = MI2.getOperand(N2 + X86::AddrDisp);
394 
395  assert(isSimilarDispOp(Op1, Op2) &&
396  "Address displacement operands are not compatible");
397 
398  // After the assert above we can be sure that both operands are of the same
399  // valid type and use the same symbol/index/address, thus displacement shift
400  // calculation is rather simple.
401  if (Op1.isJTI())
402  return 0;
403  return Op1.isImm() ? Op1.getImm() - Op2.getImm()
404  : Op1.getOffset() - Op2.getOffset();
405 }
406 
407 // Check that the Last LEA can be replaced by the First LEA. To be so,
408 // these requirements must be met:
409 // 1) Addresses calculated by LEAs differ only by displacement.
410 // 2) Def registers of LEAs belong to the same class.
411 // 3) All uses of the Last LEA def register are replaceable, thus the
412 // register is used only as address base.
413 bool OptimizeLEAPass::isReplaceable(const MachineInstr &First,
414  const MachineInstr &Last,
415  int64_t &AddrDispShift) const {
416  assert(isLEA(First) && isLEA(Last) &&
417  "The function works only with LEA instructions");
418 
419  // Make sure that LEA def registers belong to the same class. There may be
420  // instructions (like MOV8mr_NOREX) which allow a limited set of registers to
421  // be used as their operands, so we must be sure that replacing one LEA
422  // with another won't lead to putting a wrong register in the instruction.
423  if (MRI->getRegClass(First.getOperand(0).getReg()) !=
424  MRI->getRegClass(Last.getOperand(0).getReg()))
425  return false;
426 
427  // Get new address displacement.
428  AddrDispShift = getAddrDispShift(Last, 1, First, 1);
429 
430  // Loop over all uses of the Last LEA to check that its def register is
431  // used only as address base for memory accesses. If so, it can be
432  // replaced, otherwise - no.
433  for (auto &MO : MRI->use_nodbg_operands(Last.getOperand(0).getReg())) {
434  MachineInstr &MI = *MO.getParent();
435 
436  // Get the number of the first memory operand.
437  const MCInstrDesc &Desc = MI.getDesc();
438  int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags);
439 
440  // If the use instruction has no memory operand - the LEA is not
441  // replaceable.
442  if (MemOpNo < 0)
443  return false;
444 
445  MemOpNo += X86II::getOperandBias(Desc);
446 
447  // If the address base of the use instruction is not the LEA def register -
448  // the LEA is not replaceable.
449  if (!isIdenticalOp(MI.getOperand(MemOpNo + X86::AddrBaseReg), MO))
450  return false;
451 
452  // If the LEA def register is used as any other operand of the use
453  // instruction - the LEA is not replaceable.
454  for (unsigned i = 0; i < MI.getNumOperands(); i++)
455  if (i != (unsigned)(MemOpNo + X86::AddrBaseReg) &&
456  isIdenticalOp(MI.getOperand(i), MO))
457  return false;
458 
459  // Check that the new address displacement will fit 4 bytes.
460  if (MI.getOperand(MemOpNo + X86::AddrDisp).isImm() &&
461  !isInt<32>(MI.getOperand(MemOpNo + X86::AddrDisp).getImm() +
462  AddrDispShift))
463  return false;
464  }
465 
466  return true;
467 }
468 
469 void OptimizeLEAPass::findLEAs(const MachineBasicBlock &MBB, MemOpMap &LEAs) {
470  unsigned Pos = 0;
471  for (auto &MI : MBB) {
472  // Assign the position number to the instruction. Note that we are going to
473  // move some instructions during the optimization however there will never
474  // be a need to move two instructions before any selected instruction. So to
475  // avoid multiple positions' updates during moves we just increase position
476  // counter by two leaving a free space for instructions which will be moved.
477  InstrPos[&MI] = Pos += 2;
478 
479  if (isLEA(MI))
480  LEAs[getMemOpKey(MI, 1)].push_back(const_cast<MachineInstr *>(&MI));
481  }
482 }
483 
484 // Try to find load and store instructions which recalculate addresses already
485 // calculated by some LEA and replace their memory operands with its def
486 // register.
487 bool OptimizeLEAPass::removeRedundantAddrCalc(MemOpMap &LEAs) {
488  bool Changed = false;
489 
490  assert(!LEAs.empty());
491  MachineBasicBlock *MBB = (*LEAs.begin()->second.begin())->getParent();
492 
493  // Process all instructions in basic block.
494  for (auto I = MBB->begin(), E = MBB->end(); I != E;) {
495  MachineInstr &MI = *I++;
496 
497  // Instruction must be load or store.
498  if (!MI.mayLoadOrStore())
499  continue;
500 
501  // Get the number of the first memory operand.
502  const MCInstrDesc &Desc = MI.getDesc();
503  int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags);
504 
505  // If instruction has no memory operand - skip it.
506  if (MemOpNo < 0)
507  continue;
508 
509  MemOpNo += X86II::getOperandBias(Desc);
510 
511  // Do not call chooseBestLEA if there was no matching LEA
512  auto Insns = LEAs.find(getMemOpKey(MI, MemOpNo));
513  if (Insns == LEAs.end())
514  continue;
515 
516  // Get the best LEA instruction to replace address calculation.
518  int64_t AddrDispShift;
519  int Dist;
520  if (!chooseBestLEA(Insns->second, MI, DefMI, AddrDispShift, Dist))
521  continue;
522 
523  // If LEA occurs before current instruction, we can freely replace
524  // the instruction. If LEA occurs after, we can lift LEA above the
525  // instruction and this way to be able to replace it. Since LEA and the
526  // instruction have similar memory operands (thus, the same def
527  // instructions for these operands), we can always do that, without
528  // worries of using registers before their defs.
529  if (Dist < 0) {
530  DefMI->removeFromParent();
531  MBB->insert(MachineBasicBlock::iterator(&MI), DefMI);
532  InstrPos[DefMI] = InstrPos[&MI] - 1;
533 
534  // Make sure the instructions' position numbers are sane.
535  assert(((InstrPos[DefMI] == 1 &&
536  MachineBasicBlock::iterator(DefMI) == MBB->begin()) ||
537  InstrPos[DefMI] >
538  InstrPos[&*std::prev(MachineBasicBlock::iterator(DefMI))]) &&
539  "Instruction positioning is broken");
540  }
541 
542  // Since we can possibly extend register lifetime, clear kill flags.
543  MRI->clearKillFlags(DefMI->getOperand(0).getReg());
544 
545  ++NumSubstLEAs;
546  LLVM_DEBUG(dbgs() << "OptimizeLEAs: Candidate to replace: "; MI.dump(););
547 
548  // Change instruction operands.
549  MI.getOperand(MemOpNo + X86::AddrBaseReg)
550  .ChangeToRegister(DefMI->getOperand(0).getReg(), false);
552  MI.getOperand(MemOpNo + X86::AddrIndexReg)
553  .ChangeToRegister(X86::NoRegister, false);
554  MI.getOperand(MemOpNo + X86::AddrDisp).ChangeToImmediate(AddrDispShift);
555  MI.getOperand(MemOpNo + X86::AddrSegmentReg)
556  .ChangeToRegister(X86::NoRegister, false);
557 
558  LLVM_DEBUG(dbgs() << "OptimizeLEAs: Replaced by: "; MI.dump(););
559 
560  Changed = true;
561  }
562 
563  return Changed;
564 }
565 
566 MachineInstr *OptimizeLEAPass::replaceDebugValue(MachineInstr &MI,
567  unsigned VReg,
568  int64_t AddrDispShift) {
569  DIExpression *Expr = const_cast<DIExpression *>(MI.getDebugExpression());
570  if (AddrDispShift != 0)
571  Expr = DIExpression::prepend(Expr, DIExpression::StackValue, AddrDispShift);
572 
573  // Replace DBG_VALUE instruction with modified version.
574  MachineBasicBlock *MBB = MI.getParent();
575  DebugLoc DL = MI.getDebugLoc();
576  bool IsIndirect = MI.isIndirectDebugValue();
577  const MDNode *Var = MI.getDebugVariable();
578  if (IsIndirect)
579  assert(MI.getOperand(1).getImm() == 0 && "DBG_VALUE with nonzero offset");
580  return BuildMI(*MBB, MBB->erase(&MI), DL, TII->get(TargetOpcode::DBG_VALUE),
581  IsIndirect, VReg, Var, Expr);
582 }
583 
584 // Try to find similar LEAs in the list and replace one with another.
585 bool OptimizeLEAPass::removeRedundantLEAs(MemOpMap &LEAs) {
586  bool Changed = false;
587 
588  // Loop over all entries in the table.
589  for (auto &E : LEAs) {
590  auto &List = E.second;
591 
592  // Loop over all LEA pairs.
593  auto I1 = List.begin();
594  while (I1 != List.end()) {
595  MachineInstr &First = **I1;
596  auto I2 = std::next(I1);
597  while (I2 != List.end()) {
598  MachineInstr &Last = **I2;
599  int64_t AddrDispShift;
600 
601  // LEAs should be in occurrence order in the list, so we can freely
602  // replace later LEAs with earlier ones.
603  assert(calcInstrDist(First, Last) > 0 &&
604  "LEAs must be in occurrence order in the list");
605 
606  // Check that the Last LEA instruction can be replaced by the First.
607  if (!isReplaceable(First, Last, AddrDispShift)) {
608  ++I2;
609  continue;
610  }
611 
612  // Loop over all uses of the Last LEA and update their operands. Note
613  // that the correctness of this has already been checked in the
614  // isReplaceable function.
615  Register FirstVReg = First.getOperand(0).getReg();
616  Register LastVReg = Last.getOperand(0).getReg();
617  for (auto UI = MRI->use_begin(LastVReg), UE = MRI->use_end();
618  UI != UE;) {
619  MachineOperand &MO = *UI++;
620  MachineInstr &MI = *MO.getParent();
621 
622  if (MI.isDebugValue()) {
623  // Replace DBG_VALUE instruction with modified version using the
624  // register from the replacing LEA and the address displacement
625  // between the LEA instructions.
626  replaceDebugValue(MI, FirstVReg, AddrDispShift);
627  continue;
628  }
629 
630  // Get the number of the first memory operand.
631  const MCInstrDesc &Desc = MI.getDesc();
632  int MemOpNo =
634  X86II::getOperandBias(Desc);
635 
636  // Update address base.
637  MO.setReg(FirstVReg);
638 
639  // Update address disp.
640  MachineOperand &Op = MI.getOperand(MemOpNo + X86::AddrDisp);
641  if (Op.isImm())
642  Op.setImm(Op.getImm() + AddrDispShift);
643  else if (!Op.isJTI())
644  Op.setOffset(Op.getOffset() + AddrDispShift);
645  }
646 
647  // Since we can possibly extend register lifetime, clear kill flags.
648  MRI->clearKillFlags(FirstVReg);
649 
650  ++NumRedundantLEAs;
651  LLVM_DEBUG(dbgs() << "OptimizeLEAs: Remove redundant LEA: ";
652  Last.dump(););
653 
654  // By this moment, all of the Last LEA's uses must be replaced. So we
655  // can freely remove it.
656  assert(MRI->use_empty(LastVReg) &&
657  "The LEA's def register must have no uses");
658  Last.eraseFromParent();
659 
660  // Erase removed LEA from the list.
661  I2 = List.erase(I2);
662 
663  Changed = true;
664  }
665  ++I1;
666  }
667  }
668 
669  return Changed;
670 }
671 
672 bool OptimizeLEAPass::runOnMachineFunction(MachineFunction &MF) {
673  bool Changed = false;
674 
675  if (DisableX86LEAOpt || skipFunction(MF.getFunction()))
676  return false;
677 
678  MRI = &MF.getRegInfo();
679  TII = MF.getSubtarget<X86Subtarget>().getInstrInfo();
680  TRI = MF.getSubtarget<X86Subtarget>().getRegisterInfo();
681 
682  // Process all basic blocks.
683  for (auto &MBB : MF) {
684  MemOpMap LEAs;
685  InstrPos.clear();
686 
687  // Find all LEA instructions in basic block.
688  findLEAs(MBB, LEAs);
689 
690  // If current basic block has no LEAs, move on to the next one.
691  if (LEAs.empty())
692  continue;
693 
694  // Remove redundant LEA instructions.
695  Changed |= removeRedundantLEAs(LEAs);
696 
697  // Remove redundant address calculations. Do it only for -Os/-Oz since only
698  // a code size gain is expected from this part of the pass.
699  if (MF.getFunction().hasOptSize())
700  Changed |= removeRedundantAddrCalc(LEAs);
701  }
702 
703  return Changed;
704 }
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
static unsigned getHashValue(const MemOpKey &Val)
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:385
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:63
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:178
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.
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
void setReg(Register Reg)
Change the register this operand corresponds to.
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.
AddrSegmentReg - The operand # of the segment in the memory operand.
Definition: X86BaseInfo.h:38
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
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
const NodeList & List
Definition: RDFGraph.cpp:201
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
void ChangeToRegister(Register 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...
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:1973
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...
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
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