80 lines · plain
1; RUN: opt < %s -S -passes=loop-unroll -unroll-runtime=true -unroll-count=4 | FileCheck %s2 3;; Check that the remainder loop is properly assigned a branch weight for its latch branch.4; CHECK-LABEL: @test(5; CHECK-LABEL: entry:6; CHECK: [[FOR_BODY_PREHEADER:.*]]:7; CHECK: br i1 %{{.*}}, label %[[FOR_BODY_EPIL_PREHEADER:.*]], label %[[FOR_BODY_PREHEADER_NEW:.*]], !prof ![[#PROF_UR_GUARD:]]8; CHECK: [[FOR_BODY_PREHEADER_NEW]]:9; CHECK: br label %for.body10; CHECK: for.body:11; CHECK: %add = add12; CHECK: %add.1 = add13; CHECK: %add.2 = add14; CHECK: %add.3 = add15; CHECK-NOT: %add.4 = add16; CHECK: br i1 %{{.*}}, label %[[FOR_END_LOOPEXIT_UNR_LCSSA:.*]], label %for.body, !prof ![[#PROF_UR_LATCH:]], !llvm.loop ![[#LOOP_UR_LATCH:]]17; CHECK: [[FOR_END_LOOPEXIT_UNR_LCSSA]]:18; CHECK: br i1 %{{.*}}, label %[[FOR_BODY_EPIL_PREHEADER]], label %[[FOR_END_LOOPEXIT:.*]], !prof ![[#PROF_RM_GUARD:]]19; CHECK: [[FOR_BODY_EPIL_PREHEADER]]:20; CHECK: br label %[[FOR_BODY_EPIL:.*]]21; CHECK: [[FOR_BODY_EPIL]]:22; CHECK: br i1 {{.*}}, label %[[FOR_BODY_EPIL]], label %[[FOR_END_LOOPEXIT_EPILOG_LCSSA:.*]], !prof ![[#PROF_RM_LATCH:]], !llvm.loop ![[#LOOP_RM_LATCH:]]23 24define i3 @test(ptr %a, i3 %n) {25entry:26 %cmp1 = icmp eq i3 %n, 027 br i1 %cmp1, label %for.end, label %for.body28 29for.body:30 %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]31 %sum.02 = phi i3 [ %add, %for.body ], [ 0, %entry ]32 %arrayidx = getelementptr inbounds i3, ptr %a, i64 %indvars.iv33 %0 = load i3, ptr %arrayidx34 %add = add nsw i3 %0, %sum.0235 %indvars.iv.next = add i64 %indvars.iv, 136 %lftr.wideiv = trunc i64 %indvars.iv.next to i337 %exitcond = icmp eq i3 %lftr.wideiv, %n38 br i1 %exitcond, label %for.end, label %for.body, !prof !039 40for.end:41 %sum.0.lcssa = phi i3 [ 0, %entry ], [ %add, %for.body ]42 ret i3 %sum.0.lcssa43}44 45!0 = !{!"branch_weights", i32 1, i32 9999}46 47; Original loop probability: p = 9999/(1+9999) = 0.999948; Original estimated trip count: (1+9999)/1 = 1000049; Unroll count: 450 51; Probability of >=3 iterations after first: p^3 = 0.9970003 =~52; 2146839468 / (644180 + 2146839468).53; CHECK: ![[#PROF_UR_GUARD]] = !{!"branch_weights", i32 644180, i32 2146839468}54 55; Probability of >=4 more iterations: p^4 = 0.99960006 =~56; 2146624784 / (858864 + 2146624784).57; CHECK: ![[#PROF_UR_LATCH]] = !{!"branch_weights", i32 858864, i32 2146624784}58 59; 10000//4 = 250060; CHECK: ![[#LOOP_UR_LATCH]] = distinct !{![[#LOOP_UR_LATCH]], ![[#LOOP_UR_TC:]], ![[#DISABLE:]]}61; CHECK: ![[#LOOP_UR_TC]] = !{!"llvm.loop.estimated_trip_count", i32 2500}62;63; CHECK: ![[#DISABLE]] = !{!"llvm.loop.unroll.disable"}64 65; Probability of 1 to 3 more of 3 more remainder iterations:66; (p-p^4)/(1-p^4) = 0.749962497 =~ 1610532724 / (1610532724 + 536950924).67; CHECK: ![[#PROF_RM_GUARD]] = !{!"branch_weights", i32 1610532724, i32 536950924}68 69; Frequency of first remainder iter: r1 = 170; Frequency of second remainder iter: r2 = r1*(p-p^3)/(1-p^3) = 0.66663333171; Frequency of third remainder iter: r3 = r2*(p-p^2)/(1-p^2) = 0.33329999972; Solve for loop probability that produces that frequency: f = 1/(1-p') =>73; p' = 1-1/f = 1-1/(r1+r2+r3) = 0.499983332 =~74; 1073706403 / (1073706403 + 1073777245).75; CHECK: ![[#PROF_RM_LATCH]] = !{!"branch_weights", i32 1073706403, i32 1073777245}76 77; 10000%4 = 078; CHECK: ![[#LOOP_RM_LATCH]] = distinct !{![[#LOOP_RM_LATCH]], ![[#LOOP_RM_TC:]], ![[#DISABLE:]]}79; CHECK: ![[#LOOP_RM_TC]] = !{!"llvm.loop.estimated_trip_count", i32 0}80