This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] Dominator opts fixes and enhancements
- From: Diego Novillo <dnovillo at redhat dot com>
- To: "gcc-patches at gcc dot gnu dot org" <gcc-patches at gcc dot gnu dot org>
- Date: Mon, 25 Aug 2003 08:54:04 -0400
- Subject: [tree-ssa] Dominator opts fixes and enhancements
- Organization: Red Hat Canada
This patch fixes 20030823-1.c, ssa-ccp-9.c, adds a minor tweak to
optimize_stmt and prepares some infrastructure for the next set of fixes
I'm working on.
In 20030823-1.c, dominator optimization was replacing one memory load
for another. At first, I was almost tempted to let it do that. After
all, we can run SSA on the new exposed symbols, but it may be better to
change the gimplifier to avoid emitting mem<-mem moves. The bug in this
case, was in not checking the RHS for an SSA_NAME when optimizing memory
stores.
The patch also moves memory store detection outside of the test for
pointer dereferences. This allows us to detect more memory stores in
the form of structure and array stores. This fixes ssa-ccp-9.c because
we can now remove redundant loads of structures.
This introduced a regression in execute/921016-1.c, which contains a
redundant load of a bitfield. The redundant load is a bitfield
constant, which needs to be widened before we can use it. This is the
exact same problem we used to have in SSA-CCP.
When new symbols get exposed, it may happen that the symbol is partially
renamed into SSA (i.e., it's renamed in some statements and not in
others). In particular, it may happen that the first reference to the
symbol is a USE or VUSE operand. In those cases, the initial SSA name
for that symbol has been lost after the original rename pass. Now, if
the SSA renamer needs to create a default definition for a symbol, we
keep it in the variable's annotation. IIRC, Dan and Andrew had asked me
about this a while ago. Is this still useful to you, folks?
Also, we were not re-registering definitions of SSA names that have been
created in previous passes. This is going to be needed for the fixes to
must-alias that I'm working on.
I reworked the way we detect newly exposed symbols to avoid a complete
scan of the flow graph. If an optimization exposes a new symbol in a
statement, the statement is added to a queue of statements to re-scan at
the end of the dominator pass. Statements can't be scanned on the fly,
because their hash values may change with the new operands. This
corrupts the table of available expressions.
As part of the fixes I'm working on next, I added two new tests that
expose redundant memory loads. 20030824-1.c should pass with the fixes
included in this patch. Expect 20030824-2.c to fail until the next
round of fixes.
Bootstrapped and tested x86 and amd64.
Diego.
* tree-flow.h (struct var_ann_d): Add field default_def.
(widen_bitfield): Declare.
(set_default_def): Declare.
(default_def): Declare.
* tree-flow-inline.h (set_default_def): New inline function.
(default_def): New inline function.
* tree-dfa.c (dump_variable): Display default_def, if set.
* tree-simple.c (is_gimple_reg): Check for DECL_P before checking
for DECL_EXTERNAL.
* tree-ssa-dom.c (add_expr_propagated_p): Remove. Update all
users.
(find_new_vars_to_rename): New local function.
(tree_ssa_dominator_optimize): Add new argument vars_to_rename.
Change return type to void. Update all users.
(optimize_block): Add new argument vars_to_rename. Update all
users.
If the call to optimize_stmt returns true, add the statement to the
list of statements to re-scan for operands.
After optimizing the block and its dominator children, call
find_new_vars_to_rename for every statement that may have had new
symbols exposed.
(optimize_stmt): Change return type to bool. Return true if the
statement may have had new symbols exposed by optimization.
Add a sanity check for the value returned by lookup_avail_expr.
Create equivalences for more memory stores, not just the ones done
via INDIRECT_REF expressions.
Call widen_bitfield when optimizing stores to bitfields.
(lookup_avail_expr): Reformat comment.
* tree-ssa.c (rewrite_into_ssa): Remove local variable
addr_expr_propagated_p.
Clear out vars_to_rename before running dominator optimizations.
(check_for_new_variables): Remove.
(rewrite_stmt): Always register new definitions and virtual
definitions.
(register_new_def): Update comment.
(get_reaching_def): Update the default_def field for the variable
if it didn't have a reaching definition.
* tree-ssa-ccp.c (widen_bitfield): Declare it extern.
testsuite/ChangeLog.tree-ssa:
* gcc.dg/tree-ssa/20030824-1.c: New test.
* gcc.dg/tree-ssa/20030824-2.c: New test.
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.148
diff -d -u -p -d -c -p -r1.1.4.148 tree-dfa.c
*** tree-dfa.c 22 Aug 2003 23:26:27 -0000 1.1.4.148
--- tree-dfa.c 25 Aug 2003 02:36:10 -0000
*************** dump_variable (FILE *file, tree var)
*** 1389,1394 ****
--- 1389,1400 ----
if (ann->is_in_va_arg_expr)
fprintf (file, ", is used in va_arg");
+ if (ann->default_def)
+ {
+ fprintf (file, ", default def: ");
+ print_generic_expr (file, ann->default_def, 0);
+ }
+
if (ann->may_aliases)
{
fprintf (file, ", may aliases: ");
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow-inline.h,v
retrieving revision 1.1.2.47
diff -d -u -p -d -c -p -r1.1.2.47 tree-flow-inline.h
*** tree-flow-inline.h 4 Aug 2003 18:44:02 -0000 1.1.2.47
--- tree-flow-inline.h 25 Aug 2003 02:36:11 -0000
*************** may_propagate_copy (tree dest, tree orig
*** 545,548 ****
--- 545,564 ----
&& !DECL_HARD_REGISTER (SSA_NAME_VAR (dest)));
}
+ static inline void
+ set_default_def (tree var, tree def)
+ {
+ var_ann_t ann = var_ann (var);
+ if (ann == NULL)
+ ann = create_var_ann (var);
+ ann->default_def = def;
+ }
+
+ static inline tree
+ default_def (tree var)
+ {
+ var_ann_t ann = var_ann (var);
+ return ann ? ann->default_def : NULL_TREE;
+ }
+
#endif /* _TREE_FLOW_INLINE_H */
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.105
diff -d -u -p -d -c -p -r1.1.4.105 tree-flow.h
*** tree-flow.h 19 Aug 2003 19:03:24 -0000 1.1.4.105
--- tree-flow.h 25 Aug 2003 02:36:12 -0000
*************** struct var_ann_d GTY(())
*** 123,128 ****
--- 123,134 ----
/* The BIND_EXPR in that the variable is declared. */
tree scope;
+
+ /* Default definition for this symbol. If this field is not NULL, it
+ means that the first reference to this variable in the function is a
+ USE or a VUSE. In those cases, the SSA renamer creates an SSA name
+ for this variable with an empty defining statement. */
+ tree default_def;
};
*************** static inline varray_type reaching_defs
*** 284,289 ****
--- 290,297 ----
static inline bool has_hidden_use (tree);
static inline void set_has_hidden_use (tree);
static inline tree parent_stmt (tree);
+ static inline void set_default_def (tree, tree);
+ static inline tree default_def (tree);
/*---------------------------------------------------------------------------
*************** extern void tree_perform_ssapre (tree);
*** 491,499 ****
/* 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 (tree);
extern void dump_dominator_optimization_stats (FILE *);
extern void debug_dominator_optimization_stats (void);
--- 499,508 ----
/* In tree-ssa-ccp.c */
void tree_ssa_ccp (tree);
void fold_stmt (tree *);
+ tree widen_bitfield (tree, tree, tree);
/* In tree-ssa-dom.c */
! extern void tree_ssa_dominator_optimize (tree, sbitmap);
extern void dump_dominator_optimization_stats (FILE *);
extern void debug_dominator_optimization_stats (void);
Index: tree-simple.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-simple.c,v
retrieving revision 1.1.4.49
diff -d -u -p -d -c -p -r1.1.4.49 tree-simple.c
*** tree-simple.c 22 Aug 2003 20:30:19 -0000 1.1.4.49
--- tree-simple.c 25 Aug 2003 02:36:19 -0000
*************** is_gimple_reg (tree t)
*** 431,437 ****
return (is_gimple_variable (t)
&& TYPE_MODE (TREE_TYPE (t)) != BLKmode
&& ! TREE_STATIC (t)
! && ! DECL_EXTERNAL (t)
&& ! TREE_ADDRESSABLE (t)
/* A volatile decl is not acceptable because we can't reuse it as
needed. We need to copy it into a temp first. */
--- 431,437 ----
return (is_gimple_variable (t)
&& TYPE_MODE (TREE_TYPE (t)) != BLKmode
&& ! TREE_STATIC (t)
! && (! DECL_P (t) || ! DECL_EXTERNAL (t))
&& ! TREE_ADDRESSABLE (t)
/* A volatile decl is not acceptable because we can't reuse it as
needed. We need to copy it into a temp first. */
Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-ccp.c,v
retrieving revision 1.1.2.85
diff -d -u -p -d -c -p -r1.1.2.85 tree-ssa-ccp.c
*** tree-ssa-ccp.c 22 Aug 2003 23:26:27 -0000 1.1.2.85
--- tree-ssa-ccp.c 25 Aug 2003 02:36:19 -0000
*************** static void simulate_stmt (tree);
*** 119,125 ****
static void substitute_and_fold (void);
static value evaluate_stmt (tree);
static void dump_lattice_value (FILE *, const char *, value);
- static tree widen_bitfield (tree, tree, tree);
static bool replace_uses_in (tree);
static latticevalue likely_value (tree);
static tree get_rhs (tree);
--- 119,124 ----
*************** dump_lattice_value (FILE *outf, const ch
*** 933,939 ****
variable VAR, return VAL appropriately widened to fit into VAR. If
FIELD is wider than HOST_WIDE_INT, NULL is returned. */
! static tree
widen_bitfield (tree val, tree field, tree var)
{
unsigned var_size, field_size;
--- 932,938 ----
variable VAR, return VAL appropriately widened to fit into VAR. If
FIELD is wider than HOST_WIDE_INT, NULL is returned. */
! tree
widen_bitfield (tree val, tree field, tree var)
{
unsigned var_size, field_size;
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.29
diff -d -u -p -d -c -p -r1.1.2.29 tree-ssa-dom.c
*** tree-ssa-dom.c 21 Aug 2003 19:28:12 -0000 1.1.2.29
--- tree-ssa-dom.c 25 Aug 2003 02:36:20 -0000
*************** struct opt_stats_d
*** 80,90 ****
};
static struct opt_stats_d opt_stats;
- static bool addr_expr_propagated_p;
/* Local functions. */
! static void optimize_block (basic_block, tree, int);
! 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 *);
--- 80,89 ----
};
static struct opt_stats_d opt_stats;
/* Local functions. */
! static void optimize_block (basic_block, tree, int, sbitmap);
! static bool 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 tree get_eq_expr_value (tree, int
*** 94,113 ****
static hashval_t avail_expr_hash (const void *);
static int avail_expr_eq (const void *, const void *);
static void htab_statistics (FILE *, htab_t);
! static void record_cond_is_false (tree cond, varray_type *, htab_t);
! static void record_cond_is_true (tree cond, varray_type *, htab_t);
/* Optimize function FNDECL 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 (tree fndecl)
{
bool found_unreachable;
edge e;
--- 93,112 ----
static hashval_t avail_expr_hash (const void *);
static int avail_expr_eq (const void *, const void *);
static void htab_statistics (FILE *, htab_t);
! static void record_cond_is_false (tree, varray_type *, htab_t);
! static void record_cond_is_true (tree, varray_type *, htab_t);
! static void find_new_vars_to_rename (tree, sbitmap);
/* Optimize function FNDECL based on the dominator tree. This does
simple const/copy propagation and redundant expression elimination using
value numbering.
! This pass may expose new symbols that need to be renamed into SSA. For
! every new symbol exposed, its corresponding bit will be set in
! VARS_TO_RENAME. */
! void
! tree_ssa_dominator_optimize (tree fndecl, sbitmap vars_to_rename)
{
bool found_unreachable;
edge e;
*************** tree_ssa_dominator_optimize (tree fndecl
*** 122,130 ****
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;
-
/* Build the dominator tree if necessary.
We don't have a flag indicating if the dominator tree is available,
--- 121,126 ----
*************** tree_ssa_dominator_optimize (tree fndecl
*** 156,162 ****
int i;
/* Optimize the dominator tree. */
! optimize_block (ENTRY_BLOCK_PTR, NULL, 0);
/* Wipe the hash tables. */
htab_empty (const_and_copies);
--- 152,158 ----
int i;
/* Optimize the dominator tree. */
! optimize_block (ENTRY_BLOCK_PTR, NULL, 0, vars_to_rename);
/* Wipe the hash tables. */
htab_empty (const_and_copies);
*************** tree_ssa_dominator_optimize (tree fndecl
*** 206,244 ****
BITMAP_XFREE (unreachable_bitmap);
timevar_pop (TV_TREE_SSA_DOMINATOR_OPTS);
-
- 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 parent_block_last_stmt, int edge_flags)
{
varray_type block_avail_exprs;
bitmap children;
unsigned long i;
block_stmt_iterator si;
--- 202,240 ----
BITMAP_XFREE (unreachable_bitmap);
timevar_pop (TV_TREE_SSA_DOMINATOR_OPTS);
}
/* 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.
! EDGE_FLAGS are the flags for the incoming edge from BB's dominator
! parent block. This is used to determine whether BB is the first block
! of a THEN_CLAUSE or an ELSE_CLAUSE.
!
! VARS_TO_RENAME is a bitmap representing variables that will need to be
! renamed into SSA after dominator optimization. */
static void
! optimize_block (basic_block bb, tree parent_block_last_stmt, int edge_flags,
! sbitmap vars_to_rename)
{
varray_type block_avail_exprs;
+ varray_type stmts_to_rescan;
bitmap children;
unsigned long i;
block_stmt_iterator si;
*************** optimize_block (basic_block bb, tree par
*** 256,268 ****
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 our parent block ended in a COND_EXPR, add any equivalences
created by the COND_EXPR to the hash table and initialize
! EQ_EXPR_VALUE appropriately. */
if (parent_block_last_stmt
&& TREE_CODE (parent_block_last_stmt) == COND_EXPR
&& (edge_flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
--- 252,273 ----
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");
+ VARRAY_TREE_INIT (stmts_to_rescan, 20, "stmts_to_rescan");
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
/* If our parent block ended in a COND_EXPR, add any equivalences
created by the COND_EXPR to the hash table and initialize
! EQ_EXPR_VALUE appropriately.
!
! 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. */
if (parent_block_last_stmt
&& TREE_CODE (parent_block_last_stmt) == COND_EXPR
&& (edge_flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
*************** optimize_block (basic_block bb, tree par
*** 382,388 ****
/* 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);
/* Propagate known constants/copies into PHI nodes. */
for (e = bb->succ; e; e = e->succ_next)
--- 387,403 ----
/* Optimize each statement within the basic block. */
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
! {
! /* Optimization may have exposed new symbols that need to be renamed
! into SSA form. If that happens, queue the statement to re-scan its
! operands after finishing optimizing this block and its dominator
! children. Notice that we cannot re-scan the statement immediately
! because that would change the statement's value number. If the
! statement had been added to AVAIL_EXPRS, we would not be able to
! find it again. */
! if (optimize_stmt (si, &block_avail_exprs))
! VARRAY_PUSH_TREE (stmts_to_rescan, bsi_stmt (si));
! }
/* Propagate known constants/copies into PHI nodes. */
for (e = bb->succ; e; e = e->succ_next)
*************** optimize_block (basic_block bb, tree par
*** 428,434 ****
/* The destination block may have become unreachable, in
which case there's no point in optimizing it. */
if (dest->pred)
! optimize_block (dest, last, dest->pred->flags);
});
}
else
--- 443,449 ----
/* The destination block may have become unreachable, in
which case there's no point in optimizing it. */
if (dest->pred)
! optimize_block (dest, last, dest->pred->flags, vars_to_rename);
});
}
else
*************** optimize_block (basic_block bb, tree par
*** 440,446 ****
/* The destination block may have become unreachable, in
which case there's no point in optimizing it. */
if (dest->pred)
! optimize_block (dest, NULL_TREE, 0);
});
}
}
--- 455,461 ----
/* The destination block may have become unreachable, in
which case there's no point in optimizing it. */
if (dest->pred)
! optimize_block (dest, NULL_TREE, 0, vars_to_rename);
});
}
}
*************** optimize_block (basic_block bb, tree par
*** 548,553 ****
--- 563,577 ----
else
htab_remove_elt (const_and_copies, &vm);
}
+
+ /* Re-scan operands in all statements that may have had new symbols
+ exposed. */
+ while (VARRAY_ACTIVE_SIZE (stmts_to_rescan) > 0)
+ {
+ tree stmt = VARRAY_TOP_TREE (stmts_to_rescan);
+ VARRAY_POP (stmts_to_rescan);
+ find_new_vars_to_rename (stmt, vars_to_rename);
+ }
}
/* Dump SSA statistics on FILE. */
*************** record_cond_is_false (tree cond,
*** 655,661 ****
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;
--- 679,685 ----
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 bool
optimize_stmt (block_stmt_iterator si, varray_type *block_avail_exprs_p)
{
size_t i;
*************** optimize_stmt (block_stmt_iterator si, v
*** 663,676 ****
tree stmt;
varray_type defs, uses, vuses, vdefs, operand_tables[4], *table;
bool may_optimize_p;
stmt = bsi_stmt (si);
if (IS_EMPTY_STMT (stmt))
! return;
get_stmt_operands (stmt);
ann = stmt_ann (stmt);
opt_stats.num_stmts++;
if (dump_file && (dump_flags & TDF_DETAILS))
{
--- 687,702 ----
tree stmt;
varray_type defs, uses, vuses, vdefs, operand_tables[4], *table;
bool may_optimize_p;
+ bool may_have_exposed_new_symbols;
stmt = bsi_stmt (si);
if (IS_EMPTY_STMT (stmt))
! return false;
get_stmt_operands (stmt);
ann = stmt_ann (stmt);
opt_stats.num_stmts++;
+ may_have_exposed_new_symbols = false;
if (dump_file && (dump_flags & TDF_DETAILS))
{
*************** optimize_stmt (block_stmt_iterator si, v
*** 757,763 ****
if (TREE_CODE (val) == ADDR_EXPR
|| (POINTER_TYPE_P (TREE_TYPE (*op_p))
&& is_unchanging_value (val)))
! addr_expr_propagated_p = true;
if (TREE_CODE (val) == SSA_NAME)
propagate_copy (op_p, val, stmt_ann (stmt)->scope);
--- 783,789 ----
if (TREE_CODE (val) == ADDR_EXPR
|| (POINTER_TYPE_P (TREE_TYPE (*op_p))
&& is_unchanging_value (val)))
! may_have_exposed_new_symbols = true;
if (TREE_CODE (val) == SSA_NAME)
propagate_copy (op_p, val, stmt_ann (stmt)->scope);
*************** optimize_stmt (block_stmt_iterator si, v
*** 829,836 ****
--- 855,871 ----
}
opt_stats.num_re++;
+
+ #if defined ENABLE_CHECKING
+ if (TREE_CODE (cached_lhs) != SSA_NAME
+ && !is_unchanging_value (cached_lhs)
+ && !is_optimizable_addr_expr (cached_lhs))
+ abort ();
+ #endif
+
if (TREE_CODE (cached_lhs) == SSA_NAME)
fixup_var_scope (cached_lhs, stmt_ann (stmt)->scope);
+
*expr_p = cached_lhs;
ann->modified = 1;
}
*************** optimize_stmt (block_stmt_iterator si, v
*** 895,946 ****
record_cond_is_true (cond,
block_avail_exprs_p,
const_and_copies);
! /* A memory store, even an aliased store, creates a
! useful equivalence. By exchanging the LHS and RHS,
! creating suitable vops and recording the result in
! the available expression table, we may be able to
! expose more redundant loads. */
! if (!ann->has_volatile_ops
! && i == 0
! && (SSA_VAR_P (TREE_OPERAND (stmt, 1))
! || TREE_CONSTANT (TREE_OPERAND (stmt, 1))))
! {
! tree new;
! unsigned int j;
!
! /* Build a new statement with the RHS and LHS
! exchanged. */
! new = build (MODIFY_EXPR, TREE_TYPE (stmt),
! TREE_OPERAND (stmt, 1),
! TREE_OPERAND (stmt, 0));
! /* Get an annotation and set up the real operands. */
! get_stmt_ann (new);
! get_stmt_operands (new);
! /* Clear out the virtual operands on the new statement,
! we are going to set them explicitly below. */
! get_stmt_ann (new)->vops = NULL;
! /* For each VDEF on the original statement, we want
! to create a VUSE of the VDEF result on the new
! statement. */
! for (j = 0; vdefs && j < VARRAY_ACTIVE_SIZE (vdefs); j++)
! {
! tree op;
! op = (tree) VDEF_RESULT (VARRAY_TREE (vdefs, j));
! add_vuse (op, new, NULL);
! }
! /* Finally enter the statement into the available
! expression table. */
! lookup_avail_expr (new,
! block_avail_exprs_p,
! const_and_copies);
! }
}
}
}
--- 930,987 ----
record_cond_is_true (cond,
block_avail_exprs_p,
const_and_copies);
+ }
+ }
+ }
! /* A memory store, even an aliased store, creates a useful
! equivalence. By exchanging the LHS and RHS, creating suitable
! vops and recording the result in the available expression table,
! we may be able to expose more redundant loads. */
! if (!ann->has_volatile_ops
! && (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME
! || is_unchanging_value (TREE_OPERAND (stmt, 1)))
! && !is_gimple_reg (TREE_OPERAND (stmt, 0)))
! {
! tree new;
! size_t j;
! tree lhs = TREE_OPERAND (stmt, 0);
! tree rhs = TREE_OPERAND (stmt, 1);
! /* FIXME: If the LHS of the assignment is a bitfield and the RHS
! is a constant, we need to adjust the constant to fit into the
! type of the LHS. This fixes gcc.c-torture/execute/921016-1.c
! and should not be necessary if GCC represented bitfields
! properly. */
! if (TREE_CONSTANT (rhs)
! && TREE_CODE (lhs) == COMPONENT_REF
! && DECL_BIT_FIELD (TREE_OPERAND (lhs, 1)))
! rhs = widen_bitfield (rhs, TREE_OPERAND (lhs, 1), lhs);
! if (rhs)
! {
! /* Build a new statement with the RHS and LHS exchanged. */
! new = build (MODIFY_EXPR, TREE_TYPE (stmt), rhs, lhs);
! /* Get an annotation and set up the real operands. */
! get_stmt_ann (new);
! get_stmt_operands (new);
! /* Clear out the virtual operands on the new statement, we are
! going to set them explicitly below. */
! get_stmt_ann (new)->vops = NULL;
! /* For each VDEF on the original statement, we want to create a
! VUSE of the VDEF result on the new statement. */
! for (j = 0; vdefs && j < VARRAY_ACTIVE_SIZE (vdefs); j++)
! {
! tree op = VDEF_RESULT (VARRAY_TREE (vdefs, j));
! add_vuse (op, new, NULL);
}
+
+ /* Finally enter the statement into the available expression
+ table. */
+ lookup_avail_expr (new, block_avail_exprs_p, const_and_copies);
}
}
*************** optimize_stmt (block_stmt_iterator si, v
*** 1109,1114 ****
--- 1150,1157 ----
}
}
}
+
+ return may_have_exposed_new_symbols;
}
/* Hashing and equality functions for VAR_VALUE_D. */
*************** lookup_avail_expr (tree stmt,
*** 1242,1248 ****
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. */
if (SSA_VAR_P (lhs))
{
--- 1285,1291 ----
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. */
if (SSA_VAR_P (lhs))
{
*************** avail_expr_eq (const void *p1, const voi
*** 1453,1456 ****
--- 1496,1576 ----
}
return false;
+ }
+
+
+ /* Scan STMT for operands, if any new exposed symbols are found (i.e.,
+ operands that are not in SSA form), add those symbols to the bitmap
+ VARS_TO_RENAME. */
+
+ static void
+ find_new_vars_to_rename (tree stmt, sbitmap vars_to_rename)
+ {
+ varray_type ops;
+ size_t i;
+ void **slot;
+ bool found_new_symbols = false;
+
+ /* Before scanning for new operands check if STMT wasn't cached in
+ AVAIL_EXPRS. If so, we may need to replace or remove it afterwards
+ because we are about to modify the STMT's hash value. */
+ slot = htab_find_slot (avail_exprs, stmt, NO_INSERT);
+
+ /* Force an operand scan. */
+ modify_stmt (stmt);
+ get_stmt_operands (stmt);
+
+ ops = def_ops (stmt);
+ for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
+ {
+ tree *def_p = VARRAY_GENERIC_PTR (ops, i);
+ if (DECL_P (*def_p))
+ {
+ SET_BIT (vars_to_rename, var_ann (*def_p)->uid);
+ found_new_symbols = true;
+ }
+ }
+
+ ops = use_ops (stmt);
+ for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
+ {
+ tree *use_p = VARRAY_GENERIC_PTR (ops, i);
+ if (DECL_P (*use_p))
+ {
+ SET_BIT (vars_to_rename, var_ann (*use_p)->uid);
+ found_new_symbols = true;
+ }
+ }
+
+ ops = vdef_ops (stmt);
+ for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
+ {
+ tree var = VDEF_RESULT (VARRAY_TREE (ops, i));
+ if (DECL_P (var))
+ {
+ SET_BIT (vars_to_rename, var_ann (var)->uid);
+ found_new_symbols = true;
+ }
+ }
+
+ ops = vuse_ops (stmt);
+ for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
+ {
+ tree var = VARRAY_TREE (ops, i);
+ if (DECL_P (var))
+ {
+ SET_BIT (vars_to_rename, var_ann (var)->uid);
+ found_new_symbols = true;
+ }
+ }
+
+ /* If we found new exposed symbols, we have to remove the statement from
+ the hash table as it is no longer valid. Otherwise, re-insert it for
+ future use. */
+ if (slot)
+ {
+ htab_clear_slot (avail_exprs, slot);
+ slot = htab_find_slot (avail_exprs, stmt, INSERT);
+ *slot = (void *) stmt;
+ }
}
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.120
diff -d -u -p -d -c -p -r1.1.4.120 tree-ssa.c
*** tree-ssa.c 22 Aug 2003 02:54:37 -0000 1.1.4.120
--- tree-ssa.c 25 Aug 2003 02:36:20 -0000
*************** static void set_livein_block (tree, basi
*** 148,154 ****
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 *);
static void register_new_def (tree, tree, varray_type *);
--- 148,153 ----
*************** rewrite_into_ssa (tree fndecl, sbitmap v
*** 277,283 ****
sbitmap globals;
dominance_info idom;
int i, rename_count;
- bool addr_expr_propagated_p;
timevar_push (TV_TREE_SSA_OTHER);
--- 276,281 ----
*************** rewrite_into_ssa (tree fndecl, sbitmap v
*** 331,337 ****
dominator optimizations exposed more symbols to rename by propagating
ADDR_EXPR values into INDIRECT_REF expressions. */
rename_count = 0;
- addr_expr_propagated_p = false;
do
{
/* Find variable references and mark definition sites. */
--- 329,334 ----
*************** rewrite_into_ssa (tree fndecl, sbitmap v
*** 342,348 ****
/* 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);
--- 339,344 ----
*************** rewrite_into_ssa (tree fndecl, sbitmap v
*** 351,367 ****
dump_function_to_file (fndecl, dump_file, dump_flags);
/* Now optimize all the basic blocks in the program. */
if (flag_tree_dom)
- addr_expr_propagated_p = tree_ssa_dominator_optimize (fndecl);
-
- /* 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
- form and if new symbols are added to VARS_TO_RENAME, repeat the
- process. */
- if (addr_expr_propagated_p)
{
! check_for_new_variables ();
if (sbitmap_first_set_bit (vars_to_rename) >= 0)
{
/* Remove PHI nodes for the new symbols, clear the hash
--- 347,359 ----
dump_function_to_file (fndecl, dump_file, dump_flags);
/* Now optimize all the basic blocks in the program. */
+ sbitmap_zero (vars_to_rename);
if (flag_tree_dom)
{
! tree_ssa_dominator_optimize (fndecl, vars_to_rename);
!
! /* If the dominator optimizations exposed new variables, we need
! to repeat the SSA renaming process for those symbols. */
if (sbitmap_first_set_bit (vars_to_rename) >= 0)
{
/* Remove PHI nodes for the new symbols, clear the hash
*************** insert_phi_nodes_for (tree var, bitmap *
*** 1998,2059 ****
phi_insertion_points = NULL;
}
- /* 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. */
-
- static void
- check_for_new_variables (void)
- {
- basic_block bb;
-
- FOR_EACH_BB (bb)
- {
- block_stmt_iterator si;
-
- for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
- {
- varray_type ops;
- size_t i;
-
- tree stmt = bsi_stmt (si);
-
- get_stmt_operands (stmt);
-
- ops = def_ops (stmt);
- for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
- {
- tree *def_p = VARRAY_GENERIC_PTR (ops, i);
- if (DECL_P (*def_p))
- SET_BIT (vars_to_rename, var_ann (*def_p)->uid);
- }
-
- ops = use_ops (stmt);
- for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
- {
- tree *use_p = VARRAY_GENERIC_PTR (ops, i);
- if (DECL_P (*use_p))
- SET_BIT (vars_to_rename, var_ann (*use_p)->uid);
- }
-
- ops = vdef_ops (stmt);
- for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
- {
- tree var = VDEF_RESULT (VARRAY_TREE (ops, i));
- if (DECL_P (var))
- SET_BIT (vars_to_rename, var_ann (var)->uid);
- }
-
- ops = vuse_ops (stmt);
- for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
- {
- tree var = VARRAY_TREE (ops, i);
- if (DECL_P (var))
- SET_BIT (vars_to_rename, var_ann (var)->uid);
- }
- }
- }
- }
-
/* Rewrite statement pointed by iterator SI into SSA form.
--- 1990,1995 ----
*************** rewrite_stmt (block_stmt_iterator si, va
*** 2117,2126 ****
{
tree *def_p = VARRAY_GENERIC_PTR (defs, i);
if (TREE_CODE (*def_p) != SSA_NAME)
! {
! *def_p = make_ssa_name (*def_p, stmt);
! register_new_def (SSA_NAME_VAR (*def_p), *def_p, block_defs_p);
! }
}
/* Register new virtual definitions made by the statement. */
--- 2053,2060 ----
{
tree *def_p = VARRAY_GENERIC_PTR (defs, i);
if (TREE_CODE (*def_p) != SSA_NAME)
! *def_p = make_ssa_name (*def_p, stmt);
! register_new_def (SSA_NAME_VAR (*def_p), *def_p, block_defs_p);
}
/* Register new virtual definitions made by the statement. */
*************** rewrite_stmt (block_stmt_iterator si, va
*** 2128,2139 ****
{
tree vdef = VARRAY_TREE (vdefs, i);
! if (TREE_CODE (VDEF_RESULT (vdef)) == SSA_NAME)
! continue;
! rewrite_operand (&(VDEF_OP (vdef)));
- 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);
}
--- 2062,2073 ----
{
tree vdef = VARRAY_TREE (vdefs, i);
! if (TREE_CODE (VDEF_OP (vdef)) != SSA_NAME)
! rewrite_operand (&(VDEF_OP (vdef)));
! if (TREE_CODE (VDEF_RESULT (vdef)) != SSA_NAME)
! 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);
}
*************** register_new_def (tree var, tree def, va
*** 2174,2183 ****
{
tree currdef = get_value_for (var, currdefs);
! /* If the current reaching definition is NULL or a constant, push the
! variable itself so that rewrite_block knows what variable is
! associated with this NULL reaching def when unwinding the
! *BLOCK_DEFS_P stack. */
if (currdef == NULL_TREE)
VARRAY_PUSH_TREE (*block_defs_p, var);
--- 2108,2116 ----
{
tree currdef = get_value_for (var, currdefs);
! /* If the current reaching definition is NULL, push the variable itself
! so that rewrite_block knows what variable is associated with this NULL
! reaching def when unwinding the *BLOCK_DEFS_P stack. */
if (currdef == NULL_TREE)
VARRAY_PUSH_TREE (*block_defs_p, var);
*************** remove_annotations_r (tree *tp, int *wal
*** 2267,2289 ****
static tree
get_reaching_def (tree var)
{
! tree default_def, currdef_var;
/* Lookup the current reaching definition for VAR. */
! default_def = NULL_TREE;
currdef_var = get_value_for (var, currdefs);
/* If there is no reaching definition for VAR, create and register a
! default definition for it. */
if (currdef_var == NULL_TREE)
{
! default_def = make_ssa_name (var, build_empty_stmt ());
! set_value_for (var, default_def, currdefs);
}
/* Return the current reaching definition for VAR, or the default
definition, if we had to create one. */
! return (currdef_var) ? currdef_var : default_def;
}
--- 2200,2227 ----
static tree
get_reaching_def (tree var)
{
! tree default_d, currdef_var;
/* Lookup the current reaching definition for VAR. */
! default_d = NULL_TREE;
currdef_var = get_value_for (var, currdefs);
/* If there is no reaching definition for VAR, create and register a
! default definition for it (if needed). */
if (currdef_var == NULL_TREE)
{
! default_d = default_def (var);
! if (default_d == NULL_TREE)
! {
! default_d = make_ssa_name (var, build_empty_stmt ());
! set_default_def (var, default_d);
! }
! set_value_for (var, default_d, currdefs);
}
/* Return the current reaching definition for VAR, or the default
definition, if we had to create one. */
! return (currdef_var) ? currdef_var : default_d;
}
Index: testsuite/gcc.dg/tree-ssa/20030824-1.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/20030824-1.c
diff -N testsuite/gcc.dg/tree-ssa/20030824-1.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- testsuite/gcc.dg/tree-ssa/20030824-1.c 25 Aug 2003 02:36:44 -0000
***************
*** 0 ****
--- 1,22 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O1 -fdump-tree-optimized" } */
+
+ struct A
+ {
+ int a,b;
+ };
+
+ int foo (int x, int y)
+ {
+ int i, j;
+ struct A a,b;
+
+ a.a = x;
+ b.b = y;
+ j = a.a;
+ i = b.b;
+ return i + j;
+ }
+
+ /* This function should be optimized into 'return y+x'. */
+ /* { dg-final { scan-tree-dump-times "return y \\+ x" 1 "optimized"} } */
Index: testsuite/gcc.dg/tree-ssa/20030824-2.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/20030824-2.c
diff -N testsuite/gcc.dg/tree-ssa/20030824-2.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- testsuite/gcc.dg/tree-ssa/20030824-2.c 25 Aug 2003 02:36:44 -0000
***************
*** 0 ****
--- 1,22 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O1 -fdump-tree-optimized" } */
+
+ struct A
+ {
+ int a,b;
+ };
+
+ int foo (int x, int y)
+ {
+ int i, j;
+ struct A a;
+
+ a.a = x;
+ a.b = y;
+ j = a.a;
+ i = a.b;
+ return i + j;
+ }
+
+ /* This function should be optimized into 'return x+y'. */
+ /* { dg-final { scan-tree-dump-times "return y \\+ x" 1 "optimized"} } */