[CakeML-dev] Globals and clos_call

[Ramana Kumar]

This discussion seems of relevance or interest to the developers list
so I'm CC'ing them. My reply is inline below.

On 18 March 2017 at 10:13, Yong Kiam <tanyongkiam at gmail.com> wrote:
> Hi Ramana,
>
> Right, so we should distinguish between A) removing globals, which can
> happen in a number of places and B) removing call table entries, which
> should happen after we actually start getting call tables (after clos_call
> and clos_to_bvl)

I don't think those are the all the relevant distinctions. I'd say the
relevant distinctions are:
A1) Replacing unused globals with dummy values
A2) Deleting allocations of unused globals
B1) Deleting unused function bodies

I think A2 is easier to do after closures are gone, because of the
index shifting throughout the code.

I think doing A1 as early as possible has more benefits because it
means less code needs to be processed.

I think B1 can be accomplished by A1 if it's done early enough, ie.,
before the code table is populated. But otherwise it turns into B, and
I think B is much trickier because it's harder to tell which code
table entries are live.

>
> In 2), isn't the pass that deletes calls to SetGlobal essentially going to
> do the same thing as what's happening in modLang (in modLang, the
> set_globals are "deleted" by replacing the declarations)?

No, 2) does more: it actually deletes the allocations, which requires
shifting the indices. For this reason, I think 2 should happen in BVL
or later, so that there are no closures complicating the value
relation.

>
> Having an additional pass after clos_call would potentially be able to catch
> more unreferenced globals though -- to be clear, these globals become
> unreferenced because instead of using an Opapp (global ... ) , we instead
> make a direct Call to a code table entry right?

Yes that's how globals become dead via clos_call.

>
> Possibly writing/verifying one pass and running it twice, as Magnus
> suggests, could be useful:
>
> - The first pass before clos_call should hopefully delete the same things
> that should be delete-able in modLang. This would prevent the call tables
> from being generated.
> - The second pass, after clos_call should delete the extra globals that are
> now unreferenced.

I still think it's better to do the first pass in modLang and the second in BVL.

>
>
> On Fri, Mar 17, 2017 at 6:59 PM, Ramana Kumar <Ramana.Kumar at cl.cam.ac.uk>
> wrote:
>>
>> > I just want to add to the discussion that clos_call can make a lot of
>> > globals unused.
>>
>> I think we're operating under some misunderstandings currently,
>> because I think the fact that clos_call can make globals unused seems
>> not very relevant, to me, to what Yong Kiam is doing in modLang.
>>
>> Here's my understanding of the plan Yong Kiam and I came up with:
>> 1. Replace declarations of the form "val x = e" or "fun x y = b",
>> where e is pure and x is never used subsequently, with "val x = ()".
>> This should happen as early as possible. The purpose is to avoid code
>> for e or b ever entering the code table (and a side advantage is it
>> never gets processed by the rest of the compiler). The reason to
>> replace, rather than delete, the declarations is to avoid reasoning
>> about shifting global variables.
>> 2. (This is optional, most of the benefit comes from 1) Delete calls
>> to SetGlobal for globals that are never referenced, and then also
>> delete the corresponding calls to AllocGlobal (which requires
>> shifting). This should happen somewhere near BVL, like just before the
>> globals are implemented in an array.
>>
>> The fact that clos_call can make more globals never referenced is only
>> relevant to 2, and 2 should happen after clos_call. As far as I
>> understand it, none of the closLang passes make _code table entries_
>> dead. So the way to avoid a too big code table is to stop things
>> getting in there in the first place.
>>
>> So, what have I got wrong? Does what I say make sense? I'm not going
>> to be too surprised if I've missed something important...
>>
>> On 18 March 2017 at 08:39, Yong Kiam <tanyongkiam at gmail.com> wrote:
>> > I think by the time it's in closLang, a lot of the top-level functions
>> > get
>> > hidden behind Matches and Lets (actually, this happens in modLang too).
>> >
>> > I'll have a closer look at what the program looks like at the entry to
>> > closLang.
>> >
>> > On Fri, Mar 17, 2017 at 4:28 PM, Magnus Myreen <magnus.myreen at gmail.com>
>> > wrote:
>> >>
>> >> On 17 March 2017 at 19:14, Yong Kiam <tanyongkiam at gmail.com> wrote:
>> >> > I wasn't at the Hangout either. Hmm, where should I do the analysis
>> >> > then?
>> >>
>> >> Both clos_call and clos_to_bvl produce code table entries.
>> >>
>> >> > Ramana suggested to put it as early as possible to avoid extra work
>> >> > in
>> >> > the
>> >> > compiler.
>> >>
>> >> My impression is that most things run pretty quickly up to closLang.
>> >>
>> >> > The issue with putting it later on is that it becomes less obvious
>> >> > whether
>> >> > an expression is pure without doing more complicated analysis, but
>> >> > the
>> >> > advantage is that many globals can be deleted.
>> >>
>> >> Why is purity so important? In closLang, various functions expressions
>> >> are tied to globals. A Fun-expression is always pure. Most of the
>> >> expressions you want to delete are Fun-expressions.
>> >>
>> >> > It seems like we do want to put it before clos_to_bvl to avoid
>> >> > generating
>> >> > call table entries for un-used function, and then we want another one
>> >> > after
>> >> > inlining, possibly combined with code table elimination so that
>> >> > un-used
>> >> > globals (such as the initial definition of + can be deleted).
>> >>
>> >> Could you have one implementation that could run in closLang before
>> >> clos_call and after clos_call?
>> >>
>> >> Cheers,
>> >> Magnus
>> >>
>> >> > On Fri, Mar 17, 2017 at 2:21 AM, Magnus Myreen
>> >> > <magnus.myreen at gmail.com>
>> >> > wrote:
>> >> >>
>> >> >> I can't be in the hangout today, nor read the wiki effectively from
>> >> >> my
>> >> >> phone.
>> >> >>
>> >> >> I just want to add to the discussion that clos_call can make a lot
>> >> >> of
>> >> >> globals unused. It would be nice if the phase which removes unused
>> >> >> globals
>> >> >> came after clos_call. Sorry for not saying this earlier. I hadn't
>> >> >> thought of
>> >> >> it earlier.
>> >> >>
>> >> >> Cheers,
>> >> >> Magnus
>> >> >
>> >> >
>> >
>> >
>
>