[IRCE][Test] Add test to constrain a loop bounded by phi

[aleksandr.popov]

Summary

Added an example when IRCE can't parse a loop bounded by phi, due to
unsafe loop bounds. But it's possible to prove that bounds are safe, by
improving ScalarEvolution

phi(a,b) != 0
a >= 0
b >= 0
------>
phi(a,b) > 0

[mkazantsev]

llvm/unittests/Analysis/ScalarEvolutionTest.cpp

1749 ↗

(On Diff #500682)

addrspace(1) is not needed here.

1787 ↗

(On Diff #500682)

(void) LHS, RHS to avoid dead code warning?

[nikic]

Is there any way to make this an analysis / IR test instead?

[mkazantsev]

High-level comment: if you expect that SCEV is able to prove equivalence of loads, you need it to be able to prove aliasing facts, which I belive it cannot do. It need to somehow know that no one stores to this memory on any posible path from one load to another. Or maybe it can, but I've never seen it doing things like this.

[mkazantsev]

In D144845#4154391, @nikic wrote:

Is there any way to make this an analysis / IR test instead?

I believe there is a motivating example coming from IRCE. @aleksandr.popov can we add it too?

[aleksandr.popov]

Yep, that's true, will try to add IR test instead

[aleksandr.popov]

I've updated the test in IR form

[mkazantsev]

llvm/test/Transforms/IRCE/constrain_loop_with_phi_bound.ll

2

; REQUIRES: asserts

7

I don't quite understand the example here. Call can return different values every time. IRCE is supposed to generate a loop-invariant check. How it would look like?

[mkazantsev]

llvm/test/Transforms/IRCE/constrain_loop_with_phi_bound.ll

7

Ok, we are IRCEing inner loop. Looks fine then.

Maybe auto-generated checks instead or IRCE's output? Use update_test_checks.py.

[aleksandr.popov]

llvm/test/Transforms/IRCE/constrain_loop_with_phi_bound.ll

7

Thanks, done

llvm/test/Transforms/IRCE/constrain_loop_with_phi_bound.ll

+; RUN: opt -passes=irce -irce-print-range-checks -irce-print-changed-loops -S < %s 2>&1 | FileCheck %s
+
+declare i32 @bar()
+
+; TODO: Prove that inner loop L1 is guarded by cond '0 <s x' to constrain it by IRCE
+; Inner's loop bound is %x = phi i32 [ %x01, %L0.preheader ], [ %x02, %L0.latch ]
+; We know that:
+; - x != 0
+; - x01 >=s 0
+; - x02 >=s 0
+; Hense: x >s 0
+; CHECK: irce: looking at loop Loop at depth 2 containing: %L1.header<header><exiting>,%L1.latch<latch><exiting>
+; CHECK-NEXT: irce: loop has 1 inductive range checks:
+; CHECK-NEXT: InductiveRangeCheck:
+; CHECK-NEXT:   Begin: 0  Step: 1  End: %n
+; CHECK-NEXT:   CheckUse:   br i1 %cmp2, label %L1.latch, label %L1.exit Operand: 0
+define void @test_constrain_loop_with_phi_bound(i32 %n) {
+; CHECK-LABEL: define void @test_constrain_loop_with_phi_bound
+; CHECK-SAME: (i32 [[N:%.*]]) {
+; CHECK-NEXT:  Entry:
+; CHECK-NEXT:    [[X01:%.*]] = call i32 @bar()
+; CHECK-NEXT:    [[CMP0:%.*]] = icmp slt i32 [[X01]], 0
+; CHECK-NEXT:    br i1 [[CMP0]], label [[EXIT:%.*]], label [[L0_PREHEADER:%.*]]
+; CHECK:       L0.preheader:
+; CHECK-NEXT:    br label [[L0_HEADER:%.*]]
+; CHECK:       L0.header:
+; CHECK-NEXT:    [[X:%.*]] = phi i32 [ [[X01]], [[L0_PREHEADER]] ], [ [[X02:%.*]], [[L0_LATCH:%.*]] ]
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[X]], 0
+; CHECK-NEXT:    br i1 [[CMP1]], label [[L0_EXIT:%.*]], label [[L1_PREHEADER:%.*]]
+; CHECK:       L1.preheader:
+; CHECK-NEXT:    br label [[L1_HEADER:%.*]]
+; CHECK:       L1.header:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[L1_PREHEADER]] ], [ [[IV_NEXT:%.*]], [[L1_LATCH:%.*]] ]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[IV]], [[N]]
+; CHECK-NEXT:    br i1 [[CMP2]], label [[L1_LATCH]], label [[L1_EXIT:%.*]]
+; CHECK:       L1.latch:
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
+; CHECK-NEXT:    [[CMP3:%.*]] = icmp slt i32 [[IV_NEXT]], [[X]]
+; CHECK-NEXT:    br i1 [[CMP3]], label [[L1_HEADER]], label [[L0_LATCH]]
+; CHECK:       L1.exit:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       L0.latch:
+; CHECK-NEXT:    [[X02]] = call i32 @bar()
+; CHECK-NEXT:    [[CMP4:%.*]] = icmp slt i32 [[X02]], 0
+; CHECK-NEXT:    br i1 [[CMP4]], label [[L0_EXIT]], label [[L0_HEADER]]
+; CHECK:       L0.exit:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       Exit:
+; CHECK-NEXT:    ret void
+;
+Entry:
+  %x01 = call i32 @bar()
+  %cmp0 = icmp slt i32 %x01, 0
+  br i1 %cmp0, label %Exit, label %L0.preheader
+
+L0.preheader:
+  br label %L0.header
+
+L0.header:
+  %x = phi i32 [ %x01, %L0.preheader ], [ %x02, %L0.latch ]
+  %cmp1 = icmp eq i32 %x, 0
+  br i1 %cmp1, label %L0.exit, label %L1.preheader
+
+L1.preheader:
+  br label %L1.header
+
+L1.header:
+  %iv = phi i32 [ 0, %L1.preheader ], [ %iv.next, %L1.latch ]
+  %cmp2 = icmp ult i32 %iv, %n
+  br i1 %cmp2, label %L1.latch, label %L1.exit
+
+L1.latch:
+  %iv.next = add nuw nsw i32 %iv, 1
+  %cmp3 = icmp slt i32 %iv.next, %x
+  br i1 %cmp3, label %L1.header, label %L0.latch
+
+L1.exit:
+  br label %Exit
+
+L0.latch:
+  %x02 = call i32 @bar()
+  %cmp4 = icmp slt i32 %x02, 0
+  br i1 %cmp4, label %L0.exit, label %L0.header
+
+L0.exit:
+  br label %Exit
+
+Exit:
+  ret void
+}