On Mon, 2011-06-06 at 13:00 +0200, Richard Guenther wrote:
> On Wed, Jun 1, 2011 at 9:27 PM, William J. Schmidt
> <wschm...@linux.vnet.ibm.com> wrote:
<snip>
> > +/* 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.
OK. I misunderstood your intent; I thought you had provided a skeleton
and wanted me to fill in the details to match the corresponding tree
interface. I understand the concern and will remove the recursion. If
we find we're missing cases, it would be simple enough to provide
limited-depth 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.
I don't believe it is, though perhaps it should be. I didn't see any
handling for SSA_NAME or tcc_exceptional, and the default just returns
false, so I added this logic. Did I miss something subtle?
Thanks,
Bill
