C "optimization" (8 of 8)

[Dan Klein]

This is a continuation of my diatribe on "C doesn't optimize, it neatens".
In this and other articles, I compare a true optimizing compiler (Bliss-32
running under VMS) to a code neatener (C running under BSD 4.1c).  Any and
all counterexamples are welcome.  However, this is NOT a comparison of the
languages.  Both C and Bliss have their good and bad points.  This is simply
a comparison of the code they generate.  As in all examples, the source
code and uncensored assembly code is presented.  In all examples, the C source
and Bliss source are as nearly identical as language differences permit.  I
have not taken advantage of any "tricks" to get either language to perform
better or worse than the other.  The optimizer was enabled for both languages.

		-Dan Klein, Mellon Institute, Pittsburgh	(412)578-3382
=============================================================================

In this example, I construct a structure that consists of a pointer and
a data part.  The operation that is being performed is that of moving the
data part of one component to the data part of the component immediately
preceeding it in the linked list.  The mechanism is more naturally expressed
in C, but Bliss outperforms it even in light of the "irregular" constraints
placed on the code generator.

Since the Bliss optimizer has some flow control analysis built into it, it
is able to eliminate common sub-expressions from complex statements or groups
of statements.  In this case, the common subexpression (using C syntax) is
the pointer chain "a->p->p->p->".  Bliss is able to recognize this commonality,
and evaluate that chain only once.  Since C, on the other hand, has only a
peephole optimizer to work with, it fails to see this common subexpression,
and evaluates both "a->p->p->p->d" and "a->p->p->p->p->d" completely.  Without
a doubt, the Bliss generated code is both more speed and space efficient than
the C generated code.
----------------------------------------+-------------------------------------
switches structure(ref block[2]);	|	typedef struct dp *DP;
field CP =				|	struct dp {
    set					|	    int d;
    d = [0,0,%BPVAL,0],			|	    DP  p;
    p = [1,0,%BPADDR,0]			|	    }
    tes;				|
					|	test(a)
routine test(a)  : NoValue =		|	DP a;
    begin				|	{
    map a : ref block[2] field(CP);	|	    a->p->p->p->d =
    a[p][p][p][d] = .a[p][p][p][p][d];  |	 	a->p->p->p->p->d;
    end;				|	}
					|
					|
	.TITLE  FOO			|		.data
					|		.text
	.PSECT  $CODE$,NOWRT,2		|	LL0:	.align  1
					|		.globl  _test
TEST:	.WORD	^M<>			|		.lcomm  L16,8
	MOVL	4(AP), R0		|		.set	L12,0x0
	MOVL	4(R0), R0		|		.data
	MOVL	4(R0), R0		|		.text
	MOVL	4(R0), R0		|	_test:  .word	L12
	MOVL	@4(R0), (R0)		|		movl	4(ap),r0
	RET				|		movl	4(r0),r0
					|		movl	4(r0),r0
					|		movl	4(r0),r0
					|		movl	4(ap),r1
					|		movl	4(r1),r1
					|		movl	4(r1),r1
					|		movl	*4(r0),*4(r1)
					|		movab	L16,r1
					|		movq	(r0),(r1)
					|		movab	L16,r0
					|		ret