On Mon, Jun 6, 2011 at 2:12 PM, William J. Schmidt
<wschm...@linux.vnet.ibm.com> wrote:
> 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.
Sorry for being unclear.
> 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.
Indeed.
>>
>> 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?
if (arg0 == arg1 && ! (flags & OEP_ONLY_CONST)
&& (TREE_CODE (arg0) == SAVE_EXPR
|| (flags & OEP_CONSTANT_ADDRESS_OF)
|| (! TREE_SIDE_EFFECTS (arg0) && ! TREE_SIDE_EFFECTS (arg1))))
return 1;
should return true. SSA_NAMEs are shared trees, so your code
is, simplified
if (op0 == op1)
which you could pre-pend to the operand-equal check to make it cheaper
in the common case. Thus,
if (op0 == op1
|| operand_equal_p (...))
return true;
Richard.
> Thanks,
> Bill
>
>
>
