This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Middle-end dead code elimination
- From: Roger Sayle <roger at www dot eyesopen dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Sat, 29 Mar 2003 09:20:39 -0700 (MST)
- Subject: [PATCH] Middle-end dead code elimination
The following patch implements limited syntax-directed dead code
elimination in GCC's middle-end. The theory is that now that we
have function-at-time compilation its possible for GCC's expanders
to avoid generating RTL that it knows is unreachable.
For example, in the following example
void foo()
{
if (0)
bar ();
}
the GCC middle-end generates RTL for the call to bar, even though
it knows that code is unreachable.
These insns get eliminated by RTL dead-code elimination anyway (except
at -O0), but by creating less RTL initially, we speed up these RTL
optimizers and by allocating less memory, reduce the compiler footprint
and possible memory fragmentation.
On the i686-pc-linux-box I'm using, this patch reduced the time to
perform a full bootstrap, all languages except Ada and treelang
including the libjava and libstdc++-v3 libraries by 15 seconds.
Given the process takes an hour, the 0.4% speed-up isn't great,
but every little bit helps. It also improves the quality of -O0
code, and I expect bigger savings in template-based C++ code, where
"expand" has already been shown to be an issue.
This optimization centers around "expand_unreachable_stmt", a new
function, which is an analog of the existing "expand_stmt". The
semantics of this function are to skip all statements up until
the first label (case label or use label) where control flow can
resume and only emit RTL for this and later statements.
This new expand_unreachable_stmt is called when the condition in
an IF_STMT is a constant, for the body of a switch statement (which
is unreachable until the first label), and for code immediately
following "return", "break", "continue" or "goto". This new function
also understands that labels may be burried in expressions, and
that loop constructs such as "while" and "for" can branch back to
their starts following a label.
I suspect that this type of syntax-directed optimization is common
in high-performance compilers, such as Borland's TurboPascal, that
attempt to generate reasonable code from a single pass over the
source code.
I appreciate that much of this functionality may eventually be
provided by the tree-ssa branch, but the implementation below is
very light-weight (read doesn't degrade performance if SSA DCE
has already been performed), gives measurable benefits for 3.4,
and improves code quality at -O0 [which probably won't enable SSA].
The following code has been tested on i686-pc-linux-gnu, with a
full "make bootstrap", all languages except Ada and treelang, and
regression tested with a top-level "make -k check" (except for
libjava due to timeouts) with no new regressions. Many of the
common gotchas are already in the test-suite, but I've also added
two new hairy kernel-like testcases to confirm nothing breaks.
Ok for mainline?
2003-03-29 Roger Sayle <roger at eyesopen dot com>
* c-semantics.c (find_reachable_label): New function to find a
potentially reachable label in an expression.
(expand_unreachable_if_stmt): Similar to expand_if_stmt but
assumes the start of the IF_STMT is unreachable (dead) code.
(expand_unreachable_stmt): Similar to expand_stmt but assumes
the start of the statement list is unreachable (dead) code.
(genrtl_if_stmt): If the controlling expression of the IF
is constant, use expand_unreachable_stmt for the THEN or ELSE
clause as appropriate.
(genrtl_switch_stmt): Use expand_unreachable_stmt to expand
the body of a SWITCH statement.
(expand_stmt): The code immediately following a "return",
"break", "continue" or "goto" is unreachable.
* Makefile.in (c-semantics.o): Depend upon tree-inline.h.
* gcc.c-torture/execute/medce-1.c: New test case.
* gcc.c-torture/execute/medce-2.c: New test case.
Index: c-semantics.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/c-semantics.c,v
retrieving revision 1.53
diff -c -3 -p -r1.53 c-semantics.c
*** c-semantics.c 22 Feb 2003 00:32:02 -0000 1.53
--- c-semantics.c 29 Mar 2003 14:34:04 -0000
*************** Software Foundation, 59 Temple Place - S
*** 39,44 ****
--- 39,45 ----
#include "output.h"
#include "timevar.h"
#include "predict.h"
+ #include "tree-inline.h"
/* If non-NULL, the address of a language-specific function for
expanding statements. */
*************** void (*lang_expand_stmt) PARAMS ((tree))
*** 51,56 ****
--- 52,62 ----
variables and labels do not require any RTL generation. */
void (*lang_expand_decl_stmt) PARAMS ((tree));
+ static tree find_reachable_label_1 PARAMS ((tree *, int *, void *));
+ static tree find_reachable_label PARAMS ((tree));
+ static bool expand_unreachable_if_stmt PARAMS ((tree));
+ static bool expand_unreachable_stmt PARAMS ((tree));
+
/* Create an empty statement tree rooted at T. */
void
*************** genrtl_if_stmt (t)
*** 409,419 ****
emit_line_note (input_filename, lineno);
expand_start_cond (cond, 0);
if (THEN_CLAUSE (t))
! expand_stmt (THEN_CLAUSE (t));
if (ELSE_CLAUSE (t))
{
expand_start_else ();
! expand_stmt (ELSE_CLAUSE (t));
}
expand_end_cond ();
}
--- 415,434 ----
emit_line_note (input_filename, lineno);
expand_start_cond (cond, 0);
if (THEN_CLAUSE (t))
! {
! if (cond && integer_zerop (cond))
! expand_unreachable_stmt (THEN_CLAUSE (t));
! else
! expand_stmt (THEN_CLAUSE (t));
! }
!
if (ELSE_CLAUSE (t))
{
expand_start_else ();
! if (cond && integer_nonzerop (cond))
! expand_unreachable_stmt (ELSE_CLAUSE (t));
! else
! expand_stmt (ELSE_CLAUSE (t));
}
expand_end_cond ();
}
*************** genrtl_switch_stmt (t)
*** 672,678 ****
emit_line_note (input_filename, lineno);
expand_start_case (1, cond, TREE_TYPE (cond), "switch statement");
! expand_stmt (SWITCH_BODY (t));
expand_end_case_type (cond, SWITCH_TYPE (t));
}
--- 687,693 ----
emit_line_note (input_filename, lineno);
expand_start_case (1, cond, TREE_TYPE (cond), "switch statement");
! expand_unreachable_stmt (SWITCH_BODY (t));
expand_end_case_type (cond, SWITCH_TYPE (t));
}
*************** expand_stmt (t)
*** 808,814 ****
case RETURN_STMT:
genrtl_return_stmt (t);
! break;
case EXPR_STMT:
genrtl_expr_stmt_value (EXPR_STMT_EXPR (t), TREE_ADDRESSABLE (t),
--- 823,830 ----
case RETURN_STMT:
genrtl_return_stmt (t);
! expand_unreachable_stmt (TREE_CHAIN (t));
! return;
case EXPR_STMT:
genrtl_expr_stmt_value (EXPR_STMT_EXPR (t), TREE_ADDRESSABLE (t),
*************** expand_stmt (t)
*** 843,853 ****
case BREAK_STMT:
genrtl_break_stmt ();
! break;
case CONTINUE_STMT:
genrtl_continue_stmt ();
! break;
case SWITCH_STMT:
genrtl_switch_stmt (t);
--- 859,871 ----
case BREAK_STMT:
genrtl_break_stmt ();
! expand_unreachable_stmt (TREE_CHAIN (t));
! return;
case CONTINUE_STMT:
genrtl_continue_stmt ();
! expand_unreachable_stmt (TREE_CHAIN (t));
! return;
case SWITCH_STMT:
genrtl_switch_stmt (t);
*************** expand_stmt (t)
*** 872,878 ****
NOTE_PREDICTION (note) = NOTE_PREDICT (PRED_GOTO, NOT_TAKEN);
}
genrtl_goto_stmt (GOTO_DESTINATION (t));
! break;
case ASM_STMT:
genrtl_asm_stmt (ASM_CV_QUAL (t), ASM_STRING (t),
--- 890,897 ----
NOTE_PREDICTION (note) = NOTE_PREDICT (PRED_GOTO, NOT_TAKEN);
}
genrtl_goto_stmt (GOTO_DESTINATION (t));
! expand_unreachable_stmt (TREE_CHAIN (t));
! return;
case ASM_STMT:
genrtl_asm_stmt (ASM_CV_QUAL (t), ASM_STRING (t),
*************** expand_stmt (t)
*** 904,906 ****
--- 923,1065 ----
t = TREE_CHAIN (t);
}
}
+
+ /* If *TP is a potentially reachable label, return nonzero. */
+
+ static tree
+ find_reachable_label_1 (tp, walk_subtrees, data)
+ tree *tp;
+ int *walk_subtrees ATTRIBUTE_UNUSED;
+ void *data ATTRIBUTE_UNUSED;
+ {
+ switch (TREE_CODE (*tp))
+ {
+ case LABEL_STMT:
+ case CASE_LABEL:
+ return *tp;
+
+ default:
+ break;
+ }
+ return NULL_TREE;
+ }
+
+ /* Determine whether expression EXP contains a potentially
+ reachable label. */
+ static tree
+ find_reachable_label (exp)
+ tree exp;
+ {
+ int line = lineno;
+ const char *file = input_filename;
+ tree ret = walk_tree (&exp, find_reachable_label_1, NULL, NULL);
+ input_filename = file;
+ lineno = line;
+ return ret;
+ }
+
+ /* Expand an unreachable if statement, T. This function returns
+ true if the IF_STMT contains a potentially reachable code_label. */
+ static bool
+ expand_unreachable_if_stmt (t)
+ tree t;
+ {
+ if (find_reachable_label (IF_COND (t)) != NULL_TREE)
+ {
+ genrtl_if_stmt (t);
+ return true;
+ }
+
+ if (THEN_CLAUSE (t) && ELSE_CLAUSE (t))
+ {
+ if (expand_unreachable_stmt (THEN_CLAUSE (t)))
+ {
+ rtx label;
+ label = gen_label_rtx ();
+ emit_jump (label);
+ expand_unreachable_stmt (ELSE_CLAUSE (t));
+ emit_label (label);
+ return true;
+ }
+ else
+ return expand_unreachable_stmt (ELSE_CLAUSE (t));
+ }
+ else if (THEN_CLAUSE (t))
+ return expand_unreachable_stmt (THEN_CLAUSE (t));
+ else if (ELSE_CLAUSE (t))
+ return expand_unreachable_stmt (ELSE_CLAUSE (t));
+
+ return false;
+ }
+
+ /* Expand an unreachable statement list. This function skips all
+ statements preceding the first potentially reachable label and
+ then expands the statements normally with expand_stmt. This
+ function returns true if such a reachable label was found. */
+ static bool
+ expand_unreachable_stmt (t)
+ tree t;
+ {
+ int saved;
+
+ while (t && t != error_mark_node)
+ {
+ switch (TREE_CODE (t))
+ {
+ case GOTO_STMT:
+ case CONTINUE_STMT:
+ case BREAK_STMT:
+ break;
+
+ case FILE_STMT:
+ input_filename = FILE_STMT_FILENAME (t);
+ break;
+
+ case RETURN_STMT:
+ if (find_reachable_label (RETURN_STMT_EXPR (t)) != NULL_TREE)
+ {
+ expand_stmt (t);
+ return true;
+ }
+ break;
+
+ case EXPR_STMT:
+ if (find_reachable_label (EXPR_STMT_EXPR (t)) != NULL_TREE)
+ {
+ expand_stmt (t);
+ return true;
+ }
+ break;
+
+ case IF_STMT:
+ if (expand_unreachable_if_stmt (t))
+ {
+ expand_stmt (TREE_CHAIN (t));
+ return true;
+ }
+ break;
+
+ case COMPOUND_STMT:
+ if (expand_unreachable_stmt (COMPOUND_BODY (t)))
+ {
+ expand_stmt (TREE_CHAIN (t));
+ return true;
+ }
+ break;
+
+ case SCOPE_STMT:
+ saved = stmts_are_full_exprs_p ();
+ prep_stmt (t);
+ genrtl_scope_stmt (t);
+ current_stmt_tree ()->stmts_are_full_exprs_p = saved;
+ break;
+
+ default:
+ expand_stmt (t);
+ return true;
+ }
+ t = TREE_CHAIN (t);
+ }
+ return false;
+ }
+
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1026
diff -c -3 -p -r1.1026 Makefile.in
*** Makefile.in 23 Mar 2003 20:13:50 -0000 1.1026
--- Makefile.in 29 Mar 2003 14:34:06 -0000
*************** c-format.o : c-format.c $(CONFIG_H) $(SY
*** 1330,1336 ****
c-semantics.o : c-semantics.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
$(C_TREE_H) flags.h toplev.h output.h c-pragma.h $(RTL_H) $(GGC_H) \
! $(EXPR_H) $(PREDICT_H)
c-dump.o : c-dump.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
$(C_TREE_H) tree-dump.h
--- 1330,1336 ----
c-semantics.o : c-semantics.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
$(C_TREE_H) flags.h toplev.h output.h c-pragma.h $(RTL_H) $(GGC_H) \
! $(EXPR_H) $(PREDICT_H) tree-inline.h
c-dump.o : c-dump.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
$(C_TREE_H) tree-dump.h
extern void abort (void);
extern void link_error (void);
static int ok = 0;
void bar (void)
{
ok = 1;
}
void foo(int x)
{
switch (x)
{
case 0:
if (0)
{
link_error();
case 1:
bar();
}
}
}
int main()
{
foo (1);
if (!ok)
abort ();
return 0;
}
extern void abort ();
static int ok = 0;
int bar(void)
{
ok |= 1;
return 1;
}
void bat(void)
{
ok |= 2;
}
void baz(void)
{
ok |= 4;
}
void foo()
{
goto lab;
if (0)
{
if (({lab: bar();}))
bat ();
else
baz ();
}
}
int main()
{
foo();
if (ok != 3)
abort ();
return 0;
}
Roger
--
Roger Sayle, E-mail: roger at eyesopen dot com
OpenEye Scientific Software, WWW: http://www.eyesopen.com/
Suite 1107, 3600 Cerrillos Road, Tel: (+1) 505-473-7385
Santa Fe, New Mexico, 87507. Fax: (+1) 505-473-0833