add support for llvm.ctlz
MODIFY
ir/instr.cpp
ir/instr.cpp
@@ -48,6 +48,7 @@ BinOp::BinOp(Type &type, string &&name, Value &lhs, Value &rhs, Op op,
case Or:
case Xor:
case Cttz:
+ case Ctlz:
assert(flags == 0);
break;
}
@@ -74,6 +75,7 @@ void BinOp::print(ostream &os) const {
case Or: str = "or"; break;
case Xor: str = "xor"; break;
case Cttz: str = "cttz"; break;
+ case Ctlz: str = "ctlz"; break;
}
const char *flag = nullptr;
@@ -220,20 +222,31 @@ StateValue BinOp::toSMT(State &s) const {
not_poison &= (b == 0u || a != 0u);
break;
+ case Ctlz:
+ val = a.ctlz();
+ 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() &&
+ expr instrconstr;
+ switch (op) {
+ case Cttz:
+ case Ctlz:
+ instrconstr = (rhs.getType().enforceIntType() &&
rhs.getType().sizeVar() == 1u);
+ break;
+ default:
+ instrconstr = (getType() == rhs.getType());
+ }
return Value::getTypeConstraints() &&
getType().enforceIntOrPtrOrVectorType() &&
getType() == lhs.getType() &&
- instrConstraints;
+ move(instrconstr);
}

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, Cttz };
+ And, Or, Xor, Cttz, Ctlz };
enum Flags { None = 0, NSW = 1, NUW = 2, NSWNUW = 3, Exact = 4 };
private:

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

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

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

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

MODIFY
tools/alive_parser.cpp
tools/alive_parser.cpp
@@ -365,6 +365,7 @@ static BinOp::Flags parse_binop_flags(token op_token) {
case OR:
case XOR:
case CTTZ:
+ case CTLZ:
return BinOp::None;
default:
UNREACHABLE();
@@ -395,6 +396,7 @@ static unique_ptr<Instr> parse_binop(string_view name, token op_token) {
case OR: op = BinOp::Or; break;
case XOR: op = BinOp::Xor; break;
case CTTZ: op = BinOp::Cttz; break;
+ case CTLZ: op = BinOp::Ctlz; 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;
@@ -499,6 +501,7 @@ static unique_ptr<Instr> parse_instr(string_view name) {
case OR:
case XOR:
case CTTZ:
+ case CTLZ:
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(CTLZ)
TOKEN(CTTZ)
TOKEN(CULT)
TOKEN(CUGT)

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

add support for llvm.ctlz

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