aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2025-01-10 13:54:51 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2025-01-10 13:54:51 -0300
commit7ca3c40b50b385ead6b8bc4c54de97b61d11a12a (patch)
tree5c5998f39760b07e05135df56b8a828f2fb685c1
parent8a3a49250ce4a7e46ec9e90810a61d9f97aece3d (diff)
downloadlua-7ca3c40b50b385ead6b8bc4c54de97b61d11a12a.tar.gz
lua-7ca3c40b50b385ead6b8bc4c54de97b61d11a12a.tar.bz2
lua-7ca3c40b50b385ead6b8bc4c54de97b61d11a12a.zip
Another way to compile goto's
The compilation of a goto or a label just create an entry and generate boilerplate code for the gotos. As we don't know yet whether it needs a CLOSE, we code a jump followed by a CLOSE, which is then dead code. When a block ends (and then we know for sure whether there are variables that need to be closed), we check the goto's against the labels of that block. When closing a goto against a label, if it needs a CLOSE, the compiler swaps the order of the jump and the CLOSE, making the CLOSE active.
-rw-r--r--lparser.c187
-rw-r--r--lparser.h2
-rw-r--r--lvm.c1
-rw-r--r--testes/code.lua13
-rw-r--r--testes/db.lua2
-rw-r--r--testes/goto.lua35
6 files changed, 119 insertions, 121 deletions
diff --git a/lparser.c b/lparser.c
index 642e43b7..6022b38e 100644
--- a/lparser.c
+++ b/lparser.c
@@ -530,18 +530,31 @@ static l_noret jumpscopeerror (LexState *ls, Labeldesc *gt) {
530 530
531 531
532/* 532/*
533** Solves the goto at index 'g' to given 'label' and removes it 533** Closes the goto at index 'g' to given 'label' and removes it
534** from the list of pending gotos. 534** from the list of pending gotos.
535** If it jumps into the scope of some variable, raises an error. 535** If it jumps into the scope of some variable, raises an error.
536** The goto needs a CLOSE if it jumps out of a block with upvalues,
537** or out of the scope of some variable and the block has upvalues
538** (signaled by parameter 'bup').
536*/ 539*/
537static void solvegoto (LexState *ls, int g, Labeldesc *label) { 540static void closegoto (LexState *ls, int g, Labeldesc *label, int bup) {
538 int i; 541 int i;
542 FuncState *fs = ls->fs;
539 Labellist *gl = &ls->dyd->gt; /* list of gotos */ 543 Labellist *gl = &ls->dyd->gt; /* list of gotos */
540 Labeldesc *gt = &gl->arr[g]; /* goto to be resolved */ 544 Labeldesc *gt = &gl->arr[g]; /* goto to be resolved */
541 lua_assert(eqstr(gt->name, label->name)); 545 lua_assert(eqstr(gt->name, label->name));
542 if (l_unlikely(gt->nactvar < label->nactvar)) /* enter some scope? */ 546 if (l_unlikely(gt->nactvar < label->nactvar)) /* enter some scope? */
543 jumpscopeerror(ls, gt); 547 jumpscopeerror(ls, gt);
544 luaK_patchlist(ls->fs, gt->pc, label->pc); 548 if (gt->close ||
549 (label->nactvar < gt->nactvar && bup)) { /* needs close? */
550 lu_byte stklevel = reglevel(fs, label->nactvar);
551 /* move jump to CLOSE position */
552 fs->f->code[gt->pc + 1] = fs->f->code[gt->pc];
553 /* put CLOSE instruction at original position */
554 fs->f->code[gt->pc] = CREATE_ABCk(OP_CLOSE, stklevel, 0, 0, 0);
555 gt->pc++; /* must point to jump instruction */
556 }
557 luaK_patchlist(ls->fs, gt->pc, label->pc); /* goto jumps to label */
545 for (i = g; i < gl->n - 1; i++) /* remove goto from pending list */ 558 for (i = g; i < gl->n - 1; i++) /* remove goto from pending list */
546 gl->arr[i] = gl->arr[i + 1]; 559 gl->arr[i] = gl->arr[i + 1];
547 gl->n--; 560 gl->n--;
@@ -549,14 +562,14 @@ static void solvegoto (LexState *ls, int g, Labeldesc *label) {
549 562
550 563
551/* 564/*
552** Search for an active label with the given name. 565** Search for an active label with the given name, starting at
566** index 'ilb' (so that it can searh for all labels in current block
567** or all labels in current function).
553*/ 568*/
554static Labeldesc *findlabel (LexState *ls, TString *name) { 569static Labeldesc *findlabel (LexState *ls, TString *name, int ilb) {
555 int i;
556 Dyndata *dyd = ls->dyd; 570 Dyndata *dyd = ls->dyd;
557 /* check labels in current function for a match */ 571 for (; ilb < dyd->label.n; ilb++) {
558 for (i = ls->fs->firstlabel; i < dyd->label.n; i++) { 572 Labeldesc *lb = &dyd->label.arr[ilb];
559 Labeldesc *lb = &dyd->label.arr[i];
560 if (eqstr(lb->name, name)) /* correct label? */ 573 if (eqstr(lb->name, name)) /* correct label? */
561 return lb; 574 return lb;
562 } 575 }
@@ -582,29 +595,19 @@ static int newlabelentry (LexState *ls, Labellist *l, TString *name,
582} 595}
583 596
584 597
585static int newgotoentry (LexState *ls, TString *name, int line, int pc) {
586 return newlabelentry(ls, &ls->dyd->gt, name, line, pc);
587}
588
589
590/* 598/*
591** Solves forward jumps. Check whether new label 'lb' matches any 599** Create an entry for the goto and the code for it. As it is not known
592** pending gotos in current block and solves them. Return true 600** at this point whether the goto may need a CLOSE, the code has a jump
593** if any of the gotos need to close upvalues. 601** followed by an CLOSE. (As the CLOSE comes after the jump, it is a
602** dead instruction; it works as a placeholder.) When the goto is closed
603** against a label, if it needs a CLOSE, the two instructions swap
604** positions, so that the CLOSE comes before the jump.
594*/ 605*/
595static int solvegotos (LexState *ls, Labeldesc *lb) { 606static int newgotoentry (LexState *ls, TString *name, int line) {
596 Labellist *gl = &ls->dyd->gt; 607 FuncState *fs = ls->fs;
597 int i = ls->fs->bl->firstgoto; 608 int pc = luaK_jump(fs); /* create jump */
598 int needsclose = 0; 609 luaK_codeABC(fs, OP_CLOSE, 0, 1, 0); /* spaceholder, marked as dead */
599 while (i < gl->n) { 610 return newlabelentry(ls, &ls->dyd->gt, name, line, pc);
600 if (eqstr(gl->arr[i].name, lb->name)) {
601 needsclose |= gl->arr[i].close;
602 solvegoto(ls, i, lb); /* will remove 'i' from the list */
603 }
604 else
605 i++;
606 }
607 return needsclose;
608} 611}
609 612
610 613
@@ -615,8 +618,7 @@ static int solvegotos (LexState *ls, Labeldesc *lb) {
615** a close instruction if necessary. 618** a close instruction if necessary.
616** Returns true iff it added a close instruction. 619** Returns true iff it added a close instruction.
617*/ 620*/
618static int createlabel (LexState *ls, TString *name, int line, 621static void createlabel (LexState *ls, TString *name, int line, int last) {
619 int last) {
620 FuncState *fs = ls->fs; 622 FuncState *fs = ls->fs;
621 Labellist *ll = &ls->dyd->label; 623 Labellist *ll = &ls->dyd->label;
622 int l = newlabelentry(ls, ll, name, line, luaK_getlabel(fs)); 624 int l = newlabelentry(ls, ll, name, line, luaK_getlabel(fs));
@@ -624,28 +626,37 @@ static int createlabel (LexState *ls, TString *name, int line,
624 /* assume that locals are already out of scope */ 626 /* assume that locals are already out of scope */
625 ll->arr[l].nactvar = fs->bl->nactvar; 627 ll->arr[l].nactvar = fs->bl->nactvar;
626 } 628 }
627 if (solvegotos(ls, &ll->arr[l])) { /* need close? */
628 luaK_codeABC(fs, OP_CLOSE, luaY_nvarstack(fs), 0, 0);
629 return 1;
630 }
631 return 0;
632} 629}
633 630
634 631
635/* 632/*
636** Adjust pending gotos to outer level of a block. 633** Traverse the pending goto's of the finishing block checking whether
634** each match some label of that block. Those that do not match are
635** "exported" to the outer block, to be solved there. In particular,
636** its 'nactvar' is updated with the level of the inner block,
637** as the variables of the inner block are now out of scope.
637*/ 638*/
638static void movegotosout (FuncState *fs, BlockCnt *bl) { 639static void solvegotos (FuncState *fs, BlockCnt *bl) {
639 int i; 640 LexState *ls = fs->ls;
640 Labellist *gl = &fs->ls->dyd->gt; 641 Labellist *gl = &ls->dyd->gt;
641 /* correct pending gotos to current block */ 642 int outlevel = reglevel(fs, bl->nactvar); /* level outside the block */
642 for (i = bl->firstgoto; i < gl->n; i++) { /* for each pending goto */ 643 int igt = bl->firstgoto; /* first goto in the finishing block */
643 Labeldesc *gt = &gl->arr[i]; 644 while (igt < gl->n) { /* for each pending goto */
644 /* leaving a variable scope? */ 645 Labeldesc *gt = &gl->arr[igt];
645 if (reglevel(fs, gt->nactvar) > reglevel(fs, bl->nactvar)) 646 /* search for a matching label in the current block */
646 gt->close |= bl->upval; /* jump may need a close */ 647 Labeldesc *lb = findlabel(ls, gt->name, bl->firstlabel);
647 gt->nactvar = bl->nactvar; /* update goto level */ 648 if (lb != NULL) /* found a match? */
649 closegoto(ls, igt, lb, bl->upval); /* close and remove goto */
650 else { /* adjust 'goto' for outer block */
651 /* block has variables to be closed and goto escapes the scope of
652 some variable? */
653 if (bl->upval && reglevel(fs, gt->nactvar) > outlevel)
654 gt->close = 1; /* jump may need a close */
655 gt->nactvar = bl->nactvar; /* correct level for outer block */
656 igt++; /* go to next goto */
657 }
648 } 658 }
659 ls->dyd->label.n = bl->firstlabel; /* remove local labels */
649} 660}
650 661
651 662
@@ -682,23 +693,20 @@ static l_noret undefgoto (LexState *ls, Labeldesc *gt) {
682static void leaveblock (FuncState *fs) { 693static void leaveblock (FuncState *fs) {
683 BlockCnt *bl = fs->bl; 694 BlockCnt *bl = fs->bl;
684 LexState *ls = fs->ls; 695 LexState *ls = fs->ls;
685 int hasclose = 0; 696 lu_byte stklevel = reglevel(fs, bl->nactvar); /* level outside block */
686 lu_byte stklevel = reglevel(fs, bl->nactvar); /* level outside the block */ 697 if (bl->previous && bl->upval) /* need a 'close'? */
698 luaK_codeABC(fs, OP_CLOSE, stklevel, 0, 0);
699 fs->freereg = stklevel; /* free registers */
687 removevars(fs, bl->nactvar); /* remove block locals */ 700 removevars(fs, bl->nactvar); /* remove block locals */
688 lua_assert(bl->nactvar == fs->nactvar); /* back to level on entry */ 701 lua_assert(bl->nactvar == fs->nactvar); /* back to level on entry */
689 if (bl->isloop) /* has to fix pending breaks? */ 702 if (bl->isloop) /* has to fix pending breaks? */
690 hasclose = createlabel(ls, luaS_newliteral(ls->L, "break"), 0, 0); 703 createlabel(ls, luaS_newliteral(ls->L, "break"), 0, 0);
691 if (!hasclose && bl->previous && bl->upval) /* still need a 'close'? */ 704 solvegotos(fs, bl);
692 luaK_codeABC(fs, OP_CLOSE, stklevel, 0, 0); 705 if (bl->previous == NULL) { /* was it the last block? */
693 fs->freereg = stklevel; /* free registers */
694 ls->dyd->label.n = bl->firstlabel; /* remove local labels */
695 fs->bl = bl->previous; /* current block now is previous one */
696 if (bl->previous) /* was it a nested block? */
697 movegotosout(fs, bl); /* update pending gotos to enclosing block */
698 else {
699 if (bl->firstgoto < ls->dyd->gt.n) /* still pending gotos? */ 706 if (bl->firstgoto < ls->dyd->gt.n) /* still pending gotos? */
700 undefgoto(ls, &ls->dyd->gt.arr[bl->firstgoto]); /* error */ 707 undefgoto(ls, &ls->dyd->gt.arr[bl->firstgoto]); /* error */
701 } 708 }
709 fs->bl = bl->previous; /* current block now is previous one */
702} 710}
703 711
704 712
@@ -1446,40 +1454,27 @@ static int cond (LexState *ls) {
1446} 1454}
1447 1455
1448 1456
1449static void gotostat (LexState *ls) { 1457static void gotostat (LexState *ls, int line) {
1450 FuncState *fs = ls->fs;
1451 int line = ls->linenumber;
1452 TString *name = str_checkname(ls); /* label's name */ 1458 TString *name = str_checkname(ls); /* label's name */
1453 Labeldesc *lb = findlabel(ls, name); 1459 newgotoentry(ls, name, line);
1454 if (lb == NULL) /* no label? */
1455 /* forward jump; will be resolved when the label is declared */
1456 newgotoentry(ls, name, line, luaK_jump(fs));
1457 else { /* found a label */
1458 /* backward jump; will be resolved here */
1459 int lblevel = reglevel(fs, lb->nactvar); /* label level */
1460 if (luaY_nvarstack(fs) > lblevel) /* leaving the scope of a variable? */
1461 luaK_codeABC(fs, OP_CLOSE, lblevel, 0, 0);
1462 /* create jump and link it to the label */
1463 luaK_patchlist(fs, luaK_jump(fs), lb->pc);
1464 }
1465} 1460}
1466 1461
1467 1462
1468/* 1463/*
1469** Break statement. Semantically equivalent to "goto break". 1464** Break statement. Semantically equivalent to "goto break".
1470*/ 1465*/
1471static void breakstat (LexState *ls) { 1466static void breakstat (LexState *ls, int line) {
1472 int line = ls->linenumber;
1473 luaX_next(ls); /* skip break */ 1467 luaX_next(ls); /* skip break */
1474 newgotoentry(ls, luaS_newliteral(ls->L, "break"), line, luaK_jump(ls->fs)); 1468 newgotoentry(ls, luaS_newliteral(ls->L, "break"), line);
1475} 1469}
1476 1470
1477 1471
1478/* 1472/*
1479** Check whether there is already a label with the given 'name'. 1473** Check whether there is already a label with the given 'name' at
1474** current function.
1480*/ 1475*/
1481static void checkrepeated (LexState *ls, TString *name) { 1476static void checkrepeated (LexState *ls, TString *name) {
1482 Labeldesc *lb = findlabel(ls, name); 1477 Labeldesc *lb = findlabel(ls, name, ls->fs->firstlabel);
1483 if (l_unlikely(lb != NULL)) { /* already defined? */ 1478 if (l_unlikely(lb != NULL)) { /* already defined? */
1484 const char *msg = "label '%s' already defined on line %d"; 1479 const char *msg = "label '%s' already defined on line %d";
1485 msg = luaO_pushfstring(ls->L, msg, getstr(name), lb->line); 1480 msg = luaO_pushfstring(ls->L, msg, getstr(name), lb->line);
@@ -1669,38 +1664,16 @@ static void forstat (LexState *ls, int line) {
1669 1664
1670static void test_then_block (LexState *ls, int *escapelist) { 1665static void test_then_block (LexState *ls, int *escapelist) {
1671 /* test_then_block -> [IF | ELSEIF] cond THEN block */ 1666 /* test_then_block -> [IF | ELSEIF] cond THEN block */
1672 BlockCnt bl;
1673 FuncState *fs = ls->fs; 1667 FuncState *fs = ls->fs;
1674 expdesc v; 1668 int condtrue;
1675 int jf; /* instruction to skip 'then' code (if condition is false) */
1676 luaX_next(ls); /* skip IF or ELSEIF */ 1669 luaX_next(ls); /* skip IF or ELSEIF */
1677 expr(ls, &v); /* read condition */ 1670 condtrue = cond(ls); /* read condition */
1678 checknext(ls, TK_THEN); 1671 checknext(ls, TK_THEN);
1679 if (ls->t.token == TK_BREAK) { /* 'if x then break' ? */ 1672 block(ls); /* 'then' part */
1680 int line = ls->linenumber;
1681 luaK_goiffalse(ls->fs, &v); /* will jump if condition is true */
1682 luaX_next(ls); /* skip 'break' */
1683 enterblock(fs, &bl, 0); /* must enter block before 'goto' */
1684 newgotoentry(ls, luaS_newliteral(ls->L, "break"), line, v.t);
1685 while (testnext(ls, ';')) {} /* skip semicolons */
1686 if (block_follow(ls, 0)) { /* jump is the entire block? */
1687 leaveblock(fs);
1688 return; /* and that is it */
1689 }
1690 else /* must skip over 'then' part if condition is false */
1691 jf = luaK_jump(fs);
1692 }
1693 else { /* regular case (not a break) */
1694 luaK_goiftrue(ls->fs, &v); /* skip over block if condition is false */
1695 enterblock(fs, &bl, 0);
1696 jf = v.f;
1697 }
1698 statlist(ls); /* 'then' part */
1699 leaveblock(fs);
1700 if (ls->t.token == TK_ELSE || 1673 if (ls->t.token == TK_ELSE ||
1701 ls->t.token == TK_ELSEIF) /* followed by 'else'/'elseif'? */ 1674 ls->t.token == TK_ELSEIF) /* followed by 'else'/'elseif'? */
1702 luaK_concat(fs, escapelist, luaK_jump(fs)); /* must jump over it */ 1675 luaK_concat(fs, escapelist, luaK_jump(fs)); /* must jump over it */
1703 luaK_patchtohere(fs, jf); 1676 luaK_patchtohere(fs, condtrue);
1704} 1677}
1705 1678
1706 1679
@@ -1928,12 +1901,12 @@ static void statement (LexState *ls) {
1928 break; 1901 break;
1929 } 1902 }
1930 case TK_BREAK: { /* stat -> breakstat */ 1903 case TK_BREAK: { /* stat -> breakstat */
1931 breakstat(ls); 1904 breakstat(ls, line);
1932 break; 1905 break;
1933 } 1906 }
1934 case TK_GOTO: { /* stat -> 'goto' NAME */ 1907 case TK_GOTO: { /* stat -> 'goto' NAME */
1935 luaX_next(ls); /* skip 'goto' */ 1908 luaX_next(ls); /* skip 'goto' */
1936 gotostat(ls); 1909 gotostat(ls, line);
1937 break; 1910 break;
1938 } 1911 }
1939 default: { /* stat -> func | assignment */ 1912 default: { /* stat -> func | assignment */
diff --git a/lparser.h b/lparser.h
index 589befdb..a8004fa0 100644
--- a/lparser.h
+++ b/lparser.h
@@ -112,7 +112,7 @@ typedef struct Labeldesc {
112 int pc; /* position in code */ 112 int pc; /* position in code */
113 int line; /* line where it appeared */ 113 int line; /* line where it appeared */
114 lu_byte nactvar; /* number of active variables in that position */ 114 lu_byte nactvar; /* number of active variables in that position */
115 lu_byte close; /* goto that escapes upvalues */ 115 lu_byte close; /* true for goto that escapes upvalues */
116} Labeldesc; 116} Labeldesc;
117 117
118 118
diff --git a/lvm.c b/lvm.c
index 73d7ee43..074ee718 100644
--- a/lvm.c
+++ b/lvm.c
@@ -1590,6 +1590,7 @@ void luaV_execute (lua_State *L, CallInfo *ci) {
1590 } 1590 }
1591 vmcase(OP_CLOSE) { 1591 vmcase(OP_CLOSE) {
1592 StkId ra = RA(i); 1592 StkId ra = RA(i);
1593 lua_assert(!GETARG_B(i)); /* 'close must be alive */
1593 Protect(luaF_close(L, ra, LUA_OK, 1)); 1594 Protect(luaF_close(L, ra, LUA_OK, 1));
1594 vmbreak; 1595 vmbreak;
1595 } 1596 }
diff --git a/testes/code.lua b/testes/code.lua
index 08b3e23f..50ce7392 100644
--- a/testes/code.lua
+++ b/testes/code.lua
@@ -412,13 +412,22 @@ checkequal(function (l) local a; return 0 <= a and a <= l end,
412 function (l) local a; return not (not(a >= 0) or not(a <= l)) end) 412 function (l) local a; return not (not(a >= 0) or not(a <= l)) end)
413 413
414 414
415-- if-break optimizations
416check(function (a, b) 415check(function (a, b)
417 while a do 416 while a do
418 if b then break else a = a + 1 end 417 if b then break else a = a + 1 end
419 end 418 end
420 end, 419 end,
421'TEST', 'JMP', 'TEST', 'JMP', 'ADDI', 'MMBINI', 'JMP', 'RETURN0') 420'TEST', 'JMP', 'TEST', 'JMP', 'JMP', 'CLOSE', 'JMP', 'ADDI', 'MMBINI', 'JMP', 'RETURN0')
421
422check(function ()
423 do
424 goto exit -- don't need to close
425 local x <close> = nil
426 goto exit -- must close
427 end
428 ::exit::
429 end, 'JMP', 'CLOSE', 'LOADNIL', 'TBC',
430 'CLOSE', 'JMP', 'CLOSE', 'RETURN')
422 431
423checkequal(function () return 6 or true or nil end, 432checkequal(function () return 6 or true or nil end,
424 function () return k6 or kTrue or kNil end) 433 function () return k6 or kTrue or kNil end)
diff --git a/testes/db.lua b/testes/db.lua
index fc0db9ea..75730d27 100644
--- a/testes/db.lua
+++ b/testes/db.lua
@@ -128,7 +128,7 @@ then
128else 128else
129 a=2 129 a=2
130end 130end
131]], {2,3,4,7}) 131]], {2,4,7})
132 132
133 133
134test([[ 134test([[
diff --git a/testes/goto.lua b/testes/goto.lua
index 4ac6d7d0..103cccef 100644
--- a/testes/goto.lua
+++ b/testes/goto.lua
@@ -250,21 +250,36 @@ assert(testG(3) == "3")
250assert(testG(4) == 5) 250assert(testG(4) == 5)
251assert(testG(5) == 10) 251assert(testG(5) == 10)
252 252
253do 253do -- test goto's around to-be-closed variable
254 -- if x back goto out of scope of upvalue 254
255 local X 255 -- set 'var' and return an object that will reset 'var' when
256 -- it goes out of scope
257 local function newobj (var)
258 _ENV[var] = true
259 return setmetatable({}, {__close = function ()
260 _ENV[var] = nil
261 end})
262 end
263
256 goto L1 264 goto L1
257 265
258 ::L2:: goto L3 266 ::L4:: assert(not X); goto L5 -- varX dead here
259 267
260 ::L1:: do 268 ::L1::
261 local a <close> = setmetatable({}, {__close = function () X = true end}) 269 local varX <close> = newobj("X")
262 assert(X == nil) 270 assert(X); goto L2 -- varX alive here
263 if a then goto L2 end -- jumping back out of scope of 'a'
264 end
265 271
266 ::L3:: assert(X == true) -- checks that 'a' was correctly closed 272 ::L3::
273 assert(X); goto L4 -- varX alive here
274
275 ::L2:: assert(X); goto L3 -- varX alive here
276
277 ::L5:: -- return
267end 278end
279
280
281
282foo()
268-------------------------------------------------------------------------------- 283--------------------------------------------------------------------------------
269 284
270 285