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 code size.
  12 // Currently, it does one thing:
  13 // 1) Address calculations in load and store instructions are replaced by
  14 //    existing LEA def registers where possible.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "X86.h"
  19 #include "X86InstrInfo.h"
  20 #include "X86Subtarget.h"
  21 #include "llvm/ADT/Statistic.h"
  22 #include "llvm/CodeGen/LiveVariables.h"
  23 #include "llvm/CodeGen/MachineFunctionPass.h"
  24 #include "llvm/CodeGen/MachineInstrBuilder.h"
  25 #include "llvm/CodeGen/MachineRegisterInfo.h"
  26 #include "llvm/CodeGen/Passes.h"
  27 #include "llvm/IR/Function.h"
  28 #include "llvm/Support/Debug.h"
  29 #include "llvm/Support/raw_ostream.h"
  30 #include "llvm/Target/TargetInstrInfo.h"
  31
  32 using namespace llvm;
  33
  34 #define DEBUG_TYPE "x86-optimize-LEAs"
  35
  36 static cl::opt<bool> EnableX86LEAOpt("enable-x86-lea-opt", cl::Hidden,
  37                                      cl::desc("X86: Enable LEA optimizations."),
  38                                      cl::init(false));
  39
  40 STATISTIC(NumSubstLEAs, "Number of LEA instruction substitutions");
  41
  42 namespace {
  43 class OptimizeLEAPass : public MachineFunctionPass {
  44 public:
  45   OptimizeLEAPass() : MachineFunctionPass(ID) {}
  46
  47   const char *getPassName() const override { return "X86 LEA Optimize"; }
  48
  49   /// \brief Loop over all of the basic blocks, replacing address
  50   /// calculations in load and store instructions, if it's already
  51   /// been calculated by LEA. Also, remove redundant LEAs.
  52   bool runOnMachineFunction(MachineFunction &MF) override;
  53
  54 private:
  55   /// \brief Returns a distance between two instructions inside one basic block.
  56   /// Negative result means, that instructions occur in reverse order.
  57   int calcInstrDist(const MachineInstr &First, const MachineInstr &Last);
  58
  59   /// \brief Choose the best \p LEA instruction from the \p List to replace
  60   /// address calculation in \p MI instruction. Return the address displacement
  61   /// and the distance between \p MI and the choosen \p LEA in \p AddrDispShift
  62   /// and \p Dist.
  63   bool chooseBestLEA(const SmallVectorImpl<MachineInstr *> &List,
  64                      const MachineInstr &MI, MachineInstr *&LEA,
  65                      int64_t &AddrDispShift, int &Dist);
  66
  67   /// \brief Returns true if two machine operand are identical and they are not
  68   /// physical registers.
  69   bool isIdenticalOp(const MachineOperand &MO1, const MachineOperand &MO2);
  70
  71   /// \brief Returns true if the instruction is LEA.
  72   bool isLEA(const MachineInstr &MI);
  73
  74   /// \brief Returns true if two instructions have memory operands that only
  75   /// differ by displacement. The numbers of the first memory operands for both
  76   /// instructions are specified through \p N1 and \p N2. The address
  77   /// displacement is returned through AddrDispShift.
  78   bool isSimilarMemOp(const MachineInstr &MI1, unsigned N1,
  79                       const MachineInstr &MI2, unsigned N2,
  80                       int64_t &AddrDispShift);
  81
  82   /// \brief Find all LEA instructions in the basic block. Also, assign position
  83   /// numbers to all instructions in the basic block to speed up calculation of
  84   /// distance between them.
  85   void findLEAs(const MachineBasicBlock &MBB,
  86                 SmallVectorImpl<MachineInstr *> &List);
  87
  88   /// \brief Removes redundant address calculations.
  89   bool removeRedundantAddrCalc(const SmallVectorImpl<MachineInstr *> &List);
  90
  91   DenseMap<const MachineInstr *, unsigned> InstrPos;
  92
  93   MachineRegisterInfo *MRI;
  94   const X86InstrInfo *TII;
  95   const X86RegisterInfo *TRI;
  96
  97   static char ID;
  98 };
  99 char OptimizeLEAPass::ID = 0;
 100 }
 101
 102 FunctionPass *llvm::createX86OptimizeLEAs() { return new OptimizeLEAPass(); }
 103
 104 int OptimizeLEAPass::calcInstrDist(const MachineInstr &First,
 105                                    const MachineInstr &Last) {
 106   // Both instructions must be in the same basic block and they must be
 107   // presented in InstrPos.
 108   assert(Last.getParent() == First.getParent() &&
 109          "Instructions are in different basic blocks");
 110   assert(InstrPos.find(&First) != InstrPos.end() &&
 111          InstrPos.find(&Last) != InstrPos.end() &&
 112          "Instructions' positions are undefined");
 113
 114   return InstrPos[&Last] - InstrPos[&First];
 115 }
 116
 117 // Find the best LEA instruction in the List to replace address recalculation in
 118 // MI. Such LEA must meet these requirements:
 119 // 1) The address calculated by the LEA differs only by the displacement from
 120 //    the address used in MI.
 121 // 2) The register class of the definition of the LEA is compatible with the
 122 //    register class of the address base register of MI.
 123 // 3) Displacement of the new memory operand should fit in 1 byte if possible.
 124 // 4) The LEA should be as close to MI as possible, and prior to it if
 125 //    possible.
 126 bool OptimizeLEAPass::chooseBestLEA(const SmallVectorImpl<MachineInstr *> &List,
 127                                     const MachineInstr &MI, MachineInstr *&LEA,
 128                                     int64_t &AddrDispShift, int &Dist) {
 129   const MachineFunction *MF = MI.getParent()->getParent();
 130   const MCInstrDesc &Desc = MI.getDesc();
 131   int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags, MI.getOpcode()) +
 132                 X86II::getOperandBias(Desc);
 133
 134   LEA = nullptr;
 135
 136   // Loop over all LEA instructions.
 137   for (auto DefMI : List) {
 138     int64_t AddrDispShiftTemp = 0;
 139
 140     // Compare instructions memory operands.
 141     if (!isSimilarMemOp(MI, MemOpNo, *DefMI, 1, AddrDispShiftTemp))
 142       continue;
 143
 144     // Make sure address displacement fits 4 bytes.
 145     if (!isInt<32>(AddrDispShiftTemp))
 146       continue;
 147
 148     // Check that LEA def register can be used as MI address base. Some
 149     // instructions can use a limited set of registers as address base, for
 150     // example MOV8mr_NOREX. We could constrain the register class of the LEA
 151     // def to suit MI, however since this case is very rare and hard to
 152     // reproduce in a test it's just more reliable to skip the LEA.
 153     if (TII->getRegClass(Desc, MemOpNo + X86::AddrBaseReg, TRI, *MF) !=
 154         MRI->getRegClass(DefMI->getOperand(0).getReg()))
 155       continue;
 156
 157     // Choose the closest LEA instruction from the list, prior to MI if
 158     // possible. Note that we took into account resulting address displacement
 159     // as well. Also note that the list is sorted by the order in which the LEAs
 160     // occur, so the break condition is pretty simple.
 161     int DistTemp = calcInstrDist(*DefMI, MI);
 162     assert(DistTemp != 0 &&
 163            "The distance between two different instructions cannot be zero");
 164     if (DistTemp > 0 || LEA == nullptr) {
 165       // Do not update return LEA, if the current one provides a displacement
 166       // which fits in 1 byte, while the new candidate does not.
 167       if (LEA != nullptr && !isInt<8>(AddrDispShiftTemp) &&
 168           isInt<8>(AddrDispShift))
 169         continue;
 170
 171       LEA = DefMI;
 172       AddrDispShift = AddrDispShiftTemp;
 173       Dist = DistTemp;
 174     }
 175
 176     // FIXME: Maybe we should not always stop at the first LEA after MI.
 177     if (DistTemp < 0)
 178       break;
 179   }
 180
 181   return LEA != nullptr;
 182 }
 183
 184 bool OptimizeLEAPass::isIdenticalOp(const MachineOperand &MO1,
 185                                     const MachineOperand &MO2) {
 186   return MO1.isIdenticalTo(MO2) &&
 187          (!MO1.isReg() ||
 188           !TargetRegisterInfo::isPhysicalRegister(MO1.getReg()));
 189 }
 190
 191 bool OptimizeLEAPass::isLEA(const MachineInstr &MI) {
 192   unsigned Opcode = MI.getOpcode();
 193   return Opcode == X86::LEA16r || Opcode == X86::LEA32r ||
 194          Opcode == X86::LEA64r || Opcode == X86::LEA64_32r;
 195 }
 196
 197 // Check if MI1 and MI2 have memory operands which represent addresses that
 198 // differ only by displacement.
 199 bool OptimizeLEAPass::isSimilarMemOp(const MachineInstr &MI1, unsigned N1,
 200                                      const MachineInstr &MI2, unsigned N2,
 201                                      int64_t &AddrDispShift) {
 202   // Address base, scale, index and segment operands must be identical.
 203   static const int IdenticalOpNums[] = {X86::AddrBaseReg, X86::AddrScaleAmt,
 204                                         X86::AddrIndexReg, X86::AddrSegmentReg};
 205   for (auto &N : IdenticalOpNums)
 206     if (!isIdenticalOp(MI1.getOperand(N1 + N), MI2.getOperand(N2 + N)))
 207       return false;
 208
 209   // Address displacement operands may differ by a constant.
 210   const MachineOperand *Op1 = &MI1.getOperand(N1 + X86::AddrDisp);
 211   const MachineOperand *Op2 = &MI2.getOperand(N2 + X86::AddrDisp);
 212   if (!isIdenticalOp(*Op1, *Op2)) {
 213     if (Op1->isImm() && Op2->isImm())
 214       AddrDispShift = Op1->getImm() - Op2->getImm();
 215     else if (Op1->isGlobal() && Op2->isGlobal() &&
 216              Op1->getGlobal() == Op2->getGlobal())
 217       AddrDispShift = Op1->getOffset() - Op2->getOffset();
 218     else
 219       return false;
 220   }
 221
 222   return true;
 223 }
 224
 225 void OptimizeLEAPass::findLEAs(const MachineBasicBlock &MBB,
 226                                SmallVectorImpl<MachineInstr *> &List) {
 227   unsigned Pos = 0;
 228   for (auto &MI : MBB) {
 229     // Assign the position number to the instruction. Note that we are going to
 230     // move some instructions during the optimization however there will never
 231     // be a need to move two instructions before any selected instruction. So to
 232     // avoid multiple positions' updates during moves we just increase position
 233     // counter by two leaving a free space for instructions which will be moved.
 234     InstrPos[&MI] = Pos += 2;
 235
 236     if (isLEA(MI))
 237       List.push_back(const_cast<MachineInstr *>(&MI));
 238   }
 239 }
 240
 241 // Try to find load and store instructions which recalculate addresses already
 242 // calculated by some LEA and replace their memory operands with its def
 243 // register.
 244 bool OptimizeLEAPass::removeRedundantAddrCalc(
 245     const SmallVectorImpl<MachineInstr *> &List) {
 246   bool Changed = false;
 247
 248   assert(List.size() > 0);
 249   MachineBasicBlock *MBB = List[0]->getParent();
 250
 251   // Process all instructions in basic block.
 252   for (auto I = MBB->begin(), E = MBB->end(); I != E;) {
 253     MachineInstr &MI = *I++;
 254     unsigned Opcode = MI.getOpcode();
 255
 256     // Instruction must be load or store.
 257     if (!MI.mayLoadOrStore())
 258       continue;
 259
 260     // Get the number of the first memory operand.
 261     const MCInstrDesc &Desc = MI.getDesc();
 262     int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags, Opcode);
 263
 264     // If instruction has no memory operand - skip it.
 265     if (MemOpNo < 0)
 266       continue;
 267
 268     MemOpNo += X86II::getOperandBias(Desc);
 269
 270     // Get the best LEA instruction to replace address calculation.
 271     MachineInstr *DefMI;
 272     int64_t AddrDispShift;
 273     int Dist;
 274     if (!chooseBestLEA(List, MI, DefMI, AddrDispShift, Dist))
 275       continue;
 276
 277     // If LEA occurs before current instruction, we can freely replace
 278     // the instruction. If LEA occurs after, we can lift LEA above the
 279     // instruction and this way to be able to replace it. Since LEA and the
 280     // instruction have similar memory operands (thus, the same def
 281     // instructions for these operands), we can always do that, without
 282     // worries of using registers before their defs.
 283     if (Dist < 0) {
 284       DefMI->removeFromParent();
 285       MBB->insert(MachineBasicBlock::iterator(&MI), DefMI);
 286       InstrPos[DefMI] = InstrPos[&MI] - 1;
 287
 288       // Make sure the instructions' position numbers are sane.
 289       assert(((InstrPos[DefMI] == 1 && DefMI == MBB->begin()) ||
 290               InstrPos[DefMI] >
 291                   InstrPos[std::prev(MachineBasicBlock::iterator(DefMI))]) &&
 292              "Instruction positioning is broken");
 293     }
 294
 295     // Since we can possibly extend register lifetime, clear kill flags.
 296     MRI->clearKillFlags(DefMI->getOperand(0).getReg());
 297
 298     ++NumSubstLEAs;
 299     DEBUG(dbgs() << "OptimizeLEAs: Candidate to replace: "; MI.dump(););
 300
 301     // Change instruction operands.
 302     MI.getOperand(MemOpNo + X86::AddrBaseReg)
 303         .ChangeToRegister(DefMI->getOperand(0).getReg(), false);
 304     MI.getOperand(MemOpNo + X86::AddrScaleAmt).ChangeToImmediate(1);
 305     MI.getOperand(MemOpNo + X86::AddrIndexReg)
 306         .ChangeToRegister(X86::NoRegister, false);
 307     MI.getOperand(MemOpNo + X86::AddrDisp).ChangeToImmediate(AddrDispShift);
 308     MI.getOperand(MemOpNo + X86::AddrSegmentReg)
 309         .ChangeToRegister(X86::NoRegister, false);
 310
 311     DEBUG(dbgs() << "OptimizeLEAs: Replaced by: "; MI.dump(););
 312
 313     Changed = true;
 314   }
 315
 316   return Changed;
 317 }
 318
 319 bool OptimizeLEAPass::runOnMachineFunction(MachineFunction &MF) {
 320   bool Changed = false;
 321
 322   // Perform this optimization only if we care about code size.
 323   if (!EnableX86LEAOpt || !MF.getFunction()->optForSize())
 324     return false;
 325
 326   MRI = &MF.getRegInfo();
 327   TII = MF.getSubtarget<X86Subtarget>().getInstrInfo();
 328   TRI = MF.getSubtarget<X86Subtarget>().getRegisterInfo();
 329
 330   // Process all basic blocks.
 331   for (auto &MBB : MF) {
 332     SmallVector<MachineInstr *, 16> LEAs;
 333     InstrPos.clear();
 334
 335     // Find all LEA instructions in basic block.
 336     findLEAs(MBB, LEAs);
 337
 338     // If current basic block has no LEAs, move on to the next one.
 339     if (LEAs.empty())
 340       continue;
 341
 342     // Remove redundant address calculations.
 343     Changed |= removeRedundantAddrCalc(LEAs);
 344   }
 345
 346   return Changed;
 347 }