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