scmno****@osdn*****
scmno****@osdn*****
Thu Jun 28 05:25:46 JST 2018
changeset 411c30c09598 in quipu/quipu details: http://hg.osdn.jp/view/quipu/quipu?cmd=changeset;node=411c30c09598 user: Agustina Arzille <avarz****@riseu*****> date: Wed Jun 27 17:25:37 2018 -0300 description: Implement faster 'let' form expansion diffstat: bytecode.cpp | 123 ++++++++++++------------ bytecode.h | 1 + compiler.cpp | 285 +++++++++++++++++++++++++++++++++++++-------------------- eval.cpp | 45 +++++--- function.cpp | 7 +- interp.cpp | 16 ++- utils/opnames | 1 + 7 files changed, 293 insertions(+), 185 deletions(-) diffs (truncated from 631 to 300 lines): diff -r 1deed614687f -r 411c30c09598 bytecode.cpp --- a/bytecode.cpp Mon Jun 25 17:11:18 2018 -0300 +++ b/bytecode.cpp Wed Jun 27 17:25:37 2018 -0300 @@ -18,9 +18,9 @@ "nop\0dup\0pop\0ret\0is\0not\0cons\0list\0car\0cdr\0cadr\0nputcar\0" "nputcdr\0apply\0tapply\0loadt\0loadnil\0load0\0load1\0loadi8\0loada0\0" "loada1\0loadc00\0loadc01\0loadap0\0loadap1\0mkcont\0captenv\0closure\0" - "tryend\0raise\0raise2\0ldcaller\0argc\0argc.l\0vargc\0vargc.l\0jmp\0" - "jmp.l\0brt\0brt.l\0brn\0brn.l\0brneq\0brneq.l\0tcall\0tcall.l\0call\0" - "call.l\0setc\0setc.l\0seta\0seta.l\0setap\0setap.l\0setg\0setg.l\0" + "tryend\0raise\0raise2\0ldcaller\0prepfrm\0argc\0argc.l\0vargc\0vargc.l\0" + "jmp\0jmp.l\0brt\0brt.l\0brn\0brn.l\0brneq\0brneq.l\0tcall\0tcall.l\0" + "call\0call.l\0setc\0setc.l\0seta\0seta.l\0setap\0setap.l\0setg\0setg.l\0" "loadc\0loadc.l\0loada\0loada.l\0loadap\0loadap.l\0loadg\0loadg.l\0" "loadv\0loadv.l\0loadx\0loadx.l\0bind\0bind.l\0recur\0recur.l\0trecur\0" "trecur.l\0mkframe\0mkframe.l\0unwind\0unwind.l\0trybegin\0trybegin.l\0" @@ -72,64 +72,65 @@ { 184, 0 }, // raise { 190, 0 }, // raise2 { 197, 0 }, // ldcaller - { 206, 1 }, // argc - { 211, 1 | BC_LONG_FORM }, // argc.l - { 218, 1 }, // vargc - { 224, 1 | BC_LONG_FORM }, // vargc.l - { 232, 1 | BC_BRANCH_FORM }, // jmp - { 236, 1 | BC_BRANCH_FORM | BC_LONG_FORM }, // jmp.l - { 242, 1 | BC_BRANCH_FORM }, // brt - { 246, 1 | BC_BRANCH_FORM | BC_LONG_FORM }, // brt.l - { 252, 1 | BC_BRANCH_FORM }, // brn - { 256, 1 | BC_BRANCH_FORM | BC_LONG_FORM }, // brn.l - { 262, 1 | BC_BRANCH_FORM }, // brneq - { 268, 1 | BC_BRANCH_FORM | BC_LONG_FORM }, // brneq.l - { 276, 1 | BC_CALL_FORM }, // tcall - { 282, 1 | BC_CALL_FORM | BC_LONG_FORM }, // tcall.l - { 290, 1 | BC_CALL_FORM }, // call - { 295, 1 | BC_CALL_FORM | BC_LONG_FORM }, // call.l - { 302, 2 }, // setc - { 307, 2 | BC_LONG_FORM }, // setc.l - { 314, 1 }, // seta - { 319, 1 | BC_LONG_FORM }, // seta.l - { 326, 2 }, // setap - { 332, 2 | BC_LONG_FORM }, // setap.l - { 340, 1 }, // setg - { 345, 1 | BC_LONG_FORM }, // setg.l - { 352, 2 | BC_LOAD_FORM | BC_PURE_FORM }, // loadc - { 358, 2 | BC_LOAD_FORM | BC_PURE_FORM | BC_LONG_FORM }, // loadc.l - { 366, 1 | BC_LOAD_FORM | BC_PURE_FORM }, // loada - { 372, 1 | BC_LOAD_FORM | BC_PURE_FORM | BC_LONG_FORM }, // loada.l - { 380, 2 | BC_LOAD_FORM | BC_PURE_FORM }, // loadap - { 387, 2 | BC_LOAD_FORM | BC_PURE_FORM | BC_LONG_FORM }, // loadap.l - { 396, 1 | BC_LOAD_FORM }, // loadg - { 402, 1 | BC_LOAD_FORM | BC_LONG_FORM }, // loadg.l - { 410, 1 | BC_LOAD_FORM | BC_PURE_FORM }, // loadv - { 416, 1 | BC_LOAD_FORM | BC_PURE_FORM | BC_LONG_FORM }, // loadv.l - { 424, 1 | BC_LOAD_FORM }, // loadx - { 430, 1 | BC_LOAD_FORM | BC_LONG_FORM }, // loadx.l - { 438, 1 }, // bind - { 443, 1 | BC_LONG_FORM }, // bind.l - { 450, 1 | BC_CALL_FORM }, // recur - { 456, 1 | BC_CALL_FORM | BC_LONG_FORM }, // recur.l - { 464, 1 | BC_CALL_FORM }, // trecur - { 471, 1 | BC_CALL_FORM | BC_LONG_FORM }, // trecur.l - { 480, 1 }, // mkframe - { 488, 1 | BC_LONG_FORM }, // mkframe.l - { 498, 1 }, // unwind - { 505, 1 | BC_LONG_FORM }, // unwind.l - { 514, 1 | BC_BRANCH_FORM }, // trybegin - { 523, 1 | BC_BRANCH_FORM | BC_LONG_FORM }, // trybegin.l - { 534, 1 }, // setapop - { 542, 1 | BC_LONG_FORM }, // setapop.l - { 552, 1 | BC_BRANCH_FORM }, // irtjmp - { 559, 1 | BC_BRANCH_FORM | BC_LONG_FORM }, // irtjmp.l - { 568, 2 }, // optargs - { 576, 2 | BC_LONG_FORM }, // optargs.l - { 586, 1 }, // brbound - { 594, 1 | BC_LONG_FORM }, // brbound.l - { 604, 3 }, // kwargs - { 611, 3 | BC_LONG_FORM }, // kwargs.l + { 206, 0 }, // prepfrm + { 214, 1 }, // argc + { 219, 1 | BC_LONG_FORM }, // argc.l + { 226, 1 }, // vargc + { 232, 1 | BC_LONG_FORM }, // vargc.l + { 240, 1 | BC_BRANCH_FORM }, // jmp + { 244, 1 | BC_BRANCH_FORM | BC_LONG_FORM }, // jmp.l + { 250, 1 | BC_BRANCH_FORM }, // brt + { 254, 1 | BC_BRANCH_FORM | BC_LONG_FORM }, // brt.l + { 260, 1 | BC_BRANCH_FORM }, // brn + { 264, 1 | BC_BRANCH_FORM | BC_LONG_FORM }, // brn.l + { 270, 1 | BC_BRANCH_FORM }, // brneq + { 276, 1 | BC_BRANCH_FORM | BC_LONG_FORM }, // brneq.l + { 284, 1 | BC_CALL_FORM }, // tcall + { 290, 1 | BC_CALL_FORM | BC_LONG_FORM }, // tcall.l + { 298, 1 | BC_CALL_FORM }, // call + { 303, 1 | BC_CALL_FORM | BC_LONG_FORM }, // call.l + { 310, 2 }, // setc + { 315, 2 | BC_LONG_FORM }, // setc.l + { 322, 1 }, // seta + { 327, 1 | BC_LONG_FORM }, // seta.l + { 334, 2 }, // setap + { 340, 2 | BC_LONG_FORM }, // setap.l + { 348, 1 }, // setg + { 353, 1 | BC_LONG_FORM }, // setg.l + { 360, 2 | BC_LOAD_FORM | BC_PURE_FORM }, // loadc + { 366, 2 | BC_LOAD_FORM | BC_PURE_FORM | BC_LONG_FORM }, // loadc.l + { 374, 1 | BC_LOAD_FORM | BC_PURE_FORM }, // loada + { 380, 1 | BC_LOAD_FORM | BC_PURE_FORM | BC_LONG_FORM }, // loada.l + { 388, 2 | BC_LOAD_FORM | BC_PURE_FORM }, // loadap + { 395, 2 | BC_LOAD_FORM | BC_PURE_FORM | BC_LONG_FORM }, // loadap.l + { 404, 1 | BC_LOAD_FORM }, // loadg + { 410, 1 | BC_LOAD_FORM | BC_LONG_FORM }, // loadg.l + { 418, 1 | BC_LOAD_FORM | BC_PURE_FORM }, // loadv + { 424, 1 | BC_LOAD_FORM | BC_PURE_FORM | BC_LONG_FORM }, // loadv.l + { 432, 1 | BC_LOAD_FORM }, // loadx + { 438, 1 | BC_LOAD_FORM | BC_LONG_FORM }, // loadx.l + { 446, 1 }, // bind + { 451, 1 | BC_LONG_FORM }, // bind.l + { 458, 1 | BC_CALL_FORM }, // recur + { 464, 1 | BC_CALL_FORM | BC_LONG_FORM }, // recur.l + { 472, 1 | BC_CALL_FORM }, // trecur + { 479, 1 | BC_CALL_FORM | BC_LONG_FORM }, // trecur.l + { 488, 1 }, // mkframe + { 496, 1 | BC_LONG_FORM }, // mkframe.l + { 506, 1 }, // unwind + { 513, 1 | BC_LONG_FORM }, // unwind.l + { 522, 1 | BC_BRANCH_FORM }, // trybegin + { 531, 1 | BC_BRANCH_FORM | BC_LONG_FORM }, // trybegin.l + { 542, 1 }, // setapop + { 550, 1 | BC_LONG_FORM }, // setapop.l + { 560, 1 | BC_BRANCH_FORM }, // irtjmp + { 567, 1 | BC_BRANCH_FORM | BC_LONG_FORM }, // irtjmp.l + { 576, 2 }, // optargs + { 584, 2 | BC_LONG_FORM }, // optargs.l + { 594, 1 }, // brbound + { 602, 1 | BC_LONG_FORM }, // brbound.l + { 612, 3 }, // kwargs + { 619, 3 | BC_LONG_FORM }, // kwargs.l { 0, 0 } }; diff -r 1deed614687f -r 411c30c09598 bytecode.h --- a/bytecode.h Mon Jun 25 17:11:18 2018 -0300 +++ b/bytecode.h Wed Jun 27 17:25:37 2018 -0300 @@ -40,6 +40,7 @@ OP_RAISE, OP_RAISE2, OP_LDCALLER, + OP_PREPFRM, // Opcodes with long forms. OP_ARGC, OP_ARGCL, diff -r 1deed614687f -r 411c30c09598 compiler.cpp --- a/compiler.cpp Mon Jun 25 17:11:18 2018 -0300 +++ b/compiler.cpp Wed Jun 27 17:25:37 2018 -0300 @@ -1880,6 +1880,181 @@ return (as_symbol(obj)->flagged_p (symbol::special_flag)); } +static bool +handle_let_bindings (bc_emitter& bc, object& bindings, + int& nargs, cons *sbp, object& expr) +{ + bool dbind = false; + nargs = 0; + + if (!xcons_p (bindings)) + { + if (!nksymbol_p (bindings)) + bc.interp->raise2 ("arg-error", io_sprintf (bc.interp, + "let bindings must be a symbol or cons, not %Q", bindings)); + else if (!xcons_p (xcdr (expr))) + bc.interp->raise2 ("arg-error", io_sprintf (bc.interp, + "let: got a dotted list in the body: %Q", expr)); + else if (xcdr (expr) == NIL) + bc.interp->raise2 ("arg-error", "missing body in let"); + + dbind = special_symbol_p (bindings); + + sbp[0].car = bindings; + sbp[0].cdr = sbp[1].as_obj (); + + sbp[1].car = xcadr (expr); + sbp[1].cdr = NIL; + + bindings = sbp[0].as_obj (); + expr = xcdr (expr); + nargs = 1; + } + else + for (object tmp = bindings; tmp != NIL; ++nargs) + { + if (!nksymbol_p (xcar (tmp))) + bc.interp->raise2 ("arg-error", io_sprintf (bc.interp, + "let bindings must be symbols, not %Q", xcar (tmp))); + + dbind = dbind || special_symbol_p (xcar (tmp)); + + if (xcdr (tmp) == NIL) + bc.interp->raise2 ("arg-error", io_sprintf (bc.interp, + "let bindings must come in pairs, got: %Q", bindings)); + else if (!xcons_p (xcdr (tmp)) || !xcons_p (tmp = xcddr (tmp))) + bc.interp->raise2 ("arg-error", io_sprintf (bc.interp, + "let bindings must not come in a dotted list: %Q", bindings)); + } + + return (dbind); +} + +static void +let_expand_seq (bc_emitter& bc, object bindings, object env, + cons *ctvs, int& nlex, int& nctv, int nargs) +{ + cons *syms = as_cons (xcar (env)); + object *sep = &syms->cdr, *cep = &ctvs->cdr; + + for (bool first = true; bindings != NIL; bindings = xcddr (bindings)) + { + *sep = *cep = NIL; + + if (eval_ctv (bc, bindings, ctvs, nctv, cep) >= 0) + /* This is a compile-time (i.e: macro or alias) definition, + * rather than a lexical or dynamic binding. */ + continue; + else if (first) + { /* A 'let' form must be preceeded by a stack frame, and (optionally) + * an environment capture in case the body refers to a variable + * from the outer frame. Here we emit a few placeholders that we'll + * eventually patch or remove. */ + if (!(bc.rflags & bc_emitter::flg_emitted_captenv)) + { + bc.code.push_back (OPX_(FAKECAPT)); + bc.rflags |= bc_emitter::flg_emitted_captenv; + } + + bc.emit (OPX_(MKFRAME), intobj (nargs)); + ++bc.cur_f().stkdisp; + bc.push_f (); + first = false; + } + + object prev = NIL, evx = xcadr (bindings); + if (nlex > 0) + { + prev = syms[nlex - 1].cdr; + syms[nlex - 1].cdr = NIL; + } + + bc.compile_in (env, false, evx); + if (nlex > 0) + syms[nlex - 1].cdr = prev; + + if (special_symbol_p (xcar (bindings))) + { + bc.emit (OPX_(BIND), xcar (bindings)); + continue; + } + else if (!(bc.rflags & bc_emitter::flg_captured)) + bc.emit (OPX_(SETAPOP), intobj (nlex + bc.cur_f().acc)); + else + { + bc.emit (OPX_(SETAP), + intobj (bc.cur_f().acc + nargs), intobj (nlex)); + bc.emit (OPX_(POP)); + } + + ++bc.cur_f().nargs; + syms[nlex].car = xcar (bindings); + syms[nlex].cdr = syms[nlex + 1].as_obj (); + sep = &syms[++nlex].cdr; + } +} + +static bool +let_expand_fast (bc_emitter& bc, object bindings, object env, + cons *ctvs, int& nlex, int& nctv, int nargs) +{ + cons *syms = as_cons (xcar (env)); + object *sep = &syms->cdr, *cep = &ctvs->cdr; + size_t psize = bc.code.size (); + + for (bool first = true; bindings != NIL; bindings = xcddr (bindings)) + { + *cep = *sep = NIL; + + if (eval_ctv (bc, bindings, ctvs, nctv, cep) >= 0) + continue; + else if (first) + { + bc.emit (OPX_(PREPFRM)); + ++bc.cur_f().stkdisp; + bc.push_f (); + bc.cur_f().stkdisp -= interpreter::frame_size; + first = false; + } + + object prev = NIL, evx = xcadr (bindings); + if (nlex > 0) + { + prev = syms[nlex - 1].cdr; + syms[nlex - 1].cdr = NIL;
Fork