[PM/LoopUnswitch] Fix PR37651 by correctly invalidating SCEV when

unswitching loops.

Original patch trying to address this was sent in D47624, but that
didn't quite handle things correctly. There are two key principles used
to select whether and how to invalidate SCEV-cached information about
loops:

1) We must invalidate any info SCEV has cached before unswitching as we
   may change (or destroy) the loop structure by the act of unswitching,
   and make it hard to recover everything we want to invalidate within
   SCEV.

2) We need to invalidate all of the loops whose CFGs are mutated by the
   unswitching. Notably, this isn't the *entire* loop nest, this is
   every loop contained by the outermost loop reached by an exit block
   relevant to the unswitch.

And we need to do this even when doing trivial unswitching.

I've added more focused tests that directly check that SCEV starts off
with imprecise information and after unswitching (and simplifying
instructions) re-querying SCEV will produce precise information. These
tests also specifically work to check that an *outer* loop's information
becomes precise.

However, the testing here is still a bit imperfect. Crafting test cases
that reliably fail to be analyzed by SCEV before unswitching and succeed
afterward proved ... very, very hard. It took me several hours and
careful work to build these, and I'm not optimistic about necessarily
coming up with more to cover more elaborate possibilities. Fortunately,
the code pattern we are testing here in the pass is really
straightforward and reliable.

Thanks to Max Kazantsev for the initial work on this as well as the
review, and to Hal Finkel for helping me talk through approaches to test
this stuff even if it didn't come to much.

Differential Revision: https://reviews.llvm.org/D47624

llvm-svn: 336183

1 files changed, 188 insertions, 0 deletions

diff --git a/llvm/test/Transforms/SimpleLoopUnswitch/update-scev.ll b/llvm/test/Transforms/SimpleLoopUnswitch/update-scev.ll
new file mode 100644
index 00000000000..3a2d7618817
--- /dev/null
+++ b/llvm/test/Transforms/SimpleLoopUnswitch/update-scev.ll
@@ -0,0 +1,188 @@
+; RUN: opt -passes='print<scalar-evolution>,loop(unswitch,loop-instsimplify),print<scalar-evolution>' -enable-nontrivial-unswitch -S < %s 2>%t.scev | FileCheck %s
+; RUN: FileCheck %s --check-prefix=SCEV < %t.scev
+
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @f()
+
+; Check that trivially unswitching an inner loop resets both the inner and outer
+; loop trip count.
+define void @test1(i32 %n, i32 %m, i1 %cond) {
+; Check that SCEV has no trip count before unswitching.
+; SCEV-LABEL: Determining loop execution counts for: @test1
+; SCEV: Loop %inner_loop_begin: <multiple exits> Unpredictable backedge-taken count.
+; SCEV: Loop %outer_loop_begin: Unpredictable backedge-taken count.
+;
+; Now check that after unswitching and simplifying instructions we get clean
+; backedge-taken counts.
+; SCEV-LABEL: Determining loop execution counts for: @test1
+; SCEV: Loop %inner_loop_begin: backedge-taken count is (-1 + (1 smax %m))<nsw>
+; SCEV: Loop %outer_loop_begin: backedge-taken count is (-1 + (1 smax %n))<nsw>
+;
+; And verify the code matches what we expect.
+; CHECK-LABEL: define void @test1(
+entry:
+  br label %outer_loop_begin
+; Ensure the outer loop didn't get unswitched.
+; CHECK:       entry:
+; CHECK-NEXT:    br label %outer_loop_begin
+
+outer_loop_begin:
+  %i = phi i32 [ %i.next, %outer_loop_latch ], [ 0, %entry ]
+  ; Block unswitching of the outer loop with a noduplicate call.
+  call void @f() noduplicate
+  br label %inner_loop_begin
+; Ensure the inner loop got unswitched into the outer loop.
+; CHECK:       outer_loop_begin:
+; CHECK-NEXT:    %{{.*}} = phi i32
+; CHECK-NEXT:    call void @f()
+; CHECK-NEXT:    br i1 %cond,
+
+inner_loop_begin:
+  %j = phi i32 [ %j.next, %inner_loop_latch ], [ 0, %outer_loop_begin ]
+  br i1 %cond, label %inner_loop_latch, label %inner_loop_early_exit
+
+inner_loop_latch:
+  %j.next = add nsw i32 %j, 1
+  %j.cmp = icmp slt i32 %j.next, %m
+  br i1 %j.cmp, label %inner_loop_begin, label %inner_loop_late_exit
+
+inner_loop_early_exit:
+  %j.lcssa = phi i32 [ %i, %inner_loop_begin ]
+  br label %outer_loop_latch
+
+inner_loop_late_exit:
+  br label %outer_loop_latch
+
+outer_loop_latch:
+  %i.phi = phi i32 [ %j.lcssa, %inner_loop_early_exit ], [ %i, %inner_loop_late_exit ]
+  %i.next = add nsw i32 %i.phi, 1
+  %i.cmp = icmp slt i32 %i.next, %n
+  br i1 %i.cmp, label %outer_loop_begin, label %exit
+
+exit:
+  ret void
+}
+
+; Check that trivially unswitching an inner loop resets both the inner and outer
+; loop trip count.
+define void @test2(i32 %n, i32 %m, i32 %cond) {
+; Check that SCEV has no trip count before unswitching.
+; SCEV-LABEL: Determining loop execution counts for: @test2
+; SCEV: Loop %inner_loop_begin: <multiple exits> Unpredictable backedge-taken count.
+; SCEV: Loop %outer_loop_begin: Unpredictable backedge-taken count.
+;
+; Now check that after unswitching and simplifying instructions we get clean
+; backedge-taken counts.
+; SCEV-LABEL: Determining loop execution counts for: @test2
+; SCEV: Loop %inner_loop_begin: backedge-taken count is (-1 + (1 smax %m))<nsw>
+; FIXME: The following backedge taken count should be known but isn't apparently
+; just because of a switch in the outer loop.
+; SCEV: Loop %outer_loop_begin: Unpredictable backedge-taken count.
+;
+; CHECK-LABEL: define void @test2(
+entry:
+  br label %outer_loop_begin
+; Ensure the outer loop didn't get unswitched.
+; CHECK:       entry:
+; CHECK-NEXT:    br label %outer_loop_begin
+
+outer_loop_begin:
+  %i = phi i32 [ %i.next, %outer_loop_latch ], [ 0, %entry ]
+  ; Block unswitching of the outer loop with a noduplicate call.
+  call void @f() noduplicate
+  br label %inner_loop_begin
+; Ensure the inner loop got unswitched into the outer loop.
+; CHECK:       outer_loop_begin:
+; CHECK-NEXT:    %{{.*}} = phi i32
+; CHECK-NEXT:    call void @f()
+; CHECK-NEXT:    switch i32 %cond,
+
+inner_loop_begin:
+  %j = phi i32 [ %j.next, %inner_loop_latch ], [ 0, %outer_loop_begin ]
+  switch i32 %cond, label %inner_loop_early_exit [
+    i32 1, label %inner_loop_latch
+    i32 2, label %inner_loop_latch
+  ]
+
+inner_loop_latch:
+  %j.next = add nsw i32 %j, 1
+  %j.cmp = icmp slt i32 %j.next, %m
+  br i1 %j.cmp, label %inner_loop_begin, label %inner_loop_late_exit
+
+inner_loop_early_exit:
+  %j.lcssa = phi i32 [ %i, %inner_loop_begin ]
+  br label %outer_loop_latch
+
+inner_loop_late_exit:
+  br label %outer_loop_latch
+
+outer_loop_latch:
+  %i.phi = phi i32 [ %j.lcssa, %inner_loop_early_exit ], [ %i, %inner_loop_late_exit ]
+  %i.next = add nsw i32 %i.phi, 1
+  %i.cmp = icmp slt i32 %i.next, %n
+  br i1 %i.cmp, label %outer_loop_begin, label %exit
+
+exit:
+  ret void
+}
+
+; Check that non-trivial unswitching of a branch in an inner loop into the outer
+; loop invalidates both inner and outer.
+define void @test3(i32 %n, i32 %m, i1 %cond) {
+; Check that SCEV has no trip count before unswitching.
+; SCEV-LABEL: Determining loop execution counts for: @test3
+; SCEV: Loop %inner_loop_begin: <multiple exits> Unpredictable backedge-taken count.
+; SCEV: Loop %outer_loop_begin: Unpredictable backedge-taken count.
+;
+; Now check that after unswitching and simplifying instructions we get clean
+; backedge-taken counts.
+; SCEV-LABEL: Determining loop execution counts for: @test3
+; SCEV: Loop %inner_loop_begin{{.*}}: backedge-taken count is (-1 + (1 smax %m))<nsw>
+; SCEV: Loop %outer_loop_begin: backedge-taken count is (-1 + (1 smax %n))<nsw>
+;
+; And verify the code matches what we expect.
+; CHECK-LABEL: define void @test3(
+entry:
+  br label %outer_loop_begin
+; Ensure the outer loop didn't get unswitched.
+; CHECK:       entry:
+; CHECK-NEXT:    br label %outer_loop_begin
+
+outer_loop_begin:
+  %i = phi i32 [ %i.next, %outer_loop_latch ], [ 0, %entry ]
+  ; Block unswitching of the outer loop with a noduplicate call.
+  call void @f() noduplicate
+  br label %inner_loop_begin
+; Ensure the inner loop got unswitched into the outer loop.
+; CHECK:       outer_loop_begin:
+; CHECK-NEXT:    %{{.*}} = phi i32
+; CHECK-NEXT:    call void @f()
+; CHECK-NEXT:    br i1 %cond,
+
+inner_loop_begin:
+  %j = phi i32 [ %j.next, %inner_loop_latch ], [ 0, %outer_loop_begin ]
+  %j.tmp = add nsw i32 %j, 1
+  br i1 %cond, label %inner_loop_latch, label %inner_loop_early_exit
+
+inner_loop_latch:
+  %j.next = add nsw i32 %j, 1
+  %j.cmp = icmp slt i32 %j.next, %m
+  br i1 %j.cmp, label %inner_loop_begin, label %inner_loop_late_exit
+
+inner_loop_early_exit:
+  %j.lcssa = phi i32 [ %j.tmp, %inner_loop_begin ]
+  br label %outer_loop_latch
+
+inner_loop_late_exit:
+  br label %outer_loop_latch
+
+outer_loop_latch:
+  %inc.phi = phi i32 [ %j.lcssa, %inner_loop_early_exit ], [ 1, %inner_loop_late_exit ]
+  %i.next = add nsw i32 %i, %inc.phi
+  %i.cmp = icmp slt i32 %i.next, %n
+  br i1 %i.cmp, label %outer_loop_begin, label %exit
+
+exit:
+  ret void
+}