llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info-rewrite-expressions.ll

   1 ; RUN: opt -analyze -scalar-evolution %s -enable-new-pm=0 | FileCheck %s
   2 ; RUN: opt -passes='print<scalar-evolution>' -disable-output %s 2>&1 | FileCheck %s
   3
   4 ; Test cases that require rewriting zext SCEV expression with infomration from
   5 ; the loop guards.
   6
   7 define void @rewrite_zext(i32 %n) {
   8 ; CHECK-LABEL: Determining loop execution counts for: @rewrite_zext
   9 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8)
  10 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is 2
  11 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8)
  12 ; CHECK-NEXT:  Predicates:
  13 ; CHECK:        Loop %loop: Trip multiple is 1
  14 ;
  15 entry:
  16   %ext = zext i32 %n to i64
  17   %cmp5 = icmp ule i64 %ext, 24
  18   br i1 %cmp5, label %check, label %exit
  19
  20 check:                                 ; preds = %entry
  21   %min.iters.check = icmp ult i64 %ext, 8
  22   %n.vec = and i64 %ext, -8
  23   br i1 %min.iters.check, label %exit, label %loop
  24
  25 loop:
  26   %index = phi i64 [ 0, %check ], [ %index.next, %loop ]
  27   %index.next = add nuw nsw i64 %index, 8
  28   %ec = icmp eq i64 %index.next, %n.vec
  29   br i1 %ec, label %exit, label %loop
  30
  31 exit:
  32   ret void
  33 }
  34
  35 ; Test case from PR40961.
  36 define i32 @rewrite_zext_min_max(i32 %N, i32* %arr) {
  37 ; CHECK-LABEL:  Determining loop execution counts for: @rewrite_zext_min_max
  38 ; CHECK-NEXT:   Loop %loop: backedge-taken count is ((-4 + (4 * ((zext i32 (16 umin %N) to i64) /u 4))<nuw><nsw>)<nsw> /u 4)
  39 ; CHECK-NEXT:   Loop %loop: max backedge-taken count is 3
  40 ; CHECK-NEXT:   Loop %loop: Predicated backedge-taken count is ((-4 + (4 * ((zext i32 (16 umin %N) to i64) /u 4))<nuw><nsw>)<nsw> /u 4)
  41 ; CHECK-NEXT:   Predicates:
  42 ; CHECK:         Loop %loop: Trip multiple is 1
  43 ;
  44 entry:
  45   %umin = call i32 @llvm.umin.i32(i32 %N, i32 16)
  46   %ext = zext i32 %umin to i64
  47   %min.iters.check = icmp ult i64 %ext, 4
  48   br i1 %min.iters.check, label %exit, label %loop.ph
  49
  50 loop.ph:
  51   %n.vec = and i64 %ext, 28
  52   br label %loop
  53
  54 ; %n.vec is [4, 16) and a multiple of 4.
  55 loop:
  56   %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
  57   %gep = getelementptr inbounds i32, i32* %arr, i64 %index
  58   store i32 0, i32* %gep
  59   %index.next = add nuw i64 %index, 4
  60   %ec = icmp eq i64 %index.next, %n.vec
  61   br i1 %ec, label %exit, label %loop
  62
  63 exit:
  64   ret i32 0
  65 }
  66
  67 ; Test case from PR52464. applyLoopGuards needs to apply information about %and
  68 ; to %ext, which requires rewriting the zext.
  69 define i32 @rewrite_zext_with_info_from_icmp_ne(i32 %N) {
  70 ; CHECK-LABEL: Determining loop execution counts for: @rewrite_zext_with_info_from_icmp_ne
  71 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 0
  72 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is 0
  73 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 0
  74 ; CHECK-NEXT:   Predicates:
  75 ; CHECK-EMPTY:
  76 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
  77 ;
  78 entry:
  79   %and = and i32 %N, 3
  80   %cmp6.not = icmp eq i32 %and, 0
  81   br i1 %cmp6.not, label %exit, label %loop.ph
  82
  83 loop.ph:
  84   %and.sub.1 = add nsw i32 %and, -1
  85   %ext = zext i32 %and.sub.1 to i64
  86   %n.rnd.up = add nuw nsw i64 %ext, 4
  87   %n.vec = and i64 %n.rnd.up, 8589934588
  88   br label %loop
  89
  90 loop:
  91   %iv = phi i64 [ 0, %loop.ph ], [ %iv.next, %loop ]
  92   %iv.next = add i64 %iv, 4
  93   call void @use(i64 %iv.next)
  94   %ec = icmp eq i64 %iv.next, %n.vec
  95   br i1 %ec, label %exit, label %loop
  96
  97 exit:
  98   ret i32 0
  99 }
 100
 101 ; Similar to @rewrite_zext_with_info_from_icmp_ne, but the loop is not guarded by %and != 0,
 102 ; hence the subsequent subtraction may yield a negative number.
 103 define i32 @rewrite_zext_no_icmp_ne(i32 %N) {
 104 ; CHECK-LABEL: Determining loop execution counts for: @rewrite_zext_no_icmp_ne
 105 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-4 + (4 * ((4 + (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64))<nuw><nsw> /u 4))<nuw><nsw>)<nsw> /u 4)
 106 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is 1073741823
 107 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((-4 + (4 * ((4 + (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64))<nuw><nsw> /u 4))<nuw><nsw>)<nsw> /u 4)
 108 ; CHECK-NEXT:   Predicates:
 109 ; CHECK-EMPTY:
 110 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 111 ;
 112 entry:
 113   %and = and i32 %N, 3
 114   br label %loop.ph
 115
 116 loop.ph:
 117   %and.sub.1 = add nsw i32 %and, -1
 118   %ext = zext i32 %and.sub.1 to i64
 119   %n.rnd.up = add nuw nsw i64 %ext, 4
 120   %n.vec = and i64 %n.rnd.up, 8589934588
 121   br label %loop
 122
 123 loop:
 124   %iv = phi i64 [ 0, %loop.ph ], [ %iv.next, %loop ]
 125   %iv.next = add i64 %iv, 4
 126   call void @use(i64 %iv.next)
 127   %ec = icmp eq i64 %iv.next, %n.vec
 128   br i1 %ec, label %exit, label %loop
 129
 130 exit:
 131   ret i32 0
 132 }
 133
 134 ; Make sure no information is lost for conditions on both %n and (zext %n).
 135 define void @rewrite_zext_and_base_1(i32 %n) {
 136 ; CHECK-LABEL: Determining loop execution counts for: @rewrite_zext_and_base
 137 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8)
 138 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is 3
 139 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8)
 140 ; CHECK-NEXT:  Predicates:
 141 ; CHECK:        Loop %loop: Trip multiple is 1
 142 ;
 143 entry:
 144   %ext = zext i32 %n to i64
 145   %cmp5 = icmp ule i64 %ext, 48
 146   br i1 %cmp5, label %check.1, label %exit
 147
 148 check.1:
 149   %cmp.2 = icmp ule i32 %n, 32
 150   br i1 %cmp.2, label %check, label %exit
 151
 152
 153 check:                                 ; preds = %entry
 154   %min.iters.check = icmp ult i64 %ext, 8
 155   %n.vec = and i64 %ext, -8
 156   br i1 %min.iters.check, label %exit, label %loop
 157
 158 loop:
 159   %index = phi i64 [ 0, %check ], [ %index.next, %loop ]
 160   %index.next = add nuw nsw i64 %index, 8
 161   %ec = icmp eq i64 %index.next, %n.vec
 162   br i1 %ec, label %exit, label %loop
 163
 164 exit:
 165   ret void
 166 }
 167
 168 ; Make sure no information is lost for conditions on both %n and (zext %n).
 169 define void @rewrite_zext_and_base_2(i32 %n) {
 170 ; CHECK-LABEL: Determining loop execution counts for: @rewrite_zext_and_base
 171 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8)
 172 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is 3
 173 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8)
 174 ; CHECK-NEXT:  Predicates:
 175 ; CHECK:        Loop %loop: Trip multiple is 1
 176 ;
 177 entry:
 178   %ext = zext i32 %n to i64
 179   %cmp5 = icmp ule i64 %ext, 32
 180   br i1 %cmp5, label %check.1, label %exit
 181
 182 check.1:
 183   %cmp.2 = icmp ule i32 %n, 48
 184   br i1 %cmp.2, label %check, label %exit
 185
 186 check:                                 ; preds = %entry
 187   %min.iters.check = icmp ult i64 %ext, 8
 188   %n.vec = and i64 %ext, -8
 189   br i1 %min.iters.check, label %exit, label %loop
 190
 191 loop:
 192   %index = phi i64 [ 0, %check ], [ %index.next, %loop ]
 193   %index.next = add nuw nsw i64 %index, 8
 194   %ec = icmp eq i64 %index.next, %n.vec
 195   br i1 %ec, label %exit, label %loop
 196
 197 exit:
 198   ret void
 199 }
 200
 201 define void @guard_pessimizes_analysis_step2(i1 %c, i32 %N) {
 202 ; CHECK-LABEL: 'guard_pessimizes_analysis_step2'
 203 ; CHECK:       Determining loop execution counts for: @guard_pessimizes_analysis_step2
 204 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((14 + (-1 * %init)<nsw>)<nsw> /u 2)
 205 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is 6
 206 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((14 + (-1 * %init)<nsw>)<nsw> /u 2)
 207 ; CHECK-NEXT:   Predicates:
 208 ; CHECK-EMPTY:
 209 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 210 ;
 211 entry:
 212   %N.ext = zext i32 %N to i64
 213   br i1 %c, label %bb1, label %guard
 214
 215 bb1:
 216   br label %guard
 217
 218 guard:
 219   %init = phi i64 [ 2, %entry ], [ 4, %bb1 ]
 220   %c.1 = icmp ult i64 %init, %N.ext
 221   br i1 %c.1, label %loop.ph, label %exit
 222
 223 loop.ph:
 224   br label %loop
 225
 226 loop:
 227   %iv = phi i64 [ %iv.next, %loop ], [ %init, %loop.ph ]
 228   %iv.next = add i64 %iv, 2
 229   %exitcond = icmp eq i64 %iv.next, 16
 230   br i1 %exitcond, label %exit, label %loop
 231
 232 exit:
 233   ret void
 234 }
 235 declare void @use(i64)
 236
 237 declare i32 @llvm.umin.i32(i32, i32)