[GuardWidening] Add tests showing the incorrect behavior of GW wrt poison

[skatkov]

Summary

The first test shows that combineRangeChecks may choose to keep only two poison conditions.
And we cannot do simple arithmetic or logical and in guard.
The second test shows that even in simple test we can hoist a poison and even logical and does not help here.

[mkazantsev]

llvm/test/Transforms/GuardWidening/posion.ll

15

nit: considers

17

nit: consider then -> considers them

23

please add FIXME into the comment

74

I don't quite get it. COND_0 here is not poison, why would logical and not help?

[mkazantsev]

I didn't quite get what's the problem with 2nd example and logical and, but the first example is more than enough to admit it's a bug.

[skatkov]

llvm/test/Transforms/GuardWidening/posion.ll

74

Consider a = 5, b = -1
b.shift and cond2 are poison
a u< 10
So with logical and the result of select is posion.
guard on poison is UB.

In original program check in the loop b u< 10 protects us from the execution the guard in ok block on poison value - so no UB.

[mkazantsev]

Pls add test with side effect that we've discussed offline.

[skatkov]

Add test with side effect for combine range checks.

[skatkov]

handle nits.

[skatkov]

Landed.

llvm/test/Transforms/GuardWidening/posion.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -guard-widening -dce < %s | FileCheck %s
+
+; FIXME: All the tests below must be fixed.
+
+declare void @llvm.experimental.guard(i1,...)
+
+; This tests shows the incorrect behavior of guard widening in terms of
+; interaction with poison values.
+
+; Let x incoming parameter is used for rane checks.
+; Test generates 5 checks. One of them (c2) is used to get the corretness
+; of nuw/nsw flags for x3 and x5. Others are used in guards and represent
+; the checks x + 10 u< L, x + 15 u< L, x + 20 u< L and x + 3 u< L.
+; The first two checks are in the first basic block and guard widening
+; considers them as profitable to combine.
+; When c4 and c3 are considered, number of check becomes more than two
+; and combineRangeCheck consider them as profitable even if they are in
+; different basic blocks.
+; Accoding to algorithm of combineRangeCheck it detects that c3 and c4
+; are enough to cover c1 and c5, so it ends up with guard of c3 && c4
+; while both of them are poison at entry. This is a bug.
+
+define void @combine_range_checks(i32 %x) {
+; CHECK-LABEL: @combine_range_checks(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[X2:%.*]] = add i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[C2:%.*]] = icmp ult i32 [[X2]], 200
+; CHECK-NEXT:    [[X3:%.*]] = add nuw nsw i32 [[X]], 3
+; CHECK-NEXT:    [[C3:%.*]] = icmp ult i32 [[X3]], 100
+; CHECK-NEXT:    [[X4:%.*]] = add nuw nsw i32 [[X]], 20
+; CHECK-NEXT:    [[C4:%.*]] = icmp ult i32 [[X4]], 100
+; CHECK-NEXT:    [[WIDE_CHK2:%.*]] = and i1 [[C4]], [[C3]]
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK2]]) [ "deopt"(i64 1) ]
+; CHECK-NEXT:    br i1 [[C2]], label [[OK:%.*]], label [[OUT:%.*]]
+; CHECK:       ok:
+; CHECK-NEXT:    br label [[OUT]]
+; CHECK:       out:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %x1 = add i32 %x, 10
+  %c1 = icmp ult i32 %x1, 100
+  %x2 = add i32 %x, 0
+  %c2 = icmp ult i32 %x2, 200
+  %x3 = add nuw nsw i32 %x, 3
+  %c3 = icmp ult i32 %x3, 100
+  %x4 = add nuw nsw i32 %x, 20
+  %c4 = icmp ult i32 %x4, 100
+  %x5 = add i32 %x, 15
+  %c5 = icmp ult i32 %x5, 100
+  call void(i1, ...) @llvm.experimental.guard(i1 %c1) [ "deopt"(i64 1) ]
+  call void(i1, ...) @llvm.experimental.guard(i1 %c5) [ "deopt"(i64 5) ]
+  br i1 %c2, label %ok, label %out
+ok:
+  call void(i1, ...) @llvm.experimental.guard(i1 %c4) [ "deopt"(i64 4) ]
+  call void(i1, ...) @llvm.experimental.guard(i1 %c3) [ "deopt"(i64 3) ]
+  br label %out
+out:
+  ret void
+}
+
+; This is similar to @combine_range_checks but shows that simple freeze
+; over c3 and c4 will not help due to with X = SMAX_INT, guard with c1 will
+; go to deoptimization. But after guard widening freeze of c3 and c4 may return
+; true due to c3 and c4 are poisons and we pass guard executing side effect store
+; which never been executed in original program.
+define void @combine_range_checks_with_side_effect(i32 %x, i32* %p) {
+; CHECK-LABEL: @combine_range_checks_with_side_effect(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[X2:%.*]] = add i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[C2:%.*]] = icmp ult i32 [[X2]], 200
+; CHECK-NEXT:    [[X3:%.*]] = add nuw nsw i32 [[X]], 3
+; CHECK-NEXT:    [[C3:%.*]] = icmp ult i32 [[X3]], 100
+; CHECK-NEXT:    [[X4:%.*]] = add nuw nsw i32 [[X]], 20
+; CHECK-NEXT:    [[C4:%.*]] = icmp ult i32 [[X4]], 100
+; CHECK-NEXT:    [[WIDE_CHK2:%.*]] = and i1 [[C4]], [[C3]]
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK2]]) [ "deopt"(i64 1) ]
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]], align 4
+; CHECK-NEXT:    br i1 [[C2]], label [[OK:%.*]], label [[OUT:%.*]]
+; CHECK:       ok:
+; CHECK-NEXT:    br label [[OUT]]
+; CHECK:       out:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %x1 = add i32 %x, 10
+  %c1 = icmp ult i32 %x1, 100
+  %x2 = add i32 %x, 0
+  %c2 = icmp ult i32 %x2, 200
+  %x3 = add nuw nsw i32 %x, 3
+  %c3 = icmp ult i32 %x3, 100
+  %x4 = add nuw nsw i32 %x, 20
+  %c4 = icmp ult i32 %x4, 100
+  %x5 = add i32 %x, 15
+  %c5 = icmp ult i32 %x5, 100
+  call void(i1, ...) @llvm.experimental.guard(i1 %c1) [ "deopt"(i64 1) ]
+  call void(i1, ...) @llvm.experimental.guard(i1 %c5) [ "deopt"(i64 5) ]
+  store i32 0, i32* %p
+  br i1 %c2, label %ok, label %out
+ok:
+  call void(i1, ...) @llvm.experimental.guard(i1 %c4) [ "deopt"(i64 4) ]
+  call void(i1, ...) @llvm.experimental.guard(i1 %c3) [ "deopt"(i64 3) ]
+  br label %out
+out:
+  ret void
+}
+
+
+; The test shows the bug in guard widening. Critical pieces.
+; There is a %cond_1 check which provides the correctness of nuw nsw in %b.shift.
+; %b.shift and %cond_2 are poisons and after guard widening it leads to UB
+; for both arithmetic and logcal and.
+define void @simple_case(i32 %a, i32 %b, i1 %cnd) {
+; CHECK-LABEL: @simple_case(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[COND_0:%.*]] = icmp ult i32 [[A:%.*]], 10
+; CHECK-NEXT:    [[B_SHIFT:%.*]] = add nuw nsw i32 [[B:%.*]], 5
+; CHECK-NEXT:    [[COND_2:%.*]] = icmp ult i32 [[B_SHIFT]], 10
+; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0]], [[COND_2]]
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[COND_1:%.*]] = icmp ult i32 [[B]], 10
+; CHECK-NEXT:    br i1 [[COND_1]], label [[OK:%.*]], label [[LEAVE_LOOPEXIT:%.*]]
+; CHECK:       ok:
+; CHECK-NEXT:    br i1 [[CND:%.*]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
+; CHECK:       leave.loopexit:
+; CHECK-NEXT:    br label [[LEAVE:%.*]]
+; CHECK:       leave:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cond_0 = icmp ult i32 %a, 10
+  %b.shift = add nuw nsw i32 %b, 5
+  %cond_2 = icmp ult i32 %b.shift, 10
+  call void (i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+  br label %loop
+
+loop:
+  %cond_1 = icmp ult i32 %b, 10
+  br i1 %cond_1, label %ok, label %leave.loopexit
+ok:
+  call void (i1, ...) @llvm.experimental.guard(i1 %cond_2) [ "deopt"() ]
+  br i1 %cnd, label %loop, label %leave.loopexit
+
+leave.loopexit:
+  br label %leave
+
+leave:
+  ret void
+}