From 2e2538ccb85a39bfe6364d2e7a863e04d6ece9c5 Mon Sep 17 00:00:00 2001 From: Nicolas Williams Date: Sun, 27 Jul 2014 17:33:22 -0500 Subject: [PATCH] Fold constants (fix #504) --- compile.c | 20 +++++++++++++++++++- compile.h | 5 +++++ parser.y | 43 +++++++++++++++++++++++++++++++++++++++++++ tests/run | 53 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 120 insertions(+), 1 deletion(-) diff --git a/compile.c b/compile.c index 0b0208e..03d03c3 100644 --- a/compile.c +++ b/compile.c @@ -97,7 +97,7 @@ static block inst_block(inst* i) { return b; } -static int block_is_single(block b) { +int block_is_single(block b) { return b.first && b.first == b.last; } @@ -131,6 +131,10 @@ block gen_noop() { return b; } +int block_is_noop(block b) { + return (b.first == 0 && b.last == 0); +} + block gen_op_simple(opcode op) { assert(opcode_describe(op)->length == 1); return inst_block(inst_new(op)); @@ -144,6 +148,20 @@ block gen_const(jv constant) { return inst_block(i); } +int block_is_const(block b) { + return (block_is_single(b) && b.first->op == LOADK); +} + +jv_kind block_const_kind(block b) { + assert(block_is_const(b)); + return jv_get_kind(b.first->imm.constant); +} + +jv block_const(block b) { + assert(block_is_const(b)); + return jv_copy(b.first->imm.constant); +} + block gen_op_target(opcode op, block target) { assert(opcode_describe(op)->flags & OP_HAS_BRANCH); assert(target.last); diff --git a/compile.h b/compile.h index aba6a4d..a487c14 100644 --- a/compile.h +++ b/compile.h @@ -17,8 +17,12 @@ typedef struct block { block gen_location(location, struct locfile*, block); block gen_noop(); +int block_is_noop(block b); block gen_op_simple(opcode op); block gen_const(jv constant); +int block_is_const(block b); +jv_kind block_const_kind(block b); +jv block_const(block b); block gen_op_target(opcode op, block target); block gen_op_unbound(opcode op, const char* name); block gen_op_bound(opcode op, block binder); @@ -52,6 +56,7 @@ int block_has_only_binders_and_imports(block, int bindflags); int block_has_only_binders(block, int bindflags); int block_has_main(block); int block_is_funcdef(block b); +int block_is_single(block b); block block_bind(block binder, block body, int bindflags); block block_bind_library(block binder, block body, int bindflags, const char* libname); block block_bind_referenced(block binder, block body, int bindflags); diff --git a/parser.y b/parser.y index 4b4ad24..0117e1a 100644 --- a/parser.y +++ b/parser.y @@ -162,7 +162,50 @@ static block gen_slice_index(block obj, block start, block end, opcode idx_op) { return BLOCK(key, obj, gen_op_simple(idx_op)); } +static block constant_fold(block a, block b, int op) { + if (!block_is_single(a) || !block_is_const(a) || + !block_is_single(b) || !block_is_const(b)) + return gen_noop(); + if (block_const_kind(a) != block_const_kind(b)) + return gen_noop(); + + jv res = jv_invalid(); + + if (block_const_kind(a) == JV_KIND_NUMBER) { + double na = jv_number_value(block_const(a)); + double nb = jv_number_value(block_const(b)); + switch (op) { + case '+': res = jv_number(na + nb); break; + case '-': res = jv_number(na - nb); break; + case '*': res = jv_number(na * nb); break; + case '/': res = jv_number(na / nb); break; + case EQ: res = (na == nb ? jv_true() : jv_false()); break; + case NEQ: res = (na != nb ? jv_true() : jv_false()); break; + case '<': res = (na < nb ? jv_true() : jv_false()); break; + case '>': res = (na > nb ? jv_true() : jv_false()); break; + case LESSEQ: res = (na <= nb ? jv_true() : jv_false()); break; + case GREATEREQ: res = (na >= nb ? jv_true() : jv_false()); break; + default: break; + } + } else if (op == '+' && block_const_kind(a) == JV_KIND_STRING) { + res = jv_string_concat(block_const(a), block_const(b)); + } else { + return gen_noop(); + } + + if (jv_get_kind(res) == JV_KIND_INVALID) + return gen_noop(); + + block_free(a); + block_free(b); + return gen_const(res); +} + static block gen_binop(block a, block b, int op) { + block folded = constant_fold(a, b, op); + if (!block_is_noop(folded)) + return folded; + const char* funcname = 0; switch (op) { case '+': funcname = "_plus"; break; diff --git a/tests/run b/tests/run index a7ef7df..923478c 100755 --- a/tests/run +++ b/tests/run @@ -20,6 +20,59 @@ if [ -z "$d" ]; then exit 0 fi +## Test constant folding + +# String constant folding (addition only) +n=`$VALGRIND $Q ./jq -n --debug-dump-disasm '"foo"' | wc -l` +if [ $n -ne 5 ]; then + echo "Constant expression folding for strings didn't work" + exit 1 +fi + +# Numeric constant folding (not all ops yet) +n=`$VALGRIND $Q ./jq -n --debug-dump-disasm '1+1' | wc -l` +if [ $n -ne 5 ]; then + echo "Constant expression folding for strings didn't work" + exit 1 +fi +n=`$VALGRIND $Q ./jq -n --debug-dump-disasm '1-1' | wc -l` +if [ $n -ne 5 ]; then + echo "Constant expression folding for strings didn't work" + exit 1 +fi +n=`$VALGRIND $Q ./jq -n --debug-dump-disasm '2*3' | wc -l` +if [ $n -ne 5 ]; then + echo "Constant expression folding for strings didn't work" + exit 1 +fi +n=`$VALGRIND $Q ./jq -n --debug-dump-disasm '9/3' | wc -l` +if [ $n -ne 5 ]; then + echo "Constant expression folding for strings didn't work" + exit 1 +fi +n=`$VALGRIND $Q ./jq -n --debug-dump-disasm '9==3' | wc -l` +if [ $n -ne 5 ]; then + echo "Constant expression folding for strings didn't work" + exit 1 +fi +n=`$VALGRIND $Q ./jq -n --debug-dump-disasm '9!=3' | wc -l` +if [ $n -ne 5 ]; then + echo "Constant expression folding for strings didn't work" + exit 1 +fi +n=`$VALGRIND $Q ./jq -n --debug-dump-disasm '9<=3' | wc -l` +if [ $n -ne 5 ]; then + echo "Constant expression folding for strings didn't work" + exit 1 +fi +n=`$VALGRIND $Q ./jq -n --debug-dump-disasm '9>=3' | wc -l` +if [ $n -ne 5 ]; then + echo "Constant expression folding for strings didn't work" + exit 1 +fi + +## Test library/module system + cat > "$d/.jq" <