1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt < %s -instcombine -S | FileCheck %s 3 4; https://bugs.llvm.org/show_bug.cgi?id=37603 5 6; Pattern: 7; (1 << NBits) - 1 8; Should be transformed into: 9; ~(-(1 << NBits)) 10; The `not` may end up being folded into `and` 11 12; ============================================================================ ; 13; Most basic positive tests 14; ============================================================================ ; 15 16; No no-wrap tags on shl 17 18define i32 @shl_add(i32 %NBits) { 19; CHECK-LABEL: @shl_add( 20; CHECK-NEXT: [[NOTMASK:%.*]] = shl nsw i32 -1, [[NBITS:%.*]] 21; CHECK-NEXT: [[RET:%.*]] = xor i32 [[NOTMASK]], -1 22; CHECK-NEXT: ret i32 [[RET]] 23; 24 %setbit = shl i32 1, %NBits 25 %ret = add i32 %setbit, -1 26 ret i32 %ret 27} 28 29define i32 @shl_add_nsw(i32 %NBits) { 30; CHECK-LABEL: @shl_add_nsw( 31; CHECK-NEXT: [[NOTMASK:%.*]] = shl nsw i32 -1, [[NBITS:%.*]] 32; CHECK-NEXT: [[RET:%.*]] = xor i32 [[NOTMASK]], -1 33; CHECK-NEXT: ret i32 [[RET]] 34; 35 %setbit = shl i32 1, %NBits 36 %ret = add nsw i32 %setbit, -1 37 ret i32 %ret 38} 39 40define i32 @shl_add_nuw(i32 %NBits) { 41; CHECK-LABEL: @shl_add_nuw( 42; CHECK-NEXT: ret i32 -1 43; 44 %setbit = shl i32 1, %NBits 45 %ret = add nuw i32 %setbit, -1 46 ret i32 %ret 47} 48 49define i32 @shl_add_nsw_nuw(i32 %NBits) { 50; CHECK-LABEL: @shl_add_nsw_nuw( 51; CHECK-NEXT: ret i32 -1 52; 53 %setbit = shl i32 1, %NBits 54 %ret = add nuw nsw i32 %setbit, -1 55 ret i32 %ret 56} 57 58; shl is nsw 59 60define i32 @shl_nsw_add(i32 %NBits) { 61; CHECK-LABEL: @shl_nsw_add( 62; CHECK-NEXT: [[NOTMASK:%.*]] = shl nsw i32 -1, [[NBITS:%.*]] 63; CHECK-NEXT: [[RET:%.*]] = xor i32 [[NOTMASK]], -1 64; CHECK-NEXT: ret i32 [[RET]] 65; 66 %setbit = shl nsw i32 1, %NBits 67 %ret = add i32 %setbit, -1 68 ret i32 %ret 69} 70 71define i32 @shl_nsw_add_nsw(i32 %NBits) { 72; CHECK-LABEL: @shl_nsw_add_nsw( 73; CHECK-NEXT: [[NOTMASK:%.*]] = shl nsw i32 -1, [[NBITS:%.*]] 74; CHECK-NEXT: [[RET:%.*]] = xor i32 [[NOTMASK]], -1 75; CHECK-NEXT: ret i32 [[RET]] 76; 77 %setbit = shl nsw i32 1, %NBits 78 %ret = add nsw i32 %setbit, -1 79 ret i32 %ret 80} 81 82define i32 @shl_nsw_add_nuw(i32 %NBits) { 83; CHECK-LABEL: @shl_nsw_add_nuw( 84; CHECK-NEXT: ret i32 -1 85; 86 %setbit = shl nsw i32 1, %NBits 87 %ret = add nuw i32 %setbit, -1 88 ret i32 %ret 89} 90 91define i32 @shl_nsw_add_nsw_nuw(i32 %NBits) { 92; CHECK-LABEL: @shl_nsw_add_nsw_nuw( 93; CHECK-NEXT: ret i32 -1 94; 95 %setbit = shl nsw i32 1, %NBits 96 %ret = add nuw nsw i32 %setbit, -1 97 ret i32 %ret 98} 99 100; shl is nuw 101 102define i32 @shl_nuw_add(i32 %NBits) { 103; CHECK-LABEL: @shl_nuw_add( 104; CHECK-NEXT: [[NOTMASK:%.*]] = shl nsw i32 -1, [[NBITS:%.*]] 105; CHECK-NEXT: [[RET:%.*]] = xor i32 [[NOTMASK]], -1 106; CHECK-NEXT: ret i32 [[RET]] 107; 108 %setbit = shl nuw i32 1, %NBits 109 %ret = add i32 %setbit, -1 110 ret i32 %ret 111} 112 113define i32 @shl_nuw_add_nsw(i32 %NBits) { 114; CHECK-LABEL: @shl_nuw_add_nsw( 115; CHECK-NEXT: [[NOTMASK:%.*]] = shl nsw i32 -1, [[NBITS:%.*]] 116; CHECK-NEXT: [[RET:%.*]] = xor i32 [[NOTMASK]], -1 117; CHECK-NEXT: ret i32 [[RET]] 118; 119 %setbit = shl nuw i32 1, %NBits 120 %ret = add nsw i32 %setbit, -1 121 ret i32 %ret 122} 123 124define i32 @shl_nuw_add_nuw(i32 %NBits) { 125; CHECK-LABEL: @shl_nuw_add_nuw( 126; CHECK-NEXT: ret i32 -1 127; 128 %setbit = shl nuw i32 1, %NBits 129 %ret = add nuw i32 %setbit, -1 130 ret i32 %ret 131} 132 133define i32 @shl_nuw_add_nsw_nuw(i32 %NBits) { 134; CHECK-LABEL: @shl_nuw_add_nsw_nuw( 135; CHECK-NEXT: ret i32 -1 136; 137 %setbit = shl nuw i32 1, %NBits 138 %ret = add nuw nsw i32 %setbit, -1 139 ret i32 %ret 140} 141 142; shl is nuw nsw 143 144define i32 @shl_nsw_nuw_add(i32 %NBits) { 145; CHECK-LABEL: @shl_nsw_nuw_add( 146; CHECK-NEXT: [[NOTMASK:%.*]] = shl nsw i32 -1, [[NBITS:%.*]] 147; CHECK-NEXT: [[RET:%.*]] = xor i32 [[NOTMASK]], -1 148; CHECK-NEXT: ret i32 [[RET]] 149; 150 %setbit = shl nuw nsw i32 1, %NBits 151 %ret = add i32 %setbit, -1 152 ret i32 %ret 153} 154 155define i32 @shl_nsw_nuw_add_nsw(i32 %NBits) { 156; CHECK-LABEL: @shl_nsw_nuw_add_nsw( 157; CHECK-NEXT: [[NOTMASK:%.*]] = shl nsw i32 -1, [[NBITS:%.*]] 158; CHECK-NEXT: [[RET:%.*]] = xor i32 [[NOTMASK]], -1 159; CHECK-NEXT: ret i32 [[RET]] 160; 161 %setbit = shl nuw nsw i32 1, %NBits 162 %ret = add nsw i32 %setbit, -1 163 ret i32 %ret 164} 165 166define i32 @shl_nsw_nuw_add_nuw(i32 %NBits) { 167; CHECK-LABEL: @shl_nsw_nuw_add_nuw( 168; CHECK-NEXT: ret i32 -1 169; 170 %setbit = shl nuw nsw i32 1, %NBits 171 %ret = add nuw i32 %setbit, -1 172 ret i32 %ret 173} 174 175define i32 @shl_nsw_nuw_add_nsw_nuw(i32 %NBits) { 176; CHECK-LABEL: @shl_nsw_nuw_add_nsw_nuw( 177; CHECK-NEXT: ret i32 -1 178; 179 %setbit = shl nuw nsw i32 1, %NBits 180 %ret = add nuw nsw i32 %setbit, -1 181 ret i32 %ret 182} 183 184; ============================================================================ ; 185; Vectors 186; ============================================================================ ; 187 188define <2 x i32> @shl_add_vec(<2 x i32> %NBits) { 189; CHECK-LABEL: @shl_add_vec( 190; CHECK-NEXT: [[NOTMASK:%.*]] = shl nsw <2 x i32> <i32 -1, i32 -1>, [[NBITS:%.*]] 191; CHECK-NEXT: [[RET:%.*]] = xor <2 x i32> [[NOTMASK]], <i32 -1, i32 -1> 192; CHECK-NEXT: ret <2 x i32> [[RET]] 193; 194 %setbit = shl <2 x i32> <i32 1, i32 1>, %NBits 195 %ret = add <2 x i32> %setbit, <i32 -1, i32 -1> 196 ret <2 x i32> %ret 197} 198 199define <3 x i32> @shl_add_vec_undef0(<3 x i32> %NBits) { 200; CHECK-LABEL: @shl_add_vec_undef0( 201; CHECK-NEXT: [[NOTMASK:%.*]] = shl nsw <3 x i32> <i32 -1, i32 -1, i32 -1>, [[NBITS:%.*]] 202; CHECK-NEXT: [[RET:%.*]] = xor <3 x i32> [[NOTMASK]], <i32 -1, i32 -1, i32 -1> 203; CHECK-NEXT: ret <3 x i32> [[RET]] 204; 205 %setbit = shl <3 x i32> <i32 1, i32 undef, i32 1>, %NBits 206 %ret = add <3 x i32> %setbit, <i32 -1, i32 -1, i32 -1> 207 ret <3 x i32> %ret 208} 209 210define <3 x i32> @shl_add_vec_undef1(<3 x i32> %NBits) { 211; CHECK-LABEL: @shl_add_vec_undef1( 212; CHECK-NEXT: [[NOTMASK:%.*]] = shl nsw <3 x i32> <i32 -1, i32 -1, i32 -1>, [[NBITS:%.*]] 213; CHECK-NEXT: [[RET:%.*]] = xor <3 x i32> [[NOTMASK]], <i32 -1, i32 -1, i32 -1> 214; CHECK-NEXT: ret <3 x i32> [[RET]] 215; 216 %setbit = shl <3 x i32> <i32 1, i32 1, i32 1>, %NBits 217 %ret = add <3 x i32> %setbit, <i32 -1, i32 undef, i32 -1> 218 ret <3 x i32> %ret 219} 220 221define <3 x i32> @shl_add_vec_undef2(<3 x i32> %NBits) { 222; CHECK-LABEL: @shl_add_vec_undef2( 223; CHECK-NEXT: [[NOTMASK:%.*]] = shl nsw <3 x i32> <i32 -1, i32 -1, i32 -1>, [[NBITS:%.*]] 224; CHECK-NEXT: [[RET:%.*]] = xor <3 x i32> [[NOTMASK]], <i32 -1, i32 -1, i32 -1> 225; CHECK-NEXT: ret <3 x i32> [[RET]] 226; 227 %setbit = shl <3 x i32> <i32 1, i32 undef, i32 1>, %NBits 228 %ret = add <3 x i32> %setbit, <i32 -1, i32 undef, i32 -1> 229 ret <3 x i32> %ret 230} 231 232; ============================================================================ ; 233; Negative tests. Should not be folded. 234; ============================================================================ ; 235 236declare void @use32(i32) 237 238; One use only. 239define i32 @bad_oneuse0(i32 %NBits) { 240; CHECK-LABEL: @bad_oneuse0( 241; CHECK-NEXT: [[SETBIT:%.*]] = shl i32 1, [[NBITS:%.*]] 242; CHECK-NEXT: call void @use32(i32 [[SETBIT]]) 243; CHECK-NEXT: [[RET:%.*]] = add i32 [[SETBIT]], -1 244; CHECK-NEXT: ret i32 [[RET]] 245; 246 %setbit = shl i32 1, %NBits 247 call void @use32(i32 %setbit) 248 %ret = add i32 %setbit, -1 249 ret i32 %ret 250} 251 252; shift base is not `1` constant 253 254define i32 @bad_shl(i32 %base, i32 %NBits) { 255; CHECK-LABEL: @bad_shl( 256; CHECK-NEXT: [[SETBIT:%.*]] = shl i32 [[BASE:%.*]], [[NBITS:%.*]] 257; CHECK-NEXT: [[RET:%.*]] = add i32 [[SETBIT]], -1 258; CHECK-NEXT: ret i32 [[RET]] 259; 260 %setbit = shl i32 %base, %NBits ; %base instead of 1 261 %ret = add i32 %setbit, -1 262 ret i32 %ret 263} 264 265; Second `add` operand is not `-1` constant 266 267define i32 @bad_add0(i32 %NBits, i32 %addop2) { 268; CHECK-LABEL: @bad_add0( 269; CHECK-NEXT: [[SETBIT:%.*]] = shl i32 1, [[NBITS:%.*]] 270; CHECK-NEXT: [[RET:%.*]] = add i32 [[SETBIT]], [[ADDOP2:%.*]] 271; CHECK-NEXT: ret i32 [[RET]] 272; 273 %setbit = shl i32 1, %NBits 274 %ret = add i32 %setbit, %addop2 275 ret i32 %ret 276} 277 278; Bad add constant 279 280define i32 @bad_add1(i32 %NBits) { 281; CHECK-LABEL: @bad_add1( 282; CHECK-NEXT: [[SETBIT:%.*]] = shl i32 1, [[NBITS:%.*]] 283; CHECK-NEXT: [[RET:%.*]] = add i32 [[SETBIT]], 1 284; CHECK-NEXT: ret i32 [[RET]] 285; 286 %setbit = shl i32 1, %NBits 287 %ret = add i32 %setbit, 1 ; not -1 288 ret i32 %ret 289} 290 291define i32 @bad_add2(i32 %NBits) { 292; CHECK-LABEL: @bad_add2( 293; CHECK-NEXT: [[SETBIT:%.*]] = shl i32 1, [[NBITS:%.*]] 294; CHECK-NEXT: [[RET:%.*]] = add i32 [[SETBIT]], -2 295; CHECK-NEXT: ret i32 [[RET]] 296; 297 %setbit = shl i32 1, %NBits 298 %ret = add i32 %setbit, -2 ; not -1 299 ret i32 %ret 300} 301