[M3devel] Target.Aligned_procedures and closure markers?

[Rodney M. Bates]

On 08/30/2015 02:45 AM, Jay K wrote:
> The agenda remains seeing if Target variables can be made constants.
>
> The discussion in this case is more complicated and some facts are unclear.
>
>
> Background:
>
>
> Nested functions are a problem.
> In particular, if you can take their address.
> Taking the address of a nested function presents a problem.
> You are presented with two or three solutions.
>
>
>   - runtime code gen
>     - either on the stack
>
>     - or somewhere more expensive, possibly with garbage collection
>
>     - possibly "templated" instead of "arbitrary"; the meaning
>       of this is a lot to explain -- related to libffi and mremap, which
>      isn't entirely portable, but is e.g. portable to Windows
>
>
>    - or instead of runtime codegen, altering how function pointers are
>      called; you can only do this from Modula-3 code, not e.g. C or C++.
>
>
> The solution Modula-3 has taken is to alter how funtion pointers are called.
> The sequence is roughly:
>     Check if it is a "regular" function pointer or a "closure".
>     If it is a "regular" function pointer, just call it.
>     If it is a "closure", it contains a function pointer and a "static link".
>       Call the function pointer, passing the static link.
>
>
>    To tell if it is "regular" function pointer or a "closure", roughly
>    what is done is the data at the function pointer is read and compared
>    against a marker value. If it equals the marker value, it is a closure.
>
>
>    The size of the marker is the size of an integer or pointer (4 or 8 bytes).
>    The value of the marker checked for is 0 or -1, I'd have to check.
>    The alignment of the pointer might be a factor. In particular, on most
>    architectures, all instructions have a certain alignment. If the pointer has
>    less alignment, it can't be an instruction. Or maybe on those architectures,
>    the bytes are read one at a time to avoid alignment faults.
>
>
>    In particular, as far as I know, the following:
>     x86/amd64: no alignment of instructions, but functions maybe, but Modula-3 assumes functions aren't aligned
>
>     ppc32/ppc64/alpha32/alpha64/mips32/mipa64/sparc32/sparc64/arm64/hppa32/hppa64 -- instructions are all
>      4 bytes and 4 byte aligned, so functions are at least also as much
>
>     arm32 -- instructions are 2 or 4 bytes; if they are 2 bytes, then the instruction
>      pointer is actually odd as well, and the low bit is removed to really find the instructions
>      That is -- instruction pointer is either odd or 4-aligned, never 2-aligned.
>
>     ia64 -- instructions come in bundles of 3, they are 41 bits each, with a 5 bit "template" in each
>      bundle, for a total of 128 bits per bundle, likely always 128-bit-aligned
>
>
>    I could use confirmation on much of this.
>
>
>    I find the use of a marker value a little dubious. It'd be good to research if there is one
>    value that works on all.
>
>
>    I find the choice of a marker size to be pointer-sized dubious on most platforms.
>    In particular, most 64bit platforms have a 32bit instruction size, so using more than 32 bits
>    for the marker value doesn't buy much. If the marker value is actually a legal instruction,
>    then checking for two in a row reduces the odds of a false positive.
>
>
>    However, given that the closure is a marker and two pointers, it isn't like you are going
>    to pack the second and third 64bit field right up against a 32bit field. You'd want padding for alignmet.
>

Right.  If the marker had smaller alignment than a pointer, say 32-bit marker, 64-bit pointers, then
it would be necessary to start the closure on an odd multiple of 32 bits--a rule that is not part
of anybody's alignment system of any compiler that I am aware of.  So then you'd have to finesse it
by giving the closure 64-bit alignment and starting with a pad word, which would fail to gain the
space benefits.  Moreover, fewer bits of marker increase the likelihood of its accidentally being a
valid instruction or sequence thereof.

So I think making the marker the same size as a pointer, and giving the whole closure pointer-sized
alignment is the best way, unless/until we find a machine instruction set that has a known ambiguity
here.

Also, it is not necessary that there be no valid instruction sequence that starts with 32 or 64 1-bits.
It is enough that no compiler produces it at the beginning of a prologue.  Much harder to ascertain for
certain (especially if we want to be able to call procedures produced by other compilers) but much less
likely to result in a problem.

Just a wild guess, but I would not be surprised if ELF and other object formats would require the
machine code of a function/procedure to begin on a native word boundary, even if the hardware
instruction set does not.  Where so, this would obviate checking the alignment before checking
for a closure, though probably target-dependently.

>
>    If we are aiming for all out target-specificity, I'd suggest marker size be a target aspect,
>    and set it to 4 bytes for ppc64/mips64/sparc64/alpha64/arm64/hppa64.
>
>
>    However, I want less target-variation not more.
>
>
>    Here are some my lingering questions:
>      - Is the marker value actually invalid code on every platform? Does its value need to be target-specific?
>      - Is a 64bit marker value actually sufficient on IA64?
>        The way to help here, I think, is to ensure that a 64bit marker,
>        not a 128bit marker, contains the "template", and an invalid "template".
>     - Barring the previous, a solution might be to use a 128 bit marker on all platforms.
>
>
>   i believe all of these function pointers are rare.
>   I hope/believe the object method calls do not check for closures -- though actually
>    that is related to a useful language construct, that I doubt we have.
>

Method body procedures are required to be top-level, ensured statically, so there is no
need for method call code to consider the possibility of the pointer in the object type
to be a closure.

>
>    The simplest solution is likely:
>      - ignore IA64, or research it further
>      - keep marker size at integer

Pointer would be target-independent in getting the following two pointers aligned.

>      - for the C backend, assume no alignment of function pointers -- give up
>        any of the optimization, esp. x86/amd64.

I think this optimization both applies to a low-frequency situation and has a very
small benefit, so I would not worry about giving up on it.

>
>
>   For other than the C backend, maybe dial back marker size to 4 bytes for mips64/sparc64/alpha64/arm64/hppa64.
>   While I don't like target-specificity, notice this wouldn't check linux vs. bsd vs. solaris, etc. It isn't a cross produce thing.
>
>
> Thoughts?
>
>
>   - Jay
>
>
>
> _______________________________________________
> M3devel mailing list
> M3devel at elegosoft.com
> https://mail.elegosoft.com/cgi-bin/mailman/listinfo/m3devel
>

-- 
Rodney Bates
rodney.m.bates at acm.org