[M3devel] m3cc static chain stuff

[Rodney M. Bates]

Jay K wrote:
>> From: hosking at cs.purdue.edu
>> Date: Wed, 26 May 2010 10:28:51 -0400
>> To: jay.krell at cornell.edu
>> CC: m3devel at elegosoft.com
>> Subject: Re: [M3devel] m3cc static chain stuff
>>
>>
>>
>> We should endeavour to use the same functionality that the C compiler uses for its own nested functions, 

whereever possible. The only thing is that we also build closures, so the trampoline mechanisms should be avoided.
> 
> 
> Right..for those that don't know..
> 
> 
> There's no "good" efficient way to implement nested functions.
> Our implementation is pretty "bad".
> gcc's implementation is pretty "bad".

I think this is far too critical.  The inefficiencies you see are
minor.  Certainly no worse than the implementation of dispatching
methods of objects, something the world is gaga about.  And the
inefficiencies I think you are worrying about only arise when
you pass procedures as parameters.




> They are different.
> 
> 
> gcc (Tony mentions "trampoline"):
> In particular, taking the address of a nested function
> involves runtime code generation on the stack.
> These days, running code on the stack is "difficult".
> On some systems, you do mprotect() to make that part of the stack executable.
> On other systems, you just can't do it (iPhone).
> On older systems, no problem. It is simple and efficient.
> 

Yes, that is one consequence of trampolines.  There has to be a place
to generate code at runtime that will be executable, and a way to
memory-manage it.

> 
> Modula-3:
> Whenever we go to call a function pointer, we first see if it start with a 4 or 8 byte -1.
> If so, it is our "closure" thingy, and the -1 is followed
> I guess by an actual function pointer and a static link.
> The static link is loaded wherever and the function called.
> 
> 
> Other systems (see modern ATL on Windows) allocate executable
> memory not on the stack. Not even regular heap is executable
> generally any longer though, one need to VirtualAlloc or mmap or such.
> 
> 
> This is a powerful mechanism in general, you can do stuff like
> runtime "currying".
> 
> 
> Pointers to nested Modula-3 function cannot be passed off
> as function pointers to other languages.
>   But hey, at least we can write nested functions and pass
>     them off to ourselves. Interop with C would just be bonus?
> 

But if we used trampolines instead of our form of closures, they
could be.  Or, more generally, if we used the same mechanism as
"other languages", they could be.

> 
> Calling function pointers in Modula-3 is slowed down
> everywhere, in case the function pointer is nested.
> I think.

Only calling procedures through a procedure-typed _parameter_ is
slowed down.  Calling through a procedure-typed _variable_ is known,
by language semantics, always to be to a top-level procedure, and
is as fast as a C call to a non-nested function pointer.
Note that, when calling a function pointer to a nested procedure,
trampolines are surely about as fast as you can get.

> 
> 
> -1 must be ensured to be invalid code.
> Or we could make it a more visible part of porting.
>  You know -- it could be per-target and folks would have
>  to experiment with each target to find a good sequence,
>  that is cheap to detect and guaranteed invalid.
>  (ie: 0 might be better than -1!)
> 
> 
> Could possibly replace the -1 with an actual function pointer
> that is always called.
> But then pointers to non-nested functions also wouldn't
> interoperate with C.

I don't understand what mechanism you are proposing here.  Taken
literally, it sounds like a trampoline to me, which would allow
non-nested and nested function pointers to interoperate with C.

> 
> 
> I think there's something more to the mechanisms than I realize.
> The "static link" must survive calls out to non-nested functions
> or somesuch.
> 
> 
> Anyway, while I think our mechanism is pretty clearly flawed,
> it seems to be slightly less bad than gcc's.
> 

I'm not sure what you mean by flawed, but if you mean it doesn't
correctly implement language semantics, that is not true.  It works
correctly.  So do trampolines, although in C (for other reasons that
are independent of what mechanism you use for function pointers),
the semantics of the language have a big hole.  As usual, C passes
the buck by defining this as "undefined".

> 
> Perhaps we should invest in what ATL does though and
> dynamically allocate executable memory not on the stack?

If there is a way to do this, then trampolines can be made to work.
What does gcc do now on such targets?

> Still, an "open" iPhone is probably better with the current scheme.
> Most other systems should be ok either way.
> 
> 
> I think there is a bit of 4.3=>4.5 that needs closer attention
> and isn't obvious, this part:
> 
> +    case STATIC_CHAIN_EXPR:
> +      decl = TREE_OPERAND (t, 0);
> +      target_context = decl_function_context (decl);
> +      if (target_context)
> +    {
> +      if (info->context == target_context)
> +        {
> +          /* Make sure frame_decl gets created.  */
> +          (void) get_frame_type (info);
> +        }
> +      *tp = get_static_chain (info, target_context, &wi->tsi);
> +    }
> +      else
> +    *tp = null_pointer_node;
> +      break;
> +
> 
>  - Jay
>  

Jay, you have made it clear repeatedly that you only use gdb, and
never m3gdb, so obviously, Modula-3-specific support is of no importance
to you.  That's OK, but please don't spoil the game for those of us
who do care about it by ripping stuff out of the compiler that m3gdb
needs.  Even when it isn't fully working yet.