- initial import of revision 374 from cnc
[apt.git] / lua / lcode.c
1 /*
2 ** $Id: lcode.c,v 1.117 2003/04/03 13:35:34 roberto Exp $
3 ** Code generator for Lua
4 ** See Copyright Notice in lua.h
5 */
6
7
8 #include <stdlib.h>
9
10 #define lcode_c
11
12 #include "lua.h"
13
14 #include "lcode.h"
15 #include "ldebug.h"
16 #include "ldo.h"
17 #include "llex.h"
18 #include "lmem.h"
19 #include "lobject.h"
20 #include "lopcodes.h"
21 #include "lparser.h"
22 #include "ltable.h"
23
24
25 #define hasjumps(e)     ((e)->t != (e)->f)
26
27
28 void luaK_nil (FuncState *fs, int from, int n) {
29   Instruction *previous;
30   if (fs->pc > fs->lasttarget &&  /* no jumps to current position? */
31       GET_OPCODE(*(previous = &fs->f->code[fs->pc-1])) == OP_LOADNIL) {
32     int pfrom = GETARG_A(*previous);
33     int pto = GETARG_B(*previous);
34     if (pfrom <= from && from <= pto+1) {  /* can connect both? */
35       if (from+n-1 > pto)
36         SETARG_B(*previous, from+n-1);
37       return;
38     }
39   }
40   luaK_codeABC(fs, OP_LOADNIL, from, from+n-1, 0);  /* else no optimization */
41 }
42
43
44 int luaK_jump (FuncState *fs) {
45   int jpc = fs->jpc;  /* save list of jumps to here */
46   int j;
47   fs->jpc = NO_JUMP;
48   j = luaK_codeAsBx(fs, OP_JMP, 0, NO_JUMP);
49   luaK_concat(fs, &j, jpc);  /* keep them on hold */
50   return j;
51 }
52
53
54 static int luaK_condjump (FuncState *fs, OpCode op, int A, int B, int C) {
55   luaK_codeABC(fs, op, A, B, C);
56   return luaK_jump(fs);
57 }
58
59
60 static void luaK_fixjump (FuncState *fs, int pc, int dest) {
61   Instruction *jmp = &fs->f->code[pc];
62   int offset = dest-(pc+1);
63   lua_assert(dest != NO_JUMP);
64   if (abs(offset) > MAXARG_sBx)
65     luaX_syntaxerror(fs->ls, "control structure too long");
66   SETARG_sBx(*jmp, offset);
67 }
68
69
70 /*
71 ** returns current `pc' and marks it as a jump target (to avoid wrong
72 ** optimizations with consecutive instructions not in the same basic block).
73 */
74 int luaK_getlabel (FuncState *fs) {
75   fs->lasttarget = fs->pc;
76   return fs->pc;
77 }
78
79
80 static int luaK_getjump (FuncState *fs, int pc) {
81   int offset = GETARG_sBx(fs->f->code[pc]);
82   if (offset == NO_JUMP)  /* point to itself represents end of list */
83     return NO_JUMP;  /* end of list */
84   else
85     return (pc+1)+offset;  /* turn offset into absolute position */
86 }
87
88
89 static Instruction *getjumpcontrol (FuncState *fs, int pc) {
90   Instruction *pi = &fs->f->code[pc];
91   if (pc >= 1 && testOpMode(GET_OPCODE(*(pi-1)), OpModeT))
92     return pi-1;
93   else
94     return pi;
95 }
96
97
98 /*
99 ** check whether list has any jump that do not produce a value
100 ** (or produce an inverted value)
101 */
102 static int need_value (FuncState *fs, int list, int cond) {
103   for (; list != NO_JUMP; list = luaK_getjump(fs, list)) {
104     Instruction i = *getjumpcontrol(fs, list);
105     if (GET_OPCODE(i) != OP_TEST || GETARG_C(i) != cond) return 1;
106   }
107   return 0;  /* not found */
108 }
109
110
111 static void patchtestreg (Instruction *i, int reg) {
112   if (reg == NO_REG) reg = GETARG_B(*i);
113   SETARG_A(*i, reg);
114 }
115
116
117 static void luaK_patchlistaux (FuncState *fs, int list,
118           int ttarget, int treg, int ftarget, int freg, int dtarget) {
119   while (list != NO_JUMP) {
120     int next = luaK_getjump(fs, list);
121     Instruction *i = getjumpcontrol(fs, list);
122     if (GET_OPCODE(*i) != OP_TEST) {
123       lua_assert(dtarget != NO_JUMP);
124       luaK_fixjump(fs, list, dtarget);  /* jump to default target */
125     }
126     else {
127       if (GETARG_C(*i)) {
128         lua_assert(ttarget != NO_JUMP);
129         patchtestreg(i, treg);
130         luaK_fixjump(fs, list, ttarget);
131       }
132       else {
133         lua_assert(ftarget != NO_JUMP);
134         patchtestreg(i, freg);
135         luaK_fixjump(fs, list, ftarget);
136       }
137     }
138     list = next;
139   }
140 }
141
142
143 static void luaK_dischargejpc (FuncState *fs) {
144   luaK_patchlistaux(fs, fs->jpc, fs->pc, NO_REG, fs->pc, NO_REG, fs->pc);
145   fs->jpc = NO_JUMP;
146 }
147
148
149 void luaK_patchlist (FuncState *fs, int list, int target) {
150   if (target == fs->pc)
151     luaK_patchtohere(fs, list);
152   else {
153     lua_assert(target < fs->pc);
154     luaK_patchlistaux(fs, list, target, NO_REG, target, NO_REG, target);
155   }
156 }
157
158
159 void luaK_patchtohere (FuncState *fs, int list) {
160   luaK_getlabel(fs);
161   luaK_concat(fs, &fs->jpc, list);
162 }
163
164
165 void luaK_concat (FuncState *fs, int *l1, int l2) {
166   if (l2 == NO_JUMP) return;
167   else if (*l1 == NO_JUMP)
168     *l1 = l2;
169   else {
170     int list = *l1;
171     int next;
172     while ((next = luaK_getjump(fs, list)) != NO_JUMP)  /* find last element */
173       list = next;
174     luaK_fixjump(fs, list, l2);
175   }
176 }
177
178
179 void luaK_checkstack (FuncState *fs, int n) {
180   int newstack = fs->freereg + n;
181   if (newstack > fs->f->maxstacksize) {
182     if (newstack >= MAXSTACK)
183       luaX_syntaxerror(fs->ls, "function or expression too complex");
184     fs->f->maxstacksize = cast(lu_byte, newstack);
185   }
186 }
187
188
189 void luaK_reserveregs (FuncState *fs, int n) {
190   luaK_checkstack(fs, n);
191   fs->freereg += n;
192 }
193
194
195 static void freereg (FuncState *fs, int reg) {
196   if (reg >= fs->nactvar && reg < MAXSTACK) {
197     fs->freereg--;
198     lua_assert(reg == fs->freereg);
199   }
200 }
201
202
203 static void freeexp (FuncState *fs, expdesc *e) {
204   if (e->k == VNONRELOC)
205     freereg(fs, e->info);
206 }
207
208
209 static int addk (FuncState *fs, TObject *k, TObject *v) {
210   const TObject *idx = luaH_get(fs->h, k);
211   if (ttisnumber(idx)) {
212     lua_assert(luaO_rawequalObj(&fs->f->k[cast(int, nvalue(idx))], v));
213     return cast(int, nvalue(idx));
214   }
215   else {  /* constant not found; create a new entry */
216     Proto *f = fs->f;
217     luaM_growvector(fs->L, f->k, fs->nk, f->sizek, TObject,
218                     MAXARG_Bx, "constant table overflow");
219     setobj2n(&f->k[fs->nk], v);
220     setnvalue(luaH_set(fs->L, fs->h, k), cast(lua_Number, fs->nk));
221     return fs->nk++;
222   }
223 }
224
225
226 int luaK_stringK (FuncState *fs, TString *s) {
227   TObject o;
228   setsvalue(&o, s);
229   return addk(fs, &o, &o);
230 }
231
232
233 int luaK_numberK (FuncState *fs, lua_Number r) {
234   TObject o;
235   setnvalue(&o, r);
236   return addk(fs, &o, &o);
237 }
238
239
240 static int nil_constant (FuncState *fs) {
241   TObject k, v;
242   setnilvalue(&v);
243   sethvalue(&k, fs->h);  /* cannot use nil as key; instead use table itself */
244   return addk(fs, &k, &v);
245 }
246
247
248 void luaK_setcallreturns (FuncState *fs, expdesc *e, int nresults) {
249   if (e->k == VCALL) {  /* expression is an open function call? */
250     SETARG_C(getcode(fs, e), nresults+1);
251     if (nresults == 1) {  /* `regular' expression? */
252       e->k = VNONRELOC;
253       e->info = GETARG_A(getcode(fs, e));
254     }
255   }
256 }
257
258
259 void luaK_dischargevars (FuncState *fs, expdesc *e) {
260   switch (e->k) {
261     case VLOCAL: {
262       e->k = VNONRELOC;
263       break;
264     }
265     case VUPVAL: {
266       e->info = luaK_codeABC(fs, OP_GETUPVAL, 0, e->info, 0);
267       e->k = VRELOCABLE;
268       break;
269     }
270     case VGLOBAL: {
271       e->info = luaK_codeABx(fs, OP_GETGLOBAL, 0, e->info);
272       e->k = VRELOCABLE;
273       break;
274     }
275     case VINDEXED: {
276       freereg(fs, e->aux);
277       freereg(fs, e->info);
278       e->info = luaK_codeABC(fs, OP_GETTABLE, 0, e->info, e->aux);
279       e->k = VRELOCABLE;
280       break;
281     }
282     case VCALL: {
283       luaK_setcallreturns(fs, e, 1);
284       break;
285     }
286     default: break;  /* there is one value available (somewhere) */
287   }
288 }
289
290
291 static int code_label (FuncState *fs, int A, int b, int jump) {
292   luaK_getlabel(fs);  /* those instructions may be jump targets */
293   return luaK_codeABC(fs, OP_LOADBOOL, A, b, jump);
294 }
295
296
297 static void discharge2reg (FuncState *fs, expdesc *e, int reg) {
298   luaK_dischargevars(fs, e);
299   switch (e->k) {
300     case VNIL: {
301       luaK_nil(fs, reg, 1);
302       break;
303     }
304     case VFALSE:  case VTRUE: {
305       luaK_codeABC(fs, OP_LOADBOOL, reg, e->k == VTRUE, 0);
306       break;
307     }
308     case VK: {
309       luaK_codeABx(fs, OP_LOADK, reg, e->info);
310       break;
311     }
312     case VRELOCABLE: {
313       Instruction *pc = &getcode(fs, e);
314       SETARG_A(*pc, reg);
315       break;
316     }
317     case VNONRELOC: {
318       if (reg != e->info)
319         luaK_codeABC(fs, OP_MOVE, reg, e->info, 0);
320       break;
321     }
322     default: {
323       lua_assert(e->k == VVOID || e->k == VJMP);
324       return;  /* nothing to do... */
325     }
326   }
327   e->info = reg;
328   e->k = VNONRELOC;
329 }
330
331
332 static void discharge2anyreg (FuncState *fs, expdesc *e) {
333   if (e->k != VNONRELOC) {
334     luaK_reserveregs(fs, 1);
335     discharge2reg(fs, e, fs->freereg-1);
336   }
337 }
338
339
340 static void luaK_exp2reg (FuncState *fs, expdesc *e, int reg) {
341   discharge2reg(fs, e, reg);
342   if (e->k == VJMP)
343     luaK_concat(fs, &e->t, e->info);  /* put this jump in `t' list */
344   if (hasjumps(e)) {
345     int final;  /* position after whole expression */
346     int p_f = NO_JUMP;  /* position of an eventual LOAD false */
347     int p_t = NO_JUMP;  /* position of an eventual LOAD true */
348     if (need_value(fs, e->t, 1) || need_value(fs, e->f, 0)) {
349       int fj = NO_JUMP;  /* first jump (over LOAD ops.) */
350       if (e->k != VJMP)
351         fj = luaK_jump(fs);
352       p_f = code_label(fs, reg, 0, 1);
353       p_t = code_label(fs, reg, 1, 0);
354       luaK_patchtohere(fs, fj);
355     }
356     final = luaK_getlabel(fs);
357     luaK_patchlistaux(fs, e->f, p_f, NO_REG, final, reg, p_f);
358     luaK_patchlistaux(fs, e->t, final, reg, p_t, NO_REG, p_t);
359   }
360   e->f = e->t = NO_JUMP;
361   e->info = reg;
362   e->k = VNONRELOC;
363 }
364
365
366 void luaK_exp2nextreg (FuncState *fs, expdesc *e) {
367   luaK_dischargevars(fs, e);
368   freeexp(fs, e);
369   luaK_reserveregs(fs, 1);
370   luaK_exp2reg(fs, e, fs->freereg - 1);
371 }
372
373
374 int luaK_exp2anyreg (FuncState *fs, expdesc *e) {
375   luaK_dischargevars(fs, e);
376   if (e->k == VNONRELOC) {
377     if (!hasjumps(e)) return e->info;  /* exp is already in a register */ 
378     if (e->info >= fs->nactvar) {  /* reg. is not a local? */
379       luaK_exp2reg(fs, e, e->info);  /* put value on it */
380       return e->info;
381     }
382   }
383   luaK_exp2nextreg(fs, e);  /* default */
384   return e->info;
385 }
386
387
388 void luaK_exp2val (FuncState *fs, expdesc *e) {
389   if (hasjumps(e))
390     luaK_exp2anyreg(fs, e);
391   else
392     luaK_dischargevars(fs, e);
393 }
394
395
396 int luaK_exp2RK (FuncState *fs, expdesc *e) {
397   luaK_exp2val(fs, e);
398   switch (e->k) {
399     case VNIL: {
400       if (fs->nk + MAXSTACK <= MAXARG_C) {  /* constant fit in argC? */
401         e->info = nil_constant(fs);
402         e->k = VK;
403         return e->info + MAXSTACK;
404       }
405       else break;
406     }
407     case VK: {
408       if (e->info + MAXSTACK <= MAXARG_C)  /* constant fit in argC? */
409         return e->info + MAXSTACK;
410       else break;
411     }
412     default: break;
413   }
414   /* not a constant in the right range: put it in a register */
415   return luaK_exp2anyreg(fs, e);
416 }
417
418
419 void luaK_storevar (FuncState *fs, expdesc *var, expdesc *exp) {
420   switch (var->k) {
421     case VLOCAL: {
422       freeexp(fs, exp);
423       luaK_exp2reg(fs, exp, var->info);
424       return;
425     }
426     case VUPVAL: {
427       int e = luaK_exp2anyreg(fs, exp);
428       luaK_codeABC(fs, OP_SETUPVAL, e, var->info, 0);
429       break;
430     }
431     case VGLOBAL: {
432       int e = luaK_exp2anyreg(fs, exp);
433       luaK_codeABx(fs, OP_SETGLOBAL, e, var->info);
434       break;
435     }
436     case VINDEXED: {
437       int e = luaK_exp2RK(fs, exp);
438       luaK_codeABC(fs, OP_SETTABLE, var->info, var->aux, e);
439       break;
440     }
441     default: {
442       lua_assert(0);  /* invalid var kind to store */
443       break;
444     }
445   }
446   freeexp(fs, exp);
447 }
448
449
450 void luaK_self (FuncState *fs, expdesc *e, expdesc *key) {
451   int func;
452   luaK_exp2anyreg(fs, e);
453   freeexp(fs, e);
454   func = fs->freereg;
455   luaK_reserveregs(fs, 2);
456   luaK_codeABC(fs, OP_SELF, func, e->info, luaK_exp2RK(fs, key));
457   freeexp(fs, key);
458   e->info = func;
459   e->k = VNONRELOC;
460 }
461
462
463 static void invertjump (FuncState *fs, expdesc *e) {
464   Instruction *pc = getjumpcontrol(fs, e->info);
465   lua_assert(testOpMode(GET_OPCODE(*pc), OpModeT) &&
466              GET_OPCODE(*pc) != OP_TEST);
467   SETARG_A(*pc, !(GETARG_A(*pc)));
468 }
469
470
471 static int jumponcond (FuncState *fs, expdesc *e, int cond) {
472   if (e->k == VRELOCABLE) {
473     Instruction ie = getcode(fs, e);
474     if (GET_OPCODE(ie) == OP_NOT) {
475       fs->pc--;  /* remove previous OP_NOT */
476       return luaK_condjump(fs, OP_TEST, NO_REG, GETARG_B(ie), !cond);
477     }
478     /* else go through */
479   }
480   discharge2anyreg(fs, e);
481   freeexp(fs, e);
482   return luaK_condjump(fs, OP_TEST, NO_REG, e->info, cond);
483 }
484
485
486 void luaK_goiftrue (FuncState *fs, expdesc *e) {
487   int pc;  /* pc of last jump */
488   luaK_dischargevars(fs, e);
489   switch (e->k) {
490     case VK: case VTRUE: {
491       pc = NO_JUMP;  /* always true; do nothing */
492       break;
493     }
494     case VFALSE: {
495       pc = luaK_jump(fs);  /* always jump */
496       break;
497     }
498     case VJMP: {
499       invertjump(fs, e);
500       pc = e->info;
501       break;
502     }
503     default: {
504       pc = jumponcond(fs, e, 0);
505       break;
506     }
507   }
508   luaK_concat(fs, &e->f, pc);  /* insert last jump in `f' list */
509 }
510
511
512 void luaK_goiffalse (FuncState *fs, expdesc *e) {
513   int pc;  /* pc of last jump */
514   luaK_dischargevars(fs, e);
515   switch (e->k) {
516     case VNIL: case VFALSE: {
517       pc = NO_JUMP;  /* always false; do nothing */
518       break;
519     }
520     case VTRUE: {
521       pc = luaK_jump(fs);  /* always jump */
522       break;
523     }
524     case VJMP: {
525       pc = e->info;
526       break;
527     }
528     default: {
529       pc = jumponcond(fs, e, 1);
530       break;
531     }
532   }
533   luaK_concat(fs, &e->t, pc);  /* insert last jump in `t' list */
534 }
535
536
537 static void codenot (FuncState *fs, expdesc *e) {
538   luaK_dischargevars(fs, e);
539   switch (e->k) {
540     case VNIL: case VFALSE: {
541       e->k = VTRUE;
542       break;
543     }
544     case VK: case VTRUE: {
545       e->k = VFALSE;
546       break;
547     }
548     case VJMP: {
549       invertjump(fs, e);
550       break;
551     }
552     case VRELOCABLE:
553     case VNONRELOC: {
554       discharge2anyreg(fs, e);
555       freeexp(fs, e);
556       e->info = luaK_codeABC(fs, OP_NOT, 0, e->info, 0);
557       e->k = VRELOCABLE;
558       break;
559     }
560     default: {
561       lua_assert(0);  /* cannot happen */
562       break;
563     }
564   }
565   /* interchange true and false lists */
566   { int temp = e->f; e->f = e->t; e->t = temp; }
567 }
568
569
570 void luaK_indexed (FuncState *fs, expdesc *t, expdesc *k) {
571   t->aux = luaK_exp2RK(fs, k);
572   t->k = VINDEXED;
573 }
574
575
576 void luaK_prefix (FuncState *fs, UnOpr op, expdesc *e) {
577   if (op == OPR_MINUS) {
578     luaK_exp2val(fs, e);
579     if (e->k == VK && ttisnumber(&fs->f->k[e->info]))
580       e->info = luaK_numberK(fs, -nvalue(&fs->f->k[e->info]));
581     else {
582       luaK_exp2anyreg(fs, e);
583       freeexp(fs, e);
584       e->info = luaK_codeABC(fs, OP_UNM, 0, e->info, 0);
585       e->k = VRELOCABLE;
586     }
587   }
588   else  /* op == NOT */
589     codenot(fs, e);
590 }
591
592
593 void luaK_infix (FuncState *fs, BinOpr op, expdesc *v) {
594   switch (op) {
595     case OPR_AND: {
596       luaK_goiftrue(fs, v);
597       luaK_patchtohere(fs, v->t);
598       v->t = NO_JUMP;
599       break;
600     }
601     case OPR_OR: {
602       luaK_goiffalse(fs, v);
603       luaK_patchtohere(fs, v->f);
604       v->f = NO_JUMP;
605       break;
606     }
607     case OPR_CONCAT: {
608       luaK_exp2nextreg(fs, v);  /* operand must be on the `stack' */
609       break;
610     }
611     default: {
612       luaK_exp2RK(fs, v);
613       break;
614     }
615   }
616 }
617
618
619 static void codebinop (FuncState *fs, expdesc *res, BinOpr op,
620                        int o1, int o2) {
621   if (op <= OPR_POW) {  /* arithmetic operator? */
622     OpCode opc = cast(OpCode, (op - OPR_ADD) + OP_ADD);  /* ORDER OP */
623     res->info = luaK_codeABC(fs, opc, 0, o1, o2);
624     res->k = VRELOCABLE;
625   }
626   else {  /* test operator */
627     static const OpCode ops[] = {OP_EQ, OP_EQ, OP_LT, OP_LE, OP_LT, OP_LE};
628     int cond = 1;
629     if (op >= OPR_GT) {  /* `>' or `>='? */
630       int temp;  /* exchange args and replace by `<' or `<=' */
631       temp = o1; o1 = o2; o2 = temp;  /* o1 <==> o2 */
632     }
633     else if (op == OPR_NE) cond = 0;
634     res->info = luaK_condjump(fs, ops[op - OPR_NE], cond, o1, o2);
635     res->k = VJMP;
636   }
637 }
638
639
640 void luaK_posfix (FuncState *fs, BinOpr op, expdesc *e1, expdesc *e2) {
641   switch (op) {
642     case OPR_AND: {
643       lua_assert(e1->t == NO_JUMP);  /* list must be closed */
644       luaK_dischargevars(fs, e2);
645       luaK_concat(fs, &e1->f, e2->f);
646       e1->k = e2->k; e1->info = e2->info; e1->aux = e2->aux; e1->t = e2->t;
647       break;
648     }
649     case OPR_OR: {
650       lua_assert(e1->f == NO_JUMP);  /* list must be closed */
651       luaK_dischargevars(fs, e2);
652       luaK_concat(fs, &e1->t, e2->t);
653       e1->k = e2->k; e1->info = e2->info; e1->aux = e2->aux; e1->f = e2->f;
654       break;
655     }
656     case OPR_CONCAT: {
657       luaK_exp2val(fs, e2);
658       if (e2->k == VRELOCABLE && GET_OPCODE(getcode(fs, e2)) == OP_CONCAT) {
659         lua_assert(e1->info == GETARG_B(getcode(fs, e2))-1);
660         freeexp(fs, e1);
661         SETARG_B(getcode(fs, e2), e1->info);
662         e1->k = e2->k; e1->info = e2->info;
663       }
664       else {
665         luaK_exp2nextreg(fs, e2);
666         freeexp(fs, e2);
667         freeexp(fs, e1);
668         e1->info = luaK_codeABC(fs, OP_CONCAT, 0, e1->info, e2->info);
669         e1->k = VRELOCABLE;
670       }
671       break;
672     }
673     default: {
674       int o1 = luaK_exp2RK(fs, e1);
675       int o2 = luaK_exp2RK(fs, e2);
676       freeexp(fs, e2);
677       freeexp(fs, e1);
678       codebinop(fs, e1, op, o1, o2);
679     }
680   }
681 }
682
683
684 void luaK_fixline (FuncState *fs, int line) {
685   fs->f->lineinfo[fs->pc - 1] = line;
686 }
687
688
689 int luaK_code (FuncState *fs, Instruction i, int line) {
690   Proto *f = fs->f;
691   luaK_dischargejpc(fs);  /* `pc' will change */
692   /* put new instruction in code array */
693   luaM_growvector(fs->L, f->code, fs->pc, f->sizecode, Instruction,
694                   MAX_INT, "code size overflow");
695   f->code[fs->pc] = i;
696   /* save corresponding line information */
697   luaM_growvector(fs->L, f->lineinfo, fs->pc, f->sizelineinfo, int,
698                   MAX_INT, "code size overflow");
699   f->lineinfo[fs->pc] = line;
700   return fs->pc++;
701 }
702
703
704 int luaK_codeABC (FuncState *fs, OpCode o, int a, int b, int c) {
705   lua_assert(getOpMode(o) == iABC);
706   return luaK_code(fs, CREATE_ABC(o, a, b, c), fs->ls->lastline);
707 }
708
709
710 int luaK_codeABx (FuncState *fs, OpCode o, int a, unsigned int bc) {
711   lua_assert(getOpMode(o) == iABx || getOpMode(o) == iAsBx);
712   return luaK_code(fs, CREATE_ABx(o, a, bc), fs->ls->lastline);
713 }
714