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