<div dir="ltr"><div>I'm working on A1 in modLang, as Magnus suggests.<br><br></div>Here's an unrelated question: why are modSem globals behind an option? In the later languages, the option distinguishes between uninitialized and initialized globals, but global allocation doesn't occur in modLang.<br></div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Mar 18, 2017 at 4:32 AM, Magnus Myreen <span dir="ltr"><<a href="mailto:magnus.myreen@gmail.com" target="_blank">magnus.myreen@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi all,<br>
<br>
I read Yong Kiam's comments as saying that we should only have A1<br>
implemented and only for closLang, but run A1 twice. By running it<br>
before clos_call we prevent unused code table entries from turning up.<br>
By running it after clos_call but before clos_to_bvl, we replace a few<br>
now-unused globals with dummy values (and avoid producing other code<br>
table entries in clos_to_bvl). This all sounds good to me, since it<br>
means that we can avoid B1 completely. One could optionally implement<br>
A2 in BVL.<br>
<br>
I can imagine that doing A1 in modLang would probably be a bit simpler<br>
than the same in closLang, because closLang has Call and the multi-arg<br>
semantics.<br>
<br>
One option would be to just do A1 in modLang and then ignore the junk<br>
that a successful combination of clos_call and clos_to_bvl leaves in<br>
the globals and the code table. The junk only consists of small pieces<br>
of code that performs a tail call to another code table entry.<br>
<br>
I'm now of the opinion that the best course of action is to:<br>
 - implement A1 in modLang (where it should be easy-ish),<br>
 - and maybe later port A1 to closLang to run after clos_call,<br>
 - and maybe later implement A2 in BVL.<br>
<br>
I suspect having A1 in modLang should give most of the benefit. The<br>
other steps will just tidy things up a bit. I worry a bit about<br>
putting too much effort into these whole-program optimisations, since<br>
they won't be applicable to any program that uses the Eval primitive,<br>
once we have it.<br>
<br>
Cheers,<br>
Magnus<br>
<div class="HOEnZb"><div class="h5"><br>
<br>
On 18 March 2017 at 04:29, Ramana Kumar <<a href="mailto:Ramana.Kumar@cl.cam.ac.uk">Ramana.Kumar@cl.cam.ac.uk</a>> wrote:<br>
> This discussion seems of relevance or interest to the developers list<br>
> so I'm CC'ing them. My reply is inline below.<br>
><br>
> On 18 March 2017 at 10:13, Yong Kiam <<a href="mailto:tanyongkiam@gmail.com">tanyongkiam@gmail.com</a>> wrote:<br>
>> Hi Ramana,<br>
>><br>
>> Right, so we should distinguish between A) removing globals, which can<br>
>> happen in a number of places and B) removing call table entries, which<br>
>> should happen after we actually start getting call tables (after clos_call<br>
>> and clos_to_bvl)<br>
><br>
> I don't think those are the all the relevant distinctions. I'd say the<br>
> relevant distinctions are:<br>
> A1) Replacing unused globals with dummy values<br>
> A2) Deleting allocations of unused globals<br>
> B1) Deleting unused function bodies<br>
><br>
> I think A2 is easier to do after closures are gone, because of the<br>
> index shifting throughout the code.<br>
><br>
> I think doing A1 as early as possible has more benefits because it<br>
> means less code needs to be processed.<br>
><br>
> I think B1 can be accomplished by A1 if it's done early enough, ie.,<br>
> before the code table is populated. But otherwise it turns into B, and<br>
> I think B is much trickier because it's harder to tell which code<br>
> table entries are live.<br>
><br>
>><br>
>> In 2), isn't the pass that deletes calls to SetGlobal essentially going to<br>
>> do the same thing as what's happening in modLang (in modLang, the<br>
>> set_globals are "deleted" by replacing the declarations)?<br>
><br>
> No, 2) does more: it actually deletes the allocations, which requires<br>
> shifting the indices. For this reason, I think 2 should happen in BVL<br>
> or later, so that there are no closures complicating the value<br>
> relation.<br>
><br>
>><br>
>> Having an additional pass after clos_call would potentially be able to catch<br>
>> more unreferenced globals though -- to be clear, these globals become<br>
>> unreferenced because instead of using an Opapp (global ... ) , we instead<br>
>> make a direct Call to a code table entry right?<br>
><br>
> Yes that's how globals become dead via clos_call.<br>
><br>
>><br>
>> Possibly writing/verifying one pass and running it twice, as Magnus<br>
>> suggests, could be useful:<br>
>><br>
>> - The first pass before clos_call should hopefully delete the same things<br>
>> that should be delete-able in modLang. This would prevent the call tables<br>
>> from being generated.<br>
>> - The second pass, after clos_call should delete the extra globals that are<br>
>> now unreferenced.<br>
><br>
> I still think it's better to do the first pass in modLang and the second in BVL.<br>
><br>
>><br>
>><br>
>> On Fri, Mar 17, 2017 at 6:59 PM, Ramana Kumar <<a href="mailto:Ramana.Kumar@cl.cam.ac.uk">Ramana.Kumar@cl.cam.ac.uk</a>><br>
>> wrote:<br>
>>><br>
>>> > I just want to add to the discussion that clos_call can make a lot of<br>
>>> > globals unused.<br>
>>><br>
>>> I think we're operating under some misunderstandings currently,<br>
>>> because I think the fact that clos_call can make globals unused seems<br>
>>> not very relevant, to me, to what Yong Kiam is doing in modLang.<br>
>>><br>
>>> Here's my understanding of the plan Yong Kiam and I came up with:<br>
>>> 1. Replace declarations of the form "val x = e" or "fun x y = b",<br>
>>> where e is pure and x is never used subsequently, with "val x = ()".<br>
>>> This should happen as early as possible. The purpose is to avoid code<br>
>>> for e or b ever entering the code table (and a side advantage is it<br>
>>> never gets processed by the rest of the compiler). The reason to<br>
>>> replace, rather than delete, the declarations is to avoid reasoning<br>
>>> about shifting global variables.<br>
>>> 2. (This is optional, most of the benefit comes from 1) Delete calls<br>
>>> to SetGlobal for globals that are never referenced, and then also<br>
>>> delete the corresponding calls to AllocGlobal (which requires<br>
>>> shifting). This should happen somewhere near BVL, like just before the<br>
>>> globals are implemented in an array.<br>
>>><br>
>>> The fact that clos_call can make more globals never referenced is only<br>
>>> relevant to 2, and 2 should happen after clos_call. As far as I<br>
>>> understand it, none of the closLang passes make _code table entries_<br>
>>> dead. So the way to avoid a too big code table is to stop things<br>
>>> getting in there in the first place.<br>
>>><br>
>>> So, what have I got wrong? Does what I say make sense? I'm not going<br>
>>> to be too surprised if I've missed something important...<br>
>>><br>
>>> On 18 March 2017 at 08:39, Yong Kiam <<a href="mailto:tanyongkiam@gmail.com">tanyongkiam@gmail.com</a>> wrote:<br>
>>> > I think by the time it's in closLang, a lot of the top-level functions<br>
>>> > get<br>
>>> > hidden behind Matches and Lets (actually, this happens in modLang too).<br>
>>> ><br>
>>> > I'll have a closer look at what the program looks like at the entry to<br>
>>> > closLang.<br>
>>> ><br>
>>> > On Fri, Mar 17, 2017 at 4:28 PM, Magnus Myreen <<a href="mailto:magnus.myreen@gmail.com">magnus.myreen@gmail.com</a>><br>
>>> > wrote:<br>
>>> >><br>
>>> >> On 17 March 2017 at 19:14, Yong Kiam <<a href="mailto:tanyongkiam@gmail.com">tanyongkiam@gmail.com</a>> wrote:<br>
>>> >> > I wasn't at the Hangout either. Hmm, where should I do the analysis<br>
>>> >> > then?<br>
>>> >><br>
>>> >> Both clos_call and clos_to_bvl produce code table entries.<br>
>>> >><br>
>>> >> > Ramana suggested to put it as early as possible to avoid extra work<br>
>>> >> > in<br>
>>> >> > the<br>
>>> >> > compiler.<br>
>>> >><br>
>>> >> My impression is that most things run pretty quickly up to closLang.<br>
>>> >><br>
>>> >> > The issue with putting it later on is that it becomes less obvious<br>
>>> >> > whether<br>
>>> >> > an expression is pure without doing more complicated analysis, but<br>
>>> >> > the<br>
>>> >> > advantage is that many globals can be deleted.<br>
>>> >><br>
>>> >> Why is purity so important? In closLang, various functions expressions<br>
>>> >> are tied to globals. A Fun-expression is always pure. Most of the<br>
>>> >> expressions you want to delete are Fun-expressions.<br>
>>> >><br>
>>> >> > It seems like we do want to put it before clos_to_bvl to avoid<br>
>>> >> > generating<br>
>>> >> > call table entries for un-used function, and then we want another one<br>
>>> >> > after<br>
>>> >> > inlining, possibly combined with code table elimination so that<br>
>>> >> > un-used<br>
>>> >> > globals (such as the initial definition of + can be deleted).<br>
>>> >><br>
>>> >> Could you have one implementation that could run in closLang before<br>
>>> >> clos_call and after clos_call?<br>
>>> >><br>
>>> >> Cheers,<br>
>>> >> Magnus<br>
>>> >><br>
>>> >> > On Fri, Mar 17, 2017 at 2:21 AM, Magnus Myreen<br>
>>> >> > <<a href="mailto:magnus.myreen@gmail.com">magnus.myreen@gmail.com</a>><br>
>>> >> > wrote:<br>
>>> >> >><br>
>>> >> >> I can't be in the hangout today, nor read the wiki effectively from<br>
>>> >> >> my<br>
>>> >> >> phone.<br>
>>> >> >><br>
>>> >> >> I just want to add to the discussion that clos_call can make a lot<br>
>>> >> >> of<br>
>>> >> >> globals unused. It would be nice if the phase which removes unused<br>
>>> >> >> globals<br>
>>> >> >> came after clos_call. Sorry for not saying this earlier. I hadn't<br>
>>> >> >> thought of<br>
>>> >> >> it earlier.<br>
>>> >> >><br>
>>> >> >> Cheers,<br>
>>> >> >> Magnus<br>
>>> >> ><br>
>>> >> ><br>
>>> ><br>
>>> ><br>
>><br>
>><br>
</div></div></blockquote></div><br></div>