Re: Compiler design reference sought

[Camm Maguire]

Greetings!  Yes, this has been the roadblock for 2.7 for quite a
while -- compiler speed.  In general, the 2.7 compiler is substantially
heavier than 2.6, but the code produced is much better, at least
potentially so.  All users I have polled have said this is a worthwhile
trade off at least in general.  With work I have reduced the gcl compiler
overhead to less than one half the gcc overhead when building gcl
itself, which I think is acceptable.  I am just tackling the
applications now but will aim for the same minimum compiler performance.

There are quite a few known optimizations yet to be implemented because
of the impact on compiler speed.  I do believe there is an algorithmic
solution to this, but backing out the impact of changing the type of a
binding down the line when one has discovered it is more restricted than
thought without catch/throw is challenging.  These types are primarily
used in branch elimination and type propagation.  In principle, if the
output of pass 1 (e.g. c1lambda-expr) were constrained to reference a
small number of primitives, ideally just special operators, one might be
able to redo the propagation/elimination on this output after the fact.

2.6 has an extremely bare and ad-hoc type system but which is very
fast.  Almost all variables and bindings are type T.  2.7 computes
everything accurately and attains good performance with bitvector
representations.  So the basic operations are sound and fast, it is just
the processing on conflicts which needs work.

I can build maxima on my machine with approximately 2.6 performance and
just 3 test errors at present.  fricas builds are the slowest by far --
evidently the code generated are generating many more type conflicts
than typical in other systems.  I will pinpoint and address this at some
point hopefully in the near future.

Take care,

"Chun Tian (binghe)" <binghe.lisp@gmail.com> writes:

> Sorry, I should really try again before sending the last email. The
> "tangle0.lisp" I extracted, can indeed be compiled by GCL 2.7.0 in a few
> seconds:
>
>>(compile-file "tangle0.lisp")
>
> ;; Compiling tangle0.lisp.
> ;; End of Pass 1.
> ;; End of Pass 2.
> OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3
> ;; Finished compiling /Users/binghe/Lisp/AXIOM/axiom-code/books/tangle0.o.
> #P"/Users/binghe/Lisp/AXIOM/axiom-code/books/tangle0.o"
> NIL
> NIL
>
> P.S. The full "tangle.lisp" from AXIOM source code, when compiled by GCL
> 2.7.0, is really low. But now I don't have confidence to say anything
> like "infinite loop" now. Perhaps it just needs some more time, e.g. 10
> minutes.
>
> --Chun
>
> On 07/02/24 20:34, Chun Tian (binghe) wrote:
>> Hi Camm,
>> 
>> Is it possible that the "iteration" in the GCL compiler that you
>> mentioned, may not terminate (i.e. falling into infinite loops) for
>> certain inputs?
>> 
>> The attached Lisp code is the very beginning part of AXIOM's "tangle"
>> utility for extracting code from LaTeX files. In my machine, GCL 2.7.0
>> compiler seems take forever to compile the (only) Lisp function in it.
>> 
>> My guess is that, in the function, many other Lisp functions are
>> referenced, but these functions are to be defined at later position of
>> the code, and thus their type information is unknown. GCL 2.6.x can
>> compile this file any way, but the current GCL 2.7.0 compiler seems
>> failing into infinite loops.
>> 
>> Regards,
>> 
>> Chun TIAN
>> 
>> On 05/02/24 02:27, Camm Maguire wrote:
>>> Greetings!  Over the years, various theoretical papers on algorithms for
>>> Common Lisp utilities have been very helpful in GCL development,
>>> e.g. Baker's paper on the type system.
>>>
>>> I am looking for a reference on compiler design algorithms which handle
>>> type inferencing most efficiently.  Right now we iterate on conflict,
>>> and I think this is too slow.  Pointers most appreciated!
>>>
>>> Take care,
>>>
>

-- 
Camm Maguire                                        camm@maguirefamily.org
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah