Skip to content

Commit

Permalink
Extend bytecode format to preserve the nesting structure of the origi…
Browse files Browse the repository at this point in the history 
…nal source

New jmp opcodes indicate their eventual merge points (post-dominance
frontiers).  Control flow joins not happen at phi nodes.
  • Loading branch information
@cscott
cscott committed Feb 14, 2020
1 parent 5ee21a4 commit 0cad445
Show file tree
Hide file tree
Showing 3 changed files with 51 additions and 24 deletions.
30 changes: 19 additions & 11 deletions bcompile.js
View file
Original file line number Diff line number Diff line change
Expand Up @@ -470,11 +470,12 @@ define(["text!bcompile.js", "bytecode-table"], function make_bcompile(bcompile_s
state.bcompile_expr(this.first);
state.emit("dup");
state.emit("un_not");
state.emit("jmp_unless", mergeLabel);
state.emit("jmp_unless", mergeLabel, mergeLabel);
sd_before = state.current_func.stack_depth;
state.emit("pop");
state.bcompile_expr(this.second);
state.set_label(mergeLabel);
state.emit("phi");
sd_after = state.current_func.stack_depth;
assert(sd_before === sd_after, this);
});
Expand All @@ -486,11 +487,12 @@ define(["text!bcompile.js", "bytecode-table"], function make_bcompile(bcompile_s
// short circuit operator
state.bcompile_expr(this.first);
state.emit("dup");
state.emit("jmp_unless", mergeLabel);
state.emit("jmp_unless", mergeLabel, mergeLabel);
sd_before = state.current_func.stack_depth;
state.emit("pop");
state.bcompile_expr(this.second);
state.set_label(mergeLabel);
state.emit("phi");
sd_after = state.current_func.stack_depth;
assert(sd_before === sd_after, this);
});
Expand Down Expand Up @@ -551,7 +553,7 @@ define(["text!bcompile.js", "bytecode-table"], function make_bcompile(bcompile_s
var falseLabel = state.new_label();
var mergeLabel = state.new_label();
state.bcompile_expr(this.first);
state.emit("jmp_unless", falseLabel);
state.emit("jmp_unless", falseLabel, mergeLabel);

// "true" case
sd_before = state.current_func.stack_depth;
Expand All @@ -564,6 +566,7 @@ define(["text!bcompile.js", "bytecode-table"], function make_bcompile(bcompile_s
state.set_label(falseLabel);
state.bcompile_expr(this.third);
state.set_label(mergeLabel);
state.emit("phi");
assert(state.current_func.stack_depth === sd_after, this);
});
ternary("(", function(state) {
Expand Down Expand Up @@ -616,19 +619,18 @@ define(["text!bcompile.js", "bytecode-table"], function make_bcompile(bcompile_s
});
});
stmt("if", function(state) {
var falseLabel = state.new_label();
var mergeLabel = state.new_label();
var falseLabel = this.third ? state.new_label() : mergeLabel;
state.bcompile_expr(this.first);
state.emit("jmp_unless", falseLabel);
state.emit("jmp_unless", falseLabel, mergeLabel);
state.bcompile_stmt(this.second);
if (this.third) {
var mergeLabel = state.new_label();
state.emit("jmp", mergeLabel);
state.set_label(falseLabel);
state.bcompile_stmt(this.third);
state.set_label(mergeLabel);
} else {
state.set_label(falseLabel);
}
state.set_label(mergeLabel);
state.emit("phi");
});
stmt("return", function(state) {
if (this.first) {
Expand All @@ -648,14 +650,20 @@ define(["text!bcompile.js", "bytecode-table"], function make_bcompile(bcompile_s
var endLabel = state.new_label();
state.push_loop_label(endLabel);

state.emit("jmp", testLabel);
// Communicate loop boundaries to latter stages of the compiler
state.emit("jmp_into_loop", testLabel, endLabel);
state.set_label(startLabel);
state.bcompile_stmt(this.second);
state.set_label(testLabel);
state.emit("phi");
state.bcompile_expr(this.first);
state.emit("un_not");
state.emit("jmp_unless", startLabel);
// 2nd arg to jmp_unless indicates that this is the loop condition
// by referencing the active endLabel for the loop. Otherwise
// jmp_unless would be compiled as a balanced if/then/else
state.emit("jmp_unless", startLabel, endLabel);
state.set_label(endLabel);
state.emit("phi");

state.pop_loop_label();
});
Expand Down
4 changes: 4 additions & 0 deletions binterp.js
View file
Original file line number Diff line number Diff line change
Expand Up @@ -296,10 +296,14 @@ define(["text!binterp.js", "bytecode-table"/*, "!html-escape"*/], function make_
dispatch.jmp = branch(function(new_pc) {
return new_pc;
});
dispatch.jmp_into_loop = dispatch.jmp;
dispatch.jmp_unless = branch(function(new_pc) {
var condition = this.stack.pop();
return condition ? this.pc : new_pc;
});
dispatch.phi = function() {
/* no op */
};

// stack manipulation
dispatch.pop = function() {
Expand Down
41 changes: 28 additions & 13 deletions bytecode-table.js
View file
Original file line number Diff line number Diff line change
Expand Up @@ -47,11 +47,18 @@ define(['text!bytecode-table.js'],function make_bytecode_table(bytecode_table_so
return " "+idx+" /* "+state.literals[idx]+" */";
};
var print_label = function(state, bytecode, pc) {
var lbl = bytecode[pc+1];
if (typeof(lbl) !== "number") {
lbl = lbl.label;
var result = "";
var i = 0;
while (i < this.args) {
result += " ";
var lbl = bytecode[pc+1];
if (typeof(lbl) !== "number") {
lbl = lbl.label;
}
result += lbl;
i += 1;
}
return " "+lbl;
return result;
};
// define the bytecodes for the js virtual machine
// name, args, stackpop, stackpush
Expand Down Expand Up @@ -111,17 +118,25 @@ define(['text!bytecode-table.js'],function make_bytecode_table(bytecode_table_so
// unconditional branch
// argument #0 is the jump target
bc("jmp", 1, 0, 0, print_label);
// Identical to `jmp`, but hints that we're jumping into a loop body
// argument #0 is the jump target, a phi marking the top of the loop
// argument #1 hints the label of the phi marking the loop exit
bc("jmp_into_loop", 2, 0, 0, print_label);
// conditional branch
// argument #0 is the label to jump if the top of the stack is true
bc("jmp_unless", 1, 1, 0, print_label);
// argument #0 is the label to jump to if the top of the stack is true
// argument #1 hints the label of the phi marking the eventual merge point
// (hint allows you to compile to balanced control flow structures)
bc("jmp_unless", 2, 1, 0, print_label);
// This is a no-op, but it marks a control-flow merge after a branch/loop
bc("phi", 0, 0, 0);

// stack manipulation
bc("pop", 0, 1, 0); // ab -> b
bc("dup", 0, 1, 2); // a -> aa
bc("2dup", 0, 2, 4); // ab -> abab
bc("over", 0, 2, 3); // ab -> aba
bc("over2", 0, 3, 4); // abc -> abca
bc("swap", 0, 2, 2); // ab -> ba
// stack manipulation TOP <-stack grows <- BOTTOM
bc("pop", 0, 1, 0); // ab.. -> b..
bc("dup", 0, 1, 2); // a.. -> aa..
bc("2dup", 0, 2, 4); // ab.. -> abab..
bc("over", 0, 2, 3); // ab.. -> aba..
bc("over2", 0, 3, 4); // abc.. -> abca..
bc("swap", 0, 2, 2); // ab.. -> ba..

// Unary operators.
bc("un_not", 0, 1, 1);
Expand Down

0 comments on commit 0cad445

Please sign in to comment.