Bck2BrwsrFlow

From APIDesign

Revision as of 08:42, 13 March 2013

Originally Bck2Brwsr simulated control flow (conditional and non-conditional goto statements in method bodies) via for/switch mapping:

var gt = 0;
for (;;) { switch (gt) {
case 0: 
  // some instructions
  // and fallback
case 22: 
  // more instructions 
  // and fallback
case 67: 
  gt = 22; continue; // a loop
}}

This provided almost 1:1 mapping between the ByteCode and its JavaScript representation (the values in the case' statements are positions of the instruction in the ByteCode of each method). However Thomas_Würthinger (the most knowledgable person about V8 I know) warned me that this is not going to be fast. Not only a jump requires assignment of a variable, continue-jump to beginning of the loop and yet another jump to the appropriate case statement. According to Thomas, switch statement is not well optimized in V8 (as he considered it unimportant usecase when he worked on V8). I tried to convince Thomas to provide special V8 optimization for the above construct - but no luck.

Thomas suggested to use Graal's flow analyzer. Especially to look into the GraphBuilderPhase class and see how it creates SSA form (using FrameStateBuilder) and also BciBlockMapping class that is used for creating structured control flow from byte codes. We tried that, but it all seems too connected to the rest of the code and we were unsure how to extract that most easily.

Still, we were in need of some speed up. As a poor man's solution I decided to eliminate the switch and optimze at least forward jumps. Bck2Brwsr now generates:

var gt = 0;
X_0: for (;;) { IF: if (gt <= 0) {
  // some instructions
  // and fallback
}
X_22: for (;;) { IF: if (gt <= 22) {
  // more instructions 
  // and fallback
}
X_67: for (;;) { IF: if (gt <= 67) {
  continue X_22; // loop using direct jump
}
}}} // close all for loops