[PATCH][match-and-simplify] Convert SCCVN
Richard Biener
rguenther@suse.de
Tue Mar 11 15:28:00 GMT 2014
This converts remaining parts of SCCVN to use the
gimple_match_and_simplify interface. Most importantly
(apart from one legacy case) we no longer build GENERIC
trees from GIMPLE to do simplification nor track
whether it's maybe worthwhile doing so.
Committed to branch (a few more optimization regressions due
to missed patterns appear).
Richard.
2014-03-11 Richard Biener <rguenther@suse.de>
* tree-ssa-sccvn.h (struct vn_ssa_aux): Remove has_constants
member.
* tree-ssa-sccvn.c (vn_get_expr_for): Simplify for legacy PRE use.
(visit_copy): Do not set or use has_constants or expr.
(visit_reference_op_call): Likewise.
(visit_phi): Likewise.
(visit_use): Likewise.
(visit_reference_op_load): Simplify result using
gimple_match_and_simplify.
(expr_has_constants, stmt_has_constants, valueize_expr,
simplify_binary_expression, simplify_unary_expression): Remove.
(try_to_simplify): Do not use gimple_fold_stmt_to_constant_1.
Index: gcc/tree-ssa-sccvn.c
===================================================================
*** gcc/tree-ssa-sccvn.c (revision 208478)
--- gcc/tree-ssa-sccvn.c (working copy)
*************** tree
*** 383,392 ****
vn_get_expr_for (tree name)
{
vn_ssa_aux_t vn = VN_INFO (name);
- gimple def_stmt;
- tree expr = NULL_TREE;
- enum tree_code code;
-
if (vn->valnum == VN_TOP)
return name;
--- 383,388 ----
*************** vn_get_expr_for (tree name)
*** 407,464 ****
if (vn->expr != NULL_TREE)
return vn->expr;
! /* Otherwise use the defining statement to build the expression. */
! def_stmt = SSA_NAME_DEF_STMT (vn->valnum);
!
! /* If the value number is not an assignment use it directly. */
! if (!is_gimple_assign (def_stmt))
! return vn->valnum;
!
! /* FIXME tuples. This is incomplete and likely will miss some
! simplifications. */
! code = gimple_assign_rhs_code (def_stmt);
! switch (TREE_CODE_CLASS (code))
! {
! case tcc_reference:
! if ((code == REALPART_EXPR
! || code == IMAGPART_EXPR
! || code == VIEW_CONVERT_EXPR)
! && TREE_CODE (TREE_OPERAND (gimple_assign_rhs1 (def_stmt),
! 0)) == SSA_NAME)
! expr = fold_build1 (code,
! gimple_expr_type (def_stmt),
! TREE_OPERAND (gimple_assign_rhs1 (def_stmt), 0));
! break;
!
! case tcc_unary:
! expr = fold_build1 (code,
! gimple_expr_type (def_stmt),
! gimple_assign_rhs1 (def_stmt));
! break;
!
! case tcc_binary:
! expr = fold_build2 (code,
! gimple_expr_type (def_stmt),
! gimple_assign_rhs1 (def_stmt),
! gimple_assign_rhs2 (def_stmt));
! break;
!
! case tcc_exceptional:
! if (code == CONSTRUCTOR
! && TREE_CODE
! (TREE_TYPE (gimple_assign_rhs1 (def_stmt))) == VECTOR_TYPE)
! expr = gimple_assign_rhs1 (def_stmt);
! break;
!
! default:;
! }
! if (expr == NULL_TREE)
! return vn->valnum;
!
! /* Cache the expression. */
! vn->expr = expr;
!
! return expr;
}
/* Return the vn_kind the expression computed by the stmt should be
--- 403,410 ----
if (vn->expr != NULL_TREE)
return vn->expr;
! /* If not, return the value-number. */
! return vn->valnum;
}
/* Return the vn_kind the expression computed by the stmt should be
*************** defs_to_varying (gimple stmt)
*** 2727,2746 ****
return changed;
}
- static bool expr_has_constants (tree expr);
- static tree valueize_expr (tree expr);
-
/* Visit a copy between LHS and RHS, return true if the value number
changed. */
static bool
visit_copy (tree lhs, tree rhs)
{
- /* The copy may have a more interesting constant filled expression
- (we don't, since we know our RHS is just an SSA name). */
- VN_INFO (lhs)->has_constants = VN_INFO (rhs)->has_constants;
- VN_INFO (lhs)->expr = VN_INFO (rhs)->expr;
-
/* And finally valueize. */
rhs = SSA_VAL (rhs);
--- 2673,2684 ----
*************** visit_reference_op_call (tree lhs, gimpl
*** 2799,2810 ****
vnresult->result = lhs;
if (vnresult->result && lhs)
! {
! changed |= set_ssa_val_to (lhs, vnresult->result);
!
! if (VN_INFO (vnresult->result)->has_constants)
! VN_INFO (lhs)->has_constants = true;
! }
}
else
{
--- 2737,2743 ----
vnresult->result = lhs;
if (vnresult->result && lhs)
! changed |= set_ssa_val_to (lhs, vnresult->result);
}
else
{
*************** visit_reference_op_load (tree lhs, tree
*** 2864,2896 ****
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 ((CONVERT_EXPR_P (val)
! || TREE_CODE (val) == VIEW_CONVERT_EXPR)
! && TREE_CODE (TREE_OPERAND (val, 0)) == SSA_NAME)
! {
! tree tem = valueize_expr (vn_get_expr_for (TREE_OPERAND (val, 0)));
! if ((CONVERT_EXPR_P (tem)
! || TREE_CODE (tem) == VIEW_CONVERT_EXPR)
! && (tem = fold_unary_ignore_overflow (TREE_CODE (val),
! TREE_TYPE (val), tem)))
! val = tem;
! }
! result = val;
! if (!is_gimple_min_invariant (val)
! && TREE_CODE (val) != SSA_NAME)
! result = vn_nary_op_lookup (val, NULL);
/* If the expression is not yet available, value-number lhs to
a new SSA_NAME we create. */
! if (!result)
{
result = make_temp_ssa_name (TREE_TYPE (lhs), gimple_build_nop (),
"vntemp");
/* Initialize value-number information properly. */
VN_INFO_GET (result)->valnum = result;
VN_INFO (result)->value_id = get_next_value_id ();
VN_INFO (result)->expr = val;
- VN_INFO (result)->has_constants = expr_has_constants (val);
VN_INFO (result)->needs_insertion = true;
/* As all "inserted" statements are singleton SCCs, insert
to the valid table. This is strictly needed to
--- 2797,2820 ----
of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result).
So first simplify and lookup this expression to see if it
is already available. */
! tree val = gimple_match_and_simplify (VIEW_CONVERT_EXPR, TREE_TYPE (op),
! result, NULL, vn_valueize);
! if (!val)
! val = vn_nary_op_lookup_pieces (1, VIEW_CONVERT_EXPR,
! TREE_TYPE (op), &result, NULL);
/* If the expression is not yet available, value-number lhs to
a new SSA_NAME we create. */
! if (!val)
{
+ /* ??? Instead of recording a tree here we should use
+ gimple_build and record a sequence in VN_INFO->expr. */
+ val = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (op), result);
result = make_temp_ssa_name (TREE_TYPE (lhs), gimple_build_nop (),
"vntemp");
/* Initialize value-number information properly. */
VN_INFO_GET (result)->valnum = result;
VN_INFO (result)->value_id = get_next_value_id ();
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
*************** visit_reference_op_load (tree lhs, tree
*** 2916,2933 ****
fprintf (dump_file, "\n");
}
}
}
if (result)
! {
! changed = set_ssa_val_to (lhs, result);
! if (TREE_CODE (result) == SSA_NAME
! && VN_INFO (result)->has_constants)
! {
! VN_INFO (lhs)->expr = VN_INFO (result)->expr;
! VN_INFO (lhs)->has_constants = true;
! }
! }
else
{
changed = set_ssa_val_to (lhs, lhs);
--- 2840,2851 ----
fprintf (dump_file, "\n");
}
}
+ else
+ result = val;
}
if (result)
! changed = set_ssa_val_to (lhs, result);
else
{
changed = set_ssa_val_to (lhs, lhs);
*************** visit_phi (gimple phi)
*** 3075,3091 ****
value. */
if (allsame)
{
- if (is_gimple_min_invariant (sameval))
- {
- VN_INFO (PHI_RESULT (phi))->has_constants = true;
- VN_INFO (PHI_RESULT (phi))->expr = sameval;
- }
- else
- {
- VN_INFO (PHI_RESULT (phi))->has_constants = false;
- VN_INFO (PHI_RESULT (phi))->expr = sameval;
- }
-
if (TREE_CODE (sameval) == SSA_NAME)
return visit_copy (PHI_RESULT (phi), sameval);
--- 2993,2998 ----
*************** visit_phi (gimple phi)
*** 3104,3357 ****
else
{
vn_phi_insert (phi, PHI_RESULT (phi));
- VN_INFO (PHI_RESULT (phi))->has_constants = false;
- VN_INFO (PHI_RESULT (phi))->expr = PHI_RESULT (phi);
changed = set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
}
return changed;
}
- /* Return true if EXPR contains constants. */
-
- static bool
- expr_has_constants (tree expr)
- {
- switch (TREE_CODE_CLASS (TREE_CODE (expr)))
- {
- case tcc_unary:
- return is_gimple_min_invariant (TREE_OPERAND (expr, 0));
-
- case tcc_binary:
- return is_gimple_min_invariant (TREE_OPERAND (expr, 0))
- || is_gimple_min_invariant (TREE_OPERAND (expr, 1));
- /* 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);
- }
- return false;
- }
-
- /* Return true if STMT contains constants. */
-
- static bool
- stmt_has_constants (gimple stmt)
- {
- tree tem;
-
- if (gimple_code (stmt) != GIMPLE_ASSIGN)
- return false;
-
- switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
- {
- case GIMPLE_TERNARY_RHS:
- tem = gimple_assign_rhs3 (stmt);
- if (TREE_CODE (tem) == SSA_NAME)
- tem = SSA_VAL (tem);
- if (is_gimple_min_invariant (tem))
- return true;
- /* Fallthru. */
-
- case GIMPLE_BINARY_RHS:
- tem = gimple_assign_rhs2 (stmt);
- if (TREE_CODE (tem) == SSA_NAME)
- tem = SSA_VAL (tem);
- if (is_gimple_min_invariant (tem))
- return true;
- /* Fallthru. */
-
- case GIMPLE_SINGLE_RHS:
- /* Constants inside reference ops are rarely interesting, but
- it can take a lot of looking to find them. */
- case GIMPLE_UNARY_RHS:
- tem = gimple_assign_rhs1 (stmt);
- if (TREE_CODE (tem) == SSA_NAME)
- tem = SSA_VAL (tem);
- return is_gimple_min_invariant (tem);
-
- default:
- gcc_unreachable ();
- }
- return false;
- }
-
- /* Replace SSA_NAMES in expr with their value numbers, and return the
- result.
- This is performed in place. */
-
- static tree
- valueize_expr (tree expr)
- {
- switch (TREE_CODE_CLASS (TREE_CODE (expr)))
- {
- case tcc_binary:
- TREE_OPERAND (expr, 1) = vn_valueize (TREE_OPERAND (expr, 1));
- /* Fallthru. */
- case tcc_unary:
- TREE_OPERAND (expr, 0) = vn_valueize (TREE_OPERAND (expr, 0));
- break;
- default:;
- }
- return expr;
- }
-
- /* Simplify the binary expression RHS, and return the result if
- simplified. */
-
- static tree
- simplify_binary_expression (gimple stmt)
- {
- tree result = NULL_TREE;
- tree op0 = gimple_assign_rhs1 (stmt);
- tree op1 = gimple_assign_rhs2 (stmt);
- enum tree_code code = gimple_assign_rhs_code (stmt);
-
- /* This will not catch every single case we could combine, but will
- catch those with constants. The goal here is to simultaneously
- combine constants between expressions, but avoid infinite
- expansion of expressions during simplification. */
- if (TREE_CODE (op0) == SSA_NAME)
- {
- if (VN_INFO (op0)->has_constants
- || TREE_CODE_CLASS (code) == tcc_comparison
- || code == COMPLEX_EXPR)
- op0 = valueize_expr (vn_get_expr_for (op0));
- else
- op0 = vn_valueize (op0);
- }
-
- if (TREE_CODE (op1) == SSA_NAME)
- {
- if (VN_INFO (op1)->has_constants
- || code == COMPLEX_EXPR)
- op1 = valueize_expr (vn_get_expr_for (op1));
- else
- op1 = vn_valueize (op1);
- }
-
- /* Pointer plus constant can be represented as invariant address.
- Do so to allow further propatation, see also tree forwprop. */
- if (code == POINTER_PLUS_EXPR
- && tree_fits_uhwi_p (op1)
- && TREE_CODE (op0) == ADDR_EXPR
- && is_gimple_min_invariant (op0))
- return build_invariant_address (TREE_TYPE (op0),
- TREE_OPERAND (op0, 0),
- tree_to_uhwi (op1));
-
- /* Avoid folding if nothing changed. */
- if (op0 == gimple_assign_rhs1 (stmt)
- && op1 == gimple_assign_rhs2 (stmt))
- return NULL_TREE;
-
- fold_defer_overflow_warnings ();
-
- result = fold_binary (code, gimple_expr_type (stmt), op0, op1);
- if (result)
- STRIP_USELESS_TYPE_CONVERSION (result);
-
- fold_undefer_overflow_warnings (result && valid_gimple_rhs_p (result),
- stmt, 0);
-
- /* Make sure result is not a complex expression consisting
- of operators of operators (IE (a + b) + (a + c))
- Otherwise, we will end up with unbounded expressions if
- fold does anything at all. */
- if (result && valid_gimple_rhs_p (result))
- return result;
-
- return NULL_TREE;
- }
-
- /* Simplify the unary expression RHS, and return the result if
- simplified. */
-
- static tree
- simplify_unary_expression (gimple stmt)
- {
- tree result = NULL_TREE;
- tree orig_op0, op0 = gimple_assign_rhs1 (stmt);
- enum tree_code code = gimple_assign_rhs_code (stmt);
-
- /* We handle some tcc_reference codes here that are all
- GIMPLE_ASSIGN_SINGLE codes. */
- if (code == REALPART_EXPR
- || code == IMAGPART_EXPR
- || code == VIEW_CONVERT_EXPR
- || code == BIT_FIELD_REF)
- op0 = TREE_OPERAND (op0, 0);
-
- if (TREE_CODE (op0) != SSA_NAME)
- return NULL_TREE;
-
- orig_op0 = op0;
- if (VN_INFO (op0)->has_constants)
- op0 = valueize_expr (vn_get_expr_for (op0));
- else if (CONVERT_EXPR_CODE_P (code)
- || code == REALPART_EXPR
- || code == IMAGPART_EXPR
- || code == VIEW_CONVERT_EXPR
- || code == BIT_FIELD_REF)
- {
- /* We want to do tree-combining on conversion-like expressions.
- Make sure we feed only SSA_NAMEs or constants to fold though. */
- tree tem = valueize_expr (vn_get_expr_for (op0));
- if (UNARY_CLASS_P (tem)
- || BINARY_CLASS_P (tem)
- || TREE_CODE (tem) == VIEW_CONVERT_EXPR
- || TREE_CODE (tem) == SSA_NAME
- || TREE_CODE (tem) == CONSTRUCTOR
- || is_gimple_min_invariant (tem))
- op0 = tem;
- }
-
- /* Avoid folding if nothing changed, but remember the expression. */
- if (op0 == orig_op0)
- return NULL_TREE;
-
- if (code == BIT_FIELD_REF)
- {
- tree rhs = gimple_assign_rhs1 (stmt);
- result = fold_ternary (BIT_FIELD_REF, TREE_TYPE (rhs),
- op0, TREE_OPERAND (rhs, 1), TREE_OPERAND (rhs, 2));
- }
- else
- result = fold_unary_ignore_overflow (code, gimple_expr_type (stmt), op0);
- if (result)
- {
- STRIP_USELESS_TYPE_CONVERSION (result);
- if (valid_gimple_rhs_p (result))
- return result;
- }
-
- return NULL_TREE;
- }
-
/* Try to simplify RHS using equivalences and constant folding. */
static tree
try_to_simplify (gimple stmt)
{
enum tree_code code = gimple_assign_rhs_code (stmt);
- tree tem;
/* For stores we can end up simplifying a SSA_NAME rhs. Just return
in this case, there is no point in doing extra work. */
if (code == SSA_NAME)
return NULL_TREE;
- /* First try constant folding based on our current lattice.
- ??? Should be subsumed by gimple_match_and_simplify. */
- tem = gimple_fold_stmt_to_constant_1 (stmt, vn_valueize);
- if (tem
- && (TREE_CODE (tem) == SSA_NAME
- || is_gimple_min_invariant (tem)))
- return tem;
-
/* If that didn't work try combining multiple statements.
??? Handle multiple stmts being generated by storing
at most one in VN_INFO->expr? But then we'd have to
--- 3011,3034 ----
*************** try_to_simplify (gimple stmt)
*** 3359,3366 ****
created by gimple_match_and_simplify - or we never value-number
to them. */
if (TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME)
! return gimple_match_and_simplify (gimple_assign_lhs (stmt),
! NULL, vn_valueize);
return NULL_TREE;
}
--- 3036,3043 ----
created by gimple_match_and_simplify - or we never value-number
to them. */
if (TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME)
! return gimple_match_and_simplify (gimple_assign_lhs (stmt),
! NULL, vn_valueize);
return NULL_TREE;
}
*************** visit_use (tree use)
*** 3419,3429 ****
print_gimple_expr (dump_file, stmt, 0, 0);
fprintf (dump_file, " simplified to ");
print_generic_expr (dump_file, simplified, 0);
! if (TREE_CODE (lhs) == SSA_NAME)
! fprintf (dump_file, " has constants %d\n",
! expr_has_constants (simplified));
! else
! fprintf (dump_file, "\n");
}
}
/* Setting value numbers to constants will occasionally
--- 3096,3102 ----
print_gimple_expr (dump_file, stmt, 0, 0);
fprintf (dump_file, " simplified to ");
print_generic_expr (dump_file, simplified, 0);
! fprintf (dump_file, "\n");
}
}
/* Setting value numbers to constants will occasionally
*************** visit_use (tree use)
*** 3434,3441 ****
&& is_gimple_min_invariant (simplified)
&& TREE_CODE (lhs) == SSA_NAME)
{
- VN_INFO (lhs)->expr = simplified;
- VN_INFO (lhs)->has_constants = true;
changed = set_ssa_val_to (lhs, simplified);
goto done;
}
--- 3107,3112 ----
*************** visit_use (tree use)
*** 3446,3474 ****
changed = visit_copy (lhs, simplified);
goto done;
}
- else if (simplified)
- {
- if (TREE_CODE (lhs) == SSA_NAME)
- {
- VN_INFO (lhs)->has_constants = expr_has_constants (simplified);
- /* We have to unshare the expression or else
- valuizing may change the IL stream. */
- VN_INFO (lhs)->expr = unshare_expr (simplified);
- }
- }
- else if (stmt_has_constants (stmt)
- && TREE_CODE (lhs) == SSA_NAME)
- VN_INFO (lhs)->has_constants = true;
- else if (TREE_CODE (lhs) == SSA_NAME)
- {
- /* We reset expr and constantness here because we may
- have been value numbering optimistically, and
- iterating. They may become non-constant in this case,
- even if they were optimistically constant. */
-
- VN_INFO (lhs)->has_constants = false;
- VN_INFO (lhs)->expr = NULL_TREE;
- }
if ((TREE_CODE (lhs) == SSA_NAME
/* We can substitute SSA_NAMEs that are live over
--- 3117,3122 ----
*************** visit_use (tree use)
*** 3493,3499 ****
|| (simplified
&& is_gimple_min_invariant (simplified)))
{
- VN_INFO (lhs)->has_constants = true;
if (simplified)
changed = set_ssa_val_to (lhs, simplified);
else
--- 3141,3146 ----
*************** visit_use (tree use)
*** 3548,3565 ****
if (lhs && TREE_CODE (lhs) == SSA_NAME)
{
- if (stmt_has_constants (stmt))
- VN_INFO (lhs)->has_constants = true;
- else
- {
- /* We reset expr and constantness here because we may
- have been value numbering optimistically, and
- iterating. They may become non-constant in this case,
- even if they were optimistically constant. */
- VN_INFO (lhs)->has_constants = false;
- VN_INFO (lhs)->expr = NULL_TREE;
- }
-
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
{
changed = defs_to_varying (stmt);
--- 3195,3200 ----
Index: gcc/tree-ssa-sccvn.h
===================================================================
*** gcc/tree-ssa-sccvn.h (revision 208477)
--- gcc/tree-ssa-sccvn.h (working copy)
*************** typedef struct vn_ssa_aux
*** 170,177 ****
unsigned visited : 1;
unsigned on_sccstack : 1;
- /* Whether the representative expression contains constants. */
- unsigned has_constants : 1;
/* Whether the SSA_NAME has been value numbered already. This is
only saying whether visit_use has been called on it at least
once. It cannot be used to avoid visitation for SSA_NAME's
--- 170,175 ----
More information about the Gcc-patches
mailing list