Add ffs/ffsl/ffsll
MODIFY
ir/instr.cpp
ir/instr.cpp
@@ -490,7 +490,7 @@ StateValue BinOp::toSMT(State &s) const {
case Cttz:
fn = [](auto a, auto ap, auto b, auto bp) -> StateValue {
- return { a.cttz(),
+ return { a.cttz(expr::mkUInt(a.bits(), a)),
b == 0u || a != 0u };
};
break;
@@ -817,6 +817,7 @@ void UnaryOp::print(ostream &os) const {
case Ctpop: str = "ctpop "; break;
case IsConstant: str = "is.constant "; break;
case FNeg: str = "fneg "; break;
+ case FFS: str = "ffs "; break;
}
os << getName() << " = " << str << fmath << print_type(getType())
@@ -857,6 +858,11 @@ StateValue UnaryOp::toSMT(State &s) const {
return {};
fn = [](auto v) { return v.fneg(); };
break;
+ case FFS:
+ fn = [](auto v) {
+ return v.cttz(expr::mkInt(-1, v)) + expr::mkUInt(1, v);
+ };
+ break;
}
auto &v = s[*val];
@@ -894,6 +900,9 @@ expr UnaryOp::getTypeConstraints(const Function &f) const {
case FNeg:
instrconstr &= getType().enforceFloatOrVectorType();
break;
+ case FFS:
+ instrconstr &= getType().enforceIntType();
+ break;
}
return Value::getTypeConstraints() && move(instrconstr);

MODIFY
ir/instr.h
ir/instr.h
@@ -74,7 +74,7 @@ public:
class UnaryOp final : public Instr {
public:
enum Op {
- Copy, BitReverse, BSwap, Ctpop, IsConstant, FNeg
+ Copy, BitReverse, BSwap, Ctpop, IsConstant, FNeg, FFS
};
private:

MODIFY
llvm_util/known_fns.cpp
llvm_util/known_fns.cpp
@@ -94,6 +94,20 @@ known_call(llvm::CallInst &i, const llvm::TargetLibraryInfo &TLI,
make_unique<Memcmp>(*ty, value_name(i), *args[0], *args[1], *args[2],
libfn == llvm::LibFunc_bcmp));
}
+ case llvm::LibFunc_ffs:
+ case llvm::LibFunc_ffsl:
+ case llvm::LibFunc_ffsll: {
+ bool needs_trunc = &args[0]->getType() != ty;
+ auto *Op = new UnaryOp(args[0]->getType(),
+ value_name(i) + (needs_trunc ? "#beftrunc" : ""),
+ *args[0], UnaryOp::FFS);
+ if (!needs_trunc)
+ RETURN_KNOWN(unique_ptr<UnaryOp>(Op));
+
+ BB.addInstr(unique_ptr<UnaryOp>(Op));
+ RETURN_KNOWN(
+ make_unique<ConversionOp>(*ty, value_name(i), *Op, ConversionOp::Trunc));
+ }
default:
RETURN_FAIL_KNOWN();
}

MODIFY
smt/expr.cpp
smt/expr.cpp
@@ -827,13 +827,11 @@ expr expr::bitreverse() const {
return res;
}
-expr expr::cttz() const {
+expr expr::cttz(const expr &val_zero) const {
C();
- auto nbits = bits();
auto srt = sort();
-
- auto cond = mkUInt(nbits, srt);
- for (int i = nbits - 1; i >= 0; --i) {
+ auto cond = val_zero;
+ for (int i = bits() - 1; i >= 0; --i) {
cond = mkIf(extract(i, i) == 1u, mkUInt(i, srt), cond);
}

MODIFY
smt/expr.h
smt/expr.h
@@ -186,7 +186,7 @@ public:
expr log2(unsigned bw_output) const;
expr bswap() const;
expr bitreverse() const;
- expr cttz() const;
+ expr cttz(const expr &val_zero) const;
expr ctlz() const;
expr ctpop() const;

ADD
tests/alive-tv/ffs-2.srctgt.ll
+target triple = "x86_64-apple-macosx10.15.0"
+
+define i32 @src() {
+ ret i32 4
+}
+
+define i32 @tgt() {
+ %v = call i32 @ffs(i32 40)
+ ret i32 %v
+}
+
+declare i32 @ffs(i32)

ADD
tests/alive-tv/ffs-3.srctgt.ll
+target triple = "x86_64-apple-macosx10.15.0"
+
+define i32 @src() {
+ %v = call i32 @ffs(i32 10)
+ ret i32 %v
+}
+
+define i32 @tgt() {
+ ret i32 3
+}
+
+declare i32 @ffs(i32)
+
+; ERROR: Value mismatch

ADD
tests/alive-tv/ffs-4.srctgt.ll
+target triple = "x86_64-apple-macosx10.15.0"
+
+define i32 @src() {
+ %v = call i32 @ffs(i32 2147483648)
+ ret i32 %v
+}
+
+define i32 @tgt() {
+ ret i32 32
+}
+
+declare i32 @ffs(i32)

ADD
tests/alive-tv/ffs.srctgt.ll
+target triple = "x86_64-apple-macosx10.15.0"
+
+define i32 @src() {
+ ret i32 0
+}
+
+define i32 @tgt() {
+ %v = call i32 @ffs(i32 0)
+ ret i32 %v
+}
+
+declare i32 @ffs(i32)

ADD
tests/alive-tv/ffsl.srctgt.ll
+target triple = "x86_64-apple-macosx10.15.0"
+
+define i32 @src() {
+ ret i32 64
+}
+
+define i32 @tgt() {
+ %v = call i32 @ffsl(i64 9223372036854775808)
+ ret i32 %v
+}
+
+declare i32 @ffsl(i64)

ADD
tests/alive-tv/ffsll-2.srctgt.ll
+target triple = "x86_64-apple-macosx10.15.0"
+
+define i32 @src() {
+ ret i32 0
+}
+
+define i32 @tgt() {
+ %v = call i32 @ffsll(i64 0)
+ ret i32 %v
+}
+
+declare i32 @ffsll(i64)

ADD
tests/alive-tv/ffsll.srctgt.ll
+target triple = "x86_64-apple-macosx10.15.0"
+
+define i32 @src() {
+ ret i32 64
+}
+
+define i32 @tgt() {
+ %v = call i32 @ffsll(i64 9223372036854775808)
+ ret i32 %v
+}
+
+declare i32 @ffsll(i64)

ADD
tests/unit/ffs.opt
+Name: constant
+%r = ffs i32 32
+ =>
+%r = 6
+
+Name: zero
+%r = ffs i32 0
+ =>
+%r = 0
+
+Name: var
+%k = shl i32 1, %x
+%r = ffs i32 %k
+ =>
+%r = add i32 1, %x

MODIFY
tools/alive_lexer.re
tools/alive_lexer.re
@@ -251,6 +251,7 @@ space+ {
"cttz" { return CTTZ; }
"ctlz" { return CTLZ; }
"ctpop" { return CTPOP; }
+"ffs" { return FFS; }
"extractvalue" { return EXTRACTVALUE; }
"insertvalue" { return INSERTVALUE; }
"sadd_overflow" { return SADD_OVERFLOW; }

MODIFY
tools/alive_parser.cpp
tools/alive_parser.cpp
@@ -766,6 +766,7 @@ static unique_ptr<Instr> parse_unaryop(string_view name, token op_token) {
case BSWAP: op = UnaryOp::BSwap; break;
case CTPOP: op = UnaryOp::Ctpop; break;
case FNEG: op = UnaryOp::FNeg; break;
+ case FFS: op = UnaryOp::FFS; break;
default:
UNREACHABLE();
}
@@ -1117,6 +1118,7 @@ static unique_ptr<Instr> parse_instr(string_view name) {
case BITREVERSE:
case BSWAP:
case CTPOP:
+ case FFS:
case FNEG:
return parse_unaryop(name, t);
case REDUCE_ADD:

MODIFY
tools/tokens.h
tools/tokens.h
@@ -49,6 +49,7 @@ TOKEN(REDUCE_SMAX)
TOKEN(REDUCE_SMIN)
TOKEN(REDUCE_UMAX)
TOKEN(REDUCE_UMIN)
+TOKEN(FFS)
TOKEN(FP_NUM)
TOKEN(FPEXT)
TOKEN(FPTOSI)

Add ffs/ffsl/ffsll (#485)