Doomhowl-Interactive/llvm-project
0
0
Fork 0
Code Issues Pull Requests Actions 5 Packages Projects Releases Wiki Activity
Files
main
llvm-project/llvm/test/Transforms/IndVarSimplify/loop-guard-order.ll
Florian Hahn d3fe1df194 [SCEV] Improve handling of divisibility information from loop guards. (#163021) 
At the moment, the effectivness of guards that contain divisibility
information (A % B == 0 ) depends on the order of the conditions.

This patch makes using divisibility information independent of the
order, by collecting and applying the divisibility information
separately.

We first collect all conditions in a vector, then collect the
divisibility information from all guards.

When processing other guards, we apply divisibility info collected
earlier.

After all guards have been processed, we add the divisibility info,
rewriting the existing rewrite. This ensures we apply the divisibility
info to the largest rewrite expression.

This helps to improve results in a few cases, one in
https://github.com/dtcxzyw/llvm-opt-benchmark/pull/2921 and another one
in a different large C/C++ based IR corpus.

PR: https://github.com/llvm/llvm-project/pull/163021
2025-11-02 14:16:24 +00:00

299 lines
11 KiB
LLVM
Raw Permalink Blame History

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 5
; RUN: opt -p indvars -S %s | FileCheck %s
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
declare void @foo()
define void @narrow_iv_precondition_order_1(ptr %start, i32 %base, i8 %n) {
; CHECK-LABEL: define void @narrow_iv_precondition_order_1(
; CHECK-SAME: ptr [[START:%.*]], i32 [[BASE:%.*]], i8 [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*:]]
; CHECK-NEXT: [[PRE_0:%.*]] = icmp sgt i32 [[BASE]], 0
; CHECK-NEXT: br i1 [[PRE_0]], label %[[EXIT:.*]], label %[[PH:.*]]
; CHECK: [[PH]]:
; CHECK-NEXT: [[N_EXT:%.*]] = zext i8 [[N]] to i32
; CHECK-NEXT: [[PRE_1:%.*]] = icmp sgt i32 [[BASE]], [[N_EXT]]
; CHECK-NEXT: br i1 [[PRE_1]], label %[[LOOP_PREHEADER:.*]], label %[[EXIT]]
; CHECK: [[LOOP_PREHEADER]]:
; CHECK-NEXT: br label %[[LOOP:.*]]
; CHECK: [[LOOP]]:
; CHECK-NEXT: [[IV:%.*]] = phi ptr [ [[GEP:%.*]], %[[LOOP]] ], [ [[START]], %[[LOOP_PREHEADER]] ]
; CHECK-NEXT: call void @foo()
; CHECK-NEXT: [[END:%.*]] = load i8, ptr [[IV]], align 1
; CHECK-NEXT: [[END_EXT:%.*]] = zext i8 [[END]] to i32
; CHECK-NEXT: [[GEP]] = getelementptr inbounds i8, ptr [[IV]], i64 1
; CHECK-NEXT: [[EC:%.*]] = icmp sgt i32 [[BASE]], [[END_EXT]]
; CHECK-NEXT: br i1 [[EC]], label %[[LOOP]], label %[[EXIT_LOOPEXIT:.*]]
; CHECK: [[EXIT_LOOPEXIT]]:
; CHECK-NEXT: br label %[[EXIT]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
%pre.0 = icmp sgt i32 %base, 0
br i1 %pre.0, label %exit, label %ph
ph: ; preds = %entry
%n.ext = zext i8 %n to i32
%pre.1 = icmp sgt i32 %base, %n.ext
br i1 %pre.1, label %loop, label %exit
loop:
%iv = phi ptr [ %start, %ph ], [ %gep, %loop ]
call void @foo()
%end = load i8, ptr %iv, align 1
%end.ext = zext i8 %end to i32
%gep = getelementptr inbounds i8, ptr %iv, i64 1
%ec = icmp sgt i32 %base, %end.ext
br i1 %ec, label %loop, label %exit
exit:
ret void
}
define void @narrow_iv_precondition_order_2(ptr %start, i32 %base, i8 %n) {
; CHECK-LABEL: define void @narrow_iv_precondition_order_2(
; CHECK-SAME: ptr [[START:%.*]], i32 [[BASE:%.*]], i8 [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*:]]
; CHECK-NEXT: [[N_EXT:%.*]] = zext i8 [[N]] to i32
; CHECK-NEXT: [[PRE_1:%.*]] = icmp sgt i32 [[BASE]], [[N_EXT]]
; CHECK-NEXT: br i1 [[PRE_1]], label %[[EXIT:.*]], label %[[PH:.*]]
; CHECK: [[PH]]:
; CHECK-NEXT: [[PRE_0:%.*]] = icmp sgt i32 [[BASE]], 0
; CHECK-NEXT: br i1 [[PRE_0]], label %[[LOOP_PREHEADER:.*]], label %[[EXIT]]
; CHECK: [[LOOP_PREHEADER]]:
; CHECK-NEXT: [[TMP0:%.*]] = trunc i32 [[BASE]] to i8
; CHECK-NEXT: br label %[[LOOP:.*]]
; CHECK: [[LOOP]]:
; CHECK-NEXT: [[IV:%.*]] = phi ptr [ [[GEP:%.*]], %[[LOOP]] ], [ [[START]], %[[LOOP_PREHEADER]] ]
; CHECK-NEXT: call void @foo()
; CHECK-NEXT: [[END:%.*]] = load i8, ptr [[IV]], align 1
; CHECK-NEXT: [[GEP]] = getelementptr inbounds i8, ptr [[IV]], i64 1
; CHECK-NEXT: [[EC:%.*]] = icmp ugt i8 [[TMP0]], [[END]]
; CHECK-NEXT: br i1 [[EC]], label %[[LOOP]], label %[[EXIT_LOOPEXIT:.*]]
; CHECK: [[EXIT_LOOPEXIT]]:
; CHECK-NEXT: br label %[[EXIT]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
%n.ext = zext i8 %n to i32
%pre.1 = icmp sgt i32 %base, %n.ext
br i1 %pre.1, label %exit, label %ph
ph: ; preds = %entry
%pre.0 = icmp sgt i32 %base, 0
br i1 %pre.0, label %loop, label %exit
loop:
%iv = phi ptr [ %start, %ph ], [ %gep, %loop ]
call void @foo()
%end = load i8, ptr %iv, align 1
%end.ext = zext i8 %end to i32
%gep = getelementptr inbounds i8, ptr %iv, i64 1
%ec = icmp sgt i32 %base, %end.ext
br i1 %ec, label %loop, label %exit
exit:
ret void
}
define i32 @urem_order1(i32 %n) {
; CHECK-LABEL: define i32 @urem_order1(
; CHECK-SAME: i32 [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[UREM:%.*]] = urem i32 [[N]], 3
; CHECK-NEXT: [[UREM_ZERO:%.*]] = icmp eq i32 [[UREM]], 0
; CHECK-NEXT: br i1 [[UREM_ZERO]], label %[[PH:.*]], label %[[EXIT:.*]]
; CHECK: [[PH]]:
; CHECK-NEXT: [[N_NON_ZERO:%.*]] = icmp ne i32 [[N]], 0
; CHECK-NEXT: br i1 [[N_NON_ZERO]], label %[[LOOP_PREHEADER:.*]], label %[[EXIT]]
; CHECK: [[LOOP_PREHEADER]]:
; CHECK-NEXT: br label %[[LOOP:.*]]
; CHECK: [[LOOP]]:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], %[[LOOP]] ], [ 0, %[[LOOP_PREHEADER]] ]
; CHECK-NEXT: call void @foo()
; CHECK-NEXT: [[IV_NEXT]] = add nuw i32 [[IV]], 3
; CHECK-NEXT: [[EC:%.*]] = icmp eq i32 [[IV_NEXT]], [[N]]
; CHECK-NEXT: br i1 [[EC]], label %[[EXIT_LOOPEXIT:.*]], label %[[LOOP]]
; CHECK: [[EXIT_LOOPEXIT]]:
; CHECK-NEXT: br label %[[EXIT]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: [[RES:%.*]] = phi i32 [ 1, %[[ENTRY]] ], [ 2, %[[PH]] ], [ 3, %[[EXIT_LOOPEXIT]] ]
; CHECK-NEXT: ret i32 [[RES]]
;
entry:
%urem = urem i32 %n, 3
%urem.zero = icmp eq i32 %urem, 0
br i1 %urem.zero, label %ph, label %exit
ph:
%n.non.zero = icmp ne i32 %n, 0
br i1 %n.non.zero, label %loop, label %exit
loop:
%iv = phi i32 [ 0, %ph ], [ %iv.next, %loop ]
call void @foo()
%iv.next = add i32 %iv, 3
%ec = icmp eq i32 %iv.next, %n
br i1 %ec, label %exit, label %loop
exit:
%res = phi i32 [ 1, %entry ], [ 2, %ph ], [ 3, %loop ]
ret i32 %res
}
define i32 @urem_order2(i32 %n) {
; CHECK-LABEL: define i32 @urem_order2(
; CHECK-SAME: i32 [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[N_NON_ZERO:%.*]] = icmp ne i32 [[N]], 0
; CHECK-NEXT: br i1 [[N_NON_ZERO]], label %[[PH:.*]], label %[[EXIT:.*]]
; CHECK: [[PH]]:
; CHECK-NEXT: [[UREM:%.*]] = urem i32 [[N]], 3
; CHECK-NEXT: [[UREM_ZERO:%.*]] = icmp eq i32 [[UREM]], 0
; CHECK-NEXT: br i1 [[UREM_ZERO]], label %[[LOOP_PREHEADER:.*]], label %[[EXIT]]
; CHECK: [[LOOP_PREHEADER]]:
; CHECK-NEXT: br label %[[LOOP:.*]]
; CHECK: [[LOOP]]:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], %[[LOOP]] ], [ 0, %[[LOOP_PREHEADER]] ]
; CHECK-NEXT: call void @foo()
; CHECK-NEXT: [[IV_NEXT]] = add nuw i32 [[IV]], 3
; CHECK-NEXT: [[EC:%.*]] = icmp eq i32 [[IV_NEXT]], [[N]]
; CHECK-NEXT: br i1 [[EC]], label %[[EXIT_LOOPEXIT:.*]], label %[[LOOP]]
; CHECK: [[EXIT_LOOPEXIT]]:
; CHECK-NEXT: br label %[[EXIT]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: [[RES:%.*]] = phi i32 [ 1, %[[ENTRY]] ], [ 2, %[[PH]] ], [ 3, %[[EXIT_LOOPEXIT]] ]
; CHECK-NEXT: ret i32 [[RES]]
;
entry:
%n.non.zero = icmp ne i32 %n, 0
br i1 %n.non.zero, label %ph, label %exit
ph:
%urem = urem i32 %n, 3
%urem.zero = icmp eq i32 %urem, 0
br i1 %urem.zero, label %loop, label %exit
loop:
%iv = phi i32 [ 0, %ph ], [ %iv.next, %loop ]
call void @foo()
%iv.next = add i32 %iv, 3
%ec = icmp eq i32 %iv.next, %n
br i1 %ec, label %exit, label %loop
exit:
%res = phi i32 [ 1, %entry ], [ 2, %ph ], [ 3, %loop ]
ret i32 %res
}
define i64 @test_loop_with_div_order_1(i64 %n) {
; CHECK-LABEL: define i64 @test_loop_with_div_order_1(
; CHECK-SAME: i64 [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*:]]
; CHECK-NEXT: [[IS_ZERO:%.*]] = icmp eq i64 [[N]], 0
; CHECK-NEXT: br i1 [[IS_ZERO]], label %[[EXIT:.*]], label %[[CHECK_BOUNDS:.*]]
; CHECK: [[CHECK_BOUNDS]]:
; CHECK-NEXT: [[N_PLUS_63:%.*]] = add i64 [[N]], 63
; CHECK-NEXT: [[UPPER_BOUND:%.*]] = lshr i64 [[N_PLUS_63]], 6
; CHECK-NEXT: [[BOUNDS_CHECK:%.*]] = icmp ult i64 [[N_PLUS_63]], 64
; CHECK-NEXT: br i1 [[BOUNDS_CHECK]], label %[[EXIT]], label %[[CHECK_PARITY:.*]]
; CHECK: [[CHECK_PARITY]]:
; CHECK-NEXT: [[IS_ODD:%.*]] = and i64 [[N]], 1
; CHECK-NEXT: [[PARITY_CHECK:%.*]] = icmp eq i64 [[IS_ODD]], 0
; CHECK-NEXT: br i1 [[PARITY_CHECK]], label %[[LOOP_PREHEADER:.*]], label %[[EXIT]]
; CHECK: [[LOOP_PREHEADER]]:
; CHECK-NEXT: br label %[[LOOP:.*]]
; CHECK: [[LOOP]]:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], %[[LOOP]] ], [ 0, %[[LOOP_PREHEADER]] ]
; CHECK-NEXT: [[DUMMY:%.*]] = load volatile i64, ptr null, align 8
; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i64 [[IV_NEXT]], [[UPPER_BOUND]]
; CHECK-NEXT: br i1 [[EXITCOND]], label %[[LOOP]], label %[[EXIT_LOOPEXIT:.*]]
; CHECK: [[EXIT_LOOPEXIT]]:
; CHECK-NEXT: br label %[[EXIT]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret i64 0
;
entry:
%is_zero = icmp eq i64 %n, 0
br i1 %is_zero, label %exit, label %check_bounds
check_bounds:
%n_plus_63 = add i64 %n, 63
%upper_bound = lshr i64 %n_plus_63, 6
%bounds_check = icmp ult i64 %n_plus_63, 64
br i1 %bounds_check, label %exit, label %check_parity
check_parity:
%is_odd = and i64 %n, 1
%parity_check = icmp eq i64 %is_odd, 0
br i1 %parity_check, label %loop, label %exit
loop:
%iv = phi i64 [ %iv_next, %loop ], [ 0, %check_parity ]
%dummy = load volatile i64, ptr null, align 8
%iv_next = add i64 %iv, 1
%exit_cond = icmp ult i64 %iv_next, %upper_bound
br i1 %exit_cond, label %loop, label %exit
exit:
ret i64 0
}
define i64 @test_loop_with_div_order_2(i64 %n) {
; CHECK-LABEL: define i64 @test_loop_with_div_order_2(
; CHECK-SAME: i64 [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*:]]
; CHECK-NEXT: [[N_PLUS_63:%.*]] = add i64 [[N]], 63
; CHECK-NEXT: [[UPPER_BOUND:%.*]] = lshr i64 [[N_PLUS_63]], 6
; CHECK-NEXT: [[BOUNDS_CHECK:%.*]] = icmp ult i64 [[N_PLUS_63]], 64
; CHECK-NEXT: br i1 [[BOUNDS_CHECK]], label %[[EXIT:.*]], label %[[CHECK_BOUNDS:.*]]
; CHECK: [[CHECK_BOUNDS]]:
; CHECK-NEXT: [[IS_ZERO:%.*]] = icmp eq i64 [[N]], 0
; CHECK-NEXT: br i1 [[IS_ZERO]], label %[[EXIT]], label %[[CHECK_PARITY:.*]]
; CHECK: [[CHECK_PARITY]]:
; CHECK-NEXT: [[IS_ODD:%.*]] = and i64 [[N]], 1
; CHECK-NEXT: [[PARITY_CHECK:%.*]] = icmp eq i64 [[IS_ODD]], 0
; CHECK-NEXT: br i1 [[PARITY_CHECK]], label %[[LOOP_PREHEADER:.*]], label %[[EXIT]]
; CHECK: [[LOOP_PREHEADER]]:
; CHECK-NEXT: br label %[[LOOP:.*]]
; CHECK: [[LOOP]]:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], %[[LOOP]] ], [ 0, %[[LOOP_PREHEADER]] ]
; CHECK-NEXT: [[DUMMY:%.*]] = load volatile i64, ptr null, align 8
; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i64 [[IV_NEXT]], [[UPPER_BOUND]]
; CHECK-NEXT: br i1 [[EXITCOND]], label %[[LOOP]], label %[[EXIT_LOOPEXIT:.*]]
; CHECK: [[EXIT_LOOPEXIT]]:
; CHECK-NEXT: br label %[[EXIT]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret i64 0
;
entry:
%n_plus_63 = add i64 %n, 63
%upper_bound = lshr i64 %n_plus_63, 6
%bounds_check = icmp ult i64 %n_plus_63, 64
br i1 %bounds_check, label %exit, label %check_bounds
check_bounds:
%is_zero = icmp eq i64 %n, 0
br i1 %is_zero, label %exit, label %check_parity
check_parity:
%is_odd = and i64 %n, 1
%parity_check = icmp eq i64 %is_odd, 0
br i1 %parity_check, label %loop, label %exit
loop:
%iv = phi i64 [ %iv_next, %loop ], [ 0, %check_parity ]
%dummy = load volatile i64, ptr null, align 8
%iv_next = add i64 %iv, 1
%exit_cond = icmp ult i64 %iv_next, %upper_bound
br i1 %exit_cond, label %loop, label %exit
exit:
ret i64 0
}
Reference in New Issue View Git Blame Copy Permalink