[CakeML-dev] Globals and clos_call

[Magnus Myreen]

Hi all,

I read Yong Kiam's comments as saying that we should only have A1
implemented and only for closLang, but run A1 twice. By running it
before clos_call we prevent unused code table entries from turning up.
By running it after clos_call but before clos_to_bvl, we replace a few
now-unused globals with dummy values (and avoid producing other code
table entries in clos_to_bvl). This all sounds good to me, since it
means that we can avoid B1 completely. One could optionally implement
A2 in BVL.

I can imagine that doing A1 in modLang would probably be a bit simpler
than the same in closLang, because closLang has Call and the multi-arg
semantics.

One option would be to just do A1 in modLang and then ignore the junk
that a successful combination of clos_call and clos_to_bvl leaves in
the globals and the code table. The junk only consists of small pieces
of code that performs a tail call to another code table entry.

I'm now of the opinion that the best course of action is to:
 - implement A1 in modLang (where it should be easy-ish),
 - and maybe later port A1 to closLang to run after clos_call,
 - and maybe later implement A2 in BVL.

I suspect having A1 in modLang should give most of the benefit. The
other steps will just tidy things up a bit. I worry a bit about
putting too much effort into these whole-program optimisations, since
they won't be applicable to any program that uses the Eval primitive,
once we have it.

Cheers,
Magnus


On 18 March 2017 at 04:29, Ramana Kumar <Ramana.Kumar at cl.cam.ac.uk> wrote:
> 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
>>> >> >
>>> >> >
>>> >
>>> >
>>
>>