[CakeML-dev] Globals and clos_call

Sun Mar 19 08:37:55 UTC 2017

I'm working on A1 in modLang, as Magnus suggests.

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.

On Sat, Mar 18, 2017 at 4:32 AM, Magnus Myreen <magnus.myreen at gmail.com>
wrote:

> 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
> >>> >> >
> >>> >> >
> >>> >
> >>> >
> >>
> >>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.cakeml.org/pipermail/developers/attachments/20170319/5c08aff5/attachment.html>