contrib/llvm-project/llvm/lib/Target/X86/X86OptimizeLEAs.cpp

   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/CodeGen/MachineBasicBlock.h"
  29 #include "llvm/CodeGen/MachineFunction.h"
  30 #include "llvm/CodeGen/MachineFunctionPass.h"
  31 #include "llvm/CodeGen/MachineInstr.h"
  32 #include "llvm/CodeGen/MachineInstrBuilder.h"
  33 #include "llvm/CodeGen/MachineOperand.h"
  34 #include "llvm/CodeGen/MachineRegisterInfo.h"
  35 #include "llvm/CodeGen/TargetOpcodes.h"
  36 #include "llvm/CodeGen/TargetRegisterInfo.h"
  37 #include "llvm/IR/DebugInfoMetadata.h"
  38 #include "llvm/IR/DebugLoc.h"
  39 #include "llvm/IR/Function.h"
  40 #include "llvm/MC/MCInstrDesc.h"
  41 #include "llvm/Support/CommandLine.h"
  42 #include "llvm/Support/Debug.h"
  43 #include "llvm/Support/ErrorHandling.h"
  44 #include "llvm/Support/MathExtras.h"
  45 #include "llvm/Support/raw_ostream.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> {
 116   using PtrInfo = DenseMapInfo<const MachineOperand *>;
 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()) {
 145     case MachineOperand::MO_Immediate:
 146       break;
 147     case MachineOperand::MO_ConstantPoolIndex:
 148     case MachineOperand::MO_JumpTableIndex:
 149       Hash = hash_combine(Hash, Val.Disp->getIndex());
 150       break;
 151     case MachineOperand::MO_ExternalSymbol:
 152       Hash = hash_combine(Hash, Val.Disp->getSymbolName());
 153       break;
 154     case MachineOperand::MO_GlobalAddress:
 155       Hash = hash_combine(Hash, Val.Disp->getGlobal());
 156       break;
 157     case MachineOperand::MO_BlockAddress:
 158       Hash = hash_combine(Hash, Val.Disp->getBlockAddress());
 159       break;
 160     case MachineOperand::MO_MCSymbol:
 161       Hash = hash_combine(Hash, Val.Disp->getMCSymbol());
 162       break;
 163     case MachineOperand::MO_MachineBasicBlock:
 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),
 194                   &MI.getOperand(N + X86::AddrSegmentReg),
 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() ||
 202           !TargetRegisterInfo::isPhysicalRegister(MO1.getReg()));
 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:
 250   using MemOpMap = DenseMap<MemOpKey, SmallVector<MachineInstr *, 16>>;
 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
 294   DenseMap<const MachineInstr *, unsigned> InstrPos;
 295
 296   MachineRegisterInfo *MRI;
 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.
 518     MachineInstr *DefMI;
 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);
 552     MI.getOperand(MemOpNo + X86::AddrScaleAmt).ChangeToImmediate(1);
 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 =
 634               X86II::getMemoryOperandNo(Desc.TSFlags) +
 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 }