test/Transforms/IndVarSimplify/loop-predication.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -indvars -indvars-predicate-loops=1 -S | FileCheck %s
   3
   4 declare void @prevent_merging()
   5
   6 ; Base case
   7 define i32 @test1(i32* %array, i32 %length, i32 %n) {
   8 ; CHECK-LABEL: @test1(
   9 ; CHECK-NEXT:  loop.preheader:
  10 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ugt i32 [[N:%.*]], 1
  11 ; CHECK-NEXT:    [[UMAX:%.*]] = select i1 [[TMP0]], i32 [[N]], i32 1
  12 ; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[UMAX]], -1
  13 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i32 [[LENGTH:%.*]], [[TMP1]]
  14 ; CHECK-NEXT:    [[UMIN:%.*]] = select i1 [[TMP2]], i32 [[LENGTH]], i32 [[TMP1]]
  15 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[LENGTH]], [[UMIN]]
  16 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  17 ; CHECK:       loop:
  18 ; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
  19 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
  20 ; CHECK-NEXT:    br i1 [[TMP3]], label [[GUARDED]], label [[DEOPT:%.*]], !prof !0
  21 ; CHECK:       deopt:
  22 ; CHECK-NEXT:    call void @prevent_merging()
  23 ; CHECK-NEXT:    ret i32 -1
  24 ; CHECK:       guarded:
  25 ; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
  26 ; CHECK-NEXT:    [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY:%.*]], i64 [[I_I64]]
  27 ; CHECK-NEXT:    [[ARRAY_I:%.*]] = load i32, i32* [[ARRAY_I_PTR]], align 4
  28 ; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
  29 ; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
  30 ; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i32 [[I_NEXT]], [[N]]
  31 ; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
  32 ; CHECK:       exit:
  33 ; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
  34 ; CHECK-NEXT:    ret i32 [[RESULT]]
  35 ;
  36 loop.preheader:                                   ; preds = %entry
  37   br label %loop
  38
  39 loop:                                             ; preds = %guarded, %loop.preheader
  40   %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
  41   %i = phi i32 [ %i.next, %guarded ], [ 0, %loop.preheader ]
  42   %within.bounds = icmp ult i32 %i, %length
  43   br i1 %within.bounds, label %guarded, label %deopt, !prof !0
  44
  45 deopt:                                            ; preds = %loop
  46   call void @prevent_merging()
  47   ret i32 -1
  48
  49 guarded:                                          ; preds = %loop
  50   %i.i64 = zext i32 %i to i64
  51   %array.i.ptr = getelementptr inbounds i32, i32* %array, i64 %i.i64
  52   %array.i = load i32, i32* %array.i.ptr, align 4
  53   %loop.acc.next = add i32 %loop.acc, %array.i
  54   %i.next = add nuw i32 %i, 1
  55   %continue = icmp ult i32 %i.next, %n
  56   br i1 %continue, label %loop, label %exit
  57
  58 exit:                                             ; preds = %guarded, %entry
  59   %result = phi i32 [ %loop.acc.next, %guarded ]
  60   ret i32 %result
  61 }
  62
  63 ; Has side effect which must be reflected
  64 define i32 @neg_store(i32* %array, i32 %length, i32 %n) {
  65 ; CHECK-LABEL: @neg_store(
  66 ; CHECK-NEXT:  loop.preheader:
  67 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  68 ; CHECK:       loop:
  69 ; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
  70 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
  71 ; CHECK-NEXT:    [[WITHIN_BOUNDS:%.*]] = icmp ult i32 [[I]], [[LENGTH:%.*]]
  72 ; CHECK-NEXT:    br i1 [[WITHIN_BOUNDS]], label [[GUARDED]], label [[DEOPT:%.*]], !prof !0
  73 ; CHECK:       deopt:
  74 ; CHECK-NEXT:    call void @prevent_merging()
  75 ; CHECK-NEXT:    ret i32 -1
  76 ; CHECK:       guarded:
  77 ; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
  78 ; CHECK-NEXT:    [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY:%.*]], i64 [[I_I64]]
  79 ; CHECK-NEXT:    [[ARRAY_I:%.*]] = load i32, i32* [[ARRAY_I_PTR]], align 4
  80 ; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
  81 ; CHECK-NEXT:    store i32 0, i32* [[ARRAY_I_PTR]]
  82 ; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
  83 ; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i32 [[I_NEXT]], [[N:%.*]]
  84 ; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
  85 ; CHECK:       exit:
  86 ; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
  87 ; CHECK-NEXT:    ret i32 [[RESULT]]
  88 ;
  89 loop.preheader:                                   ; preds = %entry
  90   br label %loop
  91
  92 loop:                                             ; preds = %guarded, %loop.preheader
  93   %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
  94   %i = phi i32 [ %i.next, %guarded ], [ 0, %loop.preheader ]
  95   %within.bounds = icmp ult i32 %i, %length
  96   br i1 %within.bounds, label %guarded, label %deopt, !prof !0
  97
  98 deopt:                                            ; preds = %loop
  99   call void @prevent_merging()
 100   ret i32 -1
 101
 102 guarded:                                          ; preds = %loop
 103   %i.i64 = zext i32 %i to i64
 104   %array.i.ptr = getelementptr inbounds i32, i32* %array, i64 %i.i64
 105   %array.i = load i32, i32* %array.i.ptr, align 4
 106   %loop.acc.next = add i32 %loop.acc, %array.i
 107   store i32 0, i32* %array.i.ptr
 108   %i.next = add nuw i32 %i, 1
 109   %continue = icmp ult i32 %i.next, %n
 110   br i1 %continue, label %loop, label %exit
 111
 112 exit:                                             ; preds = %guarded, %entry
 113   %result = phi i32 [ %loop.acc.next, %guarded ]
 114   ret i32 %result
 115 }
 116
 117 declare void @maythrow()
 118
 119 ; May exit through implicit exception edge
 120 define i32 @neg_implicit_exit(i32* %array, i32 %length, i32 %n) {
 121 ; CHECK-LABEL: @neg_implicit_exit(
 122 ; CHECK-NEXT:  loop.preheader:
 123 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 124 ; CHECK:       loop:
 125 ; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
 126 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
 127 ; CHECK-NEXT:    call void @maythrow()
 128 ; CHECK-NEXT:    [[WITHIN_BOUNDS:%.*]] = icmp ult i32 [[I]], [[LENGTH:%.*]]
 129 ; CHECK-NEXT:    br i1 [[WITHIN_BOUNDS]], label [[GUARDED]], label [[DEOPT:%.*]], !prof !0
 130 ; CHECK:       deopt:
 131 ; CHECK-NEXT:    call void @prevent_merging()
 132 ; CHECK-NEXT:    ret i32 -1
 133 ; CHECK:       guarded:
 134 ; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
 135 ; CHECK-NEXT:    [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY:%.*]], i64 [[I_I64]]
 136 ; CHECK-NEXT:    [[ARRAY_I:%.*]] = load i32, i32* [[ARRAY_I_PTR]], align 4
 137 ; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
 138 ; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
 139 ; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i32 [[I_NEXT]], [[N:%.*]]
 140 ; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
 141 ; CHECK:       exit:
 142 ; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
 143 ; CHECK-NEXT:    ret i32 [[RESULT]]
 144 ;
 145 loop.preheader:                                   ; preds = %entry
 146   br label %loop
 147
 148 loop:                                             ; preds = %guarded, %loop.preheader
 149   %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
 150   %i = phi i32 [ %i.next, %guarded ], [ 0, %loop.preheader ]
 151   call void @maythrow()
 152   %within.bounds = icmp ult i32 %i, %length
 153   br i1 %within.bounds, label %guarded, label %deopt, !prof !0
 154
 155 deopt:                                            ; preds = %loop
 156   call void @prevent_merging()
 157   ret i32 -1
 158
 159 guarded:                                          ; preds = %loop
 160   %i.i64 = zext i32 %i to i64
 161   %array.i.ptr = getelementptr inbounds i32, i32* %array, i64 %i.i64
 162   %array.i = load i32, i32* %array.i.ptr, align 4
 163   %loop.acc.next = add i32 %loop.acc, %array.i
 164   %i.next = add nuw i32 %i, 1
 165   %continue = icmp ult i32 %i.next, %n
 166   br i1 %continue, label %loop, label %exit
 167
 168 exit:                                             ; preds = %guarded, %entry
 169   %result = phi i32 [ %loop.acc.next, %guarded ]
 170   ret i32 %result
 171 }
 172
 173
 174
 175 ; Base case, but in LFTR form (just for sanity checking)
 176 define i32 @test2(i32* %array, i32 %length, i32 %n) {
 177 ; CHECK-LABEL: @test2(
 178 ; CHECK-NEXT:  loop.preheader:
 179 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N:%.*]], -1
 180 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[LENGTH:%.*]], [[TMP0]]
 181 ; CHECK-NEXT:    [[UMIN:%.*]] = select i1 [[TMP1]], i32 [[LENGTH]], i32 [[TMP0]]
 182 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i32 [[LENGTH]], [[UMIN]]
 183 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 184 ; CHECK:       loop:
 185 ; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
 186 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
 187 ; CHECK-NEXT:    br i1 [[TMP2]], label [[GUARDED]], label [[DEOPT:%.*]], !prof !0
 188 ; CHECK:       deopt:
 189 ; CHECK-NEXT:    call void @prevent_merging()
 190 ; CHECK-NEXT:    ret i32 -1
 191 ; CHECK:       guarded:
 192 ; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
 193 ; CHECK-NEXT:    [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY:%.*]], i64 [[I_I64]]
 194 ; CHECK-NEXT:    [[ARRAY_I:%.*]] = load i32, i32* [[ARRAY_I_PTR]], align 4
 195 ; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
 196 ; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
 197 ; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ne i32 [[I_NEXT]], [[N]]
 198 ; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
 199 ; CHECK:       exit:
 200 ; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
 201 ; CHECK-NEXT:    ret i32 [[RESULT]]
 202 ;
 203 loop.preheader:                                   ; preds = %entry
 204   br label %loop
 205
 206 loop:                                             ; preds = %guarded, %loop.preheader
 207   %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
 208   %i = phi i32 [ %i.next, %guarded ], [ 0, %loop.preheader ]
 209   %within.bounds = icmp ne i32 %i, %length
 210   br i1 %within.bounds, label %guarded, label %deopt, !prof !0
 211
 212 deopt:                                            ; preds = %loop
 213   call void @prevent_merging()
 214   ret i32 -1
 215
 216 guarded:                                          ; preds = %loop
 217   %i.i64 = zext i32 %i to i64
 218   %array.i.ptr = getelementptr inbounds i32, i32* %array, i64 %i.i64
 219   %array.i = load i32, i32* %array.i.ptr, align 4
 220   %loop.acc.next = add i32 %loop.acc, %array.i
 221   %i.next = add nuw i32 %i, 1
 222   %continue = icmp ne i32 %i.next, %n
 223   br i1 %continue, label %loop, label %exit
 224
 225 exit:                                             ; preds = %guarded, %entry
 226   %result = phi i32 [ %loop.acc.next, %guarded ]
 227   ret i32 %result
 228 }
 229
 230 ; br (and rcheck1, rcheck2)
 231 define i32 @two_range_checks(i32* %array.1, i32 %length.1, i32* %array.2, i32 %length.2, i32 %n) {
 232 ; CHECK-LABEL: @two_range_checks(
 233 ; CHECK-NEXT:  loop.preheader:
 234 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[LENGTH_2:%.*]], [[LENGTH_1:%.*]]
 235 ; CHECK-NEXT:    [[UMIN:%.*]] = select i1 [[TMP0]], i32 [[LENGTH_2]], i32 [[LENGTH_1]]
 236 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[LENGTH_2]], [[LENGTH_1]]
 237 ; CHECK-NEXT:    [[UMIN1:%.*]] = select i1 [[TMP1]], i32 [[LENGTH_2]], i32 [[LENGTH_1]]
 238 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp ugt i32 [[N:%.*]], 1
 239 ; CHECK-NEXT:    [[UMAX:%.*]] = select i1 [[TMP2]], i32 [[N]], i32 1
 240 ; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[UMAX]], -1
 241 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp ult i32 [[UMIN1]], [[TMP3]]
 242 ; CHECK-NEXT:    [[UMIN2:%.*]] = select i1 [[TMP4]], i32 [[UMIN1]], i32 [[TMP3]]
 243 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp ne i32 [[UMIN]], [[UMIN2]]
 244 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 245 ; CHECK:       loop:
 246 ; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
 247 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
 248 ; CHECK-NEXT:    br i1 [[TMP5]], label [[GUARDED]], label [[DEOPT:%.*]], !prof !0
 249 ; CHECK:       deopt:
 250 ; CHECK-NEXT:    call void @prevent_merging()
 251 ; CHECK-NEXT:    ret i32 -1
 252 ; CHECK:       guarded:
 253 ; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
 254 ; CHECK-NEXT:    [[ARRAY_1_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY_1:%.*]], i64 [[I_I64]]
 255 ; CHECK-NEXT:    [[ARRAY_1_I:%.*]] = load i32, i32* [[ARRAY_1_I_PTR]], align 4
 256 ; CHECK-NEXT:    [[LOOP_ACC_1:%.*]] = add i32 [[LOOP_ACC]], [[ARRAY_1_I]]
 257 ; CHECK-NEXT:    [[ARRAY_2_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY_2:%.*]], i64 [[I_I64]]
 258 ; CHECK-NEXT:    [[ARRAY_2_I:%.*]] = load i32, i32* [[ARRAY_2_I_PTR]], align 4
 259 ; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC_1]], [[ARRAY_2_I]]
 260 ; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
 261 ; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i32 [[I_NEXT]], [[N]]
 262 ; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
 263 ; CHECK:       exit:
 264 ; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
 265 ; CHECK-NEXT:    ret i32 [[RESULT]]
 266 ;
 267 loop.preheader:                                   ; preds = %entry
 268   br label %loop
 269
 270 loop:                                             ; preds = %guarded, %loop.preheader
 271   %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
 272   %i = phi i32 [ %i.next, %guarded ], [ 0, %loop.preheader ]
 273   %within.bounds.1 = icmp ult i32 %i, %length.1
 274   %within.bounds.2 = icmp ult i32 %i, %length.2
 275   %within.bounds = and i1 %within.bounds.1, %within.bounds.2
 276   br i1 %within.bounds, label %guarded, label %deopt, !prof !0
 277
 278 deopt:                                            ; preds = %loop
 279   call void @prevent_merging()
 280   ret i32 -1
 281
 282 guarded:                                          ; preds = %loop
 283   %i.i64 = zext i32 %i to i64
 284   %array.1.i.ptr = getelementptr inbounds i32, i32* %array.1, i64 %i.i64
 285   %array.1.i = load i32, i32* %array.1.i.ptr, align 4
 286   %loop.acc.1 = add i32 %loop.acc, %array.1.i
 287   %array.2.i.ptr = getelementptr inbounds i32, i32* %array.2, i64 %i.i64
 288   %array.2.i = load i32, i32* %array.2.i.ptr, align 4
 289   %loop.acc.next = add i32 %loop.acc.1, %array.2.i
 290   %i.next = add nuw i32 %i, 1
 291   %continue = icmp ult i32 %i.next, %n
 292   br i1 %continue, label %loop, label %exit
 293
 294 exit:                                             ; preds = %guarded, %entry
 295   %result = phi i32 [ %loop.acc.next, %guarded ]
 296   ret i32 %result
 297 }
 298
 299 define i32 @three_range_checks(i32* %array.1, i32 %length.1, i32* %array.2, i32 %length.2, i32* %array.3, i32 %length.3, i32 %n) {
 300 ; CHECK-LABEL: @three_range_checks(
 301 ; CHECK-NEXT:  loop.preheader:
 302 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[LENGTH_3:%.*]], [[LENGTH_2:%.*]]
 303 ; CHECK-NEXT:    [[UMIN:%.*]] = select i1 [[TMP0]], i32 [[LENGTH_3]], i32 [[LENGTH_2]]
 304 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[UMIN]], [[LENGTH_1:%.*]]
 305 ; CHECK-NEXT:    [[UMIN1:%.*]] = select i1 [[TMP1]], i32 [[UMIN]], i32 [[LENGTH_1]]
 306 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i32 [[LENGTH_3]], [[LENGTH_2]]
 307 ; CHECK-NEXT:    [[UMIN2:%.*]] = select i1 [[TMP2]], i32 [[LENGTH_3]], i32 [[LENGTH_2]]
 308 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp ult i32 [[UMIN2]], [[LENGTH_1]]
 309 ; CHECK-NEXT:    [[UMIN3:%.*]] = select i1 [[TMP3]], i32 [[UMIN2]], i32 [[LENGTH_1]]
 310 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp ugt i32 [[N:%.*]], 1
 311 ; CHECK-NEXT:    [[UMAX:%.*]] = select i1 [[TMP4]], i32 [[N]], i32 1
 312 ; CHECK-NEXT:    [[TMP5:%.*]] = add i32 [[UMAX]], -1
 313 ; CHECK-NEXT:    [[TMP6:%.*]] = icmp ult i32 [[UMIN3]], [[TMP5]]
 314 ; CHECK-NEXT:    [[UMIN4:%.*]] = select i1 [[TMP6]], i32 [[UMIN3]], i32 [[TMP5]]
 315 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp ne i32 [[UMIN1]], [[UMIN4]]
 316 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 317 ; CHECK:       loop:
 318 ; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
 319 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
 320 ; CHECK-NEXT:    br i1 [[TMP7]], label [[GUARDED]], label [[DEOPT:%.*]], !prof !0
 321 ; CHECK:       deopt:
 322 ; CHECK-NEXT:    call void @prevent_merging()
 323 ; CHECK-NEXT:    ret i32 -1
 324 ; CHECK:       guarded:
 325 ; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
 326 ; CHECK-NEXT:    [[ARRAY_1_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY_1:%.*]], i64 [[I_I64]]
 327 ; CHECK-NEXT:    [[ARRAY_1_I:%.*]] = load i32, i32* [[ARRAY_1_I_PTR]], align 4
 328 ; CHECK-NEXT:    [[LOOP_ACC_1:%.*]] = add i32 [[LOOP_ACC]], [[ARRAY_1_I]]
 329 ; CHECK-NEXT:    [[ARRAY_2_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY_2:%.*]], i64 [[I_I64]]
 330 ; CHECK-NEXT:    [[ARRAY_2_I:%.*]] = load i32, i32* [[ARRAY_2_I_PTR]], align 4
 331 ; CHECK-NEXT:    [[LOOP_ACC_2:%.*]] = add i32 [[LOOP_ACC_1]], [[ARRAY_2_I]]
 332 ; CHECK-NEXT:    [[ARRAY_3_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY_3:%.*]], i64 [[I_I64]]
 333 ; CHECK-NEXT:    [[ARRAY_3_I:%.*]] = load i32, i32* [[ARRAY_3_I_PTR]], align 4
 334 ; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC_2]], [[ARRAY_3_I]]
 335 ; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
 336 ; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i32 [[I_NEXT]], [[N]]
 337 ; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
 338 ; CHECK:       exit:
 339 ; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
 340 ; CHECK-NEXT:    ret i32 [[RESULT]]
 341 ;
 342 loop.preheader:                                   ; preds = %entry
 343   br label %loop
 344
 345 loop:                                             ; preds = %guarded, %loop.preheader
 346   %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
 347   %i = phi i32 [ %i.next, %guarded ], [ 0, %loop.preheader ]
 348   %within.bounds.1 = icmp ult i32 %i, %length.1
 349   %within.bounds.2 = icmp ult i32 %i, %length.2
 350   %within.bounds.3 = icmp ult i32 %i, %length.3
 351   %within.bounds.1.and.2 = and i1 %within.bounds.1, %within.bounds.2
 352   %within.bounds = and i1 %within.bounds.1.and.2, %within.bounds.3
 353   br i1 %within.bounds, label %guarded, label %deopt, !prof !0
 354
 355 deopt:                                            ; preds = %loop
 356   call void @prevent_merging()
 357   ret i32 -1
 358
 359 guarded:                                          ; preds = %loop
 360   %i.i64 = zext i32 %i to i64
 361   %array.1.i.ptr = getelementptr inbounds i32, i32* %array.1, i64 %i.i64
 362   %array.1.i = load i32, i32* %array.1.i.ptr, align 4
 363   %loop.acc.1 = add i32 %loop.acc, %array.1.i
 364   %array.2.i.ptr = getelementptr inbounds i32, i32* %array.2, i64 %i.i64
 365   %array.2.i = load i32, i32* %array.2.i.ptr, align 4
 366   %loop.acc.2 = add i32 %loop.acc.1, %array.2.i
 367   %array.3.i.ptr = getelementptr inbounds i32, i32* %array.3, i64 %i.i64
 368   %array.3.i = load i32, i32* %array.3.i.ptr, align 4
 369   %loop.acc.next = add i32 %loop.acc.2, %array.3.i
 370   %i.next = add nuw i32 %i, 1
 371   %continue = icmp ult i32 %i.next, %n
 372   br i1 %continue, label %loop, label %exit
 373
 374 exit:                                             ; preds = %guarded, %entry
 375   %result = phi i32 [ %loop.acc.next, %guarded ]
 376   ret i32 %result
 377 }
 378
 379 ; Analogous to the above, but with two distinct branches (on different conditions)
 380 define i32 @distinct_checks(i32* %array.1, i32 %length.1, i32* %array.2, i32 %length.2, i32* %array.3, i32 %length.3, i32 %n) {
 381 ; CHECK-LABEL: @distinct_checks(
 382 ; CHECK-NEXT:  loop.preheader:
 383 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[LENGTH_2:%.*]], [[LENGTH_1:%.*]]
 384 ; CHECK-NEXT:    [[UMIN:%.*]] = select i1 [[TMP0]], i32 [[LENGTH_2]], i32 [[LENGTH_1]]
 385 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 [[N:%.*]], 1
 386 ; CHECK-NEXT:    [[UMAX:%.*]] = select i1 [[TMP1]], i32 [[N]], i32 1
 387 ; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[UMAX]], -1
 388 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp ult i32 [[UMIN]], [[TMP2]]
 389 ; CHECK-NEXT:    [[UMIN1:%.*]] = select i1 [[TMP3]], i32 [[UMIN]], i32 [[TMP2]]
 390 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp ne i32 [[LENGTH_1]], [[UMIN1]]
 391 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp ne i32 [[LENGTH_2]], [[UMIN1]]
 392 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 393 ; CHECK:       loop:
 394 ; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED1:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
 395 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED1]] ], [ 0, [[LOOP_PREHEADER]] ]
 396 ; CHECK-NEXT:    br i1 [[TMP4]], label [[GUARDED:%.*]], label [[DEOPT:%.*]], !prof !0
 397 ; CHECK:       deopt:
 398 ; CHECK-NEXT:    call void @prevent_merging()
 399 ; CHECK-NEXT:    ret i32 -1
 400 ; CHECK:       guarded:
 401 ; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
 402 ; CHECK-NEXT:    [[ARRAY_1_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY_1:%.*]], i64 [[I_I64]]
 403 ; CHECK-NEXT:    [[ARRAY_1_I:%.*]] = load i32, i32* [[ARRAY_1_I_PTR]], align 4
 404 ; CHECK-NEXT:    [[LOOP_ACC_1:%.*]] = add i32 [[LOOP_ACC]], [[ARRAY_1_I]]
 405 ; CHECK-NEXT:    br i1 [[TMP5]], label [[GUARDED1]], label [[DEOPT2:%.*]], !prof !0
 406 ; CHECK:       deopt2:
 407 ; CHECK-NEXT:    call void @prevent_merging()
 408 ; CHECK-NEXT:    ret i32 -1
 409 ; CHECK:       guarded1:
 410 ; CHECK-NEXT:    [[ARRAY_3_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY_3:%.*]], i64 [[I_I64]]
 411 ; CHECK-NEXT:    [[ARRAY_3_I:%.*]] = load i32, i32* [[ARRAY_3_I_PTR]], align 4
 412 ; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC_1]], [[ARRAY_3_I]]
 413 ; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
 414 ; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i32 [[I_NEXT]], [[N]]
 415 ; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
 416 ; CHECK:       exit:
 417 ; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED1]] ]
 418 ; CHECK-NEXT:    ret i32 [[RESULT]]
 419 ;
 420 loop.preheader:                                   ; preds = %entry
 421   br label %loop
 422
 423 loop:                                             ; preds = %guarded4, %loop.preheader
 424   %loop.acc = phi i32 [ %loop.acc.next, %guarded1 ], [ 0, %loop.preheader ]
 425   %i = phi i32 [ %i.next, %guarded1 ], [ 0, %loop.preheader ]
 426   %within.bounds.1 = icmp ult i32 %i, %length.1
 427   br i1 %within.bounds.1, label %guarded, label %deopt, !prof !0
 428
 429 deopt:                                            ; preds = %loop
 430   call void @prevent_merging()
 431   ret i32 -1
 432
 433 guarded:                                          ; preds = %loop
 434   %i.i64 = zext i32 %i to i64
 435   %array.1.i.ptr = getelementptr inbounds i32, i32* %array.1, i64 %i.i64
 436   %array.1.i = load i32, i32* %array.1.i.ptr, align 4
 437   %loop.acc.1 = add i32 %loop.acc, %array.1.i
 438   %within.bounds.2 = icmp ult i32 %i, %length.2
 439   br i1 %within.bounds.2, label %guarded1, label %deopt2, !prof !0
 440
 441 deopt2:                                           ; preds = %guarded
 442   call void @prevent_merging()
 443   ret i32 -1
 444
 445 guarded1:                                         ; preds = %guarded1
 446   %array.3.i.ptr = getelementptr inbounds i32, i32* %array.3, i64 %i.i64
 447   %array.3.i = load i32, i32* %array.3.i.ptr, align 4
 448   %loop.acc.next = add i32 %loop.acc.1, %array.3.i
 449   %i.next = add nuw i32 %i, 1
 450   %continue = icmp ult i32 %i.next, %n
 451   br i1 %continue, label %loop, label %exit
 452
 453 exit:
 454   %result = phi i32 [ %loop.acc.next, %guarded1 ]
 455   ret i32 %result
 456 }
 457
 458 define i32 @duplicate_checks(i32* %array.1, i32* %array.2, i32* %array.3, i32 %length, i32 %n) {
 459 ; CHECK-LABEL: @duplicate_checks(
 460 ; CHECK-NEXT:  loop.preheader:
 461 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ugt i32 [[N:%.*]], 1
 462 ; CHECK-NEXT:    [[UMAX:%.*]] = select i1 [[TMP0]], i32 [[N]], i32 1
 463 ; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[UMAX]], -1
 464 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i32 [[LENGTH:%.*]], [[TMP1]]
 465 ; CHECK-NEXT:    [[UMIN:%.*]] = select i1 [[TMP2]], i32 [[LENGTH]], i32 [[TMP1]]
 466 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[LENGTH]], [[UMIN]]
 467 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp ne i32 [[LENGTH]], [[UMIN]]
 468 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 469 ; CHECK:       loop:
 470 ; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED1:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
 471 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED1]] ], [ 0, [[LOOP_PREHEADER]] ]
 472 ; CHECK-NEXT:    br i1 [[TMP3]], label [[GUARDED:%.*]], label [[DEOPT:%.*]], !prof !0
 473 ; CHECK:       deopt:
 474 ; CHECK-NEXT:    call void @prevent_merging()
 475 ; CHECK-NEXT:    ret i32 -1
 476 ; CHECK:       guarded:
 477 ; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
 478 ; CHECK-NEXT:    [[ARRAY_1_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY_1:%.*]], i64 [[I_I64]]
 479 ; CHECK-NEXT:    [[ARRAY_1_I:%.*]] = load i32, i32* [[ARRAY_1_I_PTR]], align 4
 480 ; CHECK-NEXT:    [[LOOP_ACC_1:%.*]] = add i32 [[LOOP_ACC]], [[ARRAY_1_I]]
 481 ; CHECK-NEXT:    br i1 [[TMP4]], label [[GUARDED1]], label [[DEOPT2:%.*]], !prof !0
 482 ; CHECK:       deopt2:
 483 ; CHECK-NEXT:    call void @prevent_merging()
 484 ; CHECK-NEXT:    ret i32 -1
 485 ; CHECK:       guarded1:
 486 ; CHECK-NEXT:    [[ARRAY_3_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY_3:%.*]], i64 [[I_I64]]
 487 ; CHECK-NEXT:    [[ARRAY_3_I:%.*]] = load i32, i32* [[ARRAY_3_I_PTR]], align 4
 488 ; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC_1]], [[ARRAY_3_I]]
 489 ; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
 490 ; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i32 [[I_NEXT]], [[N]]
 491 ; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
 492 ; CHECK:       exit:
 493 ; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED1]] ]
 494 ; CHECK-NEXT:    ret i32 [[RESULT]]
 495 ;
 496 loop.preheader:                                   ; preds = %entry
 497   br label %loop
 498
 499 loop:                                             ; preds = %guarded4, %loop.preheader
 500   %loop.acc = phi i32 [ %loop.acc.next, %guarded1 ], [ 0, %loop.preheader ]
 501   %i = phi i32 [ %i.next, %guarded1 ], [ 0, %loop.preheader ]
 502   %within.bounds.1 = icmp ult i32 %i, %length
 503   br i1 %within.bounds.1, label %guarded, label %deopt, !prof !0
 504
 505 deopt:                                            ; preds = %loop
 506   call void @prevent_merging()
 507   ret i32 -1
 508
 509 guarded:                                          ; preds = %loop
 510   %i.i64 = zext i32 %i to i64
 511   %array.1.i.ptr = getelementptr inbounds i32, i32* %array.1, i64 %i.i64
 512   %array.1.i = load i32, i32* %array.1.i.ptr, align 4
 513   %loop.acc.1 = add i32 %loop.acc, %array.1.i
 514   %within.bounds.2 = icmp ult i32 %i, %length
 515   br i1 %within.bounds.2, label %guarded1, label %deopt2, !prof !0
 516
 517 deopt2:                                           ; preds = %guarded
 518   call void @prevent_merging()
 519   ret i32 -1
 520
 521 guarded1:                                         ; preds = %guarded1
 522   %array.3.i.ptr = getelementptr inbounds i32, i32* %array.3, i64 %i.i64
 523   %array.3.i = load i32, i32* %array.3.i.ptr, align 4
 524   %loop.acc.next = add i32 %loop.acc.1, %array.3.i
 525   %i.next = add nuw i32 %i, 1
 526   %continue = icmp ult i32 %i.next, %n
 527   br i1 %continue, label %loop, label %exit
 528
 529 exit:
 530   %result = phi i32 [ %loop.acc.next, %guarded1 ]
 531   ret i32 %result
 532 }
 533
 534
 535 define i32 @provably_taken(i32* %array, i32* %length.ptr) {
 536 ; CHECK-LABEL: @provably_taken(
 537 ; CHECK-NEXT:  loop.preheader:
 538 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 539 ; CHECK:       loop:
 540 ; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
 541 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
 542 ; CHECK-NEXT:    br i1 false, label [[GUARDED]], label [[DEOPT:%.*]], !prof !0
 543 ; CHECK:       deopt:
 544 ; CHECK-NEXT:    call void @prevent_merging()
 545 ; CHECK-NEXT:    ret i32 -1
 546 ; CHECK:       guarded:
 547 ; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
 548 ; CHECK-NEXT:    [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY:%.*]], i64 [[I_I64]]
 549 ; CHECK-NEXT:    [[ARRAY_I:%.*]] = load i32, i32* [[ARRAY_I_PTR]], align 4
 550 ; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
 551 ; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i32 [[I]], 1
 552 ; CHECK-NEXT:    br i1 true, label [[LOOP]], label [[EXIT:%.*]]
 553 ; CHECK:       exit:
 554 ; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
 555 ; CHECK-NEXT:    ret i32 [[RESULT]]
 556 ;
 557 loop.preheader:
 558   %length = load i32, i32* %length.ptr, !range !2
 559   br label %loop
 560
 561 loop:                                             ; preds = %guarded, %loop.preheader
 562   %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
 563   %i = phi i32 [ %i.next, %guarded ], [ 0, %loop.preheader ]
 564   %within.bounds = icmp ult i32 %i, %length
 565   br i1 %within.bounds, label %guarded, label %deopt, !prof !0
 566
 567 deopt:                                            ; preds = %loop
 568   call void @prevent_merging()
 569   ret i32 -1
 570
 571 guarded:                                          ; preds = %loop
 572   %i.i64 = zext i32 %i to i64
 573   %array.i.ptr = getelementptr inbounds i32, i32* %array, i64 %i.i64
 574   %array.i = load i32, i32* %array.i.ptr, align 4
 575   %loop.acc.next = add i32 %loop.acc, %array.i
 576   %i.next = add nuw i32 %i, 1
 577   %continue = icmp slt i32 %i.next, 200
 578   br i1 %continue, label %loop, label %exit
 579
 580 exit:                                             ; preds = %guarded
 581   %result = phi i32 [ %loop.acc.next, %guarded ]
 582   ret i32 %result
 583 }
 584
 585 ; Non-latch exits can still be predicated
 586 define i32 @unconditional_latch(i32* %a, i32 %length) {
 587 ; CHECK-LABEL: @unconditional_latch(
 588 ; CHECK-NEXT:  loop.preheader:
 589 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 590 ; CHECK:       loop:
 591 ; CHECK-NEXT:    br i1 false, label [[GUARDED:%.*]], label [[DEOPT:%.*]], !prof !0
 592 ; CHECK:       deopt:
 593 ; CHECK-NEXT:    call void @prevent_merging()
 594 ; CHECK-NEXT:    ret i32 -1
 595 ; CHECK:       guarded:
 596 ; CHECK-NEXT:    br label [[LOOP]]
 597 ;
 598 loop.preheader:
 599   br label %loop
 600
 601 loop:                                             ; preds = %guarded, %loop.preheader
 602   %i = phi i32 [ %i.next, %guarded ], [ 400, %loop.preheader ]
 603   %within.bounds = icmp ult i32 %i, %length
 604   br i1 %within.bounds, label %guarded, label %deopt, !prof !0
 605
 606 deopt:                                            ; preds = %loop
 607   call void @prevent_merging()
 608   ret i32 -1
 609
 610 guarded:                                          ; preds = %loop
 611   %i.next = add i32 %i, 1
 612   br label %loop
 613 }
 614
 615 ; Side effect in loop must run proper number of times
 616 define i32 @unconditional_latch_with_side_effect(i32* %a, i32 %length) {
 617 ; CHECK-LABEL: @unconditional_latch_with_side_effect(
 618 ; CHECK-NEXT:  loop.preheader:
 619 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 620 ; CHECK:       loop:
 621 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED:%.*]] ], [ 400, [[LOOP_PREHEADER:%.*]] ]
 622 ; CHECK-NEXT:    [[WITHIN_BOUNDS:%.*]] = icmp ult i32 [[I]], [[LENGTH:%.*]]
 623 ; CHECK-NEXT:    br i1 [[WITHIN_BOUNDS]], label [[GUARDED]], label [[DEOPT:%.*]], !prof !0
 624 ; CHECK:       deopt:
 625 ; CHECK-NEXT:    call void @prevent_merging()
 626 ; CHECK-NEXT:    ret i32 -1
 627 ; CHECK:       guarded:
 628 ; CHECK-NEXT:    store volatile i32 0, i32* [[A:%.*]]
 629 ; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
 630 ; CHECK-NEXT:    br label [[LOOP]]
 631 ;
 632 loop.preheader:
 633   br label %loop
 634
 635 loop:                                             ; preds = %guarded, %loop.preheader
 636   %i = phi i32 [ %i.next, %guarded ], [ 400, %loop.preheader ]
 637   %within.bounds = icmp ult i32 %i, %length
 638   br i1 %within.bounds, label %guarded, label %deopt, !prof !0
 639
 640 deopt:                                            ; preds = %loop
 641   call void @prevent_merging()
 642   ret i32 -1
 643
 644 guarded:                                          ; preds = %loop
 645   store volatile i32 0, i32* %a
 646   %i.next = add i32 %i, 1
 647   br label %loop
 648 }
 649
 650 ; Demonstrate that this approach works with IVs of different steps, and types
 651 ; This version uses a manually lftred exit condition to work around an issue described
 652 ; in detail on next test.
 653 define i32 @different_ivs(i32* %array, i32 %length, i32 %n) {
 654 ; CHECK-LABEL: @different_ivs(
 655 ; CHECK-NEXT:  loop.preheader:
 656 ; CHECK-NEXT:    [[N64:%.*]] = zext i32 [[N:%.*]] to i64
 657 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ugt i64 [[N64]], 1
 658 ; CHECK-NEXT:    [[UMAX:%.*]] = select i1 [[TMP0]], i64 [[N64]], i64 1
 659 ; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i64 [[UMAX]], -1
 660 ; CHECK-NEXT:    [[TMP2:%.*]] = zext i32 [[LENGTH:%.*]] to i64
 661 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp ult i64 [[TMP1]], [[TMP2]]
 662 ; CHECK-NEXT:    [[UMIN:%.*]] = select i1 [[TMP3]], i64 [[TMP1]], i64 [[TMP2]]
 663 ; CHECK-NEXT:    [[TMP4:%.*]] = zext i32 [[LENGTH]] to i64
 664 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp ne i64 [[TMP4]], [[UMIN]]
 665 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 666 ; CHECK:       loop:
 667 ; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
 668 ; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
 669 ; CHECK-NEXT:    br i1 [[TMP5]], label [[GUARDED]], label [[DEOPT:%.*]], !prof !0
 670 ; CHECK:       deopt:
 671 ; CHECK-NEXT:    call void @prevent_merging()
 672 ; CHECK-NEXT:    ret i32 -1
 673 ; CHECK:       guarded:
 674 ; CHECK-NEXT:    [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY:%.*]], i64 [[I]]
 675 ; CHECK-NEXT:    [[ARRAY_I:%.*]] = load i32, i32* [[ARRAY_I_PTR]], align 4
 676 ; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
 677 ; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i64 [[I]], 1
 678 ; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i64 [[I_NEXT]], [[N64]]
 679 ; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
 680 ; CHECK:       exit:
 681 ; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
 682 ; CHECK-NEXT:    ret i32 [[RESULT]]
 683 ;
 684 loop.preheader:
 685   %j.start = sub nuw nsw i32 %length, 1
 686   %n64 = zext i32 %n to i64
 687   br label %loop
 688
 689 loop:
 690   %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
 691   %i = phi i64 [ %i.next, %guarded ], [ 0, %loop.preheader ]
 692   %j = phi i32 [ %j.next, %guarded ], [ %j.start, %loop.preheader ]
 693   %within.bounds = icmp ne i32 %j, -1
 694   br i1 %within.bounds, label %guarded, label %deopt, !prof !0
 695
 696 deopt:
 697   call void @prevent_merging()
 698   ret i32 -1
 699
 700 guarded:
 701   %array.i.ptr = getelementptr inbounds i32, i32* %array, i64 %i
 702   %array.i = load i32, i32* %array.i.ptr, align 4
 703   %loop.acc.next = add i32 %loop.acc, %array.i
 704   %i.next = add nuw i64 %i, 1
 705   %j.next = sub nuw i32 %j, 1
 706   %continue = icmp ult i64 %i.next, %n64
 707   br i1 %continue, label %loop, label %exit
 708
 709 exit:
 710   %result = phi i32 [ %loop.acc.next, %guarded ]
 711   ret i32 %result
 712 }
 713
 714 ; TODO: We're failing to compute an exit count for the bounds check.
 715 ; From some quick analysis, it looks like we don't handle -1 step
 716 ; in howManyLessThans.  Should be a simple fix.
 717 define i32 @different_ivs2(i32* %array, i32 %length, i32 %n) {
 718 ; CHECK-LABEL: @different_ivs2(
 719 ; CHECK-NEXT:  entry:
 720 ; CHECK-NEXT:    [[POS_LENGTH:%.*]] = icmp sgt i32 [[LENGTH:%.*]], 0
 721 ; CHECK-NEXT:    br i1 [[POS_LENGTH]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 722 ; CHECK:       loop.preheader:
 723 ; CHECK-NEXT:    [[J_START:%.*]] = sub nuw nsw i32 [[LENGTH]], 1
 724 ; CHECK-NEXT:    [[N64:%.*]] = zext i32 [[N:%.*]] to i64
 725 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 726 ; CHECK:       loop:
 727 ; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
 728 ; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
 729 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ [[J_NEXT:%.*]], [[GUARDED]] ], [ [[J_START]], [[LOOP_PREHEADER]] ]
 730 ; CHECK-NEXT:    [[WITHIN_BOUNDS:%.*]] = icmp ult i32 [[J]], [[LENGTH]]
 731 ; CHECK-NEXT:    br i1 [[WITHIN_BOUNDS]], label [[GUARDED]], label [[DEOPT:%.*]], !prof !0
 732 ; CHECK:       deopt:
 733 ; CHECK-NEXT:    call void @prevent_merging()
 734 ; CHECK-NEXT:    ret i32 -1
 735 ; CHECK:       guarded:
 736 ; CHECK-NEXT:    [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY:%.*]], i64 [[I]]
 737 ; CHECK-NEXT:    [[ARRAY_I:%.*]] = load i32, i32* [[ARRAY_I_PTR]], align 4
 738 ; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
 739 ; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i64 [[I]], 1
 740 ; CHECK-NEXT:    [[J_NEXT]] = sub nuw i32 [[J]], 1
 741 ; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i64 [[I_NEXT]], [[N64]]
 742 ; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
 743 ; CHECK:       exit.loopexit:
 744 ; CHECK-NEXT:    [[LOOP_ACC_NEXT_LCSSA:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
 745 ; CHECK-NEXT:    br label [[EXIT]]
 746 ; CHECK:       exit:
 747 ; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_ACC_NEXT_LCSSA]], [[EXIT_LOOPEXIT]] ]
 748 ; CHECK-NEXT:    ret i32 [[RESULT]]
 749 ;
 750 entry:
 751   %pos_length = icmp sgt i32 %length, 0
 752   br i1 %pos_length, label %loop.preheader, label %exit
 753
 754 loop.preheader:
 755   %j.start = sub nuw nsw i32 %length, 1
 756   %n64 = zext i32 %n to i64
 757   br label %loop
 758
 759 loop:
 760   %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
 761   %i = phi i64 [ %i.next, %guarded ], [ 0, %loop.preheader ]
 762   %j = phi i32 [ %j.next, %guarded ], [ %j.start, %loop.preheader ]
 763   %within.bounds = icmp ult i32 %j, %length
 764   br i1 %within.bounds, label %guarded, label %deopt, !prof !0
 765
 766 deopt:
 767   call void @prevent_merging()
 768   ret i32 -1
 769
 770 guarded:
 771   %array.i.ptr = getelementptr inbounds i32, i32* %array, i64 %i
 772   %array.i = load i32, i32* %array.i.ptr, align 4
 773   %loop.acc.next = add i32 %loop.acc, %array.i
 774   %i.next = add nuw i64 %i, 1
 775   %j.next = sub nuw i32 %j, 1
 776   %continue = icmp ult i64 %i.next, %n64
 777   br i1 %continue, label %loop, label %exit
 778
 779 exit:
 780   %result = phi i32 [ %loop.acc.next, %guarded ], [0, %entry]
 781   ret i32 %result
 782 }
 783
 784 ; If we have a dominating exit (exit1) which can't be itself rewritten, we
 785 ; can't rewrite a later exit (exit2).  Doing so would cause the loop to exit
 786 ; from the exit2 when it should have exited from exit1.
 787 ; FIXME: This currently demonstrates a miscompile.
 788 define i32 @neg_dominating_exit(i32* %array, i32 %length, i32 %n) {
 789 ; CHECK-LABEL: @neg_dominating_exit(
 790 ; CHECK-NEXT:  loop.preheader:
 791 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ugt i32 [[N:%.*]], 1
 792 ; CHECK-NEXT:    [[UMAX:%.*]] = select i1 [[TMP0]], i32 [[N]], i32 1
 793 ; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[UMAX]], -1
 794 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i32 [[LENGTH:%.*]], [[TMP1]]
 795 ; CHECK-NEXT:    [[UMIN:%.*]] = select i1 [[TMP2]], i32 [[LENGTH]], i32 [[TMP1]]
 796 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[LENGTH]], [[UMIN]]
 797 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 798 ; CHECK:       loop:
 799 ; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED2:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
 800 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED2]] ], [ 0, [[LOOP_PREHEADER]] ]
 801 ; CHECK-NEXT:    [[WITHIN_BOUNDS:%.*]] = icmp ult i32 [[I]], [[LENGTH]]
 802 ; CHECK-NEXT:    br i1 [[WITHIN_BOUNDS]], label [[GUARDED:%.*]], label [[DEOPT:%.*]], !prof !0
 803 ; CHECK:       deopt:
 804 ; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC]], [[LOOP]] ]
 805 ; CHECK-NEXT:    call void @prevent_merging()
 806 ; CHECK-NEXT:    ret i32 [[RESULT]]
 807 ; CHECK:       guarded:
 808 ; CHECK-NEXT:    br i1 [[TMP3]], label [[GUARDED2]], label [[DEOPT2:%.*]], !prof !0
 809 ; CHECK:       deopt2:
 810 ; CHECK-NEXT:    call void @prevent_merging()
 811 ; CHECK-NEXT:    ret i32 -1
 812 ; CHECK:       guarded2:
 813 ; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
 814 ; CHECK-NEXT:    [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY:%.*]], i64 [[I_I64]]
 815 ; CHECK-NEXT:    [[ARRAY_I:%.*]] = load i32, i32* [[ARRAY_I_PTR]], align 4
 816 ; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
 817 ; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
 818 ; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i32 [[I_NEXT]], [[N]]
 819 ; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
 820 ; CHECK:       exit:
 821 ; CHECK-NEXT:    [[RESULT2:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED2]] ]
 822 ; CHECK-NEXT:    ret i32 [[RESULT2]]
 823 ;
 824 loop.preheader:                                   ; preds = %entry
 825   br label %loop
 826
 827 loop:                                             ; preds = %guarded, %loop.preheader
 828   %loop.acc = phi i32 [ %loop.acc.next, %guarded2 ], [ 0, %loop.preheader ]
 829   %i = phi i32 [ %i.next, %guarded2 ], [ 0, %loop.preheader ]
 830   %within.bounds = icmp ult i32 %i, %length
 831   br i1 %within.bounds, label %guarded, label %deopt, !prof !0
 832
 833 deopt:                                            ; preds = %loop
 834   %result = phi i32 [ %loop.acc, %loop ]
 835   call void @prevent_merging()
 836   ret i32 %result
 837
 838 guarded:                                          ; preds = %loop
 839   %within.bounds2 = icmp ult i32 %i, %length
 840   br i1 %within.bounds2, label %guarded2, label %deopt2, !prof !0
 841
 842 deopt2:                                            ; preds = %loop
 843   call void @prevent_merging()
 844   ret i32 -1
 845
 846 guarded2:                                          ; preds = %loop
 847   %i.i64 = zext i32 %i to i64
 848   %array.i.ptr = getelementptr inbounds i32, i32* %array, i64 %i.i64
 849   %array.i = load i32, i32* %array.i.ptr, align 4
 850   %loop.acc.next = add i32 %loop.acc, %array.i
 851   %i.next = add nuw i32 %i, 1
 852   %continue = icmp ult i32 %i.next, %n
 853   br i1 %continue, label %loop, label %exit
 854
 855 exit:                                             ; preds = %guarded, %entry
 856   %result2 = phi i32 [ %loop.acc.next, %guarded2 ]
 857   ret i32 %result2
 858 }
 859
 860
 861 declare i32 @llvm.experimental.deoptimize.i32(...)
 862
 863 !0 = !{!"branch_weights", i32 1048576, i32 1}
 864 !1 = !{i32 1, i32 -2147483648}
 865 !2 = !{i32 0, i32 50}