Re: Prolog to WAM Register Allocation?

Ludwig Wittgenstein <sender_001@hotmail.com> wrote:
> Hello all,


> I'm currently studying how Prolog compiles its source into Warren
> Abstract Machine code and I was wondering what kind of algorithm does
> Prolog use to assign variables and constants to X and Y registers?


> For instance, predicate(X,Y,john) allocates X1 for X, X2 for Y, and X3
> for john ? or, when I pass a query ?- lives_in(john, X) Do I assume
> that X variable is bound value is in X1 or X2?


> I've seen numerous literature on code generation/register allocation
> for imperative languages (on register-based machines and stack-based
> machines) but there seems to be no literature at all on how Prolog code
> generation against Warren Abstract machines (Ait-Kaci's book barely
> touches on this subject). Any idea on where such information could be
> found?
...




Given that Prolog dates from the 70s, when I did a grad course on
Prolog compiling c1995 I was surprised the sources were still papers
written by Warren (the Edinburgh one) and some selected otherts.




In the WAM model there are "permanent" registers and "temporary" ones.
Whether something is temp/perm depends on whether it's referenced
in the body past goal #1. If so, it's permanent; else temp.




The model is highly optimised, as you probably gather, so stack frames
(and -- hence -- number of permanent vars that need to be restored on
backtracking) get shrunk as evaluation of a goal list proceeds. Numerous
other tricks are used to minimise stack usage (e.g. determining whether
variables need to be saved on the heap instead of the stack by a runtime
test). It's all very complicated in its full generality.




If you pop over to comp.prolog you might get something out of Jan W
who implemented a "WAM in 8 instructions" compiler back in the 90s.
His SWIPL implemention is much more complex than that, so don't get
diverted. :)

Return to the comp.compilers page.
Search the comp.compilers archives again.