[M3devel] Target.Aligned_procedures and closure markers?

Jay K jay.krell at cornell.edu
Tue Sep 1 01:44:23 CEST 2015


Agreed -- I forgot to acknowledge/repeat that this is relatedto the first instruction in a function, not arbitrary instructions.

On the matter of 4 or 8 bytes though -- the thing is -- many but not all64bit architectures are the exact same instruction set as 32 bits,just a different selection of instructions.

Same size, same encodings, same alignment.

I believe this is true for alpha, mipa, ppc, sparc, hppa.
It is almost true for x86, though that kinda doesn't count,since there is no fixed size or alignment requirement.

Fyi: x86/amd64 instructions are between 1 and 15 bytes in size,inclusive, and all sizes in between. All the "lower" sizesincluding 1 are common. Upper sizes are rare, maybe starting around 7 bytes.The encoding scheme allows for longer instructions, butthere is a deliberate documented limit.

Not sure about arm -- arm64 at least gets rid of thumb.So arm instructions either 4-aligned or at odd addresses,and arm64 is like all the rest -- fixed size 4 byte aligned.

So 4 byte -1 e.g. on ppc32 has the same meaning as 8 byte -1 on ppc64,just that it is two in a row.

It looks like we have agreement -- we can set this to a constant.

The marker value is -1 I checked.

I still find the function If_closure a little unclear/subtle.I read through my comments in Target.m3 again.

It is false if:  - the system ever has alignment faults  - AND functions/instructions might be less aligned than closures  

Some of the commented I added in the code are incorrect.

The comments say that a misaligned function pointer is readone byte at a time. I believe the actual behavior is thata misaligned function pointer is deemed not a closure,and reading the marker is skipped.

The code is all still there, but branched around.When aligned_procedures == true, less code is generated,no alignment check is generated. 

Most 32bit platforms set Aligned_procedures = trueand most 64bit platforms set it to false.

 The exceptions:   amd64 is also true.    arm32 is false, due to Thumb mode. 

Because most platforms, 32bit and 64bit, have fixed size4 byte aligned instructions. So 32bit platforms haveinstructions (and functions) thereforealigned the same as closures. 64bit platforms generallyhave closures more aligned than instructions.

I think if we ignored arm32, and penalized only amd64,which granted is the most common platform,we could set aligned_procedures = false for all 64bit,true for all 32bit. And having another variablethat coincided with word size is ok.

But arm32's thumb instructions mean a function pointermight be unaligned.

I'll make it always false.

 > Method body procedures are required to be top-level 
 Kind of a language limitation compared to "more dynamic" languages. Definitely not trivial to do otherwise -- heap allocated garbage collected stack frames and such..

Thank you, - Jay




> Date: Sun, 30 Aug 2015 13:24:55 -0500
> From: rodney_bates at lcwb.coop
> To: m3devel at elegosoft.com
> Subject: Re: [M3devel] Target.Aligned_procedures and closure markers?
> 
> 
> 
> 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
> _______________________________________________
> M3devel mailing list
> M3devel at elegosoft.com
> https://mail.elegosoft.com/cgi-bin/mailman/listinfo/m3devel
 		 	   		  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20150831/e402863f/attachment-0001.html>


More information about the M3devel mailing list