This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] Move dominator opts into tree-ssa-dom.c
- From: law at redhat dot com
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 15 Jul 2003 13:14:05 -0600
- Subject: [tree-ssa] Move dominator opts into tree-ssa-dom.c
- Reply-to: law at redhat dot com
This (large) patch mostly separates the dominator based optimization
from SSA renaming process.
Previously we performed our dominator optimizations while rewriting
each statement. That worked fine and dandy.
However, in my quest to make the dominator optimizations subsume all
the path following code we do in cse1 we're going to have to add
some additional functionality to the dominator optimization code.
Rather than continue to pollute the ssa renamer with the effects of
these improvements to the dominator optimizer, Diego, Andrew and
myself decided to break the dominator optimizer into its own little
sub-pass which runs after we've performed renaming on all the blocks
in the current function.
Note that the dominator optimizer can expose more variables to the SSA
renamer by propagation of ADDR_EXPRs. So after we've renamed all the
blocks, we optimize them and if optimization propagated any ADDR_EXPRs,
then we perform renaming on the newly found variables and rerun the
dominator optimizer as well.
You might think this is expensive -- but it's still a fraction of the
time we spend in the path following code in cse1.
This patch ever-so-slightly improves dominator optimizations by not
considering statements which access static objects as having volatile
memory references. More improvements will occur shortly.
Bootstrapped and regression tested. Note that the 20000724-1 and i386-sse-3
failures are not related to this change -- they are due to Diego's
changes and I'm sure they'll be addressed appropriately.
* Makefile.in (OBJS): Add tree-ssa-dom.o
(tree-ssa-dom.o): Add dependencies.
(ssa.o, cfghooks.o): Use $(TREE_FLOW_H), not tree-flow.h.
* timevar.def: Add new timevar for dominator optimizer. Reorder
slightly.
* tree-dfa.c (add_stmt_operand): Do not consider references to
static storage as volatile operands.
(add_referenced_var): Static storage items reference global memory.
* tree-ssa.c: Simplify by moving everything specific to the
dominator optimizer into tree-ssa-dom.c. Call into the dominator
optimizer after rewriting all the basic blocks.
* tree-ssa-dom.c: New file. Mostly extracted from tree-ssa.c
* tree-flow.h (tree_ssa_dominator_optimize): Prototype.
(dump_dominator_optimization_stats): Likewise.
(debug_dominator_optimization_stats): Likewise.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.98
diff -c -3 -p -r1.903.2.98 Makefile.in
*** Makefile.in 14 Jul 2003 21:18:47 -0000 1.903.2.98
--- Makefile.in 15 Jul 2003 18:49:27 -0000
*************** OBJS = tree-cfg.o tree-dfa.o tree-ssa.o
*** 836,841 ****
--- 836,842 ----
tree-alias-type.o gimplify.o tree-nomudflap.o tree-pretty-print.o \
tree-alias-common.o tree-ssa-ccp.o tree-browser.o @ANDER@ tree-ssa-dce.o \
tree-ssa-pre.o tree-ssa-copyprop.o tree-ssa-live.o tree-must-alias.o \
+ tree-ssa-dom.o \
alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o \
cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o \
cfgloopanal.o cfgloopmanip.o loop-init.o loop-unswitch.o loop-unroll.o \
*************** tree-ssa.o : tree-ssa.c $(TREE_FLOW_H) $
*** 1516,1521 ****
--- 1517,1525 ----
ssa.h errors.h toplev.h function.h $(TIMEVAR_H) tree-alias-common.h \
$(TM_H) coretypes.h $(TREE_DUMP_H) tree-ssa-live.h langhooks.h \
cfgloop.h
+ tree-ssa-dom.o : tree-ssa-dom.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
+ $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) output.h diagnostic.h \
+ errors.h function.h $(TIMEVAR_H) $(TM_H) coretypes.h
tree-ssa-live.o : tree-ssa-live.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) output.h diagnostic.h \
ssa.h errors.h toplev.h function.h $(TIMEVAR_H) tree-alias-common.h \
*************** lcm.o : lcm.c $(CONFIG_H) $(SYSTEM_H) co
*** 1715,1721 ****
$(BASIC_BLOCK_H) $(TM_P_H) df.h function.h
ssa.o : ssa.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(REGS_H)
varray.h \
$(EXPR_H) hard-reg-set.h flags.h function.h real.h insn-config.h
$(RECOG_H) \
! $(BASIC_BLOCK_H) output.h ssa.h tree-flow.h $(TIMEVAR_H)
ssa-dce.o : ssa-dce.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H)
hard-reg-set.h \
$(BASIC_BLOCK_H) ssa.h insn-config.h $(RECOG_H) output.h
tree-ssa-dce.o : tree-ssa-dce.c $(CONFIG_H) system.h errors.h $(TREE_H) \
--- 1719,1725 ----
$(BASIC_BLOCK_H) $(TM_P_H) df.h function.h
ssa.o : ssa.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(REGS_H)
varray.h \
$(EXPR_H) hard-reg-set.h flags.h function.h real.h insn-config.h
$(RECOG_H) \
! $(BASIC_BLOCK_H) output.h ssa.h $(TREE_FLOW_H) $(TIMEVAR_H)
ssa-dce.o : ssa-dce.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H)
hard-reg-set.h \
$(BASIC_BLOCK_H) ssa.h insn-config.h $(RECOG_H) output.h
tree-ssa-dce.o : tree-ssa-dce.c $(CONFIG_H) system.h errors.h $(TREE_H) \
*************** cfg.o : cfg.c $(CONFIG_H) $(SYSTEM_H) co
*** 1760,1766 ****
$(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \
function.h except.h $(GGC_H) $(TM_P_H) alloc-pool.h
cfghooks.o: cfghooks.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H)
$(TREE_H) \
! $(BASIC_BLOCK_H) tree-flow.h cfglayout.h
cfgrtl.o : cfgrtl.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H)
flags.h \
insn-config.h $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h
$(RECOG_H) \
function.h except.h $(GGC_H) $(TM_P_H) insn-config.h
--- 1764,1770 ----
$(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \
function.h except.h $(GGC_H) $(TM_P_H) alloc-pool.h
cfghooks.o: cfghooks.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H)
$(TREE_H) \
! $(BASIC_BLOCK_H) $(TREE_FLOW_H) cfglayout.h
cfgrtl.o : cfgrtl.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H)
flags.h \
insn-config.h $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h
$(RECOG_H) \
function.h except.h $(GGC_H) $(TM_P_H) insn-config.h
Index: timevar.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/timevar.def,v
retrieving revision 1.14.2.15
diff -c -3 -p -r1.14.2.15 timevar.def
*** timevar.def 14 Jul 2003 21:18:47 -0000 1.14.2.15
--- timevar.def 15 Jul 2003 18:49:29 -0000
*************** DEFTIMEVAR (TV_TREE_MUST_ALIAS , "
*** 66,77 ****
DEFTIMEVAR (TV_TREE_INSERT_PHI_NODES , "tree PHI insertion")
DEFTIMEVAR (TV_TREE_SSA_REWRITE_BLOCKS, "tree SSA rewrite")
DEFTIMEVAR (TV_TREE_SSA_OTHER , "tree SSA other")
- DEFTIMEVAR (TV_TREE_SSA_TO_NORMAL , "tree SSA to normal")
DEFTIMEVAR (TV_TREE_DFA , "tree dataflow analysis")
DEFTIMEVAR (TV_TREE_CCP , "tree CCP")
DEFTIMEVAR (TV_TREE_PRE , "tree PRE")
DEFTIMEVAR (TV_TREE_COPYPROP , "tree COPYPROP")
DEFTIMEVAR (TV_TREE_DCE , "tree DCE")
DEFTIMEVAR (TV_DOM_FRONTIERS , "dominance frontiers")
DEFTIMEVAR (TV_OVERLOAD , "overload resolution")
DEFTIMEVAR (TV_TEMPLATE_INSTANTIATION, "template instantiation")
--- 66,78 ----
DEFTIMEVAR (TV_TREE_INSERT_PHI_NODES , "tree PHI insertion")
DEFTIMEVAR (TV_TREE_SSA_REWRITE_BLOCKS, "tree SSA rewrite")
DEFTIMEVAR (TV_TREE_SSA_OTHER , "tree SSA other")
DEFTIMEVAR (TV_TREE_DFA , "tree dataflow analysis")
+ DEFTIMEVAR (TV_TREE_SSA_DOMINATOR_OPTS , "dominator optimization")
DEFTIMEVAR (TV_TREE_CCP , "tree CCP")
DEFTIMEVAR (TV_TREE_PRE , "tree PRE")
DEFTIMEVAR (TV_TREE_COPYPROP , "tree COPYPROP")
DEFTIMEVAR (TV_TREE_DCE , "tree DCE")
+ DEFTIMEVAR (TV_TREE_SSA_TO_NORMAL , "tree SSA to normal")
DEFTIMEVAR (TV_DOM_FRONTIERS , "dominance frontiers")
DEFTIMEVAR (TV_OVERLOAD , "overload resolution")
DEFTIMEVAR (TV_TEMPLATE_INSTANTIATION, "template instantiation")
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.129
diff -c -3 -p -r1.1.4.129 tree-dfa.c
*** tree-dfa.c 15 Jul 2003 16:15:24 -0000 1.1.4.129
--- tree-dfa.c 15 Jul 2003 18:49:32 -0000
*************** add_stmt_operand (tree *var_p, tree stmt
*** 593,609 ****
v_ann = var_ann (TREE_CODE (var) == SSA_NAME ? SSA_NAME_VAR (var) : var);
! /* FIXME: Currently, global and local static variables are always treated
as
! virtual operands. Otherwise, we would have to insert copy-in/copy-out
! operations at escape points in the function (e.g., at call sites and
! return points). The additional overhead of inserting these copies may
! negate the optimizations enabled by renaming globals. */
if (decl_function_context (!DECL_P (var) ? get_base_symbol (var) : var) ==
0
|| TREE_STATIC ((!DECL_P (var) ? get_base_symbol (var) : var)))
! {
! flags |= opf_force_vop;
! s_ann->has_volatile_ops = 1;
! }
/* If the variable is an alias tag, it means that its address has been
taken and it's being accessed directly and via pointers. To avoid
--- 593,603 ----
v_ann = var_ann (TREE_CODE (var) == SSA_NAME ? SSA_NAME_VAR (var) : var);
! /* FIXME: Currently, objects in static storage are always treated as
! virtual operands. */
if (decl_function_context (!DECL_P (var) ? get_base_symbol (var) : var) ==
0
|| TREE_STATIC ((!DECL_P (var) ? get_base_symbol (var) : var)))
! flags |= opf_force_vop;
/* If the variable is an alias tag, it means that its address has been
taken and it's being accessed directly and via pointers. To avoid
*************** add_referenced_var (tree var, struct wal
*** 2269,2274 ****
--- 2263,2273 ----
&& (TREE_CODE (var) == PARM_DECL
|| decl_function_context (var) == NULL_TREE))
v_ann->may_point_to_global_mem = 1;
+
+ /* Mark local statics and global variables as global memory aliases
+ to avoid DCE killing seemingly dead stores to them. */
+ if (decl_function_context (var) == 0 || TREE_STATIC (var))
+ v_ann->may_alias_global_mem = 1;
is_addressable = TREE_ADDRESSABLE (var)
|| decl_function_context (var) == NULL;
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.91
diff -c -3 -p -r1.1.4.91 tree-flow.h
*** tree-flow.h 15 Jul 2003 16:15:24 -0000 1.1.4.91
--- tree-flow.h 15 Jul 2003 18:49:34 -0000
*************** extern void set_is_used (tree);
*** 465,475 ****
/* In tree-ssa-pre.c */
extern void tree_perform_ssapre (tree);
-
/* In tree-ssa-ccp.c */
void tree_ssa_ccp (tree);
void fold_stmt (tree);
/* In tree-ssa-dce.c */
void tree_ssa_dce (tree);
--- 465,478 ----
/* In tree-ssa-pre.c */
extern void tree_perform_ssapre (tree);
/* In tree-ssa-ccp.c */
void tree_ssa_ccp (tree);
void fold_stmt (tree);
+ /* In tree-ssa-dom.c */
+ extern bool tree_ssa_dominator_optimize (FILE *, int);
+ extern void dump_dominator_optimization_stats (FILE *);
+ extern void debug_dominator_optimization_stats (void);
/* In tree-ssa-dce.c */
void tree_ssa_dce (tree);
Index: tree-ssa-dom.c
===================================================================
RCS file: tree-ssa-dom.c
diff -N tree-ssa-dom.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- tree-ssa-dom.c 15 Jul 2003 18:49:37 -0000
***************
*** 0 ****
--- 1,686 ----
+ /* SSA Dominator optimizations for trees
+ Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc.
+ Contributed by Diego Novillo <dnovillo@redhat.com>
+
+ This file is part of GCC.
+
+ GCC is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2, or (at your option)
+ any later version.
+
+ GCC is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING. If not, write to
+ the Free Software Foundation, 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA. */
+
+ #include "config.h"
+ #include "system.h"
+ #include "coretypes.h"
+ #include "tm.h"
+ #include "tree.h"
+ #include "flags.h"
+ #include "rtl.h"
+ #include "tm_p.h"
+ #include "ggc.h"
+ #include "basic-block.h"
+ #include "output.h"
+ #include "errors.h"
+ #include "expr.h"
+ #include "function.h"
+ #include "diagnostic.h"
+ #include "tree-flow.h"
+
+ /* This file implements optimizations on the dominator tree. */
+
+ /* Dump file and flags. */
+ static FILE *dump_file;
+ static int dump_flags;
+
+ /* Structure to map variables to values. It's used to keep track of the
+ available constants and copies. */
+ struct var_value_d
+ {
+ tree var;
+ tree value;
+ };
+
+ /* Hash table with expressions made available during the renaming process.
+ When an assignment of the form X_i = EXPR is found, the statement is
+ stored in this table. If the same expression EXPR is later found on the
+ RHS of another statement, it is replaced with X_i (thus performing
+ global redundancy elimination). */
+ static htab_t avail_exprs;
+
+ /* Hash table of constant values and copies indexed by SSA name. When the
+ renaming pass finds an assignment of a constant (X_i = C) or a copy
+ assignment from another SSA variable (X_i = Y_j), it creates a mapping
+ between X_i and the RHS in this table. This mapping is used later on,
+ when renaming uses of X_i. If an assignment to X_i is found in this
+ table, instead of using X_i, we use the RHS of the statement stored in
+ this table (thus performing very simplistic copy and constant
+ propagation). */
+ static htab_t const_and_copies;
+
+ /* Statistics for dominator optimizations. */
+ struct opt_stats_d
+ {
+ long num_stmts;
+ long num_exprs_considered;
+ long num_const_prop;
+ long num_copy_prop;
+ long num_re;
+ };
+
+ static struct opt_stats_d opt_stats;
+ static bool addr_expr_propagated_p;
+
+ /* Local functions. */
+ static void optimize_block (basic_block, tree);
+ static void optimize_stmt (block_stmt_iterator, varray_type *);
+ static tree get_value_for (tree, htab_t);
+ static void set_value_for (tree, tree, htab_t);
+ static hashval_t var_value_hash (const void *);
+ static int var_value_eq (const void *, const void *);
+ static tree lookup_avail_expr (tree, varray_type *, htab_t);
+ static tree get_eq_expr_value (tree);
+ static hashval_t avail_expr_hash (const void *);
+ static int avail_expr_eq (const void *, const void *);
+ static void htab_statistics (FILE *, htab_t);
+
+ /* Optimize the current function based on the dominator tree. This does
+ simple const/copy propagation and redundant expression elimination using
+ value numbering.
+
+ The const/copy propagation may propagate ADDR_EXPRs to pointer use
+ sites. If that occurrs, then we have new variables to expose to the
+ SSA renamer and optimizer. So return nonzero if we propagate any
+ ADDR_EXPRs to their pointer use sites. */
+
+ bool
+ tree_ssa_dominator_optimize (FILE *file, int flags)
+ {
+ /* Set up debugging dump files. */
+ dump_file = file;
+ dump_flags = flags;
+
+ /* Create our hash tables. */
+ const_and_copies = htab_create (1024, var_value_hash, var_value_eq, free);
+ avail_exprs = htab_create (1024, avail_expr_hash, avail_expr_eq, NULL);
+
+ /* Indicate that we have not propagated any ADDR_EXPRs. */
+ addr_expr_propagated_p = false;
+
+ /* Now optimize the dominator tree. */
+ optimize_block (ENTRY_BLOCK_PTR, NULL);
+
+ htab_delete (const_and_copies);
+ htab_delete (avail_exprs);
+ const_and_copies = NULL;
+ avail_exprs = NULL;
+
+ /* Debugging dumps. */
+ if (dump_file)
+ {
+ if (dump_flags & TDF_STATS)
+ dump_dominator_optimization_stats (dump_file);
+ }
+
+
+ return addr_expr_propagated_p;
+ }
+
+ /* Perform a depth-first traversal of the dominator tree looking for
+ redundant expressions and copy/constant propagation opportunities.
+
+ Expressions computed by each statement are looked up in the
+ AVAIL_EXPRS table. If a statement is found to make a redundant
+ computation, it is marked for removal. Otherwise, the expression
+ computed by the statement is assigned a value number and entered
+ into the AVAIL_EXPRS table. See optimize_stmt for details on the
+ types of redundancies handled during renaming.
+
+ Once we've optimized the statements in this block we recursively
+ optimize every dominator child of this block.
+
+ Finally, remove all the expressions added to the AVAIL_EXPRS
+ table during renaming. This is because the expressions made
+ available to block BB and its dominator children are not valid for
+ blocks above BB in the dominator tree.
+
+ EQ_EXPR_VALUE is an assignment expression created when BB's immediate
+ dominator ends in a COND_EXPR statement whose predicate is of the form
+ 'VAR == VALUE', where VALUE may be another variable or a constant.
+ This is used to propagate VALUE on the THEN_CLAUSE of that conditional.
+ This assignment is inserted in CONST_AND_COPIES so that the copy and
+ constant propagator can find more propagation opportunities. */
+
+ static void
+ optimize_block (basic_block bb, tree eq_expr_value)
+ {
+ varray_type block_avail_exprs;
+ bitmap children;
+ unsigned long i;
+ block_stmt_iterator si;
+ tree prev_value = NULL_TREE;
+
+ /* Initialize the local stacks.
+
+ BLOCK_AVAIL_EXPRS stores all the expressions made available in this
+ block. Since expressions made available in this block are only valid
+ in blocks dominated by BB, when we finish rewriting BB and its
+ dominator children, we have to remove these expressions from the
+ AVAIL_EXPRS table. This stack is used to know which expressions
+ to remove from the table. */
+ VARRAY_TREE_INIT (block_avail_exprs, 20, "block_avail_exprs");
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
+
+ /* If EQ_EXPR_VALUE (VAR == VALUE) is given, register the VALUE as a
+ new value for VAR, so that occurrences of VAR can be replaced with
+ VALUE while re-writing the THEN arm of a COND_EXPR. */
+ if (eq_expr_value)
+ {
+ prev_value = get_value_for (TREE_OPERAND (eq_expr_value, 0),
+ const_and_copies);
+ set_value_for (TREE_OPERAND (eq_expr_value, 0),
+ TREE_OPERAND (eq_expr_value, 1),
+ const_and_copies);
+ }
+
+ /* Optimize each statement within the basic block. */
+ for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
+ optimize_stmt (si, &block_avail_exprs);
+
+ /* Recursively optimize the dominator children of BB. */
+ children = dom_children (bb);
+ if (children)
+ {
+ if (bb->flags & BB_CONTROL_EXPR)
+ {
+ tree last = last_stmt (bb);
+ EXECUTE_IF_SET_IN_BITMAP (children, 0, i,
+ {
+ if (BASIC_BLOCK (i)->pred->flags & EDGE_TRUE_VALUE)
+ optimize_block (BASIC_BLOCK (i), get_eq_expr_value (last));
+ else
+ optimize_block (BASIC_BLOCK (i), NULL_TREE);
+ });
+ }
+ else
+ {
+ EXECUTE_IF_SET_IN_BITMAP (children, 0, i,
+ optimize_block (BASIC_BLOCK (i), NULL_TREE));
+ }
+ }
+
+ /* Remove all the expressions made available in this block. */
+ while (VARRAY_ACTIVE_SIZE (block_avail_exprs) > 0)
+ {
+ tree stmt = VARRAY_TOP_TREE (block_avail_exprs);
+ VARRAY_POP (block_avail_exprs);
+ htab_remove_elt (avail_exprs, stmt);
+ }
+
+ /* Also remove equivalences created by EQ_EXPR_VALUE. */
+ if (eq_expr_value)
+ {
+ struct var_value_d vm;
+ vm.var = TREE_OPERAND (eq_expr_value, 0);
+ if (prev_value)
+ set_value_for (vm.var, prev_value, const_and_copies);
+ else
+ htab_remove_elt (const_and_copies, &vm);
+ }
+ }
+
+ /* Dump SSA statistics on FILE. */
+
+ void
+ dump_dominator_optimization_stats (FILE *file)
+ {
+ long n_exprs;
+
+ fprintf (file, "Total number of statements: %6ld\n\n",
+ opt_stats.num_stmts);
+ fprintf (file, "Exprs considered for dominator optimizations: %6ld\n",
+ opt_stats.num_exprs_considered);
+
+ n_exprs = opt_stats.num_exprs_considered;
+ if (n_exprs == 0)
+ n_exprs = 1;
+
+ fprintf (file, " Constants propagated: %6ld
(%.0f%%)\n",
+ opt_stats.num_const_prop, PERCENT (opt_stats.num_const_prop,
+ n_exprs));
+ fprintf (file, " Copies propagated: %6ld
(%.0f%%)\n",
+ opt_stats.num_copy_prop, PERCENT (opt_stats.num_copy_prop,
+ n_exprs));
+ fprintf (file, " Redundant expressions eliminated: %6ld
(%.0f%%)\n",
+ opt_stats.num_re, PERCENT (opt_stats.num_re,
+ n_exprs));
+
+ fprintf (file, "\nHash table statistics:\n");
+
+ fprintf (file, " avail_exprs: ");
+ htab_statistics (file, avail_exprs);
+
+ fprintf (file, " const_and_copies: ");
+ htab_statistics (file, const_and_copies);
+
+ fprintf (file, "\n");
+ }
+
+
+ /* Dump SSA statistics on stderr. */
+
+ void
+ debug_dominator_optimization_stats (void)
+ {
+ dump_dominator_optimization_stats (stderr);
+ }
+
+
+ /* Dump statistics for the hash table HTAB. */
+
+ static void
+ htab_statistics (FILE *file, htab_t htab)
+ {
+ fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
+ (long) htab_size (htab),
+ (long) htab_elements (htab),
+ htab_collisions (htab));
+ }
+
+
+ /* Optimize the statement pointed by iterator SI into SSA form.
+
+ BLOCK_AVAIL_EXPRS_P points to a stack with all the expressions that have
+ been computed in this block and are available in children blocks to
+ be reused.
+
+ We try to perform some simplistic global redundancy elimination and
+ constant propagation:
+
+ 1- To detect global redundancy, we keep track of expressions that have
+ been computed in this block and its dominators. If we find that the
+ same expression is computed more than once, we eliminate repeated
+ computations by using the target of the first one.
+
+ 2- Constant values and copy assignments. This is used to do very
+ simplistic constant and copy propagation. When a constant or copy
+ assignment is found, we map the value on the RHS of the assignment to
+ the variable in the LHS in the CONST_AND_COPIES table. */
+
+ static void
+ optimize_stmt (block_stmt_iterator si, varray_type *block_avail_exprs_p)
+ {
+ size_t i;
+ stmt_ann_t ann;
+ tree stmt, *def_p;
+ varray_type uses, vuses, vdefs;
+ bool may_optimize_p;
+
+ stmt = bsi_stmt (si);
+ if (IS_EMPTY_STMT (stmt))
+ return;
+
+ ann = stmt_ann (stmt);
+ opt_stats.num_stmts++;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Optimizing statement ");
+ print_generic_stmt (dump_file, stmt, TDF_SLIM);
+ fprintf (dump_file, "\n");
+ }
+
+ def_p = def_op (stmt);
+ uses = use_ops (stmt);
+ vuses = vuse_ops (stmt);
+ vdefs = vdef_ops (stmt);
+
+ #if defined ENABLE_CHECKING
+ /* Only assignments may make a new definition. */
+ if (def_p && TREE_CODE (stmt) != MODIFY_EXPR)
+ abort ();
+ #endif
+
+ /* Const/copy propagate into USES. */
+ for (i = 0; uses && i < VARRAY_ACTIVE_SIZE (uses); i++)
+ {
+ tree val;
+ tree *op_p = (tree *) VARRAY_GENERIC_PTR (uses, i);
+
+ /* If the operand has a known constant value or it is known to be a
+ copy of some other variable, use the value or copy stored in
+ CONST_AND_COPIES. */
+ opt_stats.num_exprs_considered++;
+ val = get_value_for (*op_p, const_and_copies);
+ if (val)
+ {
+ /* Gather statistics. */
+ if (is_unchanging_value (val)
+ || is_optimizable_addr_expr (val))
+ opt_stats.num_const_prop++;
+ else
+ opt_stats.num_copy_prop++;
+
+ /* Replace the operand with its known constant value or copy. */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " Replaced '");
+ print_generic_expr (dump_file, *op_p, 0);
+ fprintf (dump_file, "' with %s '",
+ TREE_CODE (val) == SSA_NAME ? "constant" : "variable");
+ print_generic_expr (dump_file, val, 0);
+ fprintf (dump_file, "'\n");
+ }
+
+ /* If VAL is an ADDR_EXPR, notify that we may need to have a
+ second SSA pass to rename variables exposed by the folding of
+ *&VAR expressions. */
+ if (TREE_CODE (val) == ADDR_EXPR)
+ addr_expr_propagated_p = true;
+
+ if (TREE_CODE (val) == SSA_NAME)
+ propagate_copy (op_p, val);
+ else
+ *op_p = val;
+
+ ann->modified = 1;
+ }
+ }
+
+ /* If the statement has been modified with constant replacements,
+ fold its RHS before checking for redundant computations. */
+ if (ann->modified)
+ fold_stmt (stmt);
+
+ /* Check for redundant computations. Do this optimization only
+ for assignments that make no calls and have no aliased stores
+ nor volatile references and no side effects (i.e., no VDEFs). */
+ may_optimize_p = !ann->makes_aliased_stores
+ && !ann->has_volatile_ops
+ && vdefs == NULL
+ && def_p
+ && ! TREE_SIDE_EFFECTS (TREE_OPERAND (stmt, 1));
+
+ if (may_optimize_p)
+ {
+ /* Check if the RHS of the assignment has been computed before. If
+ so, use the LHS of the previously computed statement as the
+ reaching definition for the variable defined by this statement. */
+ tree cached_lhs = lookup_avail_expr (stmt,
+ block_avail_exprs_p,
+ const_and_copies);
+ opt_stats.num_exprs_considered++;
+ if (cached_lhs && TREE_TYPE (cached_lhs) == TREE_TYPE (*def_p))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " Replaced redundant expr '");
+ print_generic_expr (dump_file, TREE_OPERAND (stmt, 1), 0);
+ fprintf (dump_file, "' with '");
+ print_generic_expr (dump_file, cached_lhs, 0);
+ fprintf (dump_file, "'\n");
+ }
+
+ opt_stats.num_re++;
+ TREE_OPERAND (stmt, 1) = cached_lhs;
+ ann->modified = 1;
+ }
+ }
+
+ /* If the RHS of an assignment is a constant or another variable that
+ may be propagated, register it in the CONST_AND_COPIES table. */
+ if (def_p)
+ {
+ tree rhs;
+
+ rhs = TREE_OPERAND (stmt, 1);
+ if (may_optimize_p)
+ {
+ if (TREE_CODE (rhs) == SSA_NAME
+ || is_unchanging_value (rhs)
+ || is_optimizable_addr_expr (rhs))
+ set_value_for (*def_p, rhs, const_and_copies);
+ }
+ }
+ }
+
+ /* Hashing and equality functions for VAR_VALUE_D. */
+
+ static hashval_t
+ var_value_hash (const void *p)
+ {
+ return htab_hash_pointer
+ ((const void *)((const struct var_value_d *)p)->var);
+ }
+
+ static int
+ var_value_eq (const void *p1, const void *p2)
+ {
+ return ((const struct var_value_d *)p1)->var
+ == ((const struct var_value_d *)p2)->var;
+ }
+
+ /* Return the value associated with variable VAR in TABLE. */
+
+ static tree
+ get_value_for (tree var, htab_t table)
+ {
+ struct var_value_d *vm_p, vm;
+
+ #if defined ENABLE_CHECKING
+ if (!SSA_VAR_P (var))
+ abort ();
+ #endif
+
+ vm.var = var;
+ vm_p = (struct var_value_d *) htab_find (table, (void *) &vm);
+ return (vm_p) ? vm_p->value : NULL_TREE;
+ }
+
+
+ /* Associate VALUE to variable VAR in TABLE. */
+
+ static void
+ set_value_for (tree var, tree value, htab_t table)
+ {
+ struct var_value_d *vm_p, vm;
+ void **slot;
+
+ #if defined ENABLE_CHECKING
+ if (!SSA_VAR_P (var))
+ abort ();
+ #endif
+
+ vm.var = var;
+ slot = htab_find_slot (table, (void *) &vm, INSERT);
+ if (*slot == NULL)
+ {
+ vm_p = xmalloc (sizeof *vm_p);
+ vm_p->var = var;
+ *slot = (void *) vm_p;
+ }
+ else
+ vm_p = (struct var_value_d *) *slot;
+
+ vm_p->value = value;
+ }
+
+
+ /* Search for an existing instance of STMT in the AVAIL_EXPRS table. If
+ found, return its LHS. Otherwise insert STMT in the table and return
+ NULL_TREE.
+
+ Also, when an expression is first inserted in the AVAIL_EXPRS table, it
+ is also added to the stack pointed by BLOCK_AVAIL_EXPRS_P, so that they
+ can be removed when we finish processing this block and its children.
+
+ NOTE: This function assumes that STMT is a MODIFY_EXPR node that
+ contains no CALL_EXPR on its RHS and makes no volatile nor
+ aliased references. */
+
+ static tree
+ lookup_avail_expr (tree stmt,
+ varray_type *block_avail_exprs_p,
+ htab_t const_and_copies)
+ {
+ void **slot;
+ tree rhs;
+ tree lhs;
+ tree temp;
+
+ /* Don't bother remembering constant assignments and copy operations.
+ Constants and copy operations are handled by the constant/copy
propagator
+ in optimize_stmt. */
+ rhs = TREE_OPERAND (stmt, 1);
+ if (TREE_CODE (rhs) == SSA_NAME
+ || is_unchanging_value (rhs)
+ || is_optimizable_addr_expr (rhs))
+ return NULL_TREE;
+
+ slot = htab_find_slot (avail_exprs, stmt, INSERT);
+ if (*slot == NULL)
+ {
+ *slot = (void *) stmt;
+ VARRAY_PUSH_TREE (*block_avail_exprs_p, stmt);
+ return NULL_TREE;
+ }
+
+ /* Extract the LHS of the assignment so that it can be used as the current
+ definition of another variable. */
+ lhs = TREE_OPERAND ((tree) *slot, 0);
+
+ /* See if the LHS appears in the const_and_copies table. If it does, then
+ use the value from the const_and_copies table. */
+ temp = get_value_for (lhs, const_and_copies);
+ if (temp)
+ lhs = temp;
+
+ return lhs;
+ }
+
+
+ /* Given a conditional statement IF_STMT, return the assignment 'X = Y', if
+ the conditional is of the form 'X == Y'. If the conditional is of the
+ form 'X'. The assignment 'X = 1' is returned. */
+
+ static tree
+ get_eq_expr_value (tree if_stmt)
+ {
+ tree cond, value;
+
+ cond = COND_EXPR_COND (if_stmt);
+
+ /* If the conditional is a single variable 'X', return 'X = 1'. */
+ if (SSA_VAR_P (cond))
+ return build (MODIFY_EXPR, TREE_TYPE (cond), cond, integer_one_node);
+
+ /* If the conditional is of the form 'X == Y', return 'X = Y'. */
+ else if (TREE_CODE (cond) == EQ_EXPR
+ && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
+ && (is_unchanging_value (TREE_OPERAND (cond, 1))
+ || is_optimizable_addr_expr (TREE_OPERAND (cond, 1))
+ || TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME))
+ value = build (MODIFY_EXPR, TREE_TYPE (cond),
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1));
+
+ /* Return nothing for any other conditional. */
+ else
+ value = NULL_TREE;
+
+ return value;
+ }
+
+
+ /* Hashing and equality functions for AVAIL_EXPRS. The table stores
+ MODIFY_EXPR statements. We compute a value number for expressions using
+ the code of the expression and the SSA numbers of its operands. */
+
+ static hashval_t
+ avail_expr_hash (const void *p)
+ {
+ hashval_t val = 0;
+ tree rhs;
+ size_t i;
+ varray_type ops;
+ tree stmt = (tree) p;
+
+ /* iterative_hash_expr knows how to deal with any expression and
+ deals with commutative operators as well, so just use it instead
+ of duplicating such complexities here. */
+ rhs = TREE_OPERAND (stmt, 1);
+ val = iterative_hash_expr (rhs, val);
+
+ /* Add the SSA version numbers of every vuse operand. This is important
+ because compound variables like arrays are not renamed in the
+ operands. Rather, the rename is done on the virtual variable
+ representing all the elements of the array. */
+ ops = vuse_ops (stmt);
+ for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
+ val = iterative_hash_expr (VARRAY_TREE (ops, i), val);
+
+ return val;
+ }
+
+
+ static int
+ avail_expr_eq (const void *p1, const void *p2)
+ {
+ tree s1, s2, rhs1, rhs2;
+
+ s1 = (tree) p1;
+ rhs1 = TREE_OPERAND (s1, 1);
+
+ s2 = (tree) p2;
+ rhs2 = TREE_OPERAND (s2, 1);
+
+ /* If they are the same physical statement, return true. */
+ if (s1 == s2)
+ return true;
+
+ /* In case of a collision, both RHS have to be identical and have the
+ same VUSE operands. */
+ if (TREE_CODE (rhs1) == TREE_CODE (rhs2)
+ && TREE_TYPE (rhs1) == TREE_TYPE (rhs2)
+ && operand_equal_p (rhs1, rhs2, 0))
+ {
+ varray_type ops1 = vuse_ops (s1);
+ varray_type ops2 = vuse_ops (s2);
+
+ if (ops1 == NULL && ops2 == NULL)
+ {
+ #ifdef ENABLE_CHECKING
+ if (avail_expr_hash (s1) != avail_expr_hash (s2))
+ abort ();
+ #endif
+ return true;
+ }
+
+ if (VARRAY_ACTIVE_SIZE (ops1) == VARRAY_ACTIVE_SIZE (ops2))
+ {
+ size_t i;
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (ops1); i++)
+ if (VARRAY_GENERIC_PTR (ops1, i) != VARRAY_GENERIC_PTR (ops2, i))
+ return false;
+
+ #ifdef ENABLE_CHECKING
+ if (avail_expr_hash (s1) != avail_expr_hash (s2))
+ abort ();
+ #endif
+ return true;
+ }
+ }
+
+ return false;
+ }
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.102
diff -c -3 -p -r1.1.4.102 tree-ssa.c
*** tree-ssa.c 15 Jul 2003 16:15:24 -0000 1.1.4.102
--- tree-ssa.c 15 Jul 2003 18:49:39 -0000
***************
*** 1,5 ****
/* SSA for trees.
! Copyright (C) 2001, 2002 Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>
This file is part of GCC.
--- 1,5 ----
/* SSA for trees.
! Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>
This file is part of GCC.
*************** struct var_value_d
*** 99,121 ****
tree value;
};
- /* Hash table with expressions made available during the renaming process.
- When an assignment of the form X_i = EXPR is found, the statement is
- stored in this table. If the same expression EXPR is later found on the
- RHS of another statement, it is replaced with X_i (thus performing
- global redundancy elimination). */
- static htab_t avail_exprs;
-
- /* Hash table of constant values and copies indexed by SSA name. When the
- renaming pass finds an assignment of a constant (X_i = C) or a copy
- assignment from another SSA variable (X_i = Y_j), it creates a mapping
- between X_i and the RHS in this table. This mapping is used later on,
- when renaming uses of X_i. If an assignment to X_i is found in this
- table, instead of using X_i, we use the RHS of the statement stored in
- this table (thus performing very simplistic copy and constant
- propagation). */
- static htab_t const_and_copies;
-
/* Used to hold all the components requires to do SSA PHI elimination. */
typedef struct _elim_graph
--- 99,104 ----
*************** typedef struct _elim_graph
*** 146,155 ****
struct ssa_stats_d
{
long num_stmts;
- long num_exprs_considered;
- long num_const_prop;
- long num_copy_prop;
- long num_re;
};
static struct ssa_stats_d ssa_stats;
--- 129,134 ----
*************** static struct ssa_stats_d ssa_stats;
*** 157,166 ****
/* Bitmap representing variables that need to be renamed into SSA form. */
static sbitmap vars_to_rename;
- /* Flag to indicate whether the dominator optimizations propagated an
- ADDR_EXPR. If that happens, we may need to run another SSA pass because
- new symbols may have been exposed. */
- static bool addr_expr_propagated_p;
/* Local functions. */
static void delete_tree_ssa (tree);
--- 136,141 ----
*************** static void set_def_block (tree, basic_b
*** 170,178 ****
static void set_livein_block (tree, basic_block);
static void insert_phi_nodes (bitmap *, sbitmap);
static void insert_phis_for_deferred_variables (varray_type);
! static void rewrite_block (basic_block, tree);
! static int rewrite_and_optimize_stmt (block_stmt_iterator, varray_type *,
! varray_type *);
static void check_for_new_variables (void);
static void rewrite_stmt (block_stmt_iterator, varray_type *);
static inline void rewrite_operand (tree *, bool);
--- 145,151 ----
static void set_livein_block (tree, basic_block);
static void insert_phi_nodes (bitmap *, sbitmap);
static void insert_phis_for_deferred_variables (varray_type);
! static void rewrite_block (basic_block);
static void check_for_new_variables (void);
static void rewrite_stmt (block_stmt_iterator, varray_type *);
static inline void rewrite_operand (tree *, bool);
*************** static hashval_t var_value_hash (const v
*** 188,197 ****
static int var_value_eq (const void *, const void *);
static void def_blocks_free (void *);
static int debug_def_blocks_r (void **, void *);
- static tree lookup_avail_expr (tree, varray_type *, htab_t);
- static tree get_eq_expr_value (tree);
- static hashval_t avail_expr_hash (const void *);
- static int avail_expr_eq (const void *, const void *);
static struct def_blocks_d *get_def_blocks_for (tree);
static void htab_statistics (FILE *, htab_t);
--- 161,166 ----
*************** rewrite_into_ssa (tree fndecl, sbitmap v
*** 307,312 ****
--- 276,282 ----
dominance_info idom;
int i, rename_count;
bool compute_df;
+ bool addr_expr_propagated_p;
timevar_push (TV_TREE_SSA_OTHER);
*************** rewrite_into_ssa (tree fndecl, sbitmap v
*** 330,341 ****
currdefs = htab_create (VARRAY_ACTIVE_SIZE (referenced_vars),
var_value_hash, var_value_eq, free);
- /* Allocate memory for the AVAIL_EXPRS hash table. */
- avail_exprs = htab_create (1024, avail_expr_hash, avail_expr_eq, NULL);
-
- /* Allocate memory for the CONST_AND_COPIES hash table. */
- const_and_copies = htab_create (1024, var_value_hash, var_value_eq, free);
-
/* Allocate memory for the GLOBALS bitmap which will indicate which
variables are live across basic block boundaries. Note that this
bitmap is indexed by variable UID, so it must always be large enough
--- 300,305 ----
*************** rewrite_into_ssa (tree fndecl, sbitmap v
*** 379,387 ****
/* Rewrite all the basic blocks in the program. */
timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
sbitmap_zero (vars_to_rename);
! rewrite_block (ENTRY_BLOCK_PTR, NULL_TREE);
timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
/* If the dominator optimizations propagated ADDR_EXPRs, we may need
to repeat the SSA renaming process for the new symbols that may
have been exposed. Re-scan the program for operands not in SSA
--- 343,360 ----
/* Rewrite all the basic blocks in the program. */
timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
sbitmap_zero (vars_to_rename);
! rewrite_block (ENTRY_BLOCK_PTR);
timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
+ if (flag_tree_dom)
+ {
+ /* Now optimize all the basic blocks in the program. */
+ timevar_push (TV_TREE_SSA_DOMINATOR_OPTS);
+ addr_expr_propagated_p = tree_ssa_dominator_optimize (dump_file,
+ dump_flags);
+ timevar_pop (TV_TREE_SSA_DOMINATOR_OPTS);
+ }
+
/* If the dominator optimizations propagated ADDR_EXPRs, we may need
to repeat the SSA renaming process for the new symbols that may
have been exposed. Re-scan the program for operands not in SSA
*************** rewrite_into_ssa (tree fndecl, sbitmap v
*** 398,412 ****
remove_all_phi_nodes_for (vars_to_rename);
htab_empty (def_blocks);
htab_empty (currdefs);
- htab_empty (avail_exprs);
- htab_empty (const_and_copies);
sbitmap_zero (globals);
}
}
-
- /* Sanity check, we shouldn't need to iterate more than twice. */
- if (rename_count++ > 1)
- abort ();
}
while (sbitmap_first_set_bit (vars_to_rename) >= 0);
--- 371,379 ----
*************** rewrite_into_ssa (tree fndecl, sbitmap v
*** 418,425 ****
free_dominance_info (idom);
htab_delete (def_blocks);
htab_delete (currdefs);
- htab_delete (avail_exprs);
- htab_delete (const_and_copies);
if (vars == NULL)
sbitmap_free (vars_to_rename);
--- 385,390 ----
*************** compute_global_livein (varray_type def_m
*** 529,536 ****
BITMAP_XFREE (in_worklist);
}
-
-
/* Look for variable references in every block of the flowgraph, compute
aliasing information and collect definition sites for every variable.
--- 494,499 ----
*************** mark_def_sites (dominance_info idom, sbi
*** 658,664 ****
free (kills);
}
-
/* Mark block BB as the definition site for variable VAR. */
static void
--- 621,626 ----
*************** insert_phi_nodes (bitmap *dfs, sbitmap g
*** 771,784 ****
rewritten with their corresponding reaching definition. DEF and
VDEF targets are registered as new definitions.
- This step performs some quick and simple value number optimizations.
- Expressions computed by each statement are looked up in the
- AVAIL_EXPRS table. If a statement is found to make a redundant
- computation, it is marked for removal. Otherwise, the expression
- computed by the statement is assigned a value number and entered into
- the AVAIL_EXPRS table. See try_optimize_stmt for details on the
- types of redundancies handled during renaming.
-
3- All the PHI nodes in successor blocks of BB are visited. The
argument corresponding to BB is replaced with its current reaching
definition.
--- 733,738 ----
*************** insert_phi_nodes (bitmap *dfs, sbitmap g
*** 789,853 ****
new definition introduced in this block. This is done so that when
we return from the recursive call, all the current reaching
definitions are restored to the names that were valid in the
! dominator parent of BB.
!
! This step also removes all the expressions added to the AVAIL_EXPRS
! table during renaming. This is because the expressions made
! available to block BB and its dominator children are not valid for
! blocks above BB in the dominator tree.
!
! EQ_EXPR_VALUE is an assignment expression created when BB's immediate
! dominator ends in a COND_EXPR statement whose predicate is of the form
! 'VAR == VALUE', where VALUE may be another variable or a constant.
! This is used to propagate VALUE on the THEN_CLAUSE of that conditional.
! This assignment is inserted in CONST_AND_COPIES so that the copy and
! constant propagator can find more propagation opportunities. */
static void
! rewrite_block (basic_block bb, tree eq_expr_value)
{
edge e;
! varray_type block_defs, block_avail_exprs;
bitmap children;
unsigned long i;
block_stmt_iterator si;
tree phi;
- tree prev_value = NULL_TREE;
/* Initialize the local stacks.
BLOCK_DEFS is used to save all the existing reaching definitions for
the new SSA names introduced in this block. Before registering a
new definition for a variable, the existing reaching definition is
! pushed into this stack so that we can restore it in Step 5.
- BLOCK_AVAIL_EXPRS is used when -ftree-dominator-opts is given. It
- stores all the expressions made available in this block. Since
- expressions made available in this block are only valid in blocks
- dominated by BB, when we finish rewriting BB and its dominator
- children, we have to remove these expressions from the AVAIL_EXPRS
- table. This stack is used to know which expressions to remove from
- the table. */
VARRAY_TREE_INIT (block_defs, 20, "block_defs");
- if (flag_tree_dom)
- VARRAY_TREE_INIT (block_avail_exprs, 20, "block_avail_exprs");
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
- /* If EQ_EXPR_VALUE (VAR == VALUE) is given and we are doing dominator
- optimizations, register the VALUE as a new value for VAR, so that
- occurrences of VAR can be replaced with VALUE while re-writing the
- THEN arm of a COND_EXPR. */
- if (flag_tree_dom && eq_expr_value)
- {
- prev_value = get_value_for (TREE_OPERAND (eq_expr_value, 0),
- const_and_copies);
- set_value_for (TREE_OPERAND (eq_expr_value, 0),
- TREE_OPERAND (eq_expr_value, 1),
- const_and_copies);
- }
-
/* Step 1. Register new definitions for every PHI node in the block.
Conceptually, all the PHI nodes are executed in parallel and each PHI
node introduces a new version for the associated variable. */
--- 743,772 ----
new definition introduced in this block. This is done so that when
we return from the recursive call, all the current reaching
definitions are restored to the names that were valid in the
! dominator parent of BB. */
static void
! rewrite_block (basic_block bb)
{
edge e;
! varray_type block_defs;
bitmap children;
unsigned long i;
block_stmt_iterator si;
tree phi;
/* Initialize the local stacks.
BLOCK_DEFS is used to save all the existing reaching definitions for
the new SSA names introduced in this block. Before registering a
new definition for a variable, the existing reaching definition is
! pushed into this stack so that we can restore it in Step 5. */
VARRAY_TREE_INIT (block_defs, 20, "block_defs");
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
/* Step 1. Register new definitions for every PHI node in the block.
Conceptually, all the PHI nodes are executed in parallel and each PHI
node introduces a new version for the associated variable. */
*************** rewrite_block (basic_block bb, tree eq_e
*** 857,878 ****
/* Step 2. Rewrite every variable used in each statement the block with
its immediate reaching definitions. Update the current definition of
! a variable when a new real or virtual definition is found. If
! -ftree-dominator-opts is given, call rewrite_and_optimize_stmt,
! otherwise simply rename every operand with rewrite_stmt. */
! if (flag_tree_dom)
! {
! for (si = bsi_start (bb); !bsi_end_p (si); )
! if (!rewrite_and_optimize_stmt (si, &block_defs, &block_avail_exprs))
! bsi_next (&si);
! else
! bsi_remove (&si);
! }
! else
! {
! for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
! rewrite_stmt (si, &block_defs);
! }
/* Step 3. Visit all the successor blocks of BB looking for PHI nodes.
--- 776,784 ----
/* Step 2. Rewrite every variable used in each statement the block with
its immediate reaching definitions. Update the current definition of
! a variable when a new real or virtual definition is found. */
! for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
! rewrite_stmt (si, &block_defs);
/* Step 3. Visit all the successor blocks of BB looking for PHI nodes.
*************** rewrite_block (basic_block bb, tree eq_e
*** 891,898 ****
if (PHI_NUM_ARGS (phi) == PHI_ARG_CAPACITY (phi))
continue;
- /* FIXME. [UNSSA] If -ftree-dominator-opts, allow constants and
- copies to be propagated into PHI arguments. */
currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
add_phi_arg (phi, currdef, e);
}
--- 797,802 ----
*************** rewrite_block (basic_block bb, tree eq_e
*** 901,924 ****
/* Step 4. Recursively search the dominator children of BB. */
children = dom_children (bb);
if (children)
! {
! if (bb->flags & BB_CONTROL_EXPR)
! {
! tree last = last_stmt (bb);
! EXECUTE_IF_SET_IN_BITMAP (children, 0, i,
! {
! if (BASIC_BLOCK (i)->pred->flags & EDGE_TRUE_VALUE)
! rewrite_block (BASIC_BLOCK (i), get_eq_expr_value (last));
! else
! rewrite_block (BASIC_BLOCK (i), NULL_TREE);
! });
! }
! else
! {
! EXECUTE_IF_SET_IN_BITMAP (children, 0, i,
! rewrite_block (BASIC_BLOCK (i), NULL_TREE));
! }
! }
/* Step 5. Restore the current reaching definition for each variable
referenced in the block (in reverse order). */
--- 805,811 ----
/* Step 4. Recursively search the dominator children of BB. */
children = dom_children (bb);
if (children)
! EXECUTE_IF_SET_IN_BITMAP (children, 0, i, rewrite_block (BASIC_BLOCK
(i)));
/* Step 5. Restore the current reaching definition for each variable
referenced in the block (in reverse order). */
*************** rewrite_block (basic_block bb, tree eq_e
*** 940,970 ****
set_value_for (var, saved_def, currdefs);
}
-
- /* If we are doing dominator optimizations, remove all the expressions
- made available in this block. */
- if (flag_tree_dom)
- {
- while (VARRAY_ACTIVE_SIZE (block_avail_exprs) > 0)
- {
- tree stmt = VARRAY_TOP_TREE (block_avail_exprs);
- VARRAY_POP (block_avail_exprs);
- htab_remove_elt (avail_exprs, stmt);
- }
-
- if (eq_expr_value)
- {
- struct var_value_d vm;
- vm.var = TREE_OPERAND (eq_expr_value, 0);
- if (prev_value)
- set_value_for (vm.var, prev_value, const_and_copies);
- else
- htab_remove_elt (const_and_copies, &vm);
- }
- }
}
-
/* This function will create a temporary for a partition based on the
type of the variable which already represents a partition. */
--- 827,834 ----
*************** debug_tree_ssa (void)
*** 1881,1907 ****
void
dump_tree_ssa_stats (FILE *file)
{
- long n_exprs;
-
- fprintf (file, "Total number of statements: %6ld\n\n",
- ssa_stats.num_stmts);
- fprintf (file, "Exprs considered for dominator optimizations: %6ld\n",
- ssa_stats.num_exprs_considered);
-
- n_exprs = ssa_stats.num_exprs_considered;
- if (n_exprs == 0)
- n_exprs = 1;
-
- fprintf (file, " Constants propagated: %6ld
(%.0f%%)\n",
- ssa_stats.num_const_prop, PERCENT (ssa_stats.num_const_prop,
- n_exprs));
- fprintf (file, " Copies propagated: %6ld
(%.0f%%)\n",
- ssa_stats.num_copy_prop, PERCENT (ssa_stats.num_copy_prop,
- n_exprs));
- fprintf (file, " Redundant expressions eliminated: %6ld
(%.0f%%)\n",
- ssa_stats.num_re, PERCENT (ssa_stats.num_re,
- n_exprs));
-
fprintf (file, "\nHash table statistics:\n");
fprintf (file, " def_blocks: ");
--- 1745,1750 ----
*************** dump_tree_ssa_stats (FILE *file)
*** 1910,1921 ****
fprintf (file, " currdefs: ");
htab_statistics (file, currdefs);
- fprintf (file, " avail_exprs: ");
- htab_statistics (file, avail_exprs);
-
- fprintf (file, " const_and_copies: ");
- htab_statistics (file, const_and_copies);
-
fprintf (file, "\n");
}
--- 1753,1758 ----
*************** insert_phi_nodes_for (tree var, bitmap *
*** 2080,2324 ****
BITMAP_XFREE (phi_insertion_points);
}
-
- /* Rewrite the statement pointed by iterator SI into SSA form. Return 1 if
- the stmt is to be deleted.
-
- BLOCK_DEFS_P points to a stack with all the definitions found in the
- block. This is used by rewrite_block to restore the current reaching
- definition for every variable defined in BB after visiting the
- immediate dominators of BB.
-
- BLOCK_AVAIL_EXPRS_P points to a stack with all the expressions that have
- been computed in this block and are available in children blocks to
- be reused.
-
- While renaming a statement, we try to perform some simplistic global
- redundancy elimination and constant propagation:
-
- 1- To detect global redundancy, we keep track of expressions that have
- been computed in this block and its dominators. If we find that the
- same expression is computed more than once, we eliminate repeated
- computations by using the target of the first one. For instance,
- consider this partially renamed fragment of code:
-
- a_1 = b_2 + c_3;
- x = b_2 + c_3;
- if (x > 0)
- ...
-
- After renaming the first instance of 'b_2 + c_3', it will be added to
- the AVAIL_EXPRS table with value 'a_1'. The next time the renaming
- process finds 'b_2 + c_3', instead of creating a new definition for
- 'x', it will set the current reaching definition of 'x' to be 'a_1'.
- This way, the renaming process will proceed to generate:
-
- a_1 = b_2 + c_3;
- <deleted>
- if (a_1 > 0)
- ...
-
-
- 2- Constant values and copy assignments. This is used to do very
- simplistic constant and copy propagation. When a constant or copy
- assignment is found, we map the value on the RHS of the assignment to
- the variable in the LHS in the CONST_AND_COPIES table. The next time
- we need to rewrite an operand, we check whether the variable has a
- known value. If so, we use that value. Notice that this does not
- replace the constant and copy propagation passes. It only does very
- simplistic propagation while renaming. */
-
- static int
- rewrite_and_optimize_stmt (block_stmt_iterator si, varray_type *block_defs_p,
- varray_type *block_avail_exprs_p)
- {
- size_t i;
- stmt_ann_t ann;
- tree stmt, *def_p;
- varray_type uses, vuses, vdefs;
- bool may_optimize_p;
-
- stmt = bsi_stmt (si);
- if (IS_EMPTY_STMT (stmt))
- return 0;
-
- ann = stmt_ann (stmt);
- ssa_stats.num_stmts++;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Renaming statement ");
- print_generic_stmt (dump_file, stmt, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
-
- #if defined ENABLE_CHECKING
- /* We have just scanned the code for operands. No statement should
- be modified. */
- if (ann->modified)
- abort ();
- #endif
-
- /* FIXME: Must change the interface to statement annotations. Helpers
- should receive the annotation, not the statement. Otherwise,
- we call stmt_ann() more than necessary. */
- def_p = def_op (stmt);
- uses = use_ops (stmt);
- vuses = vuse_ops (stmt);
- vdefs = vdef_ops (stmt);
-
- #if defined ENABLE_CHECKING
- /* Only assignments may make a new definition. */
- if (def_p && TREE_CODE (stmt) != MODIFY_EXPR)
- abort ();
- #endif
-
- /* Step 1. Rewrite USES and VUSES in the statement. */
- for (i = 0; uses && i < VARRAY_ACTIVE_SIZE (uses); i++)
- {
- tree val;
- tree *op_p = (tree *) VARRAY_GENERIC_PTR (uses, i);
-
- /* If the operand is already in SSA form, do nothing. */
- if (TREE_CODE (*op_p) == SSA_NAME)
- continue;
-
- rewrite_operand (op_p, true);
-
- /* If the operand has a known constant value or it is known to be a
- copy of some other variable, use the value or copy stored in
- CONST_AND_COPIES. */
- ssa_stats.num_exprs_considered++;
- val = get_value_for (*op_p, const_and_copies);
- if (val)
- {
- /* Gather statistics. */
- if (is_unchanging_value (val)
- || is_optimizable_addr_expr (val))
- ssa_stats.num_const_prop++;
- else
- ssa_stats.num_copy_prop++;
-
- /* Replace the operand with its known constant value or copy. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, " Replaced '");
- print_generic_expr (dump_file, *op_p, 0);
- fprintf (dump_file, "' with %s '",
- TREE_CODE (val) == SSA_NAME ? "variable" : "constant");
- print_generic_expr (dump_file, val, 0);
- fprintf (dump_file, "'\n");
- }
-
- /* If VAL is an ADDR_EXPR, notify that we may need to have a
- second SSA pass to rename variables exposed by the folding of
- *&VAR expressions. */
- if (TREE_CODE (val) == ADDR_EXPR)
- addr_expr_propagated_p = true;
-
- if (TREE_CODE (val) == SSA_NAME)
- propagate_copy (op_p, val);
- else
- *op_p = val;
-
- ann->modified = 1;
- }
- }
-
- /* Rewrite virtual uses in the statement. */
- for (i = 0; vuses && i < VARRAY_ACTIVE_SIZE (vuses); i++)
- if (TREE_CODE (VARRAY_TREE (vuses, i)) != SSA_NAME)
- rewrite_operand (&(VARRAY_TREE (vuses, i)), false);
-
- /* If the statement has been modified with constant replacements,
- fold its RHS before checking for redundant computations. */
- if (ann->modified)
- fold_stmt (stmt);
-
- /* Step 2. Check for redundant computations. Do this optimization only
- for assignments that make no calls and have no aliased stores
- nor volatile references and no side effects (i.e., no VDEFs). */
- may_optimize_p = !ann->makes_aliased_stores
- && !ann->has_volatile_ops
- && vdefs == NULL
- && def_p
- && ! TREE_SIDE_EFFECTS (TREE_OPERAND (stmt, 1));
-
- if (may_optimize_p)
- {
- /* Check if the RHS of the assignment has been computed before. If
- so, use the LHS of the previously computed statement as the
- reaching definition for the variable defined by this statement. */
- tree cached_lhs = lookup_avail_expr (stmt,
- block_avail_exprs_p,
- const_and_copies);
- ssa_stats.num_exprs_considered++;
- if (cached_lhs && TREE_TYPE (cached_lhs) == TREE_TYPE (*def_p))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, " Replaced redundant expr '");
- print_generic_expr (dump_file, TREE_OPERAND (stmt, 1), 0);
- fprintf (dump_file, "' with '");
- print_generic_expr (dump_file, cached_lhs, 0);
- fprintf (dump_file, "'\n");
- }
-
- if (cached_lhs && get_value_for (*def_p, currdefs) == cached_lhs)
- {
- /* A redundant assignment to the same lhs, perhaps a new
- evaluation of an expression temporary that is still live.
- Just discard it. */
- ssa_stats.num_re++;
- return 1;
- }
-
- ssa_stats.num_re++;
- TREE_OPERAND (stmt, 1) = cached_lhs;
- ann->modified = 1;
- }
- }
-
- /* Step 3. If the computation wasn't redundant, register its DEF and
- VDEF operands. Do nothing if the definition is already in SSA form. */
- if (def_p && TREE_CODE (*def_p) != SSA_NAME)
- {
- tree rhs;
-
- *def_p = make_ssa_name (*def_p, stmt);
- register_new_def (SSA_NAME_VAR (*def_p), *def_p, block_defs_p, true);
-
- /* If the RHS of the assignment is a constant or another variable
- that may be propagated, register it in the CONST_AND_COPIES table. */
- rhs = TREE_OPERAND (stmt, 1);
- if (may_optimize_p)
- {
- if (TREE_CODE (rhs) == SSA_NAME
- || is_unchanging_value (rhs)
- || is_optimizable_addr_expr (rhs))
- set_value_for (*def_p, rhs, const_and_copies);
- }
- }
-
- /* Register new virtual definitions made by the statement. */
- for (i = 0; vdefs && i < VARRAY_ACTIVE_SIZE (vdefs); i++)
- {
- tree vdef = VARRAY_TREE (vdefs, i);
-
- if (TREE_CODE (VDEF_RESULT (vdef)) == SSA_NAME)
- continue;
-
- rewrite_operand (&(VDEF_OP (vdef)), false);
-
- VDEF_RESULT (vdef) = make_ssa_name (VDEF_RESULT (vdef), stmt);
- register_new_def (SSA_NAME_VAR (VDEF_RESULT (vdef)),
- VDEF_RESULT (vdef), block_defs_p, false);
- }
-
- return 0;
- }
-
-
/* Scan all the statements looking for symbols not in SSA form. If any are
found, add them to VARS_TO_RENAME to trigger a second SSA pass. */
--- 1917,1922 ----
*************** check_for_new_variables (void)
*** 2373,2386 ****
}
! /* Rewrite statement pointed by iterator SI into SSA form. This is only
! used when not doing dominator optimizations (-ftree-dominator-opts), in
! which case rewrite_and_optimize_stmt is used.
BLOCK_DEFS_P points to a stack with all the definitions found in the
! block. This is used by rewrite_block to restore the current reaching
! definition for every variable defined in BB after visiting the
! immediate dominators of BB. */
static void
rewrite_stmt (block_stmt_iterator si, varray_type *block_defs_p)
--- 1971,1982 ----
}
! /* Rewrite statement pointed by iterator SI into SSA form.
BLOCK_DEFS_P points to a stack with all the definitions found in the
! block. This is used by rewrite_block to restore the current reaching
! definition for every variable defined in BB after visiting the
! immediate dominators of BB. */
static void
rewrite_stmt (block_stmt_iterator si, varray_type *block_defs_p)
*************** set_value_for (tree var, tree value, hta
*** 2736,2911 ****
vm_p->value = value;
}
-
-
- /* Search for an existing instance of STMT in the AVAIL_EXPRS table. If
- found, return its LHS. Otherwise insert STMT in the table and return
- NULL_TREE.
-
- Also, when an expression is first inserted in the AVAIL_EXPRS table, it
- is also added to the stack pointed by BLOCK_AVAIL_EXPRS_P, so that they
- can be removed when we finish processing this block and its children.
-
- NOTE: This function assumes that STMT is a MODIFY_EXPR node that
- contains no CALL_EXPR on its RHS and makes no volatile nor
- aliased references. */
-
- static tree
- lookup_avail_expr (tree stmt,
- varray_type *block_avail_exprs_p,
- htab_t const_and_copies)
- {
- void **slot;
- tree rhs;
- tree lhs;
- tree temp;
-
- /* Don't bother remembering constant assignments and copy operations.
- Constants and copy operations are handled by the constant/copy
propagator
- in rewrite_and_optimize_stmt. */
- rhs = TREE_OPERAND (stmt, 1);
- if (TREE_CODE (rhs) == SSA_NAME
- || is_unchanging_value (rhs)
- || is_optimizable_addr_expr (rhs))
- return NULL_TREE;
-
- slot = htab_find_slot (avail_exprs, stmt, INSERT);
- if (*slot == NULL)
- {
- *slot = (void *) stmt;
- VARRAY_PUSH_TREE (*block_avail_exprs_p, stmt);
- return NULL_TREE;
- }
-
- /* Extract the LHS of the assignment so that it can be used as the current
- definition of another variable. */
- lhs = TREE_OPERAND ((tree) *slot, 0);
-
- /* See if the LHS appears in the const_and_copies table. If it does, then
- use the value from the const_and_copies table. */
- temp = get_value_for (lhs, const_and_copies);
- if (temp)
- lhs = temp;
-
- return lhs;
- }
-
-
- /* Given a conditional statement IF_STMT, return the assignment 'X = Y', if
- the conditional is of the form 'X == Y'. If the conditional is of the
- form 'X'. The assignment 'X = 1' is returned. */
-
- static tree
- get_eq_expr_value (tree if_stmt)
- {
- tree cond, value;
-
- cond = COND_EXPR_COND (if_stmt);
-
- /* If the conditional is a single variable 'X', return 'X = 1'. */
- if (SSA_VAR_P (cond))
- return build (MODIFY_EXPR, TREE_TYPE (cond), cond, integer_one_node);
-
- /* If the conditional is of the form 'X == Y', return 'X = Y'. */
- else if (TREE_CODE (cond) == EQ_EXPR
- && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
- && (is_unchanging_value (TREE_OPERAND (cond, 1))
- || is_optimizable_addr_expr (TREE_OPERAND (cond, 1))
- || TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME))
- value = build (MODIFY_EXPR, TREE_TYPE (cond),
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1));
-
- /* Return nothing for any other conditional. */
- else
- value = NULL_TREE;
-
- return value;
- }
-
-
- /* Hashing and equality functions for AVAIL_EXPRS. The table stores
- MODIFY_EXPR statements. We compute a value number for expressions using
- the code of the expression and the SSA numbers of its operands. */
-
- static hashval_t
- avail_expr_hash (const void *p)
- {
- hashval_t val = 0;
- tree rhs;
- size_t i;
- varray_type ops;
- tree stmt = (tree) p;
-
- /* iterative_hash_expr knows how to deal with any expression and
- deals with commutative operators as well, so just use it instead
- of duplicating such complexities here. */
- rhs = TREE_OPERAND (stmt, 1);
- val = iterative_hash_expr (rhs, val);
-
- /* Add the SSA version numbers of every vuse operand. This is important
- because compound variables like arrays are not renamed in the
- operands. Rather, the rename is done on the virtual variable
- representing all the elements of the array. */
- ops = vuse_ops (stmt);
- for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
- val = iterative_hash_expr (VARRAY_TREE (ops, i), val);
-
- return val;
- }
-
-
- static int
- avail_expr_eq (const void *p1, const void *p2)
- {
- tree s1, s2, rhs1, rhs2;
-
- s1 = (tree) p1;
- rhs1 = TREE_OPERAND (s1, 1);
-
- s2 = (tree) p2;
- rhs2 = TREE_OPERAND (s2, 1);
-
- /* If they are the same physical statement, return true. */
- if (s1 == s2)
- return true;
-
- /* In case of a collision, both RHS have to be identical and have the
- same VUSE operands. */
- if (TREE_CODE (rhs1) == TREE_CODE (rhs2)
- && TREE_TYPE (rhs1) == TREE_TYPE (rhs2)
- && operand_equal_p (rhs1, rhs2, 0))
- {
- varray_type ops1 = vuse_ops (s1);
- varray_type ops2 = vuse_ops (s2);
-
- if (ops1 == NULL && ops2 == NULL)
- {
- #ifdef ENABLE_CHECKING
- if (avail_expr_hash (s1) != avail_expr_hash (s2))
- abort ();
- #endif
- return true;
- }
-
- if (VARRAY_ACTIVE_SIZE (ops1) == VARRAY_ACTIVE_SIZE (ops2))
- {
- size_t i;
- for (i = 0; i < VARRAY_ACTIVE_SIZE (ops1); i++)
- if (VARRAY_GENERIC_PTR (ops1, i) != VARRAY_GENERIC_PTR (ops2, i))
- return false;
-
- #ifdef ENABLE_CHECKING
- if (avail_expr_hash (s1) != avail_expr_hash (s2))
- abort ();
- #endif
- return true;
- }
- }
-
- return false;
- }
-
/* Return the set of blocks where variable VAR is defined and the blocks
where VAR is live on entry (livein). */
--- 2332,2337 ----