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

76

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

201

differ?

228

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.

246

Could you add a comment over that loop?

398

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

415

else llvm_unreachable or assert?

426

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

76

Done.

201

Fixed.

228

Removed.

246

Done.

398

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

415

Done.

426

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"
 #include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetInstrInfo.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "x86-optimize-LEAs"
 
 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.
+  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.
   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 adresses.
+  bool removeRedundantLEAs(SmallVectorImpl<MachineInstr *> &List);
+
   MachineRegisterInfo *MRI;
   const X86InstrInfo *TII;
   const X86RegisterInfo *TRI;
 
   static char ID;
 };
 char OptimizeLEAPass::ID = 0;
 }

 }
 
 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 deffer 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.
+  assert(First.getOperand(0).isDef() && First.getOperand(0).isReg() &&
+         Last.getOperand(0).isDef() && Last.getOperand(0).isReg() &&
+         "The first LEA operand must be def register");
+  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 use instruction has no memory operand - LEA is not replaceable.
+    if (MemOpNo < 0)
+      return false;
+
+    MemOpNo += X86II::getOperandBias(Desc);
+
+    // If LEA def register is used not as address base or not only so - LEA
+    // is not replaceable.
+    if (!isIdenticalOp(MI.getOperand(MemOpNo + X86::AddrBaseReg), MO))
+      return false;
+    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);
+      }
+
+      // 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()));
+      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 (!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;
 
     // 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]])
+}