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; d) (x & ((-1 << maskNbits) >> maskNbits)) << shiftNbits 10; simplify to: 11; x << shiftNbits 12; iff (shiftNbits-maskNbits) s>= 0 (i.e. shiftNbits u>= maskNbits) 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:%.*]] = lshr i32 [[T0]], [[NBITS]] 22; CHECK-NEXT: [[T2:%.*]] = and i32 [[T1]], [[X:%.*]] 23; CHECK-NEXT: call void @use32(i32 [[T0]]) 24; CHECK-NEXT: call void @use32(i32 [[T1]]) 25; CHECK-NEXT: call void @use32(i32 [[T2]]) 26; CHECK-NEXT: [[T4:%.*]] = shl i32 [[X]], [[NBITS]] 27; CHECK-NEXT: ret i32 [[T4]] 28; 29 %t0 = shl i32 -1, %nbits 30 %t1 = lshr i32 %t0, %nbits 31 %t2 = and i32 %t1, %x 32 call void @use32(i32 %t0) 33 call void @use32(i32 %t1) 34 call void @use32(i32 %t2) 35 %t4 = shl i32 %t2, %nbits 36 ret i32 %t4 37} 38 39define i32 @t1_bigger_shift(i32 %x, i32 %nbits) { 40; CHECK-LABEL: @t1_bigger_shift( 41; CHECK-NEXT: [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]] 42; CHECK-NEXT: [[T1:%.*]] = lshr i32 [[T0]], [[NBITS]] 43; CHECK-NEXT: [[T2:%.*]] = and i32 [[T1]], [[X:%.*]] 44; CHECK-NEXT: [[T3:%.*]] = add i32 [[NBITS]], 1 45; CHECK-NEXT: call void @use32(i32 [[T0]]) 46; CHECK-NEXT: call void @use32(i32 [[T1]]) 47; CHECK-NEXT: call void @use32(i32 [[T2]]) 48; CHECK-NEXT: call void @use32(i32 [[T3]]) 49; CHECK-NEXT: [[T4:%.*]] = shl i32 [[X]], [[T3]] 50; CHECK-NEXT: ret i32 [[T4]] 51; 52 %t0 = shl i32 -1, %nbits 53 %t1 = lshr i32 %t0, %nbits 54 %t2 = and i32 %t1, %x 55 %t3 = add i32 %nbits, 1 56 call void @use32(i32 %t0) 57 call void @use32(i32 %t1) 58 call void @use32(i32 %t2) 59 call void @use32(i32 %t3) 60 %t4 = shl i32 %t2, %t3 61 ret i32 %t4 62} 63 64; Vectors 65 66declare void @use3xi32(<3 x i32>) 67 68define <3 x i32> @t2_vec_splat(<3 x i32> %x, <3 x i32> %nbits) { 69; CHECK-LABEL: @t2_vec_splat( 70; CHECK-NEXT: [[T0:%.*]] = shl <3 x i32> <i32 -1, i32 -1, i32 -1>, [[NBITS:%.*]] 71; CHECK-NEXT: [[T1:%.*]] = lshr <3 x i32> [[T0]], [[NBITS]] 72; CHECK-NEXT: [[T2:%.*]] = and <3 x i32> [[T1]], [[X:%.*]] 73; CHECK-NEXT: [[T3:%.*]] = add <3 x i32> [[NBITS]], <i32 1, i32 1, i32 1> 74; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T0]]) 75; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T1]]) 76; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T2]]) 77; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T3]]) 78; CHECK-NEXT: [[T4:%.*]] = shl <3 x i32> [[X]], [[T3]] 79; CHECK-NEXT: ret <3 x i32> [[T4]] 80; 81 %t0 = shl <3 x i32> <i32 -1, i32 -1, i32 -1>, %nbits 82 %t1 = lshr <3 x i32> %t0, %nbits 83 %t2 = and <3 x i32> %t1, %x 84 %t3 = add <3 x i32> %nbits, <i32 1, i32 1, i32 1> 85 call void @use3xi32(<3 x i32> %t0) 86 call void @use3xi32(<3 x i32> %t1) 87 call void @use3xi32(<3 x i32> %t2) 88 call void @use3xi32(<3 x i32> %t3) 89 %t4 = shl <3 x i32> %t2, %t3 90 ret <3 x i32> %t4 91} 92 93define <3 x i32> @t3_vec_nonsplat(<3 x i32> %x, <3 x i32> %nbits) { 94; CHECK-LABEL: @t3_vec_nonsplat( 95; CHECK-NEXT: [[T0:%.*]] = shl <3 x i32> <i32 -1, i32 -1, i32 -1>, [[NBITS:%.*]] 96; CHECK-NEXT: [[T1:%.*]] = lshr <3 x i32> [[T0]], [[NBITS]] 97; CHECK-NEXT: [[T2:%.*]] = and <3 x i32> [[T1]], [[X:%.*]] 98; CHECK-NEXT: [[T3:%.*]] = add <3 x i32> [[NBITS]], <i32 1, i32 0, i32 2> 99; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T0]]) 100; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T1]]) 101; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T2]]) 102; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T3]]) 103; CHECK-NEXT: [[T4:%.*]] = shl <3 x i32> [[X]], [[T3]] 104; CHECK-NEXT: ret <3 x i32> [[T4]] 105; 106 %t0 = shl <3 x i32> <i32 -1, i32 -1, i32 -1>, %nbits 107 %t1 = lshr <3 x i32> %t0, %nbits 108 %t2 = and <3 x i32> %t1, %x 109 %t3 = add <3 x i32> %nbits, <i32 1, i32 0, i32 2> 110 call void @use3xi32(<3 x i32> %t0) 111 call void @use3xi32(<3 x i32> %t1) 112 call void @use3xi32(<3 x i32> %t2) 113 call void @use3xi32(<3 x i32> %t3) 114 %t4 = shl <3 x i32> %t2, %t3 115 ret <3 x i32> %t4 116} 117 118define <3 x i32> @t4_vec_undef(<3 x i32> %x, <3 x i32> %nbits) { 119; CHECK-LABEL: @t4_vec_undef( 120; CHECK-NEXT: [[T0:%.*]] = shl <3 x i32> <i32 -1, i32 undef, i32 -1>, [[NBITS:%.*]] 121; CHECK-NEXT: [[T1:%.*]] = lshr <3 x i32> [[T0]], [[NBITS]] 122; CHECK-NEXT: [[T2:%.*]] = and <3 x i32> [[T1]], [[X:%.*]] 123; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T0]]) 124; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T1]]) 125; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T2]]) 126; CHECK-NEXT: call void @use3xi32(<3 x i32> [[NBITS]]) 127; CHECK-NEXT: [[T4:%.*]] = shl <3 x i32> [[X]], [[NBITS]] 128; CHECK-NEXT: ret <3 x i32> [[T4]] 129; 130 %t0 = shl <3 x i32> <i32 -1, i32 undef, i32 -1>, %nbits 131 %t1 = lshr <3 x i32> %t0, %nbits 132 %t2 = and <3 x i32> %t1, %x 133 %t3 = add <3 x i32> %nbits, <i32 0, i32 undef, i32 0> 134 call void @use3xi32(<3 x i32> %t0) 135 call void @use3xi32(<3 x i32> %t1) 136 call void @use3xi32(<3 x i32> %t2) 137 call void @use3xi32(<3 x i32> %t3) 138 %t4 = shl <3 x i32> %t2, %t3 139 ret <3 x i32> %t4 140} 141 142; Commutativity 143 144declare i32 @gen32() 145 146define i32 @t5_commutativity0(i32 %nbits) { 147; CHECK-LABEL: @t5_commutativity0( 148; CHECK-NEXT: [[X:%.*]] = call i32 @gen32() 149; CHECK-NEXT: [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]] 150; CHECK-NEXT: [[T1:%.*]] = lshr i32 [[T0]], [[NBITS]] 151; CHECK-NEXT: [[T2:%.*]] = and i32 [[X]], [[T1]] 152; CHECK-NEXT: call void @use32(i32 [[T0]]) 153; CHECK-NEXT: call void @use32(i32 [[T1]]) 154; CHECK-NEXT: call void @use32(i32 [[T2]]) 155; CHECK-NEXT: [[T3:%.*]] = shl i32 [[X]], [[NBITS]] 156; CHECK-NEXT: ret i32 [[T3]] 157; 158 %x = call i32 @gen32() 159 %t0 = shl i32 -1, %nbits 160 %t1 = lshr i32 %t0, %nbits 161 %t2 = and i32 %x, %t1 ; swapped order 162 call void @use32(i32 %t0) 163 call void @use32(i32 %t1) 164 call void @use32(i32 %t2) 165 %t3 = shl i32 %t2, %nbits 166 ret i32 %t3 167} 168 169define i32 @t6_commutativity1(i32 %nbits0, i32 %nbits1) { 170; CHECK-LABEL: @t6_commutativity1( 171; CHECK-NEXT: [[T0:%.*]] = shl i32 -1, [[NBITS0:%.*]] 172; CHECK-NEXT: [[T1:%.*]] = lshr i32 [[T0]], [[NBITS0]] 173; CHECK-NEXT: [[T2:%.*]] = shl i32 -1, [[NBITS1:%.*]] 174; CHECK-NEXT: [[T3:%.*]] = lshr i32 [[T0]], [[NBITS1]] 175; CHECK-NEXT: [[T4:%.*]] = and i32 [[T3]], [[T1]] 176; CHECK-NEXT: call void @use32(i32 [[T0]]) 177; CHECK-NEXT: call void @use32(i32 [[T1]]) 178; CHECK-NEXT: call void @use32(i32 [[T2]]) 179; CHECK-NEXT: call void @use32(i32 [[T3]]) 180; CHECK-NEXT: call void @use32(i32 [[T4]]) 181; CHECK-NEXT: [[T5:%.*]] = shl i32 [[T3]], [[NBITS0]] 182; CHECK-NEXT: ret i32 [[T5]] 183; 184 %t0 = shl i32 -1, %nbits0 185 %t1 = lshr i32 %t0, %nbits0 186 %t2 = shl i32 -1, %nbits1 187 %t3 = lshr i32 %t0, %nbits1 188 %t4 = and i32 %t3, %t1 ; both hands of 'and' could be mask.. 189 call void @use32(i32 %t0) 190 call void @use32(i32 %t1) 191 call void @use32(i32 %t2) 192 call void @use32(i32 %t3) 193 call void @use32(i32 %t4) 194 %t5 = shl i32 %t4, %nbits0 195 ret i32 %t5 196} 197define i32 @t7_commutativity2(i32 %nbits0, i32 %nbits1) { 198; CHECK-LABEL: @t7_commutativity2( 199; CHECK-NEXT: [[T0:%.*]] = shl i32 -1, [[NBITS0:%.*]] 200; CHECK-NEXT: [[T1:%.*]] = lshr i32 [[T0]], [[NBITS0]] 201; CHECK-NEXT: [[T2:%.*]] = shl i32 -1, [[NBITS1:%.*]] 202; CHECK-NEXT: [[T3:%.*]] = lshr i32 [[T0]], [[NBITS1]] 203; CHECK-NEXT: [[T4:%.*]] = and i32 [[T3]], [[T1]] 204; CHECK-NEXT: call void @use32(i32 [[T0]]) 205; CHECK-NEXT: call void @use32(i32 [[T1]]) 206; CHECK-NEXT: call void @use32(i32 [[T2]]) 207; CHECK-NEXT: call void @use32(i32 [[T3]]) 208; CHECK-NEXT: call void @use32(i32 [[T4]]) 209; CHECK-NEXT: [[T5:%.*]] = shl i32 [[T4]], [[NBITS1]] 210; CHECK-NEXT: ret i32 [[T5]] 211; 212 %t0 = shl i32 -1, %nbits0 213 %t1 = lshr i32 %t0, %nbits0 214 %t2 = shl i32 -1, %nbits1 215 %t3 = lshr i32 %t0, %nbits1 216 %t4 = and i32 %t3, %t1 ; both hands of 'and' could be mask.. 217 call void @use32(i32 %t0) 218 call void @use32(i32 %t1) 219 call void @use32(i32 %t2) 220 call void @use32(i32 %t3) 221 call void @use32(i32 %t4) 222 %t5 = shl i32 %t4, %nbits1 223 ret i32 %t5 224} 225 226; Fast-math flags. We must not preserve them! 227 228define i32 @t8_nuw(i32 %x, i32 %nbits) { 229; CHECK-LABEL: @t8_nuw( 230; CHECK-NEXT: [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]] 231; CHECK-NEXT: [[T1:%.*]] = lshr i32 [[T0]], [[NBITS]] 232; CHECK-NEXT: [[T2:%.*]] = and i32 [[T1]], [[X:%.*]] 233; CHECK-NEXT: call void @use32(i32 [[T0]]) 234; CHECK-NEXT: call void @use32(i32 [[T1]]) 235; CHECK-NEXT: call void @use32(i32 [[T2]]) 236; CHECK-NEXT: [[T3:%.*]] = shl i32 [[X]], [[NBITS]] 237; CHECK-NEXT: ret i32 [[T3]] 238; 239 %t0 = shl i32 -1, %nbits 240 %t1 = lshr i32 %t0, %nbits 241 %t2 = and i32 %t1, %x 242 call void @use32(i32 %t0) 243 call void @use32(i32 %t1) 244 call void @use32(i32 %t2) 245 %t3 = shl nuw i32 %t2, %nbits 246 ret i32 %t3 247} 248 249define i32 @t9_nsw(i32 %x, i32 %nbits) { 250; CHECK-LABEL: @t9_nsw( 251; CHECK-NEXT: [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]] 252; CHECK-NEXT: [[T1:%.*]] = lshr i32 [[T0]], [[NBITS]] 253; CHECK-NEXT: [[T2:%.*]] = and i32 [[T1]], [[X:%.*]] 254; CHECK-NEXT: call void @use32(i32 [[T0]]) 255; CHECK-NEXT: call void @use32(i32 [[T1]]) 256; CHECK-NEXT: call void @use32(i32 [[T2]]) 257; CHECK-NEXT: [[T3:%.*]] = shl i32 [[X]], [[NBITS]] 258; CHECK-NEXT: ret i32 [[T3]] 259; 260 %t0 = shl i32 -1, %nbits 261 %t1 = lshr i32 %t0, %nbits 262 %t2 = and i32 %t1, %x 263 call void @use32(i32 %t0) 264 call void @use32(i32 %t1) 265 call void @use32(i32 %t2) 266 %t3 = shl nsw i32 %t2, %nbits 267 ret i32 %t3 268} 269 270define i32 @t10_nuw_nsw(i32 %x, i32 %nbits) { 271; CHECK-LABEL: @t10_nuw_nsw( 272; CHECK-NEXT: [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]] 273; CHECK-NEXT: [[T1:%.*]] = lshr i32 [[T0]], [[NBITS]] 274; CHECK-NEXT: [[T2:%.*]] = and i32 [[T1]], [[X:%.*]] 275; CHECK-NEXT: call void @use32(i32 [[T0]]) 276; CHECK-NEXT: call void @use32(i32 [[T1]]) 277; CHECK-NEXT: call void @use32(i32 [[T2]]) 278; CHECK-NEXT: [[T3:%.*]] = shl i32 [[X]], [[NBITS]] 279; CHECK-NEXT: ret i32 [[T3]] 280; 281 %t0 = shl i32 -1, %nbits 282 %t1 = lshr i32 %t0, %nbits 283 %t2 = and i32 %t1, %x 284 call void @use32(i32 %t0) 285 call void @use32(i32 %t1) 286 call void @use32(i32 %t2) 287 %t3 = shl nuw nsw i32 %t2, %nbits 288 ret i32 %t3 289} 290 291; Special test 292 293declare void @llvm.assume(i1 %cond) 294 295; We can't simplify (%shiftnbits-%masknbits) but we have an assumption. 296define i32 @t11_assume_uge(i32 %x, i32 %masknbits, i32 %shiftnbits) { 297; CHECK-LABEL: @t11_assume_uge( 298; CHECK-NEXT: [[CMP:%.*]] = icmp uge i32 [[SHIFTNBITS:%.*]], [[MASKNBITS:%.*]] 299; CHECK-NEXT: call void @llvm.assume(i1 [[CMP]]) 300; CHECK-NEXT: [[T0:%.*]] = shl i32 -1, [[MASKNBITS]] 301; CHECK-NEXT: [[T1:%.*]] = lshr i32 [[T0]], [[MASKNBITS]] 302; CHECK-NEXT: [[T2:%.*]] = and i32 [[T1]], [[X:%.*]] 303; CHECK-NEXT: call void @use32(i32 [[T0]]) 304; CHECK-NEXT: call void @use32(i32 [[T1]]) 305; CHECK-NEXT: call void @use32(i32 [[T2]]) 306; CHECK-NEXT: [[T4:%.*]] = shl i32 [[T2]], [[SHIFTNBITS]] 307; CHECK-NEXT: ret i32 [[T4]] 308; 309 %cmp = icmp uge i32 %shiftnbits, %masknbits 310 call void @llvm.assume(i1 %cmp) 311 %t0 = shl i32 -1, %masknbits 312 %t1 = lshr i32 %t0, %masknbits 313 %t2 = and i32 %t1, %x 314 call void @use32(i32 %t0) 315 call void @use32(i32 %t1) 316 call void @use32(i32 %t2) 317 %t4 = shl i32 %t2, %shiftnbits 318 ret i32 %t4 319} 320 321; Negative tests 322 323define i32 @n12_different_shamts0(i32 %x, i32 %nbits0, i32 %nbits1) { 324; CHECK-LABEL: @n12_different_shamts0( 325; CHECK-NEXT: [[T0:%.*]] = shl i32 [[X:%.*]], [[NBITS0:%.*]] 326; CHECK-NEXT: [[T1:%.*]] = lshr i32 [[T0]], [[NBITS1:%.*]] 327; CHECK-NEXT: [[T2:%.*]] = and i32 [[T1]], [[X]] 328; CHECK-NEXT: call void @use32(i32 [[T0]]) 329; CHECK-NEXT: call void @use32(i32 [[T1]]) 330; CHECK-NEXT: call void @use32(i32 [[T2]]) 331; CHECK-NEXT: [[T3:%.*]] = shl i32 [[T2]], [[NBITS0]] 332; CHECK-NEXT: ret i32 [[T3]] 333; 334 %t0 = shl i32 %x, %nbits0 ; different shift amts 335 %t1 = lshr i32 %t0, %nbits1 ; different shift amts 336 %t2 = and i32 %t1, %x 337 call void @use32(i32 %t0) 338 call void @use32(i32 %t1) 339 call void @use32(i32 %t2) 340 %t3 = shl i32 %t2, %nbits0 341 ret i32 %t3 342} 343 344define i32 @n13_different_shamts1(i32 %x, i32 %nbits0, i32 %nbits1) { 345; CHECK-LABEL: @n13_different_shamts1( 346; CHECK-NEXT: [[T0:%.*]] = shl i32 [[X:%.*]], [[NBITS0:%.*]] 347; CHECK-NEXT: [[T1:%.*]] = lshr i32 [[T0]], [[NBITS1:%.*]] 348; CHECK-NEXT: [[T2:%.*]] = and i32 [[T1]], [[X]] 349; CHECK-NEXT: call void @use32(i32 [[T0]]) 350; CHECK-NEXT: call void @use32(i32 [[T1]]) 351; CHECK-NEXT: call void @use32(i32 [[T2]]) 352; CHECK-NEXT: [[T3:%.*]] = shl i32 [[T2]], [[NBITS1]] 353; CHECK-NEXT: ret i32 [[T3]] 354; 355 %t0 = shl i32 %x, %nbits0 ; different shift amts 356 %t1 = lshr i32 %t0, %nbits1 ; different shift amts 357 %t2 = and i32 %t1, %x 358 call void @use32(i32 %t0) 359 call void @use32(i32 %t1) 360 call void @use32(i32 %t2) 361 %t3 = shl i32 %t2, %nbits1 362 ret i32 %t3 363} 364