test/Transforms/GuardWidening/basic.ll

   1 ; RUN: opt -S -guard-widening < %s        | FileCheck %s
   2 ; RUN: opt -S -passes=guard-widening < %s | FileCheck %s
   3
   4 declare void @llvm.experimental.guard(i1,...)
   5
   6 ; Basic test case: we wide the first check to check both the
   7 ; conditions.
   8 define void @f_0(i1 %cond_0, i1 %cond_1) {
   9 ; CHECK-LABEL: @f_0(
  10 entry:
  11 ; CHECK:  %wide.chk = and i1 %cond_0, %cond_1
  12 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
  13 ; CHECK:  ret void
  14
  15   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
  16   call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
  17   ret void
  18 }
  19
  20 ; Same as @f_0, but with using a more general notion of postdominance.
  21 define void @f_1(i1 %cond_0, i1 %cond_1) {
  22 ; CHECK-LABEL: @f_1(
  23 entry:
  24 ; CHECK:  %wide.chk = and i1 %cond_0, %cond_1
  25 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
  26 ; CHECK:  br i1 undef, label %left, label %right
  27
  28   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
  29   br i1 undef, label %left, label %right
  30
  31 left:
  32   br label %merge
  33
  34 right:
  35   br label %merge
  36
  37 merge:
  38 ; CHECK: merge:
  39 ; CHECK-NOT: call void (i1, ...) @llvm.experimental.guard(
  40 ; CHECK: ret void
  41   call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
  42   ret void
  43 }
  44
  45 ; Like @f_1, but we have some code we need to hoist before we can
  46 ; widen a dominanting check.
  47 define void @f_2(i32 %a, i32 %b) {
  48 ; CHECK-LABEL: @f_2(
  49 entry:
  50 ; CHECK:  %cond_0 = icmp ult i32 %a, 10
  51 ; CHECK:  %cond_1 = icmp ult i32 %b, 10
  52 ; CHECK:  %wide.chk = and i1 %cond_0, %cond_1
  53 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
  54 ; CHECK:  br i1 undef, label %left, label %right
  55
  56   %cond_0 = icmp ult i32 %a, 10
  57   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
  58   br i1 undef, label %left, label %right
  59
  60 left:
  61   br label %merge
  62
  63 right:
  64   br label %merge
  65
  66 merge:
  67   %cond_1 = icmp ult i32 %b, 10
  68   call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
  69   ret void
  70 }
  71
  72 ; Negative test: don't hoist stuff out of control flow
  73 ; indiscriminately, since that can make us do more work than needed.
  74 define void @f_3(i32 %a, i32 %b) {
  75 ; CHECK-LABEL: @f_3(
  76 entry:
  77 ; CHECK:  %cond_0 = icmp ult i32 %a, 10
  78 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
  79 ; CHECK:  br i1 undef, label %left, label %right
  80
  81   %cond_0 = icmp ult i32 %a, 10
  82   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
  83   br i1 undef, label %left, label %right
  84
  85 left:
  86 ; CHECK: left:
  87 ; CHECK:   %cond_1 = icmp ult i32 %b, 10
  88 ; CHECK:   call void (i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
  89 ; CHECK:   ret void
  90
  91   %cond_1 = icmp ult i32 %b, 10
  92   call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
  93   ret void
  94
  95 right:
  96   ret void
  97 }
  98
  99 ; But hoisting out of control flow is fine if it makes a loop computed
 100 ; condition loop invariant.  This behavior may require some tuning in
 101 ; the future.
 102 define void @f_4(i32 %a, i32 %b) {
 103 ; CHECK-LABEL: @f_4(
 104 entry:
 105 ; CHECK:  %cond_0 = icmp ult i32 %a, 10
 106 ; CHECK:  %cond_1 = icmp ult i32 %b, 10
 107 ; CHECK:  %wide.chk = and i1 %cond_0, %cond_1
 108 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
 109 ; CHECK:  br i1 undef, label %loop, label %leave
 110
 111   %cond_0 = icmp ult i32 %a, 10
 112   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 113   br i1 undef, label %loop, label %leave
 114
 115 loop:
 116   %cond_1 = icmp ult i32 %b, 10
 117   call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
 118   br i1 undef, label %loop, label %leave
 119
 120 leave:
 121   ret void
 122 }
 123
 124 ; Hoisting out of control flow is also fine if we can widen the
 125 ; dominating check without doing any extra work.
 126 define void @f_5(i32 %a) {
 127 ; CHECK-LABEL: @f_5(
 128 entry:
 129 ; CHECK:  %wide.chk = icmp uge i32 %a, 11
 130 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
 131 ; CHECK:  br i1 undef, label %left, label %right
 132
 133   %cond_0 = icmp ugt i32 %a, 7
 134   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 135   br i1 undef, label %left, label %right
 136
 137 left:
 138   %cond_1 = icmp ugt i32 %a, 10
 139   call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
 140   ret void
 141
 142 right:
 143   ret void
 144 }
 145
 146 ; Negative test: the load from %a can be safely speculated to before
 147 ; the first guard, but there is no guarantee that it will produce the
 148 ; same value.
 149 define void @f_6(i1* dereferenceable(32) %a, i1* %b, i1 %unknown) {
 150 ; CHECK-LABEL: @f_6(
 151 ; CHECK: call void (i1, ...) @llvm.experimental.guard(
 152 ; CHECK: call void (i1, ...) @llvm.experimental.guard(
 153 ; CHECK: ret void
 154 entry:
 155   %cond_0 = load i1, i1* %a
 156   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 157   store i1 %unknown, i1* %b
 158   %cond_1 = load i1, i1* %a
 159   call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
 160   ret void
 161 }
 162
 163 ; All else equal, we try to widen the earliest guard we can.  This
 164 ; heuristic can use some tuning.
 165 define void @f_7(i32 %a, i1* %cond_buf) {
 166 ; CHECK-LABEL: @f_7(
 167 entry:
 168 ; CHECK:  %cond_1 = load volatile i1, i1* %cond_buf
 169 ; CHECK:  %cond_3 = icmp ult i32 %a, 7
 170 ; CHECK:  %wide.chk = and i1 %cond_1, %cond_3
 171 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
 172 ; CHECK:  %cond_2 = load volatile i1, i1* %cond_buf
 173 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %cond_2) [ "deopt"() ]
 174 ; CHECK:  br i1 undef, label %left, label %right
 175
 176   %cond_1 = load volatile i1, i1* %cond_buf
 177   call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
 178   %cond_2 = load volatile i1, i1* %cond_buf
 179   call void(i1, ...) @llvm.experimental.guard(i1 %cond_2) [ "deopt"() ]
 180   br i1 undef, label %left, label %right
 181
 182 left:
 183   %cond_3 = icmp ult i32 %a, 7
 184   call void(i1, ...) @llvm.experimental.guard(i1 %cond_3) [ "deopt"() ]
 185   br label %left
 186
 187 right:
 188   ret void
 189 }
 190
 191 ; In this case the earliest dominating guard is in a loop, and we
 192 ; don't want to put extra work in there.  This heuristic can use some
 193 ; tuning.
 194 define void @f_8(i32 %a, i1 %cond_1, i1 %cond_2) {
 195 ; CHECK-LABEL: @f_8(
 196 entry:
 197   br label %loop
 198
 199 loop:
 200   call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
 201   br i1 undef, label %loop, label %leave
 202
 203 leave:
 204 ; CHECK: leave:
 205 ; CHECK:  %cond_3 = icmp ult i32 %a, 7
 206 ; CHECK:  %wide.chk = and i1 %cond_2, %cond_3
 207 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
 208 ; CHECK:  br i1 undef, label %loop2, label %leave2
 209
 210   call void(i1, ...) @llvm.experimental.guard(i1 %cond_2) [ "deopt"() ]
 211   br i1 undef, label %loop2, label %leave2
 212
 213 loop2:
 214   %cond_3 = icmp ult i32 %a, 7
 215   call void(i1, ...) @llvm.experimental.guard(i1 %cond_3) [ "deopt"() ]
 216   br label %loop2
 217
 218 leave2:
 219   ret void
 220 }
 221
 222 ; In cases like these where there isn't any "obviously profitable"
 223 ; widening sites, we refuse to do anything.
 224 define void @f_9(i32 %a, i1 %cond_0, i1 %cond_1) {
 225 ; CHECK-LABEL: @f_9(
 226 entry:
 227   br label %first_loop
 228
 229 first_loop:
 230 ; CHECK: first_loop:
 231 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 232 ; CHECK:  br i1 undef, label %first_loop, label %second_loop
 233
 234   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 235   br i1 undef, label %first_loop, label %second_loop
 236
 237 second_loop:
 238 ; CHECK: second_loop:
 239 ; CHECK:   call void (i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
 240 ; CHECK:   br label %second_loop
 241
 242   call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
 243   br label %second_loop
 244 }
 245
 246 ; Same situation as in @f_9: no "obviously profitable" widening sites,
 247 ; so we refuse to do anything.
 248 define void @f_10(i32 %a, i1 %cond_0, i1 %cond_1) {
 249 ; CHECK-LABEL: @f_10(
 250 entry:
 251   br label %loop
 252
 253 loop:
 254 ; CHECK: loop:
 255 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 256 ; CHECK:  br i1 undef, label %loop, label %no_loop
 257
 258   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 259   br i1 undef, label %loop, label %no_loop
 260
 261 no_loop:
 262 ; CHECK: no_loop:
 263 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
 264 ; CHECK:  ret void
 265   call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
 266   ret void
 267 }
 268
 269 ; With guards in loops, we're okay hoisting out the guard into the
 270 ; containing loop.
 271 define void @f_11(i32 %a, i1 %cond_0, i1 %cond_1) {
 272 ; CHECK-LABEL: @f_11(
 273 entry:
 274   br label %inner
 275
 276 inner:
 277 ; CHECK: inner:
 278 ; CHECK:  %wide.chk = and i1 %cond_0, %cond_1
 279 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
 280 ; CHECK:  br i1 undef, label %inner, label %outer
 281
 282   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 283   br i1 undef, label %inner, label %outer
 284
 285 outer:
 286   call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
 287   br label %inner
 288 }
 289
 290 ; Checks that we are adequately guarded against exponential-time
 291 ; behavior when hoisting code.
 292 define void @f_12(i32 %a0) {
 293 ; CHECK-LABEL: @f_12
 294
 295 ; Eliding the earlier 29 multiplications for brevity
 296 ; CHECK:  %a30 = mul i32 %a29, %a29
 297 ; CHECK-NEXT:  %cond = trunc i32 %a30 to i1
 298 ; CHECK-NEXT:  %wide.chk = and i1 true, %cond
 299 ; CHECK-NEXT:  call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
 300 ; CHECK-NEXT:  ret void
 301
 302 entry:
 303   call void(i1, ...) @llvm.experimental.guard(i1 true) [ "deopt"() ]
 304   %a1 = mul i32 %a0, %a0
 305   %a2 = mul i32 %a1, %a1
 306   %a3 = mul i32 %a2, %a2
 307   %a4 = mul i32 %a3, %a3
 308   %a5 = mul i32 %a4, %a4
 309   %a6 = mul i32 %a5, %a5
 310   %a7 = mul i32 %a6, %a6
 311   %a8 = mul i32 %a7, %a7
 312   %a9 = mul i32 %a8, %a8
 313   %a10 = mul i32 %a9, %a9
 314   %a11 = mul i32 %a10, %a10
 315   %a12 = mul i32 %a11, %a11
 316   %a13 = mul i32 %a12, %a12
 317   %a14 = mul i32 %a13, %a13
 318   %a15 = mul i32 %a14, %a14
 319   %a16 = mul i32 %a15, %a15
 320   %a17 = mul i32 %a16, %a16
 321   %a18 = mul i32 %a17, %a17
 322   %a19 = mul i32 %a18, %a18
 323   %a20 = mul i32 %a19, %a19
 324   %a21 = mul i32 %a20, %a20
 325   %a22 = mul i32 %a21, %a21
 326   %a23 = mul i32 %a22, %a22
 327   %a24 = mul i32 %a23, %a23
 328   %a25 = mul i32 %a24, %a24
 329   %a26 = mul i32 %a25, %a25
 330   %a27 = mul i32 %a26, %a26
 331   %a28 = mul i32 %a27, %a27
 332   %a29 = mul i32 %a28, %a28
 333   %a30 = mul i32 %a29, %a29
 334   %cond = trunc i32 %a30 to i1
 335   call void(i1, ...) @llvm.experimental.guard(i1 %cond) [ "deopt"() ]
 336   ret void
 337 }
 338
 339 define void @f_13(i32 %a) {
 340 ; CHECK-LABEL: @f_13(
 341 entry:
 342 ; CHECK:  %wide.chk = icmp ult i32 %a, 10
 343 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
 344 ; CHECK:  br i1 undef, label %left, label %right
 345
 346   %cond_0 = icmp ult i32 %a, 14
 347   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 348   br i1 undef, label %left, label %right
 349
 350 left:
 351   %cond_1 = icmp slt i32 %a, 10
 352   call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
 353   ret void
 354
 355 right:
 356   ret void
 357 }
 358
 359 define void @f_14(i32 %a) {
 360 ; CHECK-LABEL: @f_14(
 361 entry:
 362 ; CHECK:  %cond_0 = icmp ult i32 %a, 14
 363 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 364 ; CHECK:  br i1 undef, label %left, label %right
 365
 366   %cond_0 = icmp ult i32 %a, 14
 367   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 368   br i1 undef, label %left, label %right
 369
 370 left:
 371 ; CHECK: left:
 372 ; CHECK:  %cond_1 = icmp sgt i32 %a, 10
 373 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
 374
 375   %cond_1 = icmp sgt i32 %a, 10
 376   call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
 377   ret void
 378
 379 right:
 380   ret void
 381 }
 382
 383 ; Make sure we do not widen guard by trivial true conditions into something.
 384 define void @f_15(i1 %cond_0, i1 %cond_1) {
 385 ; CHECK-LABEL: @f_15(
 386 entry:
 387 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 388 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 true) [ "deopt"() ]
 389 ; CHECK:  ret void
 390
 391   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 392   call void(i1, ...) @llvm.experimental.guard(i1 true) [ "deopt"() ]
 393   ret void
 394 }
 395
 396 ; Make sure we do not widen guard by trivial false conditions into something.
 397 define void @f_16(i1 %cond_0, i1 %cond_1) {
 398 ; CHECK-LABEL: @f_16(
 399 entry:
 400 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 401 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"() ]
 402 ; CHECK:  ret void
 403
 404   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 405   call void(i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"() ]
 406   ret void
 407 }