add support for llvm.cttz
MODIFY
ir/instr.cpp
ir/instr.cpp
@@ -47,6 +47,7 @@ BinOp::BinOp(Type &type, string &&name, Value &lhs, Value &rhs, Op op,
case And:
case Or:
case Xor:
+ case Cttz:
assert(flags == 0);
break;
}
@@ -72,6 +73,7 @@ void BinOp::print(ostream &os) const {
case And: str = "and"; break;
case Or: str = "or"; break;
case Xor: str = "xor"; break;
+ case Cttz: str = "cttz"; break;
}
const char *flag = nullptr;
@@ -212,15 +214,26 @@ StateValue BinOp::toSMT(State &s) const {
case Xor:
val = a ^ b;
break;
+
+ case Cttz:
+ val = a.cttz();
+ not_poison &= (b == 0u || a != 0u);
+ break;
+
}
return { move(val), move(not_poison) };
}
expr BinOp::getTypeConstraints(const Function &f) const {
+ auto instrConstraints = (getType() == rhs.getType());
+ if (op == Cttz)
+ instrConstraints = (rhs.getType().enforceIntType() &&
+ rhs.getType().sizeVar() == 1u);
+
return Value::getTypeConstraints() &&
getType().enforceIntOrPtrOrVectorType() &&
getType() == lhs.getType() &&
- getType() == rhs.getType();
+ instrConstraints;
}

MODIFY
ir/instr.h
ir/instr.h
@@ -25,7 +25,7 @@ class BinOp final : public Instr {
public:
enum Op { Add, Sub, Mul, SDiv, UDiv, SRem, URem, Shl, AShr, LShr,
SAdd_Sat, UAdd_Sat, SSub_Sat, USub_Sat,
- And, Or, Xor };
+ And, Or, Xor, Cttz };
enum Flags { None = 0, NSW = 1, NUW = 2, NSWNUW = 3, Exact = 4 };
private:

MODIFY
smt/expr.cpp
smt/expr.cpp
@@ -523,6 +523,17 @@ expr expr::lshr_exact(const expr &rhs) const {
return (lshr(rhs) << rhs) == *this;
}
+expr expr::cttz() const {
+ auto nbits = bits();
+
+ auto cond = mkUInt(nbits, nbits);
+ for (int i = nbits - 1; i >= 0; --i) {
+ cond = mkIf(extract(i, i) == 1u, mkUInt(i, nbits), cond);
+ }
+
+ return cond;
+}
+
expr expr::operator&(const expr &rhs) const {
if (eq(rhs))
return *this;

MODIFY
smt/expr.h
smt/expr.h
@@ -129,6 +129,8 @@ public:
expr ashr_exact(const expr &rhs) const;
expr lshr_exact(const expr &rhs) const;
+ expr cttz() const;
+
expr operator&(const expr &rhs) const;
expr operator|(const expr &rhs) const;
expr operator^(const expr &rhs) const;

ADD
tests/unit/cttz.opt
+Name: cttz constant
+%r = cttz i8 32, i1 0
+ =>
+%r = 5
+
+Name: cttz undef
+%r = cttz i8 0, i1 1
+ =>
+%r = undef
+
+Name: cttz def
+%r = cttz i8 0, i1 0
+ =>
+%r = 8
+
+Name: cttz variable
+%k = shl i8 1, 3
+%r = cttz i8 %k, i1 0
+ =>
+%k = 8
+%r = 3
+
+Name: cttz variable2
+%k = lshr i8 64, 2
+%r = cttz %k, i1 1
+ =>
+%k = 16
+%r = 4
+
+Name: cttz zero
+%k = cttz i4 1, i1 1
+ =>
+%k = 0
+
+Name: cttz sge
+%a = shl i4 %x, 1
+%b = cttz i4 %a, i1 1
+%c = icmp sge %b, 1
+ =>
+%a = shl i4 %x, 1
+%b = cttz i4 %a, i1 1
+%c = 1
+
+Name: cttz eq
+%a = shl i8 %x, 3
+%b = cttz i8 %a, i1 1
+%c = icmp slt %b, 3
+ =>
+%a = shl i8 %x, 3
+%b = cttz i8 %a, i1 1
+%c = 0

MODIFY
tools/alive_lexer.re
tools/alive_lexer.re
@@ -189,6 +189,7 @@ re2c:yyfill:check = 0;
"ugt" { return UGT; }
"freeze" { return FREEZE; }
"ret" { return RETURN; }
+"cttz" { return CTTZ; }
"unreachable" { return UNREACH; }
[a-zA-Z][a-zA-Z0-9]* {

MODIFY
tools/alive_parser.cpp
tools/alive_parser.cpp
@@ -104,6 +104,10 @@ struct tokenizer_t {
return peek() == END;
}
+ bool isType() {
+ return peek() == INT_TYPE;
+ }
+
private:
token get_new_token() const {
try {
@@ -234,6 +238,12 @@ static Type& parse_type(bool optional = true) {
UNREACHABLE();
}
+static Type& try_parse_type(Type &default_type) {
+ if (tokenizer.isType())
+ return parse_type();
+ return default_type;
+}
+
static Value& parse_operand(Type &type);
static Value& parse_const_expr(Type &type) {
@@ -354,6 +364,7 @@ static BinOp::Flags parse_binop_flags(token op_token) {
case AND:
case OR:
case XOR:
+ case CTTZ:
return BinOp::None;
default:
UNREACHABLE();
@@ -365,7 +376,8 @@ static unique_ptr<Instr> parse_binop(string_view name, token op_token) {
auto &type = parse_type();
auto &a = parse_operand(type);
parse_comma();
- auto &b = parse_operand(type);
+ auto &type2 = try_parse_type(type);
+ auto &b = parse_operand(type2);
BinOp::Op op;
switch (op_token) {
@@ -382,6 +394,7 @@ static unique_ptr<Instr> parse_binop(string_view name, token op_token) {
case AND: op = BinOp::And; break;
case OR: op = BinOp::Or; break;
case XOR: op = BinOp::Xor; break;
+ case CTTZ: op = BinOp::Cttz; break;
case SADD_SAT: op = BinOp::SAdd_Sat; break;
case UADD_SAT: op = BinOp::UAdd_Sat; break;
case SSUB_SAT: op = BinOp::SSub_Sat; break;
@@ -485,6 +498,7 @@ static unique_ptr<Instr> parse_instr(string_view name) {
case AND:
case OR:
case XOR:
+ case CTTZ:
return parse_binop(name, t);
case SEXT:
case ZEXT:

MODIFY
tools/tokens.h
tools/tokens.h
@@ -14,6 +14,7 @@ TOKEN(CEQ)
TOKEN(CNE)
TOKEN(CSLT)
TOKEN(CSGT)
+TOKEN(CTTZ)
TOKEN(CULT)
TOKEN(CUGT)
TOKEN(EQ)

MODIFY
tv/tv.cpp
tv/tv.cpp
@@ -277,6 +277,12 @@ public:
RETURN_IDENTIFIER(make_unique<BinOp>(*ty, value_name(i), *a, *b,
BinOp::USub_Sat));
}
+ case llvm::Intrinsic::cttz:
+ {
+ PARSE_BINOP();
+ RETURN_IDENTIFIER(make_unique<BinOp>(*ty, value_name(i), *a, *b,
+ BinOp::Cttz));
+ }
case llvm::Intrinsic::expect:
{
PARSE_UNOP();

add support for llvm.cttz (#21)

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