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

75

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

195

differ?

222

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.

240

Could you add a comment over that loop?

392

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

409

else llvm_unreachable or assert?

420

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

75

Done.

195

Fixed.

222

Removed.

240

Done.

392

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

409

Done.

420

Done.

[qcolombet]

LGTM.

lib/Target/X86/X86.h

 /// with NOOPs. This will prevent a stall when returning on the Atom.
 FunctionPass *createX86PadShortFunctions();
 /// createX86FixupLEAs - 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 Atom processors.
 FunctionPass *createX86FixupLEAs();
 
-/// createX86OptimizeLEAs() - Return a pass that removes redundant
-/// address recalculations.
+/// createX86OptimizeLEAs() - Return a pass that removes redundant LEA
+/// instructions and redundant address recalculations.
 FunctionPass *createX86OptimizeLEAs();
 
 /// createX86CallFrameOptimization - Return a pass that optimizes
 /// the code-size of x86 call sequences. This is done by replacing
 /// esp-relative movs with pushes.
 FunctionPass *createX86CallFrameOptimization();
 
 /// createX86WinEHStatePass - Return an IR pass that inserts EH registration

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 'Last' LEA instruction can be replaced by '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 N1 and 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 'Last' LEA can be replaced by '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 '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 '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 'Last' LEA instruction can be replaced by 'First'.
+      if (!isReplaceable(First, Last, AddrDispShift)) {
+        ++I2;
+        continue;
+      }
+
+      // Loop over all uses of 'Last' LEA and update their operands. Note that
+      // the correctness of this has already been checked in 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 'Last' LEA 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;
   bool OptSize = MF.getFunction()->optForSize();
   bool MinSize = MF.getFunction()->optForMinSize();
 
   // Perform this optimization only if we care about code size.
   if (!OptSize && !MinSize)
     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 (MinSize)
+      Changed |= removeRedundantLEAs(LEAs);
+
     // Remove redundant address calculations.
     Changed |= removeRedundantAddrCalc(LEAs);
   }
 
   return Changed;
 }

test/CodeGen/X86/lea-opt.ll

 ; CHECK:  subl ([[REG2]]), {{.*}}
 ; CHECK:  leaq arr+8(,[[REG1]],4), [[REG3:%[a-z]+]]
 ; 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 @test2(i64 %x) nounwind minsize {
+entry:
+  %a = getelementptr inbounds [65 x %struct.anon], [65 x %struct.anon]* @arr, i64 0, i64 %x, i32 0
+  %0 = load i32, i32* %a, align 4
+  %b = getelementptr inbounds [65 x %struct.anon], [65 x %struct.anon]* @arr, i64 0, i64 %x, i32 1
+  %1 = load i32, i32* %b, align 4
+  %sub = sub i32 %0, %1
+  %c = getelementptr inbounds [65 x %struct.anon], [65 x %struct.anon]* @arr, i64 0, i64 %x, i32 2
+  %2 = load i32, i32* %c, align 4
+  %add = add nsw i32 %sub, %2
+  switch i32 %add, label %sw.epilog [
+    i32 1, label %sw.bb.1
+    i32 2, label %sw.bb.2
+  ]
+
+sw.bb.1:
+  store i32 111, i32* %b, align 4
+  store i32 222, i32* %c, align 4
+  br label %sw.epilog
+
+sw.bb.2:
+  store i32 333, i32* %b, align 4
+  store i32 444, i32* %c, align 4
+  br label %sw.epilog
+
+sw.epilog:
+  ret void
+; CHECK-LABEL: test2:
+; CHECK:  leaq arr+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]])
+}