Re: [MLton] Object allocation code path

--===============0532989359731137326==
Content-Type: multipart/alternative; boundary="000000000000e374c005d70d1016"

--000000000000e374c005d70d1016
Content-Type: text/plain; charset="UTF-8"

Hi Jeff,

On Fri, Jan 28, 2022 at 12:54 AM Jeffrey Murphy <[email protected]>
wrote:

> I'm currently working on reading through the compiler code and
> understanding how variables go from the AST layer through to the machine
> layer. I would like to experiment with how objects are packed. I've been
> looking at, eg, packed-representation, and trying to understand how a
> (normal) variable associated with a function is transformed into an
> object/offset. Are there detailed descriptions of how MLton transforms code
> at each layer, other than what is on mlton.org or in "An LLVM back-end
> for MLton" (Leibig)?
>

The only documentation is what is at mlton.org and the code itself.

It might help if you could describe a little more about what kinds of
transformations you are trying to make.  Object allocation and
representation is pretty much entirely implicit from the front-end all the
way to the RSSA IR.  Any constructor application (e.g., `h :: t`), record
or tuple expression, or function expression is an implicit object
allocation; there are also a few primitives that correspond to object
allocation (creation of arrays, references, and weak pointers).  But,
because representations are not dictated by the language semantics, MLton
is able to do a lot of transformations that may significantly alter what
you thought of as source allocation.  Components of tuples and constructors
might be eliminated (because they are unused or they have constant values),
tuples might be flattened into containing constructors/tuples/sequences,
tuples might be eliminated entirely (turning a function that takes and
returns a single tuple value to a function that takes and returns multiple
values), etc.


> I'd like to understand how MLton tracks and transforms SML and the
> associated functions so that I can influence how normals are allocated. For
> example, (this is contrived!), if I wanted to pack normals together that
> are allocated by functions that begin with the letter "t", how can I more
> easily learn which source files, or passes should I focus on with respect
> to how the code is parsed and transformed?   I think after the coreml->xml
> transform, function names are discarded. Additional variables may be
> introduced (for example I think LocalRef might convert refs in some
> circumstances) and so if the function name is discarded by the time SSA is
> reached...
>

All of the source code information is discarded during elaboration (type
checking).  So, any names in the CoreML are just identifiers that may an
initial "printName" associated with them from the source language, but that
carries no semantic information.  If you really needed to capture some
aspect of the source function at which an allocation happened, then you
would probably need to tag that during elaboration.  For example, here is
where we type check an AST Record expression and create a CoreML record
expression:

https://github.com/MLton/mlton/blob/master/mlton/elaborate/elaborate-core.fun#L3690-L3699
In scope is `nest : Nest.t (* = string list *)` and `maybeName : string
option` which, to some degree, capture the nesting of module and function
names leading to this point.  If you needed to track "where" an allocation
came from, this is where you would obtain it and you would then need to add
that to the `Cexp.Record` constructor and carry that information through
the subsequent IRs.  You would also need to decide what to do when
performing those transformations described above, as well as deciding what
to do when the compiler introduces an allocated object directly (without a
clear source location).  Profiling is the closest thing that we have to
tracking source location information through the compiler; see
http://mlton.org/HowProfilingWorks for some details on that.

In your contrived example, I'm not sure what you mean by "pack normals
together".  Do you mean allocate them differently from other objects (e.g.,
into a different heap)?  Or do you mean pack them together into one larger
object?

I'm also interested in how the call graph is organized and computed, eg,
> inline.fun, multi.fun. Is it just computed on-demand/as-needed? I can read
> the code (and I am!) but any additional explanations are welcome! E.g.
> another example would be if I wanted to look at packing objects based on
> how related they are in the call graph.
>

The call graph is implicit in the IR representations, so it is always
computed on demand.  During closure conversion, control-flow analysis is
used to eliminate first-class functions.  In the SSA and subsequent IRs,
the call graph is easily constructed by just looping over all functions,
drawing an edge from each function to those that it calls (directly, by
name).  Depending on the application, this might be an explicit directed
graph value (for doing things like strongly connected components analysis)
or might be more implicit.

-Matthew

--000000000000e374c005d70d1016
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div dir=3D"ltr"><div class=3D"gmail_default" style=3D"fon=
t-family:arial,sans-serif;font-size:large">Hi Jeff,</div><div dir=3D"ltr" c=
lass=3D"gmail_attr"><br></div><div dir=3D"ltr" class=3D"gmail_attr">On Fri,=
 Jan 28, 2022 at 12:54 AM Jeffrey Murphy &lt;<a href=3D"mailto:jcmurphy@buf=
falo.edu" target=3D"_blank">[email protected]</a>&gt; wrote:<br></div></=
div><div class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"m=
argin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left=
:1ex"><div dir=3D"ltr">I&#39;m currently working on reading through the com=
piler code and understanding how variables go from the AST layer through to=
 the machine layer. I would like to experiment with how objects are packed.=
 I&#39;ve been looking at, eg, packed-representation, and trying to underst=
and how a (normal) variable associated with a function is transformed into =
an object/offset. Are there detailed descriptions of how MLton transforms c=
ode at each layer, other than what is on <a href=3D"http://mlton.org" targe=
t=3D"_blank">mlton.org</a> or in &quot;An LLVM back-end for MLton&quot; (Le=
ibig)? <br></div></blockquote><div><br></div><div><div style=3D"font-family=
:arial,sans-serif;font-size:large" class=3D"gmail_default">The only documen=
tation is what is at <a href=3D"http://mlton.org" target=3D"_blank">mlton.o=
rg</a> and the code itself.</div><div style=3D"font-family:arial,sans-serif=
;font-size:large" class=3D"gmail_default"><br></div><div style=3D"font-fami=
ly:arial,sans-serif;font-size:large" class=3D"gmail_default">It might help =
if you could describe a little more about what kinds of transformations you=
 are trying to make.=C2=A0 Object allocation and representation is pretty m=
uch entirely implicit from the front-end all the way to the RSSA IR.=C2=A0 =
Any constructor application (e.g., `h :: t`), record or tuple expression, o=
r function expression is an implicit object allocation; there are also a fe=
w primitives that correspond to object allocation (creation of arrays, refe=
rences, and weak pointers).=C2=A0 But, because representations are not dict=
ated by the language semantics, MLton is able to do a lot of transformation=
s that may significantly alter what you thought of as source allocation.=C2=
=A0 Components of tuples and constructors might be eliminated (because they=
 are unused or they have constant values), tuples might be flattened into c=
ontaining constructors/tuples/sequences, tuples might be eliminated entirel=
y (turning a function that takes and returns a single tuple value to a func=
tion that takes and returns multiple values), etc.<br></div></div><div>=C2=
=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8e=
x;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"=
><div>I&#39;d like to understand how MLton=C2=A0tracks and transforms SML a=
nd the associated functions so that=C2=A0I can influence how normals are al=
located. For example, (this is contrived!), if I wanted to pack normals tog=
ether that are allocated by functions that begin with the letter &quot;t&qu=
ot;, how can I more easily learn which source files, or passes should I foc=
us on with respect to how the code is parsed and transformed?=C2=A0 =C2=A0I=
 think after the coreml-&gt;xml transform, function names are discarded. Ad=
ditional variables may be introduced (for example I think LocalRef might co=
nvert refs in some circumstances) and so if the function name is discarded =
by the time SSA is reached...</div></div></blockquote><div><br></div><div><=
div style=3D"font-family:arial,sans-serif;font-size:large" class=3D"gmail_d=
efault">All of the source code information is discarded during elaboration =
(type checking).=C2=A0 So, any names in the CoreML are just identifiers tha=
t may an initial &quot;printName&quot; associated with them from the source=
 language, but that carries no semantic information.=C2=A0 If you really ne=
eded to capture some aspect of the source function at which an allocation h=
appened, then you would probably need to tag that during elaboration.=C2=A0=
 For example, here is where we type check an AST Record expression and crea=
te a CoreML record expression:</div><div style=3D"font-family:arial,sans-se=
rif;font-size:large" class=3D"gmail_default">=C2=A0 <a href=3D"https://gith=
ub.com/MLton/mlton/blob/master/mlton/elaborate/elaborate-core.fun#L3690-L36=
99">https://github.com/MLton/mlton/blob/master/mlton/elaborate/elaborate-co=
re.fun#L3690-L3699</a></div><div style=3D"font-family:arial,sans-serif;font=
-size:large" class=3D"gmail_default">In scope is `nest : Nest.t (* =3D stri=
ng list *)` and `maybeName : string option` which, to some degree, capture =
the nesting of module and function names leading to this point.=C2=A0 If yo=
u needed to track &quot;where&quot; an allocation came from, this is where =
you would obtain it and you would then need to add that to the `Cexp.Record=
` constructor and carry that information through the subsequent IRs.=C2=A0 =
You would also need to decide what to do when performing those transformati=
ons described above, as well as deciding what to do when the compiler intro=
duces an allocated object directly (without a clear source location).=C2=A0=
 Profiling is the closest thing that we have to tracking source location in=
formation through the compiler; see <a href=3D"http://mlton.org/HowProfilin=
gWorks">http://mlton.org/HowProfilingWorks</a> for some details on that.</d=
iv><div style=3D"font-family:arial,sans-serif;font-size:large" class=3D"gma=
il_default"><br></div><div style=3D"font-family:arial,sans-serif;font-size:=
large" class=3D"gmail_default">In your contrived example, I&#39;m not sure =
what you mean by &quot;pack normals together&quot;.=C2=A0 Do you mean alloc=
ate them differently from other objects (e.g., into a different heap)?=C2=
=A0 Or do you mean pack them together into one larger object?<br></div><br>=
</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;b=
order-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><d=
iv>I&#39;m also interested in how the call graph is organized and computed,=
 eg, inline.fun, multi.fun. Is it just computed on-demand/as-needed? I can =
read the code (and I am!) but any additional explanations are welcome! E.g.=
 another example would be if I wanted to look at packing=C2=A0objects based=
 on how related they are in the call graph.=C2=A0</div></div></blockquote><=
div><br></div><div style=3D"font-family:arial,sans-serif;font-size:large" c=
lass=3D"gmail_default">The call=C2=A0graph is implicit in the IR representa=
tions, so it is always computed on demand.=C2=A0 During closure conversion,=
 control-flow analysis is used to eliminate first-class functions.=C2=A0 In=
 the SSA and subsequent IRs, the call graph is easily constructed by just l=
ooping over all functions, drawing an edge from each function to those that=
 it calls (directly, by name).=C2=A0 Depending on the application, this mig=
ht be an explicit directed graph value (for doing things like strongly conn=
ected components analysis) or might be more implicit.</div><div style=3D"fo=
nt-family:arial,sans-serif;font-size:large" class=3D"gmail_default"><br></d=
iv><div style=3D"font-family:arial,sans-serif;font-size:large" class=3D"gma=
il_default">-Matthew<br></div><div style=3D"font-family:arial,sans-serif;fo=
nt-size:large" class=3D"gmail_default"><br></div></div></div>

--000000000000e374c005d70d1016--


--===============0532989359731137326==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline


--===============0532989359731137326==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

_______________________________________________
MLton-devel mailing list
[email protected]; [email protected]
https://lists.sourceforge.net/lists/listinfo/mlton-devel

--===============0532989359731137326==--