[Transforms] Reassociate: Fix missing nsw/nuw flags

[lebedev.ri]

Patch is missing description, and legality reasoning.
Please split each diff hunk into it's own review.

[nikic]

Counter-proof for the no-op.ll change: https://alive2.llvm.org/ce/z/3_pM8c

llvm/lib/Transforms/Scalar/Reassociate.cpp

assert((isa<UnaryOperator>(Neg) || isa<BinaryOperator>(Neg)) &&
          "Expected a Negate!");
   // FIXME: It's not safe to lower a unary FNeg into a FMul by -1.0.
   unsigned OpNo = isa<BinaryOperator>(Neg) ? 1 : 0;
   Type *Ty = Neg->getType();
   Constant *NegOne = Ty->isIntOrIntVectorTy() ?
     ConstantInt::getAllOnesValue(Ty) : ConstantFP::get(Ty, -1.0);
 
   BinaryOperator *Res = CreateMul(Neg->getOperand(OpNo), NegOne, "", Neg, Neg);
+  if (OverflowingBinaryOperator *OBON = dyn_cast<OverflowingBinaryOperator>(Neg)) {
+    Res->setHasNoSignedWrap(OBON->hasNoSignedWrap());
+    Res->setHasNoUnsignedWrap(OBON->hasNoUnsignedWrap());
+  }
   Neg->setOperand(OpNo, Constant::getNullValue(Ty)); // Drop use of op.
   Res->takeName(Neg);
   Neg->replaceAllUsesWith(Res);
   Res->setDebugLoc(Neg->getDebugLoc());
   return Res;
 }
 
 /// Returns k such that lambda(2^Bitwidth) = 2^k, where lambda is the Carmichael
void ReassociatePass::RewriteExprTree(BinaryOperator *I,
   // expression tree is dominated by all of Ops.
   if (ExpressionChanged)
     do {
       // Preserve FastMathFlags.
       if (isa<FPMathOperator>(I)) {
         FastMathFlags Flags = I->getFastMathFlags();
         ExpressionChanged->clearSubclassOptionalData();
         ExpressionChanged->setFastMathFlags(Flags);
-      } else
+      } else {
+        // Preserve nsw/nuw flags.
+        OverflowingBinaryOperator *OBOI = dyn_cast<OverflowingBinaryOperator>(I);
+        bool NSW = OBOI ? OBOI->hasNoSignedWrap() : false;
+        bool NUW = OBOI ? OBOI->hasNoUnsignedWrap() : false;
         ExpressionChanged->clearSubclassOptionalData();
+        if (isa<OverflowingBinaryOperator>(ExpressionChanged)) {
+          ExpressionChanged->setHasNoSignedWrap(NSW);
+          ExpressionChanged->setHasNoUnsignedWrap(NUW);
+        }
+      }
 
       if (ExpressionChanged == I)
         break;
 
       // Discard any debug info related to the expressions that has changed (we
       // can leave debug infor related to the root, since the result of the
       // expression tree should be the same even after reassociation).
       replaceDbgUsesWithUndef(ExpressionChanged);
static BinaryOperator *BreakUpSubtract(Instruction *Sub,
   BinaryOperator *New = CreateAdd(Sub->getOperand(0), NegVal, "", Sub, Sub);
   Sub->setOperand(0, Constant::getNullValue(Sub->getType())); // Drop use of op.
   Sub->setOperand(1, Constant::getNullValue(Sub->getType())); // Drop use of op.
   New->takeName(Sub);
 
   // Everyone now refers to the add instruction.
   Sub->replaceAllUsesWith(New);
   New->setDebugLoc(Sub->getDebugLoc());
+  if (OverflowingBinaryOperator *OBOS = dyn_cast<OverflowingBinaryOperator>(Sub)) {
+    New->setHasNoSignedWrap(OBOS->hasNoSignedWrap());
+    New->setHasNoUnsignedWrap(OBOS->hasNoUnsignedWrap());
+  }
 
   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) {
Value *ReassociatePass::OptimizeExpression(BinaryOperator *I,
   if (Cst && Cst != ConstantExpr::getBinOpIdentity(Opcode, I->getType())) {
     if (Cst == ConstantExpr::getBinOpAbsorber(Opcode, I->getType()))
       return Cst;
     Ops.push_back(ValueEntry(0, Cst));
   }
 
   if (Ops.size() == 1) return Ops[0].Op;
 
+  OverflowingBinaryOperator *OBOI = dyn_cast<OverflowingBinaryOperator>(I);
+  bool NSW = OBOI ? OBOI->hasNoSignedWrap() : false;
+  bool NUW = OBOI ? OBOI->hasNoUnsignedWrap() : false;
+
   // Handle destructive annihilation due to identities between elements in the
   // argument list here.
   unsigned NumOps = Ops.size();
   switch (Opcode) {
   default: break;
   case Instruction::And:
   case Instruction::Or:
     if (Value *Result = OptimizeAndOrXor(Opcode, Ops))
       return Result;
     break;
 
   case Instruction::Xor:
     if (Value *Result = OptimizeXor(I, Ops))
       return Result;
     break;
 
   case Instruction::Add:
   case Instruction::FAdd:
-    if (Value *Result = OptimizeAdd(I, Ops))
+    if (Value *Result = OptimizeAdd(I, Ops)) {
+      BinaryOperator *BO = dyn_cast<BinaryOperator>(Result);
+      if (isa_and_nonnull<OverflowingBinaryOperator>(BO)) {
+        BO->setHasNoSignedWrap(NSW);
+        BO->setHasNoUnsignedWrap(NUW);
+      }
       return Result;
+    }
     break;
 
   case Instruction::Mul:
   case Instruction::FMul:
-    if (Value *Result = OptimizeMul(I, Ops))
+    if (Value *Result = OptimizeMul(I, Ops)) {
+      BinaryOperator *BO = dyn_cast<BinaryOperator>(Result);
+      if (isa_and_nonnull<OverflowingBinaryOperator>(BO)) {
+        BO->setHasNoSignedWrap(NSW);
+        BO->setHasNoUnsignedWrap(NUW);
+      }
       return Result;
+    }
     break;
   }
 
   if (Ops.size() != NumOps)
     return OptimizeExpression(I, Ops);
   return nullptr;
 }
 

llvm/test/Transforms/Reassociate/cse-pairs.ll

;
   store i32 %10, i32* @num2, align 4
   %11 = add nsw i32 %3, %1
   store i32 %11, i32* @num3, align 4
   ret i32 undef
 }
 
 define signext i32 @twoPairsAllOpInPairs(i32 signext %0, i32 signext %1, i32 signext %2, i32 signext %3) {
 ; CHECK-LABEL: @twoPairsAllOpInPairs(
-; CHECK-NEXT:    [[TMP5:%.*]] = add i32 [[TMP2:%.*]], [[TMP1:%.*]]
-; CHECK-NEXT:    [[TMP6:%.*]] = add i32 [[TMP5]], [[TMP0:%.*]]
-; CHECK-NEXT:    [[TMP7:%.*]] = add i32 [[TMP6]], [[TMP3:%.*]]
+; CHECK-NEXT:    [[TMP5:%.*]] = add nsw i32 [[TMP2:%.*]], [[TMP1:%.*]]
+; CHECK-NEXT:    [[TMP6:%.*]] = add nsw i32 [[TMP5]], [[TMP0:%.*]]
+; CHECK-NEXT:    [[TMP7:%.*]] = add nsw i32 [[TMP6]], [[TMP3:%.*]]
 ; CHECK-NEXT:    store i32 [[TMP7]], i32* @num1, align 4
 ; CHECK-NEXT:    store i32 [[TMP5]], i32* @num2, align 4
 ; CHECK-NEXT:    [[TMP8:%.*]] = add nsw i32 [[TMP3]], [[TMP0]]
 ; CHECK-NEXT:    store i32 [[TMP8]], i32* @num3, align 4
 ; CHECK-NEXT:    ret i32 undef
 ;
   %5 = add nsw i32 %0, %1
   %6 = add nsw i32 %5, %2
   %7 = add nsw i32 %6, %3
   store i32 %7, i32* @num1, align 4
   %8 = add nsw i32 %1, %2
   store i32 %8, i32* @num2, align 4
   %9 = add nsw i32 %0, %3
   store i32 %9, i32* @num3, align 4
   ret i32 undef
 }
 
 define signext i32 @threePairsAllOpInPairs(i32 signext %0, i32 signext %1, i32 signext %2, i32 signext %3, i32 signext %4, i32 signext %5) {
 ; CHECK-LABEL: @threePairsAllOpInPairs(
-; CHECK-NEXT:    [[TMP7:%.*]] = add i32 [[TMP3:%.*]], [[TMP2:%.*]]
-; CHECK-NEXT:    [[TMP8:%.*]] = add i32 [[TMP7]], [[TMP0:%.*]]
-; CHECK-NEXT:    [[TMP9:%.*]] = add i32 [[TMP8]], [[TMP1:%.*]]
-; CHECK-NEXT:    [[TMP10:%.*]] = add i32 [[TMP9]], [[TMP4:%.*]]
-; CHECK-NEXT:    [[TMP11:%.*]] = add i32 [[TMP10]], [[TMP5:%.*]]
+; CHECK-NEXT:    [[TMP7:%.*]] = add nsw i32 [[TMP3:%.*]], [[TMP2:%.*]]
+; CHECK-NEXT:    [[TMP8:%.*]] = add nsw i32 [[TMP7]], [[TMP0:%.*]]
+; CHECK-NEXT:    [[TMP9:%.*]] = add nsw i32 [[TMP8]], [[TMP1:%.*]]
+; CHECK-NEXT:    [[TMP10:%.*]] = add nsw i32 [[TMP9]], [[TMP4:%.*]]
+; CHECK-NEXT:    [[TMP11:%.*]] = add nsw i32 [[TMP10]], [[TMP5:%.*]]
 ; CHECK-NEXT:    store i32 [[TMP11]], i32* @num1, align 4
 ; CHECK-NEXT:    [[TMP12:%.*]] = add nsw i32 [[TMP5]], [[TMP0]]
 ; CHECK-NEXT:    store i32 [[TMP12]], i32* @num2, align 4
 ; CHECK-NEXT:    [[TMP13:%.*]] = add nsw i32 [[TMP4]], [[TMP1]]
 ; CHECK-NEXT:    store i32 [[TMP13]], i32* @num3, align 4
 ; CHECK-NEXT:    store i32 [[TMP7]], i32* @num4, align 4
 ; CHECK-NEXT:    ret i32 undef
 ;

llvm/test/Transforms/Reassociate/no-op.ll

;
   call void @use(i32 %m1)
   ret void
 }
 
 define void @test2(i32 %a, i32 %b, i32 %c, i32 %d) {
 ; The initial add doesn't change so should not lose the nsw flag.
 ; CHECK-LABEL: @test2(
 ; CHECK-NEXT:    [[A0:%.*]] = add nsw i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[A1:%.*]] = add i32 [[A0]], [[C:%.*]]
-; CHECK-NEXT:    [[A2:%.*]] = add i32 [[A1]], [[D:%.*]]
+; CHECK-NEXT:    [[A1:%.*]] = add nsw i32 [[A0]], [[C:%.*]]
+; CHECK-NEXT:    [[A2:%.*]] = add nsw i32 [[A1]], [[D:%.*]]
 ; CHECK-NEXT:    call void @use(i32 [[A2]])
 ; CHECK-NEXT:    ret void
 ;
   %a0 = add nsw i32 %b, %a
   %a1 = add nsw i32 %a0, %d
   %a2 = add nsw i32 %a1, %c
   call void @use(i32 %a2)
   ret void
 }

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

;
   %y = add nsw i64 %c, %b
   %z = add i64 %y, %a
   ret i64 %z
 }
 
 define i64 @test1(i64 %a, i64 %b, i64 %c) {
 ;
 ; CHECK-LABEL: @test1(
-; CHECK-NEXT:    [[Y:%.*]] = add i64 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = add i64 [[Y]], [[C:%.*]]
+; CHECK-NEXT:    [[Y:%.*]] = add nsw i64 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[Z:%.*]] = add nsw i64 [[Y]], [[C:%.*]]
 ; CHECK-NEXT:    ret i64 [[Z]]
 ;
   %y = add i64 %c, %b
   %z = add nsw i64 %y, %a
   ret i64 %z
 }
 
 ; PR9215

llvm/test/Transforms/Reassociate/vaarg_movable.ll

 ;
 ; CHECK-LABEL: @func(
 ; CHECK-NEXT:    [[VARARGS:%.*]] = alloca i8*, align 8
 ; CHECK-NEXT:    [[VARARGS1:%.*]] = bitcast i8** [[VARARGS]] to i8*
 ; CHECK-NEXT:    call void @llvm.va_start(i8* [[VARARGS1]])
 ; CHECK-NEXT:    [[V0:%.*]] = va_arg i8** [[VARARGS]], i32
 ; CHECK-NEXT:    [[V1:%.*]] = va_arg i8** [[VARARGS]], i32
 ; CHECK-NEXT:    [[V0_NEG:%.*]] = sub i32 0, [[V0]]
-; CHECK-NEXT:    [[SUB:%.*]] = add i32 [[V0_NEG]], 1
-; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[SUB]], [[V1]]
+; CHECK-NEXT:    [[SUB:%.*]] = add nsw i32 [[V0_NEG]], 1
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[SUB]], [[V1]]
 ; CHECK-NEXT:    call void @llvm.va_end(i8* [[VARARGS1]])
 ; CHECK-NEXT:    ret i32 [[ADD]]
 ;
   %varargs = alloca i8*, align 8
   %varargs1 = bitcast i8** %varargs to i8*
   call void @llvm.va_start(i8* %varargs1)
   %v0 = va_arg i8** %varargs, i32
   %v1 = va_arg i8** %varargs, i32
   %sub = sub nsw i32 %v1, %v0
   %add = add nsw i32 %sub, 1
   call void @llvm.va_end(i8* %varargs1)
   ret i32 %add
 }
 
 declare void @llvm.va_start(i8*)
 declare void @llvm.va_end(i8*)

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

entry:
   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:    [[SUB:%.*]] = add nuw nsw 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
 }