Re: [PATCH] Handling == or != comparisons that may affect range test optimization.

[Cong Hou <congh at google dot com>]

On Tue, Nov 5, 2013 at 12:23 PM, Jeff Law <law@redhat.com> wrote:
> On 10/31/13 18:03, Cong Hou wrote:
>>
>> (This patch is for the bug 58728:
>> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58728)
>>
>> As in the bug report, consider the following loop:
>>
>> int foo(unsigned int n)
>> {
>>    if (n != 0)
>>    if (n != 1)
>>    if (n != 2)
>>    if (n != 3)
>>    if (n != 4)
>>      return ++n;
>>    return n;
>> }
>>
>> The range test optimization should be able to merge all those five
>> conditions into one in reassoc pass, but I fails to do so. The reason
>> is that the phi arg of n is replaced by the constant it compares to in
>> case of == or != comparisons (in vrp pass). GCC checks there is no
>> side effect on n between any two neighboring conditions by examining
>> if they defined the same phi arg in the join node. But as the phi arg
>> is replace by a constant, the check fails.
>>
>> This patch deals with this situation by considering the existence of
>> == or != comparisons, which is attached below (a text file is also
>> attached with proper tabs). Bootstrap and make check both get passed.
>>
>> Any comment?
>
>
> +       bool is_eq_expr = is_cond && (gimple_cond_code (stmt) == NE_EXPR
> +                                       || gimple_cond_code (stmt) ==
> EQ_EXPR)
> +                                 && TREE_CODE (phi_arg) == INTEGER_CST;
> +
> +       if (is_eq_expr)
> +         {
> +           lhs = gimple_cond_lhs (stmt);
> +           rhs = gimple_cond_rhs (stmt);
> +
> +           if (operand_equal_p (lhs, phi_arg, 0))
> +             {
> +               tree t = lhs;
> +               lhs = rhs;
> +               rhs = t;
> +             }
> +           if (operand_equal_p (rhs, phi_arg, 0)
> +               && operand_equal_p (lhs, phi_arg2, 0))
> +             continue;
> +         }
> +
> +       gimple stmt2 = last_stmt (test_bb);
> +       bool is_eq_expr2 = gimple_code (stmt2) == GIMPLE_COND
> +                            && (gimple_cond_code (stmt2) == NE_EXPR
> +                                || gimple_cond_code (stmt2) == EQ_EXPR)
> +                            && TREE_CODE (phi_arg2) == INTEGER_CST;
> +
> +       if (is_eq_expr2)
> +         {
> +           lhs2 = gimple_cond_lhs (stmt2);
> +           rhs2 = gimple_cond_rhs (stmt2);
> +
> +           if (operand_equal_p (lhs2, phi_arg2, 0))
> +             {
> +               tree t = lhs2;
> +               lhs2 = rhs2;
> +               rhs2 = t;
> +             }
> +           if (operand_equal_p (rhs2, phi_arg2, 0)
> +               && operand_equal_p (lhs2, phi_arg, 0))
> +             continue;
> +         }
>
> Can you factor those two hunks of nearly identical code into a single
> function and call it twice?  I'm also curious if you really need the code to
> swap lhs/rhs.  When can the LHS of a cond be an integer constant?  Don't we
> canonicalize it as <ssa_name> <COND> <constant>?


I was not aware that the comparison between a variable and a constant
will always be canonicalized as <ssa_name> <COND> <constant>. Then I
will remove the swap, and as the code is much smaller, I think it may
not be necessary to create a function for them.


>
> I'd probably write the ChangeLog as:
>
>         * tree-ssa-reassoc.c (suitable_cond_bb): Handle constant PHI
>         operands resulting from propagation of edge equivalences.
>
>

OK, much better than mine ;)


> I'm also curious -- did this code show up in a particular benchmark, if so,
> which one?

I didn't find this problem from any benchmark, but from another
concern about loop upper bound estimation. Look at the following code:

int foo(unsigned int n, int r)
{
  int i;
  if (n > 0)
    if (n < 4)
    {
      do {
         --n;
         r *= 2;
      } while (n > 0);
    }
  return r+n;
}


In order to get the upper bound of the loop in this function, GCC
traverses conditions n<4 and n>0 separately and tries to get any
useful information. But as those two conditions cannot be combined
into one due to this issue (note that n>0 will be transformed into
n!=0), when GCC sees n<4, it will consider the possibility that n may
be equal to 0, in which case the upper bound is UINT_MAX. If those two
conditions can be combined into one, which is n-1<=2, then we can get
the correct upper bound of the loop.


thanks,
Cong

>
> jeff