Implemented BitCount as an intrinsic. With unit test.
Rationale:
Recognizing this important operation as an intrinsic has
various advantages:
(1) having the no-side-effects/no-throw allows for
much more GVN/LICM/BCE.
(2) Some architectures, like x86_64, provide direct
support for this operation.
Performance improvements on X86_64:
CheckersEvalBench (32-bit bitboard): 27,210KNS -> 36,798KNS = + 35%
ReversiEvalBench (64-bit bitboard): 52,562KNS -> 89,086KNS = + 69%
Change-Id: I65d549b0469b7909b12c6611cdc34a8640a5751f
diff --git a/runtime/arch/x86/instruction_set_features_x86.cc b/runtime/arch/x86/instruction_set_features_x86.cc
index 42f5df4..da01ee4 100644
--- a/runtime/arch/x86/instruction_set_features_x86.cc
+++ b/runtime/arch/x86/instruction_set_features_x86.cc
@@ -50,6 +50,10 @@
"silvermont",
};
+static constexpr const char* x86_variants_with_popcnt[] = {
+ "silvermont",
+};
+
const X86InstructionSetFeatures* X86InstructionSetFeatures::FromVariant(
const std::string& variant, std::string* error_msg ATTRIBUTE_UNUSED,
bool x86_64) {
@@ -69,6 +73,11 @@
arraysize(x86_variants_prefer_locked_add_sync),
variant);
+ bool has_POPCNT = FindVariantInArray(x86_variants_with_popcnt,
+ arraysize(x86_variants_with_popcnt),
+ variant);
+
+ // Verify that variant is known.
bool known_variant = FindVariantInArray(x86_known_variants, arraysize(x86_known_variants),
variant);
if (!known_variant && variant != "default") {
@@ -77,10 +86,10 @@
if (x86_64) {
return new X86_64InstructionSetFeatures(smp, has_SSSE3, has_SSE4_1, has_SSE4_2, has_AVX,
- has_AVX2, prefers_locked_add);
+ has_AVX2, prefers_locked_add, has_POPCNT);
} else {
return new X86InstructionSetFeatures(smp, has_SSSE3, has_SSE4_1, has_SSE4_2, has_AVX,
- has_AVX2, prefers_locked_add);
+ has_AVX2, prefers_locked_add, has_POPCNT);
}
}
@@ -93,12 +102,15 @@
bool has_AVX = (bitmap & kAvxBitfield) != 0;
bool has_AVX2 = (bitmap & kAvxBitfield) != 0;
bool prefers_locked_add = (bitmap & kPrefersLockedAdd) != 0;
+ bool has_POPCNT = (bitmap & kPopCntBitfield) != 0;
if (x86_64) {
return new X86_64InstructionSetFeatures(smp, has_SSSE3, has_SSE4_1, has_SSE4_2,
- has_AVX, has_AVX2, prefers_locked_add);
+ has_AVX, has_AVX2, prefers_locked_add,
+ has_POPCNT);
} else {
return new X86InstructionSetFeatures(smp, has_SSSE3, has_SSE4_1, has_SSE4_2,
- has_AVX, has_AVX2, prefers_locked_add);
+ has_AVX, has_AVX2, prefers_locked_add,
+ has_POPCNT);
}
}
@@ -138,12 +150,15 @@
// No #define for memory synchronization preference.
const bool prefers_locked_add = false;
+ // No #define for popcnt.
+ const bool has_POPCNT = false;
+
if (x86_64) {
return new X86_64InstructionSetFeatures(smp, has_SSSE3, has_SSE4_1, has_SSE4_2, has_AVX,
- has_AVX2, prefers_locked_add);
+ has_AVX2, prefers_locked_add, has_POPCNT);
} else {
return new X86InstructionSetFeatures(smp, has_SSSE3, has_SSE4_1, has_SSE4_2, has_AVX,
- has_AVX2, prefers_locked_add);
+ has_AVX2, prefers_locked_add, has_POPCNT);
}
}
@@ -158,6 +173,7 @@
bool has_AVX2 = false;
// No cpuinfo for memory synchronization preference.
const bool prefers_locked_add = false;
+ bool has_POPCNT = false;
std::ifstream in("/proc/cpuinfo");
if (!in.fail()) {
@@ -183,6 +199,9 @@
if (line.find("avx2") != std::string::npos) {
has_AVX2 = true;
}
+ if (line.find("popcnt") != std::string::npos) {
+ has_POPCNT = true;
+ }
} else if (line.find("processor") != std::string::npos &&
line.find(": 1") != std::string::npos) {
smp = true;
@@ -195,10 +214,10 @@
}
if (x86_64) {
return new X86_64InstructionSetFeatures(smp, has_SSSE3, has_SSE4_1, has_SSE4_2, has_AVX,
- has_AVX2, prefers_locked_add);
+ has_AVX2, prefers_locked_add, has_POPCNT);
} else {
return new X86InstructionSetFeatures(smp, has_SSSE3, has_SSE4_1, has_SSE4_2, has_AVX,
- has_AVX2, prefers_locked_add);
+ has_AVX2, prefers_locked_add, has_POPCNT);
}
}
@@ -223,7 +242,8 @@
(has_SSE4_2_ == other_as_x86->has_SSE4_2_) &&
(has_AVX_ == other_as_x86->has_AVX_) &&
(has_AVX2_ == other_as_x86->has_AVX2_) &&
- (prefers_locked_add_ == other_as_x86->prefers_locked_add_);
+ (prefers_locked_add_ == other_as_x86->prefers_locked_add_) &&
+ (has_POPCNT_ == other_as_x86->has_POPCNT_);
}
uint32_t X86InstructionSetFeatures::AsBitmap() const {
@@ -233,7 +253,8 @@
(has_SSE4_2_ ? kSse4_2Bitfield : 0) |
(has_AVX_ ? kAvxBitfield : 0) |
(has_AVX2_ ? kAvx2Bitfield : 0) |
- (prefers_locked_add_ ? kPrefersLockedAdd : 0);
+ (prefers_locked_add_ ? kPrefersLockedAdd : 0) |
+ (has_POPCNT_ ? kPopCntBitfield : 0);
}
std::string X86InstructionSetFeatures::GetFeatureString() const {
@@ -273,6 +294,11 @@
} else {
result += ",-lock_add";
}
+ if (has_POPCNT_) {
+ result += ",popcnt";
+ } else {
+ result += ",-popcnt";
+ }
return result;
}
@@ -285,6 +311,7 @@
bool has_AVX = has_AVX_;
bool has_AVX2 = has_AVX2_;
bool prefers_locked_add = prefers_locked_add_;
+ bool has_POPCNT = has_POPCNT_;
for (auto i = features.begin(); i != features.end(); i++) {
std::string feature = Trim(*i);
if (feature == "ssse3") {
@@ -311,6 +338,10 @@
prefers_locked_add = true;
} else if (feature == "-lock_add") {
prefers_locked_add = false;
+ } else if (feature == "popcnt") {
+ has_POPCNT = true;
+ } else if (feature == "-popcnt") {
+ has_POPCNT = false;
} else {
*error_msg = StringPrintf("Unknown instruction set feature: '%s'", feature.c_str());
return nullptr;
@@ -318,10 +349,10 @@
}
if (x86_64) {
return new X86_64InstructionSetFeatures(smp, has_SSSE3, has_SSE4_1, has_SSE4_2, has_AVX,
- has_AVX2, prefers_locked_add);
+ has_AVX2, prefers_locked_add, has_POPCNT);
} else {
return new X86InstructionSetFeatures(smp, has_SSSE3, has_SSE4_1, has_SSE4_2, has_AVX,
- has_AVX2, prefers_locked_add);
+ has_AVX2, prefers_locked_add, has_POPCNT);
}
}
diff --git a/runtime/arch/x86/instruction_set_features_x86.h b/runtime/arch/x86/instruction_set_features_x86.h
index 2b845f8..1819654 100644
--- a/runtime/arch/x86/instruction_set_features_x86.h
+++ b/runtime/arch/x86/instruction_set_features_x86.h
@@ -62,6 +62,8 @@
bool PrefersLockedAddSynchronization() const { return prefers_locked_add_; }
+ bool HasPopCnt() const { return has_POPCNT_; }
+
protected:
// Parse a string of the form "ssse3" adding these to a new InstructionSetFeatures.
virtual const InstructionSetFeatures*
@@ -75,10 +77,17 @@
bool x86_64, std::string* error_msg) const;
X86InstructionSetFeatures(bool smp, bool has_SSSE3, bool has_SSE4_1, bool has_SSE4_2,
- bool has_AVX, bool has_AVX2, bool prefers_locked_add)
- : InstructionSetFeatures(smp), has_SSSE3_(has_SSSE3), has_SSE4_1_(has_SSE4_1),
- has_SSE4_2_(has_SSE4_2), has_AVX_(has_AVX), has_AVX2_(has_AVX2),
- prefers_locked_add_(prefers_locked_add) {
+ bool has_AVX, bool has_AVX2,
+ bool prefers_locked_add,
+ bool has_POPCNT)
+ : InstructionSetFeatures(smp),
+ has_SSSE3_(has_SSSE3),
+ has_SSE4_1_(has_SSE4_1),
+ has_SSE4_2_(has_SSE4_2),
+ has_AVX_(has_AVX),
+ has_AVX2_(has_AVX2),
+ prefers_locked_add_(prefers_locked_add),
+ has_POPCNT_(has_POPCNT) {
}
private:
@@ -91,6 +100,7 @@
kAvxBitfield = 16,
kAvx2Bitfield = 32,
kPrefersLockedAdd = 64,
+ kPopCntBitfield = 128,
};
const bool has_SSSE3_; // x86 128bit SIMD - Supplemental SSE.
@@ -99,6 +109,7 @@
const bool has_AVX_; // x86 256bit SIMD AVX.
const bool has_AVX2_; // x86 256bit SIMD AVX 2.0.
const bool prefers_locked_add_; // x86 use locked add for memory synchronization.
+ const bool has_POPCNT_; // x86 population count
DISALLOW_COPY_AND_ASSIGN(X86InstructionSetFeatures);
};
diff --git a/runtime/arch/x86/instruction_set_features_x86_test.cc b/runtime/arch/x86/instruction_set_features_x86_test.cc
index e8d01e6..a062c12 100644
--- a/runtime/arch/x86/instruction_set_features_x86_test.cc
+++ b/runtime/arch/x86/instruction_set_features_x86_test.cc
@@ -27,7 +27,7 @@
ASSERT_TRUE(x86_features.get() != nullptr) << error_msg;
EXPECT_EQ(x86_features->GetInstructionSet(), kX86);
EXPECT_TRUE(x86_features->Equals(x86_features.get()));
- EXPECT_STREQ("smp,-ssse3,-sse4.1,-sse4.2,-avx,-avx2,-lock_add",
+ EXPECT_STREQ("smp,-ssse3,-sse4.1,-sse4.2,-avx,-avx2,-lock_add,-popcnt",
x86_features->GetFeatureString().c_str());
EXPECT_EQ(x86_features->AsBitmap(), 1U);
}
@@ -40,7 +40,7 @@
ASSERT_TRUE(x86_features.get() != nullptr) << error_msg;
EXPECT_EQ(x86_features->GetInstructionSet(), kX86);
EXPECT_TRUE(x86_features->Equals(x86_features.get()));
- EXPECT_STREQ("smp,ssse3,-sse4.1,-sse4.2,-avx,-avx2,lock_add",
+ EXPECT_STREQ("smp,ssse3,-sse4.1,-sse4.2,-avx,-avx2,lock_add,-popcnt",
x86_features->GetFeatureString().c_str());
EXPECT_EQ(x86_features->AsBitmap(), 67U);
@@ -50,7 +50,7 @@
ASSERT_TRUE(x86_default_features.get() != nullptr) << error_msg;
EXPECT_EQ(x86_default_features->GetInstructionSet(), kX86);
EXPECT_TRUE(x86_default_features->Equals(x86_default_features.get()));
- EXPECT_STREQ("smp,-ssse3,-sse4.1,-sse4.2,-avx,-avx2,-lock_add",
+ EXPECT_STREQ("smp,-ssse3,-sse4.1,-sse4.2,-avx,-avx2,-lock_add,-popcnt",
x86_default_features->GetFeatureString().c_str());
EXPECT_EQ(x86_default_features->AsBitmap(), 1U);
@@ -60,7 +60,7 @@
ASSERT_TRUE(x86_64_features.get() != nullptr) << error_msg;
EXPECT_EQ(x86_64_features->GetInstructionSet(), kX86_64);
EXPECT_TRUE(x86_64_features->Equals(x86_64_features.get()));
- EXPECT_STREQ("smp,ssse3,-sse4.1,-sse4.2,-avx,-avx2,lock_add",
+ EXPECT_STREQ("smp,ssse3,-sse4.1,-sse4.2,-avx,-avx2,lock_add,-popcnt",
x86_64_features->GetFeatureString().c_str());
EXPECT_EQ(x86_64_features->AsBitmap(), 67U);
@@ -77,9 +77,9 @@
ASSERT_TRUE(x86_features.get() != nullptr) << error_msg;
EXPECT_EQ(x86_features->GetInstructionSet(), kX86);
EXPECT_TRUE(x86_features->Equals(x86_features.get()));
- EXPECT_STREQ("smp,ssse3,sse4.1,sse4.2,-avx,-avx2,lock_add",
+ EXPECT_STREQ("smp,ssse3,sse4.1,sse4.2,-avx,-avx2,lock_add,popcnt",
x86_features->GetFeatureString().c_str());
- EXPECT_EQ(x86_features->AsBitmap(), 79U);
+ EXPECT_EQ(x86_features->AsBitmap(), 207U);
// Build features for a 32-bit x86 default processor.
std::unique_ptr<const InstructionSetFeatures> x86_default_features(
@@ -87,7 +87,7 @@
ASSERT_TRUE(x86_default_features.get() != nullptr) << error_msg;
EXPECT_EQ(x86_default_features->GetInstructionSet(), kX86);
EXPECT_TRUE(x86_default_features->Equals(x86_default_features.get()));
- EXPECT_STREQ("smp,-ssse3,-sse4.1,-sse4.2,-avx,-avx2,-lock_add",
+ EXPECT_STREQ("smp,-ssse3,-sse4.1,-sse4.2,-avx,-avx2,-lock_add,-popcnt",
x86_default_features->GetFeatureString().c_str());
EXPECT_EQ(x86_default_features->AsBitmap(), 1U);
@@ -97,9 +97,9 @@
ASSERT_TRUE(x86_64_features.get() != nullptr) << error_msg;
EXPECT_EQ(x86_64_features->GetInstructionSet(), kX86_64);
EXPECT_TRUE(x86_64_features->Equals(x86_64_features.get()));
- EXPECT_STREQ("smp,ssse3,sse4.1,sse4.2,-avx,-avx2,lock_add",
+ EXPECT_STREQ("smp,ssse3,sse4.1,sse4.2,-avx,-avx2,lock_add,popcnt",
x86_64_features->GetFeatureString().c_str());
- EXPECT_EQ(x86_64_features->AsBitmap(), 79U);
+ EXPECT_EQ(x86_64_features->AsBitmap(), 207U);
EXPECT_FALSE(x86_64_features->Equals(x86_features.get()));
EXPECT_FALSE(x86_64_features->Equals(x86_default_features.get()));
diff --git a/runtime/arch/x86_64/instruction_set_features_x86_64.h b/runtime/arch/x86_64/instruction_set_features_x86_64.h
index b8000d0..aba7234 100644
--- a/runtime/arch/x86_64/instruction_set_features_x86_64.h
+++ b/runtime/arch/x86_64/instruction_set_features_x86_64.h
@@ -74,9 +74,10 @@
private:
X86_64InstructionSetFeatures(bool smp, bool has_SSSE3, bool has_SSE4_1, bool has_SSE4_2,
- bool has_AVX, bool has_AVX2, bool prefers_locked_add)
+ bool has_AVX, bool has_AVX2, bool prefers_locked_add,
+ bool has_POPCNT)
: X86InstructionSetFeatures(smp, has_SSSE3, has_SSE4_1, has_SSE4_2, has_AVX,
- has_AVX2, prefers_locked_add) {
+ has_AVX2, prefers_locked_add, has_POPCNT) {
}
friend class X86InstructionSetFeatures;
diff --git a/runtime/arch/x86_64/instruction_set_features_x86_64_test.cc b/runtime/arch/x86_64/instruction_set_features_x86_64_test.cc
index 4562c64..78aeacf 100644
--- a/runtime/arch/x86_64/instruction_set_features_x86_64_test.cc
+++ b/runtime/arch/x86_64/instruction_set_features_x86_64_test.cc
@@ -27,7 +27,7 @@
ASSERT_TRUE(x86_64_features.get() != nullptr) << error_msg;
EXPECT_EQ(x86_64_features->GetInstructionSet(), kX86_64);
EXPECT_TRUE(x86_64_features->Equals(x86_64_features.get()));
- EXPECT_STREQ("smp,-ssse3,-sse4.1,-sse4.2,-avx,-avx2,-lock_add",
+ EXPECT_STREQ("smp,-ssse3,-sse4.1,-sse4.2,-avx,-avx2,-lock_add,-popcnt",
x86_64_features->GetFeatureString().c_str());
EXPECT_EQ(x86_64_features->AsBitmap(), 1U);
}
diff --git a/runtime/quick/inline_method_analyser.h b/runtime/quick/inline_method_analyser.h
index 6cea902..ca456c2 100644
--- a/runtime/quick/inline_method_analyser.h
+++ b/runtime/quick/inline_method_analyser.h
@@ -39,6 +39,7 @@
kIntrinsicFloatCvt,
kIntrinsicReverseBits,
kIntrinsicReverseBytes,
+ kIntrinsicBitCount,
kIntrinsicNumberOfLeadingZeros,
kIntrinsicNumberOfTrailingZeros,
kIntrinsicRotateRight,