Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!unisoft!hoptoad!gnu
From: gnu@hoptoad.uucp (John Gilmore)
Newsgroups: comp.lang.c
Subject: Re: Bad optimization in PCC?
Message-ID: <4492@hoptoad.uucp>
Date: 26 Apr 88 12:53:16 GMT
References: <793@amnesix.liu.se>
Organization: Grasshopper Group in San Francisco
Lines: 37

Mikael Pettersson complained that neither pcc nor gcc optimized away
a second test of *np which occurs at the target label of another test of *np
(where np is char *, not declared volatile).  Chris Torek did a good job of
explaining that pcc doesn't optimize this because its optimizer transforms
assembler into assembler, and doesn't know whether np was volatile or not
(or even that this register contains your variable "np", or even that the
volatile keyword exists).

While I'm not an expert at gcc's internals, I think that gcc does not
catch this because the common subexpression optimizer does not
propagate the values of variables across basic blocks.  In other words,
after a successful branch it does not know that the value of "*np" is in a
register already.  I'll let Richard's comments (in cse.c) tell it:

/* The basic idea of common subexpression elimination is to go
   through the code, keeping a record of expressions that would
   have the same value at the current scan point, and replacing
   expressions encountered with the cheapest equivalent expression.
 
   It is too complicated to keep track of the different possibilities
   when control paths merge; so, at each label, we forget all that is
   known and start fresh.  This can be described as processing each
   basic block separately.  Note, however, that these are not quite
   the same as the basic blocks found by a later pass and used for
   data flow analysis and register packing.  We do not need to start fresh
   after a conditional jump instruction if there is no label there.
 */

Richard Stallman, gcc's author, constantly tries to balance the compile
time and memory requirements versus how much optimization can be
gained.  The Microsoft Cmerge compiler provides a good example where
serious optimization is done but the compiler is too slow as a result.

This is one optimization I'd like to see too, and someday I may figure
(and implement) a cheap way to do it.
-- 
John Gilmore  {sun,pacbell,uunet,pyramid,ihnp4}!hoptoad!gnu        gnu@toad.com
/* No comment */