llvm/test/Transforms/IRCE/decrementing-loop.ll

   1 ; RUN: opt -verify-loop-info -irce -S < %s | FileCheck %s
   2 ; RUN: opt -verify-loop-info -passes='require<branch-prob>,irce' -S < %s | FileCheck %s
   3
   4 define void @decrementing_loop(i32 *%arr, i32 *%a_len_ptr, i32 %n) {
   5  entry:
   6   %len = load i32, i32* %a_len_ptr, !range !0
   7   %first.itr.check = icmp sgt i32 %n, 0
   8   %start = sub i32 %n, 1
   9   br i1 %first.itr.check, label %loop, label %exit
  10
  11  loop:
  12   %idx = phi i32 [ %start, %entry ] , [ %idx.dec, %in.bounds ]
  13   %idx.dec = sub i32 %idx, 1
  14   %abc.high = icmp slt i32 %idx, %len
  15   %abc.low = icmp sge i32 %idx, 0
  16   %abc = and i1 %abc.low, %abc.high
  17   br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1
  18
  19  in.bounds:
  20   %addr = getelementptr i32, i32* %arr, i32 %idx
  21   store i32 0, i32* %addr
  22   %next = icmp sgt i32 %idx.dec, -1
  23   br i1 %next, label %loop, label %exit
  24
  25  out.of.bounds:
  26   ret void
  27
  28  exit:
  29   ret void
  30
  31 ; CHECK: loop.preheader:
  32 ; CHECK:   [[len_hiclamp:[^ ]+]] = call i32 @llvm.smin.i32(i32 %len, i32 %n)
  33 ; CHECK:   [[not_exit_preloop_at:[^ ]+]] = call i32 @llvm.smax.i32(i32 [[len_hiclamp]], i32 0)
  34 ; CHECK:   %exit.preloop.at = add nsw i32 [[not_exit_preloop_at]], -1
  35 }
  36
  37 ; Make sure that we can eliminate the range check when the loop looks like:
  38 ; for (i = len.a - 1; i >= 0; --i)
  39 ;   b[i] = a[i];
  40 define void @test_01(i32* %a, i32* %b, i32* %a_len_ptr, i32* %b_len_ptr) {
  41
  42 ; CHECK-LABEL: test_01
  43 ; CHECK:       mainloop:
  44 ; CHECK-NEXT:    br label %loop
  45 ; CHECK:       loop:
  46 ; CHECK:         %rc = and i1 true, true
  47 ; CHECK:       loop.preloop:
  48
  49  entry:
  50   %len.a = load i32, i32* %a_len_ptr, !range !0
  51   %len.b = load i32, i32* %b_len_ptr, !range !0
  52   %first.itr.check = icmp ne i32 %len.a, 0
  53   br i1 %first.itr.check, label %loop, label %exit
  54
  55  loop:
  56   %idx = phi i32 [ %len.a, %entry ] , [ %idx.next, %in.bounds ]
  57   %idx.next = sub i32 %idx, 1
  58   %rca = icmp ult i32 %idx.next, %len.a
  59   %rcb = icmp ult i32 %idx.next, %len.b
  60   %rc = and i1 %rca, %rcb
  61   br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1
  62
  63  in.bounds:
  64   %el.a = getelementptr i32, i32* %a, i32 %idx.next
  65   %el.b = getelementptr i32, i32* %b, i32 %idx.next
  66   %v = load i32, i32* %el.a
  67   store i32 %v, i32* %el.b
  68   %loop.cond = icmp slt i32 %idx, 2
  69   br i1 %loop.cond, label %exit, label %loop
  70
  71  out.of.bounds:
  72   ret void
  73
  74  exit:
  75   ret void
  76 }
  77
  78 ; Same as test_01, but the latch condition is unsigned
  79 define void @test_02(i32* %a, i32* %b, i32* %a_len_ptr, i32* %b_len_ptr) {
  80
  81 ; CHECK-LABEL: test_02
  82 ; CHECK:       mainloop:
  83 ; CHECK-NEXT:    br label %loop
  84 ; CHECK:       loop:
  85 ; CHECK:         %rc = and i1 true, true
  86 ; CHECK:       loop.preloop:
  87
  88  entry:
  89   %len.a = load i32, i32* %a_len_ptr, !range !0
  90   %len.b = load i32, i32* %b_len_ptr, !range !0
  91   %first.itr.check = icmp ne i32 %len.a, 0
  92   br i1 %first.itr.check, label %loop, label %exit
  93
  94  loop:
  95   %idx = phi i32 [ %len.a, %entry ] , [ %idx.next, %in.bounds ]
  96   %idx.next = sub i32 %idx, 1
  97   %rca = icmp ult i32 %idx.next, %len.a
  98   %rcb = icmp ult i32 %idx.next, %len.b
  99   %rc = and i1 %rca, %rcb
 100   br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1
 101
 102  in.bounds:
 103   %el.a = getelementptr i32, i32* %a, i32 %idx.next
 104   %el.b = getelementptr i32, i32* %b, i32 %idx.next
 105   %v = load i32, i32* %el.a
 106   store i32 %v, i32* %el.b
 107   %loop.cond = icmp ult i32 %idx, 2
 108   br i1 %loop.cond, label %exit, label %loop
 109
 110  out.of.bounds:
 111   ret void
 112
 113  exit:
 114   ret void
 115 }
 116
 117 ; Check that we can figure out that IV is non-negative via implication through
 118 ; Phi node.
 119 define void @test_03(i32* %a, i32* %a_len_ptr, i1 %cond) {
 120
 121 ; CHECK-LABEL: test_03
 122 ; CHECK:       mainloop:
 123 ; CHECK-NEXT:    br label %loop
 124 ; CHECK:       loop:
 125 ; CHECK:         br i1 true, label %in.bounds, label %out.of.bounds
 126 ; CHECK:       loop.preloop:
 127
 128  entry:
 129   %len.a = load i32, i32* %a_len_ptr, !range !0
 130   %len.minus.one = sub nsw i32 %len.a, 1
 131   %len.minus.two = sub nsw i32 %len.a, 2
 132   br i1 %cond, label %if.true, label %if.false
 133
 134 if.true:
 135   br label %merge
 136
 137 if.false:
 138   br label %merge
 139
 140 merge:
 141   %starting.value = phi i32 [ %len.minus.two, %if.true ], [ %len.minus.one, %if.false ]
 142   %first.itr.check = icmp sgt i32 %len.a, 3
 143   br i1 %first.itr.check, label %loop, label %exit
 144
 145 loop:
 146   %idx = phi i32 [ %starting.value, %merge ] , [ %idx.next, %in.bounds ]
 147   %idx.next = sub i32 %idx, 1
 148   %rc = icmp ult i32 %idx.next, %len.a
 149   br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1
 150
 151 in.bounds:
 152   %el.a = getelementptr i32, i32* %a, i32 %idx.next
 153   %v = load i32, i32* %el.a
 154   %loop.cond = icmp slt i32 %idx, 2
 155   br i1 %loop.cond, label %exit, label %loop
 156
 157 out.of.bounds:
 158   ret void
 159
 160 exit:
 161   ret void
 162 }
 163
 164 ; Check that we can figure out that IV is non-negative via implication through
 165 ; two Phi nodes.
 166 define void @test_04(i32* %a, i32* %a_len_ptr, i1 %cond) {
 167
 168 ; CHECK-LABEL: test_04
 169 ; CHECK:       mainloop:
 170 ; CHECK-NEXT:    br label %loop
 171 ; CHECK:       loop:
 172 ; CHECK:         br i1 true, label %in.bounds, label %out.of.bounds
 173 ; CHECK:       loop.preloop:
 174
 175  entry:
 176   %len.a = load i32, i32* %a_len_ptr, !range !0
 177   %len.minus.one = sub nsw i32 %len.a, 1
 178   %len.plus.one = add nsw i32 %len.a, 1
 179   %len.minus.two = sub nsw i32 %len.a, 2
 180   br i1 %cond, label %if.true, label %if.false
 181
 182 if.true:
 183   br label %merge
 184
 185 if.false:
 186   br label %merge
 187
 188 merge:
 189   %starting.value = phi i32 [ %len.minus.two, %if.true ], [ %len.minus.one, %if.false ]
 190   %len.phi = phi i32 [ %len.a, %if.true ], [ %len.plus.one, %if.false ]
 191   %first.itr.check = icmp sgt i32 %len.a, 3
 192   br i1 %first.itr.check, label %loop, label %exit
 193
 194 loop:
 195   %idx = phi i32 [ %starting.value, %merge ] , [ %idx.next, %in.bounds ]
 196   %idx.next = sub i32 %idx, 1
 197   %rc = icmp ult i32 %idx.next, %len.phi
 198   br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1
 199
 200 in.bounds:
 201   %el.a = getelementptr i32, i32* %a, i32 %idx.next
 202   %v = load i32, i32* %el.a
 203   %loop.cond = icmp slt i32 %idx, 2
 204   br i1 %loop.cond, label %exit, label %loop
 205
 206 out.of.bounds:
 207   ret void
 208
 209 exit:
 210   ret void
 211 }
 212
 213 ; TODO: we need to be more careful when trying to look through phi nodes in
 214 ; cycles, because the condition to prove may reference the previous value of
 215 ; the phi. So we currently fail to optimize this case.
 216 ; Check that we can figure out that IV is non-negative via implication through
 217 ; two Phi nodes, one being AddRec.
 218 define void @test_05(i32* %a, i32* %a_len_ptr, i1 %cond) {
 219
 220 ; CHECK-LABEL: test_05
 221 ; CHECK: entry:
 222 ; CHECK:   br label %merge
 223 ; CHECK-NOT: mainloop
 224
 225  entry:
 226   %len.a = load i32, i32* %a_len_ptr, !range !0
 227   %len.minus.one = sub nsw i32 %len.a, 1
 228   %len.plus.one = add nsw i32 %len.a, 1
 229   %len.minus.two = sub nsw i32 %len.a, 2
 230   br label %merge
 231
 232 merge:
 233   %starting.value = phi i32 [ %len.minus.two, %entry ], [ %len.minus.one, %merge ]
 234   %len.phi = phi i32 [ %len.a, %entry ], [ %len.phi.next, %merge ]
 235   %len.phi.next = add nsw i32 %len.phi, 1
 236   br i1 true, label %first.iter.check, label %merge
 237
 238 first.iter.check:
 239   %first.itr.check = icmp sgt i32 %len.a, 3
 240   br i1 %first.itr.check, label %loop, label %exit
 241
 242 loop:
 243   %idx = phi i32 [ %starting.value, %first.iter.check ] , [ %idx.next, %in.bounds ]
 244   %idx.next = sub i32 %idx, 1
 245   %rc = icmp ult i32 %idx.next, %len.phi
 246   br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1
 247
 248 in.bounds:
 249   %el.a = getelementptr i32, i32* %a, i32 %idx.next
 250   %v = load i32, i32* %el.a
 251   %loop.cond = icmp slt i32 %idx, 2
 252   br i1 %loop.cond, label %exit, label %loop
 253
 254 out.of.bounds:
 255   ret void
 256
 257 exit:
 258   ret void
 259 }
 260
 261 !0 = !{i32 0, i32 2147483647}
 262 !1 = !{!"branch_weights", i32 64, i32 4}