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:    br label [[LOOP:%.*]]
 468 ; CHECK:       loop:
 469 ; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED1:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
 470 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED1]] ], [ 0, [[LOOP_PREHEADER]] ]
 471 ; CHECK-NEXT:    br i1 [[TMP3]], label [[GUARDED:%.*]], label [[DEOPT:%.*]], !prof !0
 472 ; CHECK:       deopt:
 473 ; CHECK-NEXT:    call void @prevent_merging()
 474 ; CHECK-NEXT:    ret i32 -1
 475 ; CHECK:       guarded:
 476 ; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
 477 ; CHECK-NEXT:    [[ARRAY_1_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY_1:%.*]], i64 [[I_I64]]
 478 ; CHECK-NEXT:    [[ARRAY_1_I:%.*]] = load i32, i32* [[ARRAY_1_I_PTR]], align 4
 479 ; CHECK-NEXT:    [[LOOP_ACC_1:%.*]] = add i32 [[LOOP_ACC]], [[ARRAY_1_I]]
 480 ; CHECK-NEXT:    br i1 true, label [[GUARDED1]], label [[DEOPT2:%.*]], !prof !0
 481 ; CHECK:       deopt2:
 482 ; CHECK-NEXT:    call void @prevent_merging()
 483 ; CHECK-NEXT:    ret i32 -1
 484 ; CHECK:       guarded1:
 485 ; CHECK-NEXT:    [[ARRAY_3_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY_3:%.*]], i64 [[I_I64]]
 486 ; CHECK-NEXT:    [[ARRAY_3_I:%.*]] = load i32, i32* [[ARRAY_3_I_PTR]], align 4
 487 ; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC_1]], [[ARRAY_3_I]]
 488 ; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
 489 ; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i32 [[I_NEXT]], [[N]]
 490 ; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
 491 ; CHECK:       exit:
 492 ; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED1]] ]
 493 ; CHECK-NEXT:    ret i32 [[RESULT]]
 494 ;
 495 loop.preheader:                                   ; preds = %entry
 496   br label %loop
 497
 498 loop:                                             ; preds = %guarded4, %loop.preheader
 499   %loop.acc = phi i32 [ %loop.acc.next, %guarded1 ], [ 0, %loop.preheader ]
 500   %i = phi i32 [ %i.next, %guarded1 ], [ 0, %loop.preheader ]
 501   %within.bounds.1 = icmp ult i32 %i, %length
 502   br i1 %within.bounds.1, label %guarded, label %deopt, !prof !0
 503
 504 deopt:                                            ; preds = %loop
 505   call void @prevent_merging()
 506   ret i32 -1
 507
 508 guarded:                                          ; preds = %loop
 509   %i.i64 = zext i32 %i to i64
 510   %array.1.i.ptr = getelementptr inbounds i32, i32* %array.1, i64 %i.i64
 511   %array.1.i = load i32, i32* %array.1.i.ptr, align 4
 512   %loop.acc.1 = add i32 %loop.acc, %array.1.i
 513   %within.bounds.2 = icmp ult i32 %i, %length
 514   br i1 %within.bounds.2, label %guarded1, label %deopt2, !prof !0
 515
 516 deopt2:                                           ; preds = %guarded
 517   call void @prevent_merging()
 518   ret i32 -1
 519
 520 guarded1:                                         ; preds = %guarded1
 521   %array.3.i.ptr = getelementptr inbounds i32, i32* %array.3, i64 %i.i64
 522   %array.3.i = load i32, i32* %array.3.i.ptr, align 4
 523   %loop.acc.next = add i32 %loop.acc.1, %array.3.i
 524   %i.next = add nuw i32 %i, 1
 525   %continue = icmp ult i32 %i.next, %n
 526   br i1 %continue, label %loop, label %exit
 527
 528 exit:
 529   %result = phi i32 [ %loop.acc.next, %guarded1 ]
 530   ret i32 %result
 531 }
 532
 533
 534 define i32 @provably_taken(i32* %array, i32* %length.ptr) {
 535 ; CHECK-LABEL: @provably_taken(
 536 ; CHECK-NEXT:  loop.preheader:
 537 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 538 ; CHECK:       loop:
 539 ; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
 540 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
 541 ; CHECK-NEXT:    br i1 false, label [[GUARDED]], label [[DEOPT:%.*]], !prof !0
 542 ; CHECK:       deopt:
 543 ; CHECK-NEXT:    call void @prevent_merging()
 544 ; CHECK-NEXT:    ret i32 -1
 545 ; CHECK:       guarded:
 546 ; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
 547 ; CHECK-NEXT:    [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY:%.*]], i64 [[I_I64]]
 548 ; CHECK-NEXT:    [[ARRAY_I:%.*]] = load i32, i32* [[ARRAY_I_PTR]], align 4
 549 ; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
 550 ; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i32 [[I]], 1
 551 ; CHECK-NEXT:    br i1 true, label [[LOOP]], label [[EXIT:%.*]]
 552 ; CHECK:       exit:
 553 ; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
 554 ; CHECK-NEXT:    ret i32 [[RESULT]]
 555 ;
 556 loop.preheader:
 557   %length = load i32, i32* %length.ptr, !range !2
 558   br label %loop
 559
 560 loop:                                             ; preds = %guarded, %loop.preheader
 561   %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
 562   %i = phi i32 [ %i.next, %guarded ], [ 0, %loop.preheader ]
 563   %within.bounds = icmp ult i32 %i, %length
 564   br i1 %within.bounds, label %guarded, label %deopt, !prof !0
 565
 566 deopt:                                            ; preds = %loop
 567   call void @prevent_merging()
 568   ret i32 -1
 569
 570 guarded:                                          ; preds = %loop
 571   %i.i64 = zext i32 %i to i64
 572   %array.i.ptr = getelementptr inbounds i32, i32* %array, i64 %i.i64
 573   %array.i = load i32, i32* %array.i.ptr, align 4
 574   %loop.acc.next = add i32 %loop.acc, %array.i
 575   %i.next = add nuw i32 %i, 1
 576   %continue = icmp slt i32 %i.next, 200
 577   br i1 %continue, label %loop, label %exit
 578
 579 exit:                                             ; preds = %guarded
 580   %result = phi i32 [ %loop.acc.next, %guarded ]
 581   ret i32 %result
 582 }
 583
 584 ; Non-latch exits can still be predicated
 585 define i32 @unconditional_latch(i32* %a, i32 %length) {
 586 ; CHECK-LABEL: @unconditional_latch(
 587 ; CHECK-NEXT:  loop.preheader:
 588 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 589 ; CHECK:       loop:
 590 ; CHECK-NEXT:    br i1 false, label [[GUARDED:%.*]], label [[DEOPT:%.*]], !prof !0
 591 ; CHECK:       deopt:
 592 ; CHECK-NEXT:    call void @prevent_merging()
 593 ; CHECK-NEXT:    ret i32 -1
 594 ; CHECK:       guarded:
 595 ; CHECK-NEXT:    br label [[LOOP]]
 596 ;
 597 loop.preheader:
 598   br label %loop
 599
 600 loop:                                             ; preds = %guarded, %loop.preheader
 601   %i = phi i32 [ %i.next, %guarded ], [ 400, %loop.preheader ]
 602   %within.bounds = icmp ult i32 %i, %length
 603   br i1 %within.bounds, label %guarded, label %deopt, !prof !0
 604
 605 deopt:                                            ; preds = %loop
 606   call void @prevent_merging()
 607   ret i32 -1
 608
 609 guarded:                                          ; preds = %loop
 610   %i.next = add i32 %i, 1
 611   br label %loop
 612 }
 613
 614 ; Side effect in loop must run proper number of times
 615 define i32 @unconditional_latch_with_side_effect(i32* %a, i32 %length) {
 616 ; CHECK-LABEL: @unconditional_latch_with_side_effect(
 617 ; CHECK-NEXT:  loop.preheader:
 618 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 619 ; CHECK:       loop:
 620 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED:%.*]] ], [ 400, [[LOOP_PREHEADER:%.*]] ]
 621 ; CHECK-NEXT:    [[WITHIN_BOUNDS:%.*]] = icmp ult i32 [[I]], [[LENGTH:%.*]]
 622 ; CHECK-NEXT:    br i1 [[WITHIN_BOUNDS]], label [[GUARDED]], label [[DEOPT:%.*]], !prof !0
 623 ; CHECK:       deopt:
 624 ; CHECK-NEXT:    call void @prevent_merging()
 625 ; CHECK-NEXT:    ret i32 -1
 626 ; CHECK:       guarded:
 627 ; CHECK-NEXT:    store volatile i32 0, i32* [[A:%.*]]
 628 ; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
 629 ; CHECK-NEXT:    br label [[LOOP]]
 630 ;
 631 loop.preheader:
 632   br label %loop
 633
 634 loop:                                             ; preds = %guarded, %loop.preheader
 635   %i = phi i32 [ %i.next, %guarded ], [ 400, %loop.preheader ]
 636   %within.bounds = icmp ult i32 %i, %length
 637   br i1 %within.bounds, label %guarded, label %deopt, !prof !0
 638
 639 deopt:                                            ; preds = %loop
 640   call void @prevent_merging()
 641   ret i32 -1
 642
 643 guarded:                                          ; preds = %loop
 644   store volatile i32 0, i32* %a
 645   %i.next = add i32 %i, 1
 646   br label %loop
 647 }
 648
 649 ; Demonstrate that this approach works with IVs of different steps, and types
 650 ; This version uses a manually lftred exit condition to work around an issue described
 651 ; in detail on next test.
 652 define i32 @different_ivs(i32* %array, i32 %length, i32 %n) {
 653 ; CHECK-LABEL: @different_ivs(
 654 ; CHECK-NEXT:  loop.preheader:
 655 ; CHECK-NEXT:    [[N64:%.*]] = zext i32 [[N:%.*]] to i64
 656 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ugt i64 [[N64]], 1
 657 ; CHECK-NEXT:    [[UMAX:%.*]] = select i1 [[TMP0]], i64 [[N64]], i64 1
 658 ; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i64 [[UMAX]], -1
 659 ; CHECK-NEXT:    [[TMP2:%.*]] = zext i32 [[LENGTH:%.*]] to i64
 660 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp ult i64 [[TMP1]], [[TMP2]]
 661 ; CHECK-NEXT:    [[UMIN:%.*]] = select i1 [[TMP3]], i64 [[TMP1]], i64 [[TMP2]]
 662 ; CHECK-NEXT:    [[TMP4:%.*]] = zext i32 [[LENGTH]] to i64
 663 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp ne i64 [[TMP4]], [[UMIN]]
 664 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 665 ; CHECK:       loop:
 666 ; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
 667 ; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
 668 ; CHECK-NEXT:    br i1 [[TMP5]], label [[GUARDED]], label [[DEOPT:%.*]], !prof !0
 669 ; CHECK:       deopt:
 670 ; CHECK-NEXT:    call void @prevent_merging()
 671 ; CHECK-NEXT:    ret i32 -1
 672 ; CHECK:       guarded:
 673 ; CHECK-NEXT:    [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY:%.*]], i64 [[I]]
 674 ; CHECK-NEXT:    [[ARRAY_I:%.*]] = load i32, i32* [[ARRAY_I_PTR]], align 4
 675 ; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
 676 ; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i64 [[I]], 1
 677 ; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i64 [[I_NEXT]], [[N64]]
 678 ; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
 679 ; CHECK:       exit:
 680 ; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
 681 ; CHECK-NEXT:    ret i32 [[RESULT]]
 682 ;
 683 loop.preheader:
 684   %j.start = sub nuw nsw i32 %length, 1
 685   %n64 = zext i32 %n to i64
 686   br label %loop
 687
 688 loop:
 689   %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
 690   %i = phi i64 [ %i.next, %guarded ], [ 0, %loop.preheader ]
 691   %j = phi i32 [ %j.next, %guarded ], [ %j.start, %loop.preheader ]
 692   %within.bounds = icmp ne i32 %j, -1
 693   br i1 %within.bounds, label %guarded, label %deopt, !prof !0
 694
 695 deopt:
 696   call void @prevent_merging()
 697   ret i32 -1
 698
 699 guarded:
 700   %array.i.ptr = getelementptr inbounds i32, i32* %array, i64 %i
 701   %array.i = load i32, i32* %array.i.ptr, align 4
 702   %loop.acc.next = add i32 %loop.acc, %array.i
 703   %i.next = add nuw i64 %i, 1
 704   %j.next = sub nuw i32 %j, 1
 705   %continue = icmp ult i64 %i.next, %n64
 706   br i1 %continue, label %loop, label %exit
 707
 708 exit:
 709   %result = phi i32 [ %loop.acc.next, %guarded ]
 710   ret i32 %result
 711 }
 712
 713 ; TODO: We're failing to compute an exit count for the bounds check.
 714 ; From some quick analysis, it looks like we don't handle -1 step
 715 ; in howManyLessThans.  Should be a simple fix.
 716 define i32 @different_ivs2(i32* %array, i32 %length, i32 %n) {
 717 ; CHECK-LABEL: @different_ivs2(
 718 ; CHECK-NEXT:  entry:
 719 ; CHECK-NEXT:    [[POS_LENGTH:%.*]] = icmp sgt i32 [[LENGTH:%.*]], 0
 720 ; CHECK-NEXT:    br i1 [[POS_LENGTH]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 721 ; CHECK:       loop.preheader:
 722 ; CHECK-NEXT:    [[J_START:%.*]] = sub nuw nsw i32 [[LENGTH]], 1
 723 ; CHECK-NEXT:    [[N64:%.*]] = zext i32 [[N:%.*]] to i64
 724 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 725 ; CHECK:       loop:
 726 ; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
 727 ; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
 728 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ [[J_NEXT:%.*]], [[GUARDED]] ], [ [[J_START]], [[LOOP_PREHEADER]] ]
 729 ; CHECK-NEXT:    [[WITHIN_BOUNDS:%.*]] = icmp ult i32 [[J]], [[LENGTH]]
 730 ; CHECK-NEXT:    br i1 [[WITHIN_BOUNDS]], label [[GUARDED]], label [[DEOPT:%.*]], !prof !0
 731 ; CHECK:       deopt:
 732 ; CHECK-NEXT:    call void @prevent_merging()
 733 ; CHECK-NEXT:    ret i32 -1
 734 ; CHECK:       guarded:
 735 ; CHECK-NEXT:    [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY:%.*]], i64 [[I]]
 736 ; CHECK-NEXT:    [[ARRAY_I:%.*]] = load i32, i32* [[ARRAY_I_PTR]], align 4
 737 ; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
 738 ; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i64 [[I]], 1
 739 ; CHECK-NEXT:    [[J_NEXT]] = sub nuw i32 [[J]], 1
 740 ; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i64 [[I_NEXT]], [[N64]]
 741 ; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
 742 ; CHECK:       exit.loopexit:
 743 ; CHECK-NEXT:    [[LOOP_ACC_NEXT_LCSSA:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
 744 ; CHECK-NEXT:    br label [[EXIT]]
 745 ; CHECK:       exit:
 746 ; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_ACC_NEXT_LCSSA]], [[EXIT_LOOPEXIT]] ]
 747 ; CHECK-NEXT:    ret i32 [[RESULT]]
 748 ;
 749 entry:
 750   %pos_length = icmp sgt i32 %length, 0
 751   br i1 %pos_length, label %loop.preheader, label %exit
 752
 753 loop.preheader:
 754   %j.start = sub nuw nsw i32 %length, 1
 755   %n64 = zext i32 %n to i64
 756   br label %loop
 757
 758 loop:
 759   %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
 760   %i = phi i64 [ %i.next, %guarded ], [ 0, %loop.preheader ]
 761   %j = phi i32 [ %j.next, %guarded ], [ %j.start, %loop.preheader ]
 762   %within.bounds = icmp ult i32 %j, %length
 763   br i1 %within.bounds, label %guarded, label %deopt, !prof !0
 764
 765 deopt:
 766   call void @prevent_merging()
 767   ret i32 -1
 768
 769 guarded:
 770   %array.i.ptr = getelementptr inbounds i32, i32* %array, i64 %i
 771   %array.i = load i32, i32* %array.i.ptr, align 4
 772   %loop.acc.next = add i32 %loop.acc, %array.i
 773   %i.next = add nuw i64 %i, 1
 774   %j.next = sub nuw i32 %j, 1
 775   %continue = icmp ult i64 %i.next, %n64
 776   br i1 %continue, label %loop, label %exit
 777
 778 exit:
 779   %result = phi i32 [ %loop.acc.next, %guarded ], [0, %entry]
 780   ret i32 %result
 781 }
 782
 783 ; If we have a dominating exit (exit1) which can't be itself rewritten, we
 784 ; can't rewrite a later exit (exit2).  Doing so would cause the loop to exit
 785 ; from the exit2 when it should have exited from exit1.
 786 define i32 @neg_dominating_exit(i32* %array, i32 %length, i32 %length2, i32 %n) {
 787 ; CHECK-LABEL: @neg_dominating_exit(
 788 ; CHECK-NEXT:  loop.preheader:
 789 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 790 ; CHECK:       loop:
 791 ; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED2:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
 792 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED2]] ], [ 0, [[LOOP_PREHEADER]] ]
 793 ; CHECK-NEXT:    [[WITHIN_BOUNDS:%.*]] = icmp ult i32 [[I]], [[LENGTH:%.*]]
 794 ; CHECK-NEXT:    br i1 [[WITHIN_BOUNDS]], label [[GUARDED:%.*]], label [[DEOPT:%.*]], !prof !0
 795 ; CHECK:       deopt:
 796 ; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC]], [[LOOP]] ]
 797 ; CHECK-NEXT:    call void @prevent_merging()
 798 ; CHECK-NEXT:    ret i32 [[RESULT]]
 799 ; CHECK:       guarded:
 800 ; CHECK-NEXT:    [[WITHIN_BOUNDS2:%.*]] = icmp ult i32 [[I]], [[LENGTH2:%.*]]
 801 ; CHECK-NEXT:    br i1 [[WITHIN_BOUNDS2]], label [[GUARDED2]], label [[DEOPT2:%.*]], !prof !0
 802 ; CHECK:       deopt2:
 803 ; CHECK-NEXT:    call void @prevent_merging()
 804 ; CHECK-NEXT:    ret i32 -1
 805 ; CHECK:       guarded2:
 806 ; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
 807 ; CHECK-NEXT:    [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY:%.*]], i64 [[I_I64]]
 808 ; CHECK-NEXT:    [[ARRAY_I:%.*]] = load i32, i32* [[ARRAY_I_PTR]], align 4
 809 ; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
 810 ; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
 811 ; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i32 [[I_NEXT]], [[N:%.*]]
 812 ; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
 813 ; CHECK:       exit:
 814 ; CHECK-NEXT:    [[RESULT2:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED2]] ]
 815 ; CHECK-NEXT:    ret i32 [[RESULT2]]
 816 ;
 817 loop.preheader:                                   ; preds = %entry
 818   br label %loop
 819
 820 loop:                                             ; preds = %guarded, %loop.preheader
 821   %loop.acc = phi i32 [ %loop.acc.next, %guarded2 ], [ 0, %loop.preheader ]
 822   %i = phi i32 [ %i.next, %guarded2 ], [ 0, %loop.preheader ]
 823   %within.bounds = icmp ult i32 %i, %length
 824   br i1 %within.bounds, label %guarded, label %deopt, !prof !0
 825
 826 deopt:                                            ; preds = %loop
 827   %result = phi i32 [ %loop.acc, %loop ]
 828   call void @prevent_merging()
 829   ret i32 %result
 830
 831 guarded:                                          ; preds = %loop
 832   %within.bounds2 = icmp ult i32 %i, %length2
 833   br i1 %within.bounds2, label %guarded2, label %deopt2, !prof !0
 834
 835 deopt2:                                            ; preds = %loop
 836   call void @prevent_merging()
 837   ret i32 -1
 838
 839 guarded2:                                          ; preds = %loop
 840   %i.i64 = zext i32 %i to i64
 841   %array.i.ptr = getelementptr inbounds i32, i32* %array, i64 %i.i64
 842   %array.i = load i32, i32* %array.i.ptr, align 4
 843   %loop.acc.next = add i32 %loop.acc, %array.i
 844   %i.next = add nuw i32 %i, 1
 845   %continue = icmp ult i32 %i.next, %n
 846   br i1 %continue, label %loop, label %exit
 847
 848 exit:                                             ; preds = %guarded, %entry
 849   %result2 = phi i32 [ %loop.acc.next, %guarded2 ]
 850   ret i32 %result2
 851 }
 852
 853
 854 declare i32 @llvm.experimental.deoptimize.i32(...)
 855
 856 !0 = !{!"branch_weights", i32 1048576, i32 1}
 857 !1 = !{i32 1, i32 -2147483648}
 858 !2 = !{i32 0, i32 50}