[Reassociate] Teach ConvertShiftToMul to preserve nsw flag if the shift amount is not bitwidth - 1.

[craig.topper]

Summary

Multiply and shl have different signed overflow behavior in
some cases. But it looks like we should be ok as long as the
shift amount is less than bitwidth - 1.

Alive2: http://volta.cs.utah.edu:8080/z/MM4WZP

[lebedev.ri]

LG

[lebedev.ri]

Grepping a bit, there's this:

const SCEV *ScalarEvolution::createSCEV(Value *V) {
<...>

    case Instruction::Shl:
      // Turn shift left of a constant amount into a multiply.
      if (ConstantInt *SA = dyn_cast<ConstantInt>(BO->RHS)) {
        uint32_t BitWidth = cast<IntegerType>(SA->getType())->getBitWidth();

        // If the shift count is not less than the bitwidth, the result of
        // the shift is undefined. Don't try to analyze it, because the
        // resolution chosen here may differ from the resolution chosen in
        // other parts of the compiler.
        if (SA->getValue().uge(BitWidth))
          break;

        // It is currently not resolved how to interpret NSW for left
        // shift by BitWidth - 1, so we avoid applying flags in that
        // case. Remove this check (or this comment) once the situation
        // is resolved. See
        // http://lists.llvm.org/pipermail/llvm-dev/2015-April/084195.html
        // and http://reviews.llvm.org/D8890 .
        auto Flags = SCEV::FlagAnyWrap;
        if (BO->Op && SA->getValue().ult(BitWidth - 1))
          Flags = getNoWrapFlagsFromUB(BO->Op);

        Constant *X = ConstantInt::get(
            getContext(), APInt::getOneBitSet(BitWidth, SA->getZExtValue()));
        return getMulExpr(getSCEV(BO->LHS), getSCEV(X), Flags);
      }
      break;

But apparently langref was fixed in rL286785, so we're good and i'll post SCEV patch.

llvm/lib/Transforms/Scalar/Reassociate.cpp

static BinaryOperator *BreakUpSubtract(Instruction *Sub,
   LLVM_DEBUG(dbgs() << "Negated: " << *New << '\n');
   return New;
 }
 
 /// If this is a shift of a reassociable multiply or is used by one, change
 /// this into a multiply by a constant to assist with further reassociation.
 static BinaryOperator *ConvertShiftToMul(Instruction *Shl) {
   Constant *MulCst = ConstantInt::get(Shl->getType(), 1);
-  MulCst = ConstantExpr::getShl(MulCst, cast<Constant>(Shl->getOperand(1)));
+  auto *SA = cast<ConstantInt>(Shl->getOperand(1));
+  MulCst = ConstantExpr::getShl(MulCst, SA);
 
   BinaryOperator *Mul =
     BinaryOperator::CreateMul(Shl->getOperand(0), MulCst, "", Shl);
   Shl->setOperand(0, UndefValue::get(Shl->getType())); // Drop use of op.
   Mul->takeName(Shl);
 
   // Everyone now refers to the mul instruction.
   Shl->replaceAllUsesWith(Mul);
   Mul->setDebugLoc(Shl->getDebugLoc());
 
   // We can safely preserve the nuw flag in all cases.  It's also safe to turn a
   // nuw nsw shl into a nuw nsw mul.  However, nsw in isolation requires special
-  // handling.
+  // handling.  It can be preserved as long as we're not left shifting by
+  // bitwidth - 1.
   bool NSW = cast<BinaryOperator>(Shl)->hasNoSignedWrap();
   bool NUW = cast<BinaryOperator>(Shl)->hasNoUnsignedWrap();
-  if (NSW && NUW)
+  unsigned BitWidth = Shl->getType()->getIntegerBitWidth();
+  if (NSW && (NUW || SA->getValue().ult(BitWidth - 1)))
     Mul->setHasNoSignedWrap(true);
   Mul->setHasNoUnsignedWrap(NUW);
   return Mul;
 }
 
 /// Scan backwards and forwards among values with the same rank as element i
 /// to see if X exists.  If X does not exist, return i.  This is useful when
 /// scanning for 'x' when we see '-x' because they both get the same rank.

llvm/test/Transforms/Reassociate/wrap-flags.ll

 ; CHECK-NEXT:    ret i32 [[MUL2]]
 ;
 entry:
   %mul = shl nsw i32 %i, 31
   %mul2 = add i32 %mul, 1
   ret i32 %mul2
 }
 
+define i32 @shl_to_mul_nsw_2(i32 %i) {
+;
+; CHECK-LABEL: @shl_to_mul_nsw_2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[I:%.*]], 1073741824
+; CHECK-NEXT:    [[MUL2:%.*]] = add i32 [[MUL]], 1
+; CHECK-NEXT:    ret i32 [[MUL2]]
+;
+entry:
+  %mul = shl nsw i32 %i, 30
+  %mul2 = add i32 %mul, 1
+  ret i32 %mul2
+}
+
 define i32 @shl_to_mul_nuw(i32 %i) {
 ;
 ; CHECK-LABEL: @shl_to_mul_nuw(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[MUL:%.*]] = mul nuw i32 [[I:%.*]], 4
 ; CHECK-NEXT:    [[MUL2:%.*]] = add i32 [[MUL]], 1
 ; CHECK-NEXT:    ret i32 [[MUL2]]
 ;

 ; CHECK-NEXT:    ret i32 [[MUL2]]
 ;
 entry:
   %mul = shl nuw nsw i32 %i, 2
   %mul2 = add i32 %mul, 1
   ret i32 %mul2
 }
 
+define i32 @shl_to_mul_nuw_nsw_bitwidth_m1(i32 %i) {
+;
+; CHECK-LABEL: @shl_to_mul_nuw_nsw_bitwidth_m1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[MUL:%.*]] = mul nuw nsw i32 [[I:%.*]], -2147483648
+; CHECK-NEXT:    [[MUL2:%.*]] = add i32 [[MUL]], 1
+; CHECK-NEXT:    ret i32 [[MUL2]]
+;
+entry:
+  %mul = shl nuw nsw i32 %i, 31
+  %mul2 = add i32 %mul, 1
+  ret i32 %mul2
+}
+
 define i2 @pr23926(i2 %X1, i2 %X2) {
 ;
 ; CHECK-LABEL: @pr23926(
 ; CHECK-NEXT:    [[X1_NEG:%.*]] = sub i2 0, [[X1:%.*]]
 ; CHECK-NEXT:    [[ADD_NEG:%.*]] = add i2 [[X1_NEG]], -1
 ; CHECK-NEXT:    [[SUB:%.*]] = add i2 [[ADD_NEG]], [[X2:%.*]]
 ; CHECK-NEXT:    ret i2 [[SUB]]
 ;
   %add = add nuw i2 %X1, 1
   %sub = sub nuw nsw i2 %X2, %add
   ret i2 %sub
 }