format compact % Help MATLAB save screen space
All compilers have to connect to the underlying hardware. That in turn requires knowing where the bits need to go. It isn't always fun, but that is what compiler writers do.
Completing this task definitively answers the original question of "how far" can you take the idea of bootstrapping. Anything the computer can do is made accessible by execution.
The target machine is the Intel X86 (486, pentium, ...). What you, the reader, needs to know about the X86 is that it has eight general registers and a floating point stack (FPS). 32-bit 2's complement integer arithmetic is done in four of the eight general registers (EAX, ECX, EDX, EBX).
IEEE floating point arithmetic is done on the FPS. The hardware has a vast number of variable-length instructions. Such a computer is generally designated as CISC, or "Complicated Instruction Set Computer".
The program G.exe made available below accesses MEX files. Before you can execute these MEX files you must call the MATLAB function makeMex.m in the directory containing the M and C code.
The first step here is an assembler that lays out the bits exactly as required for execution on last year's Intel hardware.
The simplest program that can be run is a subroutine prolog followed by a subroutine epilog. It does nothing useful but illustrates getting into and out of execution (and not blowing up). Here are two IOGs giving the X86 assembly language for prolog and epilog.
fprintf('%s', G.prolog); fprintf('%s', G.epilog);
pushR EBP movRR EBP ESP pushA popA xor EAX EAX leave ret
They can be turned into hexadecimal with a little stub of an assembler.
p = i p; p =; i = 'leave' e "C9"; i = 'movRR EBP ESP' e "89E5"; i = 'popA' e "61"; i = 'pushA' e "60"; i = 'pushR EBP' e "55"; i = 'ret' e "C3"; i = 'xor EAX EAX' e "33C0"; e = ' ';
Assembling the prolog/epilog pair:
assembled = GEM([G.prolog G.epilog], G.asm); fprintf('assembled prolog and epilog:\n%s', assembled);
assembled prolog and epilog: 5589E5606133C0C9C3
Intel fans will recognize 55 as pushing the base register and C9C3 as restoring the base register and program counter. In fact the output is a MATLAB string (16 bits per character). The data needs to be 4 bits each in the range 0:15. That (trivial) transformation is carried out by G.exe. Then G.exe calls another MEX file runX86.c which points the hardware at the newly constructed bits for execution. The trick in runX86.c is casting a pointer to the data containing the hex bits into a pointer to a function and then calling the function.
The calling sequence for runX86.c allows no parameters and returns only one value (usually the return code). This limitation can be relaxed by rewriting runX86.c. You can see an example in the mxcom/m directory.
Or, instead, the assembler can be turned into a disassembler by invert, and the disassembler used to recreate the original assembly code.
invertedbits = GEM(assembled,GEM(G.scan(G.asm), G.invert, 'A')); fprintf('disassembled prolog and epilog:\n%s', invertedbits);
disassembled prolog and epilog: pushR EBP movRR EBP ESP pushA popA xor EAX EAX leave ret
If you are interested in the new files runX86.c and gem5.m, you can download this File Exchange submission and look at them in the MATLAB editor.
Instead of assembler, one can compile and run a little 4-register integer calculator language. Here is a grammar for the calculator:
calc = assignment*; assignment = variable '=' value; assignment = variable operator '=' variable;
- variable is one of a, b, c, d
- value is a digit ( 0, 1, ... 9)
- operator is one of +, -, * and | (logical or, not divide).
This calculator can (obviously) be extended, but this is enough to give the idea.
As above, the sequence of calculations is compiled into Intel X86 binary, run, and also decompiled.
make31 = 'b=9;a=3;c=4;a*=b;a+=c;'; compiled = GEM(make31,G.calc, 'D'); fprintf('compiled = %s\n', compiled); executed = G.exe(compiled); fprintf('executed = %d\n',executed); invertedcalc = GEM(G.scan(G.calc),G.invert, 'A'); decompiled=GEM(compiled, invertedcalc, 'D'); fprintf('decompiled = %s',decompiled);
compiled = 554889E5B909000000B803000000BA040000000FAFC101D0C9C3 executed = 31 decompiled = b=9;a=3;c=4;a*=b;a+=c;
Unix function atoi can be implemented by compiling an ad hoc bit of x86 code for a specific string.
make376 = GEM('376', G.atoi); fprintf('make376=%s\n', make376); intval = G.exe(make376); fprintf('intval=%d\n', intval);
The story concludes with the next chapter.