[LoopUnroll] Handle certain PHIs in full unrolling properly.

[ebevhan]

Summary

When reconstructing the CFG of the loop after unrolling,
LoopUnroll could in some cases remove the phi operands of
loop-carried values instead of preserving them, resulting
in undef phi values after loop unrolling.

When doing this reconstruction, avoid removing incoming
phi values for phis in the successor blocks if the successor
is the block we are jumping to anyway.

[lebedev.ri]

test/Transforms/LoopUnroll/full-unroll-miscompile.ll

8 ↗

(On Diff #215540)

passing-by remark: it's way too fragile to test exact value names,
you may want to test more of the output (capturing the value names elsewhere),
if not all of it.

[ebevhan]

test/Transforms/LoopUnroll/full-unroll-miscompile.ll

8 ↗

(On Diff #215540)

I suppose I can generate the checks with the python script.

[lebedev.ri]

test/Transforms/LoopUnroll/full-unroll-miscompile.ll

8 ↗

(On Diff #215540)

In this case i wasn't insisting on that - it gets pretty unreadable for large functions too.
But if it is autogenerated, you might as well precommit the original test.

<.. just passing by ..>

[fhahn]

Thanks for looking into this!

lib/Transforms/Utils/LoopUnroll.cpp

726 ↗

(On Diff #215561)

Currently we have a problem when unrolling loops which exit via the header. We should only preserve the incoming value from BB for the block in the current loop we jump to. For loops where we exit via the latch, this is the current header of the loop. For loops exiting via the header, this should be the successor of the header in the loop.

I think it would be slightly better to just change the name of CurrentHeader and then pass HeaderSucc[I] at line 797, to avoid unnecessary checks and keep the code slightly simpler. Maybe also add a comment in setDest to explain better what is going on.

test/Transforms/LoopUnroll/full-unroll-miscompile.ll

38 ↗

(On Diff #215561)

Can you strip away the unnecessary stores/loads? They do not impact unrolling.

59 ↗

(On Diff #215561)

I think the test would be slightly better if we make %tmp2 loop dependent.

67 ↗

(On Diff #215561)

I think the attributes are not necessary.

[ebevhan]

lib/Transforms/Utils/LoopUnroll.cpp

726 ↗

(On Diff #215561)

I see, thanks for further insight! I'll make these changes.

test/Transforms/LoopUnroll/full-unroll-miscompile.ll

38 ↗

(On Diff #215561)

What should I replace the sdiv with in that case? Just a single load?

[fhahn]

It would be great if you could add another function to the test, where we do not fully unroll the loop, i.e. by making sure it has a high trip count. For that, the minsize/optsize attributes need to be removed. Also, could you change the test file name to something a bit more descriptive, like unroll-header-exiting-with-phis.ll?

test/Transforms/LoopUnroll/full-unroll-miscompile.ll

38 ↗

(On Diff #215561)

it's only used in %.lcssa10, you can replace it with an arbitrary constant there.

Instead of %tmp2 outside the loop, it would be good to have a loop dependent load or something, e.g. (simply pass an i16* %A as argument to the function).

%ptr = getelementptr inbounds i16, i16* %A, i64 %i.0
%tmp2 = load i16, i16* %ptr, align 1

47 ↗

(On Diff #215561)

Another nit: we could make %i.0 start at 0 and adjust the check in %cmp accordingly. Maybe also change it so we have more than 1 iteration to unroll, e.g. 2 or 3 iterations.

[fhahn]

LGTM, thanks! I think it would be good to also pick this for the 9.0 release.

[efriedma]

Yes, makes sense for 9.0

[fhahn]

@ebevhan it would be great if you could land this soon, so we can get it into the 9.0 release branch

[ebevhan]

@fhahn I don't have commit access so if someone could land it for me, that would be great!

[bjope]

In D66334#1644758, @ebevhan wrote:

@fhahn I don't have commit access so if someone could land it for me, that would be great!

I'll land this on trunk.
Any extra action needed from my side to get it into 9.0?

[fhahn]

In D66334#1644763, @bjope wrote:

In D66334#1644758, @ebevhan wrote:

@fhahn I don't have commit access so if someone could land it for me, that would be great!

I'll land this on trunk.
Any extra action needed from my side to get it into 9.0?

Thanks! Once the release branch is created, you have to file a bug to get a commit merged into the release branch, which I did for this patch: https://bugs.llvm.org/show_bug.cgi?id=43118

[bjope]

In D66334#1645356, @fhahn wrote:

In D66334#1644763, @bjope wrote:

In D66334#1644758, @ebevhan wrote:

@fhahn I don't have commit access so if someone could land it for me, that would be great!

I'll land this on trunk.
Any extra action needed from my side to get it into 9.0?

Thanks! Once the release branch is created, you have to file a bug to get a commit merged into the release branch, which I did for this patch: https://bugs.llvm.org/show_bug.cgi?id=43118

In D66334#1645356, @fhahn wrote:

In D66334#1644763, @bjope wrote:

In D66334#1644758, @ebevhan wrote:

@fhahn I don't have commit access so if someone could land it for me, that would be great!

I'll land this on trunk.
Any extra action needed from my side to get it into 9.0?

Thanks! Once the release branch is created, you have to file a bug to get a commit merged into the release branch, which I did for this patch: https://bugs.llvm.org/show_bug.cgi?id=43118

Great. I'll use that bug report as a template the next time :-)

llvm/trunk/lib/Transforms/Utils/LoopUnroll.cpp

if (CompletelyUnroll) {
       }
       assert(Latches.back() == LastValueMap[LatchBlock] && "bad last latch");
       PN->addIncoming(InVal, Latches.back());
     }
   }
 
   auto setDest = [LoopExit, ContinueOnTrue](BasicBlock *Src, BasicBlock *Dest,
                                             ArrayRef<BasicBlock *> NextBlocks,
-                                            BasicBlock *CurrentHeader,
+                                            BasicBlock *BlockInLoop,
                                             bool NeedConditional) {
     auto *Term = cast<BranchInst>(Src->getTerminator());
     if (NeedConditional) {
       // Update the conditional branch's successor for the following
       // iteration.
       Term->setSuccessor(!ContinueOnTrue, Dest);
     } else {
       // Remove phi operands at this loop exit
       if (Dest != LoopExit) {
         BasicBlock *BB = Src;
         for (BasicBlock *Succ : successors(BB)) {
-          if (Succ == CurrentHeader)
+          // Preserve the incoming value from BB if we are jumping to the block
+          // in the current loop.
+          if (Succ == BlockInLoop)
             continue;
           for (PHINode &Phi : Succ->phis())
             Phi.removeIncomingValue(BB, false);
         }
       }
       // Replace the conditional branch with an unconditional one.
       BranchInst::Create(Dest, Term);
       Term->eraseFromParent();
for (unsigned i = 0, e = Headers.size(); i != e; ++i) {
         // may have to execute the loop body depending on the condition.
         NeedConditional = j == 0 || ULO.PreserveCondBr;
       else if (j != BreakoutTrip &&
                (ULO.TripMultiple == 0 || j % ULO.TripMultiple != 0))
         // If we know the trip count or a multiple of it, we can safely use an
         // unconditional branch for some iterations.
         NeedConditional = false;
 
-      setDest(Headers[i], Dest, Headers, Headers[i], NeedConditional);
+      setDest(Headers[i], Dest, Headers, HeaderSucc[i], NeedConditional);
     }
 
     // Set up latches to branch to the new header in the unrolled iterations or
     // the loop exit for the last latch in a fully unrolled loop.
 
     for (unsigned i = 0, e = Latches.size(); i != e; ++i) {
       // The original branch was replicated in each unrolled iteration.
       BranchInst *Term = cast<BranchInst>(Latches[i]->getTerminator());

llvm/trunk/test/Transforms/LoopUnroll/unroll-header-exiting-with-phis.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -S -loop-unroll -unroll-allow-partial | FileCheck %s
+
+; The phi which acts as input to func should not be undef. It should
+; have its loop-carried value (the load in for.cond) replaced accordingly
+; after unrolling the loop.
+
+define i16 @full_unroll(i16* %A) {
+; CHECK-LABEL: @full_unroll(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[TMP2:%.*]] = load i16, i16* [[A:%.*]]
+; CHECK-NEXT:    br label [[FOR_COND_CLEANUP3:%.*]]
+; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    [[DOTLCSSA10_LCSSA:%.*]] = phi i16 [ [[TMP2_2:%.*]], [[FOR_COND_CLEANUP3_2:%.*]] ]
+; CHECK-NEXT:    [[TMP3:%.*]] = call i16 @func(i16 [[DOTLCSSA10_LCSSA]])
+; CHECK-NEXT:    ret i16 0
+; CHECK:       for.cond.cleanup3:
+; CHECK-NEXT:    [[PTR_1:%.*]] = getelementptr inbounds i16, i16* [[A]], i64 1
+; CHECK-NEXT:    [[TMP2_1:%.*]] = load i16, i16* [[PTR_1]]
+; CHECK-NEXT:    br label [[FOR_COND_CLEANUP3_1:%.*]]
+; CHECK:       for.cond.cleanup3.1:
+; CHECK-NEXT:    [[PTR_2:%.*]] = getelementptr inbounds i16, i16* [[A]], i64 2
+; CHECK-NEXT:    [[TMP2_2]] = load i16, i16* [[PTR_2]]
+; CHECK-NEXT:    br label [[FOR_COND_CLEANUP3_2]]
+; CHECK:       for.cond.cleanup3.2:
+; CHECK-NEXT:    [[PTR_3:%.*]] = getelementptr inbounds i16, i16* [[A]], i64 3
+; CHECK-NEXT:    [[TMP2_3:%.*]] = load i16, i16* [[PTR_3]]
+; CHECK-NEXT:    br i1 false, label [[FOR_COND_CLEANUP3_3:%.*]], label [[FOR_COND_CLEANUP:%.*]]
+; CHECK:       for.cond.cleanup3.3:
+; CHECK-NEXT:    unreachable
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.cond.cleanup3, %entry
+  %.lcssa10 = phi i16 [ 123, %entry ], [ %.lcssa, %for.cond.cleanup3 ]
+  %i.0 = phi i64 [ 0, %entry ], [ %inc9, %for.cond.cleanup3 ]
+  %ptr = getelementptr inbounds i16, i16* %A, i64 %i.0
+  %tmp2 = load i16, i16* %ptr
+  %cmp = icmp ult i64 %i.0, 3
+  br i1 %cmp, label %for.cond.cleanup3, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond
+  %.lcssa10.lcssa = phi i16 [ %.lcssa10, %for.cond ]
+  %tmp3 = call i16 (i16) @func(i16 %.lcssa10.lcssa)
+  ret i16 0
+
+for.cond.cleanup3:                                ; preds = %for.cond
+  %.lcssa = phi i16 [ %tmp2, %for.cond ]
+  %inc9 = add i64 %i.0, 1
+  br label %for.cond
+}
+
+define i16 @partial_unroll(i16* %A) {
+; CHECK-LABEL: @partial_unroll(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[I_0:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INC9_2:%.*]], [[FOR_COND_CLEANUP3_2:%.*]] ]
+; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds i16, i16* [[A:%.*]], i64 [[I_0]]
+; CHECK-NEXT:    [[TMP2:%.*]] = load i16, i16* [[PTR]]
+; CHECK-NEXT:    br label [[FOR_COND_CLEANUP3:%.*]]
+; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    [[DOTLCSSA10_LCSSA:%.*]] = phi i16 [ [[TMP2_1:%.*]], [[FOR_COND_CLEANUP3_1:%.*]] ]
+; CHECK-NEXT:    [[TMP3:%.*]] = call i16 @func(i16 [[DOTLCSSA10_LCSSA]])
+; CHECK-NEXT:    ret i16 0
+; CHECK:       for.cond.cleanup3:
+; CHECK-NEXT:    [[INC9:%.*]] = add nuw nsw i64 [[I_0]], 1
+; CHECK-NEXT:    [[PTR_1:%.*]] = getelementptr inbounds i16, i16* [[A]], i64 [[INC9]]
+; CHECK-NEXT:    [[TMP2_1]] = load i16, i16* [[PTR_1]]
+; CHECK-NEXT:    br label [[FOR_COND_CLEANUP3_1]]
+; CHECK:       for.cond.cleanup3.1:
+; CHECK-NEXT:    [[INC9_1:%.*]] = add nuw nsw i64 [[INC9]], 1
+; CHECK-NEXT:    [[PTR_2:%.*]] = getelementptr inbounds i16, i16* [[A]], i64 [[INC9_1]]
+; CHECK-NEXT:    [[TMP2_2:%.*]] = load i16, i16* [[PTR_2]]
+; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ult i64 [[INC9_1]], 200
+; CHECK-NEXT:    br i1 [[CMP_2]], label [[FOR_COND_CLEANUP3_2]], label [[FOR_COND_CLEANUP:%.*]]
+; CHECK:       for.cond.cleanup3.2:
+; CHECK-NEXT:    [[INC9_2]] = add nuw nsw i64 [[INC9_1]], 1
+; CHECK-NEXT:    br label [[FOR_COND]]
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.cond.cleanup3, %entry
+  %.lcssa10 = phi i16 [ 123, %entry ], [ %.lcssa, %for.cond.cleanup3 ]
+  %i.0 = phi i64 [ 0, %entry ], [ %inc9, %for.cond.cleanup3 ]
+  %ptr = getelementptr inbounds i16, i16* %A, i64 %i.0
+  %tmp2 = load i16, i16* %ptr
+  %cmp = icmp ult i64 %i.0, 200
+  br i1 %cmp, label %for.cond.cleanup3, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond
+  %.lcssa10.lcssa = phi i16 [ %.lcssa10, %for.cond ]
+  %tmp3 = call i16 (i16) @func(i16 %.lcssa10.lcssa)
+  ret i16 0
+
+for.cond.cleanup3:                                ; preds = %for.cond
+  %.lcssa = phi i16 [ %tmp2, %for.cond ]
+  %inc9 = add i64 %i.0, 1
+  br label %for.cond
+}
+
+declare i16 @func(i16)
+