[MLton] IntInf alignment

[Matthew Fluet]

I'm seeing an assertion failure when using IntInf operations.

fenrir:~/devel/mlton/mlton.svn.trunk/regression fluet$ ./conv2
gc/new-object.c:90: assert((size_t)(p - s->frontier) <= bytes) failed.
Abort trap

This is asserting that we didn't request enough bytes to accommodate 
rolling the frontier forward to an aligned address.  In this case, the 
problematic function is IntInf_toString, which is requesting bytes equal 
to

   arrayHeaderSize
   + 1 (* for the sign character *)
   + (digitsPerLimb (* computed from base *)
      * numLimbs)

In general, this number of bytes may not be aligned (either mod 4 or mod 
8).  Hence, we fail the assertion, and we could potentially be rolling 
the frontier beyond the limit, which is o.k., so long as we don't roll 
beyond limitPlusSlop.  I don't believe that rolling beyond limitPlusSlop 
can happen: we would have needed to request some number of bytes such 
that before the allocation:
   bytes <= limitPlusSlop - frontier
and
   align(frontier + bytes) > limitPlusSlop
but limitPlusSlop - frontier will always be 0 mod alignment, so 
align(frontier + bytes) can't roll beyond limitPlusSlop.

Nonetheless, we should really be really be requesting sufficient bytes 
to accommodate post alignment of the frontier, and leave the assertion 
as is.

Digging around some, I discovered a few other anomalies:

In limit-check.fun, the function bigAllocation (line 430) handles the 
limit check for a C call with a large constant or a non-constant number 
of bytesNeeded.  In both cases, the heap check is made with a number of 
bytes equal to the bytesNeeded of the C call plus the bytes in an array 
header plus the number of bytes required by the block.

First, I don't understand why the number of bytes in an array header is 
added for the heap check.  The size of the header has always been 
included in the bytesNeeded argument of the IntInf primitives.  So, we 
are performing a limit check with more bytes than necessary and all of 
the assertion checks in the runtime are being performed with the 
bytesNeeded argument of the primitives.  So, I believe that the 
arrayHeaderSize can be dropped from bigAllocation heap check.

Second, I don't see why the the RSSA program that results from inserting 
limit checks is necessarily well-formed.  In particular, an inserted 
limit check always precedes (in the CFG) all of the statements and the 
transfer in a block.  But, a C call with bytesNeeded might compute the 
bytesNeeded using the statements in the block for which it is a 
transfer; so, the variables referenced by the limit check might be 
inserted before they are assigned, violating the (R)SSA condition. 
Clearly, this hasn't been a problem in practice, since the RSSA type 
checker would reject such a program.  However, I don't see why this 
isn't a possibility.

In any case, for the immediate problem, I propose the following:

1) Require any primitive or C call with bytesNeeded to include 
sufficient bytes for any necessary headers and alignment restrictions.
[The only primitives or C calls with bytesNeeded are the IntInf 
operations, which already satisfy the former, but not the later.]

2) Remove the extraneous arrayHeaderSize from bigAllocation.

3) Include a _build_const: "MLton_Align_align", with the obvious meaning.

4) Modify the IntInf implementation to include sufficient bytes for the 
necessary alignment.

We have a couple of options with 4.  Since the bytesNeeded are just a 
request (the actual IntInf object size and frontier alignment are 
handled by the runtime), we can always request a little more than 
necessary, saving some instructions in the computation of the 
bytesNeeded.  For example, we always request a byte for the sign 
character in IntInf_toString (and constant-fold that needed byte with 
the bytes needed for the string header), rather than checking the sign 
of argument at runtime.  We could do the same thing with regards to the 
alignment; namely, always request an additional 3 bytes (for alignment 
mod 4) or 7 bytes (for alignment mod 8).  Furthermore, we can 
constant-fold these with the other constant bytes needed.

Aligning the bytesNeeded according to the alignment isn't prohibitively 
expensive, but I don't see a big advantage to doing so.