[PATCH] gimple_val_nonnegative_real_p (PR46728 patch 7 of 7)

[Richard Guenther]

On Mon, Jun 6, 2011 at 2:12 PM, William J. Schmidt
<wschmidt@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
>> <wschmidt@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
>
>
>