[M3devel] gcc 4.5 static chain

[Jay K]

Here's some background as to why it is taking me so long to
get gcc 4.5 working.


Two of gcc's internal data structures are "tree" and "gimple".


"tree" is a somewhat intuitive structure that roughly
corresponds to a C AST ("abstract syntax tree").
It has stuff like plus, and call.
I believe it is meant to support any gcc frontend: Ada, Java, etc.


"tree" is produced by the C frontend and our "parse.c"
 (The Modula-3 gcc backend is structured as a gcc frontend,
 producing similar in-memory data as the C frontend. "backend"
 and "frontend" get confused.)


I believe "tree" has been there "forever", for as long
as DEC SRC Modula-3 has had a gcc backend.
(2.x presumably)


"gimple" is very much like tree, but it is less general.
it is more amenable to optimization.
Things like loops are deconstructed into goto.
I think.


"gimple" is newer, like dating to gcc 4.x.
Previously optimization operated on tree and/or rtx and neither was great.
rtx is too low level. tree is too high level.


Gimple I think was originally just exactly tree but with
some of the node types not used. Confusing. Faster to write it,
reused the tree code, but confusing. Gives "tree" multiple meanings.
In 4.4 or 4.5 they made it its own type.
I think, for one thing, it now is made up of nodes with small arrays
instead of nodes with node pointers.



Or something like this.
I'm mostly just repeating what you can read online elsewhere from
 more authoritative and clearer sources.
 

So, at some point, "tree" is converted to "gimple".
  Though, this is a very confusing point to me.
  It appears that really the compiler deals with a significant
  mix of "tree" and "gimple". Perhaps that is inevitable. Perhaps
  tree can only be gradually converted to gimple.
  

Anyway, among the "tree codes" such as plus, call, etc., we add one.
We add to load a static link.
For the current function?
For a specific function to be called?
I find this point not obvious.


So then, given that we have introduced a tree code, we must teach
other parts of gcc about it.


Tangent.


tree-nested.c converts nested functions into non-nested functions.
As needed, it moves locals into structs, adds "display" parameters
to nested functions, changes references to outer locals into
accesses through the "display", etc.


Again, this is a transformation we probably could/should make ourselves in m3front.


Only the locals that are actually accessed are moved into a local struct.
Presumably only nested functions that reference outer locals get the extra parameter.
And so on.


In gcc-4.3/tree-nested.c we deal with our tree code.
We appear to do two things:
 
 - we ensure that the function we are getting a static link for has one
    I don't understand that actually. gcc is already doing similar.
    Why do we need to do more? 
  
  - it replaces the load of the static link with, uh, the load of the
    static link -- it replaces the tree node with our custom tree code
    with the tree node representing actually computing/getting the value we want
    It is a little fishy to me btw how this is done.
    Is overwriting *tp really the way?
    In 4.5 there are functions to insert/after/replace within the gimple
    iterator. I wonder if there is similar in 4.3.


Now, the difference in 4.5 is that "gimplification" happens earlier.
The code in 4.3 that we change to deal with tree and our custom tree code,
is now dealing with gimple instead.


Therefore, I believe part of the 4.5 change is a simple translation
of the tree code to a new gimple code.


And then some corresponding change in 4.5.


Btw, it appears gimplify_expr is also a "lang hook", which means
more of our code can move out of line to parse.c.


I haven't figured it all out yet.


I should further note that gcc's notion of a nested function is almost
identical to Modula-3's.


You know, this movement of locals into a local struct, the accepting
an extra parameter pointing to that struct in nested functions, gcc
and Modula-3 are the same.


Therefore tree-nested.c does a lot of work and it is almost all useful/relevant
to us.


The difference is only what happens when you take the address of a nested function.
Or perhaps when you call them.


gcc generates a little bit of code at runtime to add the static link parameter
 (e.g. on x86/AMD64 to load into a designated register: r10 for AMD64, ecx for x86,
 see the function ix86_static_chain).
Modula-3 generates a little bit of data: marker, function pointer, static chain,
and the caller does extra work.


There are significant tradeoffs either way and there is, I'm convinced,
absolutely no good way to do this.
gcc generates code at runtime, generally on the stack.
  These days the stack is not by default executable, in order to
  protect against viruses etc. overflowing buffers on the stack
  and writing code to the stack.
Modula-3 has to check function pointers before calling them.


As I said, neither is good, there's no good solution.
  Better perhaps to do the transform yourself. Then you have
  the option of putting the context on the stack or heap as well.
  Better perhaps to expose programmer to the cost. Perhaps.


Perhaps the C ABIs could have reserved a register for this, but I'm not sure
that makes sense. Would you load it up and it remains preserved until changed?


But I digressed.


 - Jay