Subzero: Strength-reduce mul by certain constants.

src/IceTargetLoweringX8632.cpp

 //===- subzero/src/IceTargetLoweringX8632.cpp - x86-32 lowering -----------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the TargetLoweringX8632 class, which
@@ skipping 1269 matching lines @@
     // multiple of the required alignment at runtime.
     Variable *T = makeReg(IceType_i32);
     _mov(T, TotalSize);
     _add(T, Ctx->getConstantInt32(Alignment - 1));
     _and(T, Ctx->getConstantInt32(-Alignment));
     _sub(esp, T);
   }
   _mov(Dest, esp);
 }
 
+// Strength-reduce scalar integer multiplication by a constant (for
+// i32 or narrower) for certain constants.  The lea instruction can be
+// used to multiply by 3, 5, or 9, and the lsh instruction can be used
+// to multiply by powers of 2.  These can be combined such that
+// e.g. multiplying by 100 can be done as 2 lea-based multiplies by 5,
+// combined with left-shifting by 2.
+bool TargetX8632::optimizeScalarMul(Variable *Dest, Operand *Src0,
+                                    int32_t Src1) {
+  // Disable this optimization for Om1 and O0, just to keep things
+  // simple there.
+  if (Ctx->getFlags().getOptLevel() < Opt_1)
+    return false;
+  Variable *T = nullptr;
+  if (Src1 == -1) {
+    _mov(T, Src0);
+    _neg(T);
+    _mov(Dest, T);
+    return true;
+  }
+  if (Src1 == 1) {
+    _mov(T, Src0);
+    _mov(Dest, T);
+    return true;
+  }
+  if (Src1 <= 0)

[John, 2015/06/10 17:27:52]

Just throwing an idea... would it work to invert Src1 and then _inv(T) at the
end? Then this function would become something like

if (Src1 == 0) {
  _mov(T, Zero);
  _mov(Dest, Zero);
  return true;
}

const bool NegativeSrc1 = Src1 < 0;

if (NegativeSrc1) {
  Src1 = -Src1;
}

uint32_t Count9 = 0;
uint32_t Count5 = 0;
uint32_t Count3 = 0;
uint32_t Count2 = 0;
uint32_t CountOps = NegativeSrc1 ? 1 : 0;

while (Src1 > 1) {
   ...
}

const uint32_t MaxOpsForOptimizedMul = 5;
if (CountOps > MaxOpsForOptimizedMul) {
  return false;
}

_mov(T, Src0);
...
if (NegativeSrc1) {
  _inv(T);
}
_mov(Dest, T);
return true;

[Jim Stichnoth, 2015/06/12 17:31:47]

Done.  Though I suppress that when the constant is MININT.

+    return false;
+  uint32_t Count9 = 0;
+  uint32_t Count5 = 0;
+  uint32_t Count3 = 0;
+  uint32_t Count2 = 0;
+  uint32_t CountOps = 0;
+  while (Src1 > 1) {
+    if (Src1 % 9 == 0) {
+      ++CountOps;
+      ++Count9;
+      Src1 /= 9;
+    } else if (Src1 % 5 == 0) {
+      ++CountOps;
+      ++Count5;
+      Src1 /= 5;
+    } else if (Src1 % 3 == 0) {
+      ++CountOps;
+      ++Count3;
+      Src1 /= 3;
+    } else if (Src1 % 2 == 0) {
+      if (Count2 == 0)
+        ++CountOps;
+      ++Count2;
+      Src1 /= 2;
+    } else {
+      return false;
+    }
+  }
+  // Limit the number of lea/shl operations for a single multiply, to
+  // a somewhat arbitrary choice of 5.
+  const uint32_t MaxOpsForOptimizedMul = 5;

[jvoung (off chromium), 2015/06/10 18:12:27]

FWIW, some of the agner tables say mul r/i is about 3 microops for 32-bit
(sometimes better for 8-bit, sometimes worse for 64-bit), so 5 might be high?
I'm not sure how many ops LLVM/gcc will go up to.

Anyway, could tune more later.

[John, 2015/06/10 23:47:19]

This little command

echo "int v(int i) { return i * 25; }"|gcc -S -O99 -x c - -o-|less

showed me a couple of interesting things. It seems gcc will not go over 2
instructions (and maybe a neg at the end for negative numbers.)

[Jim Stichnoth, 2015/06/12 17:31:47]

OK.  I reduced the threshold to 3.

+  if (CountOps > MaxOpsForOptimizedMul)
+    return false;
+  _mov(T, Src0);
+  Constant *Zero = Ctx->getConstantZero(IceType_i32);
+  for (uint32_t i = 0; i < Count9; ++i) {
+    const uint16_t Shift = 3; // log2(9-1)
+    _lea(T, OperandX8632Mem::create(Func, IceType_void, T, Zero, T, Shift));
+    _set_dest_nonkillable();
+  }
+  for (uint32_t i = 0; i < Count5; ++i) {
+    const uint16_t Shift = 2; // log2(5-1)
+    _lea(T, OperandX8632Mem::create(Func, IceType_void, T, Zero, T, Shift));
+    _set_dest_nonkillable();
+  }
+  for (uint32_t i = 0; i < Count3; ++i) {
+    const uint16_t Shift = 1; // log2(3-1)
+    _lea(T, OperandX8632Mem::create(Func, IceType_void, T, Zero, T, Shift));
+    _set_dest_nonkillable();
+  }
+  if (Count2) {
+    _shl(T, Ctx->getConstantInt(Dest->getType(), Count2));
+  }
+  _mov(Dest, T);
+  return true;
+}
+
 void TargetX8632::lowerArithmetic(const InstArithmetic *Inst) {
   Variable *Dest = Inst->getDest();
   Operand *Src0 = legalize(Inst->getSrc(0));
   Operand *Src1 = legalize(Inst->getSrc(1));
   if (Inst->isCommutative()) {
     if (!llvm::isa<Variable>(Src0) && llvm::isa<Variable>(Src1))
       std::swap(Src0, Src1);
+    if (llvm::isa<Constant>(Src0) && !llvm::isa<Constant>(Src1))
+      std::swap(Src0, Src1);
   }
   if (Dest->getType() == IceType_i64) {
     Variable *DestLo = llvm::cast<Variable>(loOperand(Dest));
     Variable *DestHi = llvm::cast<Variable>(hiOperand(Dest));
     Operand *Src0Lo = loOperand(Src0);
     Operand *Src0Hi = hiOperand(Src0);
     Operand *Src1Lo = loOperand(Src1);
     Operand *Src1Hi = hiOperand(Src1);
     Variable *T_Lo = nullptr, *T_Hi = nullptr;
     switch (Inst->getOp()) {
@@ skipping 207 matching lines @@
       lowerCall(Call);
     } break;
     case InstArithmetic::Fadd:
     case InstArithmetic::Fsub:
     case InstArithmetic::Fmul:
     case InstArithmetic::Fdiv:
     case InstArithmetic::Frem:
       llvm_unreachable("FP instruction with i64 type");
       break;
     }
-  } else if (isVectorType(Dest->getType())) {
+    return;
+  }
+  if (isVectorType(Dest->getType())) {
     // TODO: Trap on integer divide and integer modulo by zero.
     // See: https://code.google.com/p/nativeclient/issues/detail?id=3899
     if (llvm::isa<OperandX8632Mem>(Src1))
       Src1 = legalizeToVar(Src1);
     switch (Inst->getOp()) {
     case InstArithmetic::_num:
       llvm_unreachable("Unknown arithmetic operator");
       break;
     case InstArithmetic::Add: {
       Variable *T = makeReg(Dest->getType());
@@ skipping 108 matching lines @@
     case InstArithmetic::Fdiv: {
       Variable *T = makeReg(Dest->getType());
       _movp(T, Src0);
       _divps(T, Src1);
       _movp(Dest, T);
     } break;
     case InstArithmetic::Frem:
       scalarizeArithmetic(Inst->getOp(), Dest, Src0, Src1);
       break;
     }
-  } else { // Dest->getType() is non-i64 scalar
+    return;
+  }
+  { // TODO(stichnot): Remove this level of {}.  (It's still there to
+    // make the diffs easier to read.)
     Variable *T_edx = nullptr;
     Variable *T = nullptr;
     switch (Inst->getOp()) {
     case InstArithmetic::_num:
       llvm_unreachable("Unknown arithmetic operator");
       break;
     case InstArithmetic::Add:
       _mov(T, Src0);
       _add(T, Src1);
       _mov(Dest, T);
@@ skipping 12 matching lines @@
       _mov(T, Src0);
       _xor(T, Src1);
       _mov(Dest, T);
       break;
     case InstArithmetic::Sub:
       _mov(T, Src0);
       _sub(T, Src1);
       _mov(Dest, T);
       break;
     case InstArithmetic::Mul:
-      // TODO: Optimize for llvm::isa<Constant>(Src1)
-      // TODO: Strength-reduce multiplications by a constant,
-      // particularly -1 and powers of 2.  Advanced: use lea to
-      // multiply by 3, 5, 9.
-      //
+      if (auto *C = llvm::dyn_cast<ConstantInteger32>(Src1)) {
+        if (optimizeScalarMul(Dest, Src0, C->getValue()))
+          return;
+      }
       // The 8-bit version of imul only allows the form "imul r/m8"
       // where T must be in eax.
       if (isByteSizedArithType(Dest->getType())) {
         _mov(T, Src0, RegX8632::Reg_eax);
         Src1 = legalize(Src1, Legal_Reg | Legal_Mem);
       } else {
         _mov(T, Src0);
       }
       _imul(T, Src1);
       _mov(Dest, T);
@@ skipping 32 matching lines @@
         _mov(Dest, T);
       } else {
         Constant *Zero = Ctx->getConstantZero(IceType_i32);
         _mov(T, Src0, RegX8632::Reg_eax);
         _mov(T_edx, Zero, RegX8632::Reg_edx);
         _div(T, Src1, T_edx);
         _mov(Dest, T);
       }
       break;
     case InstArithmetic::Sdiv:
+      // TODO(stichnot): Enable this after doing better performance
+      // and cross testing.
+      if (false && Ctx->getFlags().getOptLevel() >= Opt_1) {
+        // Optimize division by constant power of 2, but not for Om1
+        // or O0, just to keep things simple there.
+        if (auto *C = llvm::dyn_cast<ConstantInteger32>(Src1)) {
+          int32_t Divisor = C->getValue();
+          uint32_t UDivisor = static_cast<uint32_t>(Divisor);
+          if (Divisor > 0 && llvm::isPowerOf2_32(UDivisor)) {
+            uint32_t LogDiv = llvm::Log2_32(UDivisor);
+            Type Ty = Dest->getType();
+            // LLVM does the following for dest=src/(1<<log):
+            //   t=src
+            //   sar t,typewidth-1 // -1 if src is negative, 0 if not
+            //   shr t,typewidth-log
+            //   add t,src
+            //   sar t,log
+            //   dest=t
+            uint32_t TypeWidth = X86_CHAR_BIT * typeWidthInBytes(Ty);
+            _mov(T, Src0);
+            // If for some reason we are dividing by 1, just treat it
+            // like an assignment.
+            if (LogDiv > 0) {
+              // The initial sar is unnecessary when dividing by 2.
+              if (LogDiv > 1)
+                _sar(T, Ctx->getConstantInt(Ty, TypeWidth - 1));
+              _shr(T, Ctx->getConstantInt(Ty, TypeWidth - LogDiv));
+              _add(T, Src0);
+              _sar(T, Ctx->getConstantInt(Ty, LogDiv));
+            }
+            _mov(Dest, T);
+            return;
+          }
+        }
+      }
       Src1 = legalize(Src1, Legal_Reg | Legal_Mem);
       if (isByteSizedArithType(Dest->getType())) {
         _mov(T, Src0, RegX8632::Reg_eax);
         _cbwdq(T, T);
         _idiv(T, Src1, T);
         _mov(Dest, T);
       } else {
         T_edx = makeReg(IceType_i32, RegX8632::Reg_edx);
         _mov(T, Src0, RegX8632::Reg_eax);
         _cbwdq(T_edx, T);
@@ skipping 12 matching lines @@
         _mov(Dest, T_ah);
       } else {
         Constant *Zero = Ctx->getConstantZero(IceType_i32);
         _mov(T_edx, Zero, RegX8632::Reg_edx);
         _mov(T, Src0, RegX8632::Reg_eax);
         _div(T_edx, Src1, T);
         _mov(Dest, T_edx);
       }
       break;
     case InstArithmetic::Srem:
+      // TODO(stichnot): Enable this after doing better performance
+      // and cross testing.
+      if (false && Ctx->getFlags().getOptLevel() >= Opt_1) {
+        // Optimize mod by constant power of 2, but not for Om1 or O0,
+        // just to keep things simple there.
+        if (auto *C = llvm::dyn_cast<ConstantInteger32>(Src1)) {
+          int32_t Divisor = C->getValue();
+          uint32_t UDivisor = static_cast<uint32_t>(Divisor);
+          if (Divisor > 0 && llvm::isPowerOf2_32(UDivisor)) {
+            uint32_t LogDiv = llvm::Log2_32(UDivisor);
+            Type Ty = Dest->getType();
+            // LLVM does the following for dest=src%(1<<log):
+            //   t=src
+            //   sar t,typewidth-1 // -1 if src is negative, 0 if not
+            //   shr t,typewidth-log
+            //   add t,src
+            //   and t, -(1<<log)
+            //   sub t,src
+            //   neg t
+            //   dest=t
+            uint32_t TypeWidth = X86_CHAR_BIT * typeWidthInBytes(Ty);
+            // If for some reason we are dividing by 1, just assign 0.
+            if (LogDiv == 0) {
+              _mov(Dest, Ctx->getConstantZero(Ty));
+              return;
+            }
+            _mov(T, Src0);
+            // The initial sar is unnecessary when dividing by 2.
+            if (LogDiv > 1)
+              _sar(T, Ctx->getConstantInt(Ty, TypeWidth - 1));
+            _shr(T, Ctx->getConstantInt(Ty, TypeWidth - LogDiv));
+            _add(T, Src0);
+            _and(T, Ctx->getConstantInt(Ty, -(1 << LogDiv)));
+            _sub(T, Src0);
+            _neg(T);
+            _mov(Dest, T);
+            return;
+          }
+        }
+      }
       Src1 = legalize(Src1, Legal_Reg | Legal_Mem);
       if (isByteSizedArithType(Dest->getType())) {
         Variable *T_ah = makeReg(IceType_i8, RegX8632::Reg_ah);
         _mov(T, Src0, RegX8632::Reg_eax);
         _cbwdq(T, T);
         Context.insert(InstFakeDef::create(Func, T_ah));
         _idiv(T_ah, Src1, T);
         _mov(Dest, T_ah);
       } else {
         T_edx = makeReg(IceType_i32, RegX8632::Reg_edx);
@@ skipping 25 matching lines @@
       break;
     case InstArithmetic::Frem: {
       const SizeT MaxSrcs = 2;
       Type Ty = Dest->getType();
       InstCall *Call =
           makeHelperCall(isFloat32Asserting32Or64(Ty) ? H_frem_f32 : H_frem_f64,
                          Dest, MaxSrcs);
       Call->addArg(Src0);
       Call->addArg(Src1);
       return lowerCall(Call);
-    } break;
+    }
     }
   }
 }
 
 void TargetX8632::lowerAssign(const InstAssign *Inst) {
   Variable *Dest = Inst->getDest();
   Operand *Src0 = Inst->getSrc(0);
   assert(Dest->getType() == Src0->getType());
   if (Dest->getType() == IceType_i64) {
     Src0 = legalize(Src0);
@@ skipping 3180 matching lines @@
   case FT_Asm:
   case FT_Iasm: {
     OstreamLocker L(Ctx);
     emitConstantPool<PoolTypeConverter<float>>(Ctx);
     emitConstantPool<PoolTypeConverter<double>>(Ctx);
   } break;
   }
 }
 
 } // end of namespace Ice