RTH helped me find that the problem in r_u_s is that we are calling
fold_stmt which is slow as there are huge number of statements in this
testcase.
The following patch added the calls to fold_stmt:
2004-01-10  Jan Hubicka  <jh@suse.cz>
         * tree-cfg.c (remove_usless_stmts_cond):  Fold statement.
         (remove_useless_stmts_1):  Fold trees we know how to fold.

If we revert this patch we actually speed up GCC for the following 
testcase:
#define ELSEIF1 else if (!a) f();
#define ELSEIF2     ELSEIF1     else if (a) ;
#define ELSEIF4     ELSEIF2     ELSEIF2
#define ELSEIF8     ELSEIF4     ELSEIF4
#define ELSEIF16    ELSEIF8     ELSEIF8
#define ELSEIF32    ELSEIF16    ELSEIF16
#define ELSEIF64    ELSEIF32    ELSEIF32
#define ELSEIF128   ELSEIF64    ELSEIF64
#define ELSEIF256   ELSEIF128   ELSEIF128
#define ELSEIF512   ELSEIF256   ELSEIF256
#define ELSEIF1024  ELSEIF512   ELSEIF512
#define ELSEIF2048  ELSEIF1024  ELSEIF1024
#define ELSEIF4096  ELSEIF2048  ELSEIF2048
void
foo (int a)
{
   int b;

   if (a);
   ELSEIF4096
}

OK? Boostrapped and tested on ppc-darwin.

Thanks,
Andrew Pinski

ChangeLog:

	Revert:
	* tree-cfg.c (remove_usless_stmts_cond):  Fold statement.
	(remove_useless_stmts_1):  Fold trees we know how to fold.

Patch: