[SCEV] (udiv X, Y) * Y is always NUW

[reames]

Summary

Motivated by the removal done in D109782. This implements the correct flag part generically.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

2403

I think this only covers a subset of cases because it assumes the udiv is the first operand. Due to complexity sorting, this is a given for the case where Y is SCEVUnknown, but wouldn't we want this to trigger also for something like 3 * (udiv X, 3)?

2404

I believe UDiv always has two operands, multi operand udiv isn't well-defined...

[reames]

Address reviewer comment

[reames]

additional test update from broader scope - should have finished for ninja check to finish.

[nikic]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type,
 
   // <0,+,nonnegative><nw> is also nuw
   // TODO: Add corresponding nsw case
   if (Type == scAddRecExpr && ScalarEvolution::hasFlags(Flags, SCEV::FlagNW) &&
       !ScalarEvolution::hasFlags(Flags, SCEV::FlagNUW) && Ops.size() == 2 &&
       Ops[0]->isZero() && IsKnownNonNegative(Ops[1]))
     Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
 
+  // both (udiv X, Y) * Y and Y * (udiv X, Y) are always NUW
+  if (Type == scMulExpr && !ScalarEvolution::hasFlags(Flags, SCEV::FlagNUW) &&
+      Ops.size() == 2) {
+    if (auto *UDiv = dyn_cast<SCEVUDivExpr>(Ops[0]))
+      if (UDiv->getOperand(1) == Ops[1])
+        Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
+    if (auto *UDiv = dyn_cast<SCEVUDivExpr>(Ops[1]))
+      if (UDiv->getOperand(1) == Ops[0])
+        Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
+  }
+
   return Flags;
 }
 
 bool ScalarEvolution::isAvailableAtLoopEntry(const SCEV *S, const Loop *L) {
   return isLoopInvariant(S, L) && properlyDominates(S, L->getHeader());
 }
 
 /// Get a canonical add expression, or something simpler if possible.

llvm/test/Analysis/ScalarEvolution/extract-highbits-variablemask.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
 ; RUN: opt -S -disable-output "-passes=print<scalar-evolution>" < %s 2>&1 | FileCheck %s
 
 ; These testcases aren't *identical* but they have the same/similar meaning.
 
 ; The obvious case.
 define i32 @div(i32 %val, i32 %num) nounwind {
 ; CHECK-LABEL: 'div'
 ; CHECK-NEXT:  Classifying expressions for: @div
 ; CHECK-NEXT:    %tmp1 = udiv i32 %val, %num
 ; CHECK-NEXT:    -->  (%val /u %num) U: full-set S: full-set
 ; CHECK-NEXT:    %tmp2 = mul i32 %tmp1, %num
-; CHECK-NEXT:    -->  ((%val /u %num) * %num) U: full-set S: full-set
+; CHECK-NEXT:    -->  ((%val /u %num) * %num)<nuw> U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @div
 ;
   %tmp1 = udiv i32 %val, %num
   %tmp2 = mul i32 %tmp1, %num
   ret i32 %tmp2
 }
 
 define i32 @sdiv(i32 %val, i32 %num) nounwind {

llvm/test/Analysis/ScalarEvolution/max-be-count-not-constant.ll

 define void @pluto(i32 %arg) {
 ; CHECK-LABEL: 'pluto'
 ; CHECK-NEXT:  Classifying expressions for: @pluto
 ; CHECK-NEXT:    %tmp = ashr i32 %arg, 31
 ; CHECK-NEXT:    --> %tmp U: [-1,1) S: [-1,1)
 ; CHECK-NEXT:    %tmp1 = add nsw i32 %tmp, 2
 ; CHECK-NEXT:    --> (2 + %tmp)<nsw> U: [1,3) S: [1,3)
 ; CHECK-NEXT:    %tmp3 = phi i32 [ 0, %bb ], [ %tmp4, %bb2 ]
-; CHECK-NEXT:    --> {0,+,(2 + %tmp)<nsw>}<nuw><nsw><%bb2> U: [0,3) S: [0,3) Exits: ((2 + %tmp)<nsw> * (1 /u (2 + %tmp)<nsw>)) LoopDispositions: { %bb2: Computable }
+; CHECK-NEXT:    --> {0,+,(2 + %tmp)<nsw>}<nuw><nsw><%bb2> U: [0,3) S: [0,3) Exits: ((2 + %tmp)<nsw> * (1 /u (2 + %tmp)<nsw>))<nuw> LoopDispositions: { %bb2: Computable }
 ; CHECK-NEXT:    %tmp4 = add nuw nsw i32 %tmp1, %tmp3
-; CHECK-NEXT:    --> {(2 + %tmp)<nsw>,+,(2 + %tmp)<nsw>}<nuw><nsw><%bb2> U: [1,5) S: [1,5) Exits: (2 + ((2 + %tmp)<nsw> * (1 /u (2 + %tmp)<nsw>)) + %tmp) LoopDispositions: { %bb2: Computable }
+; CHECK-NEXT:    --> {(2 + %tmp)<nsw>,+,(2 + %tmp)<nsw>}<nuw><nsw><%bb2> U: [1,5) S: [1,5) Exits: (2 + ((2 + %tmp)<nsw> * (1 /u (2 + %tmp)<nsw>))<nuw> + %tmp) LoopDispositions: { %bb2: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @pluto
 ; CHECK-NEXT:  Loop %bb2: backedge-taken count is (1 /u (2 + %tmp)<nsw>)
 ; CHECK-NEXT:  Loop %bb2: max backedge-taken count is 1
 ; CHECK-NEXT:  Loop %bb2: Predicated backedge-taken count is (1 /u (2 + %tmp)<nsw>)
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %bb2: Trip multiple is 1
 ;
 bb:

llvm/test/Analysis/ScalarEvolution/mul.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
 ; RUN: opt < %s "-passes=print<scalar-evolution>" -disable-output 2>&1 | FileCheck %s
 
 define i8 @test(i8 %x, i8 %y) {
 ; CHECK-LABEL: 'test'
 ; CHECK-NEXT:  Classifying expressions for: @test
 ; CHECK-NEXT:    %udiv = udiv i8 %x, %y
 ; CHECK-NEXT:    --> (%x /u %y) U: full-set S: full-set
 ; CHECK-NEXT:    %res = mul i8 %udiv, %y
-; CHECK-NEXT:    --> ((%x /u %y) * %y) U: full-set S: full-set
+; CHECK-NEXT:    --> ((%x /u %y) * %y)<nuw> U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @test
 ;
   %udiv = udiv i8 %x, %y
   %res = mul i8 %udiv, %y
   ret i8 %res
 }
 
 define i8 @test2(i8 %x) {

 define i8 @test5(i8 %x, i32 %y32) {
 ; CHECK-LABEL: 'test5'
 ; CHECK-NEXT:  Classifying expressions for: @test5
 ; CHECK-NEXT:    %y = trunc i32 %y32 to i8
 ; CHECK-NEXT:    --> (trunc i32 %y32 to i8) U: full-set S: full-set
 ; CHECK-NEXT:    %udiv = udiv i8 %x, %y
 ; CHECK-NEXT:    --> (%x /u (trunc i32 %y32 to i8)) U: full-set S: full-set
 ; CHECK-NEXT:    %res = mul i8 %udiv, %y
-; CHECK-NEXT:    --> ((trunc i32 %y32 to i8) * (%x /u (trunc i32 %y32 to i8))) U: full-set S: full-set
+; CHECK-NEXT:    --> ((trunc i32 %y32 to i8) * (%x /u (trunc i32 %y32 to i8)))<nuw> U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @test5
 ;
   %y = trunc i32 %y32 to i8
   %udiv = udiv i8 %x, %y
   %res = mul i8 %udiv, %y
   ret i8 %res
 }