[LoopVersioning] Form dedicated exits for versioned loop to preserve simplify form

[TaWeiTu]

Summary

The exit blocks of the versioned and non-versioned loops are not dedicated and thus the two loops are not in simplify form.
Insert dummy exit blocks after loop versioning with formDedicatedExits() to preserve the simplify form for subsequence passes.

[aeubanks]

lgtm, but maybe somebody else should also take a look

[TaWeiTu]

Ping. Any comments from other reviewers? Thanks!

[aeubanks]

the new assert makes sense to me, if nobody else is taking a look feel free to submit

llvm/lib/Transforms/Utils/LoopVersioning.cpp

void LoopVersioning::versionLoop(
 
   // The loops merge in the original exit block.  This is now dominated by the
   // memchecking block.
   DT->changeImmediateDominator(VersionedLoop->getExitBlock(), RuntimeCheckBB);
 
   // Adds the necessary PHI nodes for the versioned loops based on the
   // loop-defined values used outside of the loop.
   addPHINodes(DefsUsedOutside);
+  formDedicatedExitBlocks(NonVersionedLoop, DT, LI, nullptr, true);
+  formDedicatedExitBlocks(VersionedLoop, DT, LI, nullptr, true);
+  assert(NonVersionedLoop->isLoopSimplifyForm() &&
+         VersionedLoop->isLoopSimplifyForm() &&
+         "The versioned loops should be in simplify form.");
 }
 
 void LoopVersioning::addPHINodes(
     const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
   BasicBlock *PHIBlock = VersionedLoop->getExitBlock();
   assert(PHIBlock && "No single successor to loop exit block");
   PHINode *PN;
 

llvm/test/Transforms/LoopDistribute/basic-with-memchecks.ll

 ; CHECK-NOT: = icmp
 ; CHECK:     br i1 %memcheck.conflict, label %for.body.ph.lver.orig, label %for.body.ph.ldist1
 
 ; The non-distributed loop that the memchecks fall back on.
 
 ; CHECK: for.body.ph.lver.orig:
 ; CHECK:     br label %for.body.lver.orig
 ; CHECK: for.body.lver.orig:
-; CHECK:    br i1 %exitcond.lver.orig, label %for.end, label %for.body.lver.orig
+; CHECK:    br i1 %exitcond.lver.orig, label %for.end.loopexit, label %for.body.lver.orig
 
 ; Verify the two distributed loops.
 
 ; CHECK: for.body.ph.ldist1:
 ; CHECK:     br label %for.body.ldist1
 ; CHECK: for.body.ldist1:
 ; CHECK:    %mulA.ldist1 = mul i32 %loadB.ldist1, %loadA.ldist1
 ; CHECK:    br i1 %exitcond.ldist1, label %for.body.ph, label %for.body.ldist1

llvm/test/Transforms/LoopDistribute/followup.ll

 !1 = !{!"llvm.loop.distribute.enable", i1 true}
 !2 = !{!"llvm.loop.distribute.followup_all", !{!"FollowupAll"}}
 !3 = !{!"llvm.loop.distribute.followup_coincident", !{!"FollowupCoincident", i1 false}}
 !4 = !{!"llvm.loop.distribute.followup_sequential", !{!"FollowupSequential", i32 8}}
 !5 = !{!"llvm.loop.distribute.followup_fallback", !{!"FollowupFallback"}}
 
 
 ; CHECK-LABEL: for.body.lver.orig:
-; CHECK: br i1 %exitcond.lver.orig, label %for.end, label %for.body.lver.orig, !llvm.loop ![[LOOP_ORIG:[0-9]+]]
+; CHECK: br i1 %exitcond.lver.orig, label %for.end.loopexit, label %for.body.lver.orig, !llvm.loop ![[LOOP_ORIG:[0-9]+]]
 ; CHECK-LABEL: for.body.ldist1:
 ; CHECK: br i1 %exitcond.ldist1, label %for.body.ph, label %for.body.ldist1, !llvm.loop ![[LOOP_SEQUENTIAL:[0-9]+]]
 ; CHECK-LABEL: for.body:
-; CHECK: br i1 %exitcond, label %for.end, label %for.body, !llvm.loop ![[LOOP_COINCIDENT:[0-9]+]]
+; CHECK: br i1 %exitcond, label %for.end.loopexit26, label %for.body, !llvm.loop ![[LOOP_COINCIDENT:[0-9]+]]
+; CHECK-LABEL: for.end.loopexit:
+; CHECK: br label %for.end
+; CHECK-LABEL: for.end.loopexit26:
+; CHECK: br label %for.end
 
 ; CHECK: ![[LOOP_ORIG]] = distinct !{![[LOOP_ORIG]], ![[FOLLOWUP_ALL:[0-9]+]], ![[FOLLOUP_FALLBACK:[0-9]+]]}
 ; CHECK: ![[FOLLOWUP_ALL]] = !{!"FollowupAll"}
 ; CHECK: ![[FOLLOUP_FALLBACK]] = !{!"FollowupFallback"}
 ; CHECK: ![[LOOP_SEQUENTIAL]] = distinct !{![[LOOP_SEQUENTIAL]], ![[FOLLOWUP_ALL]], ![[FOLLOWUP_SEQUENTIAL:[0-9]+]]}
 ; CHECK: ![[FOLLOWUP_SEQUENTIAL]] = !{!"FollowupSequential", i32 8}
 ; CHECK: ![[LOOP_COINCIDENT]] = distinct !{![[LOOP_COINCIDENT]], ![[FOLLOWUP_ALL]], ![[FOLLOWUP_COINCIDENT:[0-9]+]]}
 ; CHECK: ![[FOLLOWUP_COINCIDENT]] = !{!"FollowupCoincident", i1 false}

llvm/test/Transforms/LoopDistribute/outside-use.ll

entry:
 
   br label %for.body
 
 ; CHECK: for.body.ldist1:
 ; CHECK:   %mulA.ldist1 = mul i32 %loadB.ldist1, %loadA.ldist1
 ; CHECK: for.body.ph:
 ; CHECK: for.body:
 ; CHECK:   %sum_add = add nuw nsw i32 %sum, %loadC
+; CHECK: for.end.loopexit:
+; CHECK:   %sum_add.lver.ph = phi i32 [ %sum_add.lver.orig, %for.body.lver.orig ]
+; CHECK: for.end.loopexit6:
+; CHECK:   %sum_add.lver.ph7 = phi i32 [ %sum_add, %for.body ]
 ; CHECK: for.end:
-; CHECK:   %sum_add.lver = phi i32 [ %sum_add, %for.body ], [ %sum_add.lver.orig, %for.body.lver.orig ]
+; CHECK:   %sum_add.lver = phi i32 [ %sum_add.lver.ph, %for.end.loopexit ], [ %sum_add.lver.ph7, %for.end.loopexit6 ]
 
 for.body:                                         ; preds = %for.body, %entry
   %ind = phi i64 [ 0, %entry ], [ %add, %for.body ]
   %sum = phi i32 [ 0, %entry ], [ %sum_add, %for.body ]
 
   %arrayidxA = getelementptr inbounds i32, i32* %a, i64 %ind
   %loadA = load i32, i32* %arrayidxA, align 4
 

llvm/test/Transforms/LoopDistribute/scev-inserted-runtime-check.ll

 ; CHECK-NEXT:    [[ARRAYIDXD_LVER_ORIG:%.*]] = getelementptr inbounds i32, i32* [[D:%.*]], i64 [[MUL_EXT_LVER_ORIG]]
 ; CHECK-NEXT:    [[LOADD_LVER_ORIG:%.*]] = load i32, i32* [[ARRAYIDXD_LVER_ORIG]], align 4
 ; CHECK-NEXT:    [[ARRAYIDXE_LVER_ORIG:%.*]] = getelementptr inbounds i32, i32* [[E:%.*]], i64 [[MUL_EXT_LVER_ORIG]]
 ; CHECK-NEXT:    [[LOADE_LVER_ORIG:%.*]] = load i32, i32* [[ARRAYIDXE_LVER_ORIG]], align 4
 ; CHECK-NEXT:    [[MULC_LVER_ORIG:%.*]] = mul i32 [[LOADD_LVER_ORIG]], [[LOADE_LVER_ORIG]]
 ; CHECK-NEXT:    [[ARRAYIDXC_LVER_ORIG:%.*]] = getelementptr inbounds i32, i32* [[C:%.*]], i64 [[MUL_EXT_LVER_ORIG]]
 ; CHECK-NEXT:    store i32 [[MULC_LVER_ORIG]], i32* [[ARRAYIDXC_LVER_ORIG]], align 4
 ; CHECK-NEXT:    [[EXITCOND_LVER_ORIG:%.*]] = icmp eq i64 [[ADD_LVER_ORIG]], [[N]]
-; CHECK-NEXT:    br i1 [[EXITCOND_LVER_ORIG]], label [[FOR_END:%.*]], label [[FOR_BODY_LVER_ORIG]]
+; CHECK-NEXT:    br i1 [[EXITCOND_LVER_ORIG]], label %[[FOR_END1:.*]], label [[FOR_BODY_LVER_ORIG]]
 ; CHECK:       for.body.ph.ldist1:
 ; CHECK-NEXT:    br label [[FOR_BODY_LDIST1:%.*]]
 ; CHECK:       for.body.ldist1:
 ; CHECK-NEXT:    [[IND_LDIST1:%.*]] = phi i64 [ 0, [[FOR_BODY_PH_LDIST1]] ], [ [[ADD_LDIST1:%.*]], [[FOR_BODY_LDIST1]] ]
 ; CHECK-NEXT:    [[IND1_LDIST1:%.*]] = phi i32 [ 0, [[FOR_BODY_PH_LDIST1]] ], [ [[INC1_LDIST1:%.*]], [[FOR_BODY_LDIST1]] ]
 ; CHECK-NEXT:    [[MUL_LDIST1:%.*]] = mul i32 [[IND1_LDIST1]], 2
 ; CHECK-NEXT:    [[MUL_EXT_LDIST1:%.*]] = zext i32 [[MUL_LDIST1]] to i64
 ; CHECK-NEXT:    [[ARRAYIDXA_LDIST1:%.*]] = getelementptr inbounds i32, i32* [[A]], i64 [[MUL_EXT_LDIST1]]

 ; CHECK-NEXT:    [[ARRAYIDXD:%.*]] = getelementptr inbounds i32, i32* [[D]], i64 [[MUL_EXT]]
 ; CHECK-NEXT:    [[LOADD:%.*]] = load i32, i32* [[ARRAYIDXD]], align 4
 ; CHECK-NEXT:    [[ARRAYIDXE:%.*]] = getelementptr inbounds i32, i32* [[E]], i64 [[MUL_EXT]]
 ; CHECK-NEXT:    [[LOADE:%.*]] = load i32, i32* [[ARRAYIDXE]], align 4
 ; CHECK-NEXT:    [[MULC:%.*]] = mul i32 [[LOADD]], [[LOADE]]
 ; CHECK-NEXT:    [[ARRAYIDXC:%.*]] = getelementptr inbounds i32, i32* [[C]], i64 [[MUL_EXT]]
 ; CHECK-NEXT:    store i32 [[MULC]], i32* [[ARRAYIDXC]], align 4
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[ADD]], [[N]]
-; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END]], label [[FOR_BODY]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label %[[FOR_END2:.*]], label [[FOR_BODY]]
+; CHECK:       [[FOR_END1]]:
+; CHECK:         br label %for.end
+; CHECK:       [[FOR_END2]]:
+; CHECK:         br label %for.end
 ; CHECK:       for.end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %entry
   %ind = phi i64 [ 0, %entry ], [ %add, %for.body ]

llvm/test/Transforms/LoopVersioning/add-phi-update-users.ll

 ; for.end, when adding a new PHI node for the versioned loops based on the
 ; loop-defined values used outside of the loop.
 ;
 ; Verify that the code compiles, that we get a versioned loop, and that the
 ; uses of %t2 in for.end and if.then are updated to use the value from the
 ; added phi node.
 
 ; CHECK:       define void @f1
+; CHECK:       for.end.loopexit:
+; CHECK-NEXT:    %t2.lver.ph = phi i16 [ %t2.lver.orig, %for.body.lver.orig ]
+; CHECK:       for.end.loopexit2:
+; CHECK-NEXT:    %t2.lver.ph3 = phi i16 [ %t2, %for.body ]
 ; CHECK:       for.end:
-; CHECK-NEXT:    %t2.lver = phi i16 [ %t2, %for.body ], [ %t2.lver.orig, %for.body.lver.orig ]
+; CHECK-NEXT:    %t2.lver = phi i16 [ %t2.lver.ph, %for.end.loopexit ], [ %t2.lver.ph3, %for.end.loopexit2 ]
 ; CHECK-NEXT:    %tobool = icmp eq i16 %t2.lver, 0
 ; CHECK:       if.then:
 ; CHECK-NEXT:    store i16 %t2.lver
 
 @a = dso_local global i16 0, align 1
 @b = dso_local global i16 0, align 1
 @c = dso_local global i16* null, align 1
 

llvm/test/Transforms/LoopVersioning/basic.ll

 ; CHECK:   icmp
 ; CHECK:   icmp
 ; CHECK:   icmp
 ; CHECK-NOT: icmp
 ; CHECK:   br i1 %memcheck.conflict, label %for.body.ph.lver.orig, label %for.body.ph
 
 ; CHECK: for.body.ph.lver.orig:
 ; CHECK: for.body.lver.orig:
-; CHECK:   br i1 %exitcond.lver.orig, label %for.end, label %for.body.lver.orig
+; CHECK:   br i1 %exitcond.lver.orig, label %for.end.loopexit, label %for.body.lver.orig
 ; CHECK: for.body.ph:
 ; CHECK: for.body:
-; CHECK:   br i1 %exitcond, label %for.end, label %for.body
+; CHECK:   br i1 %exitcond, label %for.end.loopexit12, label %for.body
+; CHECK: for.end.loopexit:
+; CHECK:   br label %for.end
+; CHECK: for.end.loopexit12:
+; CHECK:   br label %for.end
 ; CHECK: for.end:
 
 for.body:                                         ; preds = %for.body, %entry
   %ind = phi i64 [ 0, %entry ], [ %add, %for.body ]
 
   %arrayidxA = getelementptr inbounds i32, i32* %a, i64 %ind
   %loadA = load i32, i32* %arrayidxA, align 4
 

llvm/test/Transforms/LoopVersioning/incorrect-phi.ll

bb6:                                              ; preds = %bb6.lr.ph, %bb6
   %_tmp130 = load i16, i16* %_tmp129
   store i16 undef, i16* getelementptr ([2 x [3 x [5 x i16]]], [2 x [3 x [5 x i16]]]* @x, i64 0, i64 undef, i64 undef, i64 undef)
   %_tmp142 = add i64 %_tmp1423, 1
   br i1 false, label %bb6, label %loop.exit
 
 loop.exit:                                ; preds = %bb6
   %_tmp142.lcssa = phi i64 [ %_tmp142, %bb6 ]
   %split = phi i16 [ undef, %bb6 ]
-; CHECK: %split = phi i16 [ undef, %bb6 ], [ undef, %bb6.lver.orig ]
+; CHECK: %split.ph = phi i16 [ undef, %bb6.lver.orig ]
+; CHECK: %split.ph3 = phi i16 [ undef, %bb6 ]
+; CHECK: %split = phi i16 [ %split.ph, %loop.exit.loopexit ], [ %split.ph3, %loop.exit.loopexit1 ]
   br label %bb9
 
 bb9:                                              ; preds = %bb9.loopexit, %bb1
   ret void
 }
 
 ; CHECK-LABEL: @phi_with_non_loop_defined_value
 define void @phi_with_non_loop_defined_value() {
bb6:                                              ; preds = %bb6.lr.ph, %bb6
   %_tmp130 = load i16, i16* %_tmp129
   store i16 undef, i16* getelementptr ([2 x [3 x [5 x i16]]], [2 x [3 x [5 x i16]]]* @x, i64 0, i64 undef, i64 undef, i64 undef)
   %_tmp142 = add i64 %_tmp1423, 1
   br i1 false, label %bb6, label %loop.exit
 
 loop.exit:                                ; preds = %bb6
   %_tmp142.lcssa = phi i64 [ %_tmp142, %bb6 ]
   %split = phi i16 [ %t, %bb6 ]
-; CHECK: %split = phi i16 [ %t, %bb6 ], [ %t, %bb6.lver.orig ]
+; CHECK: %split.ph = phi i16 [ %t, %bb6.lver.orig ]
+; CHECK: %split.ph3 = phi i16 [ %t, %bb6 ]
+; CHECK: %split = phi i16 [ %split.ph, %loop.exit.loopexit ], [ %split.ph3, %loop.exit.loopexit1 ]
   br label %bb9
 
 bb9:                                              ; preds = %bb9.loopexit, %bb1
   ret void
 }