[CakeML-dev] Extending loc_offset on arm6

[Scott Owens]

> On 2017/07/07, at 09:07, Ramana Kumar <Ramana.Kumar at cl.cam.ac.uk> wrote:
> 
> (I'm moving this thread to the developers list.)

Good idea. I’ve recently been thinking about how those early phases work. We do have some scope for changing them as we change the semantics for eval. Right now,  a sequence of top level declarations get put into a single expression which is then wrapped in a handle expression. This was important for the REPL, since if you send several declarations to it at once (e.g., they are all in the same module), and one in the middle raises an exception, then you don’t want to do the subsequent ones, but you don’t want to just terminate the whole program either.

If we want to have the ability to eval a module definition, the whole module’s body will need to be wrapped up in a handler somehow. It is convenient to use expressions for that, but we could specialise the evaluate a list of expressions construct with a keep-going flag to achieve a similar result. I don’t know if that would help in this case, because I don’t really understand how building a big expression is causing problems in the back end.

Scott

> 
> 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.
> >> >
> >
> >
> 
> _______________________________________________
> Developers mailing list
> Developers at cakeml.org
> https://lists.cakeml.org/listinfo/developers