Generating a Minimal JavaScript VM
Specialized for Target Applications
work-in-progress project eJS
Tomoharu Ugawa (Kochi University of Technology)
Hideya Iwasaki (The University of Electro-Communications)

Background• Goal: Make programming of “Internet of Things” easier• Use JavaScript• One of the most popular language• Suitable for rapid prototyping• Matches event-driven programming style of embeddedsystems• Challenge: memory limitation• Reduce VM image size & heap size

Specialization
Key observation• Applications on a particular embedded system are fixed• Each application uses a subset of JavaScript features
Our approach• Generate a specialized VM for each set of applications• Give up supporting other applications
APP1

APP2
VM

Full-set JavaScript VM

APP1

APP2

VMAPP3crash

Subset JavaScript VM for APP1 & APP2

How do we specialize?
• Collect applications requirementson going• Customize VM code related to datatype-based dispatch• VM instruction interpreter• Built-in functions

done

on going• Type conversion internal functions on going• Customize object representation

futurework

Overview of eJSTK
1. Collect requirements of target applications
2. Generate specialized VM source code from the full-set
target applications
VM specification
application
application

requirements

application

profileVM instruction
interpreter

VM instruction
interpreter
specialisebuiltin function
builtin function
builtin function
builtin function
builtin function
builtin function
builtinbuiltin function function
builtin function select & sepcialise

full-set JavaScript VM specification

builtin functionGC

object model

builtin function
builtin function

specialised VM

datatype
identifierdone

on going

1. VM code related to datatype-based dispatchingtarget applications
application
application

requirements

application

profileVM instruction
interpreter

VM instruction
interpreter
specialisebuiltin function
builtin function
builtin function
builtin function
builtin function
builtin function
builtinbuiltin function function
builtin function select & sepcialise

full-set JavaScript VM specification

builtin function

GCobject model

builtin function
builtin function

specialised VM

datatype
identifier

Datatype-based Dispatching Codein VM Instruction Interpreter• Operator overloading• Number + Number = Number• Number + String = Stringdispatching code
switch(type(v1)) {case NUM:
switch (type(v2)) {case NUM:
dst = NUM(val(v1) + val(v2));
break;
case STR:
v1 = ToString(v1);dst = concat(v1, v2);
break;…
}
case STR:…

ADD instruction

Size Reduction by Specialization• Exclude code for unused operations• Simplify dispatching code
switch(type(v1)) {case Num:switch (type(v2)) {case Num:dst = Num(val(v1) + val(v2));
break;
case Str:v1 = toStr(v1);dst = concat(v1, v2);
break;…
}
case Str:…

switch(type(v1)) {case NUM:
dst = NUM(val(v1) + val(v2));
break;
case STR:
dst = concat(v1, v2);
break;}

Specialized Interpreter(Only supports NUM+NUM & STR+STR)
Code for unused operation (NUM + STR)

Specialized Interpreter Generator
Requirements of applications
ADD(NUM, NUM) -> accept
ADD(STR, STR) -> accept
ADD(_, _) -> error
SUB(NUM, NUM) -> accept…
\inst add (Register dst, Value v1, Value v2)\when v1:NUM && v2:NUM \{dst = NUM(val(v1), val(v2));\}\when v1:NUM && v2:STR \{v1 = ToString(v1);dst = concat(v1, v2);\}...

Specification of full-spec JavaScript(application independent)

eJSTK

switch(type(v1)) {case NUM:
dst = NUM(val(v1) + val(v2));
break;
case STR:
dst = concat(v1, v2);
break;}

Generated Interpreter for ADD

Example

Operand 1\when v1:Fixnum && v2:Fixnum \{dst = NUM(val(v1), val(v2));\}\when v1:Fixnum && v2:String \{v1 = ToString(v1);dst = concat(v1, v2);\}

Operand 2

FixnumStringDoubleObject

FixnumIAdd

ToStr1

DAdd

ToStr2StringToStr2

ConcatToStr2

ToStr2

DoubleDAdd

ToStr1

DAdd

ToStr2

ObjectToStr1

ToStr1

ToStr1

ToStr1

Dispatch Table

Apply Requirements

Operand 1

ADD(Fix, Fix) -> accept
ADD(Fix, Str) -> accept
ADD(Fix, Dbl) -> accept
ADD(Fix, Obj) -> error…

Operand 2

FixnumStringDoubleFixnumIAdd

ToStr1

DAdd

String

ToStr2

ConcatDoubleDAdd

ObjectToStr2
DAdd

ToStr1

ObjectPTag

Pointer Tagging

HTagPTag
PayloadOperand 2

FixnumGeneric

Generic

Generic-String

DoubleObjectDAdd

Operand 1

HTag
PTag

HTag

Fixnum-IAdd

ToStr1

Generic

String

ToStr2

ConcatGeneric

DoubleDAdd

Generic

ObjectToStr2
DAdd

ToStr1

Step 1: Construct Decision Tree
Unlabeled edge means wildcard
PT(v1)
FixnumGeneric

PT(v2)FG

GF

HT(v1)
DoubleObjString

DS

DAdd

ToS2

HT(v2)

IAdd

S

D

DSOS

ToS1

DAdd

DAdd

ToS1

ToS2

ConcStep 2: Combine SubgraphsPT(v1)F

GPT(v2)
FGGF

HT(v1)
DOS

DS

DAdd

ToS2

HT(v2)
SIAdd

ToS1

Dcompatible D S
DAdd

DAddToS1

OSToS2Conc

Step 2: Combine SubgraphsPT(v1)
FGPT(v2)
FGGFHT(v1)
DO

S

DS

DAdd

ToS2

HT(v2)SIAdd

ToS1

DDDAdd

SO

SToS1

ToS2

ConcStep 2: Combine Subgraphs
Key idea: Leverage “Don’t care”
PT(v1)
FGPT(v2)

Node 1F

GG

Node 2

HT(v1)
compatible DHT(v2)

1

SIAdd

ToS1

OS

DToS1

DAdd

don’tcare

S

F

DAdd

DS

DAdd

ToS2

2

DDDAddSOSToS1

ToS2

Conc

Step 2: Combine SubgraphsPT(v1)
FGPT(v2)Node 1

F

GG

Node 2HT(v1)
DO

S

DToS1

DAdd

don’tcare

S

F

DAdd

DS

DAdd

ToS2

HT(v2)

IAdd

S

DSO

SToS1

DAdd

ToS1

ToS2

Conc

Step 2: Combine SubgraphsPT(v1)
F

G

PT(v2)F

G

G

F

HT(v1)O,DS

DHT(v2)

IAdd

S

DO

S

ToS1

DAdd

ToS2

Conc

S

Step 3: Shortcut Redundant Nodes
redundant nodePT(v1)F

GPT(v2)F

G

GF

HT(v1)O,DS

DHT(v2)

IAdd

S

DOS

ToS1

DAdd

ToS2

ConcS

Step 3: Shortcut Redundant NodesPT(v1)FG

PT(v2)
FGGF

HT(v1)O,DS

DHT(v2)SIAdd

SDOSToS1

DAdd

ToS2

ConcStep 4: Translate to switch-caseswitch (PT(v1)) {case F:switch (PT(v2)) {case F: IAdd; break;case G:
L1: switch (HT(v2)) {case S: ToS1; break;case D: DAdd; break;} break; }case G:switch (PT(v2)) {Fcase G:switch (HT(v1)) {case O: case D: goto L1;case S:
switch (HT(v2)) {IAdd…

Straightforwardly translate tonested switch-case statement

FGG

GO,DF
DSSS

DOS

ToS1

DAddToS2

ConcSizes of Generated VM(KB) 35

116KB

Runtime System
Interpreter

30
25Target: ARM
Compiler: GCC 7.3.0
Option: -Os

20
15
1050

Full-set
Opt No opt

FixnumOpt
No optFixnum:Arithmetic/logicaloperations supports
only fixnums

2. Collect requirements of applications

on going

target applications
application
application

requirements

application

profileVM instruction
interpreter

VM instruction
interpreter
specialisebuiltin function
builtin function
builtin function
builtin function
builtin functionbuiltin function
builtinbuiltin function function
builtin function select & sepcialise

full-set JavaScript VM specification

builtin function

GCobject model

builtin function
builtin function

specialised VM

datatype
identifierCollect Requirements• Collect applications’ requirements from test runs
• Execute apps on full-set JavaScript VM with tracer• High code coverage in test runs is required• VM will crash if collected requirements are insuﬃcient

APP1 APP2
VM + tracer

Collect Requirements• Collect applications’ requirements by tracing test runs
• Execute apps on full-spec JavaScript VM with tracer• High code coverage in test runs is required• VM will crash if collected requirements are insuﬃcient

APP1 APP2
VM + tracer

APP1VMAPP2crashChallenge: Input Generation• Parameters• Polling sensor device using built-in functions• Large space to be explored• Events• App’s behavior depends on timingevents
xy

APPz

f(x, y, z)

xyz

APP

Sensor.getValue()sensorPiggy-back Unit Tests
Assumption:
Application developers write appropriate unit tests

VM instructionswith trace flag

Target app
compileUnit test for

Pseudo Jasmine

VM instructions
without trace flagcompilerunVM+tracer

3. Object representation

futurework

target applications
application
application

requirements

application

profileVM instruction
interpreter

VM instruction
interpreter
specialisebuiltin function
builtin function
builtin function
builtin function
builtin function
builtin function
builtinbuiltin function function
builtin function select & sepcialise

full-set JavaScript VM specification

builtin function

GCobject model

builtin function
builtin function

specialised VM

datatypeidentifier

Conclusion• eJSTK:

Framework for generating customized JavaScript VM forselected set of applications• Collect applications’ requirements from execution traceusing unit tests• Generate datatype-baed dispatching code
• Customize object representation