[InstCombine] Reorder (shl (add/sub (shl x, C0), y), C1) -> (add/sub (shl x, C0 + C1), (shl y, C1))

[goldstein.w.n]

Summary

This is just expanding the existing pattern that exists for AND/XOR/OR
and gets a bit more parallelism in from the instruction sequence.

Alive2:
Add - https://alive2.llvm.org/ce/z/dSmPkV
Sub1 - https://alive2.llvm.org/ce/z/6rpi5V
Sub2 - https://alive2.llvm.org/ce/z/UfYeUd

[spatel]

Subtract should be handled as well as add?

[goldstein.w.n]

In D141875#4058818, @spatel wrote:

Subtract should be handled as well as add?

Yes, I'll update:
https://alive2.llvm.org/ce/z/4TVEIg

[goldstein.w.n]

Add support for sub + update commit message

[goldstein.w.n]

In D141875#4058818, @spatel wrote:

Subtract should be handled as well as add?

Done.

[goldstein.w.n]

ping.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

324–325

or add -> or add/sub

325–330

This function name is too specific now since we are not limited to logic ops. Not sure if there's a compact description for the set of possibilities. If not, just go with foldShiftOfShiftedBinOp().

327

typo (it was already there but disguised) - "a a"

359–363

This was strangely matched, so I reduced it:
c2ab7e2abd834d4ef7b0f277

It shouldn't change anything functionally here, but you may need to update/rebase to patch cleanly.

368

"Reorder" doesn't seem like the right description. I'd use the more literal "FirstShiftIsOp1" or something like that.

[goldstein.w.n]

Rebase, change func name, change reorder name, fix comments

[spatel]

LGTM

[goldstein.w.n]

Either this or D140850 cause the failure: https://lab.llvm.org/buildbot/#/builders/183/builds/10447

Going to revert while I look into it.

[spatel]

In D141875#4087595, @goldstein.w.n wrote:

Either this or D140850 cause the failure: https://lab.llvm.org/buildbot/#/builders/183/builds/10447

Going to revert while I look into it.

If that was the only builder that failed, I'd try again. It passed on the next try (before you reverted!):
https://lab.llvm.org/buildbot/#/builders/183
Sometimes buildbots just fail inexplicably. :)

[goldstein.w.n]

In D141875#4087655, @spatel wrote:

In D141875#4087595, @goldstein.w.n wrote:

Either this or D140850 cause the failure: https://lab.llvm.org/buildbot/#/builders/183/builds/10447

Going to revert while I look into it.

If that was the only builder that failed, I'd try again. It passed on the next try (before you reverted!):
https://lab.llvm.org/buildbot/#/builders/183
Sometimes buildbots just fail inexplicably. :)

Yeah, also unable to reproduce locally. Coming to conclusion its unrelated, cest la vie.
For recommit should I just apply re-apply the patches and prefix with "Recommit"/explain it was a false positive?

Also thanks for taking a look :)

[spatel]

In D141875#4087663, @goldstein.w.n wrote:

Yeah, also unable to reproduce locally. Coming to conclusion its unrelated, cest la vie.
For recommit should I just apply re-apply the patches and prefix with "Recommit"/explain it was a false positive?

That should be fine - I usually just append a "(2nd try)" on the patch title, add a short explanation statement, then the original commit message.

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

dropRedundantMaskingOfLeftShiftInput(BinaryOperator *OuterShift,
   auto *NewShift = BinaryOperator::Create(OuterShift->getOpcode(), X,
                                           OuterShift->getOperand(1));
   if (!NeedMask)
     return NewShift;
 
   Builder.Insert(NewShift);
   return BinaryOperator::Create(Instruction::And, NewShift, NewMask);
 }
 
-/// If we have a shift-by-constant of a bitwise logic op that itself has a
-/// shift-by-constant operand with identical opcode, we may be able to convert
-/// that into 2 independent shifts followed by the logic op. This eliminates a
-/// a use of an intermediate value (reduces dependency chain).
-static Instruction *foldShiftOfShiftedLogic(BinaryOperator &I,
+/// If we have a shift-by-constant of a bin op (bitwise logic op or add/sub w/
+/// shl) that itself has a shift-by-constant operand with identical opcode, we
+/// may be able to convert that into 2 independent shifts followed by the logic
+/// op. This eliminates a use of an intermediate value (reduces dependency
+/// chain).
+static Instruction *foldShiftOfShiftedBinOp(BinaryOperator &I,
                                             InstCombiner::BuilderTy &Builder) {
   assert(I.isShift() && "Expected a shift as input");
-  auto *LogicInst = dyn_cast<BinaryOperator>(I.getOperand(0));
-  if (!LogicInst || !LogicInst->isBitwiseLogicOp() || !LogicInst->hasOneUse())
+  auto *BinInst = dyn_cast<BinaryOperator>(I.getOperand(0));
+  if (!BinInst ||
+      (!BinInst->isBitwiseLogicOp() &&
+       BinInst->getOpcode() != Instruction::Add &&
+       BinInst->getOpcode() != Instruction::Sub) ||
+      !BinInst->hasOneUse())
     return nullptr;
 
   Constant *C0, *C1;
   if (!match(I.getOperand(1), m_Constant(C1)))
     return nullptr;
 
   Instruction::BinaryOps ShiftOpcode = I.getOpcode();
+  // Transform for add/sub only works with shl.
+  if ((BinInst->getOpcode() == Instruction::Add ||
+       BinInst->getOpcode() == Instruction::Sub) &&
+      ShiftOpcode != Instruction::Shl)
+    return nullptr;
+
   Type *Ty = I.getType();
 
   // Find a matching one-use shift by constant. The fold is not valid if the sum
   // of the shift values equals or exceeds bitwidth.
   // TODO: Remove the one-use check if the other logic operand (Y) is constant.
   Value *X, *Y;
   auto matchFirstShift = [&](Value *V) {
     APInt Threshold(Ty->getScalarSizeInBits(), Ty->getScalarSizeInBits());
     return match(V,
                  m_OneUse(m_BinOp(ShiftOpcode, m_Value(X), m_Constant(C0)))) &&
            match(ConstantExpr::getAdd(C0, C1),
                  m_SpecificInt_ICMP(ICmpInst::ICMP_ULT, Threshold));
   };
 
-  // Logic ops are commutative, so check each operand for a match.
-  if (matchFirstShift(LogicInst->getOperand(0)))
-    Y = LogicInst->getOperand(1);
-  else if (matchFirstShift(LogicInst->getOperand(1)))
-    Y = LogicInst->getOperand(0);
-  else
+  // Logic ops and Add are commutative, so check each operand for a match. Sub
+  // is not so we cannot reoder if we match operand(1) and need to keep the
+  // operands in their original positions.
+  bool FirstShiftIsOp1 = false;
+  if (matchFirstShift(BinInst->getOperand(0)))
+    Y = BinInst->getOperand(1);
+  else if (matchFirstShift(BinInst->getOperand(1))) {
+    Y = BinInst->getOperand(0);
+    FirstShiftIsOp1 = BinInst->getOpcode() == Instruction::Sub;
+  } else
     return nullptr;
 
-  // shift (logic (shift X, C0), Y), C1 -> logic (shift X, C0+C1), (shift Y, C1)
+  // shift (binop (shift X, C0), Y), C1 -> binop (shift X, C0+C1), (shift Y, C1)
   Constant *ShiftSumC = ConstantExpr::getAdd(C0, C1);
   Value *NewShift1 = Builder.CreateBinOp(ShiftOpcode, X, ShiftSumC);
   Value *NewShift2 = Builder.CreateBinOp(ShiftOpcode, Y, C1);
-  return BinaryOperator::Create(LogicInst->getOpcode(), NewShift1, NewShift2);
+  Value *Op1 = FirstShiftIsOp1 ? NewShift2 : NewShift1;
+  Value *Op2 = FirstShiftIsOp1 ? NewShift1 : NewShift2;
+  return BinaryOperator::Create(BinInst->getOpcode(), Op1, Op2);
 }
 
 Instruction *InstCombinerImpl::commonShiftTransforms(BinaryOperator &I) {
   if (Instruction *Phi = foldBinopWithPhiOperands(I))
     return Phi;
 
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   assert(Op0->getType() == Op1->getType());
if (Op1->hasOneUse() && match(Op1, m_SRem(m_Value(A), m_Constant(C))) &&
       match(C, m_Power2())) {
     // FIXME: Should this get moved into SimplifyDemandedBits by saying we don't
     // demand the sign bit (and many others) here??
     Constant *Mask = ConstantExpr::getSub(C, ConstantInt::get(Ty, 1));
     Value *Rem = Builder.CreateAnd(A, Mask, Op1->getName());
     return replaceOperand(I, 1, Rem);
   }
 
-  if (Instruction *Logic = foldShiftOfShiftedLogic(I, Builder))
+  if (Instruction *Logic = foldShiftOfShiftedBinOp(I, Builder))
     return Logic;
 
   return nullptr;
 }
 
 /// Return true if we can simplify two logical (either left or right) shifts
 /// that have constant shift amounts: OuterShift (InnerShift X, C1), C2.
 static bool canEvaluateShiftedShift(unsigned OuterShAmt, bool IsOuterShl,

llvm/test/Transforms/InstCombine/shift-logic.ll

 ;
   %2 = mul nsw i64 %0, 52
   %3 = lshr i64 %2, 2
   ret i64 %3
 }
 
 define i8 @shl_add(i8 %x, i8 %y) {
 ; CHECK-LABEL: @shl_add(
-; CHECK-NEXT:    [[SH0:%.*]] = shl i8 [[X:%.*]], 3
-; CHECK-NEXT:    [[R:%.*]] = add i8 [[SH0]], [[Y:%.*]]
-; CHECK-NEXT:    [[SH1:%.*]] = shl i8 [[R]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 [[X:%.*]], 5
+; CHECK-NEXT:    [[TMP2:%.*]] = shl i8 [[Y:%.*]], 2
+; CHECK-NEXT:    [[SH1:%.*]] = add i8 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i8 [[SH1]]
 ;
   %sh0 = shl i8 %x, 3
   %r = add i8 %sh0, %y
   %sh1 = shl i8 %r, 2
   ret i8 %sh1
 }
 
 define <2 x i8> @shl_add_nonuniform(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @shl_add_nonuniform(
-; CHECK-NEXT:    [[SH0:%.*]] = shl <2 x i8> [[X:%.*]], <i8 3, i8 4>
-; CHECK-NEXT:    [[R:%.*]] = add <2 x i8> [[SH0]], [[Y:%.*]]
-; CHECK-NEXT:    [[SH1:%.*]] = shl <2 x i8> [[R]], <i8 2, i8 0>
+; CHECK-NEXT:    [[TMP1:%.*]] = shl <2 x i8> [[X:%.*]], <i8 5, i8 4>
+; CHECK-NEXT:    [[TMP2:%.*]] = shl <2 x i8> [[Y:%.*]], <i8 2, i8 0>
+; CHECK-NEXT:    [[SH1:%.*]] = add <2 x i8> [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret <2 x i8> [[SH1]]
 ;
   %sh0 = shl <2 x i8> %x, <i8 3, i8 4>
   %r = add <2 x i8> %sh0, %y
   %sh1 = shl <2 x i8> %r, <i8 2, i8 0>
   ret <2 x i8> %sh1
 }
 
 
 define <2 x i64> @shl_add_undef(<2 x i64> %x, <2 x i64> %py) {
 ; CHECK-LABEL: @shl_add_undef(
 ; CHECK-NEXT:    [[Y:%.*]] = srem <2 x i64> [[PY:%.*]], <i64 42, i64 42>
-; CHECK-NEXT:    [[SH0:%.*]] = shl <2 x i64> [[X:%.*]], <i64 5, i64 undef>
-; CHECK-NEXT:    [[R:%.*]] = add <2 x i64> [[Y]], [[SH0]]
-; CHECK-NEXT:    [[SH1:%.*]] = shl <2 x i64> [[R]], <i64 7, i64 undef>
+; CHECK-NEXT:    [[TMP1:%.*]] = shl <2 x i64> [[X:%.*]], <i64 12, i64 undef>
+; CHECK-NEXT:    [[TMP2:%.*]] = shl <2 x i64> [[Y]], <i64 7, i64 undef>
+; CHECK-NEXT:    [[SH1:%.*]] = add <2 x i64> [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret <2 x i64> [[SH1]]
 ;
   %y = srem <2 x i64> %py, <i64 42, i64 42> ; thwart complexity-based canonicalization
   %sh0 = shl <2 x i64> %x, <i64 5, i64 undef>
   %r = add <2 x i64> %y, %sh0
   %sh1 = shl <2 x i64> %r, <i64 7, i64 undef>
   ret <2 x i64> %sh1
 }
;
   %sh0 = lshr <2 x i64> %x, <i64 5, i64 undef>
   %r = add <2 x i64> %y, %sh0
   %sh1 = lshr <2 x i64> %r, <i64 7, i64 undef>
   ret <2 x i64> %sh1
 }
 
 define i8 @shl_sub(i8 %x, i8 %y) {
 ; CHECK-LABEL: @shl_sub(
-; CHECK-NEXT:    [[SH0:%.*]] = shl i8 [[X:%.*]], 3
-; CHECK-NEXT:    [[R:%.*]] = sub i8 [[SH0]], [[Y:%.*]]
-; CHECK-NEXT:    [[SH1:%.*]] = shl i8 [[R]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 [[X:%.*]], 5
+; CHECK-NEXT:    [[TMP2:%.*]] = shl i8 [[Y:%.*]], 2
+; CHECK-NEXT:    [[SH1:%.*]] = sub i8 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i8 [[SH1]]
 ;
   %sh0 = shl i8 %x, 3
   %r = sub i8 %sh0, %y
   %sh1 = shl i8 %r, 2
   ret i8 %sh1
 }
 
 ; Make sure we don't commute operands for sub
 define i8 @shl_sub_no_commute(i8 %x, i8 %y) {
 ; CHECK-LABEL: @shl_sub_no_commute(
-; CHECK-NEXT:    [[SH0:%.*]] = shl i8 [[Y:%.*]], 3
-; CHECK-NEXT:    [[R:%.*]] = sub i8 [[X:%.*]], [[SH0]]
-; CHECK-NEXT:    [[SH1:%.*]] = shl i8 [[R]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 [[Y:%.*]], 5
+; CHECK-NEXT:    [[TMP2:%.*]] = shl i8 [[X:%.*]], 2
+; CHECK-NEXT:    [[SH1:%.*]] = sub i8 [[TMP2]], [[TMP1]]
 ; CHECK-NEXT:    ret i8 [[SH1]]
 ;
   %sh0 = shl i8 %y, 3
   %r = sub i8 %x, %sh0
   %sh1 = shl i8 %r, 2
   ret i8 %sh1
 }
 
 define <2 x i8> @shl_sub_nonuniform(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @shl_sub_nonuniform(
-; CHECK-NEXT:    [[SH0:%.*]] = shl <2 x i8> [[X:%.*]], <i8 3, i8 4>
-; CHECK-NEXT:    [[R:%.*]] = sub <2 x i8> [[SH0]], [[Y:%.*]]
-; CHECK-NEXT:    [[SH1:%.*]] = shl <2 x i8> [[R]], <i8 2, i8 0>
+; CHECK-NEXT:    [[TMP1:%.*]] = shl <2 x i8> [[X:%.*]], <i8 5, i8 4>
+; CHECK-NEXT:    [[TMP2:%.*]] = shl <2 x i8> [[Y:%.*]], <i8 2, i8 0>
+; CHECK-NEXT:    [[SH1:%.*]] = sub <2 x i8> [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret <2 x i8> [[SH1]]
 ;
   %sh0 = shl <2 x i8> %x, <i8 3, i8 4>
   %r = sub <2 x i8> %sh0, %y
   %sh1 = shl <2 x i8> %r, <i8 2, i8 0>
   ret <2 x i8> %sh1
 }
 
 
 define <2 x i64> @shl_sub_undef(<2 x i64> %x, <2 x i64> %py) {
 ; CHECK-LABEL: @shl_sub_undef(
 ; CHECK-NEXT:    [[Y:%.*]] = srem <2 x i64> [[PY:%.*]], <i64 42, i64 42>
-; CHECK-NEXT:    [[SH0:%.*]] = shl <2 x i64> [[X:%.*]], <i64 5, i64 undef>
-; CHECK-NEXT:    [[R:%.*]] = sub <2 x i64> [[Y]], [[SH0]]
-; CHECK-NEXT:    [[SH1:%.*]] = shl <2 x i64> [[R]], <i64 7, i64 undef>
+; CHECK-NEXT:    [[TMP1:%.*]] = shl <2 x i64> [[X:%.*]], <i64 12, i64 undef>
+; CHECK-NEXT:    [[TMP2:%.*]] = shl <2 x i64> [[Y]], <i64 7, i64 undef>
+; CHECK-NEXT:    [[SH1:%.*]] = sub <2 x i64> [[TMP2]], [[TMP1]]
 ; CHECK-NEXT:    ret <2 x i64> [[SH1]]
 ;
   %y = srem <2 x i64> %py, <i64 42, i64 42> ; thwart complexity-based canonicalization
   %sh0 = shl <2 x i64> %x, <i64 5, i64 undef>
   %r = sub <2 x i64> %y, %sh0
   %sh1 = shl <2 x i64> %r, <i64 7, i64 undef>
   ret <2 x i64> %sh1
 }