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