[SCEV] ScalarEvolution::createSCEV(): clarify no-wrap flag propagation for shift by bitwidth-1

[lebedev.ri]

Summary

There was this comment here previously:

-        // 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 .

But langref was fixed in rL286785, and the behavior is pretty obvious:
http://volta.cs.utah.edu:8080/z/MM4WZP
^ nuw can always be propagated. nsw can be propagated if
either nuw is specified, or the shift is by *less* than bitwidth-1.

This mimics similar D81189 Reassociate change, alive2 is happy about that one.

I'm not sure NUW isn't being printed, but that seems unrelated.

[efriedma]

LGTM

[lebedev.ri]

In D81243#2077877, @efriedma wrote:

LGTM

Thank you for the review.

llvm/lib/Analysis/ScalarEvolution.cpp

case Instruction::Shl:
 
         // 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 .
+        // 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. It can be preserved as long as we're not
+        // left shifting by bitwidth - 1.
         auto Flags = SCEV::FlagAnyWrap;
-        if (BO->Op && SA->getValue().ult(BitWidth - 1))
-          Flags = getNoWrapFlagsFromUB(BO->Op);
+        if (BO->Op) {
+          auto MulFlags = getNoWrapFlagsFromUB(BO->Op);
+          if ((MulFlags & SCEV::FlagNSW) &&
+              ((MulFlags & SCEV::FlagNUW) || SA->getValue().ult(BitWidth - 1)))
+            Flags = (SCEV::NoWrapFlags)(Flags | SCEV::FlagNSW);
+          if (MulFlags & SCEV::FlagNUW)
+            Flags = (SCEV::NoWrapFlags)(Flags | SCEV::FlagNUW);
+        }
 
         Constant *X = ConstantInt::get(
             getContext(), APInt::getOneBitSet(BitWidth, SA->getZExtValue()));
         return getMulExpr(getSCEV(BO->LHS), getSCEV(X), Flags);
       }
       break;
 
     case Instruction::AShr: {

llvm/test/Analysis/ScalarEvolution/flags-from-poison.ll

 define void @test-shl-nuw-nsw(float* %input, i32 %start, i32 %numIterations) {
 ; CHECK-LABEL: @test-shl-nuw-nsw
 entry:
   br label %loop
 loop:
   %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
 
 ; CHECK: %index32 =
-; CHECK: --> {(-2147483648 * %start),+,-2147483648}<%loop>
+; CHECK: --> {(-2147483648 * %start),+,-2147483648}<nsw><%loop>
   %index32 = shl nuw nsw i32 %i, 31
 
 ; CHECK: %index64 =
-; CHECK: --> (sext i32 {(-2147483648 * %start),+,-2147483648}<%loop>
+; CHECK: --> {(sext i32 (-2147483648 * %start) to i64),+,-2147483648}<nsw><%loop>
   %index64 = sext i32 %index32 to i64
 
   %ptr = getelementptr inbounds float, float* %input, i64 %index64
   %nexti = add nsw i32 %i, 1
   %f = load float, float* %ptr, align 4
   %exitcond = icmp eq i32 %nexti, %numIterations
   br i1 %exitcond, label %exit, label %loop
 exit: