[LoopUnroll] Add FlagNUW for backedge count

[samparker]

Summary

While performing runtime unrolling, we assign the backedge taken count as TripCount - 1. So, if we can prove that TripCount > 0, then we know that the backedge count is nuw.

[samparker]

This is broken, as well as the patch is depends on!

lib/Transforms/Utils/LoopUnrollRuntime.cpp

bool llvm::UnrollRuntimeLoopRemainder(Loop *L, unsigned Count,
 
   // Calculate conditions for branch around loop for unrolling
   // in epilog case and around prolog remainder loop in prolog case.
   // Compute the number of extra iterations required, which is:
   //  extra iterations = run-time trip count % loop unroll factor
   PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
   Value *TripCount = Expander.expandCodeFor(TripCountSC, TripCountSC->getType(),
                                             PreHeaderBR);
-  Value *BECount = Expander.expandCodeFor(BECountSC, BECountSC->getType(),
-                                          PreHeaderBR);
+
+  Value *BECount = nullptr;
+  auto *Zero = cast<ConstantInt>(ConstantInt::get(TripCountSC->getType(), 0));
+  const SCEV *ZeroSC = SE->getConstant(Zero);
+  if (SE->isLoopEntryGuardedByCond(L, ICmpInst::ICMP_UGT, TripCountSC, ZeroSC)) {
+    // BECount == TripCount - 1, so
+    // if TripCount > 0, then
+    // BECount is NUW
+    auto *MinusOne = cast<ConstantInt>(ConstantInt::get(TripCountSC->getType(), -1));
+    const SCEV *MinusOneSC = SE->getConstant(MinusOne);
+    const SCEV *BECountSCNoWrap = SE->getAddExpr(TripCountSC, MinusOneSC,
+                                                 SCEV::FlagNUW);
+    BECount = Expander.expandCodeFor(BECountSCNoWrap, BECountSCNoWrap->getType(),
+                                     PreHeaderBR);
+  } else
+    BECount = Expander.expandCodeFor(BECountSC, BECountSC->getType(),
   IRBuilder<> B(PreHeaderBR);
   Value *ModVal;
   // Calculate ModVal = (BECount + 1) % Count.
   // Note that TripCount is BECount + 1.
   if (isPowerOf2_32(Count)) {
     // When Count is power of 2 we don't BECount for epilog case, however we'll
     // need it for a branch around unrolling loop for prolog case.
     ModVal = B.CreateAnd(TripCount, Count - 1, "xtraiter");

test/Transforms/IndVarSimplify/lftr.ll

 define void @test_udiv_as_shift(i8* %a, i8 %n) nounwind uwtable ssp {
 ; CHECK-LABEL: @test_udiv_as_shift(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[E:%.*]] = icmp sgt i8 [[N:%.*]], 3
 ; CHECK-NEXT:    br i1 [[E]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 ; CHECK:       loop.preheader:
 ; CHECK-NEXT:    [[TMP0:%.*]] = add i8 [[N]], 3
 ; CHECK-NEXT:    [[TMP1:%.*]] = lshr i8 [[TMP0]], 2
-; CHECK-NEXT:    [[TMP2:%.*]] = add i8 [[TMP1]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = add nuw nsw i8 [[TMP1]], 1
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[I1:%.*]] = phi i8 [ [[I1_INC:%.*]], [[LOOP]] ], [ 0, [[LOOP_PREHEADER]] ]
 ; CHECK-NEXT:    [[I1_INC]] = add nuw nsw i8 [[I1]], 1
 ; CHECK-NEXT:    store volatile i8 0, i8* [[A:%.*]]
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i8 [[I1_INC]], [[TMP2]]
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
 ; CHECK:       exit.loopexit:

test/Transforms/LoopUnroll/nuw-backedge.ll

+; RUN: opt -loop-unroll -unroll-runtime -unroll-count=4 %s -S -o - | FileCheck %s
+
+; CHECK-LABEL: nuw_trip_count
+; CHECK: for.body.preheader:
+; CHECK-NEXT: [[BECOUNT:%[^ ]+]] = add nuw i32 %N, -1
+; CHECK-NEXT: %xtraiter = and i32 %N, 3
+; CHECK-NEXT: [[CMP:%[^ ]+]] = icmp ult i32 [[BECOUNT]], 3
+; CHECK-NEXT:br i1 [[CMP]], label %for.cond.cleanup.loopexit.unr-lcssa, label %for.body.preheader.new
+define void @nuw_trip_count(i32* nocapture readonly %a, i32* nocapture readonly %b, i32* noalias nocapture %c, i32 %N) {
+entry:
+  %cmp8 = icmp eq i32 %N, 0
+  br i1 %cmp8, label %for.cond.cleanup, label %for.body
+
+for.cond.cleanup:
+  ret void
+
+for.body:
+  %i.09 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i32, i32* %a, i32 %i.09
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx1 = getelementptr inbounds i32, i32* %b, i32 %i.09
+  %1 = load i32, i32* %arrayidx1, align 4
+  %mul = mul nsw i32 %1, %0
+  %arrayidx2 = getelementptr inbounds i32, i32* %c, i32 %i.09
+  store i32 %mul, i32* %arrayidx2, align 4
+  %inc = add nuw i32 %i.09, 1
+  %exitcond = icmp eq i32 %inc, %N
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+

test/Transforms/LoopUnroll/runtime-unroll-remainder.ll

for.body.lr.ph:
   %wide.trip.count = zext i32 %N to i64
   br label %for.body
 
 for.cond.cleanup:
   %c.0.lcssa = phi i32 [ 0, %entry ], [ %add, %for.body ]
   ret i32 %c.0.lcssa
 
 ; CHECK-LABEL: for.body.lr.ph
-; CHECK: [[COUNT:%[a-z.0-9]+]] = add nsw i64 %wide.trip.count, -1
 ; CHECK: %xtraiter = and i64 %wide.trip.count, 3
-; CHECK: [[CMP:%[a-z.0-9]+]] = icmp ult i64 [[COUNT]], 3
-; CHECK: br i1 [[CMP]], label %[[CLEANUP:.*]], label %for.body.lr.ph.new
+; CHECK: br i1 false, label %[[CLEANUP:.*]], label %for.body.lr.ph.new
 
 ; CHECK-LABEL: for.body.lr.ph.new:
 ; CHECK: %unroll_iter = sub nsw i64 %wide.trip.count, %xtraiter
 ; CHECK: br label %for.body
 
 ; CHECK: [[CLEANUP]]:
 ; CHECK: [[MOD:%[a-z.0-9]+]] = icmp eq i64 %xtraiter, 0
 ; CHECK: br i1 [[MOD]], label %[[EXIT:.*]], label %[[EPIL_PEEL0_PRE:.*]]

test/Transforms/LoopUnrollAndJam/unroll-and-jam.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -basicaa -tbaa -loop-unroll-and-jam -allow-unroll-and-jam -unroll-and-jam-count=4 -unroll-remainder < %s -S | FileCheck %s
 
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
 
 ; CHECK-LABEL: test1
 ; Tests for(i) { sum = 0; for(j) sum += B[j]; A[i] = sum; }
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[J:%.*]], 0
 ; CHECK-NEXT:    [[CMPJ:%.*]] = icmp ne i32 [[I:%.*]], 0
 ; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[CMP]], [[CMPJ]]
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FOR_OUTER_PREHEADER:%.*]], label [[FOR_END:%.*]]
 ; CHECK:       for.outer.preheader:
-; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[I]], -1
+; CHECK-NEXT:    [[TMP0:%.*]] = add nuw i32 [[I]], -1
 ; CHECK-NEXT:    [[XTRAITER:%.*]] = and i32 [[I]], 3
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[TMP0]], 3
 ; CHECK-NEXT:    br i1 [[TMP1]], label [[FOR_END_LOOPEXIT_UNR_LCSSA:%.*]], label [[FOR_OUTER_PREHEADER_NEW:%.*]]
 ; CHECK:       for.outer.preheader.new:
 ; CHECK-NEXT:    [[UNROLL_ITER:%.*]] = sub i32 [[I]], [[XTRAITER]]
 ; CHECK-NEXT:    br label [[FOR_OUTER:%.*]]
 ; CHECK:       for.outer:
 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[ADD8_3:%.*]], [[FOR_LATCH:%.*]] ], [ 0, [[FOR_OUTER_PREHEADER_NEW]] ]