60d9e6fba8
IRCE currently has two profitability checks: 1. min number of iterations (10 by default) 2. branch is highly biased (> 15/16) However, it may still be profitable to eliminate range checks even if the branch isn't as biased. Consider, for example, a loop with 100 iterations, where IRCE currently eliminates all 100 range checks. The same range checks performed over a loop with 200 iterations aren't eliminated because the branch is 50-50. This patch proposes to relax the profitability checks of IRCE. Namely, instead of the two checks currenly in place, consider IRCE profitable if the branch probability scaled by the expected number of iterations (i.e., the estimated number of eliminated checks) is over a threshold. This covers the minimum number of iterations check (there are at least as many iterations as eliminated range checks), and changes the bias check from a percent of iterations to at least a constant threshold of eliminated checks. If the number of iterations can't be estimated, the check falls back to the current 15/16 likelihood check.
44 lines
1.4 KiB
LLVM
44 lines
1.4 KiB
LLVM
; RUN: opt -verify-loop-info -irce-print-changed-loops -passes=irce -irce-min-eliminated-checks=3 < %s 2>&1 | FileCheck %s --check-prefixes=CHECK-NO
|
|
; RUN: opt -verify-loop-info -irce-print-changed-loops -passes=irce -irce-min-eliminated-checks=0 < %s 2>&1 | FileCheck %s --check-prefixes=CHECK-YES
|
|
|
|
; CHECK-YES: constrained Loop
|
|
; CHECK-NO-NOT: constrained Loop
|
|
|
|
define i32 @multiple_access_no_preloop(
|
|
ptr %arr_a, ptr %a_len_ptr, ptr %arr_b, ptr %b_len_ptr, i32 %n) {
|
|
|
|
entry:
|
|
%len.a = load i32, ptr %a_len_ptr, !range !0
|
|
%first.itr.check = icmp sgt i32 %n, 0
|
|
br i1 %first.itr.check, label %loop, label %exit, !prof !1
|
|
|
|
loop:
|
|
%idx = phi i32 [ 0, %entry ] , [ %idx.next, %backedge ]
|
|
%idx.next = add i32 %idx, 1
|
|
%abc.a = icmp slt i32 %idx, %len.a
|
|
br i1 %abc.a, label %in.bounds.a, label %exit, !prof !2
|
|
|
|
in.bounds.a:
|
|
%addr.a = getelementptr i32, ptr %arr_a, i32 %idx
|
|
%val = load i32, ptr %addr.a
|
|
%cond = icmp ne i32 %val, 0
|
|
; Most probable exit from a loop.
|
|
br i1 %cond, label %found, label %backedge, !prof !3
|
|
|
|
backedge:
|
|
%next = icmp slt i32 %idx.next, %n
|
|
br i1 %next, label %loop, label %exit, !prof !4
|
|
|
|
found:
|
|
ret i32 %val
|
|
|
|
exit:
|
|
ret i32 0
|
|
}
|
|
|
|
!0 = !{i32 0, i32 2147483647}
|
|
!1 = !{!"branch_weights", i32 1024, i32 1}
|
|
!2 = !{!"branch_weights", i32 512, i32 1}
|
|
!3 = !{!"branch_weights", i32 1, i32 2}
|
|
!4 = !{!"branch_weights", i32 512, i32 1}
|