gaem/runner/compiler.d

   1 /* GML runner
   2  * coded by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
   3  * Understanding is not required. Only obedience.
   4  *
   5  * This program is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation, either version 3 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program. If not, see <http://www.gnu.org/licenses/>.
  17  */
  18 module gaem.runner.compiler is aliced;
  19
  20 import std.traits;
  21
  22 import gaem.parser;
  23
  24 import gaem.runner.strpool;
  25 import gaem.runner.value;
  26 import gaem.runner.opcodes;
  27 import gaem.runner.vm;
  28 import gaem.runner.objects;
  29
  30
  31 // ////////////////////////////////////////////////////////////////////////// //
  32 void compile (VM vm, NodeFunc fn) {
  33   import std.stdio : stdout;
  34   auto spc = vm.code.length;
  35   vm.doCompileFunc(fn);
  36   while (spc < vm.code.length) spc += dumpInstr(stdout, spc, vm.code);
  37 }
  38
  39
  40 // ////////////////////////////////////////////////////////////////////////// //
  41 private:
  42 void doCompileFunc (VM vm, NodeFunc fn) {
  43   int argvar (string s) {
  44     switch (s) {
  45       case "argument0": return 0;
  46       case "argument1": return 1;
  47       case "argument2": return 2;
  48       case "argument3": return 3;
  49       case "argument4": return 4;
  50       case "argument5": return 5;
  51       case "argument6": return 6;
  52       case "argument7": return 7;
  53       case "argument8": return 8;
  54       case "argument9": return 9;
  55       case "argument10": return 10;
  56       case "argument11": return 11;
  57       case "argument12": return 12;
  58       case "argument13": return 13;
  59       case "argument14": return 14;
  60       case "argument15": return 15;
  61       default:
  62     }
  63     return -1;
  64   }
  65
  66   void compileError(A...) (Loc loc, A args) {
  67     if (fn.pp !is null) {
  68       fn.pp.error(loc, args);
  69     } else {
  70       import std.stdio : stderr;
  71       stderr.writeln("ERROR at ", loc, ": ", args);
  72       string msg;
  73       foreach (immutable a; args) {
  74         import std.string : format;
  75         msg ~= "%s".format(a);
  76       }
  77       throw new ErrorAt(loc, msg);
  78     }
  79   }
  80
  81   uint sid4name (string name) {
  82     if (auto sptr = name in vm.scripts) {
  83       return *sptr;
  84     } else {
  85       auto sid = cast(uint)vm.scriptPCs.length;
  86       if (sid > 32767) compileError(fn.loc, "too many vm.scripts");
  87       assert(vm.scriptASTs.length == sid);
  88       // reserve slots
  89       vm.scriptPCs ~= 0;
  90       vm.scriptASTs ~= null;
  91       vm.scriptNum2Name[sid] = name;
  92       vm.scripts[name] = sid;
  93       return sid;
  94     }
  95   }
  96
  97   uint pc () { return cast(uint)vm.code.length; }
  98
  99   uint emit (Op op, ubyte dest=0, ubyte op0=0, ubyte op1=0) {
 100     auto res = cast(uint)vm.code.length;
 101     vm.code ~= (op1<<24)|(op0<<16)|(dest<<8)|cast(ubyte)op;
 102     return res;
 103   }
 104
 105   uint emit3Bytes (Op op, uint val) {
 106     assert(val <= 0xffffff);
 107     auto res = cast(uint)vm.code.length;
 108     vm.code ~= (val<<8)|cast(ubyte)op;
 109     return res;
 110   }
 111
 112   uint emit2Bytes (Op op, ubyte dest, short val) {
 113     auto res = cast(uint)vm.code.length;
 114     vm.code ~= (val<<16)|(dest<<8)|cast(ubyte)op;
 115     return res;
 116   }
 117
 118   uint emitJumpTo (uint addr, Op op=Op.jump) {
 119     assert(addr <= 0xffffff);
 120     auto res = cast(uint)vm.code.length;
 121     vm.code ~= cast(uint)op|(addr<<8);
 122     return res;
 123   }
 124
 125   // this starts "jump chain", return new chain id
 126   uint emitJumpChain (uint chain, Op op=Op.jump) {
 127     assert(chain <= 0xffffff);
 128     auto res = cast(uint)vm.code.length;
 129     vm.code ~= cast(uint)op|(chain<<8);
 130     return res;
 131   }
 132
 133   void fixJumpChain (uint chain, uint addr) {
 134     assert(chain <= 0xffffff);
 135     assert(addr <= 0xffffff);
 136     while (chain) {
 137       auto nc = op3Byte(vm.code[chain]);
 138       vm.code[chain] = (vm.code[chain]&0xff)|(addr<<8);
 139       chain = nc;
 140     }
 141   }
 142
 143   void opReplace (uint pc, Op op, ubyte dest) {
 144     vm.code[pc] = (vm.code[pc]&0xff_ff_00_00)|(dest<<8)|cast(ubyte)op;
 145   }
 146
 147   assert(fn !is null);
 148   assert(fn.ebody !is null);
 149   assert(fn.name.length);
 150
 151   bool[256] slots;
 152   foreach (immutable idx; 0..VM.Slot.max+1) slots[idx] = true; // used
 153   uint firstFreeSlot = VM.Slot.max+1;
 154   uint maxUsedSlot = firstFreeSlot-1;
 155
 156   ubyte allocSlot (Loc loc, int ddest=-1) {
 157     if (ddest >= 0) {
 158       assert(ddest < slots.length);
 159       return cast(ubyte)ddest;
 160     }
 161     foreach (immutable idx; firstFreeSlot..slots.length) {
 162       if (!slots[idx]) {
 163         if (idx > maxUsedSlot) maxUsedSlot = cast(uint)idx;
 164         slots[idx] = true;
 165         return cast(ubyte)idx;
 166       }
 167     }
 168     compileError(loc, "out of free slots");
 169     assert(0);
 170   }
 171
 172   ubyte allocSlots (Loc loc, int count) {
 173     assert(count > 0 && count < slots.length);
 174     foreach (immutable idx; firstFreeSlot..slots.length-count) {
 175       bool ok = true;
 176       foreach (immutable c; idx..idx+count) if (slots[c]) { ok = false; break; }
 177       if (ok) {
 178         if (idx+count-1 > maxUsedSlot) maxUsedSlot = cast(uint)idx+count-1;
 179         foreach (immutable c; idx..idx+count) slots[c] = true;
 180         return cast(ubyte)idx;
 181       }
 182     }
 183     compileError(loc, "out of free slots");
 184     assert(0);
 185   }
 186
 187   ubyte reserveCallSlots (Loc loc, uint resnum) {
 188     foreach_reverse (immutable idx, bool v; slots) {
 189       if (v) {
 190         if (idx+resnum+1 > slots.length) compileError(loc, "out of free slots");
 191         return cast(ubyte)(idx+1);
 192       }
 193     }
 194     compileError(loc, "out of free slots");
 195     assert(0);
 196   }
 197
 198   void freeSlot (ubyte num) {
 199     if (num >= firstFreeSlot) {
 200       assert(slots[num]);
 201       slots[num] = false;
 202     }
 203   }
 204
 205   ubyte[string] locals;
 206   uint[string] globals;
 207   Loc[string] vdecls; // for error messages
 208   ubyte maxArgUsed; // maximum `argumentX` we've seen
 209
 210   // collect var declarations (gml is not properly scoped)
 211   visitNodes(fn.ebody, (Node n) {
 212     if (auto vd = cast(NodeVarDecl)n) {
 213       foreach (immutable idx, string name; vd.names) {
 214         if (name in locals) {
 215           if (vd.asGlobal) compileError(vd.locs[idx], "conflicting variable '", name, "' declaration (previous at ", vdecls[name].toStringNoFile, ")");
 216         } else if (name in globals) {
 217           if (!vd.asGlobal) compileError(vd.locs[idx], "conflicting variable '", name, "' declaration (previous at ", vdecls[name].toStringNoFile, ")");
 218         }
 219         vdecls[name] = vd.locs[idx];
 220         if (vd.asGlobal) {
 221           globals[name] = 0;
 222         } else {
 223           // don't allocate slots for locals here, we can remove some locals due to arguments aliasing later
 224           //firstFreeSlot = allocSlot(vd.locs[idx]);
 225           //locals[name] = cast(ubyte)firstFreeSlot;
 226           //++firstFreeSlot;
 227           locals[name] = 42; // temporary value
 228         }
 229       }
 230     }
 231     return VisitRes.Continue;
 232   });
 233
 234   void findUninitialized () {
 235     bool[string] inited;
 236     bool[string] used;
 237
 238     void processExpr (Node n, bool asAss=false) {
 239       if (n is null) return;
 240       visitNodes(n, (Node nn) {
 241         if (auto n = cast(NodeBinaryAss)nn) {
 242           if (cast(NodeId)n.el is null && cast(NodeDot)n.el is null && cast(NodeIndex)n.el is null) {
 243             compileError(nn.loc, "assignment to rvalue");
 244             return VisitRes.SkipChildren;
 245           }
 246           processExpr(n.er); // it is calculated first
 247           if (auto did = cast(NodeId)n.el) {
 248             inited[did.name] = true;
 249             used[did.name] = true;
 250           } else {
 251             processExpr(n.el, asAss:true);
 252           }
 253           return VisitRes.SkipChildren;
 254         }
 255         if (auto id = cast(NodeId)nn) {
 256           if (argvar(id.name) < 0) {
 257             if (!asAss && id.name in locals && id.name !in inited) {
 258               compileError(nn.loc, "using uninitialized variable; declared at ", vdecls[id.name].toStringNoFile);
 259             }
 260           }
 261           inited[id.name] = true;
 262           used[id.name] = true;
 263           return VisitRes.SkipChildren;
 264         }
 265         if (auto n = cast(NodeFCall)nn) {
 266           if (cast(NodeId)n.fe is null) compileError(n.loc, "invalid function call");
 267           if (n.args.length > 16) compileError(n.loc, "too many arguments in function call");
 268           foreach (immutable idx, Node a; n.args) {
 269             // no assignments allowed there
 270             processExpr(a);
 271           }
 272           return VisitRes.SkipChildren;
 273         }
 274         return VisitRes.Continue;
 275       });
 276     }
 277
 278     void processStatement (Node nn) {
 279       if (nn is null) return;
 280       return selectNode!void(nn,
 281         (NodeVarDecl n) {},
 282         (NodeBlock n) {
 283           foreach (Node st; n.stats) {
 284             if (cast(NodeStatementBreakCont)st !is null) break;
 285             processStatement(st);
 286             if (cast(NodeReturn)st !is null) break;
 287           }
 288         },
 289         (NodeStatementEmpty n) {},
 290         (NodeStatementExpr n) { processExpr(n.e); },
 291         (NodeReturn n) { processExpr(n.e); },
 292         (NodeWith n) {
 293           processExpr(n.e); // can't contain assignments
 294           // body can be executed zero times, so...
 295           auto before = inited.dup;
 296           processStatement(n.ebody);
 297           inited = before;
 298         },
 299         (NodeIf n) {
 300           processExpr(n.ec);
 301           auto before = inited.dup;
 302           processStatement(n.et);
 303           auto tset = inited.dup;
 304           inited = before.dup;
 305           processStatement(n.ef);
 306           // now copy to `before` all items that are set both in `tset` and in `inited`
 307           foreach (string name; inited.byKey) {
 308             if (name in tset) before[name] = true;
 309           }
 310           inited = before;
 311         },
 312         (NodeStatementBreakCont n) {},
 313         (NodeFor n) {
 314           processExpr(n.einit);
 315           // "next" and "cond" can't contain assignments, so it's safe here
 316           processExpr(n.econd);
 317           processExpr(n.enext);
 318           // yet body can be executed zero times, so...
 319           auto before = inited.dup;
 320           processStatement(n.ebody);
 321           inited = before;
 322         },
 323         (NodeWhile n) {
 324           // "cond" can't contain assignments, so it's safe here
 325           processExpr(n.econd);
 326           // yet body can be executed zero times, so...
 327           auto before = inited.dup;
 328           processStatement(n.ebody);
 329           inited = before;
 330         },
 331         (NodeDoUntil n) {
 332           // "cond" can't contain assignments, so it's safe here
 333           processExpr(n.econd);
 334           // body is guaranteed to execute at least one time
 335           processStatement(n.ebody);
 336         },
 337         (NodeRepeat n) {
 338           // "count" can't contain assignments, so it's safe here
 339           processExpr(n.ecount);
 340           // yet body can be executed zero times, so...
 341           auto before = inited.dup;
 342           processStatement(n.ebody);
 343           inited = before;
 344         },
 345         (NodeSwitch n) {
 346           // "expr" can't contain assignments, so it's safe here
 347           processExpr(n.e);
 348           auto before = inited.dup;
 349           foreach (ref ci; n.cases) {
 350             processExpr(ci.e); // can't contain assignments
 351             // and this one can
 352             if (ci.st !is null) {
 353               inited = before.dup;
 354               processStatement(ci.st);
 355             }
 356           }
 357           inited = before;
 358         },
 359         () { assert(0, "unimplemented node: "~typeid(nn).name); },
 360       );
 361     }
 362
 363     processStatement(fn.ebody);
 364
 365     // now show (and remove) unused locals
 366     //static struct Info { Loc loc; string name; }
 367     //Info[] unusedLocs;
 368     foreach (string name; locals.keys) {
 369       if (name !in used) {
 370         { import std.stdio; writeln("removing unused local '", name, "'"); }
 371         //unusedLocs ~= Info(vdecls[name], name);
 372         locals.remove(name);
 373       }
 374     }
 375     //import std.algorithm : sort;
 376     //unusedLocs.sort!((ref a, ref b) { if (a.loc.line < b.loc.line) return true; if (a.loc.line > b.loc.line) return false; return (a.loc.col < b.loc.col); });
 377     //foreach (ref nfo; unusedLocs) compileError(nfo.loc, "unused local '", nfo.name, "'");
 378   }
 379
 380   findUninitialized();
 381
 382   /* here we will do very simple analysis for vm.code like
 383    *   var m, n;
 384    *   m = argument0;
 385    *   n = argument1;
 386    *   ...no `arument0` and `argument1` usage after this point
 387    * we can just alias `m` to `arument0`, and `n` to `argument1` then
 388    */
 389
 390   string[16] aaliases; // argument aliases
 391   {
 392     uint firstBadStatement = 0;
 393     foreach (immutable idx, Node st; fn.ebody.stats) {
 394       if (cast(NodeStatementEmpty)st || cast(NodeStatementExpr)st || cast(NodeVarDecl)st) {
 395         firstBadStatement = cast(uint)idx+1;
 396       } else {
 397         break;
 398       }
 399     }
 400     if (firstBadStatement > 0) {
 401       bool[string] varsused;
 402       // scan statements, find assignments
 403       foreach (immutable idx, Node st; fn.ebody.stats[0..firstBadStatement]) {
 404         if (auto se = cast(NodeStatementExpr)st) {
 405           if (auto ass = cast(NodeBinaryAss)se.e) {
 406             // wow, assignment
 407             auto lv = cast(NodeId)ass.el;
 408             auto rv = cast(NodeId)ass.er;
 409             if (lv !is null && rv !is null) {
 410               // "a = b"
 411               { import std.stdio : stderr; stderr.writeln("found assignment: '", lv.name, "' = '", rv.name, "'"); }
 412               if (argvar(rv.name) >= 0 && argvar(lv.name) < 0) {
 413                 // "a = argumentx"
 414                 if (lv.name in varsused || rv.name in varsused) continue; // no wai
 415                 if (lv.name !in locals) continue; // not a local
 416                 auto ai = argvar(rv.name);
 417                 if (aaliases[ai].length && aaliases[ai] != lv.name) continue; // already have an alias (TODO)
 418                 aaliases[ai] = lv.name; // possible alias
 419               } else {
 420                 // check for reassignment
 421                 if (lv.name !in varsused) {
 422                   // not used before, but used now; remove it from aliases
 423                   foreach (ref an; aaliases) if (an == lv.name) an = null;
 424                   varsused[lv.name] = true;
 425                 }
 426               }
 427             }
 428           }
 429         }
 430       }
 431       // now check if we have any assignment to aliased argument
 432       foreach (immutable idx, string an; aaliases) {
 433         if (an.length == 0) continue;
 434         visitNodes(fn.ebody, (Node n) {
 435           if (auto ass = cast(NodeBinaryAss)n) {
 436             if (auto id = cast(NodeId)ass.el) {
 437               auto ai = argvar(id.name);
 438               if (ai >= 0) aaliases[idx] = null;
 439               return VisitRes.Stop;
 440             }
 441           }
 442           return VisitRes.Continue;
 443         });
 444       }
 445       // remove aliases from locals (we don't need slots for 'em)
 446       foreach (immutable idx, string an; aaliases) {
 447         if (an.length == 0) continue;
 448         locals.remove(an);
 449       }
 450       // dump aliases
 451       {
 452         import std.stdio : stderr;
 453         foreach (immutable idx, string an; aaliases) {
 454           if (an.length) stderr.writeln("'argument", idx, "' is aliased to '", an, "'");
 455         }
 456       }
 457     }
 458   }
 459
 460   // now assign slots to locals
 461   foreach (string name; locals.keys) {
 462     firstFreeSlot = allocSlot(vdecls[name]);
 463     locals[name] = cast(ubyte)firstFreeSlot;
 464     ++firstFreeSlot;
 465   }
 466
 467   void emitPLit (Loc loc, ubyte dest, Real v) {
 468     uint vpidx = uint.max;
 469     if (v.isReal) {
 470       // number
 471       import core.stdc.math : lrint;
 472       if (lrint(v) == v && lrint(v) >= short.min && lrint(v) <= short.max) {
 473         emit2Bytes(Op.ilit, dest, cast(short)lrint(v));
 474         return;
 475       }
 476       //FIXME: speed it up!
 477       foreach (immutable idx, Real vp; vm.vpool) if (vp == v) { vpidx = cast(uint)idx; break; }
 478     } else if (v.isString) {
 479       // string
 480       //FIXME: speed it up!
 481       auto sid = v.getStrId;
 482       foreach (immutable idx, Real vp; vm.vpool) if (vp.isString && vp.getStrId == sid) { vpidx = cast(uint)idx; break; }
 483     } else {
 484       assert(0, "wtf?!");
 485     }
 486     if (vpidx == uint.max) {
 487       vpidx = cast(uint)vm.vpool.length;
 488       if (vpidx >= 0xffffff) compileError(loc, "too many constants");
 489       vm.vpool ~= v;
 490     }
 491     if (vpidx < ushort.max) {
 492       emit2Bytes(Op.plit, dest, cast(ushort)vpidx);
 493     } else {
 494       // special form
 495       emit2Bytes(Op.plit, dest, cast(short)ushort.max);
 496       emit3Bytes(Op.skip, vpidx);
 497     }
 498   }
 499
 500   uint allocStrConst (string s, Loc loc) { return newInternalStr(s); }
 501
 502   int varSlot (string name) {
 503     auto avn = argvar(name);
 504     if (avn >= 0) return VM.Slot.Argument0+avn;
 505     switch (name) {
 506       case "self": return VM.Slot.Self;
 507       case "other": return VM.Slot.Other;
 508       default:
 509     }
 510     // argument aliases
 511     foreach (immutable idx, string an; aaliases) if (an == name) return cast(int)VM.Slot.Argument0+idx;
 512     // locals
 513     if (auto v = name in locals) return *v;
 514     return -1;
 515   }
 516
 517   // options for expression
 518   static struct EOpts {
 519     int ddest = -1; // >=0: put result in this slot
 520     bool dna; // use `ddest` only if we don't need to allocate more slots
 521   }
 522
 523   // returns dest slot
 524   // can put value in desired dest
 525   ubyte compileExpr (Node nn, int ddest=-1, bool wantref=false) {
 526     ubyte doBinOp (Op op, NodeBinary n) {
 527       auto dest = allocSlot(n.loc, ddest);
 528       auto o0 = compileExpr(n.el);
 529       auto o1 = compileExpr(n.er);
 530       emit(op, dest, o0, o1);
 531       freeSlot(o0);
 532       freeSlot(o1);
 533       return dest;
 534     }
 535
 536     ubyte doUnOp (Op op, NodeUnary n) {
 537       auto dest = allocSlot(n.loc, ddest);
 538       auto o0 = compileExpr(n.e);
 539       emit(op, dest, o0);
 540       freeSlot(o0);
 541       return dest;
 542     }
 543
 544     nn.pcs = pc;
 545     scope(exit) nn.pce = pc;
 546     return selectNode!ubyte(nn,
 547       (NodeLiteralNum n) {
 548         auto dest = allocSlot(n.loc, ddest);
 549         emitPLit(n.loc, dest, n.val);
 550         return dest;
 551       },
 552       (NodeLiteralStr n) {
 553         auto dest = allocSlot(n.loc, ddest);
 554         auto sid = allocStrConst(n.val, n.loc);
 555         emitPLit(n.loc, dest, buildStrId(sid));
 556         return dest;
 557       },
 558       (NodeUnaryParens n) => compileExpr(n.e, ddest, wantref),
 559       (NodeUnaryNot n) => doUnOp(Op.lnot, n),
 560       (NodeUnaryNeg n) => doUnOp(Op.neg, n),
 561       (NodeUnaryBitNeg n) => doUnOp(Op.bneg, n),
 562       (NodeBinaryAss n) {
 563         // assignment
 564         if (cast(NodeId)n.el is null && cast(NodeDot)n.el is null && cast(NodeIndex)n.el is null) compileError(n.loc, "assignment to rvalue");
 565         if (auto did = cast(NodeId)n.el) {
 566           // try to put value directly to variable slot
 567           auto vdst = varSlot(did.name);
 568           if (vdst >= 0) {
 569             auto dest = compileExpr(n.er, ddest:vdst);
 570             freeSlot(dest);
 571             return 0;
 572           }
 573         }
 574         // normal assignment
 575         auto src = compileExpr(n.er);
 576         auto dest = compileExpr(n.el, wantref:true);
 577         //emit(Op.rstore, dest, src);
 578         switch (vm.code[pc-1].opCode) {
 579           case Op.lref: // load slot reference to dest; op0: slot number
 580             opReplace(pc-1, Op.lstore, src); // store value *from* dest into local slot; op0: slot number
 581             break;
 582           case Op.fref: // load field reference; op0: obj id; op1: int! reg (field id); can create fields
 583             opReplace(pc-1, Op.fstore, src); // store value *from* dest into field; op0: obj id; op1: int! reg (field id); can create fields
 584             break;
 585           case Op.i1ref: // load indexed reference; op0: varref; op1: index; can create arrays
 586             opReplace(pc-1, Op.i1store, src); // store value *from* dest into indexed reference; op0: varref; op1: index; can create arrays
 587             break;
 588           case Op.i2ref: // load indexed reference; op0: varref; op1: first index; (op1+1): second index; can create arrays
 589             opReplace(pc-1, Op.i2store, src); // store value *from* dest into indexed reference; op0: varref; op1: first index; (op1+1): second index; can create arrays
 590             break;
 591           default: assert(0, "internal compiler error");
 592         }
 593         freeSlot(src);
 594         freeSlot(dest);
 595         return 0;
 596       },
 597       (NodeBinaryAdd n) => doBinOp(Op.add, n),
 598       (NodeBinarySub n) => doBinOp(Op.sub, n),
 599       (NodeBinaryMul n) => doBinOp(Op.mul, n),
 600       (NodeBinaryRDiv n) => doBinOp(Op.rdiv, n),
 601       (NodeBinaryDiv n) => doBinOp(Op.div, n),
 602       (NodeBinaryMod n) => doBinOp(Op.mod, n),
 603       (NodeBinaryBitOr n) => doBinOp(Op.bor, n),
 604       (NodeBinaryBitAnd n) => doBinOp(Op.band, n),
 605       (NodeBinaryBitXor n) => doBinOp(Op.bxor, n),
 606       (NodeBinaryLShift n) => doBinOp(Op.shl, n),
 607       (NodeBinaryRShift n) => doBinOp(Op.shr, n),
 608       (NodeBinaryLess n) => doBinOp(Op.lt, n),
 609       (NodeBinaryLessEqu n) => doBinOp(Op.le, n),
 610       (NodeBinaryGreat n) => doBinOp(Op.gt, n),
 611       (NodeBinaryGreatEqu n) => doBinOp(Op.ge, n),
 612       (NodeBinaryEqu n) => doBinOp(Op.eq, n),
 613       (NodeBinaryNotEqu n) => doBinOp(Op.ne, n),
 614       (NodeBinaryLogOr n) => doBinOp(Op.lor, n),
 615       (NodeBinaryLogAnd n) => doBinOp(Op.land, n),
 616       (NodeBinaryLogXor n) => doBinOp(Op.lxor, n),
 617       (NodeFCall n) {
 618         if (cast(NodeId)n.fe is null) compileError(n.loc, "invalid function call");
 619         if (n.args.length > 16) compileError(n.loc, "too many arguments in function call");
 620         auto dest = allocSlot(n.loc, ddest);
 621         // preallocate frame
 622         // we can do this, as current slot allocation scheme guarantees
 623         // that we won't have used slots with higher numbert after compiling
 624         // argument expressions
 625         // `reserveCallSlots()` won't mark slots as used
 626         auto frameSize = cast(uint)n.args.length+VM.Slot.Argument0;
 627         auto fcs = reserveCallSlots(n.loc, frameSize+1); // +1 for script id
 628         // put arguments where we want 'em to be
 629         foreach (immutable idx, Node a; n.args) {
 630           // reserve result slot, so it won't be overwritten
 631           assert(!slots[fcs+VM.Slot.Argument0+idx]);
 632           slots[fcs+VM.Slot.Argument0+idx] = true;
 633           auto dp = compileExpr(a, fcs+VM.Slot.Argument0+idx);
 634           if (dp != fcs+VM.Slot.Argument0+idx) assert(0, "internal compiler error");
 635         }
 636         // now free result slots
 637         foreach (immutable idx; 0..n.args.length) freeSlot(cast(ubyte)(fcs+VM.Slot.Argument0+idx));
 638         // make sure that our invariant holds
 639         if (reserveCallSlots(n.loc, 1) != fcs) assert(0, "internal compiler error");
 640         // put script id
 641         // emit call
 642         uint sid = sid4name((cast(NodeId)n.fe).name);
 643         emit2Bytes(Op.xlit, cast(ubyte)(fcs+VM.Slot.Argument0+n.args.length), cast(short)sid);
 644         emit(Op.call, dest, fcs, cast(ubyte)n.args.length);
 645         return dest;
 646       },
 647       // variable access
 648       (NodeId n) {
 649         // keep track of maximum argument we've seen
 650         if (maxArgUsed < 15) {
 651           if (auto ai = argvar(n.name)) {
 652             if (ai > maxArgUsed) maxArgUsed = cast(ubyte)ai;
 653           }
 654         }
 655         if (wantref) {
 656           // load reference
 657           auto dest = allocSlot(n.loc, ddest);
 658           auto vsl = varSlot(n.name);
 659           if (vsl >= 0) {
 660             // this is local variable
 661             emit(Op.lref, dest, cast(ubyte)vsl);
 662           } else {
 663             // this is `self` field
 664             auto fid = allocSlot(n.loc);
 665             emit2Bytes(Op.ilit, fid, cast(short)allocateFieldId(n.name));
 666             freeSlot(fid);
 667             emit(Op.fref, dest, VM.Slot.Self, fid);
 668           }
 669           return dest;
 670         } else {
 671           // load value
 672           auto vsl = varSlot(n.name);
 673           if (vsl >= 0) {
 674             // this is local variable
 675             if (ddest < 0) return vsl; // just use this slot directly
 676             auto dest = allocSlot(n.loc, ddest);
 677             if (dest == vsl) return dest;
 678             emit(Op.copy, dest, cast(ubyte)vsl, 1);
 679             return dest;
 680           } else {
 681             // this is `self` field
 682             auto dest = allocSlot(n.loc, ddest);
 683             auto fid = allocSlot(n.loc);
 684             emit2Bytes(Op.ilit, fid, cast(short)allocateFieldId(n.name));
 685             freeSlot(fid);
 686             emit(Op.fval, dest, VM.Slot.Self, fid);
 687             return dest;
 688           }
 689         }
 690         assert(0);
 691       },
 692       (NodeDot n) {
 693         // field access
 694         auto aop = (wantref ? Op.fref : Op.fval);
 695         auto dest = allocSlot(n.loc, ddest);
 696         if (auto oid = cast(NodeId)n.e) {
 697           // we know object name directly
 698           if (oid.name == "self" || oid.name == "other" || oid.name == "global") {
 699             // well-known name
 700             auto fid = allocSlot(n.loc);
 701             emit2Bytes(Op.ilit, fid, cast(short)allocateFieldId(n.name));
 702             if (oid.name == "global") {
 703               auto oids = allocSlot(n.loc);
 704               emit2Bytes(Op.ilit, oids, -666);
 705               freeSlot(oids);
 706               emit(aop, dest, oids, fid);
 707             } else {
 708               emit(aop, dest, (oid.name == "self" ? VM.Slot.Self : VM.Slot.Other), fid);
 709             }
 710             freeSlot(fid);
 711             return dest;
 712           }
 713         }
 714         // this is some complex expression
 715         auto fid = allocSlot(n.loc);
 716         emit2Bytes(Op.ilit, fid, cast(short)allocateFieldId(n.name));
 717         auto oids = compileExpr(n.e);
 718         freeSlot(oids);
 719         emit(aop, dest, oids, fid);
 720         return dest;
 721       },
 722       (NodeIndex n) {
 723         assert(n.ei0 !is null);
 724         auto dest = allocSlot(n.loc, ddest);
 725         if (n.ei1 is null) {
 726           // one index
 727           if (auto id = cast(NodeId)n.e) {
 728             auto vid = varSlot(id.name);
 729             if (vid >= 0) {
 730               // this is local variable
 731               compileError(n.loc, "indexing locals is not supported yet");
 732               assert(0);
 733             }
 734           }
 735           // not a local
 736           auto i0 = compileExpr(n.ei0);
 737           auto refs = compileExpr(n.e, wantref:true);
 738           emit((wantref ? Op.i1ref : Op.i1val), dest, refs, i0);
 739           freeSlot(refs);
 740           freeSlot(i0);
 741         } else {
 742           // two indexes
 743           auto islots = allocSlots(n.loc, 2);
 744           auto i0 = compileExpr(n.ei0, islots);
 745           assert(i0 == islots);
 746           auto i1 = compileExpr(n.ei1, islots+1);
 747           assert(i0 == islots+1);
 748           auto refs = compileExpr(n.e, wantref:true);
 749           emit((wantref ? Op.i2ref : Op.i2val), dest, refs, islots);
 750           freeSlot(refs);
 751           freeSlot(i0);
 752           freeSlot(i1);
 753         }
 754         return dest;
 755       },
 756       () { assert(0, "unimplemented node: "~typeid(nn).name); },
 757     );
 758   }
 759
 760   uint breakChain; // current jump chain for `break`
 761   uint contChain; // current jump chain for `continue`
 762   bool contChainIsAddr; // is `contChain` an address, not a chain?
 763
 764   void compile (Node nn) {
 765     assert(nn !is null);
 766     nn.pcs = pc;
 767     scope(exit) nn.pce = pc;
 768     return selectNode!void(nn,
 769       (NodeVarDecl n) {},
 770       (NodeBlock n) {
 771         foreach (Node st; n.stats) compile(st);
 772       },
 773       (NodeStatementEmpty n) {},
 774       (NodeStatementExpr n) {
 775         freeSlot(compileExpr(n.e));
 776       },
 777       (NodeReturn n) {
 778         if (n.e is null) {
 779           emit2Bytes(Op.ilit, 0, 0);
 780           emit(Op.ret, 0);
 781         } else {
 782           auto dest = compileExpr(n.e);
 783           emit(Op.ret, dest);
 784           freeSlot(dest);
 785         }
 786       },
 787       (NodeWith n) {
 788         assert(0);
 789       },
 790       (NodeIf n) {
 791         auto cs = compileExpr(n.ec);
 792         freeSlot(cs); // yep, free it here
 793         emit(Op.xtrue, cs);
 794         uint jfc = 0;
 795         // simple optimization
 796         jfc = emitJumpChain(0, Op.jump);
 797         compile(n.et);
 798         if (n.ef !is null) {
 799           auto exc = emitJumpChain(0, Op.jump);
 800           fixJumpChain(jfc, pc);
 801           jfc = exc;
 802           compile(n.ef);
 803         }
 804         fixJumpChain(jfc, pc);
 805       },
 806       (NodeStatementBreak n) {
 807         breakChain = emitJumpChain(breakChain);
 808       },
 809       (NodeStatementContinue n) {
 810         if (contChainIsAddr) {
 811           emitJumpTo(contChain);
 812         } else {
 813           contChain = emitJumpChain(contChain);
 814         }
 815       },
 816       (NodeFor n) {
 817         freeSlot(compileExpr(n.einit));
 818         // generate vm.code like this:
 819         //   jump to "continue"
 820         //   body
 821         //  continue:
 822         //   cond
 823         //   jumptostart
 824         auto obc = breakChain;
 825         auto occ = contChain;
 826         auto cca = contChainIsAddr;
 827         scope(exit) { breakChain = obc; contChain = occ; contChainIsAddr = cca; }
 828         // jump to "continue"
 829         contChain = emitJumpChain(0); // start new chain
 830         contChainIsAddr = false;
 831         breakChain = 0; // start new chain
 832         auto stpc = pc;
 833         // increment
 834         freeSlot(compileExpr(n.enext));
 835         // body
 836         compile(n.ebody);
 837         // fix "continue"
 838         fixJumpChain(contChain, pc);
 839         // condition
 840         auto dest = compileExpr(n.econd);
 841         freeSlot(dest); // yep, right here
 842         emit(Op.xfalse, dest); // skip jump on false
 843         emitJumpTo(stpc);
 844         // "break" is here
 845         fixJumpChain(breakChain, pc);
 846       },
 847       (NodeWhile n) {
 848         // nothing fancy
 849         auto obc = breakChain;
 850         auto occ = contChain;
 851         auto cca = contChainIsAddr;
 852         scope(exit) { breakChain = obc; contChain = occ; contChainIsAddr = cca; }
 853         // new break chain
 854         breakChain = 0;
 855         // "continue" is here
 856         contChain = pc;
 857         contChainIsAddr = true;
 858         // condition
 859         auto dest = compileExpr(n.econd);
 860         freeSlot(dest); // yep, right here
 861         emit(Op.xfalse, dest); // skip jump on false
 862         breakChain = emitJumpChain(breakChain); // get out of here
 863         // body
 864         compile(n.ebody);
 865         // and again
 866         emitJumpTo(contChain);
 867         // "break" is here
 868         fixJumpChain(breakChain, pc);
 869       },
 870       (NodeDoUntil n) {
 871         // nothing fancy
 872         auto obc = breakChain;
 873         auto occ = contChain;
 874         auto cca = contChainIsAddr;
 875         scope(exit) { breakChain = obc; contChain = occ; contChainIsAddr = cca; }
 876         auto stpc = pc;
 877         // new break chain
 878         breakChain = 0;
 879         // new continue chain
 880         contChain = 0;
 881         contChainIsAddr = false;
 882         // body
 883         compile(n.ebody);
 884         // "continue" is here
 885         fixJumpChain(contChain, pc);
 886         // condition
 887         auto dest = compileExpr(n.econd);
 888         freeSlot(dest); // yep, right here
 889         emit(Op.xfalse, dest); // skip jump on false
 890         // and again
 891         emitJumpTo(stpc);
 892         // "break" is here
 893         fixJumpChain(breakChain, pc);
 894       },
 895       (NodeRepeat n) {
 896         // allocate node for counter
 897         auto cnt = compileExpr(n.ecount);
 898         // allocate "1" constant (we will need it)
 899         auto one = allocSlot(n.loc);
 900         emit2Bytes(Op.ilit, one, cast(short)1);
 901         // alice in chains
 902         auto obc = breakChain;
 903         auto occ = contChain;
 904         auto cca = contChainIsAddr;
 905         scope(exit) { breakChain = obc; contChain = occ; contChainIsAddr = cca; }
 906         // new break chain
 907         breakChain = 0;
 908         // "continue" is here
 909         contChain = pc;
 910         contChainIsAddr = true;
 911         // check and decrement counter
 912         auto ck = allocSlot(n.ecount.loc);
 913         freeSlot(ck); // we don't need that slot anymore, allow body to reuse it
 914         emit(Op.ge, ck, cnt, one);
 915         emit(Op.xtrue, ck);
 916         breakChain = emitJumpChain(breakChain); // get out of here
 917         // decrement counter in-place
 918         emit(Op.sub, cnt, cnt, one);
 919         // body
 920         compile(n.ebody);
 921         // and again
 922         emitJumpTo(contChain);
 923         // "break" is here
 924         fixJumpChain(breakChain, pc);
 925         // free used slots
 926         freeSlot(one);
 927         freeSlot(cnt);
 928       },
 929       (NodeSwitch n) {
 930         // switch expression
 931         auto expr = compileExpr(n.e);
 932         if (n.cases.length) {
 933           // has some cases
 934           uint defaultBodyAddr = 0; // address of "default" node body (even if it is empty)
 935           uint lastFalltrhuJump = 0; // this is the address of the Op.jump at the end of the previous case node
 936           uint lastCaseSkipJumpAddr = 0; // this is the address of the Op.jump at the failed condition of the previous case node
 937           // new "break" chain
 938           auto obc = breakChain;
 939           scope(exit) breakChain = obc;
 940           breakChain = 0;
 941           // now generate vm.code for case nodes, skipping "default" by the way
 942           foreach (immutable idx, ref ci; n.cases) {
 943             uint nodeSkipChain = 0;
 944             // check condition
 945             if (ci.e !is null) {
 946               // jump here from the last failed condition
 947               fixJumpChain(lastCaseSkipJumpAddr, pc);
 948               auto cond = compileExpr(ci.e);
 949               // trick: reuse "cond" slot
 950               freeSlot(cond);
 951               emit(Op.eq, cond, cond, expr);
 952               emit(Op.xtrue, cond);
 953               // new skip chain
 954               lastCaseSkipJumpAddr = emitJumpChain(0);
 955             } else {
 956               // this is default node, jump over it
 957               nodeSkipChain = emitJumpChain(0);
 958               // and save info
 959               defaultBodyAddr = pc;
 960             }
 961             // fix fallthru jump
 962             fixJumpChain(lastFalltrhuJump, pc);
 963             // the body is here
 964             compile(ci.st);
 965             // new fallthru chain
 966             lastFalltrhuJump = (idx < n.cases.length-1 ? emitJumpChain(0) : 0);
 967             // fix "default skip" chain
 968             fixJumpChain(nodeSkipChain, pc);
 969           }
 970           // we can free expression slot right here
 971           freeSlot(expr);
 972           // do we have default node?
 973           if (defaultBodyAddr) {
 974             // jump there from the last failed condition
 975             fixJumpChain(lastCaseSkipJumpAddr, defaultBodyAddr);
 976           } else {
 977             // jump here from the last failed condition
 978             fixJumpChain(lastCaseSkipJumpAddr, pc);
 979           }
 980           // fix last fallthru jump
 981           fixJumpChain(lastFalltrhuJump, pc);
 982           // fix "break" chain
 983           fixJumpChain(breakChain, pc);
 984         } else {
 985           freeSlot(expr);
 986         }
 987       },
 988       () { assert(0, "unimplemented node: "~typeid(nn).name); },
 989     );
 990   }
 991
 992   if (auto sid = fn.name in vm.scripts) {
 993     if (vm.scriptPCs[*sid] < 0) return; // can't override built-in function
 994   }
 995
 996   uint sid = sid4name(fn.name);
 997   /*debug(vm_exec)*/ { import std.stdio; writeln("compiling '", fn.name, "' (", sid, ")..."); }
 998   auto startpc = emit(Op.enter);
 999   fn.pcs = pc;
1000   compile(fn.ebody);
1001   emit(Op.ret);
1002   fn.pce = pc;
1003   // patch enter
1004   vm.code[startpc] = (locals.length<<24)|((maxUsedSlot+1)<<16)|(maxArgUsed<<8)|cast(ubyte)Op.enter;
1005   vm.scriptPCs[sid] = startpc;
1006   vm.scriptASTs[sid] = fn;
1007 }