111 lines · plain
1; RUN: opt < %s -S -passes=loop-unroll -unroll-runtime -unroll-threshold=40 -unroll-max-percent-threshold-boost=100 | FileCheck %s2 3@known_constant = internal unnamed_addr constant [9 x i32] [i32 0, i32 -1, i32 0, i32 -1, i32 5, i32 -1, i32 0, i32 -1, i32 0], align 164 5; CHECK-LABEL: @bar_prof6; CHECK: entry:7; CHECK: br i1 %{{.*}}, label %[[LOOP_EPIL_PREHEADER:.*]], label %[[ENTRY_NEW:.*]], !prof ![[#PROF_UR_GUARD:]]8; CHECK: [[ENTRY_NEW]]:9; CHECK: br label %loop10; CHECK: loop:11; CHECK: %mul = mul12; CHECK: %mul.1 = mul13; CHECK: %mul.2 = mul14; CHECK: %mul.3 = mul15; CHECK: %mul.4 = mul16; CHECK: %mul.5 = mul17; CHECK: %mul.6 = mul18; CHECK: %mul.7 = mul19; CHECK-NOT: %mul.8 = mul20; CHECK: br i1 %{{.*}}, label %[[LOOP_END_UNR_LCSSA:.*]], label %loop, !prof ![[#PROF_UR_LATCH:]], !llvm.loop ![[#LOOP_UR_LATCH:]]21; CHECK: [[LOOP_END_UNR_LCSSA]]:22; CHECK: br i1 %{{.*}}, label %[[LOOP_EPIL_PREHEADER]], label %loop.end, !prof ![[#PROF_RM_GUARD:]]23; CHECK: [[LOOP_EPIL_PREHEADER]]:24; CHECK: br label %[[LOOP_EPIL:.*]]25; CHECK: [[LOOP_EPIL]]:26; CHECK: br i1 %{{.*}}, label %[[LOOP_EPIL]], label %[[LOOP_END_EPILOG_LCSSA:.*]], !prof ![[#PROF_RM_LATCH:]], !llvm.loop ![[#LOOP_RM_LATCH:]]27define i32 @bar_prof(ptr noalias nocapture readonly %src, i64 %c) !prof !1 {28entry:29 br label %loop30 31loop:32 %iv = phi i64 [ 0, %entry ], [ %inc, %loop ]33 %r = phi i32 [ 0, %entry ], [ %add, %loop ]34 %arrayidx = getelementptr inbounds i32, ptr %src, i64 %iv35 %src_element = load i32, ptr %arrayidx, align 436 %array_const_idx = getelementptr inbounds [9 x i32], ptr @known_constant, i64 0, i64 %iv37 %const_array_element = load i32, ptr %array_const_idx, align 438 %mul = mul nsw i32 %src_element, %const_array_element39 %add = add nsw i32 %mul, %r40 %inc = add nuw nsw i64 %iv, 141 %exitcond86.i = icmp eq i64 %inc, %c42 br i1 %exitcond86.i, label %loop.end, label %loop, !prof !243 44loop.end:45 %r.lcssa = phi i32 [ %r, %loop ]46 ret i32 %r.lcssa47}48 49; CHECK-LABEL: @bar_prof_flat50; CHECK-NOT: loop.epil51define i32 @bar_prof_flat(ptr noalias nocapture readonly %src, i64 %c) !prof !1 {52entry:53 br label %loop54 55loop:56 %iv = phi i64 [ 0, %entry ], [ %inc, %loop ]57 %r = phi i32 [ 0, %entry ], [ %add, %loop ]58 %arrayidx = getelementptr inbounds i32, ptr %src, i64 %iv59 %src_element = load i32, ptr %arrayidx, align 460 %array_const_idx = getelementptr inbounds [9 x i32], ptr @known_constant, i64 0, i64 %iv61 %const_array_element = load i32, ptr %array_const_idx, align 462 %mul = mul nsw i32 %src_element, %const_array_element63 %add = add nsw i32 %mul, %r64 %inc = add nuw nsw i64 %iv, 165 %exitcond86.i = icmp eq i64 %inc, %c66 br i1 %exitcond86.i, label %loop, label %loop.end, !prof !267 68loop.end:69 %r.lcssa = phi i32 [ %r, %loop ]70 ret i32 %r.lcssa71}72 73!1 = !{!"function_entry_count", i64 1}74!2 = !{!"branch_weights", i32 1, i32 1000}75 76; Original loop probability: p = 1000/(1+1000) = 0.99900099977; Original estimated trip count: (1+1000)/1 = 100178; Unroll count: 879 80; Probability of >=7 iterations after first: p^7 = 0.993027916 =~81; 2132511214 / (14972434 + 2132511214).82; CHECK: ![[#PROF_UR_GUARD]] = !{!"branch_weights", i32 14972434, i32 2132511214}83 84; Probability of >=8 more iterations: p^8 = 0.99203588 =~85; 2130380833 / (17102815 + 2130380833).86; CHECK: ![[#PROF_UR_LATCH]] = !{!"branch_weights", i32 17102815, i32 2130380833}87 88; 1001//8 = 12589; CHECK: ![[#LOOP_UR_LATCH]] = distinct !{![[#LOOP_UR_LATCH]], ![[#LOOP_UR_TC:]]}90; CHECK: ![[#LOOP_UR_TC]] = !{!"llvm.loop.estimated_trip_count", i32 125}91 92; Probability of 1 to 7 more of 7 more remainder iterations:93; (p-p^8)/(1-p^8) = 0.874562282 =~ 1878108210 / (1878108210 + 269375438).94; CHECK: ![[#PROF_RM_GUARD]] = !{!"branch_weights", i32 1878108210, i32 269375438}95 96; Frequency of first remainder iter: r1 = 197; Frequency of second remainder iter: r2 = r1*(p-p^7)/(1-p^7) = 0.85671414398; Frequency of third remainder iter: r3 = r2*(p-p^6)/(1-p^6) = 0.71357142999; Frequency of fourth remainder iter: r4 = r2*(p-p^5)/(1-p^5) = 0.570571715100; Frequency of fifth remainder iter: r5 = r2*(p-p^4)/(1-p^4) = 0.427714858101; Frequency of sixth remainder iter: r6 = r2*(p-p^3)/(1-p^3) = 0.285000715102; Frequency of seventh remainder iter: r7 = r2*(p-p^2)/(1-p^2) = 0.142429143103; Solve for loop probability that produces that frequency: f = 1/(1-p') =>104; p' = 1-1/f = 1-1/(r1+r2+r3+r4+r5+r6+r7) = 0.749749875 =~105; 1610075606 / (1610075606 + 537408042).106; CHECK: ![[#PROF_RM_LATCH]] = !{!"branch_weights", i32 1610075606, i32 537408042}107 108; Remainder estimated trip count: 1001%8 = 1109; CHECK: ![[#LOOP_RM_LATCH]] = distinct !{![[#LOOP_RM_LATCH]], ![[#LOOP_RM_TC:]], ![[#DISABLE:]]}110; CHECK: ![[#LOOP_RM_TC]] = !{!"llvm.loop.estimated_trip_count", i32 1}111