1; RUN: opt -S -guard-widening < %s | FileCheck %s 2; RUN: opt -S -passes=guard-widening < %s | FileCheck %s 3 4declare void @llvm.experimental.guard(i1,...) 5 6; Basic test case: we wide the first check to check both the 7; conditions. 8define void @f_0(i1 %cond_0, i1 %cond_1) { 9; CHECK-LABEL: @f_0( 10entry: 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. 21define void @f_1(i1 %cond_0, i1 %cond_1) { 22; CHECK-LABEL: @f_1( 23entry: 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 31left: 32 br label %merge 33 34right: 35 br label %merge 36 37merge: 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. 47define void @f_2(i32 %a, i32 %b) { 48; CHECK-LABEL: @f_2( 49entry: 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 60left: 61 br label %merge 62 63right: 64 br label %merge 65 66merge: 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. 74define void @f_3(i32 %a, i32 %b) { 75; CHECK-LABEL: @f_3( 76entry: 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 85left: 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 95right: 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. 102define void @f_4(i32 %a, i32 %b) { 103; CHECK-LABEL: @f_4( 104entry: 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 115loop: 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 120leave: 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. 126define void @f_5(i32 %a) { 127; CHECK-LABEL: @f_5( 128entry: 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 137left: 138 %cond_1 = icmp ugt i32 %a, 10 139 call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ] 140 ret void 141 142right: 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. 149define 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 154entry: 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. 165define void @f_7(i32 %a, i1* %cond_buf) { 166; CHECK-LABEL: @f_7( 167entry: 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 182left: 183 %cond_3 = icmp ult i32 %a, 7 184 call void(i1, ...) @llvm.experimental.guard(i1 %cond_3) [ "deopt"() ] 185 br label %left 186 187right: 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. 194define void @f_8(i32 %a, i1 %cond_1, i1 %cond_2) { 195; CHECK-LABEL: @f_8( 196entry: 197 br label %loop 198 199loop: 200 call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ] 201 br i1 undef, label %loop, label %leave 202 203leave: 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 213loop2: 214 %cond_3 = icmp ult i32 %a, 7 215 call void(i1, ...) @llvm.experimental.guard(i1 %cond_3) [ "deopt"() ] 216 br label %loop2 217 218leave2: 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. 224define void @f_9(i32 %a, i1 %cond_0, i1 %cond_1) { 225; CHECK-LABEL: @f_9( 226entry: 227 br label %first_loop 228 229first_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 237second_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. 248define void @f_10(i32 %a, i1 %cond_0, i1 %cond_1) { 249; CHECK-LABEL: @f_10( 250entry: 251 br label %loop 252 253loop: 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 261no_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. 271define void @f_11(i32 %a, i1 %cond_0, i1 %cond_1) { 272; CHECK-LABEL: @f_11( 273entry: 274 br label %inner 275 276inner: 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 285outer: 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. 292define 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 302entry: 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 339define void @f_13(i32 %a) { 340; CHECK-LABEL: @f_13( 341entry: 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 350left: 351 %cond_1 = icmp slt i32 %a, 10 352 call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ] 353 ret void 354 355right: 356 ret void 357} 358 359define void @f_14(i32 %a) { 360; CHECK-LABEL: @f_14( 361entry: 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 370left: 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 379right: 380 ret void 381} 382