shylie/llvm-project
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
llvm-project/llvm/test/Transforms/ConstraintElimination/loops-header-tested-base.ll
Florian Hahn fbcf8a8cbb
[ConstraintElim] Add (UGE, var, 0) to unsigned system for new vars. (#76262) 
The constraint system used for ConstraintElimination assumes all
varibles to be signed. This can cause missed optimization in the
unsigned system, due to missing the information that all variables are
unsigned (non-negative).

Variables can be marked as non-negative by adding Var >= 0 for all
variables. This is done for arguments on ConstraintInfo construction and
after adding new variables. This handles cases like the ones outlined in
https://discourse.llvm.org/t/why-does-llvm-not-perform-range-analysis-on-integer-values/74341

The original example shared above is now handled without this change,
but adding another variable means that instcombine won't be able to
simplify examples like https://godbolt.org/z/hTnra7zdY

Adding the extra variables comes with a slight compile-time increase
https://llvm-compile-time-tracker.com/compare.php?from=7568b36a2bc1a1e496ec29246966ffdfc3a8b87f&to=641a47f0acce7755e340447386013a2e086f03d9&stat=instructions:u

stage1-O3    stage1-ReleaseThinLTO    stage1-ReleaseLTO-g  stage1-O0-g
 +0.04%           +0.07%                   +0.05%           +0.02%
stage2-O3    stage2-O0-g    stage2-clang
  +0.05%         +0.05%        +0.05%

https://github.com/llvm/llvm-project/pull/76262
2023-12-23 15:53:48 +01:00

421 lines
13 KiB
LLVM
Raw Permalink Blame History

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -passes=constraint-elimination -S %s | FileCheck %s
declare void @use(i1)
define void @loop_phi_pos_start_value(i32 %y, i1 %c, i32 %n) {
; CHECK-LABEL: @loop_phi_pos_start_value(
; CHECK-NEXT: entry:
; CHECK-NEXT: br i1 [[C:%.*]], label [[LOOP_HEADER:%.*]], label [[EXIT:%.*]]
; CHECK: loop.header:
; CHECK-NEXT: [[X:%.*]] = phi i32 [ 10, [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
; CHECK-NEXT: [[C_1:%.*]] = icmp slt i32 [[X]], [[N:%.*]]
; CHECK-NEXT: br i1 [[C_1]], label [[LOOP_LATCH]], label [[EXIT]]
; CHECK: loop.latch:
; CHECK-NEXT: call void @use(i1 true)
; CHECK-NEXT: call void @use(i1 false)
; CHECK-NEXT: [[T_2:%.*]] = icmp sge i32 [[X]], 10
; CHECK-NEXT: call void @use(i1 [[T_2]])
; CHECK-NEXT: [[C_2:%.*]] = icmp sle i32 [[X]], 9
; CHECK-NEXT: call void @use(i1 [[C_2]])
; CHECK-NEXT: [[C_3:%.*]] = icmp sgt i32 [[X]], 9
; CHECK-NEXT: call void @use(i1 [[C_3]])
; CHECK-NEXT: call void @use(i1 true)
; CHECK-NEXT: [[C_5:%.*]] = icmp sge i32 [[X]], 9
; CHECK-NEXT: call void @use(i1 [[C_5]])
; CHECK-NEXT: [[X_NEXT]] = add nsw i32 [[X]], 1
; CHECK-NEXT: br label [[LOOP_HEADER]]
; CHECK: exit:
; CHECK-NEXT: [[C_6:%.*]] = icmp sgt i32 [[Y:%.*]], 10
; CHECK-NEXT: call void @use(i1 [[C_6]])
; CHECK-NEXT: ret void
;
entry:
br i1 %c, label %loop.header, label %exit
loop.header:
%x = phi i32 [ 10, %entry ], [ %x.next, %loop.latch ]
%c.1 = icmp slt i32 %x, %n
br i1 %c.1, label %loop.latch, label %exit
loop.latch:
%f.1 = icmp sle i32 %x, %n
call void @use(i1 %f.1)
%t.1 = icmp sgt i32 %x, %n
call void @use(i1 %t.1)
%t.2 = icmp sge i32 %x, 10
call void @use(i1 %t.2)
%c.2 = icmp sle i32 %x, 9
call void @use(i1 %c.2)
%c.3 = icmp sgt i32 %x, 9
call void @use(i1 %c.3)
%c.4 = icmp sge i32 %x, 0
call void @use(i1 %c.4)
%c.5 = icmp sge i32 %x, 9
call void @use(i1 %c.5)
%x.next = add nsw i32 %x, 1
br label %loop.header
exit:
%c.6 = icmp sgt i32 %y, 10
call void @use(i1 %c.6)
ret void
}
define void @loop_phi_neg_start_value(i32 %y, i1 %c, i32 %n) {
; CHECK-LABEL: @loop_phi_neg_start_value(
; CHECK-NEXT: entry:
; CHECK-NEXT: br i1 [[C:%.*]], label [[LOOP_HEADER:%.*]], label [[EXIT:%.*]]
; CHECK: loop.header:
; CHECK-NEXT: [[X:%.*]] = phi i32 [ -10, [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
; CHECK-NEXT: [[C_1:%.*]] = icmp slt i32 [[X]], [[N:%.*]]
; CHECK-NEXT: br i1 [[C_1]], label [[LOOP_LATCH]], label [[EXIT]]
; CHECK: loop.latch:
; CHECK-NEXT: call void @use(i1 true)
; CHECK-NEXT: call void @use(i1 false)
; CHECK-NEXT: [[T_2:%.*]] = icmp sge i32 [[X]], -10
; CHECK-NEXT: call void @use(i1 [[T_2]])
; CHECK-NEXT: [[C_2:%.*]] = icmp sle i32 [[X]], 9
; CHECK-NEXT: call void @use(i1 [[C_2]])
; CHECK-NEXT: [[C_3:%.*]] = icmp sgt i32 [[X]], 9
; CHECK-NEXT: call void @use(i1 [[C_3]])
; CHECK-NEXT: [[C_4:%.*]] = icmp sge i32 [[X]], 0
; CHECK-NEXT: call void @use(i1 [[C_4]])
; CHECK-NEXT: [[C_5:%.*]] = icmp sge i32 [[X]], 9
; CHECK-NEXT: call void @use(i1 [[C_5]])
; CHECK-NEXT: [[X_NEXT]] = add nsw i32 [[X]], 1
; CHECK-NEXT: br label [[LOOP_HEADER]]
; CHECK: exit:
; CHECK-NEXT: [[C_6:%.*]] = icmp sgt i32 [[Y:%.*]], 10
; CHECK-NEXT: call void @use(i1 [[C_6]])
; CHECK-NEXT: ret void
;
entry:
br i1 %c, label %loop.header, label %exit
loop.header:
%x = phi i32 [ -10, %entry ], [ %x.next, %loop.latch ]
%c.1 = icmp slt i32 %x, %n
br i1 %c.1, label %loop.latch, label %exit
loop.latch:
%f.1 = icmp sle i32 %x, %n
call void @use(i1 %f.1)
%t.1 = icmp sgt i32 %x, %n
call void @use(i1 %t.1)
%t.2 = icmp sge i32 %x, -10
call void @use(i1 %t.2)
%c.2 = icmp sle i32 %x, 9
call void @use(i1 %c.2)
%c.3 = icmp sgt i32 %x, 9
call void @use(i1 %c.3)
%c.4 = icmp sge i32 %x, 0
call void @use(i1 %c.4)
%c.5 = icmp sge i32 %x, 9
call void @use(i1 %c.5)
%x.next = add nsw i32 %x, 1
br label %loop.header
exit:
%c.6 = icmp sgt i32 %y, 10
call void @use(i1 %c.6)
ret void
}
define void @loop_count_down(i32 %y, i1 %c, i32 %n) {
; CHECK-LABEL: @loop_count_down(
; CHECK-NEXT: entry:
; CHECK-NEXT: br i1 [[C:%.*]], label [[LOOP_HEADER:%.*]], label [[EXIT:%.*]]
; CHECK: loop.header:
; CHECK-NEXT: [[X:%.*]] = phi i32 [ [[N:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
; CHECK-NEXT: [[C_1:%.*]] = icmp sge i32 [[X]], 0
; CHECK-NEXT: br i1 [[C_1]], label [[LOOP_LATCH]], label [[EXIT]]
; CHECK: loop.latch:
; CHECK-NEXT: [[F_1:%.*]] = icmp sle i32 [[X]], [[N]]
; CHECK-NEXT: call void @use(i1 [[F_1]])
; CHECK-NEXT: [[T_1:%.*]] = icmp sgt i32 [[X]], [[N]]
; CHECK-NEXT: call void @use(i1 [[T_1]])
; CHECK-NEXT: call void @use(i1 true)
; CHECK-NEXT: call void @use(i1 true)
; CHECK-NEXT: [[C_2:%.*]] = icmp sle i32 [[X]], 9
; CHECK-NEXT: call void @use(i1 [[C_2]])
; CHECK-NEXT: [[C_3:%.*]] = icmp sgt i32 [[X]], 9
; CHECK-NEXT: call void @use(i1 [[C_3]])
; CHECK-NEXT: [[C_4:%.*]] = icmp sge i32 [[X]], 1
; CHECK-NEXT: call void @use(i1 [[C_4]])
; CHECK-NEXT: [[C_5:%.*]] = icmp sge i32 [[X]], 2
; CHECK-NEXT: call void @use(i1 [[C_5]])
; CHECK-NEXT: [[X_NEXT]] = add nsw i32 [[X]], 1
; CHECK-NEXT: br label [[LOOP_HEADER]]
; CHECK: exit:
; CHECK-NEXT: [[C_6:%.*]] = icmp sgt i32 [[Y:%.*]], 10
; CHECK-NEXT: call void @use(i1 [[C_6]])
; CHECK-NEXT: ret void
;
entry:
br i1 %c, label %loop.header, label %exit
loop.header:
%x = phi i32 [ %n, %entry ], [ %x.next, %loop.latch ]
%c.1 = icmp sge i32 %x, 0
br i1 %c.1, label %loop.latch, label %exit
loop.latch:
%f.1 = icmp sle i32 %x, %n
call void @use(i1 %f.1)
%t.1 = icmp sgt i32 %x, %n
call void @use(i1 %t.1)
%t.2 = icmp sge i32 %x, 0
call void @use(i1 %t.2)
%t.3 = icmp sge i32 %x, -1
call void @use(i1 %t.3)
%c.2 = icmp sle i32 %x, 9
call void @use(i1 %c.2)
%c.3 = icmp sgt i32 %x, 9
call void @use(i1 %c.3)
%c.4 = icmp sge i32 %x, 1
call void @use(i1 %c.4)
%c.5 = icmp sge i32 %x, 2
call void @use(i1 %c.5)
%x.next = add nsw i32 %x, 1
br label %loop.header
exit:
%c.6 = icmp sgt i32 %y, 10
call void @use(i1 %c.6)
ret void
}
define void @loop_latch_may_not_executed(i32 %y, i1 %c, i32 %n) {
; CHECK-LABEL: @loop_latch_may_not_executed(
; CHECK-NEXT: entry:
; CHECK-NEXT: br i1 [[C:%.*]], label [[LOOP_HEADER:%.*]], label [[EXIT:%.*]]
; CHECK: loop.header:
; CHECK-NEXT: [[X:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
; CHECK-NEXT: [[C_1:%.*]] = icmp ugt i32 [[X]], [[N:%.*]]
; CHECK-NEXT: br i1 [[C_1]], label [[LOOP_LATCH]], label [[EXIT]]
; CHECK: loop.latch:
; CHECK-NEXT: call void @use(i1 false)
; CHECK-NEXT: call void @use(i1 true)
; CHECK-NEXT: [[C_2:%.*]] = icmp ule i32 [[X]], 9
; CHECK-NEXT: call void @use(i1 [[C_2]])
; CHECK-NEXT: [[C_3:%.*]] = icmp ugt i32 [[X]], 9
; CHECK-NEXT: call void @use(i1 [[C_3]])
; CHECK-NEXT: [[X_NEXT]] = add i32 [[X]], 1
; CHECK-NEXT: br label [[LOOP_HEADER]]
; CHECK: exit:
; CHECK-NEXT: [[C_4:%.*]] = icmp ugt i32 [[Y:%.*]], 10
; CHECK-NEXT: call void @use(i1 [[C_4]])
; CHECK-NEXT: ret void
;
entry:
br i1 %c, label %loop.header, label %exit
loop.header:
%x = phi i32 [ 0, %entry ], [ %x.next, %loop.latch ]
%c.1 = icmp ugt i32 %x, %n
br i1 %c.1, label %loop.latch, label %exit
loop.latch:
%f.1 = icmp ule i32 %x, %n
call void @use(i1 %f.1)
%t.1 = icmp ugt i32 %x, %n
call void @use(i1 %t.1)
%c.2 = icmp ule i32 %x, 9
call void @use(i1 %c.2)
%c.3 = icmp ugt i32 %x, 9
call void @use(i1 %c.3)
%x.next = add i32 %x, 1
br label %loop.header
exit:
%c.4 = icmp ugt i32 %y, 10
call void @use(i1 %c.4)
ret void
}
define void @loop_latch_not_executed_constant_bound(i32 %y, i1 %c) {
; CHECK-LABEL: @loop_latch_not_executed_constant_bound(
; CHECK-NEXT: entry:
; CHECK-NEXT: br i1 [[C:%.*]], label [[LOOP_HEADER:%.*]], label [[EXIT:%.*]]
; CHECK: loop.header:
; CHECK-NEXT: [[X:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
; CHECK-NEXT: [[C_1:%.*]] = icmp ugt i32 [[X]], 10
; CHECK-NEXT: br i1 [[C_1]], label [[LOOP_LATCH]], label [[EXIT]]
; CHECK: loop.latch:
; CHECK-NEXT: call void @use(i1 false)
; CHECK-NEXT: call void @use(i1 true)
; CHECK-NEXT: call void @use(i1 false)
; CHECK-NEXT: call void @use(i1 true)
; CHECK-NEXT: [[X_NEXT]] = add i32 [[X]], 1
; CHECK-NEXT: br label [[LOOP_HEADER]]
; CHECK: exit:
; CHECK-NEXT: [[C_4:%.*]] = icmp ugt i32 [[Y:%.*]], 10
; CHECK-NEXT: call void @use(i1 [[C_4]])
; CHECK-NEXT: ret void
;
entry:
br i1 %c, label %loop.header, label %exit
loop.header:
%x = phi i32 [ 0, %entry ], [ %x.next, %loop.latch ]
%c.1 = icmp ugt i32 %x, 10
br i1 %c.1, label %loop.latch, label %exit
loop.latch:
%t.1 = icmp ule i32 %x, 10
call void @use(i1 %t.1)
%f.1 = icmp ugt i32 %x, 10
call void @use(i1 %f.1)
%c.2 = icmp ule i32 %x, 9
call void @use(i1 %c.2)
%c.3 = icmp ugt i32 %x, 9
call void @use(i1 %c.3)
%x.next = add i32 %x, 1
br label %loop.header
exit:
%c.4 = icmp ugt i32 %y, 10
call void @use(i1 %c.4)
ret void
}
define void @loop_iv_cond_variable_bound(i32 %n) {
; CHECK-LABEL: @loop_iv_cond_variable_bound(
; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[LOOP_HEADER:%.*]]
; CHECK: loop.header:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
; CHECK-NEXT: [[T_1:%.*]] = icmp ule i32 [[IV]], [[N:%.*]]
; CHECK-NEXT: call void @use(i1 [[T_1]])
; CHECK-NEXT: [[T_2:%.*]] = icmp sge i32 [[IV]], 0
; CHECK-NEXT: call void @use(i1 [[T_2]])
; CHECK-NEXT: [[T_3:%.*]] = icmp sge i32 [[IV]], -1
; CHECK-NEXT: call void @use(i1 [[T_3]])
; CHECK-NEXT: [[C_1:%.*]] = icmp ult i32 [[IV]], [[N]]
; CHECK-NEXT: call void @use(i1 [[C_1]])
; CHECK-NEXT: [[C_2:%.*]] = icmp ugt i32 [[IV]], 1
; CHECK-NEXT: call void @use(i1 [[C_2]])
; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[IV]], [[N]]
; CHECK-NEXT: br i1 [[CMP]], label [[LOOP_LATCH]], label [[EXIT:%.*]]
; CHECK: loop.latch:
; CHECK-NEXT: call void @use(i1 true)
; CHECK-NEXT: [[C_3:%.*]] = icmp ult i32 [[IV]], 2
; CHECK-NEXT: call void @use(i1 [[C_3]])
; CHECK-NEXT: [[C_4:%.*]] = icmp ugt i32 [[IV]], 1
; CHECK-NEXT: call void @use(i1 [[C_4]])
; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
; CHECK-NEXT: br label [[LOOP_HEADER]]
; CHECK: exit:
; CHECK-NEXT: ret void
;
entry:
br label %loop.header
loop.header:
%iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ]
%t.1 = icmp ule i32 %iv, %n
call void @use(i1 %t.1)
%t.2 = icmp sge i32 %iv, 0
call void @use(i1 %t.2)
%t.3 = icmp sge i32 %iv, -1
call void @use(i1 %t.3)
%c.1 = icmp ult i32 %iv, %n
call void @use(i1 %c.1)
%c.2 = icmp ugt i32 %iv, 1
call void @use(i1 %c.2)
%cmp = icmp ult i32 %iv, %n
br i1 %cmp, label %loop.latch, label %exit
loop.latch:
%t.4 = icmp ule i32 %iv, %n
call void @use(i1 %t.4)
%c.3 = icmp ult i32 %iv, 2
call void @use(i1 %c.3)
%c.4 = icmp ugt i32 %iv, 1
call void @use(i1 %c.4)
%iv.next = add nuw nsw i32 %iv, 1
br label %loop.header
exit:
ret void
}
define void @loop_iv_cond_constant_bound() {
; CHECK-LABEL: @loop_iv_cond_constant_bound(
; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[LOOP_HEADER:%.*]]
; CHECK: loop.header:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
; CHECK-NEXT: [[T_1:%.*]] = icmp ule i32 [[IV]], 2
; CHECK-NEXT: call void @use(i1 [[T_1]])
; CHECK-NEXT: [[T_2:%.*]] = icmp sge i32 [[IV]], 0
; CHECK-NEXT: call void @use(i1 [[T_2]])
; CHECK-NEXT: [[T_3:%.*]] = icmp sge i32 [[IV]], -1
; CHECK-NEXT: call void @use(i1 [[T_3]])
; CHECK-NEXT: [[C_1:%.*]] = icmp ult i32 [[IV]], 2
; CHECK-NEXT: call void @use(i1 [[C_1]])
; CHECK-NEXT: [[C_2:%.*]] = icmp ugt i32 [[IV]], 1
; CHECK-NEXT: call void @use(i1 [[C_2]])
; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[IV]], 2
; CHECK-NEXT: br i1 [[CMP]], label [[LOOP_LATCH]], label [[EXIT:%.*]]
; CHECK: loop.latch:
; CHECK-NEXT: call void @use(i1 true)
; CHECK-NEXT: call void @use(i1 true)
; CHECK-NEXT: call void @use(i1 false)
; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
; CHECK-NEXT: br label [[LOOP_HEADER]]
; CHECK: exit:
; CHECK-NEXT: ret void
;
entry:
br label %loop.header
loop.header:
%iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ]
%t.1 = icmp ule i32 %iv, 2
call void @use(i1 %t.1)
%t.2 = icmp sge i32 %iv, 0
call void @use(i1 %t.2)
%t.3 = icmp sge i32 %iv, -1
call void @use(i1 %t.3)
%c.1 = icmp ult i32 %iv, 2
call void @use(i1 %c.1)
%c.2 = icmp ugt i32 %iv, 1
call void @use(i1 %c.2)
%cmp = icmp ult i32 %iv, 2
br i1 %cmp, label %loop.latch, label %exit
loop.latch:
%t.4 = icmp ule i32 %iv, 2
call void @use(i1 %t.4)
%c.3 = icmp ult i32 %iv, 2
call void @use(i1 %c.3)
%c.4 = icmp ugt i32 %iv, 1
call void @use(i1 %c.4)
%iv.next = add nuw nsw i32 %iv, 1
br label %loop.header
exit:
ret void
}
Reference in New Issue View Git Blame Copy Permalink