[CakeML-dev] Extending loc_offset on arm6

[Ramana Kumar]

(I'm moving this thread to the developers list.)

I'm not opposed to making more of the compiler operate on lists of
expressions.
I think the place where the giant expression gets made is in con_to_dec, so
that's where most of the work would be.
Scott designed the way it currently works, if I recall correctly.

On 7 July 2017 at 17:58, Magnus Myreen <magnus.myreen at gmail.com> wrote:

> You are right, and I think the idea to split expressions in closLang
> phases sounds good.
>
> There could be a very simple way of splitting them there: split the
> main expression at every top-level Seq (note that Seq in closLang is
> Let [x; y] (Var 1)), and just chain them together with tail-calls.
>
> At one point, I was arguing for not composing the main program into
> one giant Seq-composed expression, instead I argued that we should
> have a list of expressions in languages from closLang and above and
> the semantics is that one runs through all of them in order. Such a
> setup would make it easy to make a tail-calling chain of all
> expressions in closLang. This would mean that there would only be
> giant functions in the call table if the user actually wrote a giant
> function. I remember that my suggestion was shot down and that I went
> on to implement the expression splitting in bvl_to_bvi, because it's a
> part of the compiler where I don't need to build a consensus before
> being able to change it.
>
> I think we should revisit whether it's a good idea to compose the
> entire program into one giant expression in the early phases of the
> compiler. I think the early phases should produce a list of
> expressions.
>
> Cheers,
> Magnus
>
>
> On 7 July 2017 at 09:45, Yong Kiam <tanyongkiam at gmail.com> wrote:
> > Hmm, but the offending LocValues that I'm getting so far are the ones
> > generated by Fn and Letrec in clos_to_bvi when it's creating the closure
> > value for them, and presumably saving the Label.
> >
> > The situation you describe seems like it will only occur if we managed to
> > inline the call to something like:
> >
> > ...
> > append x y
> > ...
> >
> > becomes
> >
> > ...
> > r <- Label append
> > call r
> > ...
> >
> > But in that situation, wouldn't we have already generated Call (...)
> > directly and not required a LocValue?
> >
> >
> > On Fri, Jul 7, 2017 at 5:38 PM, Magnus Myreen <magnus.myreen at gmail.com>
> > wrote:
> >>
> >> Hi Yong Kiam and Anthony,
> >>
> >> My worry is that there is no good place to put some of the code table
> >> entries, i.e. even if you reorder them you will end up with some very
> >> long LocValue offsets. I'm thinking of common functions, such as
> >> list-append, which are defined as one of the first functions in the
> >> basis library, but are used through out most applications.
> >>
> >> (I note that the clos_call optimisation reduces the number of LocValue
> >> instances with long offsets.)
> >>
> >> I think there are essentially two options:
> >>
> >>  a) make LocValue allow for larger offsets on ARM (and any other arch
> >>     necessary)
> >>
> >>  b) populate and use a new lookup table for location values -- I note
> >>     that the population of the lookup table would need to be
> >>     distributed so that we again avoid referring to locations that are
> >>     too far away.
> >>
> >> I would expect (a) to be a bit faster and better, even if the LocValue
> >> instruction expands to, say, 4 instructions for larger offsets.
> >>
> >> Cheers,
> >> Magnus
> >>
> >>
> >>
> >> On 7 July 2017 at 06:24, Yong Kiam <tanyongkiam at gmail.com> wrote:
> >> > Hi Anthony,
> >> >
> >> > Ramana and I have been looking at running the arm6 compiler in the
> >> > logic,
> >> > but we are running into the loc_offset limit in the asm_ok check when
> >> > the
> >> > basis is included. The list of instructions failing asm_ok is
> attached.
> >> >
> >> > I investigated a bit further, and these LocValues are coming from the
> >> > body
> >> > of the main stub, and I guess they're pointers for Fn and Letrec (so,
> >> > for
> >> > every function decl).
> >> >
> >> > Is it possible to extend the range of loc_offset?
> >> >
> >> > @Magnus, two other suggestions we have are:
> >> >
> >> > 1) Move the main expression splitting up from bvl_to_bvi into closLang
> >> > so
> >> > that the entries are forced to be closer to each other e.g.
> >> >
> >> > Code Table 0:
> >> >   let fun f = ...
> >> >   let fun g = ...
> >> >   let fun h = ...
> >> >
> >> > becomes
> >> >
> >> > Code Table 0:
> >> >   let fun f = ...
> >> >   let fun g = ...
> >> >   Call 1
> >> >
> >> > Code Table 1:
> >> >   let fun h = ...
> >> >
> >> > Then clos_to_bvl should generate entries for 0,f,g,1,h in that order
> so
> >> > that
> >> > f,g are now closer to 0, which will contain Labels for them. Ramana
> and
> >> > I
> >> > prefer doing it this way, because we can still see Letrecs at
> closLang.
> >> >
> >> > 2) The alternative is to keep the splitting where it is, and
> introduce a
> >> > new
> >> > pass that re-orders code table entries after it. So the above example
> >> > would
> >> > initially be:
> >> >
> >> > Code Table 0
> >> > let fun f = ... Label f'
> >> > let fun g = ... Label g'
> >> > let fun h = ... Label h'
> >> >
> >> > Code Table f'
> >> > Code Table g'
> >> > Code Table h'
> >> >
> >> > Then splitting might make it:
> >> > Code Table 0
> >> > let fun f = ... Label f'
> >> > let fun g = ... Label g'
> >> >
> >> > Code Table 1
> >> > let fun h = ... Label h'
> >> >
> >> > Code Table f'
> >> > Code Table g'
> >> > Code Table h'
> >> >
> >> > Then the new pass would heuristically (?) reorder the entries to force
> >> > Labels to be closer:
> >> >
> >> > Code Table 0
> >> > let fun f = ... Label f'
> >> > let fun g = ... Label g'
> >> > Code Table f'
> >> > Code Table g'
> >> >
> >> > Code Table 1
> >> > let fun h = ... Label h'
> >> > Code Table h'
> >> >
> >> > The disadvantage to this approach, I think, is that we can't really
> >> > control
> >> > the splits properly, e.g. what happens if a Letrec gets compiled to a
> >> > split
> >> > across two code table entries?
> >> >
> >> > In any case, I am going to try and manually do 2) now to see if it
> >> > actually
> >> > helps.
> >> >
> >
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.cakeml.org/pipermail/developers/attachments/20170707/4dc0508c/attachment.html>