1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt %s -instcombine -S | FileCheck %s 3 4; If we have some pattern that leaves only some low bits set, and then performs 5; left-shift of those bits, if none of the bits that are left after the final 6; shift are modified by the mask, we can omit the mask. 7 8; There are many variants to this pattern: 9; b) (x & (~(-1 << maskNbits))) << shiftNbits 10; simplify to: 11; x << shiftNbits 12; iff (maskNbits+shiftNbits) u>= bitwidth(x) 13 14; Simple tests. We don't care about extra uses. 15 16declare void @use32(i32) 17 18define i32 @t0_basic(i32 %x, i32 %nbits) { 19; CHECK-LABEL: @t0_basic( 20; CHECK-NEXT: [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]] 21; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1 22; CHECK-NEXT: [[T2:%.*]] = and i32 [[T1]], [[X:%.*]] 23; CHECK-NEXT: [[T3:%.*]] = sub i32 32, [[NBITS]] 24; CHECK-NEXT: call void @use32(i32 [[T0]]) 25; CHECK-NEXT: call void @use32(i32 [[T1]]) 26; CHECK-NEXT: call void @use32(i32 [[T2]]) 27; CHECK-NEXT: call void @use32(i32 [[T3]]) 28; CHECK-NEXT: [[T4:%.*]] = shl i32 [[X]], [[T3]] 29; CHECK-NEXT: ret i32 [[T4]] 30; 31 %t0 = shl i32 -1, %nbits 32 %t1 = xor i32 %t0, -1 33 %t2 = and i32 %t1, %x 34 %t3 = sub i32 32, %nbits 35 call void @use32(i32 %t0) 36 call void @use32(i32 %t1) 37 call void @use32(i32 %t2) 38 call void @use32(i32 %t3) 39 %t4 = shl i32 %t2, %t3 40 ret i32 %t4 41} 42 43define i32 @t1_bigger_shift(i32 %x, i32 %nbits) { 44; CHECK-LABEL: @t1_bigger_shift( 45; CHECK-NEXT: [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]] 46; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1 47; CHECK-NEXT: [[T2:%.*]] = and i32 [[T1]], [[X:%.*]] 48; CHECK-NEXT: [[T3:%.*]] = sub i32 33, [[NBITS]] 49; CHECK-NEXT: call void @use32(i32 [[T0]]) 50; CHECK-NEXT: call void @use32(i32 [[T1]]) 51; CHECK-NEXT: call void @use32(i32 [[T2]]) 52; CHECK-NEXT: call void @use32(i32 [[T3]]) 53; CHECK-NEXT: [[T4:%.*]] = shl i32 [[X]], [[T3]] 54; CHECK-NEXT: ret i32 [[T4]] 55; 56 %t0 = shl i32 -1, %nbits 57 %t1 = xor i32 %t0, -1 58 %t2 = and i32 %t1, %x 59 %t3 = sub i32 33, %nbits ; subtracting from bitwidth+1 60 call void @use32(i32 %t0) 61 call void @use32(i32 %t1) 62 call void @use32(i32 %t2) 63 call void @use32(i32 %t3) 64 %t4 = shl i32 %t2, %t3 65 ret i32 %t4 66} 67 68define i32 @t2_bigger_mask(i32 %x, i32 %nbits) { 69; CHECK-LABEL: @t2_bigger_mask( 70; CHECK-NEXT: [[T0:%.*]] = add i32 [[NBITS:%.*]], 1 71; CHECK-NEXT: [[T1:%.*]] = shl i32 -1, [[T0]] 72; CHECK-NEXT: [[T2:%.*]] = xor i32 [[T1]], -1 73; CHECK-NEXT: [[T3:%.*]] = and i32 [[T2]], [[X:%.*]] 74; CHECK-NEXT: [[T4:%.*]] = sub i32 32, [[NBITS]] 75; CHECK-NEXT: call void @use32(i32 [[T0]]) 76; CHECK-NEXT: call void @use32(i32 [[T1]]) 77; CHECK-NEXT: call void @use32(i32 [[T2]]) 78; CHECK-NEXT: call void @use32(i32 [[T3]]) 79; CHECK-NEXT: call void @use32(i32 [[T4]]) 80; CHECK-NEXT: [[T5:%.*]] = shl i32 [[X]], [[T4]] 81; CHECK-NEXT: ret i32 [[T5]] 82; 83 %t0 = add i32 %nbits, 1 84 %t1 = shl i32 -1, %t0 ; shifting by nbits+1 85 %t2 = xor i32 %t1, -1 86 %t3 = and i32 %t2, %x 87 %t4 = sub i32 32, %nbits 88 call void @use32(i32 %t0) 89 call void @use32(i32 %t1) 90 call void @use32(i32 %t2) 91 call void @use32(i32 %t3) 92 call void @use32(i32 %t4) 93 %t5 = shl i32 %t3, %t4 94 ret i32 %t5 95} 96 97; Vectors 98 99declare void @use3xi32(<3 x i32>) 100 101define <3 x i32> @t3_vec_splat(<3 x i32> %x, <3 x i32> %nbits) { 102; CHECK-LABEL: @t3_vec_splat( 103; CHECK-NEXT: [[T1:%.*]] = shl <3 x i32> <i32 -1, i32 -1, i32 -1>, [[NBITS:%.*]] 104; CHECK-NEXT: [[T2:%.*]] = xor <3 x i32> [[T1]], <i32 -1, i32 -1, i32 -1> 105; CHECK-NEXT: [[T3:%.*]] = and <3 x i32> [[T2]], [[X:%.*]] 106; CHECK-NEXT: [[T4:%.*]] = sub <3 x i32> <i32 32, i32 32, i32 32>, [[NBITS]] 107; CHECK-NEXT: call void @use3xi32(<3 x i32> [[NBITS]]) 108; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T1]]) 109; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T2]]) 110; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T3]]) 111; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T4]]) 112; CHECK-NEXT: [[T5:%.*]] = shl <3 x i32> [[X]], [[T4]] 113; CHECK-NEXT: ret <3 x i32> [[T5]] 114; 115 %t0 = add <3 x i32> %nbits, <i32 0, i32 0, i32 0> 116 %t1 = shl <3 x i32> <i32 -1, i32 -1, i32 -1>, %t0 117 %t2 = xor <3 x i32> %t1, <i32 -1, i32 -1, i32 -1> 118 %t3 = and <3 x i32> %t2, %x 119 %t4 = sub <3 x i32> <i32 32, i32 32, i32 32>, %nbits 120 call void @use3xi32(<3 x i32> %t0) 121 call void @use3xi32(<3 x i32> %t1) 122 call void @use3xi32(<3 x i32> %t2) 123 call void @use3xi32(<3 x i32> %t3) 124 call void @use3xi32(<3 x i32> %t4) 125 %t5 = shl <3 x i32> %t3, %t4 126 ret <3 x i32> %t5 127} 128 129define <3 x i32> @t4_vec_nonsplat(<3 x i32> %x, <3 x i32> %nbits) { 130; CHECK-LABEL: @t4_vec_nonsplat( 131; CHECK-NEXT: [[T0:%.*]] = add <3 x i32> [[NBITS:%.*]], <i32 -1, i32 0, i32 1> 132; CHECK-NEXT: [[T1:%.*]] = shl <3 x i32> <i32 -1, i32 -1, i32 -1>, [[T0]] 133; CHECK-NEXT: [[T2:%.*]] = xor <3 x i32> [[T1]], <i32 -1, i32 -1, i32 -1> 134; CHECK-NEXT: [[T3:%.*]] = and <3 x i32> [[T2]], [[X:%.*]] 135; CHECK-NEXT: [[T4:%.*]] = sub <3 x i32> <i32 33, i32 32, i32 32>, [[NBITS]] 136; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T0]]) 137; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T1]]) 138; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T2]]) 139; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T3]]) 140; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T4]]) 141; CHECK-NEXT: [[T5:%.*]] = shl <3 x i32> [[X]], [[T4]] 142; CHECK-NEXT: ret <3 x i32> [[T5]] 143; 144 %t0 = add <3 x i32> %nbits, <i32 -1, i32 0, i32 1> 145 %t1 = shl <3 x i32> <i32 -1, i32 -1, i32 -1>, %t0 146 %t2 = xor <3 x i32> %t1, <i32 -1, i32 -1, i32 -1> 147 %t3 = and <3 x i32> %t2, %x 148 %t4 = sub <3 x i32> <i32 33, i32 32, i32 32>, %nbits 149 call void @use3xi32(<3 x i32> %t0) 150 call void @use3xi32(<3 x i32> %t1) 151 call void @use3xi32(<3 x i32> %t2) 152 call void @use3xi32(<3 x i32> %t3) 153 call void @use3xi32(<3 x i32> %t4) 154 %t5 = shl <3 x i32> %t3, %t4 155 ret <3 x i32> %t5 156} 157 158define <3 x i32> @t5_vec_undef(<3 x i32> %x, <3 x i32> %nbits) { 159; CHECK-LABEL: @t5_vec_undef( 160; CHECK-NEXT: [[T1:%.*]] = shl <3 x i32> <i32 -1, i32 undef, i32 -1>, [[NBITS:%.*]] 161; CHECK-NEXT: [[T2:%.*]] = xor <3 x i32> [[T1]], <i32 -1, i32 undef, i32 -1> 162; CHECK-NEXT: [[T3:%.*]] = and <3 x i32> [[T2]], [[X:%.*]] 163; CHECK-NEXT: [[T4:%.*]] = sub <3 x i32> <i32 32, i32 undef, i32 32>, [[NBITS]] 164; CHECK-NEXT: call void @use3xi32(<3 x i32> [[NBITS]]) 165; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T1]]) 166; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T2]]) 167; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T3]]) 168; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T4]]) 169; CHECK-NEXT: [[T5:%.*]] = shl <3 x i32> [[X]], [[T4]] 170; CHECK-NEXT: ret <3 x i32> [[T5]] 171; 172 %t0 = add <3 x i32> %nbits, <i32 0, i32 undef, i32 0> 173 %t1 = shl <3 x i32> <i32 -1, i32 undef, i32 -1>, %t0 174 %t2 = xor <3 x i32> %t1, <i32 -1, i32 undef, i32 -1> 175 %t3 = and <3 x i32> %t2, %x 176 %t4 = sub <3 x i32> <i32 32, i32 undef, i32 32>, %nbits 177 call void @use3xi32(<3 x i32> %t0) 178 call void @use3xi32(<3 x i32> %t1) 179 call void @use3xi32(<3 x i32> %t2) 180 call void @use3xi32(<3 x i32> %t3) 181 call void @use3xi32(<3 x i32> %t4) 182 %t5 = shl <3 x i32> %t3, %t4 183 ret <3 x i32> %t5 184} 185 186; Commutativity 187 188declare i32 @gen32() 189 190define i32 @t6_commutativity0(i32 %nbits) { 191; CHECK-LABEL: @t6_commutativity0( 192; CHECK-NEXT: [[X:%.*]] = call i32 @gen32() 193; CHECK-NEXT: [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]] 194; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1 195; CHECK-NEXT: [[T2:%.*]] = and i32 [[X]], [[T1]] 196; CHECK-NEXT: [[T3:%.*]] = sub i32 32, [[NBITS]] 197; CHECK-NEXT: call void @use32(i32 [[T0]]) 198; CHECK-NEXT: call void @use32(i32 [[T1]]) 199; CHECK-NEXT: call void @use32(i32 [[T2]]) 200; CHECK-NEXT: call void @use32(i32 [[T3]]) 201; CHECK-NEXT: [[T4:%.*]] = shl i32 [[X]], [[T3]] 202; CHECK-NEXT: ret i32 [[T4]] 203; 204 %x = call i32 @gen32() 205 %t0 = shl i32 -1, %nbits 206 %t1 = xor i32 %t0, -1 207 %t2 = and i32 %x, %t1 ; swapped 208 %t3 = sub i32 32, %nbits 209 call void @use32(i32 %t0) 210 call void @use32(i32 %t1) 211 call void @use32(i32 %t2) 212 call void @use32(i32 %t3) 213 %t4 = shl i32 %t2, %t3 214 ret i32 %t4 215} 216 217define i32 @t7_commutativity1(i32 %nbits0, i32 %nbits1) { 218; CHECK-LABEL: @t7_commutativity1( 219; CHECK-NEXT: [[T0:%.*]] = shl i32 -1, [[NBITS0:%.*]] 220; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1 221; CHECK-NEXT: [[T2:%.*]] = shl i32 -1, [[NBITS1:%.*]] 222; CHECK-NEXT: [[T3:%.*]] = xor i32 [[T2]], -1 223; CHECK-NEXT: [[T4:%.*]] = and i32 [[T3]], [[T1]] 224; CHECK-NEXT: [[T5:%.*]] = sub i32 32, [[NBITS0]] 225; CHECK-NEXT: call void @use32(i32 [[T0]]) 226; CHECK-NEXT: call void @use32(i32 [[T1]]) 227; CHECK-NEXT: call void @use32(i32 [[T2]]) 228; CHECK-NEXT: call void @use32(i32 [[T3]]) 229; CHECK-NEXT: call void @use32(i32 [[T4]]) 230; CHECK-NEXT: call void @use32(i32 [[T5]]) 231; CHECK-NEXT: [[T6:%.*]] = shl i32 [[T4]], [[T5]] 232; CHECK-NEXT: ret i32 [[T6]] 233; 234 %t0 = shl i32 -1, %nbits0 235 %t1 = xor i32 %t0, -1 236 %t2 = shl i32 -1, %nbits1 237 %t3 = xor i32 %t2, -1 238 %t4 = and i32 %t3, %t1 ; both hands of 'and' could be mask.. 239 %t5 = sub i32 32, %nbits0 240 call void @use32(i32 %t0) 241 call void @use32(i32 %t1) 242 call void @use32(i32 %t2) 243 call void @use32(i32 %t3) 244 call void @use32(i32 %t4) 245 call void @use32(i32 %t5) 246 %t6 = shl i32 %t4, %t5 247 ret i32 %t6 248} 249define i32 @t8_commutativity2(i32 %nbits0, i32 %nbits1) { 250; CHECK-LABEL: @t8_commutativity2( 251; CHECK-NEXT: [[T0:%.*]] = shl i32 -1, [[NBITS0:%.*]] 252; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1 253; CHECK-NEXT: [[T2:%.*]] = shl i32 -1, [[NBITS1:%.*]] 254; CHECK-NEXT: [[T3:%.*]] = xor i32 [[T2]], -1 255; CHECK-NEXT: [[T4:%.*]] = and i32 [[T3]], [[T1]] 256; CHECK-NEXT: [[T5:%.*]] = sub i32 32, [[NBITS1]] 257; CHECK-NEXT: call void @use32(i32 [[T0]]) 258; CHECK-NEXT: call void @use32(i32 [[T1]]) 259; CHECK-NEXT: call void @use32(i32 [[T2]]) 260; CHECK-NEXT: call void @use32(i32 [[T3]]) 261; CHECK-NEXT: call void @use32(i32 [[T4]]) 262; CHECK-NEXT: call void @use32(i32 [[T5]]) 263; CHECK-NEXT: [[T6:%.*]] = shl i32 [[T1]], [[T5]] 264; CHECK-NEXT: ret i32 [[T6]] 265; 266 %t0 = shl i32 -1, %nbits0 267 %t1 = xor i32 %t0, -1 268 %t2 = shl i32 -1, %nbits1 269 %t3 = xor i32 %t2, -1 270 %t4 = and i32 %t3, %t1 ; both hands of 'and' could be mask.. 271 %t5 = sub i32 32, %nbits1 272 call void @use32(i32 %t0) 273 call void @use32(i32 %t1) 274 call void @use32(i32 %t2) 275 call void @use32(i32 %t3) 276 call void @use32(i32 %t4) 277 call void @use32(i32 %t5) 278 %t6 = shl i32 %t4, %t5 279 ret i32 %t6 280} 281 282; Fast-math flags. We must not preserve them! 283 284define i32 @t9_nuw(i32 %x, i32 %nbits) { 285; CHECK-LABEL: @t9_nuw( 286; CHECK-NEXT: [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]] 287; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1 288; CHECK-NEXT: [[T2:%.*]] = and i32 [[T1]], [[X:%.*]] 289; CHECK-NEXT: [[T3:%.*]] = sub i32 32, [[NBITS]] 290; CHECK-NEXT: call void @use32(i32 [[T0]]) 291; CHECK-NEXT: call void @use32(i32 [[T1]]) 292; CHECK-NEXT: call void @use32(i32 [[T2]]) 293; CHECK-NEXT: call void @use32(i32 [[T3]]) 294; CHECK-NEXT: [[T4:%.*]] = shl i32 [[X]], [[T3]] 295; CHECK-NEXT: ret i32 [[T4]] 296; 297 %t0 = shl i32 -1, %nbits 298 %t1 = xor i32 %t0, -1 299 %t2 = and i32 %t1, %x 300 %t3 = sub i32 32, %nbits 301 call void @use32(i32 %t0) 302 call void @use32(i32 %t1) 303 call void @use32(i32 %t2) 304 call void @use32(i32 %t3) 305 %t4 = shl nuw i32 %t2, %t3 306 ret i32 %t4 307} 308 309define i32 @t10_nsw(i32 %x, i32 %nbits) { 310; CHECK-LABEL: @t10_nsw( 311; CHECK-NEXT: [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]] 312; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1 313; CHECK-NEXT: [[T2:%.*]] = and i32 [[T1]], [[X:%.*]] 314; CHECK-NEXT: [[T3:%.*]] = sub i32 32, [[NBITS]] 315; CHECK-NEXT: call void @use32(i32 [[T0]]) 316; CHECK-NEXT: call void @use32(i32 [[T1]]) 317; CHECK-NEXT: call void @use32(i32 [[T2]]) 318; CHECK-NEXT: call void @use32(i32 [[T3]]) 319; CHECK-NEXT: [[T4:%.*]] = shl i32 [[X]], [[T3]] 320; CHECK-NEXT: ret i32 [[T4]] 321; 322 %t0 = shl i32 -1, %nbits 323 %t1 = xor i32 %t0, -1 324 %t2 = and i32 %t1, %x 325 %t3 = sub i32 32, %nbits 326 call void @use32(i32 %t0) 327 call void @use32(i32 %t1) 328 call void @use32(i32 %t2) 329 call void @use32(i32 %t3) 330 %t4 = shl nsw i32 %t2, %t3 331 ret i32 %t4 332} 333 334define i32 @t11_nuw_nsw(i32 %x, i32 %nbits) { 335; CHECK-LABEL: @t11_nuw_nsw( 336; CHECK-NEXT: [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]] 337; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1 338; CHECK-NEXT: [[T2:%.*]] = and i32 [[T1]], [[X:%.*]] 339; CHECK-NEXT: [[T3:%.*]] = sub i32 32, [[NBITS]] 340; CHECK-NEXT: call void @use32(i32 [[T0]]) 341; CHECK-NEXT: call void @use32(i32 [[T1]]) 342; CHECK-NEXT: call void @use32(i32 [[T2]]) 343; CHECK-NEXT: call void @use32(i32 [[T3]]) 344; CHECK-NEXT: [[T4:%.*]] = shl i32 [[X]], [[T3]] 345; CHECK-NEXT: ret i32 [[T4]] 346; 347 %t0 = shl i32 -1, %nbits 348 %t1 = xor i32 %t0, -1 349 %t2 = and i32 %t1, %x 350 %t3 = sub i32 32, %nbits 351 call void @use32(i32 %t0) 352 call void @use32(i32 %t1) 353 call void @use32(i32 %t2) 354 call void @use32(i32 %t3) 355 %t4 = shl nuw nsw i32 %t2, %t3 356 ret i32 %t4 357} 358 359; Negative tests 360 361define i32 @n12_not_minus_one(i32 %x, i32 %nbits) { 362; CHECK-LABEL: @n12_not_minus_one( 363; CHECK-NEXT: [[T0:%.*]] = shl i32 -2, [[NBITS:%.*]] 364; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1 365; CHECK-NEXT: [[T2:%.*]] = and i32 [[T1]], [[X:%.*]] 366; CHECK-NEXT: [[T3:%.*]] = sub i32 32, [[NBITS]] 367; CHECK-NEXT: call void @use32(i32 [[T0]]) 368; CHECK-NEXT: call void @use32(i32 [[T1]]) 369; CHECK-NEXT: call void @use32(i32 [[T2]]) 370; CHECK-NEXT: call void @use32(i32 [[T3]]) 371; CHECK-NEXT: [[T4:%.*]] = shl i32 [[T2]], [[T3]] 372; CHECK-NEXT: ret i32 [[T4]] 373; 374 %t0 = shl i32 -2, %nbits ; shifting not '-1' 375 %t1 = xor i32 %t0, -1 376 %t2 = and i32 %t1, %x 377 %t3 = sub i32 32, %nbits 378 call void @use32(i32 %t0) 379 call void @use32(i32 %t1) 380 call void @use32(i32 %t2) 381 call void @use32(i32 %t3) 382 %t4 = shl i32 %t2, %t3 383 ret i32 %t4 384} 385