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