PR27392 unroll epilog TripCount overflow fix.

[evstupac]

Summary

We should compare BECount with (Count - 1) instead of TripCount with xtraiter.

[evstupac]

PING.

[hfinkel]

We should compare BECount with (Count - 1) instead of TripCount with xtraiter.

When you commit this, make sure that the description explains why (unsigned overflow on TripCount).

Otherwise, I think this makes sense, and is consistent with how we do the tripcount < loopfactor check in the prologue case. LGTM.

lib/Transforms/Utils/LoopUnrollRuntime.cpp

581

Count - 1 is a parameter to ConstantInt::get, not CreateICmpULT. I'd prefer that it be indented accordingly (so it is under BECount->getType()).

[Eugene.Zelenko]

Committed in r267662.

lib/Transforms/Utils/LoopUnrollRuntime.cpp

for (Instruction &BBI : *Succ) {
       // node.  Corresponding instruction in epilog loop should be PHI.
       PHINode *VPN = cast<PHINode>(VMap[&BBI]);
       VPN->setIncomingValue(VPN->getBasicBlockIndex(EpilogPreHeader), NewPN);
     }
   }
 
   Instruction *InsertPt = NewExit->getTerminator();
   IRBuilder<> B(InsertPt);
-  Value *BrLoopExit = B.CreateIsNotNull(ModVal);
+  Value *BrLoopExit = B.CreateIsNotNull(ModVal, "lcmp.mod");
   assert(Exit && "Loop must have a single exit block only");
   // Split the exit to maintain loop canonicalization guarantees
   SmallVector<BasicBlock*, 4> Preds(predecessors(Exit));
   SplitBlockPredecessors(Exit, Preds, ".epilog-lcssa", DT, LI,
                          PreserveLCSSA);
   // Add the branch to the exit block (around the unrolling loop)
   B.CreateCondBr(BrLoopExit, EpilogPreHeader, Exit);
   InsertPt->eraseFromParent();

 ///        if (extraiters != 0) jump Prol: // Omitted if unroll factor is 2.
 ///        if (tripcount < loopfactor) jump End:
 /// Loop:
 /// ...
 /// End:
 ///
 /// ***Epilog case***
 ///        extraiters = tripcount % loopfactor
-///        if (extraiters == tripcount) jump LoopExit:
+///        if (tripcount < loopfactor) jump LoopExit:
 ///        unroll_iters = tripcount - extraiters
 /// Loop:  LoopBody; (executes unroll_iter times);
 ///        unroll_iter -= 1
 ///        if (unroll_iter != 0) jump Loop:
 /// LoopExit:
 ///        if (extraiters == 0) jump EpilExit:
 /// Epil:  LoopBody; (executes extraiters times)
 ///        extraiters -= 1                 // Omitted if unroll factor is 2.
if (isPowerOf2_32(Count)) {
     Value *ModValAdd = B.CreateAdd(ModValTmp,
                                    ConstantInt::get(ModValTmp->getType(), 1));
     // At that point (BECount % Count) + 1 could be equal to Count.
     // To handle this case we need to take mod by Count one more time.
     ModVal = B.CreateURem(ModValAdd,
                           ConstantInt::get(BECount->getType(), Count),
                           "xtraiter");
   }
-  Value *CmpOperand =
-      UseEpilogRemainder ? TripCount :
-                           ConstantInt::get(TripCount->getType(), 0);
-  Value *BranchVal = B.CreateICmpNE(ModVal, CmpOperand, "lcmp.mod");
-  BasicBlock *FirstLoop = UseEpilogRemainder ? NewPreHeader : PrologPreHeader;
-  BasicBlock *SecondLoop = UseEpilogRemainder ? NewExit : PrologExit;
+  Value *BranchVal =
+      UseEpilogRemainder ? B.CreateICmpULT(BECount,
+                                           ConstantInt::get(BECount->getType(),
+                                           Count - 1)) :
+                           B.CreateIsNotNull(ModVal, "lcmp.mod");
+  BasicBlock *RemainderLoop = UseEpilogRemainder ? NewExit : PrologPreHeader;
+  BasicBlock *UnrollingLoop = UseEpilogRemainder ? NewPreHeader : PrologExit;
   // Branch to either remainder (extra iterations) loop or unrolling loop.
-  B.CreateCondBr(BranchVal, FirstLoop, SecondLoop);
+  B.CreateCondBr(BranchVal, RemainderLoop, UnrollingLoop);
   PreHeaderBR->eraseFromParent();
   Function *F = Header->getParent();
   // Get an ordered list of blocks in the loop to help with the ordering of the
   // cloned blocks in the prolog/epilog code
   LoopBlocksDFS LoopBlocks(L);
   LoopBlocks.perform(LI);
 
   //

test/Transforms/LoopUnroll/AArch64/runtime-loop.ll

 ; RUN: opt < %s -S -loop-unroll -mtriple aarch64 -mcpu=cortex-a57 | FileCheck %s -check-prefix=EPILOG
 ; RUN: opt < %s -S -loop-unroll -mtriple aarch64 -mcpu=cortex-a57 -unroll-runtime-epilog=false | FileCheck %s -check-prefix=PROLOG
 
 ; Tests for unrolling loops with run-time trip counts
 
 ; EPILOG:  %xtraiter = and i32 %n
-; EPILOG:  %lcmp.mod = icmp ne i32 %xtraiter, %n
-; EPILOG:  br i1 %lcmp.mod, label %for.body.preheader.new, label %for.end.loopexit.unr-lcssa
+; EPILOG:  for.body:
+; EPILOG:  %lcmp.mod = icmp ne i32 %xtraiter, 0
+; EPILOG:  br i1 %lcmp.mod, label %for.body.epil.preheader, label %for.end.loopexit
+; EPILOG:  for.body.epil:
 
 ; PROLOG:  %xtraiter = and i32 %n
 ; PROLOG:  %lcmp.mod = icmp ne i32 %xtraiter, 0
 ; PROLOG:  br i1 %lcmp.mod, label %for.body.prol.preheader, label %for.body.prol.loopexit
-
-; EPILOG:  for.body:
-; EPILOG:  for.body.epil:
-
 ; PROLOG:  for.body.prol:
 ; PROLOG:  for.body:
 
 define i32 @test(i32* nocapture %a, i32 %n) nounwind uwtable readonly {
 entry:
   %cmp1 = icmp eq i32 %n, 0
   br i1 %cmp1, label %for.end, label %for.body
 

test/Transforms/LoopUnroll/runtime-loop.ll

 ; RUN: opt < %s -S -loop-unroll -unroll-runtime=true | FileCheck %s -check-prefix=EPILOG
 ; RUN: opt < %s -S -loop-unroll -unroll-runtime=true -unroll-runtime-epilog=false | FileCheck %s -check-prefix=PROLOG
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 
 ; Tests for unrolling loops with run-time trip counts
 
 ; EPILOG: %xtraiter = and i32 %n
-; EPILOG:  %lcmp.mod = icmp ne i32 %xtraiter, %n
-; EPILOG:  br i1 %lcmp.mod, label %for.body.preheader.new, label %for.end.loopexit.unr-lcssa
+; EPILOG:  %lcmp.mod = icmp ne i32 %xtraiter, 0
+; EPILOG:  br i1 %lcmp.mod, label %for.body.epil.preheader, label %for.end.loopexit
 
 ; PROLOG: %xtraiter = and i32 %n
 ; PROLOG:  %lcmp.mod = icmp ne i32 %xtraiter, 0
 ; PROLOG:  br i1 %lcmp.mod, label %for.body.prol.preheader, label %for.body.prol.loopexit
 
 ; EPILOG: for.body.epil:
 ; EPILOG: %indvars.iv.epil = phi i64 [ %indvars.iv.next.epil, %for.body.epil ],  [ %indvars.iv.unr, %for.body.epil.preheader ]
 ; EPILOG:  %epil.iter.sub = sub i32 %epil.iter, 1

test/Transforms/LoopUnroll/runtime-loop1.ll

 ; RUN: opt < %s -S -loop-unroll -unroll-runtime -unroll-count=2 | FileCheck %s -check-prefix=EPILOG
 ; RUN: opt < %s -S -loop-unroll -unroll-runtime -unroll-count=2 -unroll-runtime-epilog=false | FileCheck %s -check-prefix=PROLOG
 
 ; This tests that setting the unroll count works
 
 
 ; EPILOG: for.body.preheader:
-; EPILOG:   br i1 %lcmp.mod, label %for.body.preheader.new, label %for.end.loopexit.unr-lcssa, !dbg [[PH_LOC:![0-9]+]]
+; EPILOG:   br i1 %1, label %for.end.loopexit.unr-lcssa, label %for.body.preheader.new, !dbg [[PH_LOC:![0-9]+]]
 ; EPILOG: for.body:
 ; EPILOG:   br i1 %niter.ncmp.1, label %for.end.loopexit.unr-lcssa.loopexit, label %for.body, !dbg [[BODY_LOC:![0-9]+]]
 ; EPILOG-NOT: br i1 %niter.ncmp.2, label %for.end.loopexit{{.*}}, label %for.body
 ; EPILOG: for.body.epil.preheader:
 ; EPILOG:   br label %for.body.epil, !dbg [[EXIT_LOC:![0-9]+]]
 ; EPILOG: for.body.epil:
 ; EPILOG:   br label %for.end.loopexit.epilog-lcssa, !dbg [[BODY_LOC:![0-9]+]]
 

test/Transforms/LoopUnroll/tripcount-overflow.ll

-; RUN: opt < %s -S -unroll-runtime -unroll-count=2 -loop-unroll | FileCheck %s
+; RUN: opt < %s -S -unroll-runtime -unroll-count=2 -loop-unroll | FileCheck %s -check-prefix=EPILOG
+; RUN: opt < %s -S -unroll-runtime -unroll-count=2 -loop-unroll -unroll-runtime-epilog=false | FileCheck %s -check-prefix=PROLOG
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 ; This test case documents how runtime loop unrolling handles the case
 ; when the backedge-count is -1.
 
 ; If %N, the backedge-taken count, is -1 then %0 unsigned-overflows
 ; and is 0.  %xtraiter too is 0, signifying that the total trip-count
 ; is divisible by 2.  The prologue then branches to the unrolled loop
 ; and executes the 2^32 iterations there, in groups of 2.
 
+; EPILOG: entry:
 
-; CHECK: entry:
-; CHECK-NEXT: %0 = add i32 %N, 1
-; CHECK-NEXT: %xtraiter = and i32 %0, 1
-; CHECK-NEXT: %lcmp.mod = icmp ne i32 %xtraiter, %0
-; CHECK-NEXT: br i1 %lcmp.mod, label %entry.new, label %while.end.unr-lcssa
-
-; CHECK: while.body.epil:
-; CHECK: br label %while.end.epilog-lcssa
-
-; CHECK: while.end.epilog-lcssa:
+; EPILOG-NEXT: %0 = add i32 %N, 1
+; EPILOG-NEXT: %xtraiter = and i32 %0, 1
+; EPILOG-NEXT: %1 = icmp ult i32 %N, 1
+; EPILOG-NEXT: br i1 %1, label %while.end.unr-lcssa, label %entry.new
+; EPILOG: while.body:
+
+; EPILOG: %lcmp.mod = icmp ne i32 %xtraiter, 0
+; EPILOG-NEXT: br i1 %lcmp.mod, label %while.body.epil.preheader, label %while.end
+; EPILOG: while.body.epil:
+
+; PROLOG: entry:
+; PROLOG-NEXT: %0 = add i32 %N, 1
+; PROLOG-NEXT: %xtraiter = and i32 %0, 1
+; PROLOG-NEXT: %lcmp.mod = icmp ne i32 %xtraiter, 0
+; PROLOG-NEXT: br i1 %lcmp.mod, label %while.body.prol.preheader, label %while.body.prol.loopexit
+; PROLOG: while.body.prol:
+
+; PROLOG: %1 = icmp ult i32 %N, 1
+; PROLOG-NEXT: br i1 %1, label %while.end, label %entry.new
+; PROLOG: while.body:
 
 ; Function Attrs: nounwind readnone ssp uwtable
 define i32 @foo(i32 %N) {
 entry:
   br label %while.body
 
 while.body:                                       ; preds = %while.body, %entry
   %i = phi i32 [ 0, %entry ], [ %inc, %while.body ]
   %cmp = icmp eq i32 %i, %N
   %inc = add i32 %i, 1
   br i1 %cmp, label %while.end, label %while.body
 
 while.end:                                        ; preds = %while.body
   ret i32 %i
 }