Re: compile
From: Ray Dillinger (bear_at_sonic.net)
Date: 02/05/04
- Next message: Erann Gat: "Re: Understanding #' and function variables"
- Previous message: Joe Marshall: "Re: Understanding #' and function variables"
- In reply to: Ari Johnson: "Re: compile"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Thu, 05 Feb 2004 17:54:01 GMT
Ari Johnson wrote:
>
> ways to improve it. One thing that I'd like to do is make it into a
> to-native-code compiler, specifically for the Z80 in my TI-85. (Don't
> ask 'why', I'm infamous for answering 'because I got bored'. :P)
Scheme on a Z80? Whee!
> There are a few points that I don't know how other compilers do, though:
> 1. What do you do about garbage collection? Is this part of a
> standard library that gets linked into every executable, like _init from
> crt0.s in C does? I'm guessing it gets called by the memory allocation
> routines when needed, and that those are also linked in.
A garbage collector basically has to provide three calls:
1) GCMalloc, which allocates memory on a garbage-collected heap. GCMalloc
needs to know how much *working* memory an object must contain and needs
to have a map of which fields in it are pointers. (If you design all your
objects so that pointers are compacted toward the front, just knowing
how many pointers are in an object will suffice).
2) Register, which identifies some pointer or GCMalloc'd structure as
being in the "root set" for garbage collection.
3) Collect, which frees GCMalloc'd objects not reachable by traversing
known pointers starting from the root set. In some implementations,
Collect is actually a separate thread that loops infinitely. In
others, it's called implicitly every time there's a jump to a lower
address. If it's called very often, it's usually made "incremental",
meaning it doesn't do very much before it returns and it may take
hundreds of calls to reap all the floating garbage.
These three things work together. Usually malloc is called to get one
or more 'arenas' of memory that GCMalloc allocates from. This has other
benefits too, since if you allocate particular types from particular
arenas, you can recognize the type of something by the high-order bits
of the pointer that points to it. GCMalloc usually allocates at least
a word or two more than is visible to the program to facilitate the
operation of Collect, although their contents will vary depending on
the collection algorithm.
> 2. What about type resolution? The compiler has no way of knowing
> what data type a given expression will evaluate to, so how are things
> like + implemented? Do they have to play bitwise tricks like my
> interpreter does (a la GNU Scheme's method), or is there a better way?
Depends on the sophistication of the system. A GCMalloc'd value will
always carry information indicating its type. Immediate values (numbers
and characters in most implementations don't have to be GCMalloc'd and
can be stored in the same space as a pointer to some other kind of value)
are widely implemented using bitwise tricks for performance: If you
determine that you can allocate all objects on 8-byte boundaries, it
follows that the low 3 bits of an address will always be zero. That
means you can use those three bits to indicate non-pointer types as long
as the values of the non-pointer immediate types fit into (pointersize -
3) bits of memory. Sometimes there will be auxiliary registers in an
object and the 'marked' pointers indicate only which auxiliary register
to look in. This allows full-sized or even oversized 'immediate' values.
Things that are too big for immediate representation have to be GCMalloc'd,
and in that case, if GCMalloc always takes the memory for particular
types from particular arenas, then you can determine the type from the
high bits of the pointer. Although it's usually simpler to just follow
the pointer and read the typetag in the object, it can be a cache miss,
so knowing the type before following the pointer is a performance win
sometimes.
Sometimes an implementation is able to *prove* that all calls to + from
a particular set of call site will have an integer*integer call type.
In that case it can compile a special version of '+' that skips all
typechecking and link it to (or, if + is a constant, inline it at)
that set of call sites, while simultaneously having a version of '+'
that performs normal typechecking and is linked to other call sites.
> 3. How are function parameters marshalled? As a list or are they
> pushed on the stack as in normal C calling conventions? If the latter,
> how do you deal with optional and 'rest' arguments?
The simplest implementation is for arguments to be a list. Higher
performance puts them on the stack or (if the system has continuations)
into a GCMalloc'd invocation frame. Functions that take optional and
'rest' arguments most commonly take their additional arguments as a
list. For higher performance, they may be compiled in multiple versions
for different numbers of arguments, or the call sites may be "extended"
in compilation with dummy arguments so as to fake a call to a routine
that takes all the args.
> 4. How are macros implemented? Do you have to include a complete
> Lisp interpreter in the linked executable to evaluate the arguments? I
> guess that knowing how 'eval' works in compiled code would be very
> helpful here.
Macros are implemented as a set of instructions for a Lisp program about
how to transform another Lisp program. The result is a macro-less lisp
program which is then compiled. In Lisp and Scheme, Macros no longer
exist after compilation.
> 5. How does memory management typically work?
Carefully.
> 6. What am I missing?
Since you mentioned scheme specifically, I'll say continuations.
Bear
- Next message: Erann Gat: "Re: Understanding #' and function variables"
- Previous message: Joe Marshall: "Re: Understanding #' and function variables"
- In reply to: Ari Johnson: "Re: compile"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
