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

Aldy Hernandez aldyh@redhat.com
Sat Nov 13 13:43:53 GMT 2021


On Sat, Nov 13, 2021 at 12:55 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> On Sat, Nov 13, 2021 at 10:41 AM Aldy Hernandez <aldyh@redhat.com> wrote:
> >
> > 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.
>
> And lo and behold, a PR just came in exhibiting this exact behavior,
> saving me from having to come up with a reduced testcase ;-).
>
> The testcase in the PR has a path coming in from BB5:
>
>     # p3_7 = PHI <1(2), 0(5)>
>     # p2_17 = PHI <1(2), p3_7(5)>
>
> We're picking up the p3_7 in the PHI when calculating p2_17.
>
> Attached is the patch in testing.

Tested on x86-64 & ppc64le Linux.

Pushed.



More information about the Gcc-patches mailing list