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; f) ((x << maskNbits) a>> 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 [[X:%.*]], [[NBITS:%.*]] 21; CHECK-NEXT: [[T1:%.*]] = ashr i32 [[T0]], [[NBITS]] 22; CHECK-NEXT: call void @use32(i32 [[T0]]) 23; CHECK-NEXT: call void @use32(i32 [[T1]]) 24; CHECK-NEXT: [[T2:%.*]] = shl i32 [[X]], [[NBITS]] 25; CHECK-NEXT: ret i32 [[T2]] 26; 27 %t0 = shl i32 %x, %nbits 28 %t1 = ashr i32 %t0, %nbits 29 call void @use32(i32 %t0) 30 call void @use32(i32 %t1) 31 %t2 = shl i32 %t1, %nbits 32 ret i32 %t2 33} 34 35define i32 @t1_bigger_shift(i32 %x, i32 %nbits) { 36; CHECK-LABEL: @t1_bigger_shift( 37; CHECK-NEXT: [[T0:%.*]] = shl i32 [[X:%.*]], [[NBITS:%.*]] 38; CHECK-NEXT: [[T1:%.*]] = ashr i32 [[T0]], [[NBITS]] 39; CHECK-NEXT: [[T2:%.*]] = add i32 [[NBITS]], 1 40; CHECK-NEXT: call void @use32(i32 [[T0]]) 41; CHECK-NEXT: call void @use32(i32 [[T1]]) 42; CHECK-NEXT: call void @use32(i32 [[T2]]) 43; CHECK-NEXT: [[T3:%.*]] = shl i32 [[X]], [[T2]] 44; CHECK-NEXT: ret i32 [[T3]] 45; 46 %t0 = shl i32 %x, %nbits 47 %t1 = ashr i32 %t0, %nbits 48 %t2 = add i32 %nbits, 1 49 call void @use32(i32 %t0) 50 call void @use32(i32 %t1) 51 call void @use32(i32 %t2) 52 %t3 = shl i32 %t1, %t2 53 ret i32 %t3 54} 55 56; Vectors 57 58declare void @use3xi32(<3 x i32>) 59 60define <3 x i32> @t2_vec_splat(<3 x i32> %x, <3 x i32> %nbits) { 61; CHECK-LABEL: @t2_vec_splat( 62; CHECK-NEXT: [[T0:%.*]] = shl <3 x i32> [[X:%.*]], [[NBITS:%.*]] 63; CHECK-NEXT: [[T1:%.*]] = ashr <3 x i32> [[T0]], [[NBITS]] 64; CHECK-NEXT: [[T2:%.*]] = add <3 x i32> [[NBITS]], <i32 1, i32 1, i32 1> 65; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T0]]) 66; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T1]]) 67; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T2]]) 68; CHECK-NEXT: [[T3:%.*]] = shl <3 x i32> [[X]], [[T2]] 69; CHECK-NEXT: ret <3 x i32> [[T3]] 70; 71 %t0 = shl <3 x i32> %x, %nbits 72 %t1 = ashr <3 x i32> %t0, %nbits 73 %t2 = add <3 x i32> %nbits, <i32 1, i32 1, i32 1> 74 call void @use3xi32(<3 x i32> %t0) 75 call void @use3xi32(<3 x i32> %t1) 76 call void @use3xi32(<3 x i32> %t2) 77 %t3 = shl <3 x i32> %t1, %t2 78 ret <3 x i32> %t3 79} 80 81define <3 x i32> @t3_vec_nonsplat(<3 x i32> %x, <3 x i32> %nbits) { 82; CHECK-LABEL: @t3_vec_nonsplat( 83; CHECK-NEXT: [[T0:%.*]] = shl <3 x i32> [[X:%.*]], [[NBITS:%.*]] 84; CHECK-NEXT: [[T1:%.*]] = ashr <3 x i32> [[T0]], [[NBITS]] 85; CHECK-NEXT: [[T2:%.*]] = add <3 x i32> [[NBITS]], <i32 1, i32 0, i32 2> 86; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T0]]) 87; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T1]]) 88; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T2]]) 89; CHECK-NEXT: [[T3:%.*]] = shl <3 x i32> [[X]], [[T2]] 90; CHECK-NEXT: ret <3 x i32> [[T3]] 91; 92 %t0 = shl <3 x i32> %x, %nbits 93 %t1 = ashr <3 x i32> %t0, %nbits 94 %t2 = add <3 x i32> %nbits, <i32 1, i32 0, i32 2> 95 call void @use3xi32(<3 x i32> %t0) 96 call void @use3xi32(<3 x i32> %t1) 97 call void @use3xi32(<3 x i32> %t2) 98 %t3 = shl <3 x i32> %t1, %t2 99 ret <3 x i32> %t3 100} 101 102define <3 x i32> @t4_vec_undef(<3 x i32> %x, <3 x i32> %nbits) { 103; CHECK-LABEL: @t4_vec_undef( 104; CHECK-NEXT: [[T0:%.*]] = shl <3 x i32> [[X:%.*]], [[NBITS:%.*]] 105; CHECK-NEXT: [[T1:%.*]] = ashr <3 x i32> [[T0]], [[NBITS]] 106; CHECK-NEXT: [[T2:%.*]] = add <3 x i32> [[NBITS]], <i32 1, i32 undef, i32 1> 107; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T0]]) 108; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T1]]) 109; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T2]]) 110; CHECK-NEXT: [[T3:%.*]] = shl <3 x i32> [[X]], [[T2]] 111; CHECK-NEXT: ret <3 x i32> [[T3]] 112; 113 %t0 = shl <3 x i32> %x, %nbits 114 %t1 = ashr <3 x i32> %t0, %nbits 115 %t2 = add <3 x i32> %nbits, <i32 1, i32 undef, i32 1> 116 call void @use3xi32(<3 x i32> %t0) 117 call void @use3xi32(<3 x i32> %t1) 118 call void @use3xi32(<3 x i32> %t2) 119 %t3 = shl <3 x i32> %t1, %t2 120 ret <3 x i32> %t3 121} 122 123; Fast-math flags. We must not preserve them! 124 125define i32 @t5_nuw(i32 %x, i32 %nbits) { 126; CHECK-LABEL: @t5_nuw( 127; CHECK-NEXT: [[T0:%.*]] = shl i32 [[X:%.*]], [[NBITS:%.*]] 128; CHECK-NEXT: [[T1:%.*]] = ashr i32 [[T0]], [[NBITS]] 129; CHECK-NEXT: call void @use32(i32 [[T0]]) 130; CHECK-NEXT: call void @use32(i32 [[T1]]) 131; CHECK-NEXT: [[T2:%.*]] = shl i32 [[X]], [[NBITS]] 132; CHECK-NEXT: ret i32 [[T2]] 133; 134 %t0 = shl i32 %x, %nbits 135 %t1 = ashr i32 %t0, %nbits 136 call void @use32(i32 %t0) 137 call void @use32(i32 %t1) 138 %t2 = shl nuw i32 %t1, %nbits 139 ret i32 %t2 140} 141 142define i32 @t6_nsw(i32 %x, i32 %nbits) { 143; CHECK-LABEL: @t6_nsw( 144; CHECK-NEXT: [[T0:%.*]] = shl i32 [[X:%.*]], [[NBITS:%.*]] 145; CHECK-NEXT: [[T1:%.*]] = ashr i32 [[T0]], [[NBITS]] 146; CHECK-NEXT: call void @use32(i32 [[T0]]) 147; CHECK-NEXT: call void @use32(i32 [[T1]]) 148; CHECK-NEXT: [[T2:%.*]] = shl i32 [[X]], [[NBITS]] 149; CHECK-NEXT: ret i32 [[T2]] 150; 151 %t0 = shl i32 %x, %nbits 152 %t1 = ashr i32 %t0, %nbits 153 call void @use32(i32 %t0) 154 call void @use32(i32 %t1) 155 %t2 = shl nsw i32 %t1, %nbits 156 ret i32 %t2 157} 158 159define i32 @t7_nuw_nsw(i32 %x, i32 %nbits) { 160; CHECK-LABEL: @t7_nuw_nsw( 161; CHECK-NEXT: [[T0:%.*]] = shl i32 [[X:%.*]], [[NBITS:%.*]] 162; CHECK-NEXT: [[T1:%.*]] = ashr i32 [[T0]], [[NBITS]] 163; CHECK-NEXT: call void @use32(i32 [[T0]]) 164; CHECK-NEXT: call void @use32(i32 [[T1]]) 165; CHECK-NEXT: [[T2:%.*]] = shl i32 [[X]], [[NBITS]] 166; CHECK-NEXT: ret i32 [[T2]] 167; 168 %t0 = shl i32 %x, %nbits 169 %t1 = ashr i32 %t0, %nbits 170 call void @use32(i32 %t0) 171 call void @use32(i32 %t1) 172 %t2 = shl nuw nsw i32 %t1, %nbits 173 ret i32 %t2 174} 175 176; Special test 177 178declare void @llvm.assume(i1 %cond) 179 180; We can't simplify (%shiftnbits-%masknbits) but we have an assumption. 181define i32 @t8_assume_uge(i32 %x, i32 %masknbits, i32 %shiftnbits) { 182; CHECK-LABEL: @t8_assume_uge( 183; CHECK-NEXT: [[CMP:%.*]] = icmp uge i32 [[SHIFTNBITS:%.*]], [[MASKNBITS:%.*]] 184; CHECK-NEXT: call void @llvm.assume(i1 [[CMP]]) 185; CHECK-NEXT: [[T0:%.*]] = shl i32 [[X:%.*]], [[MASKNBITS]] 186; CHECK-NEXT: [[T1:%.*]] = ashr i32 [[T0]], [[MASKNBITS]] 187; CHECK-NEXT: call void @use32(i32 [[T0]]) 188; CHECK-NEXT: call void @use32(i32 [[T1]]) 189; CHECK-NEXT: [[T2:%.*]] = shl i32 [[T1]], [[SHIFTNBITS]] 190; CHECK-NEXT: ret i32 [[T2]] 191; 192 %cmp = icmp uge i32 %shiftnbits, %masknbits 193 call void @llvm.assume(i1 %cmp) 194 %t0 = shl i32 %x, %masknbits 195 %t1 = ashr i32 %t0, %masknbits 196 call void @use32(i32 %t0) 197 call void @use32(i32 %t1) 198 %t2 = shl i32 %t1, %shiftnbits 199 ret i32 %t2 200} 201 202; Negative tests 203 204define i32 @n9_different_shamts0(i32 %x, i32 %nbits0, i32 %nbits1) { 205; CHECK-LABEL: @n9_different_shamts0( 206; CHECK-NEXT: [[T0:%.*]] = shl i32 [[X:%.*]], [[NBITS0:%.*]] 207; CHECK-NEXT: [[T1:%.*]] = ashr i32 [[T0]], [[NBITS1:%.*]] 208; CHECK-NEXT: call void @use32(i32 [[T0]]) 209; CHECK-NEXT: call void @use32(i32 [[T1]]) 210; CHECK-NEXT: [[T2:%.*]] = shl i32 [[T1]], [[NBITS0]] 211; CHECK-NEXT: ret i32 [[T2]] 212; 213 %t0 = shl i32 %x, %nbits0 ; different shift amts 214 %t1 = ashr i32 %t0, %nbits1 ; different shift amts 215 call void @use32(i32 %t0) 216 call void @use32(i32 %t1) 217 %t2 = shl i32 %t1, %nbits0 218 ret i32 %t2 219} 220 221define i32 @n10_different_shamts1(i32 %x, i32 %nbits0, i32 %nbits1) { 222; CHECK-LABEL: @n10_different_shamts1( 223; CHECK-NEXT: [[T0:%.*]] = shl i32 [[X:%.*]], [[NBITS0:%.*]] 224; CHECK-NEXT: [[T1:%.*]] = ashr i32 [[T0]], [[NBITS1:%.*]] 225; CHECK-NEXT: call void @use32(i32 [[T0]]) 226; CHECK-NEXT: call void @use32(i32 [[T1]]) 227; CHECK-NEXT: [[T2:%.*]] = shl i32 [[T1]], [[NBITS1]] 228; CHECK-NEXT: ret i32 [[T2]] 229; 230 %t0 = shl i32 %x, %nbits0 ; different shift amts 231 %t1 = ashr i32 %t0, %nbits1 ; different shift amts 232 call void @use32(i32 %t0) 233 call void @use32(i32 %t1) 234 %t2 = shl i32 %t1, %nbits1 235 ret i32 %t2 236} 237 238define i32 @n11_shamt_is_smaller(i32 %x, i32 %nbits) { 239; CHECK-LABEL: @n11_shamt_is_smaller( 240; CHECK-NEXT: [[T0:%.*]] = shl i32 [[X:%.*]], [[NBITS:%.*]] 241; CHECK-NEXT: [[T1:%.*]] = ashr i32 [[T0]], [[NBITS]] 242; CHECK-NEXT: [[T2:%.*]] = add i32 [[NBITS]], -1 243; CHECK-NEXT: call void @use32(i32 [[T0]]) 244; CHECK-NEXT: call void @use32(i32 [[T2]]) 245; CHECK-NEXT: [[T3:%.*]] = shl i32 [[T1]], [[T2]] 246; CHECK-NEXT: ret i32 [[T3]] 247; 248 %t0 = shl i32 %x, %nbits 249 %t1 = ashr i32 %t0, %nbits 250 %t2 = add i32 %nbits, -1 251 call void @use32(i32 %t0) 252 call void @use32(i32 %t2) 253 %t3 = shl i32 %t1, %t2 ; shift is smaller than mask 254 ret i32 %t3 255} 256