add support for llvm.ctpop
MODIFY
ir/instr.cpp
ir/instr.cpp
@@ -250,6 +250,34 @@ expr BinOp::getTypeConstraints(const Function &f) const {
}
+void UnaryOp::print(ostream &os) const {
+ const char *str = nullptr;
+ switch (op) {
+ case Ctpop: str = "ctpop "; break;
+ }
+
+ os << getName() << " = " << str << val;
+}
+
+StateValue UnaryOp::toSMT(State &s) const {
+ auto &[v, vp] = s[val];
+ expr newval;
+
+ switch (op) {
+ case Ctpop:
+ newval = v.ctpop();
+ break;
+ }
+ return { move(newval), expr(vp) };
+}
+
+expr UnaryOp::getTypeConstraints(const Function &f) const {
+ return Value::getTypeConstraints() &&
+ getType().enforceIntOrPtrOrVectorType() &&
+ getType() == val.getType();
+}
+
+
void ConversionOp::print(ostream &os) const {
const char *str = nullptr;
switch (op) {

MODIFY
ir/instr.h
ir/instr.h
@@ -42,6 +42,21 @@ public:
smt::expr getTypeConstraints(const Function &f) const override;
};
+class UnaryOp final : public Instr {
+public:
+ enum Op { Ctpop };
+
+private:
+ Value &val;
+ Op op;
+
+public:
+ UnaryOp(Type &type, std::string &&name, Value &val, Op op)
+ : Instr(type, std::move(name)), val(val), op(op) {}
+ void print(std::ostream &os) const override;
+ StateValue toSMT(State &s) const override;
+ smt::expr getTypeConstraints(const Function &f) const override;
+};
class ConversionOp final : public Instr {
public:

MODIFY
smt/expr.cpp
smt/expr.cpp
@@ -547,6 +547,18 @@ expr expr::ctlz() const {
return cond;
}
+expr expr::ctpop() const {
+ C();
+ auto nbits = bits();
+
+ auto res = mkUInt(0, nbits);
+ for (unsigned i = 0; i < nbits; ++i) {
+ res = res + extract(i, i).zext(nbits - 1);
+ }
+
+ return res;
+}
+
expr expr::operator&(const expr &rhs) const {
if (eq(rhs))
return *this;

MODIFY
smt/expr.h
smt/expr.h
@@ -131,6 +131,7 @@ public:
expr cttz() const;
expr ctlz() const;
+ expr ctpop() const;
expr operator&(const expr &rhs) const;
expr operator|(const expr &rhs) const;

ADD
tests/unit/ctpop.opt
+Name: ctpop constant
+%a = ctpop i8 32
+ =>
+%a = 1
+
+Name: ctpop variable
+%a = shl i8 255, 3
+%b = ctpop i8 %a
+ =>
+%a = shl i8 255, 3
+%b = 5
+
+Name: ctpop zero
+%a = ctpop i8 0
+ =>
+%a = 0
+
+Name: ctpop all
+%a = ctpop i8 255
+ =>
+%a = 8
+
+Name: ctpop icmp
+%a = shl i8 %x, 2
+%b = ctpop i8 %a
+%c = icmp sle %b, 6
+ =>
+%a = shl i8 %x, 2
+%b = ctpop i8 %a
+%c = 1
+
+Name: ctpop negtest
+%a = shl i8 %x, 3
+%b = ctpop i8 %a
+%c = icmp sgt %b, 5
+ =>
+%a = shl i8 %x, 3
+%b = ctpop i8 %a
+%c = 0

MODIFY
tools/alive_lexer.re
tools/alive_lexer.re
@@ -191,6 +191,7 @@ re2c:yyfill:check = 0;
"ret" { return RETURN; }
"cttz" { return CTTZ; }
"ctlz" { return CTLZ; }
+"ctpop" { return CTPOP; }
"unreachable" { return UNREACH; }
[a-zA-Z][a-zA-Z0-9]* {

MODIFY
tools/alive_parser.cpp
tools/alive_parser.cpp
@@ -407,6 +407,19 @@ static unique_ptr<Instr> parse_binop(string_view name, token op_token) {
return make_unique<BinOp>(type, string(name), a, b, op, flags);
}
+static unique_ptr<Instr> parse_unaryop(string_view name, token op_token) {
+ UnaryOp::Op op;
+ switch (op_token) {
+ case CTPOP: op = UnaryOp::Ctpop; break;
+ default:
+ UNREACHABLE();
+ }
+
+ auto &ty = parse_type();
+ auto &a = parse_operand(ty);
+ return make_unique<UnaryOp>(ty, string(name), a, op);
+}
+
static unique_ptr<Instr> parse_conversionop(string_view name, token op_token) {
// op ty %op to ty2
auto &opty = parse_type();
@@ -503,6 +516,8 @@ static unique_ptr<Instr> parse_instr(string_view name) {
case CTTZ:
case CTLZ:
return parse_binop(name, t);
+ case CTPOP:
+ return parse_unaryop(name, t);
case SEXT:
case ZEXT:
case TRUNC:

MODIFY
tools/tokens.h
tools/tokens.h
@@ -15,6 +15,7 @@ TOKEN(CNE)
TOKEN(CSLT)
TOKEN(CSGT)
TOKEN(CTLZ)
+TOKEN(CTPOP)
TOKEN(CTTZ)
TOKEN(CULT)
TOKEN(CUGT)

MODIFY
tv/tv.cpp
tv/tv.cpp
@@ -289,6 +289,11 @@ public:
RETURN_IDENTIFIER(make_unique<BinOp>(*ty, value_name(i), *a, *b,
BinOp::Ctlz));
}
+ case llvm::Intrinsic::ctpop:
+ {
+ PARSE_UNOP();
+ RETURN_IDENTIFIER(make_unique<UnaryOp>(*ty, value_name(i), *val, UnaryOp::Ctpop));
+ }
case llvm::Intrinsic::expect:
{
PARSE_UNOP();

add support for llvm.ctpop

https://llvm.org/docs/LangRef.html#llvm-ctpop-intrinsic