Re: [COMMITTED] path solver: Solve PHI imports first for ranges.

[Aldy Hernandez <aldyh@redhat.com>]

On Sat, Nov 13, 2021 at 1:51 AM Andrew MacLeod <amacleod@redhat.com> wrote:
>
> On 11/12/21 14:50, Richard Biener via Gcc-patches wrote:
> > On November 12, 2021 8:46:25 PM GMT+01:00, Aldy Hernandez via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
> >> PHIs must be resolved first while solving ranges in a block,
> >> regardless of where they appear in the import bitmap.  We went through
> >> a similar exercise for the relational code, but missed these.
> > Must not all stmts be resolved in program order (for optimality at least)?
>
> Generally,Imports are live on entry values to a block, so their order is
> not particularly important.. they are all simultaneous. PHIs are also
> considered imports for data flow purposes, but they happen before the
> first stmt, all simultaneously... they need to be distinguished because
> phi arguments can refer to other phi defs which may be in this block
> live around a back edge, and we need to be sure we get the right version.
>
> we should look closer to be sure this isn't an accidental fix that
> leaves the root problem .   we need to be sure *all* the PHI arguments
> are resolved from outside this block. whats the testcase?

The testcase is the simpler testcase from the PR:

https://gcc.gnu.org/bugzilla/attachment.cgi?id=51776

The gist is on a path coming in from BB13:

    # n_42 = PHI <m_31(13), addr_14(D)(4)>
    # m_31 = PHI <0(13), m_16(4)>

We were solving m_31 first and putting it in the cache, and then the
calculation for n_42 picked up this cached m_31 incorrectly.

With my patch we do the PHIs first, in whatever gphi_iterator order
uses, which I assume is the order in the IL above.

However, if PHIs must be resolved simultaneously, then perhaps we need
to tweak this.  Suppose we flip the definitions:

    # m_31 = PHI <0(13), m_16(4)>
    # n_42 = PHI <m_31(13), addr_14(D)(4)>

I assume the definition of n_42 should pick up the incoming m_31(13),
not one defined in the other PHI.  In which case, we could resolve all
the PHIs first, but put them in the cache after we're done with all of
them.

Thoughts?
Aldy