eJSTK: Building JavaScript virtual machines withcustomized datatypes for embedded systems
Tomoharu Ugawaa,∗, Hideya Iwasakib , Takafumi Kataokaa
a Kochi University of Technology, Tosayamada, Kami, Kochi 782-8502, Japanb The University of Electro-Communications, Chofu, Tokyo 182-8585, Japan

Abstract
Using JavaScript as a description language can increase the productivity of
application programs on embedded systems. Since JavaScript is a dynamic
language, it is important for a JavaScript virtual machine (VM) to efficiently
identify the types of first-class values and perform type-based dispatches. For
embedded systems, the type-based dispatching code is desired to be compact aswell as fast. Although operators of JavaScript are heavily overloaded and capable of accepting a variety of datatypes as operands, all the datatypes are notalways necessarily used in a specific program. If some datatypes are never usedin this program, a VM for a subset of JavaScript with operators that support
limited datatypes suffices. Such a VM is expected to be compact and efficient.
In addition, internal representation of datatype of each value may affect performance of type-based dispatching. This paper presents a novel framework thatcan generate a VM for a subset of JavaScript on the basis of operand specifications and datatype specifications given by the programmer. The operand
specifications describe possible operand datatypes for every instruction and thedatatype specifications describe adequate internal representations of necessary
datatypes for a target program. The generated VM is specialized in the sensethat it has efficient and minimum type-based dispatching code for all instructions.
Keywords: virtual machine, JavaScript, embedded systems, code generation,
decision diagram

I This paper is a revised version of the paper entitled “A Framework for Constructing
JavaScript Virtual Machines with Customized Datatype Representations” presented at SAC
2018.
∗ Corresponding author
Email addresses: ugawa.tomoharu@kochi-tech.ac.jp (Tomoharu Ugawa),
iwasaki@cs.uec.ac.jp (Hideya Iwasaki), kataoka@pl.info.kochi-tech.ac.jp (Takafumi
Kataoka)

Preprint submitted to Computer Languages, Systems and Structures

March 20, 2019

1. Introduction
Embedded systems [1] are now becoming quite common. We can find various
kinds of small devices installed with application programs that carry out certain
specialized operations of their own and transmit, if necessary, data to other devices. Such application programs are typically developed in low-level languages
such as C and assembly languages. However, program development by using
these low-level languages suffers from three main productivity problems.
• Since low-level languages are not suitable for rapid prototyping, it takes
much time to evolve applications on embedded systems.
• Writing programs in such languages is very cumbersome. For example,
programmers have to be very careful in not forgetting to free allocatedmemory when it is no longer needed to avoid memory leak.
• Programs written in low-level languages have a problem in portability.
Even though a program is written in C, it is less portable compared to a
program written in a high-level language, e.g., JavaScript.
This paper focuses on the use of virtual machine (VM) based managed languages to resolve these problems. Out of a number of managed languages,
we adopted JavaScript, which is one of widely-used scripting languages with ahigher level of abstractions than low-level languages, for the following two main
reasons.
• JavaScript is quite suitable for the rapid development of prototype programs from the inherent characteristics of scripting languages. This enables programmers to readily try and improve new ideas.
• JavaScript’s event-driven programming style matches data processing inembedded systems [2, 3]. For example, an embedded system with a small
device forms a sensor node in a network and collects data that are to
be transmitted to another node in an event-driven manner. This kind of
event-driven behavior can be naturally described as a JavaScript program.
The goal of this research is to make a JavaScript VM available on embedded systems. Such a VM is required to be compact and lightweight. This isbecause the capabilities of devices for embedded systems are generally “poor”
in the sense that minimum required performance suffices for the objectives ofthe system. Over performance of the hardware of a device, e.g., excessive CPU
speed or too much capacity in the installed memory, is avoided to reduce thecost of embedded systems, and especially in battery-powered systems, to reduce
the power consumption.
Our approach is to allow programmers of embedded system applications tocustomize their own VMs for their individual applications. We have decided totake this approach on the basis of the following observations.

2First, once an application is installed on an embedded device and begins its
operation, the embedded system becomes specialized for the operation because
another application is not supposed to be run at the same time on the same device. In this point, JavaScript VMs for embedded systems have a big advantage
over those for web browsers. Since VMs for web browsers must be capable ofexecuting any programs efficiently, they adopt dynamic adaptation techniquessuch as just-in-time compilation [4]. In contrast, every VM for an embedded
system can be specialized to the target application.
Second, a JavaScript VM in many cases is not necessarily the “full-set” one.
The operators of JavaScript are heavily overloaded and capable of accepting avariety of datatypes as operands. For example, according to the specification of
JavaScript [5], the plus (+) operator behaves as an addition operator for number
operands, a concatenation operator for string operands, and either of the twofor other operand datatypes depending on the results of type conversions of theoperands. However, many applications use the plus operator with limited combinations of operand datatypes. For example, some application may not apply
the plus operator to string operands at all. Needless to say, few applications
apply the plus operator to a combination of boolean and array operands.
Third, datatypes mainly and frequently handled in an application are fixed
depending on its specialized operation. For example, integer data might bemainly used in some systems, while arrays might be heavily used in other systems.
This paper provides a framework that offers a mechanism of generating customized JavaScript VMs to the programmers of embedded systems. “Customizability” within this context has two aspects: datatype selection and datatype
representation.
Our framework can generate a VM for the aspect of datatype selection that
excludes the interpreter code for handling datatypes that will never be given as
an operand of each instruction. The feature of datatype selection contributes
to reducing the size of VM code. Limiting possible datatypes also makes typebased dispatching process needed for operator overloading simple.
Our framework can also generate a VM for the aspect of datatype representation that has efficient internal representations for frequently used datatypes.
For example, if the programmer specifies the use of a special format of tagged
pointers for a program with a heavy use of arrays to distinguish arrays fromother datatypes, the program can assess quickly whether a given value is anarray or not.
The above idea was incorporated into our new JavaScript VM named eJSVM(embedded JavaScript Virtual Machine), and the framework named eJSTK (embedded JavaScript Tool Kit) offers a mechanism of customizability to the programmer for eJSVM with respect to the two previously described aspects. The
programmer gives two descriptions: the operand specifications for datatype selection and the datatype specifications for customizing datatype representation.
Given these descriptions, eJSTK produces a set of C source programs of the customized eJSVM. Then, by using a standard C compiler such as GCC and Clang,the programmer can obtain the executable file of the advantageously customized
3

VM. The customized VM is optimized for a specific application whose requirements are written in the given descriptions at the cost of giving up supporting
other applications. If the application performs an operation that is beyond thegiven datatype specifications, the VM can crash.
Our framework currently supports a subset of ECMAScript 5.1 [5], fromwhich some features that need complicated treatment by eJSVM, such as theeval() function, are excluded.
The main contributions of the work reported in this paper are summarized
below.
• We present eJSTK, which is a framework that enables the programmer
to generate a customized JavaScript VM. eJSTK is datatype-centric; theprogrammer gives the operand and datatype specifications, from which an
efficient VM for specialized computations is generated.
• We present an algorithm that generates C code with a compact and efficient type-based dispatching for an interpreter from the operand anddatatype specifications and the descriptions of VM instruction behaviorsof the full-set JavaScript written in a domain specific language (DSL).
• We provide some experimental customizations of JavaScript VMs built
from different operand and datatype specifications, and show the effectiveness of eJSTK.
2. eJSVM
2.1. Features of JavaScript
JavaScript is a multi-paradigm scripting language that has prototype-based
object-oriented features [6]. It is widely accepted as a description language forclient-side programs of Web applications. JavaScript is currently also used inserver-side website programming. Well-known JavaScript engines include V81 ,Rhino2 , SpiderMonkey3 , V74 , and JerryScript5 .
Table 1 presents datatypes in JavaScript. Types determined by the language
specification [5] are listed in the left column of the table. Of these six types,
only an Object has a collection of properties. The Object type can be further
classified into simple Object, Array, Function, Regexp, etc., as indicated in the
middle column. Thus, in essence, we can consider that JavaScript’s types arethose listed in the third column of the table. We call them JS-datatypes in therest of this paper. We also use the term VM-datatypes to represent internal
datatypes for implementing JS-datatypes in a VM. VM-datatypes defined in
the eJSVM will be explained in Sect. 2.2.
1 https://developers.google.com/v8/
2 https://developer.mozilla.org/en-US/docs/Mozilla/Projects/Rhino
3 https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/Internals
4 https://github.com/cesanta/v7
5 http://jerryscript.net/

4

types in
specification
Undefined
Null
BooleanStringNumberObjectTable 1: Types of JavaScript.
classification
JS-datatypeof Object
Undefined
Null
BooleanStringNumber
SimpleObject
Array
Function
RegexpBooleanObject
StringObject
NumberObject

Object Object
Array
Function
RegexpBoolean Object
String Object
Number Object

description
undefinednull
true or false
stringnumbernormal object
array
function
regular expr
boxed boolean
boxed string
boxed number

Since JavaScript is a dynamic language, executing a JavaScript program
causes many type-based dispatches according to the values of interest and also
many type conversions from a value of some type to another value of anothertype. This is partly because some operators work differently depending on thetypes of their operands, and partly because some operators convert the types of
their operands to those they expect.
For example, consider the addition operator “+”. It behaves as follows.
• When the values of both operands are numbers, it returns their sum as anumber.
• When the values of both operands are strings, it returns the concatenatedstring.
• When either of the values of operands is a string or an object that can beconverted to a string, it converts the other operand to a string and returns
the concatenated string.
• Otherwise, it converts both operands to numbers and returns their sum.
As can be seen from this example, it is important for a JavaScript VM toefficiently identify the datatype of a given value and dispatch its execution on
the basis of the identified datatype.
2.2. Internals of eJSVM
The eJSVM is a register-based virtual machine for JavaScript programs thatare aimed to be run on embedded systems. It is an interpreter of VM instructions, into which JavaScript programs are compiled by the eJS compiler. The
main loop of eJSVM executes a compiled program by interpreting a sequence of
VM instructions one by one on the basis of the threaded code [7] technique.
The instruction set of eJSVM was designed by the authors. We explain theadd instruction that corresponds to the “+” operator as a typical example of5

Table 2: JS-datatypes, VM-datatypes, and VM-reptypes in default setting of eJSVM.
JS-datatype

VM-datatype

VM-reptype

ptag/htag

ptr/imm

description

Undefined
Null
BooleanStringNumberspecialspecialspecialstringfixnumflonumsimple object
array
functionbuiltinregexpboolean object
string object
number object

normal special
normal special
normal special
normal string
normal fixnum
normal flonum
normal simple object
normal arraynormal function
normal builtin
normal regexp
normal boolean object
normal string object
normal number object

110 / –
110 / –
110 / –
100 / 4111 / –
101 / 5000 / 6000 / 7000 / 8000 / 9000 / 11000 / 14000 / 12000 / 13

imm
imm
imm
ptr
imm
ptr
ptr
ptr
ptr
ptr
ptr
ptr
ptr
ptr

seq of chars
61-bit signed int
C’s double
normal object
array
user-definedbuilt-inregular expr
boxed boolean
boxed string
boxed number

SimpleObject
Array
Function
RegexpBooleanObject
StringObject
NumberObject

instruction execution. This instruction takes three registers as its operands;
the first is the destination register of the result, and the second and third are
input registers that have the values of the augend and addend respectively.
Interpreting this instruction, the VM checks the datatypes of these input values
and appropriately dispatches the execution according to the combination of thedatatypes to perform adequate type-based operations of “+”. Since JavaScript
is a dynamic language, many VM instructions need similar dispatching processes
at runtime. In fact, 26 out of 59 VM instructions need such dispatching.
The proposed framework defines internal datatypes called VM-datatypes inthe eJSVM that correspond to JS-datatypes. Table 2 lists VM-datatypes. Basically, the relationship between JS-datatypes and VM-datatypes is one-to-one,
but there are three exceptions. First, Undefined, Null, and Boolean correspond to special. Since these JS-datatypes have very small number of instances,i.e., Undefined and Null have only one (undefined and null, respectively) and
Boolean has only two (true and false), we have decided to treat them altogether in a single VM-datatype special. Second, Number has two VM-datatypes,
namely fixnum (signed integers) and flonum (floating point numbers). It is natural to have these two, one of which is specialized to integers, because integer
values are very frequently used. The third exception is Function. Since an instance of a Function is either a user-defined or a built-in one, eJSTK defines
two VM-datatypes. The relationship between JS-datatypes and VM-datatypes
is fixed; the programmer is not allowed to change the relationship in customization.
Each customization has to provide concrete representations for necessary
VM-datatypes. We call a representation of a VM-datatype a VM-datatype representation, or VM-reptype for short. Defining VM-reptypes is very important in
the customization of eJSTK. The default setting of eJSVM defines VM-reptypes(third column of Table 2) so that every VM-datatype has a single VM-reptype.
VM-reptypes in the default setting are predefined. Thus, programmers canmake use of these VM-datatypes in their own customization.
6

pointer tag
pointer / immediate value

XXX(a) Tagged pointer.
pointer tag
XXX

header tag
payload(b) Header tag in data structure.
Figure 1: Tagged pointer and header tag in eJSVM.

The eJSVM internally uses pointer tags in tagged pointers and header tags
simultaneously to identify the VM-reptype (and thus VM-datatype) of a firstclass value in JavaScript, on the condition that every data structure is n-bytealigned in the heap area where n is determined by the architecture of the CPU.
For the case of a 64-bit architecture, n is eight and thus the least significant
three bits of an aligned address are definitely zero. These bits can be used tohold a pointer tag value to represent its VM-reptype. At most, eight distinct
pointer tag values can be used in this case. For the case where eight tag values
are insufficient to identify VM-reptypes, eJSVM also uses a separate tag field,
i.e., header tag, in the body of a data structure in the heap. We assume thatthe pointer tag has three bits in the 64-bit architecture in the rest of this paper
because eJSVM currently supports only such architectures. However, the designof eJSTK is independent of the width of a pointer tag.
Figure 1 outlines a tagged pointer and a header tag in the eJSVM. A firstclass value is represented as a tagged pointer that contains either a pointer to adata structure or an immediate value when a pointer is unnecessary, such as aninteger value. If it has a pointer, the pointed data structure has a header within
which the header tag is placed. The right of Table 2 presents pointer tags andheader tags for VM-reptypes in the default setting of the eJSVM.
If a VM-reptype uses a pointer tag value that is not shared with another
VM-reptype, e.g., normal string in Table 2, whether the value of a given tagged
pointer is of the VM-reptype or not can be quickly determined by only checking
its pointer tag. We say that such a pointer tag is unique. In contrast, if a
VM-reptype’s pointer tag value is not unique, i.e., shared with another VMreptype (in the case the pointer tag has a pointer in it), it requires two checks
for both the pointer tag value and the header tag value to determine whether avalue is of the VM-reptype. This is costly compared to the first case because it
needs indirect access to the header tag. Thus, it is important to assign a uniquepointer tag value for a frequently used VM-reptype to gain the efficiency of
the type-based dispatch in a customized VM. It is worth noting that every VM-

7

1
2
3
4
5
6
7
8
9
10
11
12

#define T_STRING 4// pointer tag for string#define T_GENERIC 0// pointer tag for simple object/array#define HTAG_SIMPLE_OBJECT 6 // header tag for simple object#define HTAG_ARRAY 7// header tag for array// individual VM-datatype#define is_string(v) (PTAG(v) == T_STRING)#define is_simple_object(v) \((PTAG(v) == T_GENERIC) && (HTAG(v) == HTAG_SIMPLE_OBJECT))#define is_array(v) ((PTAG(v) == T_GENERIC) && (HTAG(v) == HTAG_ARRAY))// set of VM-datatypes#define is_object(v) (PTAG(v) == T_GENERIC)#define is_number(v) ((PTAG(v) == T_FIXNUM) || (PTAG(v) == T_FLONUM))
Figure 2: Predicate macros for default setting.

reptype that has an immediate value in its tagged pointer is necessarily assigned
a unique pointer tag. normal fixnum is an example of such VM-reptypes in thedefault setting shown in Table 2. One might think that the header tag for a
VM-reptype that is assigned a unique pointer tag value is unnecessary because
it is never referred to in identifying the datatype. However, it is retained in
preparation for cases where garbage collection6 requires the header tag value of
every data structure in the heap area.
The C source code of eJSVM needs predicate macros. A predicate macro
has the form of is vmdatatype(v), where vmdatatype is the name of a VMdatatype, and returns whether a tagged pointer v is vmdatatype or not. Predicate macros of this type are called VM-datatype predicates. In addition, eJSVM
needs predicate macros for a set of VM-datatypes, which are called datatypefamily predicates. For example, is object(v) returns whether v is one of the
VM-datatypes corresponding to Object (see Table 1). Figure 2 presents somepredicate macros for the default setting listed in Table 2. Predicate macros areautomatically defined by eJSTK for a customized VM. Here, PTAG(v) returns
the pointer tag value and HTAG(v) returns header tag value of a given tagged
pointer v.
3. Overview of proposed framework
The proposed framework, eJSTK, offers the programmer means of making
datatype-centric customizations, i.e., datatype selection and datatype representation. Due to these customizations, the size of program code of the customized
eJSVM decreases because unnecessary cases concerning unused datatypes are
not generated. This is crucial from the viewpoint of limited resources in embedded systems. Furthermore, the type-based dispatching process in the customized
eJSVM becomes simplified and the VM is expected to be speeded up.
Figure 3 presents the overall structure of eJSTK.
6 eJSVM currently implements mark and sweep garbage collection.

8

supplied by the programmer
datatype
specifications

supplied by the framework
instruction
definitions(in DSL)

operandspecifications

datatype part
generator

instruction part
generator

datatype
part(in C)

instruction
part(in C)

fixed part(in C)

customized eJSVM
Figure 3: Overall structure of eJSTK.

The programmer has to properly specify the following datatype specifications
to customize a VM:
1. correspondences between VM-datatypes and VM-reptypes, and2. assignments of pointer tag values and header tag values to VM-reptypes.
In the design of eJSTK, the relationships between VM-datatypes and VMreptypes are not limited to one-to-one; the programmer is allowed to define morethan one VM-reptype for a VM-datatype as long as every VM-reptype is implemented in the fixed part in Fig. 3. The reason why we took this design decision
is that we have a plan to enable the programmer to give multiple VM-reptypes
to string as JerryScript does. In JerryScript, short strings are represented as direct strings, which have a totally different structure from that of normal strings;
a normal string is allocated in the heap while a direct string is embedded withina pointer. Although the current eJSTK has not implemented direct strings in
the fixed part yet, the datatype part generator and the instruction part generator can generate type-based dispatching code for those VM-datatypes that havemultiple VM-reptypes. We will give an example in Sect. 4.3.
In addition to datatype specifications, the programmer has to specify operand
specifications for every instruction that describe possible datatypes given as its
operand. Instructions that are not given operand specifications are supposed totake all datatypes as default.
The entire C source code of eJSVM can be grouped into three categories.
First, the fixed part consists of code that is independent of customization. Thisis supplied by the framework and the programmer does not need to know its
details. Second, the datatype part consists of code generated by the datatype

9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

special:string:fixnum:flonum:simple_object:array:
function:builtin:regexp:string_object:number_object:boolean_object:+normal_special+normal_string+normal_fixnum+normal_flonum+normal_simple_object+normal_array+normal_function+normal_builtin+normal_regexp+normal_string_object+normal_number_object+normal_boolean_object

normal_special:
T_SPECIAL(110)normal_string:
T_STRING(100)/HTAG_STRING(4)normal_fixnum:
T_FIXNUM(111)normal_flonum:
T_FLONUM(101)/HTAG_FLONUM(5)normal_simple_object: T_GENERIC(000)/HTAG_SIMPLE_OBJECT(6)normal_array:
T_GENERIC(000)/HTAG_ARRAY(7)normal_function:
T_GENERIC(000)/HTAG_FUNCTION(8)normal_builtin:
T_GENERIC(000)/HTAG_BUILTIN(9)normal_regexp:
T_GENERIC(000)/HTAG_REGEXP(11)normal_string_object: T_GENERIC(000)/HTAG_STRING_OBJECT(12)normal_number_object: T_GENERIC(000)/HTAG_NUMBER_OBJECT(13)normal_boolean_object: T_GENERIC(000)/HTAG_BOOLEAN_OBJECT(14)Figure 4: Datatype specifications for default setting.

part generator in eJSTK on the basis of given datatype specifications. Its maincontent consists of definitions of predicate macros. Third, the instruction partconsists of code for executing VM instructions in the interpreter’s main loop.
This part is generated by the instruction code generator in eJSTK from the
instruction definitions, datatype specifications and operand specifications. Here,the instruction definition is supplied by the framework; it specifies the typebased behavior of every VM instruction.
The eJSVM uses VM-datatypes in four places: in the interpreter’s main loopthat executes a sequence of VM instructions, in datatype conversion functions,in built-in functions, and in the tracer of the garbage collector. The current
eJSTK generates efficient dispatcher only for the interpreter of VM instructions.
Generating type-based dispatching code for the other places is left for our futurework.
4. Specifying customizations
4.1. Datatype specifications
We first present datatype specifications for the default setting of eJSVM in
Fig. 4. Each line consists of two parts separated by a colon. The left part ofthe colon is a name of either a VM-datatype or a VM-reptype. The names of
VM-datatypes (e.g., string and array) and those of VM-reptypes for the default
setting (e.g., normal string and normal array) are reserved.
When a VM-datatype emanates in the left part, its corresponding VMreptypes occur in the right part with a “+” character in front of each VM-

10reptype. Lines 1–12 in the example of Fig. 4 mean that every VM-datatype is
only represented by its default VM-reptype.
When a VM-reptype emanates on the left, assignments of pointer tag values
and header tag values occur on the right in the following form.
ptag name(ptag value)/htag name(htag value)
where ptag name is the name for the pointer tag value, ptag value is the pointertag value in a binary number, htag name is the name for the header tag value,and htag value is the header tag value in a decimal number. Both ptag nameand htag name are used by the macro definitions in the generated datatype part.
The “/” or later is only necessary when the tagged pointer has a pointer within
it7 . For example, Line 16 in Fig. 4 indicates that the VM-reptype normal fixnum
has 111 as its pointer tag with immediate data in its tagged pointer. Similarly,Line 19 means that the VM-reptype normal array has 000 as its pointer tag andits tagged pointer points to a data structure whose header tag is seven.
eJSTK generates macro definitions, part of which have already been presented in Fig. 2, from the datatype specifications.
4.2. Operand specifications
Though the language specification [5] determines type conversion rules foreach JavaScript’s operator, it is likely that an application only gives values ofsome limited datatypes for each VM instruction. For example, an application
only gives numbers as operands to every occurrence of the add instruction. To
customize the eJSVM in such a case, the programmer gives operand specifications
that describe possible datatypes given to each VM instruction.
Each line in operand specifications has the following form.
instruction name(operand type, . . .) action
Here, “(operand type, . . .)” specifies a combination of datatypes for input
operands, where operand type is either a name of VM-datatype or VM-reptype,“ ” (which means any datatype), or “-” (which means that the operand is not
an input), and action is either accept, error, or unspecified.
In the default setting, every instruction is allowed to be given all datatypes as
its input operand. Thus, its operand specifications, part of which are presented
in Fig. 5, do not limit input datatypes at all.
4.3. Examples of customization
We here explain how to specify a required customization by providing two
examples.
Example 1: Assigning a unique pointer tag to Array
Suppose that we want to run an application that uses many arrays. This
example customizes the eJSVM to have a special treatment for the Array type.
The VM-reptype normal array has a pointer tag value of 000 in the default
7 In this case, the structure name for the body pointed to from a tagged pointer has to be
specified on the same line. However, we omit it in this paper for simplicity.

11

1
2
3
4
5
6
7

add (-,_,_) accept
bitand (-,_,_) accept
bitor (-,_,_) accept
call (_,-) accept
div (-,_,_) accept
eq (-,_,_) accept// The rest is omitted// instruction for ‘+’// instruction for ‘&’// instruction for ‘|’// instruction for function call// instruction for ‘/’// instruction for ‘==’Figure 5: Operand specifications for default setting.
18(Lines 1–18 are the same as those of Fig. 4)
19 normal_array:
T_ARRAY(010)/HTAG_ARRAY(7)20(Lines 20–25 are the same as those of Fig. 4)

Figure 6: Datatype specifications for Example 1.

setting. This pointer tag value is shared with JavaScript’s Object family, suchas simple object and function. This example assigns a unique pointer tag valueof 010 to normal array and allows normal arrays to be quickly examined.
Figure 6 presents the datatype specifications for this customization. The
only difference from the specifications of default setting is on Line 19. normal array in this example is assigned a unique pointer tag of 010. The operand
specifications for this customization are the same as those for default setting.
Example 2: Limiting operand datatypes
Suppose that we are developing an application that uses only limited combinations of operand datatypes for some instructions, especially which perform
arithmetic / comparison operations. For example, the add instruction in thisapplication assumes that both operands are fixnums, both are flonums, augend
is flonum and addend is fixnum, or both are strings.
Figure 7 presents part of the operand specifications for this application. Thissays that the above combinations for add are accepted but other combinations
should signal errors. Any datatype specifications can be used with the operand
specifications in Fig. 7.
Example 3: Making direct string
Our last example is to make two kinds of VM-reptypes for string VMdatatype. In the default setting, VM-reptype for string is normal string. Itstagged pointer has an address of a data structure allocated in the heap area,
which contains a null-terminated C string in it.
Suppose an application that uses many short strings. If a tagged pointer has

1
2
3
4
5

add (-,fixnum,fixnum) accept
add (-,flonum,fixnum) accept
add (-,flonum,flonum) accept
add (-,string,string) accept
add (-,_,_) error
Figure 7: Part of operand specifications for Example 2.

12pointer tag
null-terminated string

length 010
LSB byte

Figure 8: Tagged pointer for direct string.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

special:string:fixnum:flonum:simple_object:array:
function:builtin:regexp:string_object:number_object:boolean_object:+normal_special+normal_string +direct_string+normal_fixnum+normal_flonum+normal_simple_object+normal_array+normal_funcition+normal_builtin+normal_regexp+normal_string_object+normal_number_object+normal_boolean_object

normal_special:
T_SPECIAL(110)normal_string:
T_STRING(100)/HTAG_STRING(4)direct_string:
T_DSTRING(010)
normal_fixnum:
T_FIXNUM(111)normal_flonum:
T_FLONUM(101)/HTAG_FLONUM(5)normal_simple_object: T_GENERIC(000)/HTAG_SIMPLE_OBJECT(6)normal_array:
T_GENERIC(000)/HTAG_ARRAY(7)normal_function:
T_GENERIC(000)/HTAG_FUNCTION(8)normal_builtin:
T_GENERIC(000)/HTAG_BUILTIN(9)normal_regexp:
T_GENERIC(000)/HTAG_REGEXP(11)normal_string_object: T_GENERIC(000)/HTAG_STRING_OBJECT(12)normal_number_object: T_GENERIC(000)/HTAG_NUMBER_OBJECT(13)normal_boolean_object: T_GENERIC(000)/HTAG_BOOLEAN_OBJECT(14)Figure 9: Datatype specifications of Example 3.

64 bits, a null-terminated short string whose length is less than seven can bepacked into a tagged pointer as an immediate data. Although this representation
for short string is not implemented yet, in the current eJSTK, this example
assumes that it were implemented.
This customization example makes two VM-reptypes, namely direct string8(for short strings) and normal string (for other strings), as representations ofstring VM-datatype. We use 010 as the pointer tag value of direct string.
Figure 8 presents the tagged pointer for direct string. Before the last byte
comes a sequence of characters. The last byte contains the pointer tag (leastsignificant three bits) and the length of the string.
The datatype specifications are presented in Fig. 9. Line 2 specifies that VMdatatype string has two VM-reptypes, normal string and direct string. Line 16
assigns a pointer tag 010 to direct string. Since tagged pointer for direct string
contains immediate data, i.e., null-terminated string and length information,
8 This is a different representation from the direct string of JerryScript.

13

hinstruction-definitioni ::= \inst hinstruction-namei ( hoperand-listi ) hbodyi
hinstruction-namei ::= hstringi
hoperand-listi ::= hoperandi (, hoperandi)∗
hoperandi ::= hoperand-typei hoperand-variablei
hbodyi ::= hclausei∗
hclausei ::= hwhen-clausei | hotherwise-clausei | hprologuei | hepiloguei
hwhen-clausei ::= \when hconditioni \{ hc-programi \}hotherwise-clausei ::= \otherwise \{ hc-programi \}hprologuei ::= \prologue \{ hc-programi \}hepiloguei ::= \epilogue \{ hc-programi \}hconditioni ::= hatomic-conditioni | hcompound-conditioni | ( hconditioni )hatomic-conditioni ::= hoperand-variablei : hVM-datatypei
hcompound-conditioni ::= hconditioni && hconditioni | hconditioni || hconditioni
hoperand-typei ::= Register | Value | Subscript | Immediate | Displacement
hoperand-variablei ::= variable namehVM-datatypei ::= name of VM-datatypehc-programi ::= fragment of C codes
Figure 10: Syntax of DSL for instruction definition.

header tag is not, of course, assigned.
5. Instruction definitions
The eJSTK generates C code for VM instruction execution in the main loopof the eJSVM interpreter by using instruction definitions, datatype specifications
and operand specifications.
eJSTK supplies an instruction definition written in DSL for every instruction.
As presented in Fig. 3, the instruction definition is referred to only by the
instruction part generator. Thus, programmers need not be familiar with the
DSL, and furthermore need not write a “program” in this DSL.
The syntax for the DSL is presented in Fig. 10.
Figure 11 presents the instruction definition written in DSL for the add
instruction. Its three operands are given as register numbers, but its instruction
definition supposes that the place of the first operand (destination register) has
already been stored into dst of type Register, and the values retrieved fromthe second and third registers have already been stored into v1 (augend) andv2 (addend) of type Value. This definition describes eight cases for type-based
dispatching.
The DSL describes the behavior of the instruction as a collection of whenclauses, each of which is composed of a condition on the VM-datatypes of its
input operands and a C code fragment that is to be executed when the condition is satisfied. For example, a when-clause is described in Lines 3–9 of Fig.
11; its condition states that both v1 and v2 are fixnums, and if this conditionis satisfied, a C code fragment at Lines 4–8 is executed. Types specified in acondition part of a when-clause are not VM-reptypes but VM-datatypes because every instruction definition is independent of customization, i.e., concrete
14

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

\inst add (Register dst, Value v1, Value v2)// v1 and v2 have values in the source registers.
\when v1:fixnum && v2:fixnum \{cint s = fixnum_to_cint(v1) + fixnum_to_cint(v2);// Adds two Fixnums after converting them into C integer.
dst = cint_to_number(s);// Stores the sum to the destination register after converting the sum// to a JavaScript’s number.
\}\when v1:string && (v2:fixnum || v2:flonum || v2:special) \{v2 = to_string(context, v2);// First converts v2 to a string.
goto add_STRSTR;// Then goes to add STRSTR.
\}\when (v1:fixnum || v1:flonum || v1:special) && v2:string \{v1 = to_string(context, v1);// First converts v1 to a string.
goto add_STRSTR;// Then goes to add STRSTR.
\}\when v1:string && v2:string \{add_STRSTR:// This label is the case where both values are strings.
dst = cstr_to_string2(context, string_to_cstr(v1), string_to_cstr(v2));// Concatenating two strings after converting them into C strings.
\}\when (v1:simple_object || v1:array || v1:function || v1:builtin || v1:regexp|| v1:string_object || v1:number_object || v1:boolean_object) &&(v2:special || v2:string || v2:fixnum || v2:flonum) \{v1 = object_to_string(context, v1);// First converts v1 to a string.
goto add_HEAD;// Then goes to the entrance.
\}\when (v1:special || v1:string || v1:fixnum || v1:flonum) &&(v2:simple_object || v2:array || v2:function || v2:builtin || v2:regexp|| v2:string_object || v2:number_object || v2:boolean_object) \{v2 = object_to_string(context, v2);// First converts v2 to a string.
goto add_HEAD;// Then goes to the entrance.
\}\when (v1:simple_object || v1:array || v1:function || v1:builtin || v1:regexp|| v1:string_object || v1:number_object || v1:boolean_object) &&(v2:simple_object || v2:array || v2:function || v2:builtin || v1:regexp|| v2:string_object || v2:number_object || v2:boolean_object) \{v1 = object_to_string(context, v1);// Converts v1 to a string.
v2 = object_to_string(context, v2);// Converts v2 to a string.
goto add_HEAD;// Then goes to the entrance.
\}\otherwise \{double x1 = to_double(context, v1);// Converts v1 to a C double.
double x2 = to_double(context, v2);// Converts v2 to a C double.
dst = double_to_number(x1 + x2);// Adds them, converts the sum to a number, and stores it to the destination.
\}
Figure 11: Instruction definition for ADD instruction.

15

representations of VM-datatypes. If none of the conditions in when-clauses are
satisfied, C code fragment in the otherwise-clause, if any, is executed.
It is worth noting that the order of when-clauses in an instruction definition
is not in the least important. The instruction part generator adequately arranges
the order of condition checking and C code fragments for every pair of interest byusing the information in the datatype specifications to generate the instruction
part. How to generate C code from an instruction definition will be describedin Sect. 7.
Second, the DSL enables the C code fragment of an instruction to easily
access all given operands via its corresponding formal parameters. Each formal
parameter has a “type” which is determined depending on its role; Register
for a place of a register, Value for a value (tagged pointer) stored in an input
register, Subscript for an integer representing a subscript, Immediate for an
immediate value of a fixnum/special, and Displacement for a displacement fora jump/conditional jump instruction.
For the sake of convenience, the DSL offers the prologue and epilogue parts,
which are inserted at the entrance and exit of the generated instruction code,
respectively. Though they are not used in Fig. 11, their typical usages might be
to define comprehensive names by #define in the “prologue” part and undefinethem by #undef in the “epilogue” part.
The proposed DSL does not allow the nesting of conditionals and C codefragments. As long as our definitions of VM instructions, nesting was not necessary; we used goto statements to perform further type-based dispatching afterconverting some operands as shown in Fig. 11. The goto statements are used
not only for representing nesting but also for unifying similar type-based dispatching code.
6. Generating customized code for datatype part
From the datatype specifications, eJSTK generates macro definitions, some ofwhich have already been presented in Fig. 2. eJSVM uses two kinds of predicate
macros.
• A VM-datatype predicate macro returns whether a given value is of a VMdatatype of interest.
• A datatype family predicate macro returns whether a given value is of a
VM-datatype that belongs to a particular group of VM-datatypes.
A VM-datatype may correspond to multiple VM-reptypes. For example, in
Example 3 in Sect. 4.3, the string VM-datatype corresponds to two VM-reptypes,
normal string and direct string. Thus, not only a datatype family predicate macro
but also a VM-datatype predicate macro judges whether the VM-reptype of agiven value belongs to a certain set of VM-reptypes.
The program of the runtime system is hand-written “static” code and isindependent of datatype representations. This makes it possible for the programmer to customize datatype representations. Whenever the runtime system16examines the VM-datatype of a value, it uses a VM-datatype predicate macroor a datatype family predicate macro. For example, built-in functions often use
a is object datatype family predicate macro to judge whether a given value
belongs to the JavaScript’s Object family, such as simple object and array.
Every VM-datatype predicate macro and datatype family predicate macro
can be defined as a disjunction of predicates, each of which returns whether agiven value is of a specified VM-reptype. However, if we simply defined them inthis way, predicate macros would be inefficient. For example, is object with adefault datatype specification defined as#define is_object(v) \(is_simple_object(v) || is_array(v) || ...)
is expanded to the following.
#define is_object(v) \((PTAG(v) == T_GENERIC) && (HTAG(v) == HTAG_SIMPLE_OBJECT) \|| (PTAG(v) == T_GENERIC) && (HTAG(v) == HTAG_ARRAY) \|| ...)
Instead, eJSTK simplifies such a macro definition by using the following rules.
• Combine terms with the same test for a pointer tag value by using the
distributive law.
• Replace a disjunction that covers all possible cases with TRUE.
In the case of is object, all terms have (PTAG(v) == T GENERIC) in common.
Thus, eJSTK transforms the definition by combining all terms as follows.
#define is_object(v) \((PTAG(v) == T_GENERIC) && \((HTAG(v) == HTAG_SIMPLE_OBJECT) || \(HTAG(v) == HTAG_ARRAY) || ...))
Then, since the disjunction of tests for a header tag of v covers all possible
header tag values, eJSTK transforms it into the following definition.
#define is_object(v) ((PTAG(v) == T_GENERIC) && TRUE)
The latter transformation is impossible for a C compiler because it cannot
know if a disjunction covers all possible cases. We apply the former transformation to enhance the opportunity for the latter transformation. Please notethat it is not necessary to eliminate TRUE because it will be eliminated by the
C compiler.
7. Generating customized code for instruction part
An instruction needs to dispatch its execution code with respect to thedatatypes of the given input values, which have already been stored in its
operands. The instruction part generator of eJSTK outputs rearranged C code17for this purpose, in the sense that the code excludes on the basis of operand specifications unnecessary cases for unused datatypes. Since the condition part in
an instruction definition is written by using VM-datatypes, eJSTK re-interprets
each VM-datatype to its corresponding VM-reptypes and generates C code that
identifies these VM-reptypes.
We prioritize both the efficiency and compactness of the generated C code.
For the sake of efficiency, the C code accesses the header tag of a data structure
only when the pointer tag value in a tagged pointer is shared. We assume that
VM-reptypes with a unique pointer tag value are used with almost the same
frequency. We understand that this assumption is not always practical, andleave its improvement to our future work. We avoid duplicating the same C
code fragment for compactness by using goto statements when necessary.
eJSTK uses a decision diagram as its internal representation of type-based
dispatching code. It generates rearranged C code for an instruction using afour-step process.
1. Read the instruction definition written in the DSL (e.g., Fig. 11) andconvert it into a collection of normalized dispatch rules, each of which
specifies a VM-reptype for each operand and the C code fragment to be
executed if datatypes of operands match the specified VM-reptypes.
2. Construct a decision tree from the instruction definition. A leaf of thetree corresponds to a C code fragment in the instruction definition. Theinternal nodes of the tree are constructed from the condition part. Each of
the internal nodes corresponds to a multi-way branch based on the pointertag value or the header tag value of an operand.
3. Optimize the decision tree. In this step, some nodes might be combined
and shared with multiple parent nodes. As a result, the decision tree istransformed into a directed acyclic graph (DAG).
4. Generate C code from the DAG.
7.1. Running example
We explain the details of the code generation process by using a running
example. Although the example is simple and rather artificial, it suffices tooutline the process.
Suppose that we are interested in only three VM-datatypes, namely fixnum,
string, and array. We use the default internal representations for both fixnum
and array: normal fixnum and normal array. We use two VM-reptypes for string,normal string and direct string, which are introduced in Sect. 4.3. The datatype
specifications for this example are presented in Fig. 12 (a). Different from
Example 3 in Sect. 4.3, we assign the same pointer tag value to normal arrayand normal string. Note that both T DSTRING and T FIXNUM are unique andthat T GENERIC is shared.
We generate instruction code for a two-operand instruction, exam insn,
which is not an actual instruction. Its instruction definition is presented inFig. 12 (b). We use A, B, C, D, and E instead of real C code fragments for simplicity. We assume that the values of operands are already stored in v0 and
v1.
18

1
2
3
4
5
6
7
8

string:fixnum:array:+normal_string +direct_string+normal_fixnum+normal_arraynormal_string:
direct_string:normal_fixnum:
normal_array:

T_GENERIC(000)/HTAG_STRING(4)
T_DSTRING(010)
T_FIXNUM(111)
T_GENERIC(000)/HTAG_ARRAY(7)

1
2
3
4
5
6

\inst exam_insn (Value v0, Value v1)\when v0:fixnum && v1:fixnum \{ A \}\when v0:fixnum && (v1:string || v1:array) \{ B \}\when (v0:string || v0:array) && v1:fixnum \{ C \}\when v0:string && v1:string \{ D \}\otherwise \{ E \}(a) Datatype specifications.

(b) Instruction definition for example instruction.
Figure 12: Running example of code generation.

For the sake of brevity, we use the following abbreviated notations. DS , NS ,NF , and NA denote VM-reptypes direct string, normal string, normal fixnum, andnormal array, respectively. PS , PF , and PG denote pointer tag values T DSTRING,
T FIXNUM, and T GENERIC, and HS and HA denote header tag values for normal string and normal array.
7.2. Code generation process
As mentioned above, eJSTK generates rearranged C code using a four-stepprocess.
7.2.1. Step 1: Condition normalizationeJSTK transforms the instruction definition written in the DSL into a collection of normalized dispatch rules. A normalized dispatch rule is a pair of acondition and a C code fragment, where the condition part specifies a single
VM-reptype for each operand. For example, if the instruction for our running
example takes two operands, a condition is (t0 , t1 ), which means that the VMreptype of v0 is t0 and that of v1 is t1 .
eJSTK decomposes a single hwhen-clausei or an hotherwise-clausei in an
instruction definition into one or more normalized dispatch rules. At the sametime, it discards some normalized dispatch rules that do not appear in theoperand specifications. More specifically, eJSTK creates a set of normalized
dispatch rules as follows.
1. eJSTK decomposes each condition into one or more half-normalized dispatch rules, where a half-normalized dispatch rule is a pair of a condition
specifying a single VM-datatype for each operand and a C code fragment.
In this process, hotherwise-clausei is replaced with an appropriate collection of half-normalized dispatch rules.

19

(NF , NF )(NF , DS )(NF , NS )(NF , NA)
(DS , NF )(NS , NF )(NA, NF )(DS , DS )

⇒ A
⇒ B
⇒ B
⇒ B
⇒ C
⇒ C
⇒ C
⇒ D

(DS , NS )(NS , DS )(NS , NS )(DS , NA)
(NS , NA)
(NA, DS )(NA, NS )(NA, NA)

⇒ D
⇒ D
⇒ D
⇒ E
⇒ E
⇒ E
⇒ E
⇒ E

Figure 13: Normalized dispatch rules for running example.

2. eJSTK discards the half-normalized dispatch rules whose conditions specify combinations of operand datatypes that are never given to the instruction in accordance with the operand specifications.
3. eJSTK further decomposes each half-normalized dispatch rules by decomposing VM-datatypes into VM-reptypes.
The resulting collection of normalized dispatch rules for the running example
is shown in Fig. 13. Note that this running example assumes that the operand
specifications require the instruction to accept any operand datatypes.
7.2.2. Step 2: Decision tree construction
eJSTK constructs a decision tree in which each normalized dispatch rulecreated in Step 1 corresponds to a path from the root to a leaf. An internal
node of the tree examines a pointer tag value or a header tag value of some
operand. An internal node has edges, each of which is labeled with a pointertag value or a header tag value to a child. A leaf of the tree is a C code fragment.
Because the decision tree is made from the normalized dispatch rules createdin Step 1, a node does not necessarily have edges for all the tag values; anedge for a tag value of an unspecified datatype in the operand datatypes is notcreated. Formally speaking, the result of the decision tree is undefined if thevalue examined by a node is not found in any of the labels of the edges. However,such a case never happens as long as the operand specifications specify all thepossible operand datatypes, which we assume.
The constructed decision tree is ordered ; i.e., the pointer tags and header
tags are examined in the same order along all paths from the root to the leaves.
The ordered decision tree examines the pointer tags of all operands from the first
operand to the last and then examines the header tags, if any, of all operands,
also from the first operand to the last.
Furthermore, along every path from the root to a leaf, both the pointer tag
value and header tag value of every operand are examined. This is done tosimplify the optimization algorithm used in Step 3. If the VM-reptype of an
operand has a unique pointer tag value, the datatype of the operand can be
judged only by the pointer tag value, as mentioned in Sect. 2.2. Nevertheless,eJSTK always creates internal nodes in the ordered decision tree for the header
tags of such VM-reptypes. In particular, even if a tagged pointer contains
an immediate value, such as normal fixnum in the running example, and the20

PTAG(v0)

PF

PG

PS

PTAG(v1)

PF PS PGPFPF PS PGPSPG
HTAG(v0)

A
HS HH
S

HA HS

HA
HTAG(v1)

A
HS HA
HS HA
HS HH
HA
S
A B B B C D D E C C D E D E E E

Figure 14: Decision tree for running example. Edges drawn with dashed lines indicate that
VM-reptype does not have header tag.

operand has no header tag, eJSTK creates internal nodes for the non-existentheader tags.
The decision tree for the running example is shown in Fig. 14. The root node
tests the pointer tag of operand v0. There are three possibilities: PF (for normal fixnum), PS (for direct string), and PG (for normal string and normal array).
Next, the second level node tests the pointer tag value of v1. The third level
node tests the header tag of operand v0. If the pointer tag of operand v0 is PF
or PS , the VM-reptype is normal fixnum or direct string, which does not have aheader tag. For such cases, the decision tree yields a child node without testing
the tag. Edges to these children are drawn with dashed lines in Fig. 14.
It is worth noting that an internal node created for the header tag of a VMreptype with a unique pointer tag value has exactly one child. This property isimportant for efficiency because eJSTK removes such nodes in Step 3.
Proposition 7.1. In the constructed ordered decision tree, if an internal node
examines the header tag of an operand of a VM-reptype with a unique pointertag value, this internal node has exactly one child.
7.2.3. Step 3: Decision tree optimizationeJSTK transforms the ordered decision tree into a DAG to produce more
efficient and compact type-based dispatching code.
For a formal discussion, we define an ordered decision diagram (ODD). A
decision diagram is a rooted DAG. A terminal node is called a leaf. A leaf isassociated with a C code fragment. When a leaf L is associated with a C codefragment C, we denote code(L) = C. A non-terminal node is called a decisionnode. A decision node is associated with a test that examines the pointer tag
value or the header tag value of an operand. We denote the tag value of the21

operand that a decision node V examines as test(V ). A decision node with asingle successor is called a branchless node, and one with multiple successors iscalled a branching node. An edge from a decision node is labeled with one ormore pointer tag values or header tag values. An ODD is a decision diagram inwhich tests appear in the same order along all paths from the root to the leaves.
We denote a decision node of an ODD by using a partial function V thatmaps a pointer tag value or a header tag value t to V (t), the successor nodeconnected through the edge labeled with t. If such a successor does not exist,
V (t) is undefined. If a decision node V is for a non-existent header tag introduced in Step 2, V has exactly a single successor node U . In this case, we define
that, for every header tag value t, V (t) = U .
The input of an ODD is a combination of operands. For example, hv0, v1i
is given as input to an ODD for a two-operand instruction. The output of an
ODD is a C code fragment. We denote that an ODD with root R yields a C
code fragment C for a combination of operands I as dispatch(R, I) = C. We
consider not only the entire ODD but also a sub-ODD, which is some node V(the root of the sub-ODD in the ODD) and its transitive closure. In this case,
we denote dispatch(V, I) = C if the sub-ODD starting from V yields C for input
I. It should be noted that dispatch(V, I) may not be defined for some input I,
which we denote dispatch(V, I) = ⊥, because the datatypes of operands might
be limited in accordance with the operand specifications.
Before proceeding to the optimization process in Step 3, we define the equivalence and upward-compatibility of ODDs and the consistency of nodes.
Definition 7.1. Two ODDs starting from nodes U and V are equivalent iff,
for every combination of operands I, the outputs of both ODDs are defined anddispatch(U, I) = dispatch(V, I) or neither is defined.
Definition 7.2. An ODD starting from node V is upward-compatible withthat from U , or simply V is upward-compatible with U , iff dispatch(U, I) =dispatch(V, I) for every combination of operands I such that dispatch(U, I) is
defined.
Please note that we do not care about dispatch(V, I) if dispatch(U, I) = ⊥in Definition 7.2.
Definition 7.3. Two nodes U and V in an ODD are consistent iff test(U ) =test(V ) and one of the following conditions is satisfied.
1. Both U and V are leaves and code(U ) = code(V ).
2. Both U and V are branching nodes that satisfy that, for every pointertag value or header tag value t such that both U (t) and V (t) are defined,
U (t) = V (t).
3. Both U and V are branchless nodes, and U (s) = V (t), where s and t are
the labels of their only edges.
For example, in Fig. 15, in which we assume test(A) = test(B) for decisionnodes A and B, A and B are consistent in cases (a) and (b) because they
22

A
s

B
t

t

(a)

A
u

B
s

t

A
s

(b)

B
t

t

s

(c)

Figure 15: Consistency; A and B are consistent in (a) and (b), but not in (c). We assumetest(A) = test(B).

satisfy the second and third conditions, respectively. In case (c), A and B are
not consistent because they are branching nodes that are defined on tag values, but A(s) 6= B(s). Please note that U and V are not consistent if one is abranching node and the other is branchless.
The input for Step 3 is the ordered decision tree constructed in Step 2. Sincean ordered decision tree is a special case of ODD, we can rephrase this: the input
for Step 3 is the ODD constructed in Step 2. In addition, the input decision
diagram has a property that, every path examines all the tag values. We call
ODD with this property a fully-testing ODD. Let the depth of V , denoted as
depth(V ), be the distance from the root to a node V .
Proposition 7.2. In a fully-testing ODD, for two nodes U and V , depth(U ) =depth(V ) if and only if test(U ) = test(V ).
The output of Step 3 is an optimized ODD that is equivalent to the input
ODD. We next describe the optimization algorithm and then the properties ofan optimized ODD.
Optimization algorithm. To generate the optimized ODD, eJSTK first combines
consistent nodes, and then it removes branchless nodes.
If two nodes are consistent, their “combined” node can be defined.
Definition 7.4. Let U and V be consistent nodes. Their combined node, denoted as U ⊕ V , is defined as follows.
• If both U and V are leaves, U ⊕ V = U .
• If both U and V are decision nodes,

U (t) if U (t) is defined.
(U ⊕ V )(t) =V (t) otherwise
The combined node of U and V , U ⊕ V , is upward-compatible with both U
and V . Thus, eJSTK replaces both U and V with U ⊕ V . Or, we say simply
that eJSTK combines U and V .
Non-consistent nodes U and V may become consistent after combining theirsuccessor nodes. For example, if both U and V are branching nodes and U (t)and V (t) are combined for all t such that both U (t) and V (t) are defined, U andV become consistent. Thus, eJSTK repeatedly combines two consistent nodes
from the leaves to the root to maximize the opportunity for combining.
23

Because the input ODD is a fully-testing one, two nodes U and V are consistent only if depth(U ) = depth(V ) by Definition 7.3 and Proposition 7.2. This
property is preserved even after a pair of nodes is combined. Therefore, once
we combine all the consistent pairs of nodes in some distance N from the rootor farther, any node V such that depth(V ) ≥ N never becomes consistent withother nodes even if we combine nodes closer to the root.
Algorithm 7.1. First combine every consistent pair of leaves until no consistent pairs of leaves are left. Then, combine every consistent pair of decisionnodes whose successors are leaves until no such consistent pairs are left. In thisway, from the leaves to the root, combine every consistent pair of nodes whose
depths are the same. until no consistent pairs in the depth are left.
The resulting ODD is equivalent to the original ODD. In addition, typebased dispatching code generated from the resulting ODD should be more compact because each leaf is translated into the associated C code fragment, andeach decision node is translated into a switch-case statement in Step 4.
eJSTK next removes all branchless nodes.
Algorithm 7.2. Remove all branchless nodes. Whenever a branchless node V
with predecessor node P and successor node S is removed, replace the destinations of all edges from P to V with S. The new predecessor node P 0 is definedas
S
if P (t) = V .
P 0 (t) =P (t) otherwise
In theory, Algorithm 7.2 can create a new consistent pair of nodes. Supposethat two branching nodes U and V have edges labeled with t to branchlesssuccessor nodes U (t) and V (t) before performing Algorithm 7.2. Suppose further
that U (t) and V (t) share a successor W through edges with different labels, thatis, U (t)(a) = V (t)(b) = W for some a and b (a 6= b). Suppose even further that
U and V would be consistent if U (t) and V (t) were consistent, that is, forevery label s such that s 6= t and both U (s) and V (s) are defined, U (s) andV (t) are consistent. In this case, Algorithm 7.2 removes U (t) and V (t), and wehave U (t) = V (t) = W . Thus, U and V become consistent by Algorithm 7.2.
However, we did not find such cases in our experimentation using our instruction
definition.
After combining all consistent nodes using Algorithm 7.1, our running example is transformed into the ODD shown in Fig. 16. Combining decision nodes
can result in an edge having multiple labels. For example, the edge above B haslabels HS and HA .
After removing all branchless nodes using Algorithm 7.2, our running example is transformed as shown in Fig. 17.
Properties of optimized ODD. We first define a redundant decision node. Intuitively, if an ODD has a redundant decision node, generated type-based dispatching code tests the header tag of an operand of a VM-reptype with a uniquepointer tag value.
24

PTAG(v0)

PF

PG

PS
PF

PG

PS
PG

PS

PTAG(v1)

PF
PS

PF

PG
HTAG(v0)

HS

A

HS
HA
B

HA HS
HS
HA

HA
HTAG(v1)

HAHS
C

D E

Figure 16: ODD for running example after combining consistent nodes.

PTAG(v0)

PF

PG

PS
PF

PS
PG

PG

PTAG(v1)

PF
PS

PS PF

PG
HTAG(v0)

HS

A

B

C

HA HS
HS
HA

HA
HTAG(v1)

D E

Figure 17: ODD for running example after removing branchless decision nodes.

25

Definition 7.5. A decision node V is redundant in an ODD iff it examines
the header tag of an operand of a VM-reptype with a unique pointer tag value
and the pointer tag is examined by another decision node along the path fromthe root to V .
The ODD optimized using Algorithms 7.1 and 7.2 has two properties.
1. There are no branchless decision nodes.
2. There are no redundant decision nodes.
Property 1 is obviously satisfied because Algorithm 7.2 removes all branchless nodes.
Regarding property 2, Proposition 7.1 guarantees that the ODD input to
Algorithm 7.1 has the following weaker property:
20 . There are no redundant branching nodes.
Proposition 7.3 states that Algorithm 7.1 preserves property 20 . Therefore, theoptimized ODD has property 2 because Algorithm 7.2 removes all branchlessnodes.
Proposition 7.3. For every combining operation performed using Algorithm 7.1,
if the ODD before the combining operation does not have a redundant branchingnode, the resulting ODD also does not have a redundant branching node.
Proof. Assume that the combining operation replaces consistent nodes U andV with U ⊕ V .
• If U and V are leaves, U ⊕ V is also a leaf.
• If U and V are branching nodes, neither U nor V is redundant because
the ODD before combining does not have a redundant branching node by
the premise of this proposition. Thus, U ⊕ V is also not redundant.
• If U and V are branchless decision nodes, their successor nodes are thesame node. Thus, U ⊕ V is also a branchless node.
Therefore, the resulting ODD does not have a redundant branching node.
Theorem 7.1. The optimized ODD does not have redundant decision nodes.
Proof. At the beginning of Step 3, every decision node examining a header tagof an operand of a VM-reptype with a unique pointer tag value is branchless.
Thus, the ODD input to Algorithm 7.1 does not have redundant branchingnodes by definition of redundancy. By Proposition 7.3, the ODD output by
Algorithm 7.1 does not have redundant branching nodes. Because Algorithm 7.2
removes all branchless nodes, all decision nodes remaining in the optimized ODD
are branching nodes. Therefore, all decision nodes are not redundant.

26

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

switch(PTAG(v1)) {case T_FIXNUM:
switch(PTAG(v2)) {case T_FIXNUM: { A } break;case T_GENERIC: case T_DSTRING: { B } break;} break;case T_DSTRING:
switch(PTAG(v2)) {case T_FIXNUM: goto LC;
case T_DSTRING: goto LD;
case T_GENERIC: goto L1;} break;case T_GENERIC:
switch(PTAG(v2)) {case T_FIXNUM: LC: { C } break;case T_DSTRING:
switch(HTAG(v1)) {case HTAG_STRING: LD: { D } break;case HTAG_ARRAY: LE: { E } break;} break;case T_GENERIC:
switch(HTAG(v1)) {case HTAG_STRING:
L1:switch(HTAG(v2)) {case HTAG_STRING: goto LD;
case HTAG_ARRAY: goto LE;} break;case HTAG_ARRAY: goto LE;} break;} break;}
Figure 18: Generated C code for running example.

7.2.4. Step 4: C code generationeJSTK generates C code for type-based dispatching from the optimized ODD.
This is a straightforward process using a depth-first search over the ODD. A
decision node is translated into a switch-case statement that branches on
the basis of the associated test with the node, and a leaf is translated into its
associated C code fragment. If a node is shared with multiple predecessor nodes,
eJSTK generates the code for the node when it visits the node for the first timeand emits a goto statement for the second time and later.
The generated C code for our running example is shown Fig. 18.
8. Evaluation
We evaluated the effectiveness of eJSTK from three viewpoints: (1) effectiveness of customization, (2) effectiveness of optimization in the instruction part
generator, and (3) comparison of generated VMs with other JavaScript engines.
Execution environment. We used two environments, ARM and x86. Though x86
is not an embedded system, we used it to show the potential of eJSTK.
ARM: A Raspberry Pi 3 with the BCM2837 64-bit CPU (1.2 GHz), the Raspbian GNU/Linux 8 (Linux kernel 4.9.35) OS, and the GCC 7.3.0 compiler.
27

x86: A desktop computer with the Intel(R) Core(TM) i7-6700K CPU (4.00
GHz), the Ubuntu 14.04.5 (Linux kernel 3.13.0) OS, and the GCC 7.3.0
compiler.
We used the -Os compilation option to reduce the code size for both environments.
For all executions, we used a 10-MB heap to minimize the effect of garbage
collection. The current eJSVM use a naive mark-sweep garbage collection that is
not well tuned. Furthermore, our object model was not specialized for embedded
systems, and thus required a large heap. The garbage collection and object
model are beyond the scope of this work, and are left for future work.
Benchmark programs. We selected a set of benchmark programs from SunSpider
Benchmarks9 version 0.9 and made minor modifications so that they could run
on our eJSVM. The selected benchmarks are listed in Fig. 19.
The benchmark names start with their category names, which represent theircharacteristics:• Benchmarks with 3d- and math- perform arithmetic operations on floatingpoint numbers.
• Those with access- access properties of objects or arrays intensively.
• Those with bitops- perform bitwise operations on integers that fit our
fixnumVM-datatype.
• Those with string- deal with many strings.
The modifications we made were in• reduction in the number of iterations, and• rewriting so as not to use some built-in functions; e.g., we replaced Math.random,which was used in string-base64 to generate the text to be encoded, witha manually written pseudo-random number generator function.
VMs. We compared four VMs generated with eJSTK and a manually tuned
handcrafted VM in terms of their binary size and elapsed time in executing
the benchmark programs.
We made two datatype specifications and two operand specifications andcombined them to generate the four VMs.
• The default datatype specifications were the default settings shown in
Table 2.
• The arraytag datatype specifications correspond to Example 1 in Sect.
4.3. A unique pointer tag value was assigned to normal array. The value
was 001, which was not used in the default setting.
9 https://webkit.org/perf/sunspider/sunspider.html

28• The any operand specifications were used to generate instructions that
supported any operand datatype.
• The fixnum operand specifications were used to generate arithmetic andrelational instructions that accepted only fixnums. The add instruction isan exception; it accepted either two fixnums or two strings. When operands
with unsupported datatypes were given, the VM possibly crashes. Moreprecisely, it executes code for other datatypes10 .
We denote the four VMs by concatenating the names of the specifications:default-any, arraytag-any, default-fixnum, and arraytag-fixnum.
The handcrafted VM had the same datatype representations and accepted
the same combinations of operand datatypes for each instruction as a VM withthe default setting, but we manually wrote all of the VM code and tuned it asmuch as possible. For example, its instructions dealt with only probable casesin the interpreter loop and called slow path functions for other cases; e.g., theadd instruction called the slow path function unless both of its source operands
were numbers or both were strings. This may have contributed to keeping themain loop of the interpreter small.
Note that we did not implement any specialized representation of strings,
such as direct string, which we used as an example in Section 4.2 and Section 6.
8.1. Effectiveness of customization
Figure 19 presents the elapsed times for executing the benchmarks in the
ARM and x86 environments. All results were normalized to the elapsed timesof the handcrafted VM.
Figure 20 compares the sizes of the VMs. The bars in the group labeled
optimized represent the sizes of VMs generated using the decision tree optimization described in Sect. 7.2. The colored areas represent the sizes of the maininterpreter loop (and out-of-line slow path functions for handcrafted), and thegrey areas represent the sizes of the remaining part excluding the built-in functions. We excluded the sizes for built-in functions because they are assumed to
be selectively included in the VMs.
Before examining the effectiveness of the customization, we examine theoverall performance of the code generator. The default-any VM had the samedatatype representations as the handcrafted VM, and its instructions acceptedany operand datatypes. Comparing these two, the manually tuned handcrafted
VM was around 1.2 times faster or more for 7 out of 13 benchmarks on the
ARM environment. We think the manual tuning applied to the handcrafted
VM worked effectively for these benchmarks. For example, in the handcrafted
VM, we chose operand datatypes that are expected to be used frequently for each
instructions and inlined VM internal functions on such hot paths. More specifically, we inlined to double VM internal function, which converts a value of any
10 eJSTK can also generate VMs that terminate gracefully when unsupported datatypes are
given. Such VMs are larger than those that crash.

29

default-any
default-fixnum

arraytag-any
arraytag-fixnum

1.2
1.0
0.5
0.0

be es ch dy ve te te nd ive dic rm 64 sta ean-cu tre ku bo sie -by -by -a rs or no se fa
3d nary- -fann ess-n ess-n its-in its-in itwise -recu ath-c ctral- ng-ba tring- eo. mgsbi ss cc acc it-b ps-b ps-b flow m spe strib ito ito rol
ss- acce a
3
h
e
t
c
t
s
b
b on
ac
ma
op
c
bit
(a) ARM

default-any
default-fixnum

arraytag-any
arraytag-fixnum

1.2
1.0
0.5
0.0

be es ch dy ve te te nd ive dic rm 64 sta an-cu ry-tre nnku s-nbo -nsie -in-by -in-by ise-a curs -cor al-no -base g-fa . med3 na -fa es ess its its itw -re ath ctr ng trin eo
g
i
s
i
c
b
b
s
s-b cces ac acc 3bit- ops- ops-b olflow mh-spe str
s
e
t
t
r
a
t
s
bi bi ont
acc
ma
op
c
bit
(b) x86
Figure 19: Elapsed times normalized to handcrafted. Missing data indicates that execution
failed.

30

default-any

arraytag-any

default-ﬁxnum

30

30
(KB)

40

(KB)

40

arraytag-ﬁxnum

20

20

10

10

0

fted ized
cra ptim
d
n
o
ha

0

opt
not

fted ized
cra ptimdnoha(a) ARM: the sizes of default-any
and arraytag-any with no optimizations were 151 KB and 163 KB.

opt
not

(b) x86: the sizes of default-any
and arraytag-any with no optimizations were 158 KB and 181 KB.

Figure 20: Sizes of generated and handcrafted VMs.

datatype into a double value of the C language, for fixnum and flonum operandsof arithmetic and relational instructions. The to double function performs further dispatching to call a datatype-specific type conversion function, such as
fixnum to double. On the inlined paths, the interpreter directly calls thesedatatype specific converting functions. The effect of this inlining contributed
to two thirds of the difference of elapsed times between the handcrafted anddefault-any VMs for 3d-cube on ARM. Concretely speaking, the absolute times
for 3d-cube on ARM were 3.60 seconds for the handcrafted VM, 4.77 seconds
for the default-any VM, and 4.37 seconds for the handcrafted VM without
inlining tuning.
As for the VM sizes, the default-any VM was smaller, but not by much.
This shows that the manual tuning caused overhead in size. We conclude thatthe speed and size of the generated VM were comparable to those of the VM
programmed manually in the traditional way.
Let’s turn now to the effectiveness of customization. The purpose of thecustomization was to generate an appropriate VM for each program, each demand such as execution time and VM size, and each condition such as execution
environment and available bits in pointers for unique pointer tag values. Thus,
if the best customized VM differs between benchmark programs, demands, orconditions, we can say that customization was effective.

31

Comparing the default-any and default-fixnum VMs, default-fixnum
was faster and smaller for all benchmarks that default-fixnum could execute.
Comparison of the arraytag-any and arraytag-fixnum VMs showed the sametendency. Thus, we can conclude that limiting operand datatypes is effective.
Although the VM cannot execute programs that need instructions to accept
more operand datatypes than specified in the operand specifications, this is not
a problem because a customized VM is specialized for a specific program to be
run on the VM.
Next, we compare the default-any and arraytag-any VMs to examine
the effects of customizing datatype representations. The arraytag datatype
representations were specialized for programs that intensively performed property access (including array access with the fixnum index). Thus, we assigned aunique pointer tag to normal array.
In contrast to our expectation, default-any and arraytag-any showedsimilar performance both in execution speed and VM size. The only exception was access-fannkuch on the x86 environment. However, when we used
the arraytag datatype specifications together with the fixnum operand specifications, arraytag-fixnum outperformed default-fixnum for access-sieve as
well as access-fuannkuch. These benchmarks accessed arrays intensively. For
the other benchmarks, arraytag-fixnum was as fast as default-fixnum aslong as both could run. As for size, arraytag-fixnum was not worse thandefault-fixnum. Since arraytag-fixnum required more bit patterns for pointertag values to represent normal array with a unique pointer tag value, this resultshows that we succeeded in generating an appropriate VM for each conditionon the number of available bits for pointer tag by customization. Therefore, we
conclude that customization of datatype representations was effective.
8.2. Effectiveness of optimization
In this section, we compare optimized VMs (optimized) with not optimized
ones (not opt) to examine the effectiveness of the decision tree optimization
described in Step 3 of Sect. 7.2.
The sizes of the VMs are shown in Fig. 20. Figures 21 and 22 show theelapsed times in executing each benchmark. They were normalized to those of
the handcrafted VM.
Figure 20 indicates that the decision tree optimization is effective for reducing VM size. Without the decision tree optimization (not opt), the generated
VMs were larger than the handcrafted VM. In particular, the VMs with any
operand specifications were about 10 times larger than the handcrafted VM.
This was because any operand specifications required more complicated typebased dispatching than fixnum operand specifications. Figures 21 and 22 showthat the optimization made the VMs substantially faster.
Code generation took about 9 seconds in total for all 29 instructions regardless of whether the optimization was enabled.
We conclude that the optimizations were effective in terms of both speed
and size.

32

default-any

arraytag-any

default-ﬁxnum

arraytag-ﬁxnum

1.6

1.6

1.6

1.6

1.4

1.4

1.4

1.4

1.2

1.2

1.2

1.2

1.0

1.0

1.0

1.0

0.8

0.8

0.8

0.8

0.6

0.6

0.6

1.6

1.6

1.6

1.6

1.4

1.4

1.4

1.4

1.2

1.2

1.2

1.2

1.0

1.0

1.0

1.0

0.8

0.8

0.8

0.8

0.6

0.6

t
zed ot op
imi
n
t
p
o
3d-cube

zed
imi

opt
not

opt
access-nsievet
zed ot op
imi
n
t
p
o
access-binary-trees

0.6

zed
imi

t
zed ot op
imi
n
t
p
o
access-fannkuch

0.6

opt
not

opt
bitops-3bit-bits-inbyte

zed
imi

opt
not

opt
bitops-bits-in-byte

0.6t
zed ot op
iminopt
bitops-bitwise-and

1.6

1.6

1.6

1.6

1.4

1.4

1.4

1.4

1.2

1.2

1.2

1.2

1.0

1.0

1.0

1.0

0.8

0.8

0.8

0.8

0.6

0.6

0.6

0.6

t
zed ot op
imi
n
t
p
o
controlflow-recursivet
zed ot op
imi
n
t
p
o
math-cordict
zed ot op
imi
n
t
p
o
math-spectral-normt
zed ot op
imi
n
t
p
o
access-nbodyt
zed ot op
imi
n
t
p
o
string-base64

1.6
1.4
1.2
1.0
0.8
0.6

t
zed ot opiminopt
string-fasta

Figure 21: Elapsed times on ARM normalized to handcrafted.

33

default-any

arraytag-any

default-ﬁxnum

arraytag-ﬁxnum

1.6

1.6

1.6

1.6

1.4

1.4

1.4

1.4

1.2

1.2

1.2

1.2

1.0

1.0

1.0

1.0

0.8

0.8

0.8

0.8

0.6

0.6

0.6

1.6

1.6

1.6

1.6

1.4

1.4

1.4

1.4

1.2

1.2

1.2

1.2

1.0

1.0

1.0

1.0

0.8

0.8

0.8

0.8

0.6

0.6

t
zed ot op
imi
n
t
p
o
3d-cube

zed
imi

opt
not

opt
access-nsievet
zed ot op
imi
n
t
p
o
access-binary-trees

0.6

zed
imi

t
zed ot op
imi
n
t
p
o
access-fannkuch

0.6

opt
not

opt
bitops-3bit-bits-inbyte

zed
imi

opt
not

opt
bitops-bits-in-byte

0.6t
zed ot op
iminopt
bitops-bitwise-and

1.6

1.6

1.6

1.6

1.4

1.4

1.4

1.4

1.2

1.2

1.2

1.2

1.0

1.0

1.0

1.0

0.8

0.8

0.8

0.8

0.6

0.6

0.6

0.6

t
zed ot op
imi
n
t
p
o
controlflow-recursivet
zed ot op
imi
n
t
p
o
math-cordict
zed ot op
imi
n
t
p
o
math-spectral-normt
zed ot op
imi
n
t
p
o
access-nbodyt
zed ot op
imi
n
t
p
o
string-base64

1.6
1.4
1.2
1.0
0.8
0.6

t
zed ot opiminopt
string-fasta

Figure 22: Elapsed times on x86 normalized to handcrafted.

34

Table 3: Comparison with other JavaScript engines in the ARM environment. Elapsed time
including garbage collection time (in parentheses) for each benchmark (sec).
benchmark program
3d-cubeaccess-binary-trees
access-fannkuch
access-nbody
access-nsieve
bitops-3bit-bits-in-byte
bitops-bits-in-byte
bitops-bitwise-andcontrolflow-recursive
math-cordic
math-spectral-norm
string-base64
string-fasta

eJSVM
4.81 (0.13)
3.01 (0.08)
6.49 (0.00)
8.50 (0.13)
1.73 (0.01)
1.85 (0.00)
3.21 (0.00)
9.68 (0.00)
1.98 (0.00)
5.64 (0.04)
3.08 (0.02)
61.72 (0.99)
9.54 (0.19)

JerryScript
5.3
3.3
13.0
6.6
failed
3.5
5.1
6.2
2.3
7.4
3.3
8.3
7.3

V7
91.43 ( 21.04)
137.06 (116.36)
276.16 ( 40.15)
74.46 ( 15.35)> 360065.64 ( 12.71)
91.97 ( 10.76)
46.75 ( 0.00)
310.17 (278.44)
113.83 ( 19.28)
164.14 ( 75.63)
421.41 ( 48.60)
112.88 ( 29.03)

8.3. Comparison with other JavaScript engines
We compared the default-any VM with other JavaScript engines for embedded systems, namely JerryScript (Version 1.0) and V7 (Version 3.0) in the
ARM environment. Both engines were run with their default settings. Fromtheir default settings, the heap size of JerryScript was 512 KB fixed, and thatof V7 grew on-demand, starting at 22 KB.
Table 3 shows the elapsed time and garbage collection time for each benchmark. Every elapsed time includes garbage collection time. For JerryScript,
only elapsed times are shown because JerryScript uses reference-counting garbage
collection, which prevented us from measuring garbage collection times.
In comparison to JerryScript, the results for eJSVM were comparable; eJSVM
was faster for 8 out of 13 benchmarks. The string-base64 benchmark was an
exception; it was much slower on eJSVM because eJSVM could not create strings
efficiently.
V7 was much slower than eJSVM even if we compare pure computation times
except garbage collection. We think that this is due to V7’s implementation ofproperty accesses including array index accesses, which uses association lists.
eJSVM used a much larger heap to reduce the effect of our poor memory
management. Nevertheless, eJSVM and JerryScript were comparable even if we
assume that half of the execution times in JerryScript were spent on garbage
collection. In addition, eJSVM was faster than V7 in pure computation times.
Thus, the larger heap setting did not over-compensate for the memory management implementation.
To sum up, these results indicate that eJSVM has comparable performanceto that of other JavaScript engines for embedded systems.
We also compared eJSVM in the x86 environment with more mature JavaScript
VMs for desktop computers, Rhino (Version 1.7.9), SpiderMonkey (Version
C24.2.0), and V8 (Version 7.0.276.28-node.5), under their default settings. For
Rhino, the Java heap size was initially 118 MB, and it grew up to 207 MB. For

35

Table 4: Comparison with other JavaScript engines in the x86 environment. Elapsed time
including garbage collection time (in parentheses) for each benchmark (sec).
benchmark program
3d-cubeaccess-binary-trees
access-fannkuch
access-nbody
access-nsieve
bitops-3bit-bits-in-byte
bitops-bits-in-byte
bitops-bitwise-andcontrolflow-recursive
math-cordic
math-spectral-norm
string-base64
string-fasta

eJSVM
0.357 (0.027)
0.209 (0.006)
0.540 (0.000)
0.636 (0.034)
0.133 (0.000)
0.121 (0.000)
0.255 (0.000)
0.546 (0.000)
0.145 (0.000)
0.399 (0.014)
0.218 (0.008)
23.373 (0.100)
1.057 (0.022)

Rhino
0.398 (0.016)
0.245 (0.007)
0.695 (0.010)
0.360 (0.009)
1.511 (0.075)
0.157 (0.008)
0.300 (0.008)
0.407 (0.005)
0.158 (0.006)
0.351 (0.011)
0.157 (0.007)
0.613 (0.011)
0.625 (0.011)

SpiderMonkey
0.037 (0.0)
0.012 (0.0)
0.033 (0.0)
0.014 (0.0)
0.015 (0.0)
0.005 (0.0)
0.021 (0.0)
0.024 (0.0)
0.011 (0.0)
0.016 (0.0)
0.007 (0.0)
0.021 (0.0)
0.106 (0.0)

V80.039 (0.003)
0.011 (0.002)
0.034 (0.001)
0.015 (0.002)
0.020 (0.002)
0.006 (0.001)
0.016 (0.001)
0.017 (0.001)
0.013 (0.001)
0.024 (0.002)
0.009 (0.002)
0.043 (0.007)
0.058 (0.003)

V8, the heap size was initially 4.2 MB, and it grew up to 11.2 MB. We could
not find the heap sizes for SpiderMonkey.
Table 4 presents the results. Every elapsed time includes garbage collection
time.
The results of eJSVM were comparable with Rhino, but almost one ordermagnitude slower than SpiderMonkey and V8. Though the target of eJSVM
is low-memory systems, performance improvement of customized eJSVM is our
future work.
9. Related Work
Vmgen [8, 9] is a virtual machine interpreter generator that has special support for stack machines. Vmgen generates C code for executing VM instructions
by taking as input VM instruction descriptions. Although both Vmgen and
eJSTK generate VM interpreters, there are two major differences between the
two. First, their directions for customization are totally different; Vmgen is “customizable” in the sense that Vmgen enables the programmer to define required
instructions and generate VM code for various languages, e.g., Gforth [10] andCacao JVM [11]. In contrast, eJSTK’s target language is fixed to JavaScript,
and its customizability is based on the internal structures of datatypes to makethe generated VM adapt to the target application. To sum up, Vmgen is aimed
at instruction-centric customization, while eJSTK is aimed at datatype-centric
customization. Second, the features of target languages are different. An instruction specification in Vmgen contains the type information of the items
popped from and pushed onto the stack. For example, the iadd instructionof Java VM is defined as taking two integers from the stack and pushing an
integer onto the stack. This means that datatypes concerning each instruction
are supposed to be fixed in its target language. Compared to this, eJSTK’s target is JavaScript and datatypes of values given to an instruction are therefore

36dynamically determined at runtime. Thus, it is necessary for each instruction
to perform type-based dispatching efficiently.
Beatty et al. [12] presented an efficient Java interpreter for connected devices
and embedded systems. They used Vmgen for interpreter generation. A Javaapplication bytecode was translated into direct threaded code during which
a number of optimizations were applied. They focused on reducing the cost of
instruction dispatching, while eJSTK focused on reducing the cost of type-based
dispatching in the execution of each instruction.
Mruby [13, 14] is a lightweight implementation of Ruby. It is intended to belinked with target applications, which are typically those on embedded systems.
Both mruby and eJSTK share the same purpose but take different approaches.
While mruby’s approach makes it possible for the programmer to select required modules, ours makes it possible to select required datatypes and theirrepresentations.
Many studies have been done on the dynamic customization or optimization of language interpreters. Quickening [15, 16] and superinstruction [17, 18]
are well-known optimization techniques based on runtime instruction rewriting.
Quickening replaces an instruction with one that is specialized by using runtime
information, typically by its operands. Superinstruction replaces a successive
sequence of more than one instruction with an equivalent, i.e., merged single
instruction. We think that these techniques can be applied to a customized
eJSVM. It may be possible to automatically generate a specialized/merged instruction from the instruction definitions without much effort because an instruction’s behavior is described according to every individual combination of
given datatypes.
NaN boxing [19] is an implementation technique for value representation.
This technique embeds an entire pointer into the mantissa part of a Not-aNumber representation of the IEEE Standard for Floating Point Arithmetic.
By using Nan boxing, it is not necessary to allocate a data structure for a
floating point number within the heap area. It might be better to allow the
programmer to use this technique for more thorough customization. It is left
for our future work.
Kim et al. [20] introduced Typed Architectures that achieve efficient program
execution of scripting languages from the observation that dynamic types, i.e.,
type checking and method dispatch, are main causes of inefficiency of scripting
languages. Typed Architecture lets each internal representation of a value retain
high-level type information at an instruction set architecture level and performs
type checking implicitly with the pipeline with instruction execution. Theirwork and ours concern the same problem of scripting languages, but the approaches taken are totally different; they relied on hardware-based accelerationof type checking, while our work addressed this problem by means of providing
the ability of VM customization by the programmer.
Würthinger et al. [21] and Humer et al. [22] presented an idea for implementing abstract syntax tree (AST) interpreters where AST was appropriately
modified during program execution. They took a layered approach: a guest VM(written in Java) was on top of a host VM (written in C++). The AST inter37

preter rewrote the tree by replacing one node with another that was specializedthat could more quickly carry out expected operations. This might be simpler
than the instruction rewriting previously described, but it would be difficult toapply this idea to embedded systems due to their limited resources.
This work is also related to interpreter specialization [23, 24], which applies
the program specialization technique to an interpreter to generate an efficient
implementation. In a sense, eJSTK can be regarded as a special kind of acompile-time interpreter specialization approach. The program generation by
eJSTK is not a pure source-to-source (C-to-C) program transformation but a
DSL-to-C program transformation to adapt eJSVM for each target application.
This DSL-to-C transformation enables eJSTK to generate compact and efficient
type-based dispatching code by means of decision diagrams.
ODD and its optimization process described in Sect. 7.2 are related to ordered binary decision diagram (OBDD) and normalized OBDD (NOBDD) [25].
There are two main differences between an ODD in this paper and an OBDD.
First, the number of branches from a decision node in our ODD is not limited
to two; it might be one, i.e., branchless, or more than two, depending on the
tag value assignments described in the datatype specifications and the numberof possible datatypes for the operand that corresponds to the decision node.
Second, a decision node in our ODD is represented as a partial function, whilethat of OBDD is represented as a total function whose domain is {0, 1}. Thus,
the result of the function for a decision node is undefined, or “don’t care”, for
an impossible pointer tag / header tag value. The optimization process in Sect.
7.2 uses this fact in combining two nodes to form an upward-compatible nodewith the two.
Code generation on the basis of ODD is related to multiple dispatching in
object-oriented systems, which is the selection of methods (i.e., multi-methods/ open-methods) to be invoked based on the dynamic types of more than one
argument. One major technique for dispatching of a multi-method invocation
uses a dispatch table, which holds dispatching entries for all possible combinations of the arguments’ types. This dispatch table technique can be optimizedby compressing the table to eliminate the number of dispatching entries [26].
Comparing our ODD-based technique with the dispatch table technique is left
for our future work.
10. Conclusion
We presented a novel approach to generating customized JavaScript VM
interpreters. The proposed framework, eJSTK, is datatype-centric in the sensethat customizations with respect to the representations of datatypes specified
by the programmer are applied. A generated VM interpreter has efficient typebased dispatching code according to the datatype specifications.
We would like to explore the selection of VM instructions in a customized
eJSVM in future work. We can know the set of VM instructions used by aprogram from the compiled program to be run on a customized VM. Thus, weare able to remove such instructions that are never used from the main loop38

of the VM. We are also considering to generate both operand specifications
and datatype specifications automatically from an application. Such a system
would help the programmer develop applications for embedded systems by using
eJSTK.
The eJSTK is available on GitHub https://github.com/plasklab/ejstk.
Acknowledgement
The authors would like to thank all members involved in the eJSVM project.
This work was partly supported by the JSPS KAKENHI Grant Number 16K00103.
References[1] P. Koopman, Better Embedded System Software, Drumnadrochit Press,
2010.
URL http://koopman.us/book.html[2] G. Chadha, S. Mahlke, S. Narayanasamy, Efetch: Optimizing instruction
fetch for event-driven web applications, in: Proc. 23rd International Conference on Parallel Architectures and Compilation, PACT 2014, 2014, pp.
75–86. doi:10.1145/2628071.2628103.
[3] Y. Zhu, D. Richins, M. Halpern, V. J. Reddi, Microarchitectural implications of event-driven server-side web applications, in: Proc. 48th International Symposium on Microarchitecture, MICRO-48, ACM, 2015, pp.
762–774. doi:10.1145/2830772.2830792.
URL http://doi.acm.org/10.1145/2830772.2830792[4] J. Aycock, A brief history of just-in-time, ACM Comput. Surv. 35 (2)(2003) 97–113. doi:10.1145/857076.857077.
[5] ECMA International, Standard ECMA-262 - ECMAScript Language Specification, 5th Edition, 2011.
[6] C. Chambers, D. Ungar, E. Lee, An efficient implementation of SELF, adynamically-typed object-oriented language based on prototypes, Lisp andSymbolic Computation 4 (3) (1991) 243–281.
[7] J. R. Bell, Threaded code, Commun. ACM 16 (6) (1973) 370–372. doi:
10.1145/362248.362270.
[8] M. A. Ertl, D. Gregg, A. Krall, B. Paysan, Vmgen - a generator of efficientvirtual machine interpreters, Softw., Pract. Exper. 32 (3) (2002) 265–294.
doi:10.1002/spe.434.
URL https://doi.org/10.1002/spe.43439

[9] D. Gregg, M. A. Ertl, A language and tool for generating efficient virtual
machine interpreters, in: Proc. Domain-Specific Program Generation, 2003,
pp. 196–215. doi:10.1007/978-3-540-25935-0_12.
URL https://doi.org/10.1007/978-3-540-25935-0_12[10] M. A. Ertl, A portable forth engine, in: Proc. EuroFORTH ’93 Conference,
1993.
[11] D. Gregg, M. A. Ertl, A. Krall, Implementing an efficient Java interpreter, in: Proc. High-Performance Computing and Networking, 9th International Conference, HPCN Europe 2001, 2001, pp. 613–620. doi:
10.1007/3-540-48228-8_70.
URL https://doi.org/10.1007/3-540-48228-8_70[12] A. Beatty, K. Casey, D. Gregg, A. Nisbet, An optimized Java interpreter forconnected devices and embedded systems, in: Proc. 2003 ACM Symposium
on Applied Computing, SAC 2003, ACM, 2003, pp. 692–697. doi:10.1145/
952532.952667.
[13] K. Tanaka, A. D. Nagumanthri, Y. Matsumoto, mruby – rapid softwaredevelopment for embedded systems, in: Proc. 15th International Conference on Computational Science and Its Applications, ICCSA 2015, 2015,
pp. 27–32. doi:10.1109/ICCSA.2015.22.
URL https://doi.org/10.1109/ICCSA.2015.22[14] T. Azumi, Y. Nagahara, H. Oyama, N. Nishio, mruby on TECS:
component-based framework for running script program, in: Proc. IEEE
18th International Symposium on Real-Time Distributed Computing,
ISORC 2015, 2015, pp. 252–259. doi:10.1109/ISORC.2015.42.
[15] S. Brunthaler, Inline caching meets quickening, in: Proc. Object-Oriented
Programming, 24th European Conference, ECOOP 2010, 2010, pp. 429–
451. doi:10.1007/978-3-642-14107-2_21.
[16] S. Brunthaler, Efficient interpretation using quickening, in: Proc. 6th
Symposium on Dynamic Languages, DLS 2010, ACM, 2010, pp. 1–14.
doi:10.1145/1869631.1869633.
[17] T. A. Proebsting, Optimizing an ANSI C interpreter with superoperators, in: Proc. 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 1995, 1995, pp. 322–332. doi:
10.1145/199448.199526.
URL http://doi.acm.org/10.1145/199448.199526[18] G. B. Prokopski, C. Verbrugge, Analyzing the performance of code-copying
virtual machines, in: Proc. 23rd Annual ACM SIGPLAN Conference on
Object-Oriented Programming, Systems, Languages, and Applications,OOPSLA 2008, ACM, 2008, pp. 403–422. doi:10.1145/1449764.1449796.
URL http://doi.acm.org/10.1145/1449764.1449796
40[19] B. Klemens, 21st Century C: C Tips from the New School, 1st Edition,
O’Reilly Media, Inc., 2012.
[20] C. Kim, J. Kim, S. Kim, D. Kim, N. Kim, G. Na, Y. H. Oh, H. G. Cho, J. W.
Lee, Typed architectures: Architectural support for lightweight scripting,in: Proc. 22nd International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’17, ACM, New
York, NY, USA, 2017, pp. 77–90. doi:10.1145/3037697.3037726.
URL http://doi.acm.org/10.1145/3037697.3037726[21] T. Würthinger, A. Wöß, L. Stadler, G. Duboscq, D. Simon, C. Wimmer,
Self-optimizing AST interpreters, in: Proc. 8th Symposium on Dynamic
Languages, DLS 2012, ACM, 2012, pp. 73–82. doi:10.1145/2384577.
2384587.
URL http://doi.acm.org/10.1145/2384577.2384587[22] C. Humer, C. Wimmer, C. Wirth, A. Wöß, T. Würthinger, A domainspecific language for building self-optimizing AST interpreters, in: Proc.
2014 International Conference on Generative Programming: Concepts andExperiences, GPCE 2014, 2014, pp. 123–132. doi:10.1145/2658761.
2658776.
URL http://doi.acm.org/10.1145/2658761.2658776[23] N. D. Jones, Transformation by interpreter specialisation, Sci. Comput.
Program. 52 (2004) 307–339. doi:10.1016/j.scico.2004.03.010.
URL https://doi.org/10.1016/j.scico.2004.03.010[24] S. Thibault, C. Consel, J. L. Lawall, R. Marlet, G. Muller, Static and dynamic program compilation by interpreter specializ ation, Higher-Orderand Symbolic Computation 13 (3) (2000) 161–178. doi:10.1023/A:
1010078412711.
URL https://doi.org/10.1023/A:1010078412711[25] D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 1:
Bitwise Tricks & Techniques; Binary Decision Diagrams, 12th Edition,
Addison-Wesley Professional, 2009.
[26] E. Dujardin, E. Amiel, E. Simon, Fast algorithms for compressed multimethod dispatch table generation, ACM Trans. Program. Lang. Syst. 20 (1)(1998) 116–165. doi:10.1145/271510.271521.
URL http://doi.acm.org/10.1145/271510.271521

41