[WIP][LoopUnroll] Enable unrolled loops to have scevable trip counts.

[samparker]

Summary

Loops with an 'unsigned' trip count appear to be a mystery to SCEV once it is unrolled, so try something different to make it understandable.

[samparker]

Currently using a mask to calculate the unrolled body test value, this looks like it solves the problem but causes regressions! Next I will try counting up with adds instead of down...

lib/Transforms/Utils/LoopUnrollRuntime.cpp

     // PHI functions.
     ConnectEpilog(L, ModVal, NewExit, LatchExit, PreHeader,
                   EpilogPreHeader, NewPreHeader, VMap, DT, LI,
                   PreserveLCSSA);
 
     // Update counter in loop for unrolling.
     // I should be multiply of Count.
     IRBuilder<> B2(NewPreHeader->getTerminator());
-    Value *TestVal = B2.CreateSub(TripCount, ModVal, "unroll_iter");
+    Value *TestVal = B2.CreateNUWSub(TripCount, ModVal, "unroll_iter");
     BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
     B2.SetInsertPoint(LatchBR);
     PHINode *NewIdx = PHINode::Create(TestVal->getType(), 2, "niter",
                                       Header->getFirstNonPHI());
     Value *IdxSub =
-        B2.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
+        B2.CreateNUWSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
                      NewIdx->getName() + ".nsub");
     Value *IdxCmp;
     if (LatchBR->getSuccessor(0) == Header)
       IdxCmp = B2.CreateIsNotNull(IdxSub, NewIdx->getName() + ".ncmp");
     else
       IdxCmp = B2.CreateIsNull(IdxSub, NewIdx->getName() + ".ncmp");
     NewIdx->addIncoming(TestVal, NewPreHeader);
     NewIdx->addIncoming(IdxSub, Latch);

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: entry:
+; CHECK: [[LOOP_GUARD:%[^ ]+]] = icmp eq i32 %N, 0
+; CHECK: br i1 [[LOOP_GUARD]], label {{.*}}, label %for.body.preheader
+
+; CHECK: for.body.preheader:
+; CHECK: [[BECOUNT:%[^ ]+]] = add i32 %N, -1
+; CHECK: %xtraiter = and i32 %N, 3
+; CHECK: [[UNROLL_GUARD:%[^ ]+]] = icmp ult i32 [[BECOUNT]], 3
+; CHECK: br i1 [[UNROLL_GUARD]], label {{.*}}, label %for.body.preheader.new
+
+; CHECK: for.body.preheader.new:
+; CHECK: %unroll_iter = sub nuw i32 %N, %xtraiter
+; CHECK: br label %for.body
+
+; CHECK: for.body:
+; CHECK: %niter = phi i32 [ %unroll_iter, %for.body.preheader.new ], [ [[NSUB3:%[^ ]+]], %for.body ]
+; CHECK: [[NSUB:%[^ ]+]] = sub nuw i32 %niter, 1
+; CHECK: [[NSUB1:%[^ ]+]] = sub nuw i32 [[NSUB]], 1
+; CHECK: [[NSUB2:%[^ ]+]] = sub nuw i32 [[NSUB1]], 1
+; CHECK: [[NSUB3:%[^ ]+]] = sub nuw i32 [[NSUB2]], 1
+; CHECK: [[NCMP:%[^ ]+]] = icmp eq i32 [[NSUB3]], 0
+; CHECK: br i1 [[NCMP]], label {{.*}}, label %for.body
+
+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-loop-multiple-exits.ll

 define void @test1(i64 %trip, i1 %cond) {
 ; EPILOG: test1(
 ; EPILOG-NEXT:  entry:
 ; EPILOG-NEXT:    [[TMP0:%.*]] = add i64 [[TRIP:%.*]], -1
 ; EPILOG-NEXT:    [[XTRAITER:%.*]] = and i64 [[TRIP]], 7
 ; EPILOG-NEXT:    [[TMP1:%.*]] = icmp ult i64 [[TMP0]], 7
 ; EPILOG-NEXT:    br i1 [[TMP1]], label %exit2.loopexit.unr-lcssa, label [[ENTRY_NEW:%.*]]
 ; EPILOG:       entry.new:
-; EPILOG-NEXT:    [[UNROLL_ITER:%.*]] = sub i64 [[TRIP]], [[XTRAITER]]
+; EPILOG-NEXT:    [[UNROLL_ITER:%.*]] = sub nuw i64 [[TRIP]], [[XTRAITER]]
 ; EPILOG-NEXT:    br label [[LOOP_HEADER:%.*]]
 ; EPILOG:  loop_latch.epil:
 ; EPILOG-NEXT:     %epil.iter.sub = add i64 %epil.iter, -1
 ; EPILOG-NEXT:     %epil.iter.cmp = icmp eq i64 %epil.iter.sub, 0
 ; EPILOG-NEXT:     br i1 %epil.iter.cmp, label %exit2.loopexit.epilog-lcssa, label %loop_header.epil
 ; EPILOG:  loop_latch.7:
 ; EPILOG-NEXT:     %niter.nsub.7 = add i64 %niter, -8
 ; EPILOG-NEXT:     %niter.ncmp.7 = icmp eq i64 %niter.nsub.7, 0

 define void @test3(i64 %trip, i64 %add) {
 ; EPILOG: test3(
 ; EPILOG-NEXT:  entry:
 ; EPILOG-NEXT:    [[TMP0:%.*]] = add i64 [[TRIP:%.*]], -1
 ; EPILOG-NEXT:    [[XTRAITER:%.*]] = and i64 [[TRIP]], 7
 ; EPILOG-NEXT:    [[TMP1:%.*]] = icmp ult i64 [[TMP0]], 7
 ; EPILOG-NEXT:    br i1 [[TMP1]], label %exit2.loopexit.unr-lcssa, label [[ENTRY_NEW:%.*]]
 ; EPILOG:       entry.new:
-; EPILOG-NEXT:    %unroll_iter = sub i64 [[TRIP]], [[XTRAITER]]
+; EPILOG-NEXT:    %unroll_iter = sub nuw i64 [[TRIP]], [[XTRAITER]]
 ; EPILOG-NEXT:    br label [[LOOP_HEADER:%.*]]
 ; EPILOG:  loop_header:
 ; EPILOG-NEXT:     %sum = phi i64 [ 0, %entry.new ], [ %sum.next.7, %loop_latch.7 ]
 ; EPILOG-NEXT:     %niter = phi i64 [ %unroll_iter, %entry.new ], [ %niter.nsub.7, %loop_latch.7 ]
 ; EPILOG:  loop_exiting_bb1.7:
 ; EPILOG-NEXT:     switch i64 %sum.next.6, label %loop_latch.7
 ; EPILOG:  loop_latch.7:
 ; EPILOG-NEXT:     %sum.next.7 = add i64 %sum.next.6, %add

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

 
 ; 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-LABEL: for.body.lr.ph.new:
-; CHECK: %unroll_iter = sub nsw i64 %wide.trip.count, %xtraiter
+; CHECK: %unroll_iter = sub nuw 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:.*]]
 
 ; CHECK: [[EPIL_PEEL0_PRE]]:
 ; CHECK: br label %[[EPIL_PEEL0:.*]]