LEA code size optimization pass (Part 2): Remove redundant LEA instructions

[aturetsk]

Summary

Make x86 OptimizeLEAs pass remove LEA instruction if there is another LEA (in the same basic block) which calculates address differing only be a displacement. Works only for -Oz.

[aturetsk]

Follows up http://reviews.llvm.org/D13294.

[aturetsk]

Ping.

[aturetsk]

Ping.

[nadav]

LGTM.

[aturetsk]

Made some changes according to the comments to the first part of the patch

[aturetsk]

Minor test changes to be up-to-date with the first part of the patch.

[aturetsk]

Improved comments.

[aturetsk]

Sync up with the changes of the first part of the patch.

[aturetsk]

Ping.

[aturetsk]

Updated to the latest trunk.

[qcolombet]

Hi Andrey,

Thanks for working on this.

Out of curiosity, what performance impact do you see?
I.e., compile time and code size improvements.

Couple more comments inlined.

Thanks,
-Quentin

lib/Target/X86/X86OptimizeLEAs.cpp

81

Please comment what AddrDispShift is and how it should be used by the caller.

213

differ?

240

This assert is useless.
This is already enforced by isLEA, isn’t it?

Moreover, in the previous check (getOperand(0).getReg()), the compiler would have asserted if the operand was not a register.

258

Could you add a comment over that loop?

426

The formatting looks funny to me, have you used clang-format?

443

else llvm_unreachable or assert?

454

Add a message in the assert.

[aturetsk]

Fixed remarks from inline comments.

[aturetsk]

Hi Quentin,
Thanks for the review.
This part reduces code size on Spec2000 for additional 0.1%, making it total 0.3% at -Oz.
The performance impact I measured was negative, yet very close to zero. I didn't want to possibly hurt performance at any rate at -Os, so I enabled it only for -Oz and I intend to keep it so until I do some analysis.
I don't see any significant compile time impact on Spec 2000 or the test from https://llvm.org/bugs/show_bug.cgi?id=25843. The complexity of removeRedundantLEAs is something like O(n^2), so the compile time should not blow up for big basic blocks.

lib/Target/X86/X86OptimizeLEAs.cpp

81

Done.

213

Fixed.

240

Removed.

258

Done.

426

Absolutely, that's clang-format's doing.

443

Done.

454

Done.

[qcolombet]

LGTM.

lib/Target/X86/X86.h

 /// This will prevent a stall when returning on the Atom.
 FunctionPass *createX86PadShortFunctions();
 
 /// Return a a pass that selectively replaces certain instructions (like add,
 /// sub, inc, dec, some shifts, and some multiplies) by equivalent LEA
 /// instructions, in order to eliminate execution delays in some processors.
 FunctionPass *createX86FixupLEAs();
 
-/// Return a pass that removes redundant address recalculations.
+/// Return a pass that removes redundant LEA instructions and redundant address
+/// recalculations.
 FunctionPass *createX86OptimizeLEAs();
 
 /// Return a pass that optimizes the code-size of x86 call sequences. This is
 /// done by replacing esp-relative movs with pushes.
 FunctionPass *createX86CallFrameOptimization();
 
 /// Return an IR pass that inserts EH registration stack objects and explicit
 /// EH state updates. This pass must run after EH preparation, which does

lib/Target/X86/X86OptimizeLEAs.cpp

 //===-- X86OptimizeLEAs.cpp - optimize usage of LEA instructions ----------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines the pass that performs some optimizations with LEA
 // instructions in order to improve code size.
-// Currently, it does one thing:
-// 1) Address calculations in load and store instructions are replaced by
+// Currently, it does two things:
+// 1) If there are two LEA instructions calculating addresses which only differ
+//    by displacement inside a basic block, one of them is removed.
+// 2) Address calculations in load and store instructions are replaced by
 //    existing LEA def registers where possible.
 //
 //===----------------------------------------------------------------------===//
 
 #include "X86.h"
 #include "X86InstrInfo.h"
 #include "X86Subtarget.h"
 #include "llvm/ADT/Statistic.h"

 #define DEBUG_TYPE "x86-optimize-LEAs"
 
 static cl::opt<bool>
     DisableX86LEAOpt("disable-x86-lea-opt", cl::Hidden,
                      cl::desc("X86: Disable LEA optimizations."),
                      cl::init(false));
 
 STATISTIC(NumSubstLEAs, "Number of LEA instruction substitutions");
+STATISTIC(NumRedundantLEAs, "Number of redundant LEA instructions removed");
 
 namespace {
 class OptimizeLEAPass : public MachineFunctionPass {
 public:
   OptimizeLEAPass() : MachineFunctionPass(ID) {}
 
   const char *getPassName() const override { return "X86 LEA Optimize"; }
 
private:
 
   /// \brief Returns true if two machine operand are identical and they are not
   /// physical registers.
   bool isIdenticalOp(const MachineOperand &MO1, const MachineOperand &MO2);
 
   /// \brief Returns true if the instruction is LEA.
   bool isLEA(const MachineInstr &MI);
 
+  /// \brief Returns true if the \p Last LEA instruction can be replaced by the
+  /// \p First. The difference between displacements of the addresses calculated
+  /// by these LEAs is returned in \p AddrDispShift. It'll be used for proper
+  /// replacement of the \p Last LEA's uses with the \p First's def register.
+  bool isReplaceable(const MachineInstr &First, const MachineInstr &Last,
+                     int64_t &AddrDispShift);
+
   /// \brief Returns true if two instructions have memory operands that only
   /// differ by displacement. The numbers of the first memory operands for both
   /// instructions are specified through \p N1 and \p N2. The address
   /// displacement is returned through AddrDispShift.
   bool isSimilarMemOp(const MachineInstr &MI1, unsigned N1,
                       const MachineInstr &MI2, unsigned N2,
                       int64_t &AddrDispShift);
 
   /// \brief Find all LEA instructions in the basic block. Also, assign position
   /// numbers to all instructions in the basic block to speed up calculation of
   /// distance between them.
   void findLEAs(const MachineBasicBlock &MBB,
                 SmallVectorImpl<MachineInstr *> &List);
 
   /// \brief Removes redundant address calculations.
   bool removeRedundantAddrCalc(const SmallVectorImpl<MachineInstr *> &List);
 
+  /// \brief Removes LEAs which calculate similar addresses.
+  bool removeRedundantLEAs(SmallVectorImpl<MachineInstr *> &List);
+
   DenseMap<const MachineInstr *, unsigned> InstrPos;
 
   MachineRegisterInfo *MRI;
   const X86InstrInfo *TII;
   const X86RegisterInfo *TRI;
 
   static char ID;
 };

 }
 
 bool OptimizeLEAPass::isLEA(const MachineInstr &MI) {
   unsigned Opcode = MI.getOpcode();
   return Opcode == X86::LEA16r || Opcode == X86::LEA32r ||
          Opcode == X86::LEA64r || Opcode == X86::LEA64_32r;
 }
 
+// Check that the Last LEA can be replaced by the First LEA. To be so,
+// these requirements must be met:
+// 1) Addresses calculated by LEAs differ only by displacement.
+// 2) Def registers of LEAs belong to the same class.
+// 3) All uses of the Last LEA def register are replaceable, thus the
+//    register is used only as address base.
+bool OptimizeLEAPass::isReplaceable(const MachineInstr &First,
+                                    const MachineInstr &Last,
+                                    int64_t &AddrDispShift) {
+  assert(isLEA(First) && isLEA(Last) &&
+         "The function works only with LEA instructions");
+
+  // Compare instructions' memory operands.
+  if (!isSimilarMemOp(Last, 1, First, 1, AddrDispShift))
+    return false;
+
+  // Make sure that LEA def registers belong to the same class. There may be
+  // instructions (like MOV8mr_NOREX) which allow a limited set of registers to
+  // be used as their operands, so we must be sure that replacing one LEA
+  // with another won't lead to putting a wrong register in the instruction.
+  if (MRI->getRegClass(First.getOperand(0).getReg()) !=
+      MRI->getRegClass(Last.getOperand(0).getReg()))
+    return false;
+
+  // Loop over all uses of the Last LEA to check that its def register is
+  // used only as address base for memory accesses. If so, it can be
+  // replaced, otherwise - no.
+  for (auto &MO : MRI->use_operands(Last.getOperand(0).getReg())) {
+    MachineInstr &MI = *MO.getParent();
+
+    // Get the number of the first memory operand.
+    const MCInstrDesc &Desc = MI.getDesc();
+    int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags, MI.getOpcode());
+
+    // If the use instruction has no memory operand - the LEA is not
+    // replaceable.
+    if (MemOpNo < 0)
+      return false;
+
+    MemOpNo += X86II::getOperandBias(Desc);
+
+    // If the address base of the use instruction is not the LEA def register -
+    // the LEA is not replaceable.
+    if (!isIdenticalOp(MI.getOperand(MemOpNo + X86::AddrBaseReg), MO))
+      return false;
+
+    // If the LEA def register is used as any other operand of the use
+    // instruction - the LEA is not replaceable.
+    for (unsigned i = 0; i < MI.getNumOperands(); i++)
+      if (i != (unsigned)(MemOpNo + X86::AddrBaseReg) &&
+          isIdenticalOp(MI.getOperand(i), MO))
+        return false;
+
+    // Check that the new address displacement will fit 4 bytes.
+    if (MI.getOperand(MemOpNo + X86::AddrDisp).isImm() &&
+        !isInt<32>(MI.getOperand(MemOpNo + X86::AddrDisp).getImm() +
+                   AddrDispShift))
+      return false;
+  }
+
+  return true;
+}
+
 // Check if MI1 and MI2 have memory operands which represent addresses that
 // differ only by displacement.
 bool OptimizeLEAPass::isSimilarMemOp(const MachineInstr &MI1, unsigned N1,
                                      const MachineInstr &MI2, unsigned N2,
                                      int64_t &AddrDispShift) {
   // Address base, scale, index and segment operands must be identical.
   static const int IdenticalOpNums[] = {X86::AddrBaseReg, X86::AddrScaleAmt,
                                         X86::AddrIndexReg, X86::AddrSegmentReg};
for (auto I = MBB->begin(), E = MBB->end(); I != E;) {
     DEBUG(dbgs() << "OptimizeLEAs: Replaced by: "; MI.dump(););
 
     Changed = true;
   }
 
   return Changed;
 }
 
+// Try to find similar LEAs in the list and replace one with another.
+bool
+OptimizeLEAPass::removeRedundantLEAs(SmallVectorImpl<MachineInstr *> &List) {
+  bool Changed = false;
+
+  // Loop over all LEA pairs.
+  auto I1 = List.begin();
+  while (I1 != List.end()) {
+    MachineInstr &First = **I1;
+    auto I2 = std::next(I1);
+    while (I2 != List.end()) {
+      MachineInstr &Last = **I2;
+      int64_t AddrDispShift;
+
+      // LEAs should be in occurence order in the list, so we can freely
+      // replace later LEAs with earlier ones.
+      assert(calcInstrDist(First, Last) > 0 &&
+             "LEAs must be in occurence order in the list");
+
+      // Check that the Last LEA instruction can be replaced by the First.
+      if (!isReplaceable(First, Last, AddrDispShift)) {
+        ++I2;
+        continue;
+      }
+
+      // Loop over all uses of the Last LEA and update their operands. Note that
+      // the correctness of this has already been checked in the isReplaceable
+      // function.
+      for (auto UI = MRI->use_begin(Last.getOperand(0).getReg()),
+                UE = MRI->use_end();
+           UI != UE;) {
+        MachineOperand &MO = *UI++;
+        MachineInstr &MI = *MO.getParent();
+
+        // Get the number of the first memory operand.
+        const MCInstrDesc &Desc = MI.getDesc();
+        int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags, MI.getOpcode()) +
+                      X86II::getOperandBias(Desc);
+
+        // Update address base.
+        MO.setReg(First.getOperand(0).getReg());
+
+        // Update address disp.
+        MachineOperand *Op = &MI.getOperand(MemOpNo + X86::AddrDisp);
+        if (Op->isImm())
+          Op->setImm(Op->getImm() + AddrDispShift);
+        else if (Op->isGlobal())
+          Op->setOffset(Op->getOffset() + AddrDispShift);
+        else
+          llvm_unreachable("Invalid address displacement operand");
+      }
+
+      // Since we can possibly extend register lifetime, clear kill flags.
+      MRI->clearKillFlags(First.getOperand(0).getReg());
+
+      ++NumRedundantLEAs;
+      DEBUG(dbgs() << "OptimizeLEAs: Remove redundant LEA: "; Last.dump(););
+
+      // By this moment, all of the Last LEA's uses must be replaced. So we can
+      // freely remove it.
+      assert(MRI->use_empty(Last.getOperand(0).getReg()) &&
+             "The LEA's def register must have no uses");
+      Last.eraseFromParent();
+
+      // Erase removed LEA from the list.
+      I2 = List.erase(I2);
+
+      Changed = true;
+    }
+    ++I1;
+  }
+
+  return Changed;
+}
+
 bool OptimizeLEAPass::runOnMachineFunction(MachineFunction &MF) {
   bool Changed = false;
 
   // Perform this optimization only if we care about code size.
   if (DisableX86LEAOpt || !MF.getFunction()->optForSize())
     return false;
 
   MRI = &MF.getRegInfo();
   TII = MF.getSubtarget<X86Subtarget>().getInstrInfo();
   TRI = MF.getSubtarget<X86Subtarget>().getRegisterInfo();
 
   // Process all basic blocks.
   for (auto &MBB : MF) {
     SmallVector<MachineInstr *, 16> LEAs;
     InstrPos.clear();
 
     // Find all LEA instructions in basic block.
     findLEAs(MBB, LEAs);
 
     // If current basic block has no LEAs, move on to the next one.
     if (LEAs.empty())
       continue;
 
+    // Remove redundant LEA instructions. The optimization may have a negative
+    // effect on performance, so do it only for -Oz.
+    if (MF.getFunction()->optForMinSize())
+      Changed |= removeRedundantLEAs(LEAs);
+
     // Remove redundant address calculations.
     Changed |= removeRedundantAddrCalc(LEAs);
   }
 
   return Changed;
 }

test/CodeGen/X86/lea-opt.ll

 
 ; CHECK:  movl ([[REG2]]), {{.*}}
 ; CHECK:  addl ([[REG3]]), {{.*}}
 ; CHECK:  movl ${{[1-4]+}}, ([[REG2]])
 ; CHECK:  movl ${{[1-4]+}}, ([[REG3]])
 ; CHECK:  movl ${{[1-4]+}}, ([[REG2]])
 ; CHECK:  movl ${{[1-4]+}}, ([[REG3]])
 }
+
+define void @test4(i64 %x) nounwind minsize {
+entry:
+  %a = getelementptr inbounds [65 x %struct.anon1], [65 x %struct.anon1]* @arr1, i64 0, i64 %x, i32 0
+  %tmp = load i32, i32* %a, align 4
+  %b = getelementptr inbounds [65 x %struct.anon1], [65 x %struct.anon1]* @arr1, i64 0, i64 %x, i32 1
+  %tmp1 = load i32, i32* %b, align 4
+  %sub = sub i32 %tmp, %tmp1
+  %c = getelementptr inbounds [65 x %struct.anon1], [65 x %struct.anon1]* @arr1, i64 0, i64 %x, i32 2
+  %tmp2 = load i32, i32* %c, align 4
+  %add = add nsw i32 %sub, %tmp2
+  switch i32 %add, label %sw.epilog [
+    i32 1, label %sw.bb.1
+    i32 2, label %sw.bb.2
+  ]
+
+sw.bb.1:                                          ; preds = %entry
+  store i32 111, i32* %b, align 4
+  store i32 222, i32* %c, align 4
+  br label %sw.epilog
+
+sw.bb.2:                                          ; preds = %entry
+  store i32 333, i32* %b, align 4
+  store i32 444, i32* %c, align 4
+  br label %sw.epilog
+
+sw.epilog:                                        ; preds = %sw.bb.2, %sw.bb.1, %entry
+  ret void
+; CHECK-LABEL: test4:
+; CHECK:  leaq arr1+4({{.*}}), [[REG2:%[a-z]+]]
+; CHECK:  movl -4([[REG2]]), {{.*}}
+; CHECK:  subl ([[REG2]]), {{.*}}
+; CHECK:  addl 4([[REG2]]), {{.*}}
+; CHECK:  movl ${{[1-4]+}}, ([[REG2]])
+; CHECK:  movl ${{[1-4]+}}, 4([[REG2]])
+; CHECK:  movl ${{[1-4]+}}, ([[REG2]])
+; CHECK:  movl ${{[1-4]+}}, 4([[REG2]])
+}