Re: [MLton] Object allocation code path
Jeffrey Murphy <[email protected]> Thu, 3 Feb 2022 18:30:40 -0500
| Newsgroups | gmane.comp.lang.ml.mlton.devel |
|---|---|
| Message-ID | <CAJ36g22Qy=CtRbO-JYmqvAjpkz3sAL8XDkBoqsOm1S3bdWmkkg@mail.gmail.com> |
--===============2592549231325017941== Content-Type: multipart/alternative; boundary="0000000000005a756805d72586d4" --0000000000005a756805d72586d4 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Wed, Feb 2, 2022 at 1:20 PM Matthew Fluet <[email protected]> wrote: > 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 c= ode >> at each layer, other than what is on mlton.org >> <https://nam12.safelinks.protection.outlook.com/?url=3Dhttp%3A%2F%2Fmlto= n.org%2F&data=3D04%7C01%7Cjcmurphy%40g-mail.buffalo.edu%7C07adfd21d84b40f80= 9ec08d9e678abb5%7C96464a8af8ed40b199e25f6b50a20250%7C0%7C0%7C63779422821843= 4226%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik= 1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=3DkC4NQgMKUHmj9Johv9iKfivGeq9QuBMuKEW7nMX= wwos%3D&reserved=3D0> >> or in "An LLVM back-end for MLton" (Leibig)? >> > > The only documentation is what is at mlton.org > <https://nam12.safelinks.protection.outlook.com/?url=3Dhttp%3A%2F%2Fmlton= .org%2F&data=3D04%7C01%7Cjcmurphy%40g-mail.buffalo.edu%7C07adfd21d84b40f809= ec08d9e678abb5%7C96464a8af8ed40b199e25f6b50a20250%7C0%7C0%7C637794228218434= 226%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1= haWwiLCJXVCI6Mn0%3D%7C3000&sdata=3DkC4NQgMKUHmj9Johv9iKfivGeq9QuBMuKEW7nMXw= wos%3D&reserved=3D0> > 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 th= e > 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 constructo= rs > 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 multipl= e > 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 mor= e >> easily learn which source files, or passes should I focus on with respec= t >> to how the code is parsed and transformed? I think after the coreml->x= ml >> 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 th= at > 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 > <https://nam12.safelinks.protection.outlook.com/?url=3Dhttps%3A%2F%2Fgith= ub.com%2FMLton%2Fmlton%2Fblob%2Fmaster%2Fmlton%2Felaborate%2Felaborate-core= .fun%23L3690-L3699&data=3D04%7C01%7Cjcmurphy%40g-mail.buffalo.edu%7C07adfd2= 1d84b40f809ec08d9e678abb5%7C96464a8af8ed40b199e25f6b50a20250%7C0%7C0%7C6377= 94228218434226%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIi= LCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=3D5UofmpD%2FS1ENWQdDcY8rm6q6BMI= RMMmHan1YK7amWQU%3D&reserved=3D0> > In scope is `nest : Nest.t (* =3D 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 allocatio= n > came from, this is where you would obtain it and you would then need to a= dd > 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 wha= t > 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 > <https://nam12.safelinks.protection.outlook.com/?url=3Dhttp%3A%2F%2Fmlton= .org%2FHowProfilingWorks&data=3D04%7C01%7Cjcmurphy%40g-mail.buffalo.edu%7C0= 7adfd21d84b40f809ec08d9e678abb5%7C96464a8af8ed40b199e25f6b50a20250%7C0%7C0%= 7C637794228218434226%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2= luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=3DYBsl7Ll%2FkfI20fq7FGv5u= tbIZobB5pQfGDV7Z1Npsas%3D&reserved=3D0> > 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 large= r > object? > By "normals" I mean not arrays or stacks. I think to make things simpler, I would like to exclude refs also. To provide more context, we have a GC that is similar to a region based GC. Each MLton Object[1] is encapsulated in a region. While we can merge multiple Objects into a region, on a block by block basis, I am interested in a less obvious packing approach that involves merging Objects across unrelated functions. In particular, I want the compiler to decide how to do this. I think doing the packing as late as possible, in RSSA, lets me ignore what the Object contains, and only have to deal with the size. However, and maybe I'm thinking about this the wrong way, I feel like I need to know which two (or more) unrelated SML functions' Objects should be packed into the same region, and that bit of information is not available in RSSA (easily at least). One thought is to just manually determine its "x_100 and x_200" for now and leave the function name propagation (as you propose below) for later. I haven't thought too much about that because the actual merging of Objects is what I'm trying to do first. At the moment, I have the packing algorithm implemented as an external tool and I would like to do the following (I'm speculating a lot here). Assume we have function A which calls B. We also have C and D which are unrelated to each other or to A/B. Assume optimization passes do not eliminate any of these. 1. save, as part of "-keep", the call tree and allocations. something like "A vars x_1599 size 8, x_1601 size 12, ..." "A calls B" "B vars x_7777 size 8, x_8888, size 12, ..." "C vars x_299 size 8, ..." "D vars x_333 size 8, ..." 2. Produce 'packing' instructions (in the absence of which the compiler will leave things as is -- in other words each object is encapsulated in a region by itself). Assuming the tool is told "pack functions A, B, C" the 'packing' instructions might look like "region_0: x_1599, x_1601, x_7777, x_8888, x_299" "region_1: x_333" and when I rerun the compilation, but with, say "-packing instructions.txt", the compiler will take x_1599, wrap it in a region at offset 0, then place X_1601 in the same but at offset 20, and so on. I would include each Object header (and so the offsets into the region would need to account for that) as well so the machine output would (hopefully) not need any substantial changes (I would need to adjust the Move operand so it is aware of the region offset, I'm not sure what else may be impacted?) My plan for "who allocates the region since you might not know if A runs before C or vice versa" would be to (in this initial implementation) to keep a runtime array of regions and if, at the start of a block, an allocation were to occur, it would first see if there is a memory address in the region slot the allocation was assigned to and then use that, otherwise create a region and record it. Advice on whether I'm approaching this reasonably (by focusing on RSSA) is welcome! [1] https://github.com/MLton/mlton/blob/master/mlton/backend/backend.fun#L651 jeff > > 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 re= ad >> 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 > > --0000000000005a756805d72586d4 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr"><div dir=3D"ltr"><br></div><br><div class=3D"gmail_quote">= <div dir=3D"ltr" class=3D"gmail_attr">On Wed, Feb 2, 2022 at 1:20 PM Matthe= w Fluet <<a href=3D"mailto:[email protected]">matthew.fluet@gmail.= com</a>> wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"marg= in:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1e= x"><div dir=3D"ltr"><div dir=3D"ltr"><div style=3D"font-family:arial,sans-s= erif;font-size:large">Hi Jeff,</div><div dir=3D"ltr" class=3D"gmail_attr"><= br></div><div dir=3D"ltr" class=3D"gmail_attr">On Fri, Jan 28, 2022 at 12:5= 4 AM Jeffrey Murphy <<a href=3D"mailto:[email protected]" target=3D"_= blank">[email protected]</a>> wrote:<br></div></div><div class=3D"gma= il_quote"><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8= ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr= ">I'm currently working on reading through the compiler code and unders= tanding 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 lookin= g at, eg, packed-representation, and trying to understand how a (normal) va= riable associated with a function is transformed into an object/offset. Are= there detailed descriptions of how MLton transforms code at each layer, ot= her than what is on <a href=3D"https://nam12.safelinks.protection.outlook.c= om/?url=3Dhttp%3A%2F%2Fmlton.org%2F&data=3D04%7C01%7Cjcmurphy%40g-mail.= buffalo.edu%7C07adfd21d84b40f809ec08d9e678abb5%7C96464a8af8ed40b199e25f6b50= a20250%7C0%7C0%7C637794228218434226%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjA= wMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=3DkC4N= QgMKUHmj9Johv9iKfivGeq9QuBMuKEW7nMXwwos%3D&reserved=3D0" target=3D"_bla= nk">mlton.org</a> or in "An LLVM back-end for MLton" (Leibig)? <b= r></div></blockquote><div><br></div><div><div style=3D"font-family:arial,sa= ns-serif;font-size:large">The only documentation is what is at <a href=3D"h= ttps://nam12.safelinks.protection.outlook.com/?url=3Dhttp%3A%2F%2Fmlton.org= %2F&data=3D04%7C01%7Cjcmurphy%40g-mail.buffalo.edu%7C07adfd21d84b40f809= ec08d9e678abb5%7C96464a8af8ed40b199e25f6b50a20250%7C0%7C0%7C637794228218434= 226%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1= haWwiLCJXVCI6Mn0%3D%7C3000&sdata=3DkC4NQgMKUHmj9Johv9iKfivGeq9QuBMuKEW7= nMXwwos%3D&reserved=3D0" target=3D"_blank">mlton.org</a> and the code i= tself.</div><div style=3D"font-family:arial,sans-serif;font-size:large"><br= ></div><div style=3D"font-family:arial,sans-serif;font-size:large">It might= help if you could describe a little more about what kinds of transformatio= ns you are trying to make.=C2=A0 Object allocation and representation is pr= etty much 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 expres= sion, or function expression is an implicit object allocation; there are al= so a few primitives that correspond to object allocation (creation of array= s, references, and weak pointers).=C2=A0 But, because representations are n= ot dictated by the language semantics, MLton is able to do a lot of transfo= rmations that may significantly alter what you thought of as source allocat= ion.=C2=A0 Components of tuples and constructors might be eliminated (becau= se 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.<br></div></div><d= iv>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0p= x 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir= =3D"ltr"><div>I'd like to understand how MLton=C2=A0tracks and transfor= ms SML and the associated functions so that=C2=A0I can influence how normal= s are allocated. For example, (this is contrived!), if I wanted to pack nor= mals together that are allocated by functions that begin with the letter &q= uot;t", how can I more easily learn which source files, or passes shou= ld I focus on with respect to how the code is parsed and transformed?=C2=A0= =C2=A0I think after the coreml->xml transform, function names are disca= rded. Additional variables may be introduced (for example I think LocalRef = might convert refs in some circumstances) and so if the function name is di= scarded by the time SSA is reached...</div></div></blockquote><div><br></di= v><div><div style=3D"font-family:arial,sans-serif;font-size:large">All of t= he source code information is discarded during elaboration (type checking).= =C2=A0 So, any names in the CoreML are just identifiers that may an initial= "printName" associated with them from the source language, but t= hat carries no semantic information.=C2=A0 If you really needed to capture = some aspect of the source function at which an allocation happened, then yo= u would probably need to tag that during elaboration.=C2=A0 For example, he= re is where we type check an AST Record expression and create a CoreML reco= rd expression:</div><div style=3D"font-family:arial,sans-serif;font-size:la= rge">=C2=A0 <a href=3D"https://nam12.safelinks.protection.outlook.com/?url= =3Dhttps%3A%2F%2Fgithub.com%2FMLton%2Fmlton%2Fblob%2Fmaster%2Fmlton%2Felabo= rate%2Felaborate-core.fun%23L3690-L3699&data=3D04%7C01%7Cjcmurphy%40g-m= ail.buffalo.edu%7C07adfd21d84b40f809ec08d9e678abb5%7C96464a8af8ed40b199e25f= 6b50a20250%7C0%7C0%7C637794228218434226%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4= wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=3D= 5UofmpD%2FS1ENWQdDcY8rm6q6BMIRMMmHan1YK7amWQU%3D&reserved=3D0" target= =3D"_blank">https://github.com/MLton/mlton/blob/master/mlton/elaborate/elab= orate-core.fun#L3690-L3699</a></div><div style=3D"font-family:arial,sans-se= rif;font-size:large">In scope is `nest : Nest.t (* =3D string list *)` and = `maybeName : string option` which, to some degree, capture the nesting of m= odule and function names leading to this point.=C2=A0 If you needed to trac= k "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 an= d carry that information through the subsequent IRs.=C2=A0 You would also n= eed to decide what to do when performing those transformations described ab= ove, as well as deciding what to do when the compiler introduces an allocat= ed object directly (without a clear source location).=C2=A0 Profiling is th= e closest thing that we have to tracking source location information throug= h the compiler; see <a href=3D"https://nam12.safelinks.protection.outlook.c= om/?url=3Dhttp%3A%2F%2Fmlton.org%2FHowProfilingWorks&data=3D04%7C01%7Cj= cmurphy%40g-mail.buffalo.edu%7C07adfd21d84b40f809ec08d9e678abb5%7C96464a8af= 8ed40b199e25f6b50a20250%7C0%7C0%7C637794228218434226%7CUnknown%7CTWFpbGZsb3= d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000= &sdata=3DYBsl7Ll%2FkfI20fq7FGv5utbIZobB5pQfGDV7Z1Npsas%3D&reserved= =3D0" target=3D"_blank">http://mlton.org/HowProfilingWorks</a> for some det= ails on that.</div><div style=3D"font-family:arial,sans-serif;font-size:lar= ge"><br></div><div style=3D"font-family:arial,sans-serif;font-size:large">I= n your contrived example, I'm not sure what you mean by "pack norm= als together".=C2=A0 Do you mean allocate them differently from other = objects (e.g., into a different heap)?=C2=A0 Or do you mean pack them toget= her into one larger object?<br></div></div></div></div></blockquote><div><b= r></div><div>By "normals" I mean not arrays=C2=A0or stacks. I thi= nk to make things simpler, I would like to exclude refs also.=C2=A0</div><d= iv><br></div><div>To provide more context, we have a GC that is similar to = a region based GC. Each MLton Object[1] is encapsulated in a region. While = we can merge multiple Objects into a region, on a block by block basis,=C2= =A0I am interested in a less obvious packing approach that involves merging= Objects across unrelated functions. In particular, I want the compiler to = decide how to do this. I think doing the packing as late as possible, in RS= SA, lets me ignore what the Object contains, and only have to deal with the= size. However, and maybe I'm thinking about this the wrong way, I feel= like I need to know which two (or more) unrelated SML functions' Objec= ts should be packed into the same region, and that bit of information is no= t available in RSSA (easily at least). One thought is to just manually dete= rmine its "x_100 and x_200" for now and leave the function name p= ropagation (as you propose below) for later. I haven't thought too much= about that because the actual merging of Objects is what I'm trying to= do first.=C2=A0</div><div><br></div><div>At the moment, I have the packing= algorithm implemented as an external tool and I would like to do the follo= wing (I'm speculating a lot here). Assume we have function A which call= s B. We also have C and D which are unrelated to each other or to A/B. Assu= me optimization passes do not eliminate any of these.=C2=A0</div><div><br><= /div><div>1. save, as part of "-keep", the call tree and allocati= ons. something like=C2=A0</div><div><br></div><div>"A vars x_1599 size= 8, x_1601 size 12, ..."</div><div>"A calls B"</div><div>&qu= ot;B vars x_7777 size 8, x_8888, size 12, ..."</div><div><div>"C = vars x_299 size 8, ..."</div>"D vars x_333 size 8, ..."<br c= lass=3D"gmail-Apple-interchange-newline"></div><div><br></div><div>2. Produ= ce 'packing' instructions (in the absence of which the compiler wil= l leave things as is -- in other words each object is encapsulated=C2=A0in = a region by itself). Assuming the tool is told "pack functions A, B, C= " the 'packing' instructions might look like</div><div><br></d= iv><div>"region_0: x_1599, x_1601, x_7777, x_8888, x_299"</div><d= iv>"region_1: x_333"</div><div><br></div><div>and when I rerun th= e compilation, but with, say "-packing instructions.txt", the com= piler will take x_1599, wrap it in a region at offset 0, then place X_1601 = in the same but at offset 20, and so on. I would include each Object header= (and so the offsets into the region would need to account for that) as wel= l so the machine output would (hopefully) not need any substantial changes = (I=C2=A0would need to adjust the Move operand so it is aware of the region = offset, I'm not sure what else may be impacted?) My plan for "who = allocates the region since you might not know if A runs before C or vice ve= rsa" would be to (in this initial implementation) to keep a runtime ar= ray of regions and if, at the start of a block, an allocation were to occur= , it would first see if there is a memory address in the region slot the al= location was assigned to and then use that, otherwise create a region and r= ecord it.=C2=A0</div><div><br></div><div>Advice on whether I'm approach= ing this reasonably (by focusing on RSSA) is welcome!</div><div><br></div><= div><br></div><div>[1]=C2=A0<a href=3D"https://github.com/MLton/mlton/blob/= master/mlton/backend/backend.fun#L651">https://github.com/MLton/mlton/blob/= master/mlton/backend/backend.fun#L651</a></div><div><br></div><div><br></di= v><div>jeff</div><div><br></div><div><br></div><div>=C2=A0</div><blockquote= class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px so= lid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><div class=3D"gmail= _quote"><div><div style=3D"font-family:arial,sans-serif;font-size:large"></= div><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px= 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D= "ltr"><div>I'm also interested in how the call graph is organized and c= omputed, 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 welco= me! E.g. another example would be if I wanted to look at packing=C2=A0objec= ts based on how related they are in the call graph.=C2=A0</div></div></bloc= kquote><div><br></div><div style=3D"font-family:arial,sans-serif;font-size:= large">The call=C2=A0graph is implicit in the IR representations, so it is = always computed on demand.=C2=A0 During closure conversion, control-flow an= alysis is used to eliminate first-class functions.=C2=A0 In the SSA and sub= sequent IRs, the call graph is easily constructed by just looping over all = functions, drawing an edge from each function to those that it calls (direc= tly, by name).=C2=A0 Depending on the application, this might be an explici= t directed graph value (for doing things like strongly connected components= analysis) or might be more implicit.</div><div style=3D"font-family:arial,= sans-serif;font-size:large"><br></div><div style=3D"font-family:arial,sans-= serif;font-size:large">-Matthew<br></div><div style=3D"font-family:arial,sa= ns-serif;font-size:large"><br></div></div></div> </blockquote></div></div> --0000000000005a756805d72586d4-- --===============2592549231325017941== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline --===============2592549231325017941== 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 --===============2592549231325017941==--