[InstCombine] Support pulling left shifts through a subtract with constant LHS

[craig.topper]

Summary

We already support pulling through an add with constant RHS. We can do the same for subtract.

[craig.topper]

Use Builder.CreateShl since we know this is a left shift.

[efriedma]

For reference, http://rise4fun.com/Alive/8l5 .

This transform throws nsw/nuw flags; can we preserve them in some situations?

lib/Transforms/InstCombine/InstCombineShifts.cpp

525 ↗

(On Diff #110137)

Maybe add a comment writing out the transform in mathematical terms? (e.g. "2 * (A - B)" -> "2 * A - 2 * B").

test/Transforms/InstCombine/sub.ll

1082 ↗

(On Diff #110137)

This could use a couple more tests, to specifically show the transform this patch adds.

[craig.topper]

Add a simpler test case and a more mathematical comment.

Not sure how to preserve NSW/NUW without calling computeKnownBits. Any ideas?

[efriedma]

LGTM, with one small question.

lib/Transforms/InstCombine/InstCombineShifts.cpp

518 ↗

(On Diff #110256)

It looks like this can match a vector? If it can, please add a vector testcase.

[craig.topper]

Good catch. I'll add a vector test.

llvm/trunk/lib/Transforms/InstCombine/InstCombineShifts.cpp

if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0)) {
           Value *NewShift =
             Builder.CreateBinOp(I.getOpcode(), Op0BO->getOperand(0), Op1);
           NewShift->takeName(Op0BO);
 
           return BinaryOperator::Create(Op0BO->getOpcode(), NewShift,
                                         NewRHS);
         }
       }
+
+      // If the operand is a subtract with a constant LHS, and the shift
+      // is the only use, we can pull it out of the shift.
+      // This folds (shl (sub C1, X), C2) -> (sub (C1 << C2), (shl X, C2))
+      if (isLeftShift && Op0BO->getOpcode() == Instruction::Sub &&
+          match(Op0BO->getOperand(0), m_APInt(Op0C))) {
+        Constant *NewRHS = ConstantExpr::get(I.getOpcode(),
+                                   cast<Constant>(Op0BO->getOperand(0)), Op1);
+
+        Value *NewShift = Builder.CreateShl(Op0BO->getOperand(1), Op1);
+        NewShift->takeName(Op0BO);
+
+        return BinaryOperator::CreateSub(NewRHS, NewShift);
+      }
     }
   }
 
   return nullptr;
 }
 
 Instruction *InstCombiner::visitShl(BinaryOperator &I) {
   if (Value *V = SimplifyVectorOp(I))

llvm/trunk/test/Transforms/InstCombine/sub.ll

; gep2 has a non-constant index and more than one uses. Shouldn't duplicate the arithmetic.
   %gep1 = getelementptr inbounds [100 x [100 x i8]], [100 x [100 x i8]]* %foo, i64 0, i64 42, i64 0
   %gep2 = getelementptr inbounds [100 x [100 x i8]], [100 x [100 x i8]]* %foo, i64 0, i64 %j, i64 %i
   %cast1 = ptrtoint i8* %gep1 to i64
   %cast2 = ptrtoint i8* %gep2 to i64
   %sub = sub i64 %cast1, %cast2
   store i8* %gep2, i8** @dummy_global2
   ret i64 %sub
 }
+
+define i32 @test62(i32 %A) {
+; CHECK-LABEL: @test62(
+; CHECK-NEXT:    [[B:%.*]] = shl i32 [[A:%.*]], 1
+; CHECK-NEXT:    [[C:%.*]] = sub i32 2, [[B]]
+; CHECK-NEXT:    ret i32 [[C]]
+;
+  %B = sub i32 1, %A
+  %C = shl i32 %B, 1
+  ret i32 %C
+}
+
+define <2 x i32> @test62vec(<2 x i32> %A) {
+; CHECK-LABEL: @test62vec(
+; CHECK-NEXT:    [[B:%.*]] = shl <2 x i32> [[A:%.*]], <i32 1, i32 1>
+; CHECK-NEXT:    [[C:%.*]] = sub <2 x i32> <i32 2, i32 2>, [[B]]
+; CHECK-NEXT:    ret <2 x i32> [[C]]
+;
+  %B = sub <2 x i32> <i32 1, i32 1>, %A
+  %C = shl <2 x i32> %B, <i32 1, i32 1>
+  ret <2 x i32> %C
+}
+
+define i32 @test63(i32 %A) {
+; CHECK-LABEL: @test63(
+; CHECK-NEXT:    [[B:%.*]] = shl i32 [[A:%.*]], 1
+; CHECK-NEXT:    ret i32 [[B]]
+;
+  %B = sub i32 1, %A
+  %C = shl i32 %B, 1
+  %D = sub i32 2, %C
+  ret i32 %D
+}
+
+define <2 x i32> @test63vec(<2 x i32> %A) {
+; CHECK-LABEL: @test63vec(
+; CHECK-NEXT:    [[B:%.*]] = shl <2 x i32> [[A:%.*]], <i32 1, i32 1>
+; CHECK-NEXT:    ret <2 x i32> [[B]]
+;
+  %B = sub <2 x i32> <i32 1, i32 1>, %A
+  %C = shl <2 x i32> %B, <i32 1, i32 1>
+  %D = sub <2 x i32> <i32 2, i32 2>, %C
+  ret <2 x i32> %D
+}