This tries to extend the previously posted CCP folding patch by
introducing a generic interface for non-tree-building, GIMPLE SSA
aware folding. The low-level interface for folding regular
operations is
/* Fold the expression composed by *CODEP, TYPE and valueized operands
*OP0P,
*OP1P and *OP2P (as required), using the VALUEIZE callback to valueize
SSA names that turn up during statement lookup and producing a result
of at most KIND. The folding result will be stored in the operands.
GF_KIND_FAIL is returned if no folding was done.
If GF_KIND_CONST or GF_KIND_VAL is returned the folding result is
stored in *OP0P and is a is_gimple_min_invariant or a is_gimple_val.
If GF_KIND_STMT is returned the folding result is stored in *CODEP,
*OP0P, *OP1P and *OP2P (as required) and will compose a valid set of
operands for a gimple assignment.
If GF_KIND_COMPLEX is returned the folding result is stored in *OP0P
and will be an arbitrarily complex tree. */
enum gf_kind
gimple_fold (enum tree_code *codep, tree type,
tree *op0p, tree *op1p, tree *op2p,
tree (*valueize)(tree), enum gf_kind kind)
which would allow existing gimple-level foldings to build ontop of this
(including fold_stmt and friends and the special CCP foldings).
The current implementation is quite lame, just dispatching to fold,
but I plan to integrate it with the CCP and fold_stmt foldings before
considering to merge it (eventually producing some sort of statistics
of what the fold path catches that the gimple path does not).
The low-level interface needs to be amended by one for builtin calls
where I'm not sure if it is going to take decomposed operands
or just a gimple statement (I think we have at most 3 operands to
any builtin we can fold in some way).
This again is just a RFC (even though the patch "works" as far as
plugging into the SCCVN binary operation simplification).
Thanks,
Richard.
<ChangeLog to be inserted...>
Index: gcc/gimple-fold.h
===================================================================
*** gcc/gimple-fold.h (revision 0)
--- gcc/gimple-fold.h (revision 0)
***************
*** 0 ****
--- 1,39 ----
+ /* Gimple folding definitions.
+
+ Copyright 2011 Free Software Foundation, Inc.
+ Contributed by Richard Guenther <rguent...@suse.de>
+
+ This file is part of GCC.
+
+ GCC is free software; you can redistribute it and/or modify it under
+ the terms of the GNU General Public License as published by the Free
+ Software Foundation; either version 3, or (at your option) any later
+ version.
+
+ GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING3. If not see
+ <http://www.gnu.org/licenses/>. */
+
+ #ifndef GCC_GIMPLE_FOLD_H
+ #define GCC_GIMPLE_FOLD_H
+
+ #include "coretypes.h"
+
+ enum gf_kind {
+ GF_KIND_FAIL = 0,
+ GF_KIND_CONST,
+ GF_KIND_VAL,
+ GF_KIND_STMT,
+ GF_KIND_COMPLEX
+ };
+
+ enum gf_kind gimple_fold (enum tree_code *, tree,
+ tree *, tree *, tree *,
+ tree (*)(tree), enum gf_kind);
+
+ #endif /* GCC_GIMPLE_FOLD_H */
Index: gcc/gimple-fold.c
===================================================================
*** gcc/gimple-fold.c (revision 171133)
--- gcc/gimple-fold.c (working copy)
*************** along with GCC; see the file COPYING3.
*** 30,35 ****
--- 30,36 ----
#include "tree-pass.h"
#include "tree-ssa-propagate.h"
#include "target.h"
+ #include "gimple-fold.h"
/* Return true when DECL can be referenced from current unit.
We can get declarations that are not possible to reference for
*************** maybe_fold_or_comparisons (enum tree_cod
*** 2665,2667 ****
--- 2666,2914 ----
else
return or_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
}
+
+
+ static tree
+ build_valueized_tree_from_def (tree name, tree (*valueize)(tree))
+ {
+ gimple def_stmt = SSA_NAME_DEF_STMT (name);
+ tree op0, op1, op2;
+
+ if (!is_gimple_assign (def_stmt)
+ || gimple_vuse (def_stmt))
+ return name;
+
+ switch (gimple_assign_rhs_class (def_stmt))
+ {
+ case GIMPLE_SINGLE_RHS:
+ return gimple_assign_rhs1 (def_stmt);
+
+ case GIMPLE_TERNARY_RHS:
+ op2 = gimple_assign_rhs3 (def_stmt);
+ if (TREE_CODE (op2) == SSA_NAME
+ && valueize)
+ op2 = (*valueize) (op2);
+
+ case GIMPLE_BINARY_RHS:
+ op1 = gimple_assign_rhs2 (def_stmt);
+ if (TREE_CODE (op1) == SSA_NAME
+ && valueize)
+ op1 = (*valueize) (op1);
+
+ case GIMPLE_UNARY_RHS:
+ op0 = gimple_assign_rhs1 (def_stmt);
+ if (TREE_CODE (op0) == SSA_NAME
+ && valueize)
+ op0 = (*valueize) (op0);
+ break;
+
+ default:;
+ }
+
+ switch (gimple_assign_rhs_class (def_stmt))
+ {
+ case GIMPLE_UNARY_RHS:
+ return fold_build1 (gimple_assign_rhs_code (def_stmt),
+ TREE_TYPE (name), op0);
+ case GIMPLE_BINARY_RHS:
+ return fold_build2 (gimple_assign_rhs_code (def_stmt),
+ TREE_TYPE (name), op0, op1);
+ case GIMPLE_TERNARY_RHS:
+ return fold_build3 (gimple_assign_rhs_code (def_stmt),
+ TREE_TYPE (name), op0, op1, op2);
+ default:;
+ }
+
+ return name;
+ }
+
+ static enum gf_kind
+ const_or_val (tree res, enum gf_kind kind)
+ {
+ if (res
+ && kind >= GF_KIND_CONST
+ && is_gimple_min_invariant (res))
+ return GF_KIND_CONST;
+ if (res
+ && kind >= GF_KIND_VAL
+ && is_gimple_val (res))
+ return GF_KIND_VAL;
+ return GF_KIND_FAIL;
+ }
+
+ /* Fold the expression composed by *CODEP, TYPE and valueized operands *OP0P,
+ *OP1P and *OP2P (as required), using the VALUEIZE callback to valueize
+ SSA names that turn up during statement lookup and producing a result
+ of at most KIND. The folding result will be stored in the operands.
+ GF_KIND_FAIL is returned if no folding was done.
+ If GF_KIND_CONST or GF_KIND_VAL is returned the folding result is
+ stored in *OP0P and is a is_gimple_min_invariant or a is_gimple_val.
+ If GF_KIND_STMT is returned the folding result is stored in *CODEP,
+ *OP0P, *OP1P and *OP2P (as required) and will compose a valid set of
+ operands for a gimple assignment.
+ If GF_KIND_COMPLEX is returned the folding result is stored in *OP0P
+ and will be an arbitrarily complex tree. */
+
+ enum gf_kind
+ gimple_fold (enum tree_code *codep, tree type,
+ tree *op0p, tree *op1p, tree *op2p,
+ tree (*valueize)(tree), enum gf_kind kind)
+ {
+ enum tree_code code = *codep;
+ tree op0 = *op0p;
+ tree op1 = *op1p;
+ tree op2 = *op2p;
+ tree alt_op0, alt_op1, res;
+ enum gf_kind res_kind;
+
+ switch (code)
+ {
+ case COMPLEX_EXPR:
+ if (TREE_CODE (op0) == SSA_NAME
+ && TREE_CODE (op1) == SSA_NAME)
+ {
+ gimple def_stmt0 = SSA_NAME_DEF_STMT (op0);
+ gimple def_stmt1 = SSA_NAME_DEF_STMT (op1);
+ if (gimple_assign_single_p (def_stmt0)
+ && !gimple_vuse (def_stmt0)
+ && gimple_assign_single_p (def_stmt1)
+ && !gimple_vuse (def_stmt1)
+ && gimple_assign_rhs_code (def_stmt0) == REALPART_EXPR
+ && gimple_assign_rhs_code (def_stmt1) == IMAGPART_EXPR)
+ {
+ tree dop0 = TREE_OPERAND (gimple_assign_rhs1 (def_stmt0), 0);
+ tree dop1 = TREE_OPERAND (gimple_assign_rhs1 (def_stmt1), 0);
+ if (TREE_CODE (dop0) == SSA_NAME)
+ dop0 = (*valueize) (dop0);
+ if (TREE_CODE (dop1) == SSA_NAME)
+ dop1 = (*valueize) (dop1);
+ if (operand_equal_p (dop0, dop1, 0))
+ {
+ *op0p = dop0;
+ return (TREE_CODE (dop0) == COMPLEX_CST
+ ? GF_KIND_CONST : GF_KIND_VAL);
+ }
+ }
+ }
+ default:;
+ }
+
+ /* Now fall back to building trees and using fold. */
+ /* ??? This code should obviously go completely and be replaced by
+ gimple aware, non-tree building variants. It can be used to
+ identify commonly missed opportunities. */
+
+ switch (get_gimple_rhs_class (code))
+ {
+ case GIMPLE_SINGLE_RHS:
+ if ((code == VIEW_CONVERT_EXPR
+ || code == REALPART_EXPR
+ || code == IMAGPART_EXPR)
+ && TREE_CODE (TREE_OPERAND (op0, 0)) == SSA_NAME)
+ {
+ op0 = TREE_OPERAND (op0, 0);
+ if (valueize)
+ op0 = (*valueize) (op0);
+ goto handle_unary;
+ }
+ else if (code == BIT_FIELD_REF
+ && TREE_CODE (TREE_OPERAND (op0, 0)) == SSA_NAME)
+ {
+ op0 = TREE_OPERAND (op0, 0);
+ if (valueize)
+ op0 = (*valueize) (op0);
+ goto handle_ternary;
+ }
+ return GF_KIND_FAIL;
+
+ handle_unary:
+ case GIMPLE_UNARY_RHS:
+ res = fold_unary (code, type, op0);
+ if ((res_kind = const_or_val (res, kind)) != GF_KIND_FAIL)
+ {
+ *op0p = res;
+ return res_kind;
+ }
+ alt_op0 = op0;
+ if (TREE_CODE (op0) == SSA_NAME)
+ alt_op0 = build_valueized_tree_from_def (op0, valueize);
+ if (alt_op0 != op0)
+ {
+ res = fold_unary (code, type, alt_op0);
+ if ((res_kind = const_or_val (res, kind)) != GF_KIND_FAIL)
+ {
+ *op0p = res;
+ return res_kind;
+ }
+ }
+ return GF_KIND_FAIL;
+
+ case GIMPLE_BINARY_RHS:
+ res = fold_binary (code, type, op0, op1);
+ if ((res_kind = const_or_val (res, kind)) != GF_KIND_FAIL)
+ {
+ *op0p = res;
+ return res_kind;
+ }
+ alt_op0 = op0;
+ if (TREE_CODE (op0) == SSA_NAME)
+ alt_op0 = build_valueized_tree_from_def (op0, valueize);
+ if (alt_op0 != op0)
+ {
+ res = fold_binary (code, type, alt_op0, op1);
+ if ((res_kind = const_or_val (res, kind)) != GF_KIND_FAIL)
+ {
+ *op0p = res;
+ return res_kind;
+ }
+ }
+ alt_op1 = op1;
+ if (TREE_CODE (op1) == SSA_NAME)
+ alt_op1 = build_valueized_tree_from_def (op1, valueize);
+ if (alt_op1 != op1)
+ {
+ res = fold_binary (code, type, op0, alt_op1);
+ if ((res_kind = const_or_val (res, kind)) != GF_KIND_FAIL)
+ {
+ *op0p = res;
+ return res_kind;
+ }
+ }
+ if (alt_op0 != op0
+ && alt_op1 != op1)
+ {
+ res = fold_binary (code, type, alt_op0, alt_op1);
+ if ((res_kind = const_or_val (res, kind)) != GF_KIND_FAIL)
+ {
+ *op0p = res;
+ return res_kind;
+ }
+ }
+ return GF_KIND_FAIL;
+
+ handle_ternary:
+ case GIMPLE_TERNARY_RHS:
+ res = fold_ternary (code, type, op0, op1, op2);
+ if ((res_kind = const_or_val (res, kind)) != GF_KIND_FAIL)
+ {
+ *op0p = res;
+ return res_kind;
+ }
+ alt_op0 = op0;
+ if (TREE_CODE (op0) == SSA_NAME)
+ alt_op0 = build_valueized_tree_from_def (op0, valueize);
+ if (alt_op0 != op0)
+ {
+ res = fold_ternary (code, type, alt_op0, op1, op2);
+ if ((res_kind = const_or_val (res, kind)) != GF_KIND_FAIL)
+ {
+ *op0p = res;
+ return res_kind;
+ }
+ }
+ return GF_KIND_FAIL;
+
+ default:
+ return GF_KIND_FAIL;
+ }
+ }
Index: gcc/tree-ssa-sccvn.c
===================================================================
*** gcc/tree-ssa-sccvn.c (revision 171133)
--- gcc/tree-ssa-sccvn.c (working copy)
*************** along with GCC; see the file COPYING3.
*** 44,49 ****
--- 44,50 ----
#include "params.h"
#include "tree-ssa-propagate.h"
#include "tree-ssa-sccvn.h"
+ #include "gimple-fold.h"
/* This algorithm is based on the SCC algorithm presented by Keith
Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
*************** valueize_expr (tree expr)
*** 2745,2796 ****
static tree
simplify_binary_expression (gimple stmt)
{
- tree result = NULL_TREE;
tree op0 = gimple_assign_rhs1 (stmt);
tree op1 = gimple_assign_rhs2 (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 (gimple_assign_rhs_code (stmt)) == tcc_comparison)
! op0 = valueize_expr (vn_get_expr_for (op0));
! else if (SSA_VAL (op0) != VN_TOP && SSA_VAL (op0) != op0)
! op0 = SSA_VAL (op0);
! }
!
! if (TREE_CODE (op1) == SSA_NAME)
! {
! if (VN_INFO (op1)->has_constants)
! op1 = valueize_expr (vn_get_expr_for (op1));
! else if (SSA_VAL (op1) != VN_TOP && SSA_VAL (op1) != op1)
! op1 = SSA_VAL (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 (gimple_assign_rhs_code (stmt),
! 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;
}
--- 2746,2767 ----
static tree
simplify_binary_expression (gimple stmt)
{
tree op0 = gimple_assign_rhs1 (stmt);
tree op1 = gimple_assign_rhs2 (stmt);
+ enum tree_code code = gimple_assign_rhs_code (stmt);
+ tree dummy;
! if (TREE_CODE (op0) == SSA_NAME
! && SSA_VAL (op0) != VN_TOP)
! op0 = SSA_VAL (op0);
!
! if (TREE_CODE (op1) == SSA_NAME
! && SSA_VAL (op1) != VN_TOP)
! op1 = SSA_VAL (op1);
!
! if (gimple_fold (&code, TREE_TYPE (gimple_assign_lhs (stmt)),
! &op0, &op1, &dummy, NULL, GF_KIND_VAL) != GF_KIND_FAIL)
! return op0;
return NULL_TREE;
}
