This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH]: Make PRE handle globals
- From: "Daniel Berlin" <dberlin at dberlin dot org>
- To: "GCC Patches" <gcc-patches at gcc dot gnu dot org>
- Date: Fri, 6 Jul 2007 15:58:09 -0400
- Subject: [PATCH]: Make PRE handle globals
One of the longstanding deficiencies of GVNPRE (and FRE) was it's
inability to optimize away duplicate loads from globals, as well as
hoist them.
The attached fixes this. SCCVN knows how to value number globals
properly, which takes care of FRE.
PRE needed a little more work. In order to be able to store different
values on a global at different times, we "unshare" the global locally
when creating it's value expression (this does not affect the original
IR), and have a pointer map for value handles for decl's.
Bootstrapped and regtested on i686-darwin
Committed to mainline
2007-07-06 Daniel Berlin <dberlin@dberlin.org>
* tree-ssa-sccvn.c (expr_has_constants): Handle tcc_declaration.
(try_to_simplify): Ditto.
(visit_use): Ditto.
* tree-vn.c (set_value_handle): Use decl_vh_map for decl value
handles.
* tree-flow-inline.h (get_value_handle): Ditto.
* tree-ssa-pre.c (decl_vh_map): New.
(decl_node_pool): New.
(can_value_number_operation): Support DECL_P.
(can_PRE_operation): Ditto.
(create_expression_by_pieces): Ditto.
(find_existing_value_expr): Modify to differnetiate between
addressing and top level.
(create_value_handle_for_expr): Handle DECL's.
(poolify_tree): Ditto.
(make_values_for_phi): Don't insert into PHI_GEN during FRE.
(make_values_for_stmt): Handle DECL's properly.
(init_pre): Reorg to not init useless things during FRE.
(fini_pre): Ditto.
* tree-flow.h: Include pointer-set.h.
(decl_vh_map): Declare.
* Makefile.in (TREE_FLOW_H): Add pointer-set.h
Index: tree-ssa-sccvn.c
===================================================================
--- tree-ssa-sccvn.c (revision 126397)
+++ tree-ssa-sccvn.c (working copy)
@@ -1332,6 +1332,7 @@ expr_has_constants (tree expr)
/* Constants inside reference ops are rarely interesting, but
it can take a lot of looking to find them. */
case tcc_reference:
+ case tcc_declaration:
return false;
default:
return is_gimple_min_invariant (expr);
@@ -1453,7 +1454,7 @@ try_to_simplify (tree stmt, tree rhs)
{
/* For references, see if we find a result for the lookup,
and use it if we do. */
-
+ case tcc_declaration:
case tcc_reference:
{
tree result = vn_reference_lookup (rhs,
@@ -1613,7 +1614,7 @@ visit_use (tree use)
if (TREE_CODE (lhs) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
changed = defs_to_varying (stmt);
- else if (REFERENCE_CLASS_P (lhs))
+ else if (REFERENCE_CLASS_P (lhs) || DECL_P (lhs))
{
changed = visit_reference_op_store (lhs, rhs, stmt);
}
Index: tree-vn.c
===================================================================
--- tree-vn.c (revision 126397)
+++ tree-vn.c (working copy)
@@ -99,7 +99,12 @@ set_value_handle (tree e, tree v)
{
if (TREE_CODE (e) == SSA_NAME)
SSA_NAME_VALUE (e) = v;
- else if (EXPR_P (e) || DECL_P (e) || TREE_CODE (e) == TREE_LIST
+ else if (DECL_P (e))
+ {
+ tree *slot = (tree *)pointer_map_insert (decl_vh_map, e);
+ *slot = v;
+ }
+ else if (EXPR_P (e) || TREE_CODE (e) == TREE_LIST
|| GIMPLE_STMT_P (e)
|| TREE_CODE (e) == CONSTRUCTOR)
get_tree_common_ann (e)->value_handle = v;
Index: tree-flow-inline.h
===================================================================
--- tree-flow-inline.h (revision 126397)
+++ tree-flow-inline.h (working copy)
@@ -1792,12 +1792,20 @@ get_value_handle (tree expr)
{
if (TREE_CODE (expr) == SSA_NAME)
return SSA_NAME_VALUE (expr);
- else if (DECL_P (expr) || TREE_CODE (expr) == TREE_LIST
+ else if (TREE_CODE (expr) == TREE_LIST
|| TREE_CODE (expr) == CONSTRUCTOR)
{
tree_ann_common_t ann = tree_common_ann (expr);
return ((ann) ? ann->value_handle : NULL_TREE);
}
+ else if (DECL_P (expr))
+ {
+ tree *result = (tree *)pointer_map_contains (decl_vh_map,
+ expr);
+ if (result)
+ return *result;
+ return NULL_TREE;
+ }
else if (is_gimple_min_invariant (expr))
return expr;
else if (EXPR_P (expr))
Index: tree-ssa-pre.c
===================================================================
--- tree-ssa-pre.c (revision 126397)
+++ tree-ssa-pre.c (working copy)
@@ -46,6 +46,7 @@ Boston, MA 02110-1301, USA. */
#include "langhooks.h"
#include "cfgloop.h"
#include "tree-ssa-sccvn.h"
+#include "pointer-set.h"
/* TODO:
@@ -182,6 +183,11 @@ Boston, MA 02110-1301, USA. */
useful only for debugging, since we don't do identity lookups. */
+/* Mapping from decl's to value handles, by pointer equality. We
+ "unshare" decls so we can give the same decl in different places
+ different value handles. */
+struct pointer_map_t *decl_vh_map;
+
/* Next global expression id number. */
static unsigned int next_expression_id;
@@ -369,6 +375,7 @@ static alloc_pool unary_node_pool;
static alloc_pool reference_node_pool;
static alloc_pool comparison_node_pool;
static alloc_pool modify_expr_node_pool;
+static alloc_pool decl_node_pool;
static bitmap_obstack grand_bitmap_obstack;
/* We can't use allocation pools to hold temporary CALL_EXPR objects, since
@@ -2065,6 +2072,7 @@ can_value_number_operation (tree op)
|| BINARY_CLASS_P (op)
|| COMPARISON_CLASS_P (op)
|| REFERENCE_CLASS_P (op)
+ || DECL_P (op)
|| (TREE_CODE (op) == CALL_EXPR
&& can_value_number_call (op));
}
@@ -2080,6 +2088,7 @@ can_PRE_operation (tree op)
return UNARY_CLASS_P (op)
|| BINARY_CLASS_P (op)
|| COMPARISON_CLASS_P (op)
+ || DECL_P (op)
|| TREE_CODE (op) == INDIRECT_REF
|| TREE_CODE (op) == COMPONENT_REF
|| TREE_CODE (op) == CALL_EXPR
@@ -2316,7 +2325,14 @@ create_expression_by_pieces (basic_block
genop1, genop2);
break;
}
-
+ case tcc_declaration:
+ {
+ /* Get the "shared" version of the DECL, that we didn't create
+ using a pool. */
+ folded = referenced_var_lookup (DECL_UID (expr));
+ }
+ break;
+
case tcc_unary:
{
tree op1 = TREE_OPERAND (expr, 0);
@@ -2957,10 +2973,15 @@ find_existing_value_expr (tree t, tree s
replaced with the value handles of each of the operands of EXPR.
VUSES represent the virtual use operands associated with EXPR (if
- any). Insert EXPR's operands into the EXP_GEN set for BLOCK. */
+ any). Insert EXPR's operands into the EXP_GEN set for BLOCK.
+
+ TOP_LEVEL is true if we are at the top of the original
+ expression. This is used to differentiate between addressing and
+ actual loads of globals. IE a = t vs a = t[0]. */
static inline tree
-create_value_expr_from (tree expr, basic_block block, tree stmt)
+create_value_expr_from (tree expr, basic_block block, tree stmt,
+ bool top_level)
{
int i;
enum tree_code code = TREE_CODE (expr);
@@ -2985,6 +3006,8 @@ create_value_expr_from (tree expr, basic
pool = binary_node_pool;
else if (TREE_CODE_CLASS (code) == tcc_comparison)
pool = comparison_node_pool;
+ else if (TREE_CODE_CLASS (code) == tcc_declaration)
+ pool = decl_node_pool;
else
gcc_assert (code == CALL_EXPR);
@@ -3000,7 +3023,10 @@ create_value_expr_from (tree expr, basic
{
tree val = NULL_TREE;
tree op;
-
+
+ if (i != 0)
+ top_level = false;
+
op = TREE_OPERAND (expr, i);
if (op == NULL_TREE)
continue;
@@ -3008,7 +3034,7 @@ create_value_expr_from (tree expr, basic
/* Recursively value-numberize reference ops and tree lists. */
if (REFERENCE_CLASS_P (op))
{
- tree tempop = create_value_expr_from (op, block, stmt);
+ tree tempop = create_value_expr_from (op, block, stmt, false);
op = tempop ? tempop : op;
val = vn_lookup_or_add_with_stmt (op, stmt);
}
@@ -3059,13 +3085,15 @@ poolify_tree (tree node)
return temp;
}
break;
+ case PARM_DECL:
+ case RESULT_DECL:
+ case VAR_DECL:
+ case CONST_DECL:
+ case FUNCTION_DECL:
case SSA_NAME:
case INTEGER_CST:
case STRING_CST:
case REAL_CST:
- case PARM_DECL:
- case VAR_DECL:
- case RESULT_DECL:
return node;
default:
gcc_unreachable ();
@@ -3280,7 +3308,8 @@ make_values_for_phi (tree phi, basic_blo
if (sccvnval)
{
vn_add (result, sccvnval);
- bitmap_insert_into_set (PHI_GEN (block), result);
+ if (!in_fre)
+ bitmap_insert_into_set (PHI_GEN (block), result);
bitmap_value_insert_into_set (AVAIL_OUT (block), result);
}
else
@@ -3348,7 +3377,7 @@ make_values_for_stmt (tree stmt, basic_b
/* For value numberable operation, create a
duplicate expression with the operands replaced
with the value handles of the original RHS. */
- tree newt = create_value_expr_from (rhs, block, stmt);
+ tree newt = create_value_expr_from (rhs, block, stmt, true);
if (newt)
{
/* If we already have a value number for the LHS, reuse
@@ -3376,8 +3405,7 @@ make_values_for_stmt (tree stmt, basic_b
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
|| is_gimple_min_invariant (rhs)
|| TREE_CODE (rhs) == ADDR_EXPR
- || TREE_INVARIANT (rhs)
- || DECL_P (rhs))
+ || TREE_INVARIANT (rhs))
{
if (lhsval)
@@ -3785,7 +3813,9 @@ static void
init_pre (bool do_fre)
{
basic_block bb;
-
+
+ unsigned int max_decl_size;
+
next_expression_id = 0;
expressions = NULL;
in_fre = do_fre;
@@ -3796,52 +3826,62 @@ init_pre (bool do_fre)
storetemp = NULL_TREE;
prephitemp = NULL_TREE;
- if (!do_fre)
- loop_optimizer_init (LOOPS_NORMAL);
-
- connect_infinite_loops_to_exit ();
memset (&pre_stats, 0, sizeof (pre_stats));
-
-
- postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
- post_order_compute (postorder, false, false);
-
+ bitmap_obstack_initialize (&grand_bitmap_obstack);
+
+ if (!do_fre)
+ {
+ loop_optimizer_init (LOOPS_NORMAL);
+ connect_infinite_loops_to_exit ();
+ postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
+ post_order_compute (postorder, false, false);
+ calculate_dominance_info (CDI_POST_DOMINATORS);
+ phi_translate_table = htab_create (5110, expr_pred_trans_hash,
+ expr_pred_trans_eq, free);
+ seen_during_translate = BITMAP_ALLOC (&grand_bitmap_obstack);
+ binary_node_pool = create_alloc_pool ("Binary tree nodes",
+ tree_code_size (PLUS_EXPR), 30);
+ unary_node_pool = create_alloc_pool ("Unary tree nodes",
+ tree_code_size (NEGATE_EXPR), 30);
+ reference_node_pool = create_alloc_pool ("Reference tree nodes",
+ tree_code_size (ARRAY_REF), 30);
+ comparison_node_pool = create_alloc_pool ("Comparison tree nodes",
+ tree_code_size (EQ_EXPR), 30);
+ modify_expr_node_pool = create_alloc_pool ("GIMPLE_MODIFY_STMT nodes",
+ tree_code_size (GIMPLE_MODIFY_STMT),
+ 30);
+ max_decl_size = MAX (tree_code_size (VAR_DECL), tree_code_size (PARM_DECL));
+ max_decl_size = MAX (max_decl_size, tree_code_size (RESULT_DECL));
+ max_decl_size = MAX (max_decl_size, tree_code_size (CONST_DECL));
+ max_decl_size = MAX (max_decl_size, tree_code_size (FUNCTION_DECL));
+ decl_node_pool = create_alloc_pool ("_DECL nodes", max_decl_size, 30);
+
+ obstack_init (&temp_call_expr_obstack);
+ modify_expr_template = NULL;
+ }
+
FOR_ALL_BB (bb)
bb->aux = xcalloc (1, sizeof (struct bb_bitmap_sets));
- calculate_dominance_info (CDI_POST_DOMINATORS);
calculate_dominance_info (CDI_DOMINATORS);
- bitmap_obstack_initialize (&grand_bitmap_obstack);
- phi_translate_table = htab_create (5110, expr_pred_trans_hash,
- expr_pred_trans_eq, free);
- seen_during_translate = BITMAP_ALLOC (&grand_bitmap_obstack);
bitmap_set_pool = create_alloc_pool ("Bitmap sets",
sizeof (struct bitmap_set), 30);
- binary_node_pool = create_alloc_pool ("Binary tree nodes",
- tree_code_size (PLUS_EXPR), 30);
- unary_node_pool = create_alloc_pool ("Unary tree nodes",
- tree_code_size (NEGATE_EXPR), 30);
- reference_node_pool = create_alloc_pool ("Reference tree nodes",
- tree_code_size (ARRAY_REF), 30);
- comparison_node_pool = create_alloc_pool ("Comparison tree nodes",
- tree_code_size (EQ_EXPR), 30);
- modify_expr_node_pool = create_alloc_pool ("GIMPLE_MODIFY_STMT nodes",
- tree_code_size (GIMPLE_MODIFY_STMT),
- 30);
- obstack_init (&temp_call_expr_obstack);
- modify_expr_template = NULL;
FOR_ALL_BB (bb)
{
- EXP_GEN (bb) = bitmap_set_new ();
- PHI_GEN (bb) = bitmap_set_new ();
- TMP_GEN (bb) = bitmap_set_new ();
+ if (!do_fre)
+ {
+ EXP_GEN (bb) = bitmap_set_new ();
+ PHI_GEN (bb) = bitmap_set_new ();
+ TMP_GEN (bb) = bitmap_set_new ();
+ }
AVAIL_OUT (bb) = bitmap_set_new ();
}
- maximal_set = in_fre ? NULL : bitmap_set_new ();
+ maximal_set = do_fre ? NULL : bitmap_set_new ();
need_eh_cleanup = BITMAP_ALLOC (NULL);
+ decl_vh_map = pointer_map_create ();
}
@@ -3852,19 +3892,24 @@ fini_pre (void)
{
basic_block bb;
unsigned int i;
-
- free (postorder);
- VEC_free (tree, heap, inserted_exprs);
- VEC_free (tree, heap, need_creation);
+
+ if (!in_fre)
+ {
+ free (postorder);
+ VEC_free (tree, heap, inserted_exprs);
+ VEC_free (tree, heap, need_creation);
+ free_alloc_pool (binary_node_pool);
+ free_alloc_pool (reference_node_pool);
+ free_alloc_pool (unary_node_pool);
+ free_alloc_pool (comparison_node_pool);
+ free_alloc_pool (modify_expr_node_pool);
+ free_alloc_pool (decl_node_pool);
+ htab_delete (phi_translate_table);
+ remove_fake_exit_edges ();
+ free_dominance_info (CDI_POST_DOMINATORS);
+ }
bitmap_obstack_release (&grand_bitmap_obstack);
free_alloc_pool (bitmap_set_pool);
- free_alloc_pool (binary_node_pool);
- free_alloc_pool (reference_node_pool);
- free_alloc_pool (unary_node_pool);
- free_alloc_pool (comparison_node_pool);
- free_alloc_pool (modify_expr_node_pool);
- htab_delete (phi_translate_table);
- remove_fake_exit_edges ();
FOR_ALL_BB (bb)
{
@@ -3872,8 +3917,6 @@ fini_pre (void)
bb->aux = NULL;
}
- free_dominance_info (CDI_POST_DOMINATORS);
-
if (!bitmap_empty_p (need_eh_cleanup))
{
tree_purge_all_dead_eh_edges (need_eh_cleanup);
@@ -3881,7 +3924,8 @@ fini_pre (void)
}
BITMAP_FREE (need_eh_cleanup);
-
+ pointer_map_destroy (decl_vh_map);
+
/* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant
future we will want them to be persistent though. */
for (i = 0; i < num_ssa_names; i++)
@@ -3895,7 +3939,7 @@ fini_pre (void)
&& TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE)
SSA_NAME_VALUE (name) = NULL;
}
- if (current_loops != NULL)
+ if (current_loops != NULL && !in_fre)
loop_optimizer_finalize ();
}
Index: tree-flow.h
===================================================================
--- tree-flow.h (revision 126397)
+++ tree-flow.h (working copy)
@@ -31,6 +31,7 @@ Boston, MA 02110-1301, USA. */
#include "tree-ssa-operands.h"
#include "cgraph.h"
#include "ipa-reference.h"
+#include "pointer-set.h"
/* Forward declare structures for the garbage collector GTY markers. */
#ifndef GCC_BASIC_BLOCK_H
@@ -1081,7 +1082,7 @@ extern bool maybe_clean_or_replace_eh_st
void add_to_value (tree, tree);
void debug_value_expressions (tree);
void print_value_expressions (FILE *, tree);
-
+extern struct pointer_map_t *decl_vh_map;
/* In tree-vn.c */
tree make_value_handle (tree);
Index: Makefile.in
===================================================================
--- Makefile.in (revision 126397)
+++ Makefile.in (working copy)
@@ -805,7 +805,7 @@ TREE_DUMP_H = tree-dump.h $(SPLAY_TREE_H
TREE_GIMPLE_H = tree-gimple.h tree-iterator.h
TREE_FLOW_H = tree-flow.h tree-flow-inline.h tree-ssa-operands.h \
bitmap.h $(BASIC_BLOCK_H) hard-reg-set.h $(TREE_GIMPLE_H) \
- $(HASHTAB_H) $(CGRAPH_H) $(IPA_REFERENCE_H)
+ $(HASHTAB_H) $(CGRAPH_H) $(IPA_REFERENCE_H) pointer-set.h
TREE_SSA_LIVE_H = tree-ssa-live.h $(PARTITION_H) vecprim.h
PRETTY_PRINT_H = pretty-print.h input.h $(OBSTACK_H)
DIAGNOSTIC_H = diagnostic.h diagnostic.def $(PRETTY_PRINT_H) options.h
Index: testsuite/gcc.dg/tree-ssa/ssa-pre-17.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/ssa-pre-17.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/ssa-pre-17.c (revision 0)
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-pre-details" } */
+
+ int i;
+ int foo(int q) {
+ int j;
+ int p;
+ for (j = 0; j < 9; j++)
+ {
+ p = i + q;
+ }
+ return p;
+ }
+/* We should replace p = a load from i that will pop into the loop, with a hoisted version.
+ We should also replace i + q with a hoisted version. */
+/* { dg-final { scan-tree-dump-times "Replaced " 2 "pre" } } */
+/* { dg-final { cleanup-tree-dump "pre" } } */
Index: testsuite/gcc.dg/tree-ssa/ssa-fre-6.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/ssa-fre-6.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/ssa-fre-6.c (revision 0)
@@ -0,0 +1,6 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-fre-details" } */
+
+ int i; int foo(void) { i = 2; int j = i * 2; int k = i + 2; return j == k; }
+/* { dg-final { scan-tree-dump-times "Replaced " 5 "fre" } } */
+/* { dg-final { cleanup-tree-dump "fre" } } */
Index: testsuite/ChangeLog
===================================================================
--- testsuite/ChangeLog (revision 126424)
+++ testsuite/ChangeLog (working copy)
@@ -1,3 +1,8 @@
+2007-07-06 Daniel Berlin <dberlin@dberlin.org>
+
+ * gcc.dg/tree-ssa/ssa-pre-17.c: New test.
+ * gcc.dg/tree-ssa/ssa-fre-7.c: New test.
+
2007-07-06 Josh Conner <jconner@apple.com>
PR middle-end/32602