On Wed, Jun 1, 2011 at 9:27 PM, William J. Schmidt
<[email protected]> wrote:
> This patch cleans up the FIXME logic in gimple_expand_builtin_pow by
> introducing gimple_val_nonnegative_real_p for the same purpose that
> tree_expr_nonnegative_p served in the expand logic. This completes the
> work for PR46728.
>
> Bootstrapped/regtested on powerpc64-linux.
>
>
> 2011-06-01 Bill Schmidt <[email protected]>
>
> PR tree-optimization/46728
> * tree-ssa-math-opts.c (gimple_expand_builtin_pow): Change FIXME
> to use gimple_val_nonnegative_real_p.
> * gimple-fold.c (gimple_val_nonnegative_real_p): New function.
> * gimple.h (gimple_val_nonnegative_real_p): New declaration.
>
>
> Index: gcc/tree-ssa-math-opts.c
> ===================================================================
> --- gcc/tree-ssa-math-opts.c (revision 174535)
> +++ gcc/tree-ssa-math-opts.c (working copy)
> @@ -1172,13 +1172,7 @@ gimple_expand_builtin_pow (gimple_stmt_iterator *g
>
> if (flag_unsafe_math_optimizations
> && cbrtfn
> - /* FIXME: The following line was originally
> - && (tree_expr_nonnegative_p (arg0) || !HONOR_NANS (mode)),
> - but since arg0 is a gimple value, the first predicate
> - will always return false. It needs to be replaced with a
> - call to a similar gimple_val_nonnegative_p function to be
> - added in gimple-fold.c. */
> - && !HONOR_NANS (mode)
> + && (gimple_val_nonnegative_real_p (arg0) || !HONOR_NANS (mode))
> && REAL_VALUES_EQUAL (c, dconst1_3))
> return build_and_insert_call (gsi, loc, &target, cbrtfn, arg0);
>
> @@ -1190,13 +1184,7 @@ gimple_expand_builtin_pow (gimple_stmt_iterator *g
> if (flag_unsafe_math_optimizations
> && sqrtfn
> && cbrtfn
> - /* FIXME: The following line was originally
> - && (tree_expr_nonnegative_p (arg0) || !HONOR_NANS (mode)),
> - but since arg0 is a gimple value, the first predicate
> - will always return false. It needs to be replaced with a
> - call to a similar gimple_val_nonnegative_p function to be
> - added in gimple-fold.c. */
> - && !HONOR_NANS (mode)
> + && (gimple_val_nonnegative_real_p (arg0) || !HONOR_NANS (mode))
> && optimize_function_for_speed_p (cfun)
> && hw_sqrt_exists
> && REAL_VALUES_EQUAL (c, dconst1_6))
> @@ -1270,13 +1258,7 @@ gimple_expand_builtin_pow (gimple_stmt_iterator *g
>
> if (flag_unsafe_math_optimizations
> && cbrtfn
> - /* FIXME: The following line was originally
> - && (tree_expr_nonnegative_p (arg0) || !HONOR_NANS (mode)),
> - but since arg0 is a gimple value, the first predicate
> - will always return false. It needs to be replaced with a
> - call to a similar gimple_val_nonnegative_p function to be
> - added in gimple-fold.c. */
> - && !HONOR_NANS (mode)
> + && (gimple_val_nonnegative_real_p (arg0) || !HONOR_NANS (mode))
> && real_identical (&c2, &c)
> && optimize_function_for_speed_p (cfun)
> && powi_cost (n / 3) <= POWI_MAX_MULTS)
> Index: gcc/gimple-fold.c
> ===================================================================
> --- gcc/gimple-fold.c (revision 174535)
> +++ gcc/gimple-fold.c (working copy)
> @@ -3433,3 +3433,224 @@ fold_const_aggregate_ref (tree t)
> {
> return fold_const_aggregate_ref_1 (t, NULL);
> }
> +
> +/* Return true iff VAL is a gimple expression that is known to be
> + non-negative. Restricted to floating-point inputs. When changing
> + this function, review fold-const.c:tree_expr_nonnegative_p to see
> + whether similar changes are required. */
> +
> +bool
> +gimple_val_nonnegative_real_p (tree val)
> +{
> + gimple def_stmt;
> +
> + /* Use existing logic for non-gimple trees. */
> + if (tree_expr_nonnegative_p (val))
> + return true;
> +
> + if (TREE_CODE (val) != SSA_NAME)
> + return false;
> +
> + def_stmt = SSA_NAME_DEF_STMT (val);
> +
> + if (is_gimple_assign (def_stmt))
> + {
> + tree op0, op1;
> +
> + /* If this is just a copy between SSA names, check the RHS. */
> + if (gimple_assign_ssa_name_copy_p (def_stmt))
> + {
> + op0 = gimple_assign_rhs1 (def_stmt);
> + return gimple_val_nonnegative_real_p (op0);
> + }
If handled then do so as SSA_NAME: case below.
> + switch (gimple_assign_rhs_code (def_stmt))
> + {
> + case ABS_EXPR:
> + /* Always true for floating-point operands. */
> + return true;
You don't verify anywhere that the input is FP.
As the depth of the expression we look at is unbound it is probably
easy to construct a testcase that exhibits quadratic compile-time
behavior like pow(pow(pow(pow(...,0.5), 0.5), 0.5), 0.5). I originally
thought of just looking at the immediate defining statement but
never at its operands (simply return false when only the operand
would tell). And I still think that is the way to go and should still
catch 99% of the useful cases.
As for the grand masterplan we probably should eventually drive
the builtin-folding by information provided by a SSA or DOM propagation
engine (see tree-complex.c for example). That would avoid the
quadratic-ness.
So, please prune any recursion.
Thanks,
Richard.
> + case NOP_EXPR:
> + case CONVERT_EXPR:
> + /* True if the first operand is a nonnegative real. */
> + op0 = gimple_assign_rhs1 (def_stmt);
> + return (TREE_CODE (TREE_TYPE (op0)) == REAL_TYPE
> + && gimple_val_nonnegative_real_p (op0));
> +
> + case PLUS_EXPR:
> + case MIN_EXPR:
> + case RDIV_EXPR:
> + /* True if both operands are nonnegative. */
> + op0 = gimple_assign_rhs1 (def_stmt);
> + op1 = gimple_assign_rhs2 (def_stmt);
> + return (gimple_val_nonnegative_real_p (op0)
> + && gimple_val_nonnegative_real_p (op1));
> +
> + case MAX_EXPR:
> + /* True if either operand is nonnegative. */
> + op0 = gimple_assign_rhs1 (def_stmt);
> + op1 = gimple_assign_rhs2 (def_stmt);
> + return (gimple_val_nonnegative_real_p (op0)
> + || gimple_val_nonnegative_real_p (op1));
> +
> + case MULT_EXPR:
> + /* True if the two operands are identical (since we are
> + restricted to floating-point inputs), or if both operands
> + are nonnegative. */
> + op0 = gimple_assign_rhs1 (def_stmt);
> + op1 = gimple_assign_rhs2 (def_stmt);
> +
> + if (operand_equal_p (op0, op1, 0))
> + return true;
> +
> + if (TREE_CODE (op0) == SSA_NAME
> + && TREE_CODE (op1) == SSA_NAME
> + && SSA_NAME_VAR (op0) == SSA_NAME_VAR (op1)
> + && SSA_NAME_VERSION (op0) == SSA_NAME_VERSION (op1))
> + return true;
That case is covered by operand_equal_p already.
> +
> + /* FIXME: Could we miss cases where op0 and op1 are different
> + SSA_NAMES whose defining values are equivalent, or one is
> + an SSA_NAME and the other is an equivalent non-SSA_NAME?
> + These cases likely don't constitute a great loss in any
> + event. */
Well, we can surely assume value-numbering has done its job.
> + return (gimple_val_nonnegative_real_p (op0)
> + && gimple_val_nonnegative_real_p (op1));
> +
> + default:
> + return false;
> + }
> + }
> + else if (is_gimple_call (def_stmt))
> + {
> + tree fndecl = gimple_call_fndecl (def_stmt);
> + if (fndecl
> + && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
> + {
> + tree arg0, arg1;
> +
> + switch (DECL_FUNCTION_CODE (fndecl))
> + {
> + CASE_FLT_FN (BUILT_IN_ACOS):
> + CASE_FLT_FN (BUILT_IN_ACOSH):
> + CASE_FLT_FN (BUILT_IN_CABS):
> + CASE_FLT_FN (BUILT_IN_COSH):
> + CASE_FLT_FN (BUILT_IN_ERFC):
> + CASE_FLT_FN (BUILT_IN_EXP):
> + CASE_FLT_FN (BUILT_IN_EXP10):
> + CASE_FLT_FN (BUILT_IN_EXP2):
> + CASE_FLT_FN (BUILT_IN_FABS):
> + CASE_FLT_FN (BUILT_IN_FDIM):
> + CASE_FLT_FN (BUILT_IN_HYPOT):
> + CASE_FLT_FN (BUILT_IN_POW10):
> + return true;
> +
> + CASE_FLT_FN (BUILT_IN_SQRT):
> + /* sqrt(-0.0) is -0.0, and sqrt is not defined over other
> + nonnegative inputs. */
> + if (!HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (val))))
> + return true;
> +
> + arg0 = gimple_call_arg (def_stmt, 0);
> + return gimple_val_nonnegative_real_p (arg0);
> +
> + CASE_FLT_FN (BUILT_IN_ASINH):
> + CASE_FLT_FN (BUILT_IN_ATAN):
> + CASE_FLT_FN (BUILT_IN_ATANH):
> + CASE_FLT_FN (BUILT_IN_CBRT):
> + CASE_FLT_FN (BUILT_IN_CEIL):
> + CASE_FLT_FN (BUILT_IN_ERF):
> + CASE_FLT_FN (BUILT_IN_EXPM1):
> + CASE_FLT_FN (BUILT_IN_FLOOR):
> + CASE_FLT_FN (BUILT_IN_FMOD):
> + CASE_FLT_FN (BUILT_IN_FREXP):
> + CASE_FLT_FN (BUILT_IN_LCEIL):
> + CASE_FLT_FN (BUILT_IN_LDEXP):
> + CASE_FLT_FN (BUILT_IN_LFLOOR):
> + CASE_FLT_FN (BUILT_IN_LLCEIL):
> + CASE_FLT_FN (BUILT_IN_LLFLOOR):
> + CASE_FLT_FN (BUILT_IN_LLRINT):
> + CASE_FLT_FN (BUILT_IN_LLROUND):
> + CASE_FLT_FN (BUILT_IN_LRINT):
> + CASE_FLT_FN (BUILT_IN_LROUND):
> + CASE_FLT_FN (BUILT_IN_MODF):
> + CASE_FLT_FN (BUILT_IN_NEARBYINT):
> + CASE_FLT_FN (BUILT_IN_RINT):
> + CASE_FLT_FN (BUILT_IN_ROUND):
> + CASE_FLT_FN (BUILT_IN_SCALB):
> + CASE_FLT_FN (BUILT_IN_SCALBLN):
> + CASE_FLT_FN (BUILT_IN_SCALBN):
> + CASE_FLT_FN (BUILT_IN_SIGNBIT):
> + CASE_FLT_FN (BUILT_IN_SIGNIFICAND):
> + CASE_FLT_FN (BUILT_IN_SINH):
> + CASE_FLT_FN (BUILT_IN_TANH):
> + CASE_FLT_FN (BUILT_IN_TRUNC):
> + /* True if the first argument is nonnegative. */
> + arg0 = gimple_call_arg (def_stmt, 0);
> + return gimple_val_nonnegative_real_p (arg0);
> +
> + CASE_FLT_FN (BUILT_IN_FMAX):
> + /* True if either argument is nonnegative. */
> + arg0 = gimple_call_arg (def_stmt, 0);
> + arg1 = gimple_call_arg (def_stmt, 1);
> + return (gimple_val_nonnegative_real_p (arg0)
> + || gimple_val_nonnegative_real_p (arg1));
> +
> + CASE_FLT_FN (BUILT_IN_FMIN):
> + /* True if both arguments are nonnegative. */
> + arg0 = gimple_call_arg (def_stmt, 0);
> + arg1 = gimple_call_arg (def_stmt, 1);
> + return (gimple_val_nonnegative_real_p (arg0)
> + && gimple_val_nonnegative_real_p (arg1));
> +
> + CASE_FLT_FN (BUILT_IN_COPYSIGN):
> + /* True if the second argument is nonnegative. */
> + arg1 = gimple_call_arg (def_stmt, 1);
> + return gimple_val_nonnegative_real_p (arg1);
> +
> + CASE_FLT_FN (BUILT_IN_POWI):
> + /* True if the first argument is nonnegative or the
> + second argument is an even integer. */
> + arg0 = gimple_call_arg (def_stmt, 0);
> + arg1 = gimple_call_arg (def_stmt, 1);
> +
> + if (TREE_CODE (arg1) == INTEGER_CST
> + && (TREE_INT_CST_LOW (arg1) & 1) == 0)
> + return true;
> +
> + return gimple_val_nonnegative_real_p (arg0);
> +
> + CASE_FLT_FN (BUILT_IN_POW):
> + /* True if the first argument is nonnegative or the
> + second argument is an even integer-valued real. */
> + arg0 = gimple_call_arg (def_stmt, 0);
> + arg1 = gimple_call_arg (def_stmt, 1);
> +
> + if (TREE_CODE (arg1) == REAL_CST)
> + {
> + REAL_VALUE_TYPE c;
> + HOST_WIDE_INT n;
> +
> + c = TREE_REAL_CST (arg1);
> + n = real_to_integer (&c);
> +
> + if ((n & 1) == 0)
> + {
> + REAL_VALUE_TYPE cint;
> + real_from_integer (&cint, VOIDmode, n, n < 0 ? -1 : 0,
> 0);
> + if (real_identical (&c, &cint))
> + return true;
> + }
> + }
> +
> + return gimple_val_nonnegative_real_p (arg0);
> +
> + default:
> + return false;
> + }
> + }
> + }
> +
> + return false;
> +}
> Index: gcc/gimple.h
> ===================================================================
> --- gcc/gimple.h (revision 174535)
> +++ gcc/gimple.h (working copy)
> @@ -4988,4 +4988,5 @@ extern tree maybe_fold_and_comparisons (enum tree_
> extern tree maybe_fold_or_comparisons (enum tree_code, tree, tree,
> enum tree_code, tree, tree);
>
> +bool gimple_val_nonnegative_real_p (tree);
> #endif /* GCC_GIMPLE_H */
>
>
>
