[CakeML-dev] Globals and clos_call

Scott Owens S.A.Owens at kent.ac.uk
Sun Mar 19 17:38:29 UTC 2017


Look at the evalute_prompt function in modSem. If you get an exception while evaluating a binding, then subsequent globals in that group of bindings (e.g., a module body) get initialised with None. In later languages, you get two levels of options.

Scott

> On 2017/03/19, at 08:37, Yong Kiam <tanyongkiam at gmail.com> wrote:
> 
> 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
> >>> >> >
> >>> >> >
> >>> >
> >>> >
> >>
> >>
> 
> _______________________________________________
> Developers mailing list
> Developers at cakeml.org
> https://lists.cakeml.org/listinfo/developers




More information about the Developers mailing list