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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
# Bytecode generator
A relatively simple script that generates pretty fast bytecode systems.
Relies on some non-standard C, but should in theory be completely portable.
# Usage
```
bcgen <rules.py>
```
The script is pretty bare bones at the moment. Essentially, it generates a number of files in a
directory called `gen` in the working directory. These generated files are included by `bcode.c`,
which you can compile into an object file that provides an interface to compiling and running your
bytecode system.
`rules.py` is a file that describes which operations to generate. Here's an example `rules.py`:
```
g = BCGen(r = 4, f = 0)
g.rule('addi', 'rRR__I', 'R0 = R1 + IMM;')
```
`BCGen()` is the generator class. It has three optional parameters:
+ `r` for number of general purpose registers.
+ `f` for number of floating point registers.
+ `head` for user configurable code, placed just before execution of the bytecode.
`rule()` is the workhorse here. It takes three parameters:
+ `name` for the instruction name.
+ `fmt` for the instruction format.
+ `body` for the instruction body.
The `fmt` parameter is a string of six characters, from left to right:
1) Relocation slot, `r` or `_`
`r` means that the when compiling the instruction, it should return a relocation that can
later be patched with a value. `_` means that no relocation is necessary.
2) Four register slots, `R`, `F` or `_`:
`R` refers to a general purpose register, and `F` refers to a floating point register.
`_` means the register slot is unused. When compiling an operation, the user can pass
in a number for each register slot that is the index of the register to use. Each operation
can take a maximum of four register arguments.
3) Immediate slot, `I`, `D` or `_`:
`I` refers to an integer immediate value, `D` refers to a floating point immediate value.
`_` means the slot is unused. The user can pass in an immediate value that is accessible
to the operation at runtime.
The body of the instruction is what gets executed. The register arguments are referenced
via `R` + index for the general purpose registers and `F` + index for the floating point registers.
Immediate values are accessed via `IMM` for integer and `DIMM` for doubles, respectively.
The index to use when specifying register arguments is the register slot index, so for exampl
the format `_R_FR_` makes registers `R0`, `F2` and `R3` available to the body. It's *very* important
to note that `R0` does not refer to the literal first register in the machine, rather it's the
first register argument the user gives when compiling the instruction.
Each instruction can be compiled via the generated procedure `select_name()`. For the example
`rules.py` above, to compile the instruction `addi` you would call `select_addi(0, 2, 500);`.
The first and second arguments are the register indexes to use, and map to `R0` and `R1`.
The immediate is always last, and in this case it's `500`. One way to look at the situation is
that we're requesting that a bytecode instruction be compiled where register 2 plus `500` be
placed into register 0.
## Jumps
By default the following bytecode instruction is executed automatically. You can however specify
explicit jumps, such as in branches, by `JUMP(target)`. The target can be patched in later or be
specified as an immediate. For example:
```
# rules.py
...
g.rule('beq', 'rRR__I', 'if (R0 == R1) JUMP(IMM);')
```
```
// file.c
breg_t label = label();
...
select_beq(0, 1, label.g); // we already know where we want to jump
// OR
breg_t reloc = select_beq(0, 1, 0); // zero is placeholder
...
breloc_t label = label();
patch(reloc, label); // now we know where we want to jump
```
(Note that the patch system should be improved, but good enough for now)
See `example` for a simple test program that generates a limited set of operations that are enough
to sum the first billion integers.
## Performance
As a very basic test, below is a comparison of `example/exec` found in this repo
in relation to some other methods to accomplish summing the first billion integers.
| 'Method' | Time (s) |
|------------------------|----------|
| C, `-O3 -march=native` | 0.062 |
| C, `-O2` | 0.221 |
| LuaJIT | 0.656 |
| C, `-O0` | 0.709 |
| `example/exec` | 1.533 |
| Lua | 18.717 |
| Perl | 27.962 |
The full C program is
```{C}
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
assert(argc == 2);
unsigned long sum = 0;
unsigned long n = strtoull(argv[1], 0, 0);
for (unsigned long i = 0; i < n; ++i)
sum += i;
printf("%llu\n", sum);
return 0;
}
```
Note the user input so as to avoid completely optimizing away the loop.
# Notes
This software is currently very crude and pretty much only suitable for a
simple demonstration. However, I think the performance figures are
pretty impressive for what it is. A JIT system will essentially always
beat this system in speed, but this is trivially portable and the
code generation is ligtning fast.
A fairly close match in the JIT world is `lightning` (and its lighter fork,
`lightening`). My intention is to try and use this tool to generate a bytecode
backend for `lightening` as a fallback for platforms that `lightening` doesn't
yet support to create a 'universal' low level virtual machine.
Currently you may have to manually modify `bcode.c` to suit your project,
for example adding headers etc. I might improve the tool to output a single
header + implementation file, similar to `flex` and/or `bison` but the current
method is good enough for now.
No restrictions are placed on register count or instruction count.
The instruction count increases the size and compile time linearly, but register
count affects the size and compile time exponentially so be careful.
Also, to maintain the highest performance, the register count should be
smaller than the register count of the underlying hardware. This allows
the compiler to lower bytecode registers to hardware registers, speeding things
up considerably.
Finally, note that the system doesn't assign any specific usage conventions
to registers. You are responsible for maintaining an ABI of some kind, with
stack/frame register(s), callee-save vs. caller-save, etc.
|
