llvm/test/Transforms/IndVarSimplify/loop-predication.ll

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