From 80d9b09f351c7a9be557116e9c79ae11e9b3f032 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Wed, 13 Sep 2017 16:50:08 -0300 Subject: jumps do not close upvalues (to be faster and simpler); explicit instruction to close upvalues; command 'break' not handled like a 'goto' (to optimize removal of uneeded 'close' instructions) --- lcode.c | 51 ++++++++++++++++++++----- lcode.h | 6 ++- lopcodes.c | 6 ++- lopcodes.h | 5 ++- lparser.c | 127 +++++++++++++++++++++++++++++++++++++++---------------------- lvm.c | 11 +++--- 6 files changed, 139 insertions(+), 67 deletions(-) diff --git a/lcode.c b/lcode.c index 169c439d..1edf08aa 100644 --- a/lcode.c +++ b/lcode.c @@ -1,5 +1,5 @@ /* -** $Id: lcode.c,v 2.120 2017/06/27 11:35:31 roberto Exp roberto $ +** $Id: lcode.c,v 2.121 2017/06/29 15:06:44 roberto Exp roberto $ ** Code generator for Lua ** See Copyright Notice in lua.h */ @@ -272,20 +272,51 @@ void luaK_patchlist (FuncState *fs, int list, int target) { /* -** Path all jumps in 'list' to close upvalues up to given 'level' -** (The assertion checks that jumps either were closing nothing -** or were closing higher levels, from inner blocks.) +** Check whether some jump in given list needs a close instruction. */ -void luaK_patchclose (FuncState *fs, int list, int level) { - level++; /* argument is +1 to reserve 0 as non-op */ +int luaK_needclose (FuncState *fs, int list) { for (; list != NO_JUMP; list = getjump(fs, list)) { - lua_assert(GET_OPCODE(fs->f->code[list]) == OP_JMP && - (GETARG_A(fs->f->code[list]) == 0 || - GETARG_A(fs->f->code[list]) >= level)); - SETARG_A(fs->f->code[list], level); + if (GETARG_A(fs->f->code[list])) /* needs close? */ + return 1; + } + return 0; +} + + +/* +** Correct a jump list to jump to 'target'. If 'hasclose' is true, +** 'target' contains an OP_CLOSE instruction (see first assert). +** Only jumps with the A arg true need that close; other jumps +** avoid it jumping to the next instruction. +*/ +void luaK_patchgoto (FuncState *fs, int list, int target, int hasclose) { + lua_assert(!hasclose || GET_OPCODE(fs->f->code[target]) == OP_CLOSE); + while (list != NO_JUMP) { + int next = getjump(fs, list); + lua_assert(!GETARG_A(fs->f->code[list]) || hasclose); + patchtestreg(fs, list, NO_REG); /* do not generate values */ + if (!hasclose || GETARG_A(fs->f->code[list])) + fixjump(fs, list, target); + else /* there is a CLOSE instruction but jump does not need it */ + fixjump(fs, list, target + 1); /* avoid CLOSE instruction */ + list = next; } } + +/* +** Mark (using the A arg) all jumps in 'list' to close upvalues. Mark +** will instruct 'luaK_patchgoto' to make these jumps go to OP_CLOSE +** instructions. +*/ +void luaK_patchclose (FuncState *fs, int list) { + for (; list != NO_JUMP; list = getjump(fs, list)) { + lua_assert(GET_OPCODE(fs->f->code[list]) == OP_JMP); + SETARG_A(fs->f->code[list], 1); + } +} + + #if !defined(MAXIWTHABS) #define MAXIWTHABS 120 #endif diff --git a/lcode.h b/lcode.h index e7ff3522..70953559 100644 --- a/lcode.h +++ b/lcode.h @@ -1,5 +1,5 @@ /* -** $Id: lcode.h,v 1.64 2016/01/05 16:22:37 roberto Exp roberto $ +** $Id: lcode.h,v 1.65 2017/04/20 19:53:55 roberto Exp roberto $ ** Code generator for Lua ** See Copyright Notice in lua.h */ @@ -73,8 +73,10 @@ LUAI_FUNC void luaK_setoneret (FuncState *fs, expdesc *e); LUAI_FUNC int luaK_jump (FuncState *fs); LUAI_FUNC void luaK_ret (FuncState *fs, int first, int nret); LUAI_FUNC void luaK_patchlist (FuncState *fs, int list, int target); +void luaK_patchgoto (FuncState *fs, int list, int target, int hasclose); LUAI_FUNC void luaK_patchtohere (FuncState *fs, int list); -LUAI_FUNC void luaK_patchclose (FuncState *fs, int list, int level); +LUAI_FUNC void luaK_patchclose (FuncState *fs, int list); +LUAI_FUNC int luaK_needclose (FuncState *fs, int list); LUAI_FUNC void luaK_concat (FuncState *fs, int *l1, int l2); LUAI_FUNC int luaK_getlabel (FuncState *fs); LUAI_FUNC void luaK_prefix (FuncState *fs, UnOpr op, expdesc *v, int line); diff --git a/lopcodes.c b/lopcodes.c index 74195d42..a64c29ce 100644 --- a/lopcodes.c +++ b/lopcodes.c @@ -1,5 +1,5 @@ /* -** $Id: lopcodes.c,v 1.59 2017/06/29 15:38:41 roberto Exp roberto $ +** $Id: lopcodes.c,v 1.60 2017/08/14 18:33:14 roberto Exp roberto $ ** Opcodes for Lua virtual machine ** See Copyright Notice in lua.h */ @@ -54,6 +54,7 @@ LUAI_DDEF const char *const luaP_opnames[NUM_OPCODES+1] = { "NOT", "LEN", "CONCAT", + "CLOSE", "JMP", "EQ", "LT", @@ -115,7 +116,8 @@ LUAI_DDEF const lu_byte luaP_opmodes[NUM_OPCODES] = { ,opmode(0, 1, OpArgR, OpArgN, iABC) /* OP_NOT */ ,opmode(0, 1, OpArgR, OpArgN, iABC) /* OP_LEN */ ,opmode(0, 1, OpArgR, OpArgR, iABC) /* OP_CONCAT */ - ,opmode(0, 0, OpArgR, OpArgN, iAsBx) /* OP_JMP */ + ,opmode(0, 0, OpArgN, OpArgN, iABC) /* OP_CLOSE */ + ,opmode(0, 0, OpArgU, OpArgN, iAsBx) /* OP_JMP */ ,opmode(1, 0, OpArgK, OpArgK, iABC) /* OP_EQ */ ,opmode(1, 0, OpArgK, OpArgK, iABC) /* OP_LT */ ,opmode(1, 0, OpArgK, OpArgK, iABC) /* OP_LE */ diff --git a/lopcodes.h b/lopcodes.h index f35de02a..4dfe66ce 100644 --- a/lopcodes.h +++ b/lopcodes.h @@ -1,5 +1,5 @@ /* -** $Id: lopcodes.h,v 1.155 2017/06/29 15:38:41 roberto Exp roberto $ +** $Id: lopcodes.h,v 1.156 2017/08/14 18:33:14 roberto Exp roberto $ ** Opcodes for Lua virtual machine ** See Copyright Notice in lua.h */ @@ -217,7 +217,8 @@ OP_LEN,/* A B R(A) := length of R(B) */ OP_CONCAT,/* A B C R(A) := R(B).. ... ..R(C) */ -OP_JMP,/* A sBx pc+=sBx; if (A) close all upvalues >= R(A - 1) */ +OP_CLOSE,/* A close all upvalues >= R(A) */ +OP_JMP,/* sBx pc+=sBx */ OP_EQ,/* A B C if ((RK(B) == RK(C)) ~= A) then pc++ */ OP_LT,/* A B C if ((RK(B) < RK(C)) ~= A) then pc++ */ OP_LE,/* A B C if ((RK(B) <= RK(C)) ~= A) then pc++ */ diff --git a/lparser.c b/lparser.c index 2eb5581f..7fd62f50 100644 --- a/lparser.c +++ b/lparser.c @@ -1,5 +1,5 @@ /* -** $Id: lparser.c,v 2.163 2017/08/12 13:12:21 roberto Exp roberto $ +** $Id: lparser.c,v 2.164 2017/08/14 18:33:14 roberto Exp roberto $ ** Lua Parser ** See Copyright Notice in lua.h */ @@ -49,6 +49,8 @@ typedef struct BlockCnt { struct BlockCnt *previous; /* chain */ int firstlabel; /* index of first label in this block */ int firstgoto; /* index of first pending goto in this block */ + int brks; /* list of break jumps in this block */ + lu_byte brkcls; /* true if some 'break' needs to close upvalues */ lu_byte nactvar; /* # active locals outside the block */ lu_byte upval; /* true if some variable in the block is an upvalue */ lu_byte isloop; /* true if 'block' is a loop */ @@ -351,7 +353,7 @@ static void closegoto (LexState *ls, int g, Labeldesc *label) { getstr(gt->name), gt->line, getstr(vname)); semerror(ls, msg); } - luaK_patchlist(fs, gt->pc, label->pc); + luaK_patchgoto(fs, gt->pc, label->pc, 1); /* remove goto from pending list */ for (i = g; i < gl->n - 1; i++) gl->arr[i] = gl->arr[i + 1]; @@ -362,7 +364,7 @@ static void closegoto (LexState *ls, int g, Labeldesc *label) { /* ** try to close a goto with existing labels; this solves backward jumps */ -static int findlabel (LexState *ls, int g) { +static int solvelabel (LexState *ls, int g) { int i; BlockCnt *bl = ls->fs->bl; Dyndata *dyd = ls->dyd; @@ -373,7 +375,7 @@ static int findlabel (LexState *ls, int g) { if (eqstr(lb->name, gt->name)) { /* correct label? */ if (gt->nactvar > lb->nactvar && (bl->upval || dyd->label.n > bl->firstlabel)) - luaK_patchclose(ls->fs, gt->pc, lb->nactvar); + luaK_patchclose(ls->fs, gt->pc); closegoto(ls, g, lb); /* close it */ return 1; } @@ -400,12 +402,12 @@ static int newlabelentry (LexState *ls, Labellist *l, TString *name, ** check whether new label 'lb' matches any pending gotos in current ** block; solves forward jumps */ -static void findgotos (LexState *ls, Labeldesc *lb) { +static void solvegotos (LexState *ls, Labeldesc *lb) { Labellist *gl = &ls->dyd->gt; int i = ls->fs->bl->firstgoto; while (i < gl->n) { if (eqstr(gl->arr[i].name, lb->name)) - closegoto(ls, i, lb); + closegoto(ls, i, lb); /* will remove 'i' from the list */ else i++; } @@ -416,23 +418,32 @@ static void findgotos (LexState *ls, Labeldesc *lb) { ** export pending gotos to outer level, to check them against ** outer labels; if the block being exited has upvalues, and ** the goto exits the scope of any variable (which can be the -** upvalue), close those variables being exited. +** upvalue), close those variables being exited. Also export +** break list. */ static void movegotosout (FuncState *fs, BlockCnt *bl) { int i = bl->firstgoto; Labellist *gl = &fs->ls->dyd->gt; /* correct pending gotos to current block and try to close it with visible labels */ - while (i < gl->n) { + while (i < gl->n) { /* for each pending goto */ Labeldesc *gt = &gl->arr[i]; - if (gt->nactvar > bl->nactvar) { - if (bl->upval) - luaK_patchclose(fs, gt->pc, bl->nactvar); - gt->nactvar = bl->nactvar; + if (gt->nactvar > bl->nactvar) { /* leaving a variable scope? */ + if (bl->upval) /* variable may be an upvalue? */ + luaK_patchclose(fs, gt->pc); /* jump will need a close */ + gt->nactvar = bl->nactvar; /* update goto level */ } - if (!findlabel(fs->ls, i)) + if (!solvelabel(fs->ls, i)) i++; /* move to next one */ + /* else, 'solvelabel' removed current goto from the list + and 'i' now points to next one */ } + /* handles break list */ + if (bl->upval) /* exiting the scope of an upvalue? */ + luaK_patchclose(fs, bl->brks); /* breaks will need OP_CLOSE */ + /* move breaks to outer block */ + luaK_concat(fs, &bl->previous->brks, bl->brks); + bl->previous->brkcls |= bl->brkcls; } @@ -441,6 +452,8 @@ static void enterblock (FuncState *fs, BlockCnt *bl, lu_byte isloop) { bl->nactvar = fs->nactvar; bl->firstlabel = fs->ls->dyd->label.n; bl->firstgoto = fs->ls->dyd->gt.n; + bl->brks = NO_JUMP; + bl->brkcls = 0; bl->upval = 0; bl->previous = fs->bl; fs->bl = bl; @@ -449,22 +462,24 @@ static void enterblock (FuncState *fs, BlockCnt *bl, lu_byte isloop) { /* -** create a label named 'break' to resolve break statements +** Fix all breaks in block 'bl' to jump to the end of the block. */ -static void breaklabel (LexState *ls) { - TString *n = luaS_new(ls->L, "break"); - int l = newlabelentry(ls, &ls->dyd->label, n, 0, ls->fs->pc); - findgotos(ls, &ls->dyd->label.arr[l]); +static void fixbreaks (FuncState *fs, BlockCnt *bl) { + int target = fs->pc; + if (bl->brkcls) /* does the block need to close upvalues? */ + luaK_codeABC(fs, OP_CLOSE, bl->nactvar, 0, 0); + luaK_patchgoto(fs, bl->brks, target, bl->brkcls); + bl->brks = NO_JUMP; /* no more breaks to fix */ + bl->brkcls = 0; /* no more need to close upvalues */ + lua_assert(!bl->upval); /* loop body cannot have local variables */ } + /* -** generates an error for an undefined 'goto'; choose appropriate -** message when label name is a reserved word (which can only be 'break') +** generates an error for an undefined 'goto'. */ static l_noret undefgoto (LexState *ls, Labeldesc *gt) { - const char *msg = isreserved(gt->name) - ? "<%s> at line %d not inside a loop" - : "no visible label '%s' for at line %d"; + const char *msg = "no visible label '%s' for at line %d"; msg = luaO_pushfstring(ls->L, msg, getstr(gt->name), gt->line); semerror(ls, msg); } @@ -473,14 +488,12 @@ static l_noret undefgoto (LexState *ls, Labeldesc *gt) { static void leaveblock (FuncState *fs) { BlockCnt *bl = fs->bl; LexState *ls = fs->ls; - if (bl->previous && bl->upval) { - /* create a 'jump to here' to close upvalues */ - int j = luaK_jump(fs); - luaK_patchclose(fs, j, bl->nactvar); - luaK_patchtohere(fs, j); - } + if (bl->upval && bl->brks != NO_JUMP) /* breaks in upvalue scopes? */ + bl->brkcls = 1; /* these breaks must close the upvalues */ if (bl->isloop) - breaklabel(ls); /* close pending breaks */ + fixbreaks(fs, bl); /* fix pending breaks */ + if (bl->previous && bl->upval) + luaK_codeABC(fs, OP_CLOSE, bl->nactvar, 0, 0); fs->bl = bl->previous; removevars(fs, bl->nactvar); lua_assert(bl->nactvar == fs->nactvar); @@ -488,8 +501,11 @@ static void leaveblock (FuncState *fs) { ls->dyd->label.n = bl->firstlabel; /* remove local labels */ if (bl->previous) /* inner block? */ movegotosout(fs, bl); /* update pending gotos to outer block */ - else if (bl->firstgoto < ls->dyd->gt.n) /* pending gotos in outer block? */ - undefgoto(ls, &ls->dyd->gt.arr[bl->firstgoto]); /* error */ + else { + lua_assert(bl->brks == NO_JUMP); /* no pending breaks */ + if (bl->firstgoto < ls->dyd->gt.n) /* pending gotos in outer block? */ + undefgoto(ls, &ls->dyd->gt.arr[bl->firstgoto]); /* error */ + } } @@ -1205,16 +1221,21 @@ static int cond (LexState *ls) { static void gotostat (LexState *ls, int pc) { int line = ls->linenumber; - TString *label; int g; - if (testnext(ls, TK_GOTO)) - label = str_checkname(ls); - else { - luaX_next(ls); /* skip break */ - label = luaS_new(ls->L, "break"); - } - g = newlabelentry(ls, &ls->dyd->gt, label, line, pc); - findlabel(ls, g); /* close it if label already defined */ + luaX_next(ls); /* skip 'goto' */ + g = newlabelentry(ls, &ls->dyd->gt, str_checkname(ls), line, pc); + solvelabel(ls, g); /* close it if label already defined */ +} + + +static void breakstat (LexState *ls, int pc) { + FuncState *fs = ls->fs; + BlockCnt *bl = fs->bl; + luaX_next(ls); /* skip break */ + while (bl && !bl->isloop) { bl = bl->previous; } + if (!bl) + luaX_syntaxerror(ls, "no loop to break"); + luaK_concat(fs, &fs->bl->brks, pc); } @@ -1248,12 +1269,13 @@ static void labelstat (LexState *ls, TString *label, int line) { checknext(ls, TK_DBCOLON); /* skip double colon */ /* create new entry for this label */ l = newlabelentry(ls, ll, label, line, luaK_getlabel(fs)); + luaK_codeABC(fs, OP_CLOSE, fs->nactvar, 0, 0); skipnoopstat(ls); /* skip other no-op statements */ if (block_follow(ls, 0)) { /* label is last no-op statement in the block? */ /* assume that locals are already out of scope */ ll->arr[l].nactvar = fs->bl->nactvar; } - findgotos(ls, &ll->arr[l]); + solvegotos(ls, &ll->arr[l]); } @@ -1289,8 +1311,15 @@ static void repeatstat (LexState *ls, int line) { check_match(ls, TK_UNTIL, TK_REPEAT, line); condexit = cond(ls); /* read condition (inside scope block) */ if (bl2.upval) /* upvalues? */ - luaK_patchclose(fs, condexit, bl2.nactvar); + luaK_patchclose(fs, condexit); leaveblock(fs); /* finish scope */ + if (bl2.upval) { /* upvalues? */ + int exit = luaK_jump(fs); /* normal exit must jump over fix */ + luaK_patchtohere(fs, condexit); /* repetition must close upvalues */ + luaK_codeABC(fs, OP_CLOSE, bl2.nactvar, 0, 0); + condexit = luaK_jump(fs); /* repeat after closing upvalues */ + luaK_patchtohere(fs, exit); /* normal exit comes to here */ + } luaK_patchlist(fs, condexit, repeat_init); /* close the loop */ leaveblock(fs); /* finish loop */ } @@ -1428,9 +1457,12 @@ static void test_then_block (LexState *ls, int *escapelist) { if (ls->t.token == TK_GOTO || ls->t.token == TK_BREAK) { luaK_goiffalse(ls->fs, &v); /* will jump to label if condition is true */ enterblock(fs, &bl, 0); /* must enter block before 'goto' */ - gotostat(ls, v.t); /* handle goto/break */ + if (ls->t.token == TK_GOTO) + gotostat(ls, v.t); /* handle goto */ + else + breakstat(ls, v.t); /* handle break */ while (testnext(ls, ';')) {} /* skip semicolons */ - if (block_follow(ls, 0)) { /* 'goto' is the entire block? */ + if (block_follow(ls, 0)) { /* 'goto'/'break' is the entire block? */ leaveblock(fs); return; /* and that is it */ } @@ -1623,7 +1655,10 @@ static void statement (LexState *ls) { retstat(ls); break; } - case TK_BREAK: /* stat -> breakstat */ + case TK_BREAK: { /* stat -> breakstat */ + breakstat(ls, luaK_jump(ls->fs)); + break; + } case TK_GOTO: { /* stat -> 'goto' NAME */ gotostat(ls, luaK_jump(ls->fs)); break; diff --git a/lvm.c b/lvm.c index be4793d1..b1e74f3d 100644 --- a/lvm.c +++ b/lvm.c @@ -1,5 +1,5 @@ /* -** $Id: lvm.c,v 2.290 2017/07/07 16:34:32 roberto Exp roberto $ +** $Id: lvm.c,v 2.291 2017/08/14 18:33:14 roberto Exp roberto $ ** Lua virtual machine ** See Copyright Notice in lua.h */ @@ -753,10 +753,7 @@ void luaV_finishOp (lua_State *L) { ** Execute a jump instruction. The 'updatemask' allows signals to stop ** tight loops. (Without it, the local copy of 'mask' could never change.) */ -#define dojump(ci,i,e) \ - { int a = GETARG_A(i); \ - if (a != 0) luaF_close(L, ci->func + a); \ - pc += GETARG_sBx(i) + e; updatemask(L); } +#define dojump(ci,i,e) { pc += GETARG_sBx(i) + e; updatemask(L); } /* for test instructions, execute the jump instruction that follows it */ @@ -1201,6 +1198,10 @@ void luaV_execute (lua_State *L) { L->top = ci->top; /* restore top */ vmbreak; } + vmcase(OP_CLOSE) { + luaF_close(L, ra); + vmbreak; + } vmcase(OP_JMP) { dojump(ci, i, 0); vmbreak; -- cgit v1.2.3-55-g6feb