[PATCH] Teach SCCVN/FRE expression insertion, optimize type-punning through unions (final!)
Richard Guenther
rguenther@suse.de
Fri Mar 14 12:03:00 GMT 2008
This final patch makes it possible for SCCVN to value-number something
to an expression that is not yet computed and cause it to be inserted
at FRE elimination time instead. The use in this patch is for optimizing
type-punning through unions to use VIEW_CONVERT_EXPRs instead which
allow to get rid of the union temporary and generates better code.
The SCCVN part generates a new (temporary) SSA_NAME as a leader and
value-number for a to-be inserted expression.
During FRE elimination, if we do not find an available replacement, we
use the PRE insertion infrastructure to insert the expression SCCVN
thinks is simpler just before the elimination point. As this is
not always possible checks for availability in the replacement block
(to make sure its not a partial redundancy) and dominance checks for
the insertion point are done (this uglifies the patch somewhat, so
just ignore that part ;)).
The main problem with insertion and dominance is that we visit
unrelated SCCs in arbitrary oder and only once. Thus for
# VUSE <SFT.10_8(D), SFT.11_9(D)>
D.1569_1 = fs.offset;
D.1570_2 = (char) D.1569_1;
# SMT.16_10 = VDEF <SMT.16_6>
*state_in_3(D) = D.1570_2;
# VUSE <SFT.10_8(D), SFT.11_9(D)>
D.1571_4 = fs.reg;
D.1572_5 = (char) D.1571_4;
# SMT.16_11 = VDEF <SMT.16_10>
*state_in_3(D) = D.1572_5;
dependent on which singleton SCC (D.1569_1 = fs.offset or D.1571_4 =
fs.reg) we happen to visit first, either the load from fs.reg or
that of fs.offset is value-numbered to V_C_E <the-other-result>.
The verification makes sure that in the case we would try to replace
the load from fs.offset, the replacement fails (and thus no optimization
is done - we don't re-visit the other SCC to make both transformations
after all).
One trivial adjustment makes the above cases less likely, namely
iterating over all SSA_NAMEs in forward oder rather than backward
order, which happens to more likely visit SCCs in dominator order.
A "real" fix would try to do a topological sort of all SCCs after
collecting them - but this is for another patch.
Bootstrapped and tested on x86_64-unknown-linux-gnu for all
languages and Ada.
Ok for mainline?
Thanks,
Richard.
2008-03-14 Richard Guenther <rguenther@suse.de>
PR tree-optimization/34043
PR tree-optimization/33989
* tree-ssa-pre.c (execute_pre): Allow SCCVN to do insertion
when doing FRE.
(bitmap_find_leader): Use extra argument to verify dominance
relationship inside a basic-block.
(can_PRE_operation): Add VIEW_CONVERT_EXPR.
(find_leader_in_sets): Adjust.
(create_component_ref_by_pieces): Take extra argument for
dominance check, handle lookup failures.
(find_or_generate_expression): Likewise.
(create_expression_by_pieces): Likewise.
(insert_into_preds_of_block): Adjust.
(create_value_expr_from): If asked for, verify all operands
are in the blocks AVAIL_OUT set.
(make_values_for_stmt): Check for SSA_NAMEs that are life
over an abnormal edge.
(compute_avail): Remove such check.
(do_SCCVN_insertion): New function.
(eliminate): If we do not find a leader suitable for replacement
insert a replacement expression from SCCVN if available.
* tree-ssa-sccvn.h (run_scc_vn): Update prototype.
(struct vn_ssa_aux): Add needs_insertion flag.
* tree-ssa-sccvn.c (may_insert): New global flag.
(copy_reference_ops_from_ref): Value-number union member access
based on its size, not type and member if insertion is allowed.
(visit_reference_op_load): For a weak match from union type
punning lookup a view-converted value and insert a SSA_NAME
for that value if that is not found.
(visit_use): Make dumps shorter. Do not disallow value numbering
SSA_NAMEs that are life over an abnormal edge to constants.
(free_scc_vn): Release inserted SSA_NAMEs.
(run_scc_vn): New flag to specify whether insertion is allowed.
Process SSA_NAMEs in forward order.
* tree-ssa-loop-im.c (for_each_index): Handle invariant
ADDR_EXPRs inside VIEW_CONVERT_EXPR.
* fold-const.c (fold_unary): Fold VIEW_CONVERT_EXPRs from/to
pointer type to/from integral types that do not change the
precision to regular conversions.
* gcc.dg/tree-ssa/ssa-fre-7.c: New testcase.
* gcc.dg/tree-ssa/ssa-fre-8.c: Likewise.
* gcc.dg/tree-ssa/ssa-fre-9.c: Likewise.
* gcc.dg/tree-ssa/ssa-fre-10.c: Likewise.
* gcc.dg/tree-ssa/ssa-pre-17.c: Likewise.
Index: trunk/gcc/tree-ssa-pre.c
===================================================================
*** trunk.orig/gcc/tree-ssa-pre.c 2008-03-13 15:34:33.000000000 +0100
--- trunk/gcc/tree-ssa-pre.c 2008-03-14 11:27:41.000000000 +0100
*************** static struct
*** 376,390 ****
} pre_stats;
static bool do_partial_partial;
! static tree bitmap_find_leader (bitmap_set_t, tree);
static void bitmap_value_insert_into_set (bitmap_set_t, tree);
static void bitmap_value_replace_in_set (bitmap_set_t, tree);
static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
static bool bitmap_set_contains_value (bitmap_set_t, tree);
static void bitmap_insert_into_set (bitmap_set_t, tree);
static bitmap_set_t bitmap_set_new (void);
! static tree create_expression_by_pieces (basic_block, tree, tree);
! static tree find_or_generate_expression (basic_block, tree, tree);
/* We can add and remove elements and entries to and from sets
and hash tables, so we use alloc pools for them. */
--- 376,390 ----
} pre_stats;
static bool do_partial_partial;
! static tree bitmap_find_leader (bitmap_set_t, tree, tree);
static void bitmap_value_insert_into_set (bitmap_set_t, tree);
static void bitmap_value_replace_in_set (bitmap_set_t, tree);
static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
static bool bitmap_set_contains_value (bitmap_set_t, tree);
static void bitmap_insert_into_set (bitmap_set_t, tree);
static bitmap_set_t bitmap_set_new (void);
! static tree create_expression_by_pieces (basic_block, tree, tree, tree);
! static tree find_or_generate_expression (basic_block, tree, tree, tree);
/* We can add and remove elements and entries to and from sets
and hash tables, so we use alloc pools for them. */
*************** find_leader_in_sets (tree expr, bitmap_s
*** 954,962 ****
{
tree result;
! result = bitmap_find_leader (set1, expr);
if (!result && set2)
! result = bitmap_find_leader (set2, expr);
return result;
}
--- 954,962 ----
{
tree result;
! result = bitmap_find_leader (set1, expr, NULL_TREE);
if (!result && set2)
! result = bitmap_find_leader (set2, expr, NULL_TREE);
return result;
}
*************** phi_translate_set (bitmap_set_t dest, bi
*** 1394,1404 ****
}
/* Find the leader for a value (i.e., the name representing that
! value) in a given set, and return it. Return NULL if no leader is
! found. */
static tree
! bitmap_find_leader (bitmap_set_t set, tree val)
{
if (val == NULL)
return NULL;
--- 1394,1405 ----
}
/* Find the leader for a value (i.e., the name representing that
! value) in a given set, and return it. If STMT is non-NULL it
! makes sure the defining statement for the leader dominates it.
! Return NULL if no leader is found. */
static tree
! bitmap_find_leader (bitmap_set_t set, tree val, tree stmt)
{
if (val == NULL)
return NULL;
*************** bitmap_find_leader (bitmap_set_t set, tr
*** 1425,1431 ****
EXECUTE_IF_AND_IN_BITMAP (exprset->expressions,
set->expressions, 0, i, bi)
! return expression_for_id (i);
}
return NULL;
}
--- 1426,1442 ----
EXECUTE_IF_AND_IN_BITMAP (exprset->expressions,
set->expressions, 0, i, bi)
! {
! tree val = expression_for_id (i);
! if (stmt)
! {
! tree def_stmt = SSA_NAME_DEF_STMT (val);
! if (bb_for_stmt (def_stmt) == bb_for_stmt (stmt)
! && stmt_ann (def_stmt)->uid >= stmt_ann (stmt)->uid)
! continue;
! }
! return val;
! }
}
return NULL;
}
*************** can_PRE_operation (tree op)
*** 2107,2112 ****
--- 2118,2124 ----
|| COMPARISON_CLASS_P (op)
|| TREE_CODE (op) == INDIRECT_REF
|| TREE_CODE (op) == COMPONENT_REF
+ || TREE_CODE (op) == VIEW_CONVERT_EXPR
|| TREE_CODE (op) == CALL_EXPR
|| TREE_CODE (op) == ARRAY_REF;
}
*************** static VEC(tree, heap) *need_creation;
*** 2136,2149 ****
are doing.
*/
static tree
! create_component_ref_by_pieces (basic_block block, tree expr, tree stmts)
{
tree genop = expr;
tree folded;
if (TREE_CODE (genop) == VALUE_HANDLE)
{
! tree found = bitmap_find_leader (AVAIL_OUT (block), expr);
if (found)
return found;
}
--- 2148,2162 ----
are doing.
*/
static tree
! create_component_ref_by_pieces (basic_block block, tree expr, tree stmts,
! tree domstmt)
{
tree genop = expr;
tree folded;
if (TREE_CODE (genop) == VALUE_HANDLE)
{
! tree found = bitmap_find_leader (AVAIL_OUT (block), expr, domstmt);
if (found)
return found;
}
*************** create_component_ref_by_pieces (basic_bl
*** 2163,2178 ****
tree op1, op2, op3;
op0 = create_component_ref_by_pieces (block,
TREE_OPERAND (genop, 0),
! stmts);
op1 = TREE_OPERAND (genop, 1);
if (TREE_CODE (op1) == VALUE_HANDLE)
! op1 = find_or_generate_expression (block, op1, stmts);
op2 = TREE_OPERAND (genop, 2);
if (op2 && TREE_CODE (op2) == VALUE_HANDLE)
! op2 = find_or_generate_expression (block, op2, stmts);
op3 = TREE_OPERAND (genop, 3);
if (op3 && TREE_CODE (op3) == VALUE_HANDLE)
! op3 = find_or_generate_expression (block, op3, stmts);
folded = build4 (ARRAY_REF, TREE_TYPE (genop), op0, op1,
op2, op3);
return folded;
--- 2176,2193 ----
tree op1, op2, op3;
op0 = create_component_ref_by_pieces (block,
TREE_OPERAND (genop, 0),
! stmts, domstmt);
op1 = TREE_OPERAND (genop, 1);
if (TREE_CODE (op1) == VALUE_HANDLE)
! op1 = find_or_generate_expression (block, op1, stmts, domstmt);
op2 = TREE_OPERAND (genop, 2);
if (op2 && TREE_CODE (op2) == VALUE_HANDLE)
! op2 = find_or_generate_expression (block, op2, stmts, domstmt);
op3 = TREE_OPERAND (genop, 3);
if (op3 && TREE_CODE (op3) == VALUE_HANDLE)
! op3 = find_or_generate_expression (block, op3, stmts, domstmt);
! if (!op0 || !op1)
! return NULL_TREE;
folded = build4 (ARRAY_REF, TREE_TYPE (genop), op0, op1,
op2, op3);
return folded;
*************** create_component_ref_by_pieces (basic_bl
*** 2183,2189 ****
tree op1;
op0 = create_component_ref_by_pieces (block,
TREE_OPERAND (genop, 0),
! stmts);
/* op1 should be a FIELD_DECL, which are represented by
themselves. */
op1 = TREE_OPERAND (genop, 1);
--- 2198,2206 ----
tree op1;
op0 = create_component_ref_by_pieces (block,
TREE_OPERAND (genop, 0),
! stmts, domstmt);
! if (!op0)
! return NULL_TREE;
/* op1 should be a FIELD_DECL, which are represented by
themselves. */
op1 = TREE_OPERAND (genop, 1);
*************** create_component_ref_by_pieces (basic_bl
*** 2195,2201 ****
case INDIRECT_REF:
{
tree op1 = TREE_OPERAND (genop, 0);
! tree genop1 = find_or_generate_expression (block, op1, stmts);
folded = fold_build1 (TREE_CODE (genop), TREE_TYPE (genop),
genop1);
--- 2212,2220 ----
case INDIRECT_REF:
{
tree op1 = TREE_OPERAND (genop, 0);
! tree genop1 = find_or_generate_expression (block, op1, stmts, domstmt);
! if (!genop1)
! return NULL_TREE;
folded = fold_build1 (TREE_CODE (genop), TREE_TYPE (genop),
genop1);
*************** create_component_ref_by_pieces (basic_bl
*** 2222,2233 ****
EXPR is the expression to find a leader or generate for.
STMTS is the statement list to put the inserted expressions on.
Returns the SSA_NAME of the LHS of the generated expression or the
! leader. */
static tree
! find_or_generate_expression (basic_block block, tree expr, tree stmts)
{
! tree genop = bitmap_find_leader (AVAIL_OUT (block), expr);
/* If it's still NULL, it must be a complex expression, so generate
it recursively. */
--- 2241,2257 ----
EXPR is the expression to find a leader or generate for.
STMTS is the statement list to put the inserted expressions on.
Returns the SSA_NAME of the LHS of the generated expression or the
! leader.
! DOMSTMT if non-NULL is a statement that should be dominated by
! all uses in the generated expression. If DOMSTMT is non-NULL this
! routine can fail and return NULL_TREE. Otherwise it will assert
! on failure. */
static tree
! find_or_generate_expression (basic_block block, tree expr, tree stmts,
! tree domstmt)
{
! tree genop = bitmap_find_leader (AVAIL_OUT (block), expr, domstmt);
/* If it's still NULL, it must be a complex expression, so generate
it recursively. */
*************** find_or_generate_expression (basic_block
*** 2247,2256 ****
if (can_PRE_operation (genop))
{
handled = true;
! genop = create_expression_by_pieces (block, genop, stmts);
break;
}
}
gcc_assert (handled);
}
return genop;
--- 2271,2284 ----
if (can_PRE_operation (genop))
{
handled = true;
! genop = create_expression_by_pieces (block, genop, stmts,
! domstmt);
break;
}
}
+ if (!handled && domstmt)
+ return NULL_TREE;
+
gcc_assert (handled);
}
return genop;
*************** find_or_generate_expression (basic_block
*** 2269,2278 ****
partially or fully redundant. Those that are will be either made
fully redundant during the next iteration of insert (for partially
redundant ones), or eliminated by eliminate (for fully redundant
! ones). */
static tree
! create_expression_by_pieces (basic_block block, tree expr, tree stmts)
{
tree temp, name;
tree folded, forced_stmts, newexpr;
--- 2297,2311 ----
partially or fully redundant. Those that are will be either made
fully redundant during the next iteration of insert (for partially
redundant ones), or eliminated by eliminate (for fully redundant
! ones).
!
! If DOMSTMT is non-NULL then we make sure that all uses in the
! expressions dominate that statement. In this case the function
! can return NULL_TREE to signal failure. */
static tree
! create_expression_by_pieces (basic_block block, tree expr, tree stmts,
! tree domstmt)
{
tree temp, name;
tree folded, forced_stmts, newexpr;
*************** create_expression_by_pieces (basic_block
*** 2293,2299 ****
fn = CALL_EXPR_FN (expr);
sc = CALL_EXPR_STATIC_CHAIN (expr);
! genfn = find_or_generate_expression (block, fn, stmts);
nargs = call_expr_nargs (expr);
buffer = (tree*) alloca (nargs * sizeof (tree));
--- 2326,2334 ----
fn = CALL_EXPR_FN (expr);
sc = CALL_EXPR_STATIC_CHAIN (expr);
! genfn = find_or_generate_expression (block, fn, stmts, domstmt);
! if (!genfn)
! return NULL_TREE;
nargs = call_expr_nargs (expr);
buffer = (tree*) alloca (nargs * sizeof (tree));
*************** create_expression_by_pieces (basic_block
*** 2301,2313 ****
for (i = 0; i < nargs; i++)
{
tree arg = CALL_EXPR_ARG (expr, i);
! buffer[i] = find_or_generate_expression (block, arg, stmts);
}
folded = build_call_array (TREE_TYPE (expr), genfn, nargs, buffer);
if (sc)
! CALL_EXPR_STATIC_CHAIN (folded) =
! find_or_generate_expression (block, sc, stmts);
folded = fold (folded);
break;
}
--- 2336,2355 ----
for (i = 0; i < nargs; i++)
{
tree arg = CALL_EXPR_ARG (expr, i);
! buffer[i] = find_or_generate_expression (block, arg, stmts,
! domstmt);
! if (!buffer[i])
! return NULL_TREE;
}
folded = build_call_array (TREE_TYPE (expr), genfn, nargs, buffer);
if (sc)
! {
! CALL_EXPR_STATIC_CHAIN (folded) =
! find_or_generate_expression (block, sc, stmts, domstmt);
! if (!CALL_EXPR_STATIC_CHAIN (folded))
! return NULL_TREE;
! }
folded = fold (folded);
break;
}
*************** create_expression_by_pieces (basic_block
*** 2317,2328 ****
if (TREE_CODE (expr) == COMPONENT_REF
|| TREE_CODE (expr) == ARRAY_REF)
{
! folded = create_component_ref_by_pieces (block, expr, stmts);
}
else
{
tree op1 = TREE_OPERAND (expr, 0);
! tree genop1 = find_or_generate_expression (block, op1, stmts);
folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr),
genop1);
--- 2359,2376 ----
if (TREE_CODE (expr) == COMPONENT_REF
|| TREE_CODE (expr) == ARRAY_REF)
{
! folded = create_component_ref_by_pieces (block, expr, stmts,
! domstmt);
! if (!folded)
! return NULL_TREE;
}
else
{
tree op1 = TREE_OPERAND (expr, 0);
! tree genop1 = find_or_generate_expression (block, op1, stmts,
! domstmt);
! if (!genop1)
! return NULL_TREE;
folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr),
genop1);
*************** create_expression_by_pieces (basic_block
*** 2335,2342 ****
{
tree op1 = TREE_OPERAND (expr, 0);
tree op2 = TREE_OPERAND (expr, 1);
! tree genop1 = find_or_generate_expression (block, op1, stmts);
! tree genop2 = find_or_generate_expression (block, op2, stmts);
folded = fold_build2 (TREE_CODE (expr), TREE_TYPE (expr),
genop1, genop2);
break;
--- 2383,2392 ----
{
tree op1 = TREE_OPERAND (expr, 0);
tree op2 = TREE_OPERAND (expr, 1);
! tree genop1 = find_or_generate_expression (block, op1, stmts, domstmt);
! tree genop2 = find_or_generate_expression (block, op2, stmts, domstmt);
! if (!genop1 || !genop2)
! return NULL_TREE;
folded = fold_build2 (TREE_CODE (expr), TREE_TYPE (expr),
genop1, genop2);
break;
*************** create_expression_by_pieces (basic_block
*** 2345,2351 ****
case tcc_unary:
{
tree op1 = TREE_OPERAND (expr, 0);
! tree genop1 = find_or_generate_expression (block, op1, stmts);
folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr),
genop1);
break;
--- 2395,2403 ----
case tcc_unary:
{
tree op1 = TREE_OPERAND (expr, 0);
! tree genop1 = find_or_generate_expression (block, op1, stmts, domstmt);
! if (!genop1)
! return NULL_TREE;
folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr),
genop1);
break;
*************** create_expression_by_pieces (basic_block
*** 2421,2427 ****
vn_add (name, v);
VN_INFO_GET (name)->valnum = name;
get_or_alloc_expression_id (name);
! bitmap_value_replace_in_set (NEW_SETS (block), name);
bitmap_value_replace_in_set (AVAIL_OUT (block), name);
pre_stats.insertions++;
--- 2473,2480 ----
vn_add (name, v);
VN_INFO_GET (name)->valnum = name;
get_or_alloc_expression_id (name);
! if (!in_fre)
! bitmap_value_replace_in_set (NEW_SETS (block), name);
bitmap_value_replace_in_set (AVAIL_OUT (block), name);
pre_stats.insertions++;
*************** insert_into_preds_of_block (basic_block
*** 2497,2503 ****
{
builtexpr = create_expression_by_pieces (bprime,
eprime,
! stmts);
gcc_assert (!(pred->flags & EDGE_ABNORMAL));
bsi_insert_on_edge (pred, stmts);
avail[bprime->index] = builtexpr;
--- 2550,2556 ----
{
builtexpr = create_expression_by_pieces (bprime,
eprime,
! stmts, NULL_TREE);
gcc_assert (!(pred->flags & EDGE_ABNORMAL));
bsi_insert_on_edge (pred, stmts);
avail[bprime->index] = builtexpr;
*************** do_regular_insertion (basic_block block,
*** 2659,2665 ****
vprime = get_value_handle (eprime);
gcc_assert (vprime);
edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
! vprime);
if (edoubleprime == NULL)
{
avail[bprime->index] = eprime;
--- 2712,2718 ----
vprime = get_value_handle (eprime);
gcc_assert (vprime);
edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
! vprime, NULL_TREE);
if (edoubleprime == NULL)
{
avail[bprime->index] = eprime;
*************** do_partial_partial_insertion (basic_bloc
*** 2788,2794 ****
vprime = get_value_handle (eprime);
gcc_assert (vprime);
edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
! vprime);
if (edoubleprime == NULL)
{
by_all = false;
--- 2841,2847 ----
vprime = get_value_handle (eprime);
gcc_assert (vprime);
edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
! vprime, NULL_TREE);
if (edoubleprime == NULL)
{
by_all = false;
*************** find_existing_value_expr (tree t, VEC (t
*** 2970,2979 ****
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. */
static inline tree
! create_value_expr_from (tree expr, basic_block block, VEC (tree, gc) *vuses)
{
int i;
enum tree_code code = TREE_CODE (expr);
--- 3023,3036 ----
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.
!
! If CHECK_AVAIL is true, checks availability of each operand in
! BLOCKs AVAIL_OUT set. */
static inline tree
! create_value_expr_from (tree expr, basic_block block, VEC (tree, gc) *vuses,
! bool check_avail)
{
int i;
enum tree_code code = TREE_CODE (expr);
*************** create_value_expr_from (tree expr, basic
*** 3021,3027 ****
/* Recursively value-numberize reference ops and tree lists. */
if (REFERENCE_CLASS_P (op))
{
! tree tempop = create_value_expr_from (op, block, vuses);
op = tempop ? tempop : op;
val = vn_lookup_or_add_with_vuses (op, vuses);
set_expression_vuses (op, vuses);
--- 3078,3084 ----
/* Recursively value-numberize reference ops and tree lists. */
if (REFERENCE_CLASS_P (op))
{
! tree tempop = create_value_expr_from (op, block, vuses, check_avail);
op = tempop ? tempop : op;
val = vn_lookup_or_add_with_vuses (op, vuses);
set_expression_vuses (op, vuses);
*************** create_value_expr_from (tree expr, basic
*** 3037,3042 ****
--- 3094,3104 ----
TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i));
TREE_OPERAND (vexpr, i) = val;
+
+ if (check_avail
+ && TREE_CODE (val) == VALUE_HANDLE
+ && !bitmap_set_contains_value (AVAIL_OUT (block), val))
+ return NULL_TREE;
}
efi = find_existing_value_expr (vexpr, vuses);
if (efi)
*************** make_values_for_stmt (tree stmt, basic_b
*** 3271,3282 ****
vuses = copy_vuses_from_stmt (stmt);
STRIP_USELESS_TYPE_CONVERSION (rhs);
if (can_value_number_operation (rhs)
! && (!lhsval || !is_gimple_min_invariant (lhsval)))
{
/* 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, vuses);
if (newt)
{
set_expression_vuses (newt, vuses);
--- 3333,3345 ----
vuses = copy_vuses_from_stmt (stmt);
STRIP_USELESS_TYPE_CONVERSION (rhs);
if (can_value_number_operation (rhs)
! && (!lhsval || !is_gimple_min_invariant (lhsval))
! && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
{
/* 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, vuses, false);
if (newt)
{
set_expression_vuses (newt, vuses);
*************** compute_avail (void)
*** 3480,3487 ****
else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
&& !ann->has_volatile_ops
&& TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME
- && (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI
- (GIMPLE_STMT_OPERAND (stmt, 0)))
&& !tree_could_throw_p (stmt))
{
if (make_values_for_stmt (stmt, block))
--- 3543,3548 ----
*************** compute_avail (void)
*** 3510,3515 ****
--- 3571,3606 ----
free (worklist);
}
+ /* Insert the expression for SSA_VN that SCCVN thought would be simpler
+ than the available expressions for it. The insertion point is
+ right before the first use in STMT. Returns the SSA_NAME that should
+ be used for replacement. */
+
+ static tree
+ do_SCCVN_insertion (tree stmt, tree ssa_vn)
+ {
+ basic_block bb = bb_for_stmt (stmt);
+ block_stmt_iterator bsi;
+ tree expr, stmts;
+
+ /* First create a value expression from the expression we want
+ to insert and associate it with the value handle for SSA_VN. */
+ expr = create_value_expr_from (VN_INFO (ssa_vn)->expr, bb, NULL, true);
+ if (expr == NULL_TREE)
+ return NULL_TREE;
+ set_value_handle (expr, get_value_handle (ssa_vn));
+
+ /* Then use create_expression_by_pieces to generate a valid
+ expression to insert at this point of the IL stream. */
+ stmts = alloc_stmt_list ();
+ expr = create_expression_by_pieces (bb, expr, stmts, stmt);
+ if (expr == NULL_TREE)
+ return NULL_TREE;
+ bsi = bsi_for_stmt (stmt);
+ bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
+
+ return expr;
+ }
/* Eliminate fully redundant computations. */
*************** eliminate (void)
*** 3540,3546 ****
tree sprime;
sprime = bitmap_find_leader (AVAIL_OUT (b),
! get_value_handle (lhs));
if (sprime
&& sprime != lhs
--- 3631,3650 ----
tree sprime;
sprime = bitmap_find_leader (AVAIL_OUT (b),
! get_value_handle (lhs), NULL_TREE);
!
! /* If there is no existing usable leader but SCCVN thinks
! it has an expression it wants to use as replacement,
! insert that. */
! if (!sprime
! || sprime == lhs)
! {
! tree val = VN_INFO (lhs)->valnum;
! if (val != VN_TOP
! && VN_INFO (val)->needs_insertion
! && can_PRE_operation (VN_INFO (val)->expr))
! sprime = do_SCCVN_insertion (stmt, val);
! }
if (sprime
&& sprime != lhs
*************** execute_pre (bool do_fre)
*** 3837,3843 ****
insert_fake_stores ();
/* Collect and value number expressions computed in each basic block. */
! if (!run_scc_vn ())
{
if (!do_fre)
remove_dead_inserted_code ();
--- 3941,3947 ----
insert_fake_stores ();
/* Collect and value number expressions computed in each basic block. */
! if (!run_scc_vn (do_fre))
{
if (!do_fre)
remove_dead_inserted_code ();
*************** execute_pre (bool do_fre)
*** 3885,3892 ****
}
bsi_commit_edge_inserts ();
- free_scc_vn ();
clear_expression_ids ();
if (!do_fre)
{
remove_dead_inserted_code ();
--- 3989,3996 ----
}
bsi_commit_edge_inserts ();
clear_expression_ids ();
+ free_scc_vn ();
if (!do_fre)
{
remove_dead_inserted_code ();
Index: trunk/gcc/tree-ssa-sccvn.c
===================================================================
*** trunk.orig/gcc/tree-ssa-sccvn.c 2008-03-13 15:34:33.000000000 +0100
--- trunk/gcc/tree-ssa-sccvn.c 2008-03-14 11:29:57.000000000 +0100
*************** tree VN_TOP;
*** 221,226 ****
--- 221,229 ----
static unsigned int next_dfs_num;
static VEC (tree, heap) *sccstack;
+ static bool may_insert;
+
+
DEF_VEC_P(vn_ssa_aux_t);
DEF_VEC_ALLOC_P(vn_ssa_aux_t, heap);
*************** copy_reference_ops_from_ref (tree ref, V
*** 525,532 ****
temp.op1 = TREE_OPERAND (ref, 2);
break;
case COMPONENT_REF:
! /* Record field as operand. */
! temp.op0 = TREE_OPERAND (ref, 1);
break;
case ARRAY_RANGE_REF:
case ARRAY_REF:
--- 528,548 ----
temp.op1 = TREE_OPERAND (ref, 2);
break;
case COMPONENT_REF:
! /* If this is a reference to a union member, record the union
! member size as operand. Do so only if we are doing
! expression insertion (during FRE), as PRE currently gets
! confused with this. */
! if (may_insert
! && TREE_CODE (DECL_CONTEXT (TREE_OPERAND (ref, 1))) == UNION_TYPE
! && integer_zerop (DECL_FIELD_OFFSET (TREE_OPERAND (ref, 1)))
! && integer_zerop (DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1))))
! {
! temp.type = NULL_TREE;
! temp.op0 = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (ref, 1)));
! }
! else
! /* Record field as operand. */
! temp.op0 = TREE_OPERAND (ref, 1);
break;
case ARRAY_RANGE_REF:
case ARRAY_REF:
*************** defs_to_varying (tree stmt)
*** 1017,1022 ****
--- 1033,1041 ----
return changed;
}
+ static tree
+ try_to_simplify (tree stmt, tree rhs);
+
/* Visit a copy between LHS and RHS, return true if the value number
changed. */
*************** visit_reference_op_load (tree lhs, tree
*** 1089,1094 ****
--- 1108,1171 ----
bool changed = false;
tree result = vn_reference_lookup (op, shared_vuses_from_stmt (stmt));
+ /* We handle type-punning through unions by value-numbering based
+ on offset and size of the access. Be prepared to handle a
+ type-mismatch here via creating a VIEW_CONVERT_EXPR. */
+ if (result
+ && !useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (op)))
+ {
+ /* We will be setting the value number of lhs to the value number
+ of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
+ So first simplify and lookup this expression to see if it
+ is already available. */
+ tree val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (op), result);
+ if (stmt
+ && !is_gimple_min_invariant (val)
+ && TREE_CODE (val) != SSA_NAME)
+ {
+ tree tem = try_to_simplify (stmt, val);
+ if (tem)
+ val = tem;
+ }
+ result = val;
+ if (!is_gimple_min_invariant (val)
+ && TREE_CODE (val) != SSA_NAME)
+ result = vn_nary_op_lookup (val);
+ /* If the expression is not yet available, value-number lhs to
+ a new SSA_NAME we create. */
+ if (!result && may_insert)
+ {
+ result = make_ssa_name (SSA_NAME_VAR (lhs), NULL_TREE);
+ /* Initialize value-number information properly. */
+ VN_INFO_GET (result)->valnum = result;
+ VN_INFO (result)->expr = val;
+ VN_INFO (result)->needs_insertion = true;
+ /* As all "inserted" statements are singleton SCCs, insert
+ to the valid table. This is strictly needed to
+ avoid re-generating new value SSA_NAMEs for the same
+ expression during SCC iteration over and over (the
+ optimistic table gets cleared after each iteration).
+ We do not need to insert into the optimistic table, as
+ lookups there will fall back to the valid table. */
+ if (current_info == optimistic_info)
+ {
+ current_info = valid_info;
+ vn_nary_op_insert (val, result);
+ current_info = optimistic_info;
+ }
+ else
+ vn_nary_op_insert (val, result);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Inserting name ");
+ print_generic_expr (dump_file, result, 0);
+ fprintf (dump_file, " for expression ");
+ print_generic_expr (dump_file, val, 0);
+ fprintf (dump_file, "\n");
+ }
+ }
+ }
+
if (result)
{
changed = set_ssa_val_to (lhs, result);
*************** visit_use (tree use)
*** 1496,1502 ****
VN_INFO (use)->use_processed = true;
gcc_assert (!SSA_NAME_IN_FREE_LIST (use));
! if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Value numbering ");
print_generic_expr (dump_file, use, 0);
--- 1573,1580 ----
VN_INFO (use)->use_processed = true;
gcc_assert (!SSA_NAME_IN_FREE_LIST (use));
! if (dump_file && (dump_flags & TDF_DETAILS)
! && !IS_EMPTY_STMT (stmt))
{
fprintf (dump_file, "Value numbering ");
print_generic_expr (dump_file, use, 0);
*************** visit_use (tree use)
*** 1607,1612 ****
--- 1685,1693 ----
}
if (TREE_CODE (lhs) == SSA_NAME
+ /* We can substitute SSA_NAMEs that are live over
+ abnormal edges with their constant value. */
+ && !is_gimple_min_invariant (rhs)
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
changed = defs_to_varying (stmt);
else if (REFERENCE_CLASS_P (lhs) || DECL_P (lhs))
*************** free_scc_vn (void)
*** 1985,1990 ****
--- 2066,2074 ----
&& SSA_NAME_VALUE (name)
&& TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE)
SSA_NAME_VALUE (name) = NULL;
+ if (name
+ && VN_INFO (name)->needs_insertion)
+ release_ssa_name (name);
}
obstack_free (&vn_ssa_aux_obstack, NULL);
VEC_free (vn_ssa_aux_t, heap, vn_ssa_aux_table);
*************** free_scc_vn (void)
*** 2005,2015 ****
due to ressource constraints. */
bool
! run_scc_vn (void)
{
size_t i;
tree param;
init_scc_vn ();
current_info = valid_info;
--- 2089,2101 ----
due to ressource constraints. */
bool
! run_scc_vn (bool may_insert_arg)
{
size_t i;
tree param;
+ may_insert = may_insert_arg;
+
init_scc_vn ();
current_info = valid_info;
*************** run_scc_vn (void)
*** 2024,2030 ****
}
}
! for (i = num_ssa_names - 1; i > 0; i--)
{
tree name = ssa_name (i);
if (name
--- 2110,2116 ----
}
}
! for (i = 1; i < num_ssa_names; ++i)
{
tree name = ssa_name (i);
if (name
*************** run_scc_vn (void)
*** 2033,2038 ****
--- 2119,2125 ----
if (!DFS (name))
{
free_scc_vn ();
+ may_insert = false;
return false;
}
}
*************** run_scc_vn (void)
*** 2058,2062 ****
--- 2145,2150 ----
}
}
+ may_insert = false;
return true;
}
Index: trunk/gcc/tree-ssa-sccvn.h
===================================================================
*** trunk.orig/gcc/tree-ssa-sccvn.h 2008-03-13 15:34:33.000000000 +0100
--- trunk/gcc/tree-ssa-sccvn.h 2008-03-13 15:34:41.000000000 +0100
*************** typedef struct vn_ssa_aux
*** 44,55 ****
once. It cannot be used to avoid visitation for SSA_NAME's
involved in non-singleton SCC's. */
unsigned use_processed : 1;
} *vn_ssa_aux_t;
/* Return the value numbering info for an SSA_NAME. */
extern vn_ssa_aux_t VN_INFO (tree);
extern vn_ssa_aux_t VN_INFO_GET (tree);
! bool run_scc_vn (void);
void free_scc_vn (void);
void switch_to_PRE_table (void);
tree vn_nary_op_lookup (tree);
--- 44,60 ----
once. It cannot be used to avoid visitation for SSA_NAME's
involved in non-singleton SCC's. */
unsigned use_processed : 1;
+
+ /* Whether the SSA_NAME has no defining statement and thus an
+ insertion of such with EXPR as definition is required before
+ a use can be created of it. */
+ unsigned needs_insertion : 1;
} *vn_ssa_aux_t;
/* Return the value numbering info for an SSA_NAME. */
extern vn_ssa_aux_t VN_INFO (tree);
extern vn_ssa_aux_t VN_INFO_GET (tree);
! bool run_scc_vn (bool);
void free_scc_vn (void);
void switch_to_PRE_table (void);
tree vn_nary_op_lookup (tree);
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-7.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-7.c 2008-03-13 15:34:41.000000000 +0100
***************
*** 0 ****
--- 1,31 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fdump-tree-fre-details -fdump-tree-optimized" } */
+
+ struct X {
+ int i;
+ union {
+ int j;
+ int k;
+ float f;
+ } u;
+ };
+
+ int foo(int j)
+ {
+ struct X a;
+
+ a.u.j = j;
+ a.u.f = a.u.f;
+ a.u.f = a.u.f;
+ a.u.j = a.u.j;
+ a.u.f = a.u.f;
+ return a.u.k;
+ }
+
+ /* { dg-final { scan-tree-dump-times "Inserted pretmp" 1 "fre" } } */
+ /* { dg-final { scan-tree-dump-times "Replaced a.u.f with pretmp" 3 "fre" } } */
+ /* { dg-final { scan-tree-dump-times "Replaced a.u.k with j" 1 "fre" } } */
+ /* { dg-final { scan-tree-dump "= VIEW_CONVERT_EXPR<float>\\\(j_" "fre" } } */
+ /* { dg-final { scan-tree-dump "return j" "optimized" } } */
+ /* { dg-final { cleanup-tree-dump "fre" } } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-8.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-8.c 2008-03-13 15:34:41.000000000 +0100
***************
*** 0 ****
--- 1,27 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fdump-tree-fre-details" } */
+
+ union U {
+ int i;
+ float f;
+ };
+ int foo(int i, int b)
+ {
+ union U u;
+ if (b)
+ {
+ i = i << 2;
+ u.i = i;
+ return u.f;
+ }
+ else
+ {
+ i = i << 2;
+ u.i = i;
+ return u.f;
+ }
+ }
+
+ /* { dg-final { scan-tree-dump-times "Replaced u.f with pretmp" 2 "fre" } } */
+ /* { dg-final { scan-tree-dump-times "Inserted pretmp" 2 "fre" } } */
+ /* { dg-final { cleanup-tree-dump "fre" } } */
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-17.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-17.c 2008-03-13 15:34:41.000000000 +0100
***************
*** 0 ****
--- 1,18 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-pre-stats" } */
+
+ typedef union {
+ int i;
+ float f;
+ } U;
+
+ int foo(U *u, int b, int i)
+ {
+ u->i = 0;
+ if (b)
+ u->i = i;
+ return u->i;
+ }
+
+ /* { dg-final { scan-tree-dump "Eliminated: 1" "pre" } } */
+ /* { dg-final { cleanup-tree-dump "pre" } } */
Index: trunk/gcc/fold-const.c
===================================================================
*** trunk.orig/gcc/fold-const.c 2008-03-13 15:34:33.000000000 +0100
--- trunk/gcc/fold-const.c 2008-03-13 15:34:41.000000000 +0100
*************** fold_unary (enum tree_code code, tree ty
*** 7941,7959 ****
/* For integral conversions with the same precision or pointer
conversions use a NOP_EXPR instead. */
! if ((INTEGRAL_TYPE_P (type) && INTEGRAL_TYPE_P (TREE_TYPE (op0))
! && TYPE_PRECISION (type) == TYPE_PRECISION (TREE_TYPE (op0))
! /* Do not muck with VIEW_CONVERT_EXPRs that convert from
! a sub-type to its base type as generated by the Ada FE. */
! && !TREE_TYPE (TREE_TYPE (op0)))
! || (POINTER_TYPE_P (type) && POINTER_TYPE_P (TREE_TYPE (op0))))
return fold_convert (type, op0);
/* Strip inner integral conversions that do not change the precision. */
if ((TREE_CODE (op0) == NOP_EXPR
|| TREE_CODE (op0) == CONVERT_EXPR)
! && INTEGRAL_TYPE_P (TREE_TYPE (op0))
! && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (op0, 0)))
&& (TYPE_PRECISION (TREE_TYPE (op0))
== TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op0, 0)))))
return fold_build1 (VIEW_CONVERT_EXPR, type, TREE_OPERAND (op0, 0));
--- 7941,7964 ----
/* For integral conversions with the same precision or pointer
conversions use a NOP_EXPR instead. */
! if ((INTEGRAL_TYPE_P (type)
! || POINTER_TYPE_P (type))
! && (INTEGRAL_TYPE_P (TREE_TYPE (op0))
! || POINTER_TYPE_P (TREE_TYPE (op0)))
! && TYPE_PRECISION (type) == TYPE_PRECISION (TREE_TYPE (op0))
! /* Do not muck with VIEW_CONVERT_EXPRs that convert from
! a sub-type to its base type as generated by the Ada FE. */
! && !(INTEGRAL_TYPE_P (TREE_TYPE (op0))
! && TREE_TYPE (TREE_TYPE (op0))))
return fold_convert (type, op0);
/* Strip inner integral conversions that do not change the precision. */
if ((TREE_CODE (op0) == NOP_EXPR
|| TREE_CODE (op0) == CONVERT_EXPR)
! && (INTEGRAL_TYPE_P (TREE_TYPE (op0))
! || POINTER_TYPE_P (TREE_TYPE (op0)))
! && (INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (op0, 0)))
! || POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (op0, 0))))
&& (TYPE_PRECISION (TREE_TYPE (op0))
== TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op0, 0)))))
return fold_build1 (VIEW_CONVERT_EXPR, type, TREE_OPERAND (op0, 0));
Index: trunk/gcc/tree-ssa-loop-im.c
===================================================================
*** trunk.orig/gcc/tree-ssa-loop-im.c 2008-03-13 15:34:33.000000000 +0100
--- trunk/gcc/tree-ssa-loop-im.c 2008-03-13 15:34:41.000000000 +0100
*************** for_each_index (tree *addr_p, bool (*cbc
*** 208,213 ****
--- 208,217 ----
case CONSTRUCTOR:
return true;
+ case ADDR_EXPR:
+ gcc_assert (is_gimple_min_invariant (*addr_p));
+ return true;
+
case TARGET_MEM_REF:
idx = &TMR_BASE (*addr_p);
if (*idx
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-9.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-9.c 2008-03-13 15:34:41.000000000 +0100
***************
*** 0 ****
--- 1,28 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fdump-tree-fre-stats" } */
+
+ union loc {
+ unsigned reg;
+ signed offset;
+ };
+ void __frame_state_for2 (char *state_in)
+ {
+ union loc fs;
+ {
+ *state_in = fs.reg;
+ *state_in = fs.offset;
+ }
+ }
+ void __frame_state_for1 (char *state_in)
+ {
+ union loc fs;
+ for (;;)
+ {
+ *state_in = fs.offset;
+ *state_in = fs.reg;
+ }
+ }
+
+ /* { dg-final { scan-tree-dump-times "Eliminated: 1" 2 "fre" } } */
+ /* { dg-final { scan-tree-dump-times "Insertions: 1" 2 "fre" } } */
+ /* { dg-final { cleanup-tree-dump "fre" } } */
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-10.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-10.c 2008-03-13 15:34:41.000000000 +0100
***************
*** 0 ****
--- 1,20 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-pre-stats" } */
+
+ union loc { unsigned reg; signed offset; };
+ void __frame_state_for (char *state_in, int x)
+ {
+ union loc fs;
+ int reg;
+ for (;;) {
+ switch (x) {
+ case 0:
+ *state_in = fs.reg;
+ case 1:
+ *state_in = fs.offset;
+ }
+ }
+ }
+
+ /* { dg-final { scan-tree-dump "Insertions: 0" "pre" } } */
+ /* { dg-final { cleanup-tree-dump "pre" } } */
More information about the Gcc-patches
mailing list