llvm/test/Transforms/SimpleLoopUnswitch/update-scev.ll

   1 ; RUN: opt -passes='print<scalar-evolution>,loop(simple-loop-unswitch<nontrivial>,loop-instsimplify),print<scalar-evolution>' -S < %s 2>%t.scev | FileCheck %s
   2 ; RUN: opt -verify-memoryssa -passes='print<scalar-evolution>,loop-mssa(simple-loop-unswitch<nontrivial>,loop-instsimplify),print<scalar-evolution>' -S < %s 2>%t.scev | FileCheck %s
   3 ; RUN: FileCheck %s --check-prefix=SCEV < %t.scev
   4
   5 target triple = "x86_64-unknown-linux-gnu"
   6
   7 declare void @f()
   8
   9 ; Check that trivially unswitching an inner loop resets both the inner and outer
  10 ; loop trip count.
  11 define void @test1(i32 %n, i32 %m, i1 %cond) {
  12 ; Check that SCEV has no trip count before unswitching.
  13 ; SCEV-LABEL: Determining loop execution counts for: @test1
  14 ; SCEV: Loop %inner_loop_begin: <multiple exits> Unpredictable backedge-taken count.
  15 ; SCEV: Loop %outer_loop_begin: Unpredictable backedge-taken count.
  16 ;
  17 ; Now check that after unswitching and simplifying instructions we get clean
  18 ; backedge-taken counts.
  19 ; SCEV-LABEL: Determining loop execution counts for: @test1
  20 ; SCEV: Loop %inner_loop_begin: backedge-taken count is (-1 + (1 smax %m))<nsw>
  21 ; SCEV: Loop %outer_loop_begin: backedge-taken count is (-1 + (1 smax %n))<nsw>
  22 ;
  23 ; And verify the code matches what we expect.
  24 ; CHECK-LABEL: define void @test1(
  25 entry:
  26   br label %outer_loop_begin
  27 ; Ensure the outer loop didn't get unswitched.
  28 ; CHECK:       entry:
  29 ; CHECK-NEXT:    br label %outer_loop_begin
  30
  31 outer_loop_begin:
  32   %i = phi i32 [ %i.next, %outer_loop_latch ], [ 0, %entry ]
  33   ; Block unswitching of the outer loop with a noduplicate call.
  34   call void @f() noduplicate
  35   br label %inner_loop_begin
  36 ; Ensure the inner loop got unswitched into the outer loop.
  37 ; CHECK:       outer_loop_begin:
  38 ; CHECK-NEXT:    %{{.*}} = phi i32
  39 ; CHECK-NEXT:    call void @f()
  40 ; CHECK-NEXT:    br i1 %cond,
  41
  42 inner_loop_begin:
  43   %j = phi i32 [ %j.next, %inner_loop_latch ], [ 0, %outer_loop_begin ]
  44   br i1 %cond, label %inner_loop_latch, label %inner_loop_early_exit
  45
  46 inner_loop_latch:
  47   %j.next = add nsw i32 %j, 1
  48   %j.cmp = icmp slt i32 %j.next, %m
  49   br i1 %j.cmp, label %inner_loop_begin, label %inner_loop_late_exit
  50
  51 inner_loop_early_exit:
  52   %j.lcssa = phi i32 [ %i, %inner_loop_begin ]
  53   br label %outer_loop_latch
  54
  55 inner_loop_late_exit:
  56   br label %outer_loop_latch
  57
  58 outer_loop_latch:
  59   %i.phi = phi i32 [ %j.lcssa, %inner_loop_early_exit ], [ %i, %inner_loop_late_exit ]
  60   %i.next = add nsw i32 %i.phi, 1
  61   %i.cmp = icmp slt i32 %i.next, %n
  62   br i1 %i.cmp, label %outer_loop_begin, label %exit
  63
  64 exit:
  65   ret void
  66 }
  67
  68 ; Check that trivially unswitching an inner loop resets both the inner and outer
  69 ; loop trip count.
  70 define void @test2(i32 %n, i32 %m, i32 %cond) {
  71 ; Check that SCEV has no trip count before unswitching.
  72 ; SCEV-LABEL: Determining loop execution counts for: @test2
  73 ; SCEV: Loop %inner_loop_begin: <multiple exits> Unpredictable backedge-taken count.
  74 ; SCEV: Loop %outer_loop_begin: Unpredictable backedge-taken count.
  75 ;
  76 ; Now check that after unswitching and simplifying instructions we get clean
  77 ; backedge-taken counts.
  78 ; SCEV-LABEL: Determining loop execution counts for: @test2
  79 ; SCEV: Loop %inner_loop_begin: backedge-taken count is (-1 + (1 smax %m))<nsw>
  80 ; SCEV: Loop %outer_loop_begin: backedge-taken count is (-1 + (1 smax %n))<nsw>
  81 ;
  82 ; CHECK-LABEL: define void @test2(
  83 entry:
  84   br label %outer_loop_begin
  85 ; Ensure the outer loop didn't get unswitched.
  86 ; CHECK:       entry:
  87 ; CHECK-NEXT:    br label %outer_loop_begin
  88
  89 outer_loop_begin:
  90   %i = phi i32 [ %i.next, %outer_loop_latch ], [ 0, %entry ]
  91   ; Block unswitching of the outer loop with a noduplicate call.
  92   call void @f() noduplicate
  93   br label %inner_loop_begin
  94 ; Ensure the inner loop got unswitched into the outer loop.
  95 ; CHECK:       outer_loop_begin:
  96 ; CHECK-NEXT:    %{{.*}} = phi i32
  97 ; CHECK-NEXT:    call void @f()
  98 ; CHECK-NEXT:    switch i32 %cond,
  99
 100 inner_loop_begin:
 101   %j = phi i32 [ %j.next, %inner_loop_latch ], [ 0, %outer_loop_begin ]
 102   switch i32 %cond, label %inner_loop_early_exit [
 103     i32 1, label %inner_loop_latch
 104     i32 2, label %inner_loop_latch
 105   ]
 106
 107 inner_loop_latch:
 108   %j.next = add nsw i32 %j, 1
 109   %j.cmp = icmp slt i32 %j.next, %m
 110   br i1 %j.cmp, label %inner_loop_begin, label %inner_loop_late_exit
 111
 112 inner_loop_early_exit:
 113   %j.lcssa = phi i32 [ %i, %inner_loop_begin ]
 114   br label %outer_loop_latch
 115
 116 inner_loop_late_exit:
 117   br label %outer_loop_latch
 118
 119 outer_loop_latch:
 120   %i.phi = phi i32 [ %j.lcssa, %inner_loop_early_exit ], [ %i, %inner_loop_late_exit ]
 121   %i.next = add nsw i32 %i.phi, 1
 122   %i.cmp = icmp slt i32 %i.next, %n
 123   br i1 %i.cmp, label %outer_loop_begin, label %exit
 124
 125 exit:
 126   ret void
 127 }
 128
 129 ; Check that non-trivial unswitching of a branch in an inner loop into the outer
 130 ; loop invalidates both inner and outer.
 131 define void @test3(i32 %n, i32 %m, i1 %cond) {
 132 ; Check that SCEV has no trip count before unswitching.
 133 ; SCEV-LABEL: Determining loop execution counts for: @test3
 134 ; SCEV: Loop %inner_loop_begin: <multiple exits> Unpredictable backedge-taken count.
 135 ; SCEV: Loop %outer_loop_begin: Unpredictable backedge-taken count.
 136 ;
 137 ; Now check that after unswitching and simplifying instructions we get clean
 138 ; backedge-taken counts.
 139 ; SCEV-LABEL: Determining loop execution counts for: @test3
 140 ; SCEV: Loop %inner_loop_begin{{.*}}: backedge-taken count is (-1 + (1 smax %m))<nsw>
 141 ; SCEV: Loop %outer_loop_begin: backedge-taken count is (-1 + (1 smax %n))<nsw>
 142 ;
 143 ; And verify the code matches what we expect.
 144 ; CHECK-LABEL: define void @test3(
 145 entry:
 146   br label %outer_loop_begin
 147 ; Ensure the outer loop didn't get unswitched.
 148 ; CHECK:       entry:
 149 ; CHECK-NEXT:    br label %outer_loop_begin
 150
 151 outer_loop_begin:
 152   %i = phi i32 [ %i.next, %outer_loop_latch ], [ 0, %entry ]
 153   ; Block unswitching of the outer loop with a noduplicate call.
 154   call void @f() noduplicate
 155   br label %inner_loop_begin
 156 ; Ensure the inner loop got unswitched into the outer loop.
 157 ; CHECK:       outer_loop_begin:
 158 ; CHECK-NEXT:    %{{.*}} = phi i32
 159 ; CHECK-NEXT:    call void @f()
 160 ; CHECK-NEXT:    br i1 %cond,
 161
 162 inner_loop_begin:
 163   %j = phi i32 [ %j.next, %inner_loop_latch ], [ 0, %outer_loop_begin ]
 164   %j.tmp = add nsw i32 %j, 1
 165   br i1 %cond, label %inner_loop_latch, label %inner_loop_early_exit
 166
 167 inner_loop_latch:
 168   %j.next = add nsw i32 %j, 1
 169   %j.cmp = icmp slt i32 %j.next, %m
 170   br i1 %j.cmp, label %inner_loop_begin, label %inner_loop_late_exit
 171
 172 inner_loop_early_exit:
 173   %j.lcssa = phi i32 [ %j.tmp, %inner_loop_begin ]
 174   br label %outer_loop_latch
 175
 176 inner_loop_late_exit:
 177   br label %outer_loop_latch
 178
 179 outer_loop_latch:
 180   %inc.phi = phi i32 [ %j.lcssa, %inner_loop_early_exit ], [ 1, %inner_loop_late_exit ]
 181   %i.next = add nsw i32 %i, %inc.phi
 182   %i.cmp = icmp slt i32 %i.next, %n
 183   br i1 %i.cmp, label %outer_loop_begin, label %exit
 184
 185 exit:
 186   ret void
 187 }