Back-end HOWTO

[acken@informatik.uni-kl.de]

Last week someone asked me what had to be done to implement a
back-end.  I couldn't give an adeqaute answer, because I hadn't put
much thought into this (and I don't really want to).  So I decided to
put together a list of possible implementation steps and let the
back-end people discuss/correct it and put more details into it.  Here
it comes: 


Code generation:

1) Turn GSA opcodes into instructions for the target architecture.
Most of the opcodes are fairly easy to translate, others need more
work.

adr: 
  The front-end can only emit these symbolic address references, they
  have to stay in the code until all procedure inlining has been
  done.  Has to be replaced by a number of instructions that calculate
  the address of a global, nonlocal, local variable, a constant, or a
  type descriptor.

array-length, type-tag, tb-proc-adr, type-test, type-guard, type-assert:
  All these instructions somehow depend on the layout of type
  descriptors and the placement of type information on the heap.  The
  high level type test instructions allow to implement a type-flow
  analysis that takes type tests and guards into account.  All these
  instructions will have to be turned into some address calculations,
  a memory access or two, and maybe a comparison or a trap. [Come to
  think of it, the address calculations should be visible to the  
  optimizers, similar to the address values of access instructions of
  record fields and array elements.  I think all the above mentioned
  instructions should be extended by an additional argument that is
  calculated by back-end hooks called from the front-end.]

bound-index, bound-range:
  Probably translated into a (single) comparison plus a branch and a
  trap.  Since both opcodes test against 0 <= x < y, it's only
  necessary to do a _unsigned_ comparison x < y.

cc, access-reg, update-reg:
  I don't think that there is much sense in testing a processors
  condition code or accessing registers from GSA level.  Probably
  the predefined procedures CC, GETREG, PUTREG will have to be
  removed.  Or has anyone a better suggestion?

zero, string-copy, bit, bit-range, eqlstr, neqstr, etc:
  These instructions can be (and probably should be) translated
  into standard GSA code, leaving the question when this should.  The
  string comparison opcodes should stay in the code until constant
  propagation and common subexpression elimination has been run.

new, new-block:
  Have to be replaced by calls to the appropiate functions of the
  run-time system. 

enter, exit, call:
  The enter and exit instructions correspond to procedure prolog and
  epilog respectively.  A lot of implicit values are passed between
  the three of them: return address, stack pointer, static or dynamic
  links, static base pointers.  I don't know if (and how) these
  implicit values should be introduced by the front-end or at a later
  stage.  Can anyone work this out?

A lot of instructions (like access and update) will simply turn into a
nop or into a load resp. store.  Other instructions (like gates) can
only be handled after all location attributes have been assigned.

2) Do peephole optimizations.
Try to take advantage of higher level instructions of the target
architecture, for example by combining several instructions into a
more complex one.  

3) Do register and storage allocation.
In this step the location attributes of all results and operands have
to be set.  Instructions that move values to the appropiate locations
(like load and store) have to be introduced.  The instructions that
need locations (gate) have to converted.  After this step all
instructions are complete, i.e., they have been assigned their target
opcode and the location (register index, memory address) of their
operands and results is defined.

4) Do instruction scheduling.
Arrange the instructions in a valid way, taking pecularities of the
target archictectures pipeline(s) into account.  The GSA control flow
(modeled by guards and merges) has to be translated into conditional
branches and jumps.  Only this step introduces a linear ordering of
instructions, all previous steps work on the half ordering introduced
by the GSA operand/result dependencies.

5) Emit code into object files.
This step can probably combined with the instruction scheduling.


There are some odds and ends to consider.  GSA's notion of data flow
is somewhat peculiar.  It considers every result of an instruction as
an unique value that is defined once and never changed again.
Therefore every result is a distinct copy of a value that remains
static over its entire lifetime.  But in the target code you don't
want to keep multiple copies of structured variables in memory, you
rather map all copies onto a single location.  See [Bra95], section
9.1, for a discussion of this problem.




Other stuff:

1) Adjust the configuation modules Config.Mod and StdTypes.Mod.  Note
that the size of the standard types shouldn't be modified (although
the alignment may need to be modified).

2) Put together a run-time system to handle memory allocation, do
garbage collection, to handle failed run-time checks (i.e. emit a
appropriate error message), to raise and catch exceptions, ... [what
else has to be added to this list?]

3) Provide implementations for the system-dependent libraries
(e.g. the i/o stuff).  



Remember this list is put together by someone who doesn't know
anything about native code back-ends or how to translate GSA into CPU
opcodes.  Don't believe everything I put here and please discuss open
questions on the mailing list.  I'll update this text accordingly. 

-- mva