Re: PR tree-optimization/57337

[Easwaran Raman <eraman at google dot com>]

On Sat, May 25, 2013 at 4:46 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
> Easwaran Raman <eraman@google.com> wrote:
>
>>In that case, if my insert_stmt immediately follows dep_stmt and both
>>have the same UID, not_dominated_by would return true and I will end
>>up updating insert_stmt to dep_stmt which is wrong.
>
> But there should be a safe default answer for
> Equal uids. Unless we are asking different questions in different places.
> Thus, I do not like the stmt walking but rather have a safe fallback.

I am lost here. I don't see how we could avoid doing the stmt walking
to resolve the equal uid case. How to ensure that not_dominated_by (a,
b) returns true and not_dominated_by (b, a) returns false if A and B
have the same UID and A appears before B without doing the statement
walk. And, I don't see why the statement walk is bad. It is not likely
that there is a long sequence of statements with the same UID.

Thanks,
Easwaran

>
> Richard.
>
>>- Easwaran
>>
>>On Fri, May 24, 2013 at 1:07 AM, Richard Biener
>><richard.guenther@gmail.com> wrote:
>>> On Thu, May 23, 2013 at 7:26 PM, Easwaran Raman <eraman@google.com>
>>wrote:
>>>> This addresses the case where UID alone is not sufficient to figure
>>>> out which statement appears earlier in  a BB. Bootstraps and no test
>>>> regressions in x86_64 on linux. Ok for trunk?
>>>
>>> Why not simply conservatively use gimple_uid (a) <= gimple_uid (b)
>>> in not_dominated_by?
>>>
>>> Richard.
>>>
>>>
>>>
>>>> Thanks,
>>>> Easwaran
>>>>
>>>>
>>>> 2013-05-23  Easwaran Raman  <eraman@google.com>
>>>>
>>>> PR tree-optimization/57337
>>>> * tree-ssa-reassoc.c (appears_later_in_bb): New function.
>>>> (find_insert_point): Correctly identify the insertion point
>>>> when two statements with the same UID is compared.
>>>>
>>>> Index: gcc/tree-ssa-reassoc.c
>>>> ===================================================================
>>>> --- gcc/tree-ssa-reassoc.c      (revision 199211)
>>>> +++ gcc/tree-ssa-reassoc.c      (working copy)
>>>> @@ -2866,6 +2866,31 @@ not_dominated_by (gimple a, gimple b)
>>>>
>>>>  }
>>>>
>>>> +/* Among STMT1 and STMT2, return the statement that appears later.
>>Both
>>>> +   statements are in same BB and have the same UID.  */
>>>> +
>>>> +static gimple
>>>> +appears_later_in_bb (gimple stmt1, gimple stmt2)
>>>> +{
>>>> +  unsigned uid = gimple_uid (stmt1);
>>>> +  gimple_stmt_iterator gsi = gsi_for_stmt (stmt1);
>>>> +  gsi_next (&gsi);
>>>> +  if (gsi_end_p (gsi))
>>>> +    return stmt1;
>>>> +  for (; !gsi_end_p (gsi); gsi_next (&gsi))
>>>> +    {
>>>> +      gimple stmt = gsi_stmt (gsi);
>>>> +
>>>> +      /* If STMT has a different UID than STMT1 and we haven't seen
>>>> +         STMT2 during traversal, we know STMT1 appears later.  */
>>>> +      if (gimple_uid (stmt) != uid)
>>>> +        return stmt1;
>>>> +      else if (stmt == stmt2)
>>>> +        return stmt2;
>>>> +    }
>>>> +  gcc_unreachable ();
>>>> +}
>>>> +
>>>>  /* Find the statement after which STMT must be moved so that the
>>>>     dependency from DEP_STMT to STMT is maintained.  */
>>>>
>>>> @@ -2875,7 +2900,11 @@ find_insert_point (gimple stmt, gimple
>>dep_stmt)
>>>>    gimple insert_stmt = stmt;
>>>>    if (dep_stmt == NULL)
>>>>      return stmt;
>>>> -  if (not_dominated_by (insert_stmt, dep_stmt))
>>>> +  if (gimple_uid (insert_stmt) == gimple_uid (dep_stmt)
>>>> +      && gimple_bb (insert_stmt) == gimple_bb (dep_stmt)
>>>> +      && insert_stmt != dep_stmt)
>>>> +    insert_stmt = appears_later_in_bb (insert_stmt, dep_stmt);
>>>> +  else if (not_dominated_by (insert_stmt, dep_stmt))
>>>>      insert_stmt = dep_stmt;
>>>>    return insert_stmt;
>>>>  }
>
>