🚀 go-pugleaf

Several people have asked me to post the code and/or explain what kind of
optimizations are done.  Aw shucks, don't you know that a magician doesn't
like to give away his secrets?

I will answer the second question first.  The tak benchmark is able to
take advantage of several optimization techniques:

(1) Deterministic predicates.  The compiler is able to recognize determinacy
    in the program.  The Prolog code given for tak uses a tremendous amount of
    memory on systems like Quintus or Sicstus Prolog because they will create
    a choice point for each call.  A cut is needed to make it run for them.
(2) Simplifying variable binding.  The compiler recognizes that the variables
    used to bind the output of tak can be implemented in a simpler way than
    the default method of creating a memory cell pointing to itself, passing
    it into the routine, and binding it there.  Tak does recursive calculations
    on integers (i.e. objects that fit in a register), so the compiler is able
    to output the results directly in registers.  This is a general technique
    which is also used to implement integer arithmetic.
(3) Last call optimization.  The last call to tak is compiled as a jump, i.e.
    recursion is converted to iteration.  This is not done by the C compiler,
    and measurements with the pixie utility on the MIPS show that this explains
    a large part of the speed difference.  This optimization is essential for
    Prolog because the only way to denote iteration in Prolog is by using
    recursion.  C has other constructs to denote iteration (i.e. "for" and
    "while" loops) so it does not need last call optimization as badly as
    Prolog does.
(4) Dataflow analysis.  The compiler incorporates a global dataflow analysis
    module to do type inferencing.  For tak, the results of analysis are crucial
    for optimization (2) above, and they also make it unnecessary to do type
    checking, dereferencing, and trailing.  To do analysis the programmer has
    to declare only the types of the entry points.  For tak this is a single
    directive:
	:- entry((main:-true)).
    No other declarations are used.

For those who are interested, the paper "The Benefits of Global Flow Analysis
for an Optimizing Prolog Compiler", to appear in the 1990 North American
Conference on Logic Programming, describes techniques (2) and (4) in detail
and gives more numbers (for the BAM processor).

The compiler has only recently been ported to the MIPS and the run-time system
is not yet completely functional there.  I plan to extend the comparison to
other programs (such as Overbeek's theorem prover).  The BAM version is
completely functional, but the BAM processor does not have a C compiler.

The Aquarius compiler does not do memoization.  However, there is no reason
a smart (*very* smart) compiler couldn't do it for tak.  The C compiler could
do it as well.  This is an orthogonal issue to the performance comparison.

By the way, the execution time for tak(18,12,6), given by Gabriel in his study
of Lisp performance, is 31 ms for Aquarius Prolog on a 25 MHz MIPS processor.

Sincerely,
    Peter Van Roy

-------------------------------------------------------------------------------

In answer to the first question, here is the MIPS assembly code generated by
the Aquarius compiler for the tak benchmark:
(I've left out the code for the run-time system.)

	.data
	.align	3
$32:
	.word	7
	.word	atm_string_0+1
atm_string_0:
	.word	1463
	.word	1f+1
1:
	.word	1495
	.word	3
	.text
	.align	2
 #	procedure(tak/0)
	.globl	tak_0
	.ent	tak_0
tak_0:
$33:
	.set	noreorder
	sltu	$14, $17, $16
	bne	$14, 0, 1f
	move	$14, $16
	move	$16, $17
 #	label(1)
1:
	addu	$16, 8
	sw	$14, -8($16)
	sw	$31, -4($16)
	.set	reorder
	li	$2, 295
	li	$3, 199
	li	$4, 103
	jal	$34
	move	$2, $5
	jal	$35
	lw	$31, -4($16)
	lw	$16, -8($16)
	j	$36
	.end	tak_0
 #	procedure(tak/4)
	.globl	tak_4
	.ent	tak_4
tak_4:
$34:
	bgt	$2, $3, $37
	move	$5, $4
	j	$31
 #	label('$b_tak/4_2'/4)
$37:
	.set	noreorder
	sltu	$14, $17, $16
	bne	$14, 0, 1f
	move	$14, $16
	move	$16, $17
 #	label(1)
1:
	addu	$16, 32
	sw	$14, -8($16)
	sw	$31, -4($16)
	.set	reorder
	sw	$2, -24($16)
	sw	$3, -20($16)
	sw	$4, -28($16)
	addu	$2, $2, -16
	jal	$34
	sw	$5, -16($16)
	lw	$14, -20($16)
	addu	$2, $14, -16
	lw	$3, -28($16)
	lw	$4, -24($16)
	jal	$34
	sw	$5, -12($16)
	lw	$14, -28($16)
	addu	$2, $14, -16
	lw	$3, -24($16)
	lw	$4, -20($16)
	jal	$34
	lw	$2, -16($16)
	lw	$3, -12($16)
	move	$4, $5
	lw	$31, -4($16)
	lw	$16, -8($16)
	j	$34
	.end	tak_4

-------------------------------------------------------------------------------