Index: llvm/lib/Analysis/ScalarEvolution.cpp
===================================================================
--- llvm/lib/Analysis/ScalarEvolution.cpp
+++ llvm/lib/Analysis/ScalarEvolution.cpp
@@ -2397,6 +2397,17 @@
       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;
 }
 
Index: llvm/test/Analysis/ScalarEvolution/extract-highbits-variablemask.ll
===================================================================
--- llvm/test/Analysis/ScalarEvolution/extract-highbits-variablemask.ll
+++ llvm/test/Analysis/ScalarEvolution/extract-highbits-variablemask.ll
@@ -10,7 +10,7 @@
 ; 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
Index: llvm/test/Analysis/ScalarEvolution/mul.ll
===================================================================
--- llvm/test/Analysis/ScalarEvolution/mul.ll
+++ llvm/test/Analysis/ScalarEvolution/mul.ll
@@ -7,7 +7,7 @@
 ; 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
@@ -65,7 +65,7 @@
 ; 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