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

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