| blob | 467d195e5c246c28a11b83a883684134bd0d818b |
1 # Bytecode
3 Bytecode (BC, also *P-code*, "portable code") is a type of [binary](binary.md) format for executable programs usually intended to be [interpreted](interpreter.md) or to serve as an [intermediate representation](intermediate_representation.md) in [compilers](compiler.md) (i.e. meant to be translated to some other language); it is quite similar to [machine code](machine_code.md), however machine code is meant to be directly run by some physical [hardware](hardware.md) while bytecode is more of a [virtual](virtual.md), machine independent code preferring things like [portability](portability.md), speed of interpretation, retaining meta information or being easy to translate.
5 TODO: moar
7 ## Example
9 Let's consider a simple algorithm that tests the [Collatz conjecture](collatz_conjecture.md) (which says that applying a simple operation from any starting number over and over will always lead to number 1). The program reads a number (one digit for simplicity) and then prints the sequence until reaching the final number 1. The algorithm in [C](c.md) would look as follows:
11 ```
12 // Collatz conjecture
13 #include <stdio.h>
15 int next(int n)
16 {
17 return n % 2 ? // is odd?
18 3 * n + 1 :
19 n / 2;
20 }
22 int main(void)
23 {
24 int n = getchar() - '0'; // read input ASCII digit
26 while (1)
27 {
28 printf("%d\n",n);
30 if (n == 1)
31 break;
33 n = next(n);
34 }
36 return 0;
37 }
38 ```
40 C will be normally compiled to [machine code](machine_code.md), however we can take a look at some immediate representation bytecode that compilers internally use to generate the machine code. The following is [LLVM](llvm.md), a widely used bytecode that can be produced from the above C code with [clang](clang.md) compiler (e.g. as `clang -cc1 tmp.c -S -emit-llvm -o -`):
42 ```
43 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
44 target triple = "x86_64-pc-linux-gnu"
46 @.str = private unnamed_addr constant [4 x i8] c"%d\0A\00", align 1
48 ; Function Attrs: noinline nounwind optnone
49 define i32 @next(i32 %n) #0 {
50 entry:
51 %n.addr = alloca i32, align 4
52 store i32 %n, i32* %n.addr, align 4
53 %0 = load i32, i32* %n.addr, align 4
54 %rem = srem i32 %0, 2
55 %tobool = icmp ne i32 %rem, 0
56 br i1 %tobool, label %cond.true, label %cond.false
58 cond.true: ; preds = %entry
59 %1 = load i32, i32* %n.addr, align 4
60 %mul = mul nsw i32 3, %1
61 %add = add nsw i32 %mul, 1
62 br label %cond.end
64 cond.false: ; preds = %entry
65 %2 = load i32, i32* %n.addr, align 4
66 %div = sdiv i32 %2, 2
67 br label %cond.end
69 cond.end: ; preds = %cond.false, %cond.true
70 %cond = phi i32 [ %add, %cond.true ], [ %div, %cond.false ]
71 ret i32 %cond
72 }
74 ; Function Attrs: noinline nounwind optnone
75 define i32 @main() #0 {
76 entry:
77 %retval = alloca i32, align 4
78 %n = alloca i32, align 4
79 store i32 0, i32* %retval, align 4
80 %call = call i32 (...) @getchar()
81 %sub = sub nsw i32 %call, 48
82 store i32 %sub, i32* %n, align 4
83 br label %while.body
85 while.body: ; preds = %entry, %if.end
86 %0 = load i32, i32* %n, align 4
87 %call1 = call i32 (i8*, ...) @printf(i8* ... )
88 %1 = load i32, i32* %n, align 4
89 %cmp = icmp eq i32 %1, 1
90 br i1 %cmp, label %if.then, label %if.end
92 if.then: ; preds = %while.body
93 br label %while.end
95 if.end: ; preds = %while.body
96 %2 = load i32, i32* %n, align 4
97 %call2 = call i32 @next(i32 %2)
98 store i32 %call2, i32* %n, align 4
99 br label %while.body
101 while.end: ; preds = %if.then
102 ret i32 0
103 }
105 declare i32 @getchar(...) #1
107 declare i32 @printf(i8*, ...) #1
109 attributes #0 = { ... }
110 attributes #1 = { ... }
112 !llvm.module.flags = !{!0}
113 !llvm.ident = !{!1}
115 !0 = !{i32 1, !"wchar_size", i32 4}
116 !1 = !{!"clang version 7.0.1-8+deb10u2 (tags/RELEASE_701/final)"}
117 ```
119 TODO: analyze the above
121 Now let's rewrite the same algorithm in [comun](comun.md), a different language which will allow us to produce another kind of bytecode (obtained with `comun -T program.cmn`):
123 ```
124 # Collatz conjecture
126 next:
127 $0 2 % ? # is odd?
128 3 * 1 +
129 ;
130 2 /
131 .
132 .
134 <- # read input ASCII digit
135 "0" - # convert it to number
137 @@
138 # print:
139 $0 10 / "0" + ->
140 $0 10 % "0" + ->
141 10 ->
143 $0 1 = ?
144 !@
145 .
147 next
148 .
149 ```
151 Here is annotated comun bytecode this compiles to:
153 ```
154 000000: DES 00 0111 # func \ next:
155 000001: JMA 00 0100... # 20 (#14) |
156 000002: COC 00 0001 |
157 000003: MGE 00 0000 | $0
158 000004: CON' 00 0010 # 2 (#2) | 2
159 000005: MOX 00 0000 | %
160 000006: DES 00 0001 # if | \ ?
161 000007: JNA 00 0000... # 16 (#10) | |
162 000008: COC 00 0001 | |
163 000009: CON' 00 0011 # 3 (#3) | | 3
164 00000a: MUX 00 0000 | | *
165 00000b: CON' 00 0001 # 1 (#1) | | 1
166 00000c: ADX 00 0000 | | +
167 00000d: DES 00 0010 # else | < ;
168 00000e: JMA 00 0011... # 19 (#13) | |
169 00000f: COC 00 0001 | |
170 000010: CON' 00 0010 # 2 (#2) | | 2
171 000011: DIX 00 0000 | | /
172 000012: DES 00 0011 # end if | / .
173 000013: RET 00 0000 / .
174 000014: INI 00 0000
175 000015: INP 00 0000 <-
176 000016: CON' 00 0000... # 48 (#30) "0"
177 000017: COC 00 0011
178 000018: SUX 00 0000 -
179 000019: DES 00 0100 # loop \ @@
180 00001a: MGE 00 0000 | $0
181 00001b: CON' 00 1010 # 10 (#a) | 10
182 00001c: DIX 00 0000 | /
183 00001d: CON' 00 0000... # 48 (#30) | "0"
184 00001e: COC 00 0011 |
185 00001f: ADX 00 0000 | +
186 000020: OUT 00 0000 | ->
187 000021: MGE 00 0000 | $0
188 000022: CON' 00 1010 # 10 (#a) | 10
189 000023: MOX 00 0000 | %
190 000024: CON' 00 0000... # 48 (#30) | "0"
191 000025: COC 00 0011 |
192 000026: ADX 00 0000 | +
193 000027: OUT 00 0000 | ->
194 000028: CON' 00 1010 # 10 (#a) | 10
195 000029: OUT 00 0000 | ->
196 00002a: MGE 00 0000 | $0
197 00002b: CON' 00 0001 # 1 (#1) | 1
198 00002c: EQX 00 0000 | =
199 00002d: DES 00 0001 # if | \ ?
200 00002e: JNA 00 0100... # 52 (#34) | |
201 00002f: COC 00 0011 | |
202 000030: DES 00 0101 # break | | !@
203 000031: JMA 00 1000... # 56 (#38) | |
204 000032: COC 00 0011 | |
205 000033: DES 00 0011 # end if | / .
206 000034: CAL 00 0011 # 3 (#3) | next
207 000035: DES 00 0110 # end loop / .
208 000036: JMA 00 1010... # 26 (#1a)
209 000037: COC 00 0001
210 000038: END 00 0000
211 ```
213 TODO: analyze the above, show other bytecodes (python, java, ...)
215 Let's try the same in [Python](python.md). The code we'll examine will look like this:
217 ```
218 # Collatz conjecture
220 def next(n):
221 return 3 * n + 1 if n % 2 != 0 else n / 2
223 n = ord(raw_input()[0]) - ord('0')
225 while True:
226 print(n)
228 if n == 1:
229 break
231 n = next(n)
232 ```
234 And the bytecode we get (e.g. with `python -m dis program.py`):
236 ```
237 3 0 LOAD_CONST 0 (<code object next at ...)
238 3 MAKE_FUNCTION 0
239 6 STORE_NAME 0 (next)
241 6 9 LOAD_NAME 1 (ord)
242 12 LOAD_NAME 2 (raw_input)
243 15 CALL_FUNCTION 0
244 18 LOAD_CONST 1 (0)
245 21 BINARY_SUBSCR
246 22 CALL_FUNCTION 1
247 25 LOAD_NAME 1 (ord)
248 28 LOAD_CONST 2 ('0')
249 31 CALL_FUNCTION 1
250 34 BINARY_SUBTRACT
251 35 STORE_NAME 3 (n)
253 8 38 SETUP_LOOP 43 (to 84)
254 >> 41 LOAD_NAME 4 (True)
255 44 POP_JUMP_IF_FALSE 83
257 9 47 LOAD_NAME 3 (n)
258 50 PRINT_ITEM
259 51 PRINT_NEWLINE
261 11 52 LOAD_NAME 3 (n)
262 55 LOAD_CONST 3 (1)
263 58 COMPARE_OP 2 (==)
264 61 POP_JUMP_IF_FALSE 68
266 12 64 BREAK_LOOP
267 65 JUMP_FORWARD 0 (to 68)
269 14 >> 68 LOAD_NAME 0 (next)
270 71 LOAD_NAME 3 (n)
271 74 CALL_FUNCTION 1
272 77 STORE_NAME 3 (n)
273 80 JUMP_ABSOLUTE 41
274 >> 83 POP_BLOCK
275 >> 84 LOAD_CONST 4 (None)
276 87 RETURN_VALUE
277 ```
279 TODO: make sense of it and analyze it
281 TODO: web assembly