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

   1 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
   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: 'rewrite_zext'
   9 ; CHECK-NEXT:  Classifying expressions for: @rewrite_zext
  10 ; CHECK-NEXT:    %ext = zext i32 %n to i64
  11 ; CHECK-NEXT:    --> (zext i32 %n to i64) U: [0,4294967296) S: [0,4294967296)
  12 ; CHECK-NEXT:    %n.vec = and i64 %ext, -8
  13 ; CHECK-NEXT:    --> (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw> U: [0,4294967289) S: [0,4294967289)
  14 ; CHECK-NEXT:    %index = phi i64 [ 0, %check ], [ %index.next, %loop ]
  15 ; CHECK-NEXT:    --> {0,+,8}<nuw><nsw><%loop> U: [0,17) S: [0,17) Exits: (8 * ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8))<nuw> LoopDispositions: { %loop: Computable }
  16 ; CHECK-NEXT:    %index.next = add nuw nsw i64 %index, 8
  17 ; CHECK-NEXT:    --> {8,+,8}<nuw><nsw><%loop> U: [8,25) S: [8,25) Exits: (8 + (8 * ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8))<nuw>) LoopDispositions: { %loop: Computable }
  18 ; CHECK-NEXT:  Determining loop execution counts for: @rewrite_zext
  19 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8)
  20 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 2
  21 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8)
  22 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
  23 ;
  24 entry:
  25   %ext = zext i32 %n to i64
  26   %cmp5 = icmp ule i64 %ext, 24
  27   br i1 %cmp5, label %check, label %exit
  28
  29 check:                                 ; preds = %entry
  30   %min.iters.check = icmp ult i64 %ext, 8
  31   %n.vec = and i64 %ext, -8
  32   br i1 %min.iters.check, label %exit, label %loop
  33
  34 loop:
  35   %index = phi i64 [ 0, %check ], [ %index.next, %loop ]
  36   %index.next = add nuw nsw i64 %index, 8
  37   %ec = icmp eq i64 %index.next, %n.vec
  38   br i1 %ec, label %exit, label %loop
  39
  40 exit:
  41   ret void
  42 }
  43
  44 ; Test case from PR40961.
  45 define i32 @rewrite_zext_min_max(i32 %N, ptr %arr) {
  46 ; CHECK-LABEL: 'rewrite_zext_min_max'
  47 ; CHECK-NEXT:  Classifying expressions for: @rewrite_zext_min_max
  48 ; CHECK-NEXT:    %umin = call i32 @llvm.umin.i32(i32 %N, i32 16)
  49 ; CHECK-NEXT:    --> (16 umin %N) U: [0,17) S: [0,17)
  50 ; CHECK-NEXT:    %ext = zext i32 %umin to i64
  51 ; CHECK-NEXT:    --> (16 umin (zext i32 %N to i64)) U: [0,17) S: [0,17)
  52 ; CHECK-NEXT:    %n.vec = and i64 %ext, 28
  53 ; CHECK-NEXT:    --> (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw> U: [0,17) S: [0,17)
  54 ; CHECK-NEXT:    %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
  55 ; CHECK-NEXT:    --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (4 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4))<nuw> LoopDispositions: { %loop: Computable }
  56 ; CHECK-NEXT:    %gep = getelementptr inbounds i32, ptr %arr, i64 %index
  57 ; CHECK-NEXT:    --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }
  58 ; CHECK-NEXT:    %index.next = add nuw i64 %index, 4
  59 ; CHECK-NEXT:    --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 + (4 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4))<nuw>) LoopDispositions: { %loop: Computable }
  60 ; CHECK-NEXT:  Determining loop execution counts for: @rewrite_zext_min_max
  61 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)
  62 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 3
  63 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)
  64 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
  65 ;
  66 entry:
  67   %umin = call i32 @llvm.umin.i32(i32 %N, i32 16)
  68   %ext = zext i32 %umin to i64
  69   %min.iters.check = icmp ult i64 %ext, 4
  70   br i1 %min.iters.check, label %exit, label %loop.ph
  71
  72 loop.ph:
  73   %n.vec = and i64 %ext, 28
  74   br label %loop
  75
  76 ; %n.vec is [4, 16) and a multiple of 4.
  77 loop:
  78   %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
  79   %gep = getelementptr inbounds i32, ptr %arr, i64 %index
  80   store i32 0, ptr %gep
  81   %index.next = add nuw i64 %index, 4
  82   %ec = icmp eq i64 %index.next, %n.vec
  83   br i1 %ec, label %exit, label %loop
  84
  85 exit:
  86   ret i32 0
  87 }
  88
  89 ; This is same as rewrite_zext_min_max, but zext and umin are swapped.
  90 ; It should be able to prove the same exit count.
  91 define i32 @rewrite_min_max_zext(i32 %N, ptr %arr) {
  92 ; CHECK-LABEL: 'rewrite_min_max_zext'
  93 ; CHECK-NEXT:  Classifying expressions for: @rewrite_min_max_zext
  94 ; CHECK-NEXT:    %N.wide = zext i32 %N to i64
  95 ; CHECK-NEXT:    --> (zext i32 %N to i64) U: [0,4294967296) S: [0,4294967296)
  96 ; CHECK-NEXT:    %umin = call i64 @llvm.umin.i64(i64 %N.wide, i64 16)
  97 ; CHECK-NEXT:    --> (16 umin (zext i32 %N to i64)) U: [0,17) S: [0,17)
  98 ; CHECK-NEXT:    %n.vec = and i64 %umin, 28
  99 ; CHECK-NEXT:    --> (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw> U: [0,17) S: [0,17)
 100 ; CHECK-NEXT:    %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
 101 ; CHECK-NEXT:    --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (4 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4))<nuw> LoopDispositions: { %loop: Computable }
 102 ; CHECK-NEXT:    %gep = getelementptr inbounds i32, ptr %arr, i64 %index
 103 ; CHECK-NEXT:    --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }
 104 ; CHECK-NEXT:    %index.next = add nuw i64 %index, 4
 105 ; CHECK-NEXT:    --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 + (4 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4))<nuw>) LoopDispositions: { %loop: Computable }
 106 ; CHECK-NEXT:  Determining loop execution counts for: @rewrite_min_max_zext
 107 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)
 108 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 3
 109 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)
 110 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 111 ;
 112 entry:
 113   %N.wide = zext i32 %N to i64
 114   %umin = call i64 @llvm.umin.i64(i64 %N.wide, i64 16)
 115   %min.iters.check = icmp ult i64 %umin, 4
 116   br i1 %min.iters.check, label %exit, label %loop.ph
 117
 118 loop.ph:
 119   %n.vec = and i64 %umin, 28
 120   br label %loop
 121
 122 ; %n.vec is [4, 16) and a multiple of 4.
 123 loop:
 124   %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
 125   %gep = getelementptr inbounds i32, ptr %arr, i64 %index
 126   store i32 0, ptr %gep
 127   %index.next = add nuw i64 %index, 4
 128   %ec = icmp eq i64 %index.next, %n.vec
 129   br i1 %ec, label %exit, label %loop
 130
 131 exit:
 132   ret i32 0
 133 }
 134
 135 ; same as rewrite_zext_min_max, but everything is signed.
 136 ; It should be able to prove the same exit count.
 137 define i32 @rewrite_sext_min_max(i32 %N, ptr %arr) {
 138 ; CHECK-LABEL: 'rewrite_sext_min_max'
 139 ; CHECK-NEXT:  Classifying expressions for: @rewrite_sext_min_max
 140 ; CHECK-NEXT:    %smin = call i32 @llvm.smin.i32(i32 %N, i32 16)
 141 ; CHECK-NEXT:    --> (16 smin %N) U: [-2147483648,17) S: [-2147483648,17)
 142 ; CHECK-NEXT:    %ext = sext i32 %smin to i64
 143 ; CHECK-NEXT:    --> (16 smin (sext i32 %N to i64)) U: [-2147483648,17) S: [-2147483648,17)
 144 ; CHECK-NEXT:    %n.vec = and i64 %ext, 28
 145 ; CHECK-NEXT:    --> (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw> U: [0,29) S: [0,29)
 146 ; CHECK-NEXT:    %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
 147 ; CHECK-NEXT:    --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (4 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4))<nuw> LoopDispositions: { %loop: Computable }
 148 ; CHECK-NEXT:    %gep = getelementptr inbounds i32, ptr %arr, i64 %index
 149 ; CHECK-NEXT:    --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }
 150 ; CHECK-NEXT:    %index.next = add nsw i64 %index, 4
 151 ; CHECK-NEXT:    --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 + (4 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4))<nuw>) LoopDispositions: { %loop: Computable }
 152 ; CHECK-NEXT:  Determining loop execution counts for: @rewrite_sext_min_max
 153 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)
 154 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 3
 155 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)
 156 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 157 ;
 158 entry:
 159   %smin = call i32 @llvm.smin.i32(i32 %N, i32 16)
 160   %ext = sext i32 %smin to i64
 161   %min.iters.check = icmp slt i64 %ext, 4
 162   br i1 %min.iters.check, label %exit, label %loop.ph
 163
 164 loop.ph:
 165   %n.vec = and i64 %ext, 28
 166   br label %loop
 167
 168 ; %n.vec is [4, 16) and a multiple of 4.
 169 loop:
 170   %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
 171   %gep = getelementptr inbounds i32, ptr %arr, i64 %index
 172   store i32 0, ptr %gep
 173   %index.next = add nsw i64 %index, 4
 174   %ec = icmp eq i64 %index.next, %n.vec
 175   br i1 %ec, label %exit, label %loop
 176
 177 exit:
 178   ret i32 0
 179 }
 180
 181 ; This is a signed version of rewrite_min_max_zext.
 182 ; It should be able to prove the same exit count.
 183 define i32 @rewrite_min_max_sext(i32 %N, ptr %arr) {
 184 ; CHECK-LABEL: 'rewrite_min_max_sext'
 185 ; CHECK-NEXT:  Classifying expressions for: @rewrite_min_max_sext
 186 ; CHECK-NEXT:    %N.wide = sext i32 %N to i64
 187 ; CHECK-NEXT:    --> (sext i32 %N to i64) U: [-2147483648,2147483648) S: [-2147483648,2147483648)
 188 ; CHECK-NEXT:    %smin = call i64 @llvm.smin.i64(i64 %N.wide, i64 16)
 189 ; CHECK-NEXT:    --> (16 smin (sext i32 %N to i64)) U: [-2147483648,17) S: [-2147483648,17)
 190 ; CHECK-NEXT:    %n.vec = and i64 %smin, 28
 191 ; CHECK-NEXT:    --> (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw> U: [0,29) S: [0,29)
 192 ; CHECK-NEXT:    %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
 193 ; CHECK-NEXT:    --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (4 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4))<nuw> LoopDispositions: { %loop: Computable }
 194 ; CHECK-NEXT:    %gep = getelementptr inbounds i32, ptr %arr, i64 %index
 195 ; CHECK-NEXT:    --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }
 196 ; CHECK-NEXT:    %index.next = add nsw i64 %index, 4
 197 ; CHECK-NEXT:    --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 + (4 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4))<nuw>) LoopDispositions: { %loop: Computable }
 198 ; CHECK-NEXT:  Determining loop execution counts for: @rewrite_min_max_sext
 199 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)
 200 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 3
 201 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)
 202 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 203 ;
 204 entry:
 205   %N.wide = sext i32 %N to i64
 206   %smin = call i64 @llvm.smin.i64(i64 %N.wide, i64 16)
 207   %min.iters.check = icmp slt i64 %smin, 4
 208   br i1 %min.iters.check, label %exit, label %loop.ph
 209
 210 loop.ph:
 211   %n.vec = and i64 %smin, 28
 212   br label %loop
 213
 214 ; %n.vec is [4, 16) and a multiple of 4.
 215 loop:
 216   %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
 217   %gep = getelementptr inbounds i32, ptr %arr, i64 %index
 218   store i32 0, ptr %gep
 219   %index.next = add nsw i64 %index, 4
 220   %ec = icmp eq i64 %index.next, %n.vec
 221   br i1 %ec, label %exit, label %loop
 222
 223 exit:
 224   ret i32 0
 225 }
 226
 227 ; Test case from PR52464. applyLoopGuards needs to apply information about %and
 228 ; to %ext, which requires rewriting the zext.
 229 define i32 @rewrite_zext_with_info_from_icmp_ne(i32 %N) {
 230 ; CHECK-LABEL: 'rewrite_zext_with_info_from_icmp_ne'
 231 ; CHECK-NEXT:  Classifying expressions for: @rewrite_zext_with_info_from_icmp_ne
 232 ; CHECK-NEXT:    %and = and i32 %N, 3
 233 ; CHECK-NEXT:    --> (zext i2 (trunc i32 %N to i2) to i32) U: [0,4) S: [0,4)
 234 ; CHECK-NEXT:    %and.sub.1 = add nsw i32 %and, -1
 235 ; CHECK-NEXT:    --> (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> U: [-1,3) S: [-1,3)
 236 ; CHECK-NEXT:    %ext = zext i32 %and.sub.1 to i64
 237 ; CHECK-NEXT:    --> (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64) U: [0,4294967296) S: [0,4294967296)
 238 ; CHECK-NEXT:    %n.rnd.up = add nuw nsw i64 %ext, 4
 239 ; CHECK-NEXT:    --> (4 + (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64))<nuw><nsw> U: [4,4294967300) S: [4,4294967300)
 240 ; CHECK-NEXT:    %n.vec = and i64 %n.rnd.up, 8589934588
 241 ; CHECK-NEXT:    --> (4 * ((4 + (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64))<nuw><nsw> /u 4))<nuw><nsw> U: [4,4294967297) S: [4,4294967297)
 242 ; CHECK-NEXT:    %iv = phi i64 [ 0, %loop.ph ], [ %iv.next, %loop ]
 243 ; CHECK-NEXT:    --> {0,+,4}<nuw><nsw><%loop> U: [0,1) S: [0,1) Exits: 0 LoopDispositions: { %loop: Computable }
 244 ; CHECK-NEXT:    %iv.next = add i64 %iv, 4
 245 ; CHECK-NEXT:    --> {4,+,4}<nuw><nsw><%loop> U: [4,5) S: [4,5) Exits: 4 LoopDispositions: { %loop: Computable }
 246 ; CHECK-NEXT:  Determining loop execution counts for: @rewrite_zext_with_info_from_icmp_ne
 247 ; CHECK-NEXT:  Loop %loop: backedge-taken count is i64 0
 248 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 0
 249 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is i64 0
 250 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 251 ;
 252 entry:
 253   %and = and i32 %N, 3
 254   %cmp6.not = icmp eq i32 %and, 0
 255   br i1 %cmp6.not, label %exit, label %loop.ph
 256
 257 loop.ph:
 258   %and.sub.1 = add nsw i32 %and, -1
 259   %ext = zext i32 %and.sub.1 to i64
 260   %n.rnd.up = add nuw nsw i64 %ext, 4
 261   %n.vec = and i64 %n.rnd.up, 8589934588
 262   br label %loop
 263
 264 loop:
 265   %iv = phi i64 [ 0, %loop.ph ], [ %iv.next, %loop ]
 266   %iv.next = add i64 %iv, 4
 267   call void @use(i64 %iv.next)
 268   %ec = icmp eq i64 %iv.next, %n.vec
 269   br i1 %ec, label %exit, label %loop
 270
 271 exit:
 272   ret i32 0
 273 }
 274
 275 ; Similar to @rewrite_zext_with_info_from_icmp_ne, but the loop is not guarded by %and != 0,
 276 ; hence the subsequent subtraction may yield a negative number.
 277 define i32 @rewrite_zext_no_icmp_ne(i32 %N) {
 278 ; CHECK-LABEL: 'rewrite_zext_no_icmp_ne'
 279 ; CHECK-NEXT:  Classifying expressions for: @rewrite_zext_no_icmp_ne
 280 ; CHECK-NEXT:    %and = and i32 %N, 3
 281 ; CHECK-NEXT:    --> (zext i2 (trunc i32 %N to i2) to i32) U: [0,4) S: [0,4)
 282 ; CHECK-NEXT:    %and.sub.1 = add nsw i32 %and, -1
 283 ; CHECK-NEXT:    --> (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> U: [-1,3) S: [-1,3)
 284 ; CHECK-NEXT:    %ext = zext i32 %and.sub.1 to i64
 285 ; CHECK-NEXT:    --> (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64) U: [0,4294967296) S: [0,4294967296)
 286 ; CHECK-NEXT:    %n.rnd.up = add nuw nsw i64 %ext, 4
 287 ; CHECK-NEXT:    --> (4 + (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64))<nuw><nsw> U: [4,4294967300) S: [4,4294967300)
 288 ; CHECK-NEXT:    %n.vec = and i64 %n.rnd.up, 8589934588
 289 ; CHECK-NEXT:    --> (4 * ((4 + (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64))<nuw><nsw> /u 4))<nuw><nsw> U: [4,4294967297) S: [4,4294967297)
 290 ; CHECK-NEXT:    %iv = phi i64 [ 0, %loop.ph ], [ %iv.next, %loop ]
 291 ; CHECK-NEXT:    --> {0,+,4}<nuw><nsw><%loop> U: [0,4294967293) S: [0,4294967293) Exits: (4 * ((-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))<nuw><nsw> LoopDispositions: { %loop: Computable }
 292 ; CHECK-NEXT:    %iv.next = add i64 %iv, 4
 293 ; CHECK-NEXT:    --> {4,+,4}<nuw><nsw><%loop> U: [4,4294967297) S: [4,4294967297) Exits: (4 + (4 * ((-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))<nuw><nsw>)<nuw><nsw> LoopDispositions: { %loop: Computable }
 294 ; CHECK-NEXT:  Determining loop execution counts for: @rewrite_zext_no_icmp_ne
 295 ; 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)
 296 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 1073741823
 297 ; CHECK-NEXT:  Loop %loop: symbolic max 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)
 298 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 299 ;
 300 entry:
 301   %and = and i32 %N, 3
 302   br label %loop.ph
 303
 304 loop.ph:
 305   %and.sub.1 = add nsw i32 %and, -1
 306   %ext = zext i32 %and.sub.1 to i64
 307   %n.rnd.up = add nuw nsw i64 %ext, 4
 308   %n.vec = and i64 %n.rnd.up, 8589934588
 309   br label %loop
 310
 311 loop:
 312   %iv = phi i64 [ 0, %loop.ph ], [ %iv.next, %loop ]
 313   %iv.next = add i64 %iv, 4
 314   call void @use(i64 %iv.next)
 315   %ec = icmp eq i64 %iv.next, %n.vec
 316   br i1 %ec, label %exit, label %loop
 317
 318 exit:
 319   ret i32 0
 320 }
 321
 322 ; Make sure no information is lost for conditions on both %n and (zext %n).
 323 define void @rewrite_zext_and_base_1(i32 %n) {
 324 ; CHECK-LABEL: 'rewrite_zext_and_base_1'
 325 ; CHECK-NEXT:  Classifying expressions for: @rewrite_zext_and_base_1
 326 ; CHECK-NEXT:    %ext = zext i32 %n to i64
 327 ; CHECK-NEXT:    --> (zext i32 %n to i64) U: [0,4294967296) S: [0,4294967296)
 328 ; CHECK-NEXT:    %n.vec = and i64 %ext, -8
 329 ; CHECK-NEXT:    --> (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw> U: [0,4294967289) S: [0,4294967289)
 330 ; CHECK-NEXT:    %index = phi i64 [ 0, %check ], [ %index.next, %loop ]
 331 ; CHECK-NEXT:    --> {0,+,8}<nuw><nsw><%loop> U: [0,25) S: [0,25) Exits: (8 * ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8))<nuw> LoopDispositions: { %loop: Computable }
 332 ; CHECK-NEXT:    %index.next = add nuw nsw i64 %index, 8
 333 ; CHECK-NEXT:    --> {8,+,8}<nuw><nsw><%loop> U: [8,33) S: [8,33) Exits: (8 + (8 * ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8))<nuw>) LoopDispositions: { %loop: Computable }
 334 ; CHECK-NEXT:  Determining loop execution counts for: @rewrite_zext_and_base_1
 335 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8)
 336 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 3
 337 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8)
 338 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 339 ;
 340 entry:
 341   %ext = zext i32 %n to i64
 342   %cmp5 = icmp ule i64 %ext, 48
 343   br i1 %cmp5, label %check.1, label %exit
 344
 345 check.1:
 346   %cmp.2 = icmp ule i32 %n, 32
 347   br i1 %cmp.2, label %check, label %exit
 348
 349
 350 check:                                 ; preds = %entry
 351   %min.iters.check = icmp ult i64 %ext, 8
 352   %n.vec = and i64 %ext, -8
 353   br i1 %min.iters.check, label %exit, label %loop
 354
 355 loop:
 356   %index = phi i64 [ 0, %check ], [ %index.next, %loop ]
 357   %index.next = add nuw nsw i64 %index, 8
 358   %ec = icmp eq i64 %index.next, %n.vec
 359   br i1 %ec, label %exit, label %loop
 360
 361 exit:
 362   ret void
 363 }
 364
 365 ; Make sure no information is lost for conditions on both %n and (zext %n).
 366 define void @rewrite_zext_and_base_2(i32 %n) {
 367 ; CHECK-LABEL: 'rewrite_zext_and_base_2'
 368 ; CHECK-NEXT:  Classifying expressions for: @rewrite_zext_and_base_2
 369 ; CHECK-NEXT:    %ext = zext i32 %n to i64
 370 ; CHECK-NEXT:    --> (zext i32 %n to i64) U: [0,4294967296) S: [0,4294967296)
 371 ; CHECK-NEXT:    %n.vec = and i64 %ext, -8
 372 ; CHECK-NEXT:    --> (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw> U: [0,4294967289) S: [0,4294967289)
 373 ; CHECK-NEXT:    %index = phi i64 [ 0, %check ], [ %index.next, %loop ]
 374 ; CHECK-NEXT:    --> {0,+,8}<nuw><nsw><%loop> U: [0,25) S: [0,25) Exits: (8 * ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8))<nuw> LoopDispositions: { %loop: Computable }
 375 ; CHECK-NEXT:    %index.next = add nuw nsw i64 %index, 8
 376 ; CHECK-NEXT:    --> {8,+,8}<nuw><nsw><%loop> U: [8,33) S: [8,33) Exits: (8 + (8 * ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8))<nuw>) LoopDispositions: { %loop: Computable }
 377 ; CHECK-NEXT:  Determining loop execution counts for: @rewrite_zext_and_base_2
 378 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8)
 379 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 3
 380 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8)
 381 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 382 ;
 383 entry:
 384   %ext = zext i32 %n to i64
 385   %cmp5 = icmp ule i64 %ext, 32
 386   br i1 %cmp5, label %check.1, label %exit
 387
 388 check.1:
 389   %cmp.2 = icmp ule i32 %n, 48
 390   br i1 %cmp.2, label %check, label %exit
 391
 392 check:                                 ; preds = %entry
 393   %min.iters.check = icmp ult i64 %ext, 8
 394   %n.vec = and i64 %ext, -8
 395   br i1 %min.iters.check, label %exit, label %loop
 396
 397 loop:
 398   %index = phi i64 [ 0, %check ], [ %index.next, %loop ]
 399   %index.next = add nuw nsw i64 %index, 8
 400   %ec = icmp eq i64 %index.next, %n.vec
 401   br i1 %ec, label %exit, label %loop
 402
 403 exit:
 404   ret void
 405 }
 406
 407 define void @guard_pessimizes_analysis_step2(i1 %c, i32 %N) {
 408 ; CHECK-LABEL: 'guard_pessimizes_analysis_step2'
 409 ; CHECK-NEXT:  Classifying expressions for: @guard_pessimizes_analysis_step2
 410 ; CHECK-NEXT:    %N.ext = zext i32 %N to i64
 411 ; CHECK-NEXT:    --> (zext i32 %N to i64) U: [0,4294967296) S: [0,4294967296)
 412 ; CHECK-NEXT:    %init = phi i64 [ 2, %entry ], [ 4, %bb1 ]
 413 ; CHECK-NEXT:    --> %init U: [2,5) S: [2,5)
 414 ; CHECK-NEXT:    %iv = phi i64 [ %iv.next, %loop ], [ %init, %loop.ph ]
 415 ; CHECK-NEXT:    --> {%init,+,2}<nuw><nsw><%loop> U: [2,17) S: [2,17) Exits: ((2 * ((14 + (-1 * %init)<nsw>)<nsw> /u 2))<nuw><nsw> + %init) LoopDispositions: { %loop: Computable }
 416 ; CHECK-NEXT:    %iv.next = add i64 %iv, 2
 417 ; CHECK-NEXT:    --> {(2 + %init)<nuw><nsw>,+,2}<nuw><nsw><%loop> U: [4,19) S: [4,19) Exits: (2 + (2 * ((14 + (-1 * %init)<nsw>)<nsw> /u 2))<nuw><nsw> + %init) LoopDispositions: { %loop: Computable }
 418 ; CHECK-NEXT:  Determining loop execution counts for: @guard_pessimizes_analysis_step2
 419 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((14 + (-1 * %init)<nsw>)<nsw> /u 2)
 420 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 6
 421 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((14 + (-1 * %init)<nsw>)<nsw> /u 2)
 422 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 423 ;
 424 entry:
 425   %N.ext = zext i32 %N to i64
 426   br i1 %c, label %bb1, label %guard
 427
 428 bb1:
 429   br label %guard
 430
 431 guard:
 432   %init = phi i64 [ 2, %entry ], [ 4, %bb1 ]
 433   %c.1 = icmp ult i64 %init, %N.ext
 434   br i1 %c.1, label %loop.ph, label %exit
 435
 436 loop.ph:
 437   br label %loop
 438
 439 loop:
 440   %iv = phi i64 [ %iv.next, %loop ], [ %init, %loop.ph ]
 441   %iv.next = add i64 %iv, 2
 442   %exitcond = icmp eq i64 %iv.next, 16
 443   br i1 %exitcond, label %exit, label %loop
 444
 445 exit:
 446   ret void
 447 }
 448
 449 define i32 @rewrite_sext_slt_narrow_check(i32 %N, ptr %arr) {
 450 ; CHECK-LABEL: 'rewrite_sext_slt_narrow_check'
 451 ; CHECK-NEXT:  Classifying expressions for: @rewrite_sext_slt_narrow_check
 452 ; CHECK-NEXT:    %smin = call i32 @llvm.smax.i32(i32 %N, i32 4)
 453 ; CHECK-NEXT:    --> (4 smax %N) U: [4,-2147483648) S: [4,-2147483648)
 454 ; CHECK-NEXT:    %ext = sext i32 %smin to i64
 455 ; CHECK-NEXT:    --> (zext i32 (4 smax %N) to i64) U: [4,2147483648) S: [4,2147483648)
 456 ; CHECK-NEXT:    %n.vec = and i64 %ext, 28
 457 ; CHECK-NEXT:    --> (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw> U: [0,29) S: [0,29)
 458 ; CHECK-NEXT:    %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
 459 ; CHECK-NEXT:    --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (4 * ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4))<nuw> LoopDispositions: { %loop: Computable }
 460 ; CHECK-NEXT:    %gep = getelementptr inbounds i32, ptr %arr, i64 %index
 461 ; CHECK-NEXT:    --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }
 462 ; CHECK-NEXT:    %index.next = add nuw i64 %index, 4
 463 ; CHECK-NEXT:    --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 + (4 * ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4))<nuw>) LoopDispositions: { %loop: Computable }
 464 ; CHECK-NEXT:  Determining loop execution counts for: @rewrite_sext_slt_narrow_check
 465 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)
 466 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 3
 467 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)
 468 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 469 ;
 470 entry:
 471   %smin = call i32 @llvm.smax.i32(i32 %N, i32 4)
 472   %ext = sext i32 %smin to i64
 473   %min.iters.check = icmp slt i32 %smin, 17
 474   br i1 %min.iters.check, label %loop.ph, label %exit
 475
 476 loop.ph:
 477   %n.vec = and i64 %ext, 28
 478   br label %loop
 479
 480 ; %n.vec is [4, 16] and a multiple of 4.
 481 loop:
 482   %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
 483   %gep = getelementptr inbounds i32, ptr %arr, i64 %index
 484   store i32 0, ptr %gep
 485   %index.next = add nuw i64 %index, 4
 486   %ec = icmp eq i64 %index.next, %n.vec
 487   br i1 %ec, label %exit, label %loop
 488
 489 exit:
 490   ret i32 0
 491 }
 492
 493 define i32 @rewrite_zext_ult_narrow_check(i32 %N, ptr %arr) {
 494 ; CHECK-LABEL: 'rewrite_zext_ult_narrow_check'
 495 ; CHECK-NEXT:  Classifying expressions for: @rewrite_zext_ult_narrow_check
 496 ; CHECK-NEXT:    %umin = call i32 @llvm.umax.i32(i32 %N, i32 4)
 497 ; CHECK-NEXT:    --> (4 umax %N) U: [4,0) S: [4,0)
 498 ; CHECK-NEXT:    %ext = zext i32 %umin to i64
 499 ; CHECK-NEXT:    --> (4 umax (zext i32 %N to i64)) U: [4,4294967296) S: [4,4294967296)
 500 ; CHECK-NEXT:    %n.vec = and i64 %ext, 28
 501 ; CHECK-NEXT:    --> (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw> U: [0,29) S: [0,29)
 502 ; CHECK-NEXT:    %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
 503 ; CHECK-NEXT:    --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (4 * ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4))<nuw> LoopDispositions: { %loop: Computable }
 504 ; CHECK-NEXT:    %gep = getelementptr inbounds i32, ptr %arr, i64 %index
 505 ; CHECK-NEXT:    --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }
 506 ; CHECK-NEXT:    %index.next = add nuw i64 %index, 4
 507 ; CHECK-NEXT:    --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 + (4 * ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4))<nuw>) LoopDispositions: { %loop: Computable }
 508 ; CHECK-NEXT:  Determining loop execution counts for: @rewrite_zext_ult_narrow_check
 509 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)
 510 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 3
 511 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)
 512 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 513 ;
 514 entry:
 515   %umin = call i32 @llvm.umax.i32(i32 %N, i32 4)
 516   %ext = zext i32 %umin to i64
 517   %min.iters.check = icmp ult i32 %umin, 17
 518   br i1 %min.iters.check, label %loop.ph, label %exit
 519
 520 loop.ph:
 521   %n.vec = and i64 %ext, 28
 522   br label %loop
 523
 524 ; %n.vec is [4, 16] and a multiple of 4.
 525 loop:
 526   %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
 527   %gep = getelementptr inbounds i32, ptr %arr, i64 %index
 528   store i32 0, ptr %gep
 529   %index.next = add nuw i64 %index, 4
 530   %ec = icmp eq i64 %index.next, %n.vec
 531   br i1 %ec, label %exit, label %loop
 532
 533 exit:
 534   ret i32 0
 535 }
 536
 537 define i32 @rewrite_zext_ule_narrow_check(i32 %N, ptr %arr) {
 538 ; CHECK-LABEL: 'rewrite_zext_ule_narrow_check'
 539 ; CHECK-NEXT:  Classifying expressions for: @rewrite_zext_ule_narrow_check
 540 ; CHECK-NEXT:    %umin = call i32 @llvm.umax.i32(i32 %N, i32 4)
 541 ; CHECK-NEXT:    --> (4 umax %N) U: [4,0) S: [4,0)
 542 ; CHECK-NEXT:    %ext = zext i32 %umin to i64
 543 ; CHECK-NEXT:    --> (4 umax (zext i32 %N to i64)) U: [4,4294967296) S: [4,4294967296)
 544 ; CHECK-NEXT:    %n.vec = and i64 %ext, 28
 545 ; CHECK-NEXT:    --> (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw> U: [0,29) S: [0,29)
 546 ; CHECK-NEXT:    %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
 547 ; CHECK-NEXT:    --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (4 * ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4))<nuw> LoopDispositions: { %loop: Computable }
 548 ; CHECK-NEXT:    %gep = getelementptr inbounds i32, ptr %arr, i64 %index
 549 ; CHECK-NEXT:    --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }
 550 ; CHECK-NEXT:    %index.next = add nuw i64 %index, 4
 551 ; CHECK-NEXT:    --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 + (4 * ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4))<nuw>) LoopDispositions: { %loop: Computable }
 552 ; CHECK-NEXT:  Determining loop execution counts for: @rewrite_zext_ule_narrow_check
 553 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)
 554 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 3
 555 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)
 556 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 557 ;
 558 entry:
 559   %umin = call i32 @llvm.umax.i32(i32 %N, i32 4)
 560   %ext = zext i32 %umin to i64
 561   %min.iters.check = icmp ule i32 %umin, 16
 562   br i1 %min.iters.check, label %loop.ph, label %exit
 563
 564 loop.ph:
 565   %n.vec = and i64 %ext, 28
 566   br label %loop
 567
 568 ; %n.vec is [4, 16] and a multiple of 4.
 569 loop:
 570   %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
 571   %gep = getelementptr inbounds i32, ptr %arr, i64 %index
 572   store i32 0, ptr %gep
 573   %index.next = add nuw i64 %index, 4
 574   %ec = icmp eq i64 %index.next, %n.vec
 575   br i1 %ec, label %exit, label %loop
 576
 577 exit:
 578   ret i32 0
 579 }
 580
 581 define i32 @rewrite_zext_sle_narrow_check(i32 %N, ptr %arr) {
 582 ; CHECK-LABEL: 'rewrite_zext_sle_narrow_check'
 583 ; CHECK-NEXT:  Classifying expressions for: @rewrite_zext_sle_narrow_check
 584 ; CHECK-NEXT:    %smin = call i32 @llvm.smax.i32(i32 %N, i32 4)
 585 ; CHECK-NEXT:    --> (4 smax %N) U: [4,-2147483648) S: [4,-2147483648)
 586 ; CHECK-NEXT:    %ext = sext i32 %smin to i64
 587 ; CHECK-NEXT:    --> (zext i32 (4 smax %N) to i64) U: [4,2147483648) S: [4,2147483648)
 588 ; CHECK-NEXT:    %n.vec = and i64 %ext, 28
 589 ; CHECK-NEXT:    --> (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw> U: [0,29) S: [0,29)
 590 ; CHECK-NEXT:    %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
 591 ; CHECK-NEXT:    --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (4 * ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4))<nuw> LoopDispositions: { %loop: Computable }
 592 ; CHECK-NEXT:    %gep = getelementptr inbounds i32, ptr %arr, i64 %index
 593 ; CHECK-NEXT:    --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }
 594 ; CHECK-NEXT:    %index.next = add nuw i64 %index, 4
 595 ; CHECK-NEXT:    --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 + (4 * ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4))<nuw>) LoopDispositions: { %loop: Computable }
 596 ; CHECK-NEXT:  Determining loop execution counts for: @rewrite_zext_sle_narrow_check
 597 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)
 598 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 3
 599 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)
 600 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 601 ;
 602 entry:
 603   %smin = call i32 @llvm.smax.i32(i32 %N, i32 4)
 604   %ext = sext i32 %smin to i64
 605   %min.iters.check = icmp sle i32 %smin, 17
 606   br i1 %min.iters.check, label %loop.ph, label %exit
 607
 608 loop.ph:
 609   %n.vec = and i64 %ext, 28
 610   br label %loop
 611
 612 ; %n.vec is [4, 16] and a multiple of 4.
 613 loop:
 614   %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
 615   %gep = getelementptr inbounds i32, ptr %arr, i64 %index
 616   store i32 0, ptr %gep
 617   %index.next = add nuw i64 %index, 4
 618   %ec = icmp eq i64 %index.next, %n.vec
 619   br i1 %ec, label %exit, label %loop
 620
 621 exit:
 622   ret i32 0
 623 }
 624
 625 define i32 @rewrite_zext_uge_narrow_check(i32 %N, ptr %arr) {
 626 ; CHECK-LABEL: 'rewrite_zext_uge_narrow_check'
 627 ; CHECK-NEXT:  Classifying expressions for: @rewrite_zext_uge_narrow_check
 628 ; CHECK-NEXT:    %umin = call i32 @llvm.umin.i32(i32 %N, i32 16)
 629 ; CHECK-NEXT:    --> (16 umin %N) U: [0,17) S: [0,17)
 630 ; CHECK-NEXT:    %ext = zext i32 %umin to i64
 631 ; CHECK-NEXT:    --> (16 umin (zext i32 %N to i64)) U: [0,17) S: [0,17)
 632 ; CHECK-NEXT:    %n.vec = and i64 %ext, 28
 633 ; CHECK-NEXT:    --> (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw> U: [0,17) S: [0,17)
 634 ; CHECK-NEXT:    %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
 635 ; CHECK-NEXT:    --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (4 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4))<nuw> LoopDispositions: { %loop: Computable }
 636 ; CHECK-NEXT:    %gep = getelementptr inbounds i32, ptr %arr, i64 %index
 637 ; CHECK-NEXT:    --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }
 638 ; CHECK-NEXT:    %index.next = add nuw i64 %index, 4
 639 ; CHECK-NEXT:    --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 + (4 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4))<nuw>) LoopDispositions: { %loop: Computable }
 640 ; CHECK-NEXT:  Determining loop execution counts for: @rewrite_zext_uge_narrow_check
 641 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)
 642 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 3
 643 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)
 644 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 645 ;
 646 entry:
 647   %umin = call i32 @llvm.umin.i32(i32 %N, i32 16)
 648   %ext = zext i32 %umin to i64
 649   %min.iters.check = icmp uge i32 %umin, 4
 650   br i1 %min.iters.check, label %loop.ph, label %exit
 651
 652 loop.ph:
 653   %n.vec = and i64 %ext, 28
 654   br label %loop
 655
 656 ; %n.vec is [4, 16] and a multiple of 4.
 657 loop:
 658   %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
 659   %gep = getelementptr inbounds i32, ptr %arr, i64 %index
 660   store i32 0, ptr %gep
 661   %index.next = add nuw i64 %index, 4
 662   %ec = icmp eq i64 %index.next, %n.vec
 663   br i1 %ec, label %exit, label %loop
 664
 665 exit:
 666   ret i32 0
 667 }
 668
 669 define i32 @rewrite_sext_sge_narrow_check(i32 %N, ptr %arr) {
 670 ; CHECK-LABEL: 'rewrite_sext_sge_narrow_check'
 671 ; CHECK-NEXT:  Classifying expressions for: @rewrite_sext_sge_narrow_check
 672 ; CHECK-NEXT:    %smin = call i32 @llvm.smin.i32(i32 %N, i32 16)
 673 ; CHECK-NEXT:    --> (16 smin %N) U: [-2147483648,17) S: [-2147483648,17)
 674 ; CHECK-NEXT:    %ext = sext i32 %smin to i64
 675 ; CHECK-NEXT:    --> (16 smin (sext i32 %N to i64)) U: [-2147483648,17) S: [-2147483648,17)
 676 ; CHECK-NEXT:    %n.vec = and i64 %ext, 28
 677 ; CHECK-NEXT:    --> (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw> U: [0,29) S: [0,29)
 678 ; CHECK-NEXT:    %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
 679 ; CHECK-NEXT:    --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (4 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4))<nuw> LoopDispositions: { %loop: Computable }
 680 ; CHECK-NEXT:    %gep = getelementptr inbounds i32, ptr %arr, i64 %index
 681 ; CHECK-NEXT:    --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }
 682 ; CHECK-NEXT:    %index.next = add nuw i64 %index, 4
 683 ; CHECK-NEXT:    --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 + (4 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4))<nuw>) LoopDispositions: { %loop: Computable }
 684 ; CHECK-NEXT:  Determining loop execution counts for: @rewrite_sext_sge_narrow_check
 685 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)
 686 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 3
 687 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)
 688 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 689 ;
 690 entry:
 691   %smin = call i32 @llvm.smin.i32(i32 %N, i32 16)
 692   %ext = sext i32 %smin to i64
 693   %min.iters.check = icmp sge i32 %smin, 4
 694   br i1 %min.iters.check, label %loop.ph, label %exit
 695
 696 loop.ph:
 697   %n.vec = and i64 %ext, 28
 698   br label %loop
 699
 700 ; %n.vec is [4, 16] and a multiple of 4.
 701 loop:
 702   %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
 703   %gep = getelementptr inbounds i32, ptr %arr, i64 %index
 704   store i32 0, ptr %gep
 705   %index.next = add nuw i64 %index, 4
 706   %ec = icmp eq i64 %index.next, %n.vec
 707   br i1 %ec, label %exit, label %loop
 708
 709 exit:
 710   ret i32 0
 711 }
 712
 713 define i32 @rewrite_zext_ugt_narrow_check(i32 %N, ptr %arr) {
 714 ; CHECK-LABEL: 'rewrite_zext_ugt_narrow_check'
 715 ; CHECK-NEXT:  Classifying expressions for: @rewrite_zext_ugt_narrow_check
 716 ; CHECK-NEXT:    %umin = call i32 @llvm.umin.i32(i32 %N, i32 16)
 717 ; CHECK-NEXT:    --> (16 umin %N) U: [0,17) S: [0,17)
 718 ; CHECK-NEXT:    %ext = zext i32 %umin to i64
 719 ; CHECK-NEXT:    --> (16 umin (zext i32 %N to i64)) U: [0,17) S: [0,17)
 720 ; CHECK-NEXT:    %n.vec = and i64 %ext, 28
 721 ; CHECK-NEXT:    --> (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw> U: [0,17) S: [0,17)
 722 ; CHECK-NEXT:    %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
 723 ; CHECK-NEXT:    --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (4 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4))<nuw> LoopDispositions: { %loop: Computable }
 724 ; CHECK-NEXT:    %gep = getelementptr inbounds i32, ptr %arr, i64 %index
 725 ; CHECK-NEXT:    --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }
 726 ; CHECK-NEXT:    %index.next = add nuw i64 %index, 4
 727 ; CHECK-NEXT:    --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 + (4 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4))<nuw>) LoopDispositions: { %loop: Computable }
 728 ; CHECK-NEXT:  Determining loop execution counts for: @rewrite_zext_ugt_narrow_check
 729 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)
 730 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 3
 731 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)
 732 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 733 ;
 734 entry:
 735   %umin = call i32 @llvm.umin.i32(i32 %N, i32 16)
 736   %ext = zext i32 %umin to i64
 737   %min.iters.check = icmp ugt i32 %umin, 3
 738   br i1 %min.iters.check, label %loop.ph, label %exit
 739
 740 loop.ph:
 741   %n.vec = and i64 %ext, 28
 742   br label %loop
 743
 744 ; %n.vec is [4, 16] and a multiple of 4.
 745 loop:
 746   %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
 747   %gep = getelementptr inbounds i32, ptr %arr, i64 %index
 748   store i32 0, ptr %gep
 749   %index.next = add nuw i64 %index, 4
 750   %ec = icmp eq i64 %index.next, %n.vec
 751   br i1 %ec, label %exit, label %loop
 752
 753 exit:
 754   ret i32 0
 755 }
 756
 757 define i32 @rewrite_sext_sgt_narrow_check(i32 %N, ptr %arr) {
 758 ; CHECK-LABEL: 'rewrite_sext_sgt_narrow_check'
 759 ; CHECK-NEXT:  Classifying expressions for: @rewrite_sext_sgt_narrow_check
 760 ; CHECK-NEXT:    %smin = call i32 @llvm.smin.i32(i32 %N, i32 16)
 761 ; CHECK-NEXT:    --> (16 smin %N) U: [-2147483648,17) S: [-2147483648,17)
 762 ; CHECK-NEXT:    %ext = sext i32 %smin to i64
 763 ; CHECK-NEXT:    --> (16 smin (sext i32 %N to i64)) U: [-2147483648,17) S: [-2147483648,17)
 764 ; CHECK-NEXT:    %n.vec = and i64 %ext, 28
 765 ; CHECK-NEXT:    --> (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw> U: [0,29) S: [0,29)
 766 ; CHECK-NEXT:    %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
 767 ; CHECK-NEXT:    --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (4 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4))<nuw> LoopDispositions: { %loop: Computable }
 768 ; CHECK-NEXT:    %gep = getelementptr inbounds i32, ptr %arr, i64 %index
 769 ; CHECK-NEXT:    --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }
 770 ; CHECK-NEXT:    %index.next = add nuw i64 %index, 4
 771 ; CHECK-NEXT:    --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 + (4 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4))<nuw>) LoopDispositions: { %loop: Computable }
 772 ; CHECK-NEXT:  Determining loop execution counts for: @rewrite_sext_sgt_narrow_check
 773 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)
 774 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 3
 775 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)
 776 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 777 ;
 778 entry:
 779   %smin = call i32 @llvm.smin.i32(i32 %N, i32 16)
 780   %ext = sext i32 %smin to i64
 781   %min.iters.check = icmp sgt i32 %smin, 3
 782   br i1 %min.iters.check, label %loop.ph, label %exit
 783
 784 loop.ph:
 785   %n.vec = and i64 %ext, 28
 786   br label %loop
 787
 788 ; %n.vec is [4, 16) and a multiple of 4.
 789 loop:
 790   %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
 791   %gep = getelementptr inbounds i32, ptr %arr, i64 %index
 792   store i32 0, ptr %gep
 793   %index.next = add nuw i64 %index, 4
 794   %ec = icmp eq i64 %index.next, %n.vec
 795   br i1 %ec, label %exit, label %loop
 796
 797 exit:
 798   ret i32 0
 799 }
 800
 801 declare void @use(i64)
 802
 803 declare i32 @llvm.umin.i32(i32, i32)
 804 declare i64 @llvm.umin.i64(i64, i64)
 805 declare i32 @llvm.smin.i32(i32, i32)
 806 declare i64 @llvm.smin.i64(i64, i64)
 807
 808 declare i32 @llvm.umax.i32(i32, i32)
 809 declare i32 @llvm.smax.i32(i32, i32)