[fonc] port of jolt-burg

[John Leuner]

I've been working on an experimental port of jolt-burg. The main
difference is that my implementation language is Common Lisp and that my
compiler targets relocatable ELF object files.

Currently I have a compiler that can read sexp input, eg:

(define |main| (lambda ()
((call-c |dlsym| 0 "puts") "hello, dynamic world!")))

and then compile it down to a tree of blocks and instruction objects
(see instruction.lisp or Instruction.st)


BLOCK(--- NIL ---)
| | 0(--- VOID BLOCK --- 369
| | | | | 0(+++ REG CALLI4 ---
| | | | | | 0(+++ REG CNSTP4 --- reloc ---)
| | | | | | 0(+++ REG CNSTI4 --- 0)
| | | | | | 0(+++ REG CNSTP4 --- reloc ---))
| | | | | 0(+++ REG CNSTP4 --- reloc ---))
| | 0(--- VOID BLOCK --- 369
| | | | | 0(+++ REG CALLI4 EBX
| | | | | | 0(+++ REG CNSTP4 EBX reloc ---)
| | | | | | 0(+++ REG CNSTI4 EAX 0)
| | | | | | 0(+++ REG CNSTP4 ECX reloc ---))
| | | | | 0(+++ REG CNSTP4 EAX reloc ---))


This tree is processed by the burg compiler to emit x86 machine code.
(in the diagram we see registers being assigned to the tree nodes)

The last stage is when I collect the machine code generated by the burg
compiler and combine it with data and relocation entries to generate an
ELF object file.

I can then pass this to the unix linker (ld) to produce an executable.

ld --dynamic-linker=/lib/ld-linux.so.2 state/start.o state/hello.state.o
-ldl -lc -o myhello

Here you can see the disassembled elf object file with relocation
entries for the "dlsym" symbol and the "puts" and "hello world" strings.

objdump -d state/hello.state.o -r


Disassembly of section .text:

00000000 <main>:
0: 55 push %ebp
1: 89 e5 mov %esp,%ebp
3: 53 push %ebx
4: 83 ec 14 sub $0x14,%esp
7: bb 00 00 00 00 mov $0x0,%ebx
8: R_386_32 dlsym
c: b8 00 00 00 00 mov $0x0,%eax
11: b9 00 00 00 00 mov $0x0,%ecx
12: R_386_32 _data_286
16: 89 4c 24 04 mov %ecx,0x4(%esp)
1a: 89 04 24 mov %eax,(%esp)
1d: ff d3 call *%ebx
1f: 89 c3 mov %eax,%ebx
21: b8 00 00 00 00 mov $0x0,%eax
22: R_386_32 _data_287
26: 89 04 24 mov %eax,(%esp)
29: ff d3 call *%ebx
2b: 89 c0 mov %eax,%eax
2d: 89 c0 mov %eax,%eax
2f: 83 c4 14 add $0x14,%esp
32: 5b pop %ebx
33: 5d pop %ebp
34: c3 ret


You can view the code at:

http://subvert-the-dominant-paradigm.net/repos/hgwebdir.cgi/bootstrap/

(click manifest to see the files, or run 'hg clone <url>' to get a local
copy)

John Leuner

[Michael FIG]

I've been working on an experimental port of jolt-burg. The main difference is
that my implementation language is Common Lisp and that my compiler targets
relocatable ELF object files.

Interesting!

I was inspired by you, and tried my hand at getting similar changes
into jolt2. The attached patch should apply cleanly on top of SVN
-r407, followed by my jolt2-fixes.patch that I posted earlier.

Here is the function/examples2/slink/README file (also included in the
attached jolt2-slink.patch) for more information:

SLINK 0.2
*********

Slink is the beginning of a statically-linking compiler extension for
Jolt2 (think "Static LINK" or "System LINK"). It was partly inspired
by John Leuner's Common Lisp port of jolt-burg that creates
relocatable ELF objects. I'm basically attempting to land the same
kinds of features in COLA proper without changing too much of the
existing compiler machinery.

It has many limitations, but is a proof-of-concept and will probably
evolve (the main direction for evolution is to make the changes less
and less dependent on patching Jolt2's Id sources directly, and
instead accomplish its features at runtime via slink.k and friends).

The centerpiece of this system is slink-compile, which currently can
only generate i386 assembly code. The following new syntax is
introduced:

(define (slink SYMBOL))
Import SYMBOL from the system linker. If running with the dynamic
compiler, this is equivalent to:

(active SYMBOL (dlsym "SYMBOL"))

If under the static compiler (slink-compile), this will cause future
references to SYMBOL to be resolved at link time rather than
runtime.

(define (slink SYMBOL) EXPRESSION)
Create a region of memory containing the results of EXPRESSION.
SYMBOL is exported to the system linker. Only expressions resulting
in integers, strings, floats, and lambdas currently work.

To get a feel for things, run "make test" which exercises slink both
at runtime and compile time. You'll notice that the results of this
execution are a binary executable (slinktest) with no runtime
dependency on COLA.

IMPLEMENTATION
**************

I did a lot of work creating a bunch of slink-specific methods in the
existing COLA compiler. Now I'm gradually undoing as much of that
work as possible to leave only the core features in Jolt2, so that the
rest can be just another unprivileged application.

Once you understand what the slink syntax does, it shouldn't be too
hard to follow what I needed to do to get things working. A "grep -i
slink *.st" is very informative (and half the reason I needed to find
a catchy name that wouldn't be buried in the other identifiers).

Toplevel Jolt expressions are gathered up and attached to the system's
initialisation functions so that they are executed at program start
(for i386, using the same method as C++ constructors).

The syntax and actives systems will need to be revisited, probably to
do something like Scheme-48 where a "load-syntax" or "require-syntax"
will import only the syntax elements into the namespace (thereby
avoiding problems with importing undesired lambdas and toplevel code
evaluation by accident).

It would be really nice to implement a few more CodeGenerator backends
to bypass assembly language entirely and generate binaries.

Slink has a naive three-region model for assembler output. First
comes a bss section with all the variables, then a data section with
all the strings, then finally a text section with all the compiled
functions. To my knowledge, this is adequate for the platforms on
which COLA already runs, but of course it would be good to be able to
provide something akin to linker scripts in the future to allow much
more flexible layout.

Have fun,

[John Leuner]

Post by Michael FIG

I've been working on an experimental port of jolt-burg. The main difference is
that my implementation language is Common Lisp and that my compiler targets
relocatable ELF object files.

Interesting!
I was inspired by you, and tried my hand at getting similar changes
into jolt2. The attached patch should apply cleanly on top of SVN
-r407, followed by my jolt2-fixes.patch that I posted earlier.

...

Post by Michael FIG
It would be really nice to implement a few more CodeGenerator backends
to bypass assembly language entirely and generate binaries.

It shouldn't be too different from what is there already. Although we
have a "static" and "dynamic" generator, the dynamic generator is
perfect for generating relocatable code which can then be linked into a
static executable.

Post by Michael FIG
Slink has a naive three-region model for assembler output. First
comes a bss section with all the variables, then a data section with
all the strings, then finally a text section with all the compiled
functions. To my knowledge, this is adequate for the platforms on
which COLA already runs, but of course it would be good to be able to
provide something akin to linker scripts in the future to allow much
more flexible layout.

For my simple tests I have managed with a .text and .data segment (plus
a list of relocations and a symbol table).

I haven't implemented any initializers for static variables like you
have though.

John

[Nathan Cain]

Hi Michael,

I was hoping to toy with this some, and start in on adapting an arm
backend... unfortunately, the patch does not want to apply, as it seems
to expect a different jolt2/boot.k then what is in svn r407. Perhaps I
need another of your patches as well, beyond just jolt2-fixes? Could
you tell me which?

I've attached my boot.k.rej for you to glance at.

Thanks for any help you can provide,
--Nathan

Post by Michael FIG

I've been working on an experimental port of jolt-burg. The main difference is
that my implementation language is Common Lisp and that my compiler targets
relocatable ELF object files.

Interesting!
I was inspired by you, and tried my hand at getting similar changes
into jolt2. The attached patch should apply cleanly on top of SVN
-r407, followed by my jolt2-fixes.patch that I posted earlier.
Here is the function/examples2/slink/README file (also included in the
SLINK 0.2
*********
Slink is the beginning of a statically-linking compiler extension for
Jolt2 (think "Static LINK" or "System LINK"). It was partly inspired
by John Leuner's Common Lisp port of jolt-burg that creates
relocatable ELF objects. I'm basically attempting to land the same
kinds of features in COLA proper without changing too much of the
existing compiler machinery.
It has many limitations, but is a proof-of-concept and will probably
evolve (the main direction for evolution is to make the changes less
and less dependent on patching Jolt2's Id sources directly, and
instead accomplish its features at runtime via slink.k and friends).
The centerpiece of this system is slink-compile, which currently can
only generate i386 assembly code. The following new syntax is
(define (slink SYMBOL))
Import SYMBOL from the system linker. If running with the dynamic
(active SYMBOL (dlsym "SYMBOL"))
If under the static compiler (slink-compile), this will cause future
references to SYMBOL to be resolved at link time rather than
runtime.
(define (slink SYMBOL) EXPRESSION)
Create a region of memory containing the results of EXPRESSION.
SYMBOL is exported to the system linker. Only expressions resulting
in integers, strings, floats, and lambdas currently work.
To get a feel for things, run "make test" which exercises slink both
at runtime and compile time. You'll notice that the results of this
execution are a binary executable (slinktest) with no runtime
dependency on COLA.
IMPLEMENTATION
**************
I did a lot of work creating a bunch of slink-specific methods in the
existing COLA compiler. Now I'm gradually undoing as much of that
work as possible to leave only the core features in Jolt2, so that the
rest can be just another unprivileged application.
Once you understand what the slink syntax does, it shouldn't be too
hard to follow what I needed to do to get things working. A "grep -i
slink *.st" is very informative (and half the reason I needed to find
a catchy name that wouldn't be buried in the other identifiers).
Toplevel Jolt expressions are gathered up and attached to the system's
initialisation functions so that they are executed at program start
(for i386, using the same method as C++ constructors).
The syntax and actives systems will need to be revisited, probably to
do something like Scheme-48 where a "load-syntax" or "require-syntax"
will import only the syntax elements into the namespace (thereby
avoiding problems with importing undesired lambdas and toplevel code
evaluation by accident).
It would be really nice to implement a few more CodeGenerator backends
to bypass assembly language entirely and generate binaries.
Slink has a naive three-region model for assembler output. First
comes a bss section with all the variables, then a data section with
all the strings, then finally a text section with all the compiled
functions. To my knowledge, this is adequate for the platforms on
which COLA already runs, but of course it would be good to be able to
provide something akin to linker scripts in the future to allow much
more flexible layout.
Have fun,
------------------------------------------------------------------------
_______________________________________________
fonc mailing list
http://vpri.org/mailman/listinfo/fonc

[Michael FIG]

Hi,

Post by Nathan Cain
I was hoping to toy with this some, and start in on adapting an arm
backend...

Cool! I'd be more than happy to help with this process, if you need
any assistance at all. I think most of it should be relatively
straightforward by staring at the patch to CodeGenerator-i386.st.

Post by Nathan Cain
unfortunately, the patch does not want to apply, as it seems to
expect a different jolt2/boot.k then what is in svn r407. Perhaps I
need another of your patches as well, beyond just jolt2-fixes?
Could you tell me which?

Actually, I just described the patch requirements really badly. The
idea is:

$ svn checkout -r407 ...
$ cd idst
$ patch -p0 < ../jolt2-fixes.patch
$ patch -p0 < ../jolt2-slink.patch

I've attached new versions of these patches that fix a few issues
(forgot the '{...} grammar syntax in jolt2-fixes.patch, mangle Jolt
names that can't be directly expressed in the output) and demonstrates
the use of (syntax ...) in function/examples2/slink/main.k.

Good luck,

[Nathan Cain]

Post by Michael FIG
Hi,

Post by Nathan Cain
I was hoping to toy with this some, and start in on adapting an arm
backend...

Cool! I'd be more than happy to help with this process, if you need
any assistance at all. I think most of it should be relatively
straightforward by staring at the patch to CodeGenerator-i386.st.

Yes, i've spent the past few days staring at it, alongside the original
-i386 and the -arm generators, and think it's sufficiently stared at for
a reasonable understanding of how it will come together.

Post by Michael FIG

Post by Nathan Cain
unfortunately, the patch does not want to apply, as it seems to
expect a different jolt2/boot.k then what is in svn r407. Perhaps I
need another of your patches as well, beyond just jolt2-fixes?
Could you tell me which?

Actually, I just described the patch requirements really badly. The
$ svn checkout -r407 ...
$ cd idst
$ patch -p0 < ../jolt2-fixes.patch
$ patch -p0 < ../jolt2-slink.patch
I've attached new versions of these patches that fix a few issues
(forgot the '{...} grammar syntax in jolt2-fixes.patch, mangle Jolt
names that can't be directly expressed in the output) and demonstrates
the use of (syntax ...) in function/examples2/slink/main.k.

Yup, it looks like this jolt2-fixes patch should resolve the problem I
was running into with the slink patch. I'll let you know how it goes
from here!

Thanks much,
--Nathan

Post by Michael FIG
Good luck,
------------------------------------------------------------------------
_______________________________________________
fonc mailing list
http://vpri.org/mailman/listinfo/fonc