335 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 42; RUN: opt < %s -passes=instcombine -S | FileCheck %s3 4define i32 @log2_ceil_idiom(i32 %x) {5; CHECK-LABEL: define i32 @log2_ceil_idiom(6; CHECK-SAME: i32 [[X:%.*]]) {7; CHECK-NEXT: [[TMP1:%.*]] = add i32 [[X]], -18; CHECK-NEXT: [[TMP2:%.*]] = call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[TMP1]], i1 false)9; CHECK-NEXT: [[RET:%.*]] = sub nuw nsw i32 32, [[TMP2]]10; CHECK-NEXT: ret i32 [[RET]]11;12 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)13 %xor = xor i32 %ctlz, 3114 %ctpop = tail call i32 @llvm.ctpop.i32(i32 %x)15 %cmp = icmp ugt i32 %ctpop, 116 %zext = zext i1 %cmp to i3217 %ret = add i32 %xor, %zext18 ret i32 %ret19}20 21define i5 @log2_ceil_idiom_trunc(i32 %x) {22; CHECK-LABEL: define i5 @log2_ceil_idiom_trunc(23; CHECK-SAME: i32 [[X:%.*]]) {24; CHECK-NEXT: [[TMP1:%.*]] = add i32 [[X]], -125; CHECK-NEXT: [[TMP2:%.*]] = call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[TMP1]], i1 false)26; CHECK-NEXT: [[TMP3:%.*]] = sub nsw i32 0, [[TMP2]]27; CHECK-NEXT: [[RET:%.*]] = trunc i32 [[TMP3]] to i528; CHECK-NEXT: ret i5 [[RET]]29;30 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)31 %trunc = trunc i32 %ctlz to i532 %xor = xor i5 %trunc, 3133 %ctpop = tail call i32 @llvm.ctpop.i32(i32 %x)34 %cmp = icmp ugt i32 %ctpop, 135 %zext = zext i1 %cmp to i536 %ret = add i5 %xor, %zext37 ret i5 %ret38}39 40define i64 @log2_ceil_idiom_zext(i32 %x) {41; CHECK-LABEL: define i64 @log2_ceil_idiom_zext(42; CHECK-SAME: i32 [[X:%.*]]) {43; CHECK-NEXT: [[TMP1:%.*]] = add i32 [[X]], -144; CHECK-NEXT: [[TMP2:%.*]] = call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[TMP1]], i1 false)45; CHECK-NEXT: [[TMP3:%.*]] = sub nuw nsw i32 32, [[TMP2]]46; CHECK-NEXT: [[RET:%.*]] = zext nneg i32 [[TMP3]] to i6447; CHECK-NEXT: ret i64 [[RET]]48;49 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)50 %xor = xor i32 %ctlz, 3151 %ext = zext nneg i32 %xor to i6452 %ctpop = tail call i32 @llvm.ctpop.i32(i32 %x)53 %cmp = icmp ugt i32 %ctpop, 154 %zext = zext i1 %cmp to i6455 %ret = add i64 %ext, %zext56 ret i64 %ret57}58 59define i32 @log2_ceil_idiom_power2_test2(i32 %x) {60; CHECK-LABEL: define i32 @log2_ceil_idiom_power2_test2(61; CHECK-SAME: i32 [[X:%.*]]) {62; CHECK-NEXT: [[TMP1:%.*]] = add i32 [[X]], -163; CHECK-NEXT: [[TMP2:%.*]] = call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[TMP1]], i1 false)64; CHECK-NEXT: [[RET:%.*]] = sub nuw nsw i32 32, [[TMP2]]65; CHECK-NEXT: ret i32 [[RET]]66;67 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)68 %xor = xor i32 %ctlz, 3169 %ctpop = tail call i32 @llvm.ctpop.i32(i32 %x)70 %cmp = icmp ne i32 %ctpop, 171 %zext = zext i1 %cmp to i3272 %ret = add i32 %xor, %zext73 ret i32 %ret74}75 76define i32 @log2_ceil_idiom_commuted(i32 %x) {77; CHECK-LABEL: define i32 @log2_ceil_idiom_commuted(78; CHECK-SAME: i32 [[X:%.*]]) {79; CHECK-NEXT: [[TMP1:%.*]] = add i32 [[X]], -180; CHECK-NEXT: [[TMP2:%.*]] = call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[TMP1]], i1 false)81; CHECK-NEXT: [[RET:%.*]] = sub nuw nsw i32 32, [[TMP2]]82; CHECK-NEXT: ret i32 [[RET]]83;84 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)85 %xor = xor i32 %ctlz, 3186 %ctpop = tail call i32 @llvm.ctpop.i32(i32 %x)87 %cmp = icmp ugt i32 %ctpop, 188 %zext = zext i1 %cmp to i3289 %ret = add i32 %zext, %xor90 ret i32 %ret91}92 93define i32 @log2_ceil_idiom_multiuse1(i32 %x) {94; CHECK-LABEL: define i32 @log2_ceil_idiom_multiuse1(95; CHECK-SAME: i32 [[X:%.*]]) {96; CHECK-NEXT: [[CTPOP:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctpop.i32(i32 [[X]])97; CHECK-NEXT: call void @use32(i32 [[CTPOP]])98; CHECK-NEXT: [[TMP1:%.*]] = add i32 [[X]], -199; CHECK-NEXT: [[TMP2:%.*]] = call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[TMP1]], i1 false)100; CHECK-NEXT: [[RET:%.*]] = sub nuw nsw i32 32, [[TMP2]]101; CHECK-NEXT: ret i32 [[RET]]102;103 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)104 %xor = xor i32 %ctlz, 31105 %ctpop = tail call i32 @llvm.ctpop.i32(i32 %x)106 call void @use32(i32 %ctpop)107 %cmp = icmp ugt i32 %ctpop, 1108 %zext = zext i1 %cmp to i32109 %ret = add i32 %xor, %zext110 ret i32 %ret111}112 113; Negative tests114 115define i32 @log2_ceil_idiom_x_may_be_zero(i32 %x) {116; CHECK-LABEL: define i32 @log2_ceil_idiom_x_may_be_zero(117; CHECK-SAME: i32 [[X:%.*]]) {118; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[X]], i1 false)119; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[CTLZ]], 31120; CHECK-NEXT: [[CTPOP:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctpop.i32(i32 [[X]])121; CHECK-NEXT: [[CMP:%.*]] = icmp samesign ugt i32 [[CTPOP]], 1122; CHECK-NEXT: [[ZEXT:%.*]] = zext i1 [[CMP]] to i32123; CHECK-NEXT: [[RET:%.*]] = add nuw nsw i32 [[XOR]], [[ZEXT]]124; CHECK-NEXT: ret i32 [[RET]]125;126 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %x, i1 false)127 %xor = xor i32 %ctlz, 31128 %ctpop = tail call i32 @llvm.ctpop.i32(i32 %x)129 %cmp = icmp ugt i32 %ctpop, 1130 %zext = zext i1 %cmp to i32131 %ret = add i32 %xor, %zext132 ret i32 %ret133}134 135define i4 @log2_ceil_idiom_trunc_too_short(i32 %x) {136; CHECK-LABEL: define i4 @log2_ceil_idiom_trunc_too_short(137; CHECK-SAME: i32 [[X:%.*]]) {138; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[X]], i1 true)139; CHECK-NEXT: [[TRUNC:%.*]] = trunc i32 [[CTLZ]] to i4140; CHECK-NEXT: [[XOR:%.*]] = xor i4 [[TRUNC]], -1141; CHECK-NEXT: [[CTPOP:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctpop.i32(i32 [[X]])142; CHECK-NEXT: [[CMP:%.*]] = icmp samesign ugt i32 [[CTPOP]], 1143; CHECK-NEXT: [[ZEXT:%.*]] = zext i1 [[CMP]] to i4144; CHECK-NEXT: [[RET:%.*]] = add i4 [[XOR]], [[ZEXT]]145; CHECK-NEXT: ret i4 [[RET]]146;147 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)148 %trunc = trunc i32 %ctlz to i4149 %xor = xor i4 %trunc, 31150 %ctpop = tail call i32 @llvm.ctpop.i32(i32 %x)151 %cmp = icmp ugt i32 %ctpop, 1152 %zext = zext i1 %cmp to i4153 %ret = add i4 %xor, %zext154 ret i4 %ret155}156 157define i32 @log2_ceil_idiom_mismatched_operands(i32 %x, i32 %y) {158; CHECK-LABEL: define i32 @log2_ceil_idiom_mismatched_operands(159; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) {160; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[X]], i1 true)161; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[CTLZ]], 31162; CHECK-NEXT: [[CTPOP:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctpop.i32(i32 [[Y]])163; CHECK-NEXT: [[CMP:%.*]] = icmp samesign ugt i32 [[CTPOP]], 1164; CHECK-NEXT: [[ZEXT:%.*]] = zext i1 [[CMP]] to i32165; CHECK-NEXT: [[RET:%.*]] = add nuw nsw i32 [[XOR]], [[ZEXT]]166; CHECK-NEXT: ret i32 [[RET]]167;168 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)169 %xor = xor i32 %ctlz, 31170 %ctpop = tail call i32 @llvm.ctpop.i32(i32 %y)171 %cmp = icmp ugt i32 %ctpop, 1172 %zext = zext i1 %cmp to i32173 %ret = add i32 %xor, %zext174 ret i32 %ret175}176 177define i32 @log2_ceil_idiom_wrong_constant(i32 %x) {178; CHECK-LABEL: define i32 @log2_ceil_idiom_wrong_constant(179; CHECK-SAME: i32 [[X:%.*]]) {180; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[X]], i1 true)181; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[CTLZ]], 30182; CHECK-NEXT: [[CTPOP:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctpop.i32(i32 [[X]])183; CHECK-NEXT: [[CMP:%.*]] = icmp samesign ugt i32 [[CTPOP]], 1184; CHECK-NEXT: [[ZEXT:%.*]] = zext i1 [[CMP]] to i32185; CHECK-NEXT: [[RET:%.*]] = add nuw nsw i32 [[XOR]], [[ZEXT]]186; CHECK-NEXT: ret i32 [[RET]]187;188 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)189 %xor = xor i32 %ctlz, 30190 %ctpop = tail call i32 @llvm.ctpop.i32(i32 %x)191 %cmp = icmp ugt i32 %ctpop, 1192 %zext = zext i1 %cmp to i32193 %ret = add i32 %xor, %zext194 ret i32 %ret195}196 197define i32 @log2_ceil_idiom_not_a_power2_test1(i32 %x) {198; CHECK-LABEL: define i32 @log2_ceil_idiom_not_a_power2_test1(199; CHECK-SAME: i32 [[X:%.*]]) {200; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[X]], i1 true)201; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[CTLZ]], 31202; CHECK-NEXT: [[CTPOP:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctpop.i32(i32 [[X]])203; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[CTPOP]], 1204; CHECK-NEXT: [[ZEXT:%.*]] = zext i1 [[CMP]] to i32205; CHECK-NEXT: [[RET:%.*]] = add nuw nsw i32 [[XOR]], [[ZEXT]]206; CHECK-NEXT: ret i32 [[RET]]207;208 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)209 %xor = xor i32 %ctlz, 31210 %ctpop = tail call i32 @llvm.ctpop.i32(i32 %x)211 %cmp = icmp eq i32 %ctpop, 1212 %zext = zext i1 %cmp to i32213 %ret = add i32 %xor, %zext214 ret i32 %ret215}216 217define i32 @log2_ceil_idiom_not_a_power2_test2(i32 %x) {218; CHECK-LABEL: define i32 @log2_ceil_idiom_not_a_power2_test2(219; CHECK-SAME: i32 [[X:%.*]]) {220; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[X]], i1 true)221; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[CTLZ]], 31222; CHECK-NEXT: [[CTPOP:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctpop.i32(i32 [[X]])223; CHECK-NEXT: [[CMP:%.*]] = icmp samesign ugt i32 [[CTPOP]], 2224; CHECK-NEXT: [[ZEXT:%.*]] = zext i1 [[CMP]] to i32225; CHECK-NEXT: [[RET:%.*]] = add nuw nsw i32 [[XOR]], [[ZEXT]]226; CHECK-NEXT: ret i32 [[RET]]227;228 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)229 %xor = xor i32 %ctlz, 31230 %ctpop = tail call i32 @llvm.ctpop.i32(i32 %x)231 %cmp = icmp ugt i32 %ctpop, 2232 %zext = zext i1 %cmp to i32233 %ret = add i32 %xor, %zext234 ret i32 %ret235}236 237define i32 @log2_ceil_idiom_multiuse2(i32 %x) {238; CHECK-LABEL: define i32 @log2_ceil_idiom_multiuse2(239; CHECK-SAME: i32 [[X:%.*]]) {240; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[X]], i1 true)241; CHECK-NEXT: call void @use32(i32 [[CTLZ]])242; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[CTLZ]], 31243; CHECK-NEXT: [[CTPOP:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctpop.i32(i32 [[X]])244; CHECK-NEXT: [[CMP:%.*]] = icmp samesign ugt i32 [[CTPOP]], 1245; CHECK-NEXT: [[ZEXT:%.*]] = zext i1 [[CMP]] to i32246; CHECK-NEXT: [[RET:%.*]] = add nuw nsw i32 [[XOR]], [[ZEXT]]247; CHECK-NEXT: ret i32 [[RET]]248;249 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)250 call void @use32(i32 %ctlz)251 %xor = xor i32 %ctlz, 31252 %ctpop = tail call i32 @llvm.ctpop.i32(i32 %x)253 %cmp = icmp ugt i32 %ctpop, 1254 %zext = zext i1 %cmp to i32255 %ret = add i32 %xor, %zext256 ret i32 %ret257}258 259define i32 @log2_ceil_idiom_multiuse3(i32 %x) {260; CHECK-LABEL: define i32 @log2_ceil_idiom_multiuse3(261; CHECK-SAME: i32 [[X:%.*]]) {262; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[X]], i1 true)263; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[CTLZ]], 31264; CHECK-NEXT: call void @use32(i32 [[XOR]])265; CHECK-NEXT: [[CTPOP:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctpop.i32(i32 [[X]])266; CHECK-NEXT: [[CMP:%.*]] = icmp samesign ugt i32 [[CTPOP]], 1267; CHECK-NEXT: [[ZEXT:%.*]] = zext i1 [[CMP]] to i32268; CHECK-NEXT: [[RET:%.*]] = add nuw nsw i32 [[XOR]], [[ZEXT]]269; CHECK-NEXT: ret i32 [[RET]]270;271 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)272 %xor = xor i32 %ctlz, 31273 call void @use32(i32 %xor)274 %ctpop = tail call i32 @llvm.ctpop.i32(i32 %x)275 %cmp = icmp ugt i32 %ctpop, 1276 %zext = zext i1 %cmp to i32277 %ret = add i32 %xor, %zext278 ret i32 %ret279}280 281define i5 @log2_ceil_idiom_trunc_multiuse4(i32 %x) {282; CHECK-LABEL: define i5 @log2_ceil_idiom_trunc_multiuse4(283; CHECK-SAME: i32 [[X:%.*]]) {284; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[X]], i1 true)285; CHECK-NEXT: [[TRUNC:%.*]] = trunc nuw i32 [[CTLZ]] to i5286; CHECK-NEXT: call void @use5(i5 [[TRUNC]])287; CHECK-NEXT: [[XOR:%.*]] = xor i5 [[TRUNC]], -1288; CHECK-NEXT: [[CTPOP:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctpop.i32(i32 [[X]])289; CHECK-NEXT: [[CMP:%.*]] = icmp samesign ugt i32 [[CTPOP]], 1290; CHECK-NEXT: [[ZEXT:%.*]] = zext i1 [[CMP]] to i5291; CHECK-NEXT: [[RET:%.*]] = add i5 [[XOR]], [[ZEXT]]292; CHECK-NEXT: ret i5 [[RET]]293;294 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)295 %trunc = trunc i32 %ctlz to i5296 call void @use5(i5 %trunc)297 %xor = xor i5 %trunc, 31298 %ctpop = tail call i32 @llvm.ctpop.i32(i32 %x)299 %cmp = icmp ugt i32 %ctpop, 1300 %zext = zext i1 %cmp to i5301 %ret = add i5 %xor, %zext302 ret i5 %ret303}304 305define i64 @log2_ceil_idiom_zext_multiuse5(i32 %x) {306; CHECK-LABEL: define i64 @log2_ceil_idiom_zext_multiuse5(307; CHECK-SAME: i32 [[X:%.*]]) {308; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[X]], i1 true)309; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[CTLZ]], 31310; CHECK-NEXT: [[EXT:%.*]] = zext nneg i32 [[XOR]] to i64311; CHECK-NEXT: call void @use64(i64 [[EXT]])312; CHECK-NEXT: [[CTPOP:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctpop.i32(i32 [[X]])313; CHECK-NEXT: [[CMP:%.*]] = icmp samesign ugt i32 [[CTPOP]], 1314; CHECK-NEXT: [[ZEXT:%.*]] = zext i1 [[CMP]] to i64315; CHECK-NEXT: [[RET:%.*]] = add nuw nsw i64 [[EXT]], [[ZEXT]]316; CHECK-NEXT: ret i64 [[RET]]317;318 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)319 %xor = xor i32 %ctlz, 31320 %ext = zext nneg i32 %xor to i64321 call void @use64(i64 %ext)322 %ctpop = tail call i32 @llvm.ctpop.i32(i32 %x)323 %cmp = icmp ugt i32 %ctpop, 1324 %zext = zext i1 %cmp to i64325 %ret = add i64 %ext, %zext326 ret i64 %ret327}328 329declare void @use5(i5)330declare void @use32(i32)331declare void @use64(i64)332 333declare i32 @llvm.ctlz.i32(i32, i1)334declare i32 @llvm.ctpop.i32(i32)335