Path: utzoo!mnetor!uunet!husc6!bbn!rochester!pt.cs.cmu.edu!sei!sei.cmu.edu!firth
From: firth@sei.cmu.edu (Robert Firth)
Newsgroups: comp.lang.c
Subject: Re: Bad optimization in PCC?
Message-ID: <5246@aw.sei.cmu.edu>
Date: 26 Apr 88 21:05:29 GMT
References: <793@amnesix.liu.se>
Sender: netnews@sei.cmu.edu
Reply-To: firth@bd.sei.cmu.edu.UUCP (Robert Firth)
Organization: Carnegie-Mellon University, SEI, Pgh, Pa
Lines: 71

In article <793@amnesix.liu.se> mikpe@amnesix.liu.se (Mikael Pettersson) writes:

[a missed optimisation in some C compilers: the code reads as shown]

>(1) while(*np && (*np++ == *ep++))
>        /* empty */ ;
>(2) if(!*np)
>        *envp = val;
>
>Notice that the value of the test at line (2) is known if the '*np'
>part of line (1) evaluates to 0.
>
>Actual code generated (compiling flags: -O -S):
>
>Sun CC, SunOS3.2                  GNU CC, ver 1.18 for Sun3
>-----------------------------------------------------------
>L18:    tstb    a3@               L5:     moveb a1@,d0
>     (+)jeq     L19   <-----THIS-----> (+)jeq L6
>        cmpmb   a4@+,a3@+                 addql #1,a1
>        jeq     L18                       cmpb a0@+,d0
>L19:    tstb    a3@                       jeq L5
>     (*)jne     L20               L6:     tstb a1@
>        movl    a6@(12),a5@            (*)jne L7
>L20:                                      movel d1,a2@
>                                  L7:

Just to add my own comments.  The optimisation requested should happen
as part of a set of transformations that might be called "branch chaining".

This kind of thing is pretty easy:

	goto L1
	...
    L1: goto L2

The optimiser looks at the target of the jump, sees it is another jump,
and simply changes the first jump to read 'goto L2', naturally also
decrementing the reference count of L1.  (Incidentally, it is sometimes
advantageous to make the reverse transformation, but that's another
story.)

As a next step, observe that the first jump can easily be conditional;
the transformation is still valid:

	if B goto L1
	...
    L1: goto L2

=>	if B goto L2

The third step is where BOTH jumps are conditional.  If the truth
of the first condition implies the truth of the second, we can still
chain:
	if B1 goto L1
	...
    L1: if B2 goto L2	/* B1 implies B2 */

=>	if B1 goto L2

Finally, if the truth of the first condition implies the FALSEHOOD of
the second condition, we can retarget the first branch, giving:

	if B1 goto L1a
	...
    L1: if B2 goto L2	/* B1 implies NOT B2 */
    L1a:

This is the required transformation.  Note, though, that it is a lot
easier to do on the attributed parse tree - optimising the Assembler
code involves also understanding why the second test instruction can
be bypassed, for example.