1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt < %s -passes=correlated-propagation -S | FileCheck %s 3 4define void @test_nop(i32 %n) { 5; CHECK-LABEL: @test_nop( 6; CHECK-NEXT: [[DIV:%.*]] = udiv i32 [[N:%.*]], 100 7; CHECK-NEXT: ret void 8; 9 %div = udiv i32 %n, 100 10 ret void 11} 12 13define void @test1(i32 %n) { 14; CHECK-LABEL: @test1( 15; CHECK-NEXT: entry: 16; CHECK-NEXT: [[CMP:%.*]] = icmp ule i32 [[N:%.*]], 65535 17; CHECK-NEXT: br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]] 18; CHECK: bb: 19; CHECK-NEXT: [[DIV_LHS_TRUNC:%.*]] = trunc i32 [[N]] to i16 20; CHECK-NEXT: [[DIV1:%.*]] = urem i16 [[DIV_LHS_TRUNC]], 100 21; CHECK-NEXT: [[DIV_ZEXT:%.*]] = zext i16 [[DIV1]] to i32 22; CHECK-NEXT: br label [[EXIT]] 23; CHECK: exit: 24; CHECK-NEXT: ret void 25; 26entry: %cmp = icmp ule i32 %n, 65535 27 br i1 %cmp, label %bb, label %exit 28 29bb: 30 %div = urem i32 %n, 100 31 br label %exit 32 33exit: 34 ret void 35} 36 37define void @test2(i32 %n) { 38; CHECK-LABEL: @test2( 39; CHECK-NEXT: entry: 40; CHECK-NEXT: [[CMP:%.*]] = icmp ule i32 [[N:%.*]], 65536 41; CHECK-NEXT: br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]] 42; CHECK: bb: 43; CHECK-NEXT: [[DIV:%.*]] = urem i32 [[N]], 100 44; CHECK-NEXT: br label [[EXIT]] 45; CHECK: exit: 46; CHECK-NEXT: ret void 47; 48entry: 49 %cmp = icmp ule i32 %n, 65536 50 br i1 %cmp, label %bb, label %exit 51 52bb: 53 %div = urem i32 %n, 100 54 br label %exit 55 56exit: 57 ret void 58} 59 60define void @test3(i32 %m, i32 %n) { 61; CHECK-LABEL: @test3( 62; CHECK-NEXT: entry: 63; CHECK-NEXT: [[CMP1:%.*]] = icmp ult i32 [[M:%.*]], 65535 64; CHECK-NEXT: [[CMP2:%.*]] = icmp ult i32 [[N:%.*]], 65535 65; CHECK-NEXT: [[CMP:%.*]] = and i1 [[CMP1]], [[CMP2]] 66; CHECK-NEXT: br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]] 67; CHECK: bb: 68; CHECK-NEXT: [[DIV_LHS_TRUNC:%.*]] = trunc i32 [[M]] to i16 69; CHECK-NEXT: [[DIV_RHS_TRUNC:%.*]] = trunc i32 [[N]] to i16 70; CHECK-NEXT: [[DIV1:%.*]] = urem i16 [[DIV_LHS_TRUNC]], [[DIV_RHS_TRUNC]] 71; CHECK-NEXT: [[DIV_ZEXT:%.*]] = zext i16 [[DIV1]] to i32 72; CHECK-NEXT: br label [[EXIT]] 73; CHECK: exit: 74; CHECK-NEXT: ret void 75; 76entry: 77 %cmp1 = icmp ult i32 %m, 65535 78 %cmp2 = icmp ult i32 %n, 65535 79 %cmp = and i1 %cmp1, %cmp2 80 br i1 %cmp, label %bb, label %exit 81 82bb: 83 %div = urem i32 %m, %n 84 br label %exit 85 86exit: 87 ret void 88} 89 90define void @test4(i32 %m, i32 %n) { 91; CHECK-LABEL: @test4( 92; CHECK-NEXT: entry: 93; CHECK-NEXT: [[CMP1:%.*]] = icmp ult i32 [[M:%.*]], 65535 94; CHECK-NEXT: [[CMP2:%.*]] = icmp ule i32 [[N:%.*]], 65536 95; CHECK-NEXT: [[CMP:%.*]] = and i1 [[CMP1]], [[CMP2]] 96; CHECK-NEXT: br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]] 97; CHECK: bb: 98; CHECK-NEXT: [[DIV:%.*]] = urem i32 [[M]], [[N]] 99; CHECK-NEXT: br label [[EXIT]] 100; CHECK: exit: 101; CHECK-NEXT: ret void 102; 103entry: 104 %cmp1 = icmp ult i32 %m, 65535 105 %cmp2 = icmp ule i32 %n, 65536 106 %cmp = and i1 %cmp1, %cmp2 107 br i1 %cmp, label %bb, label %exit 108 109bb: 110 %div = urem i32 %m, %n 111 br label %exit 112 113exit: 114 ret void 115} 116 117define void @test5(i32 %n) { 118; CHECK-LABEL: @test5( 119; CHECK-NEXT: [[TRUNC:%.*]] = and i32 [[N:%.*]], 63 120; CHECK-NEXT: [[TRUNC_FROZEN:%.*]] = freeze i32 [[TRUNC]] 121; CHECK-NEXT: [[DIV_UREM:%.*]] = sub nuw i32 [[TRUNC_FROZEN]], 42 122; CHECK-NEXT: [[DIV_CMP:%.*]] = icmp ult i32 [[TRUNC_FROZEN]], 42 123; CHECK-NEXT: [[DIV:%.*]] = select i1 [[DIV_CMP]], i32 [[TRUNC_FROZEN]], i32 [[DIV_UREM]] 124; CHECK-NEXT: ret void 125; 126 %trunc = and i32 %n, 63 127 %div = urem i32 %trunc, 42 128 ret void 129} 130 131define void @test6(i32 %n) { 132; CHECK-LABEL: @test6( 133; CHECK-NEXT: entry: 134; CHECK-NEXT: [[CMP:%.*]] = icmp ule i32 [[N:%.*]], 255 135; CHECK-NEXT: br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]] 136; CHECK: bb: 137; CHECK-NEXT: [[DIV1_LHS_TRUNC:%.*]] = trunc i32 [[N]] to i8 138; CHECK-NEXT: [[DIV12:%.*]] = urem i8 [[DIV1_LHS_TRUNC]], 100 139; CHECK-NEXT: [[DIV1_ZEXT:%.*]] = zext i8 [[DIV12]] to i32 140; CHECK-NEXT: br label [[EXIT]] 141; CHECK: exit: 142; CHECK-NEXT: ret void 143; 144entry: 145 %cmp = icmp ule i32 %n, 255 146 br i1 %cmp, label %bb, label %exit 147 148bb: 149 %div = srem i32 %n, 100 150 br label %exit 151 152exit: 153 ret void 154} 155 156declare void @llvm.assume(i1) 157 158define i16 @test7(i16 %x, i16 %y) { 159; CHECK-LABEL: @test7( 160; CHECK-NEXT: [[ABOVE_RANGE:%.*]] = icmp uge i16 [[Y:%.*]], 13 161; CHECK-NEXT: call void @llvm.assume(i1 [[ABOVE_RANGE]]) 162; CHECK-NEXT: [[BELOW_RANGE:%.*]] = icmp ult i16 [[X:%.*]], 13 163; CHECK-NEXT: call void @llvm.assume(i1 [[BELOW_RANGE]]) 164; CHECK-NEXT: ret i16 [[X]] 165; 166 %above_range = icmp uge i16 %y, 13 167 call void @llvm.assume(i1 %above_range) 168 169 %below_range = icmp ult i16 %x, 13 170 call void @llvm.assume(i1 %below_range) 171 172 %r = urem i16 %x, %y 173 ret i16 %r 174} 175 176define void @non_power_of_2(i24 %n) { 177; CHECK-LABEL: @non_power_of_2( 178; CHECK-NEXT: [[DIV:%.*]] = urem i24 [[N:%.*]], 42 179; CHECK-NEXT: ret void 180; 181 %div = urem i24 %n, 42 182 ret void 183} 184 185; (x urem 5) uge 2 implies x uge 2 on the true branch. 186; We don't know anything about the lower bound on the false branch. 187define void @urem_implied_cond_uge(i8 %x, i8 %m) { 188; CHECK-LABEL: @urem_implied_cond_uge( 189; CHECK-NEXT: [[U:%.*]] = urem i8 [[X:%.*]], [[M:%.*]] 190; CHECK-NEXT: [[C1:%.*]] = icmp uge i8 [[U]], 2 191; CHECK-NEXT: br i1 [[C1]], label [[IF:%.*]], label [[ELSE:%.*]] 192; CHECK: if: 193; CHECK-NEXT: call void @use(i1 false) 194; CHECK-NEXT: [[C3:%.*]] = icmp ule i8 [[X]], 2 195; CHECK-NEXT: call void @use(i1 [[C3]]) 196; CHECK-NEXT: call void @use(i1 true) 197; CHECK-NEXT: [[C5:%.*]] = icmp ugt i8 [[X]], 2 198; CHECK-NEXT: call void @use(i1 [[C5]]) 199; CHECK-NEXT: ret void 200; CHECK: else: 201; CHECK-NEXT: [[C2_2:%.*]] = icmp ult i8 [[X]], 2 202; CHECK-NEXT: call void @use(i1 [[C2_2]]) 203; CHECK-NEXT: [[C3_2:%.*]] = icmp ule i8 [[X]], 2 204; CHECK-NEXT: call void @use(i1 [[C3_2]]) 205; CHECK-NEXT: [[C4_2:%.*]] = icmp uge i8 [[X]], 2 206; CHECK-NEXT: call void @use(i1 [[C4_2]]) 207; CHECK-NEXT: [[C5_2:%.*]] = icmp ugt i8 [[X]], 2 208; CHECK-NEXT: call void @use(i1 [[C5_2]]) 209; CHECK-NEXT: ret void 210; 211 %u = urem i8 %x, %m 212 %c1 = icmp uge i8 %u, 2 213 br i1 %c1, label %if, label %else 214 215if: 216 %c2 = icmp ult i8 %x, 2 217 call void @use(i1 %c2) 218 %c3 = icmp ule i8 %x, 2 219 call void @use(i1 %c3) 220 %c4 = icmp uge i8 %x, 2 221 call void @use(i1 %c4) 222 %c5 = icmp ugt i8 %x, 2 223 call void @use(i1 %c5) 224 ret void 225 226else: 227 %c2.2 = icmp ult i8 %x, 2 228 call void @use(i1 %c2.2) 229 %c3.2 = icmp ule i8 %x, 2 230 call void @use(i1 %c3.2) 231 %c4.2 = icmp uge i8 %x, 2 232 call void @use(i1 %c4.2) 233 %c5.2 = icmp ugt i8 %x, 2 234 call void @use(i1 %c5.2) 235 ret void 236} 237 238; (x urem 5) uge 5 is always false. It ends up being folded first, but if it 239; weren't, we should handle that gracefully. 240define void @urem_implied_cond_uge_out_of_range(i8 %x) { 241; CHECK-LABEL: @urem_implied_cond_uge_out_of_range( 242; CHECK-NEXT: [[U:%.*]] = urem i8 [[X:%.*]], 5 243; CHECK-NEXT: br i1 false, label [[IF:%.*]], label [[ELSE:%.*]] 244; CHECK: if: 245; CHECK-NEXT: [[C2:%.*]] = icmp ult i8 [[X]], 5 246; CHECK-NEXT: call void @use(i1 [[C2]]) 247; CHECK-NEXT: [[C3:%.*]] = icmp ule i8 [[X]], 5 248; CHECK-NEXT: call void @use(i1 [[C3]]) 249; CHECK-NEXT: [[C4:%.*]] = icmp uge i8 [[X]], 5 250; CHECK-NEXT: call void @use(i1 [[C4]]) 251; CHECK-NEXT: [[C5:%.*]] = icmp ugt i8 [[X]], 5 252; CHECK-NEXT: call void @use(i1 [[C5]]) 253; CHECK-NEXT: ret void 254; CHECK: else: 255; CHECK-NEXT: [[C2_2:%.*]] = icmp ult i8 [[X]], 5 256; CHECK-NEXT: call void @use(i1 [[C2_2]]) 257; CHECK-NEXT: [[C3_2:%.*]] = icmp ule i8 [[X]], 5 258; CHECK-NEXT: call void @use(i1 [[C3_2]]) 259; CHECK-NEXT: [[C4_2:%.*]] = icmp uge i8 [[X]], 5 260; CHECK-NEXT: call void @use(i1 [[C4_2]]) 261; CHECK-NEXT: [[C5_2:%.*]] = icmp ugt i8 [[X]], 5 262; CHECK-NEXT: call void @use(i1 [[C5_2]]) 263; CHECK-NEXT: ret void 264; 265 %u = urem i8 %x, 5 266 %c1 = icmp uge i8 %u, 5 267 br i1 %c1, label %if, label %else 268 269if: 270 %c2 = icmp ult i8 %x, 5 271 call void @use(i1 %c2) 272 %c3 = icmp ule i8 %x, 5 273 call void @use(i1 %c3) 274 %c4 = icmp uge i8 %x, 5 275 call void @use(i1 %c4) 276 %c5 = icmp ugt i8 %x, 5 277 call void @use(i1 %c5) 278 ret void 279 280else: 281 %c2.2 = icmp ult i8 %x, 5 282 call void @use(i1 %c2.2) 283 %c3.2 = icmp ule i8 %x, 5 284 call void @use(i1 %c3.2) 285 %c4.2 = icmp uge i8 %x, 5 286 call void @use(i1 %c4.2) 287 %c5.2 = icmp ugt i8 %x, 5 288 call void @use(i1 %c5.2) 289 ret void 290} 291 292; (x urem 5) != 0 is the same as (x urem 5) >= 1 and implies x >= 1. 293define void @urem_implied_cond_ne_zero(i8 %x, i8 %m) { 294; CHECK-LABEL: @urem_implied_cond_ne_zero( 295; CHECK-NEXT: [[U:%.*]] = urem i8 [[X:%.*]], [[M:%.*]] 296; CHECK-NEXT: [[C1:%.*]] = icmp ne i8 [[U]], 0 297; CHECK-NEXT: br i1 [[C1]], label [[IF:%.*]], label [[ELSE:%.*]] 298; CHECK: if: 299; CHECK-NEXT: call void @use(i1 false) 300; CHECK-NEXT: [[C3:%.*]] = icmp ule i8 [[X]], 1 301; CHECK-NEXT: call void @use(i1 [[C3]]) 302; CHECK-NEXT: call void @use(i1 true) 303; CHECK-NEXT: [[C5:%.*]] = icmp ugt i8 [[X]], 1 304; CHECK-NEXT: call void @use(i1 [[C5]]) 305; CHECK-NEXT: ret void 306; CHECK: else: 307; CHECK-NEXT: [[C2_2:%.*]] = icmp ult i8 [[X]], 1 308; CHECK-NEXT: call void @use(i1 [[C2_2]]) 309; CHECK-NEXT: [[C3_2:%.*]] = icmp ule i8 [[X]], 1 310; CHECK-NEXT: call void @use(i1 [[C3_2]]) 311; CHECK-NEXT: [[C4_2:%.*]] = icmp uge i8 [[X]], 1 312; CHECK-NEXT: call void @use(i1 [[C4_2]]) 313; CHECK-NEXT: [[C5_2:%.*]] = icmp ugt i8 [[X]], 1 314; CHECK-NEXT: call void @use(i1 [[C5_2]]) 315; CHECK-NEXT: ret void 316; 317 %u = urem i8 %x, %m 318 %c1 = icmp ne i8 %u, 0 319 br i1 %c1, label %if, label %else 320 321if: 322 %c2 = icmp ult i8 %x, 1 323 call void @use(i1 %c2) 324 %c3 = icmp ule i8 %x, 1 325 call void @use(i1 %c3) 326 %c4 = icmp uge i8 %x, 1 327 call void @use(i1 %c4) 328 %c5 = icmp ugt i8 %x, 1 329 call void @use(i1 %c5) 330 ret void 331 332else: 333 %c2.2 = icmp ult i8 %x, 1 334 call void @use(i1 %c2.2) 335 %c3.2 = icmp ule i8 %x, 1 336 call void @use(i1 %c3.2) 337 %c4.2 = icmp uge i8 %x, 1 338 call void @use(i1 %c4.2) 339 %c5.2 = icmp ugt i8 %x, 1 340 call void @use(i1 %c5.2) 341 ret void 342} 343 344; (x urem 5) != 1 doesn't imply anything on the true branch. However, on the 345; false branch (x urem 5) == 1 implies x >= 1. 346define void @urem_implied_cond_ne_non_zero(i8 %x, i8 %m) { 347; CHECK-LABEL: @urem_implied_cond_ne_non_zero( 348; CHECK-NEXT: [[U:%.*]] = urem i8 [[X:%.*]], [[M:%.*]] 349; CHECK-NEXT: [[C1:%.*]] = icmp ne i8 [[U]], 1 350; CHECK-NEXT: br i1 [[C1]], label [[IF:%.*]], label [[ELSE:%.*]] 351; CHECK: if: 352; CHECK-NEXT: [[C2:%.*]] = icmp ult i8 [[X]], 1 353; CHECK-NEXT: call void @use(i1 [[C2]]) 354; CHECK-NEXT: [[C3:%.*]] = icmp ule i8 [[X]], 1 355; CHECK-NEXT: call void @use(i1 [[C3]]) 356; CHECK-NEXT: [[C4:%.*]] = icmp uge i8 [[X]], 1 357; CHECK-NEXT: call void @use(i1 [[C4]]) 358; CHECK-NEXT: [[C5:%.*]] = icmp ugt i8 [[X]], 1 359; CHECK-NEXT: call void @use(i1 [[C5]]) 360; CHECK-NEXT: ret void 361; CHECK: else: 362; CHECK-NEXT: call void @use(i1 false) 363; CHECK-NEXT: [[C3_2:%.*]] = icmp ule i8 [[X]], 1 364; CHECK-NEXT: call void @use(i1 [[C3_2]]) 365; CHECK-NEXT: call void @use(i1 true) 366; CHECK-NEXT: [[C5_2:%.*]] = icmp ugt i8 [[X]], 1 367; CHECK-NEXT: call void @use(i1 [[C5_2]]) 368; CHECK-NEXT: ret void 369; 370 %u = urem i8 %x, %m 371 %c1 = icmp ne i8 %u, 1 372 br i1 %c1, label %if, label %else 373 374if: 375 %c2 = icmp ult i8 %x, 1 376 call void @use(i1 %c2) 377 %c3 = icmp ule i8 %x, 1 378 call void @use(i1 %c3) 379 %c4 = icmp uge i8 %x, 1 380 call void @use(i1 %c4) 381 %c5 = icmp ugt i8 %x, 1 382 call void @use(i1 %c5) 383 ret void 384 385else: 386 %c2.2 = icmp ult i8 %x, 1 387 call void @use(i1 %c2.2) 388 %c3.2 = icmp ule i8 %x, 1 389 call void @use(i1 %c3.2) 390 %c4.2 = icmp uge i8 %x, 1 391 call void @use(i1 %c4.2) 392 %c5.2 = icmp ugt i8 %x, 1 393 call void @use(i1 %c5.2) 394 ret void 395} 396 397define i8 @urem_undef_range_op1(i8 %x) { 398; CHECK-LABEL: @urem_undef_range_op1( 399; CHECK-NEXT: entry: 400; CHECK-NEXT: switch i8 [[X:%.*]], label [[JOIN:%.*]] [ 401; CHECK-NEXT: i8 1, label [[CASE1:%.*]] 402; CHECK-NEXT: i8 2, label [[CASE2:%.*]] 403; CHECK-NEXT: ] 404; CHECK: case1: 405; CHECK-NEXT: br label [[JOIN]] 406; CHECK: case2: 407; CHECK-NEXT: br label [[JOIN]] 408; CHECK: join: 409; CHECK-NEXT: [[PHI:%.*]] = phi i8 [ 1, [[CASE1]] ], [ 2, [[CASE2]] ], [ undef, [[ENTRY:%.*]] ] 410; CHECK-NEXT: [[RES:%.*]] = urem i8 [[PHI]], 3 411; CHECK-NEXT: ret i8 [[RES]] 412; 413entry: 414 switch i8 %x, label %join [ 415 i8 1, label %case1 416 i8 2, label %case2 417 ] 418 419case1: 420 br label %join 421 422case2: 423 br label %join 424 425join: 426 %phi = phi i8 [ 1, %case1 ], [ 2, %case2 ], [ undef, %entry ] 427 %res = urem i8 %phi, 3 428 ret i8 %res 429} 430 431define i8 @urem_undef_range_op2(i8 %x) { 432; CHECK-LABEL: @urem_undef_range_op2( 433; CHECK-NEXT: entry: 434; CHECK-NEXT: switch i8 [[X:%.*]], label [[JOIN:%.*]] [ 435; CHECK-NEXT: i8 1, label [[CASE1:%.*]] 436; CHECK-NEXT: i8 2, label [[CASE2:%.*]] 437; CHECK-NEXT: ] 438; CHECK: case1: 439; CHECK-NEXT: br label [[JOIN]] 440; CHECK: case2: 441; CHECK-NEXT: br label [[JOIN]] 442; CHECK: join: 443; CHECK-NEXT: [[PHI:%.*]] = phi i8 [ 5, [[CASE1]] ], [ 6, [[CASE2]] ], [ undef, [[ENTRY:%.*]] ] 444; CHECK-NEXT: [[RES:%.*]] = sub nuw i8 7, [[PHI]] 445; CHECK-NEXT: ret i8 [[RES]] 446; 447entry: 448 switch i8 %x, label %join [ 449 i8 1, label %case1 450 i8 2, label %case2 451 ] 452 453case1: 454 br label %join 455 456case2: 457 br label %join 458 459join: 460 %phi = phi i8 [ 5, %case1 ], [ 6, %case2 ], [ undef, %entry ] 461 %res = urem i8 7, %phi 462 ret i8 %res 463} 464 465define i1 @urem_i1() { 466; CHECK-LABEL: @urem_i1( 467; CHECK-NEXT: [[REM:%.*]] = urem i1 false, false 468; CHECK-NEXT: ret i1 [[REM]] 469; 470 %rem = urem i1 false, false 471 ret i1 %rem 472} 473 474declare void @use(i1) 475