diff options
author | Muh Muhten <muh.muhten@gmail.com> | 2019-02-20 01:48:56 -0500 |
---|---|---|
committer | Nico Williams <nico@cryptonector.com> | 2019-02-20 19:43:13 -0600 |
commit | e843a4fdf9f6f446f5ddebf2c108cb7d4dda867b (patch) | |
tree | 55ad29089dbf9146706690eda70ee0753c925a1d | |
parent | b2b0bd37a13c449806acae3312169edc297ab1d9 (diff) |
Make builtin binding fast again by binding only referenced symbols
Avoid doing the internal binding of top-level symbols in the parser,
leaving that work to be done in a post-processing step. For builtins,
this lets us do a reference-aware bind step (block_bind_incremental)
*after* generating builtins/0.
Libraries are a bit trickier since they may be bound multiple times, so
instead of thinking through the implications I added (block_bind_self)
to resolve all internal symbols immediately.
-rw-r--r-- | src/builtin.c | 4 | ||||
-rw-r--r-- | src/compile.c | 51 | ||||
-rw-r--r-- | src/compile.h | 3 | ||||
-rw-r--r-- | src/linker.c | 1 | ||||
-rw-r--r-- | src/parser.c | 2 | ||||
-rw-r--r-- | src/parser.y | 2 |
6 files changed, 54 insertions, 9 deletions
diff --git a/src/builtin.c b/src/builtin.c index 5a1be9e5..13f0717d 100644 --- a/src/builtin.c +++ b/src/builtin.c @@ -1743,7 +1743,7 @@ static block bind_bytecoded_builtins(block b) { BLOCK(gen_param("start"), gen_param("end")), range)); } - return block_bind(builtins, b, OP_IS_CALL_PSEUDO); + return BLOCK(builtins, b); } static const char jq_builtins[] = @@ -1793,7 +1793,7 @@ int builtins_bind(jq_state *jq, block* bb) { builtins = gen_cbinding(function_list, sizeof(function_list)/sizeof(function_list[0]), builtins); builtins = gen_builtin_list(builtins); - *bb = block_bind(builtins, *bb, OP_IS_CALL_PSEUDO); + *bb = block_bind_incremental(builtins, *bb, OP_IS_CALL_PSEUDO); *bb = block_drop_unreferenced(*bb); return nerrors; } diff --git a/src/compile.c b/src/compile.c index 3d3132f7..75929aa9 100644 --- a/src/compile.c +++ b/src/compile.c @@ -222,8 +222,9 @@ block gen_op_unbound(opcode op, const char* name) { block gen_op_var_fresh(opcode op, const char* name) { assert(opcode_describe(op)->flags & OP_HAS_VARIABLE); - return block_bind(gen_op_unbound(op, name), - gen_noop(), OP_HAS_VARIABLE); + block b = gen_op_unbound(op, name); + b.first->bound_by = b.first; + return b; } block gen_op_bound(opcode op, block binder) { @@ -382,7 +383,7 @@ static int block_bind_each(block binder, block body, int bindflags) { return nrefs; } -block block_bind(block binder, block body, int bindflags) { +static block block_bind(block binder, block body, int bindflags) { block_bind_each(binder, body, bindflags); return block_join(binder, body); } @@ -434,6 +435,48 @@ block block_bind_referenced(block binder, block body, int bindflags) { return body; } +static inst* block_take_last(block* b) { + inst* i = b->last; + if (i == 0) + return 0; + if (i->prev) { + i->prev->next = i->next; + b->last = i->prev; + i->prev = 0; + } else { + b->first = 0; + b->last = 0; + } + return i; +} + +// Binds a sequence of binders, which *must not* alrady be bound to each other, +// to body, throwing away unreferenced defs +block block_bind_incremental(block binder, block body, int bindflags) { + assert(block_has_only_binders(binder, bindflags)); + bindflags |= OP_HAS_BINDING; + + inst* curr; + while ((curr = block_take_last(&binder))) { + body = block_bind_referenced(inst_block(curr), body, bindflags); + } + return body; +} + +block block_bind_self(block binder, int bindflags) { + assert(block_has_only_binders(binder, bindflags)); + bindflags |= OP_HAS_BINDING; + block body = gen_noop(); + + inst* curr; + while ((curr = block_take_last(&binder))) { + block b = inst_block(curr); + block_bind_subblock(b, body, bindflags, 0); + body = BLOCK(b, body); + } + return body; +} + static void block_mark_referenced(block body) { int saw_top = 0; for (inst* i = body.last; i; i = i->prev) { @@ -1074,7 +1117,7 @@ block gen_cbinding(const struct cfunction* cfunctions, int ncfunctions, block co i->imm.cfunc = &cfunctions[cfunc]; i->symbol = strdup(i->imm.cfunc->name); i->any_unbound = 0; - code = block_bind(inst_block(i), code, OP_IS_CALL_PSEUDO); + code = BLOCK(inst_block(i), code); } return code; } diff --git a/src/compile.h b/src/compile.h index 27206125..8ea4d6fc 100644 --- a/src/compile.h +++ b/src/compile.h @@ -72,9 +72,10 @@ 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); +block block_bind_incremental(block binder, block body, int bindflags); +block block_bind_self(block binder, int bindflags); block block_drop_unreferenced(block body); jv block_take_imports(block* body); diff --git a/src/linker.c b/src/linker.c index 5c3845f4..aa1ff137 100644 --- a/src/linker.c +++ b/src/linker.c @@ -336,6 +336,7 @@ static int load_library(jq_state *jq, jv lib_path, int is_data, int raw, const c jv_string(dirname(lib_origin)), &program, lib_state); free(lib_origin); + program = block_bind_self(program, OP_IS_CALL_PSEUDO); } } state_idx = lib_state->ct++; diff --git a/src/parser.c b/src/parser.c index 3b8cc7ae..f82bdd1a 100644 --- a/src/parser.c +++ b/src/parser.c @@ -2423,7 +2423,7 @@ yyreduce: case 9: #line 333 "src/parser.y" /* yacc.c:1646 */ { - (yyval.blk) = block_bind((yyvsp[-1].blk), (yyvsp[0].blk), OP_IS_CALL_PSEUDO); + (yyval.blk) = block_join((yyvsp[-1].blk), (yyvsp[0].blk)); } #line 2429 "src/parser.c" /* yacc.c:1646 */ break; diff --git a/src/parser.y b/src/parser.y index 2fb81871..946a9582 100644 --- a/src/parser.y +++ b/src/parser.y @@ -331,7 +331,7 @@ FuncDefs: $$ = gen_noop(); } | FuncDef FuncDefs { - $$ = block_bind($1, $2, OP_IS_CALL_PSEUDO); + $$ = block_join($1, $2); } Exp: |