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

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

[Aldy Hernandez]

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.

Tested on x86-64 & ppc64le Linux.

gcc/ChangeLog:

	PR tree-optimization/103202
	* gimple-range-path.cc
	(path_range_query::compute_ranges_in_block): Solve PHI imports first.
---
 gcc/gimple-range-path.cc | 15 +++++++++++++--
 1 file changed, 13 insertions(+), 2 deletions(-)

diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index b9aceaf2565..71b290434cb 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -365,12 +365,23 @@ path_range_query::compute_ranges_in_block (basic_block bb)
 	clear_cache (name);
     }
 
-  // Solve imports defined in this block.
+  // Solve imports defined in this block, starting with the PHIs...
+  for (gphi_iterator iter = gsi_start_phis (bb); !gsi_end_p (iter);
+       gsi_next (&iter))
+    {
+      gphi *phi = iter.phi ();
+      tree name = gimple_phi_result (phi);
+
+      if (import_p (name) && range_defined_in_block (r, name, bb))
+	set_cache (r, name);
+    }
+  // ...and then the rest of the imports.
   EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
     {
       tree name = ssa_name (i);
 
-      if (range_defined_in_block (r, name, bb))
+      if (gimple_code (SSA_NAME_DEF_STMT (name)) != GIMPLE_PHI
+	  && range_defined_in_block (r, name, bb))
 	set_cache (r, name);
     }
 
-- 
2.31.1

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

[Richard Biener]

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)? 

>Tested on x86-64 & ppc64le Linux.
>
>gcc/ChangeLog:
>
>	PR tree-optimization/103202
>	* gimple-range-path.cc
>	(path_range_query::compute_ranges_in_block): Solve PHI imports first.
>---
> gcc/gimple-range-path.cc | 15 +++++++++++++--
> 1 file changed, 13 insertions(+), 2 deletions(-)
>
>diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
>index b9aceaf2565..71b290434cb 100644
>--- a/gcc/gimple-range-path.cc
>+++ b/gcc/gimple-range-path.cc
>@@ -365,12 +365,23 @@ path_range_query::compute_ranges_in_block (basic_block bb)
> 	clear_cache (name);
>     }
> 
>-  // Solve imports defined in this block.
>+  // Solve imports defined in this block, starting with the PHIs...
>+  for (gphi_iterator iter = gsi_start_phis (bb); !gsi_end_p (iter);
>+       gsi_next (&iter))
>+    {
>+      gphi *phi = iter.phi ();
>+      tree name = gimple_phi_result (phi);
>+
>+      if (import_p (name) && range_defined_in_block (r, name, bb))
>+	set_cache (r, name);
>+    }
>+  // ...and then the rest of the imports.
>   EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
>     {
>       tree name = ssa_name (i);
> 
>-      if (range_defined_in_block (r, name, bb))
>+      if (gimple_code (SSA_NAME_DEF_STMT (name)) != GIMPLE_PHI
>+	  && range_defined_in_block (r, name, bb))
> 	set_cache (r, name);
>     }
> 

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

[Aldy Hernandez]

On Fri, Nov 12, 2021, 20:50 Richard Biener <richard.guenther@gmail.com>
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)?
>

The recursion takes care of that. Dependencies get taken care of before the
definitions that need them. I've yet to see a case where we get it wrong,
even in the presence of loops and interdependencies. Well....except in the
phis cause we should've done them first. :-)

Aldy

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

[Andrew MacLeod]

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?

>
>> Tested on x86-64 & ppc64le Linux.
>>
>> gcc/ChangeLog:
>>
>> 	PR tree-optimization/103202
>> 	* gimple-range-path.cc
>> 	(path_range_query::compute_ranges_in_block): Solve PHI imports first.
>> ---
>> gcc/gimple-range-path.cc | 15 +++++++++++++--
>> 1 file changed, 13 insertions(+), 2 deletions(-)
>>
>> diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
>> index b9aceaf2565..71b290434cb 100644
>> --- a/gcc/gimple-range-path.cc
>> +++ b/gcc/gimple-range-path.cc
>> @@ -365,12 +365,23 @@ path_range_query::compute_ranges_in_block (basic_block bb)
>> 	clear_cache (name);
>>      }
>>
>> -  // Solve imports defined in this block.
>> +  // Solve imports defined in this block, starting with the PHIs...
>> +  for (gphi_iterator iter = gsi_start_phis (bb); !gsi_end_p (iter);
>> +       gsi_next (&iter))
>> +    {
>> +      gphi *phi = iter.phi ();
>> +      tree name = gimple_phi_result (phi);
>> +
>> +      if (import_p (name) && range_defined_in_block (r, name, bb))
>> +	set_cache (r, name);
>> +    }
>> +  // ...and then the rest of the imports.
>>    EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
>>      {
>>        tree name = ssa_name (i);
>>
>> -      if (range_defined_in_block (r, name, bb))
>> +      if (gimple_code (SSA_NAME_DEF_STMT (name)) != GIMPLE_PHI
>> +	  && range_defined_in_block (r, name, bb))
>> 	set_cache (r, name);
>>      }
>>

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

[Aldy Hernandez]

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

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

[Aldy Hernandez]

[-- Attachment #1: Type: text/plain, Size: 2584 bytes --]

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.

[-- Attachment #2: 0001-path-solver-Compute-all-PHI-ranges-simultaneously.patch --]
[-- Type: text/x-patch, Size: 4644 bytes --]

From bbe7d177711cd930d2b66679482a6892d9bd4348 Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <aldyh@redhat.com>
Date: Sat, 13 Nov 2021 12:37:25 +0100
Subject: [PATCH] path solver: Compute all PHI ranges simultaneously.

PHIs must be resolved simulatenously, otherwise we may not pick up the
ranges incoming to the block.

For example.  If we put p3_7 in the cache before all PHIs have been
computed, we will pick up the wrong p3_7 value for p2_17:

    # p3_7 = PHI <1(2), 0(5)>
    # p2_17 = PHI <1(2), p3_7(5)>

This patch delays updating the cache until all PHIs have been
analyzed.

gcc/ChangeLog:

	PR tree-optimization/103222
	* gimple-range-path.cc (path_range_query::compute_ranges_in_phis):
	New.
	(path_range_query::compute_ranges_in_block): Call
	compute_ranges_in_phis.
	* gimple-range-path.h (path_range_query::compute_ranges_in_phis):
	New.

gcc/testsuite/ChangeLog:

	* gcc.dg/pr103222.c: New test.
---
 gcc/gimple-range-path.cc        | 42 ++++++++++++++++++++++++++-------
 gcc/gimple-range-path.h         |  3 +++
 gcc/testsuite/gcc.dg/pr103222.c | 33 ++++++++++++++++++++++++++
 3 files changed, 69 insertions(+), 9 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/pr103222.c

diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index 32b2cb57597..9957ac9b6c7 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -343,6 +343,38 @@ path_range_query::range_defined_in_block (irange &r, tree name, basic_block bb)
   return true;
 }
 
+// Compute ranges defined in the PHIs in this block.
+
+void
+path_range_query::compute_ranges_in_phis (basic_block bb)
+{
+  int_range_max r;
+  gphi_iterator iter;
+
+  // PHIs must be resolved simultaneously on entry to the block
+  // because any dependencies must be satistifed with values on entry.
+  // Thus, we calculate all PHIs first, and then update the cache at
+  // the end.
+
+  m_tmp_phi_cache.clear ();
+  for (iter = gsi_start_phis (bb); !gsi_end_p (iter); gsi_next (&iter))
+    {
+      gphi *phi = iter.phi ();
+      tree name = gimple_phi_result (phi);
+
+      if (import_p (name) && range_defined_in_block (r, name, bb))
+	m_tmp_phi_cache.set_global_range (name, r);
+    }
+  for (iter = gsi_start_phis (bb); !gsi_end_p (iter); gsi_next (&iter))
+    {
+      gphi *phi = iter.phi ();
+      tree name = gimple_phi_result (phi);
+
+      if (m_tmp_phi_cache.get_global_range (r, name))
+	set_cache (r, name);
+    }
+}
+
 // Compute ranges defined in the current block, or exported to the
 // next block.
 
@@ -369,15 +401,7 @@ path_range_query::compute_ranges_in_block (basic_block bb)
     }
 
   // Solve imports defined in this block, starting with the PHIs...
-  for (gphi_iterator iter = gsi_start_phis (bb); !gsi_end_p (iter);
-       gsi_next (&iter))
-    {
-      gphi *phi = iter.phi ();
-      tree name = gimple_phi_result (phi);
-
-      if (import_p (name) && range_defined_in_block (r, name, bb))
-	set_cache (r, name);
-    }
+  compute_ranges_in_phis (bb);
   // ...and then the rest of the imports.
   EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
     {
diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h
index f8b2b04e57c..c80734f65a1 100644
--- a/gcc/gimple-range-path.h
+++ b/gcc/gimple-range-path.h
@@ -58,6 +58,7 @@ private:
   // Methods to compute ranges for the given path.
   bool range_defined_in_block (irange &, tree name, basic_block bb);
   void compute_ranges_in_block (basic_block bb);
+  void compute_ranges_in_phis (basic_block bb);
   void adjust_for_non_null_uses (basic_block bb);
   void ssa_range_in_phi (irange &r, gphi *phi);
   void compute_outgoing_relations (basic_block bb, basic_block next);
@@ -80,6 +81,8 @@ private:
   // Range cache for SSA names.
   ssa_global_cache *m_cache;
 
+  ssa_global_cache m_tmp_phi_cache;
+
   // Set for each SSA that has an active entry in the cache.
   bitmap m_has_cache_entry;
 
diff --git a/gcc/testsuite/gcc.dg/pr103222.c b/gcc/testsuite/gcc.dg/pr103222.c
new file mode 100644
index 00000000000..2a84437b25d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr103222.c
@@ -0,0 +1,33 @@
+// { dg-do run }
+// { dg-options "-O2" }
+
+#include <stdint.h>
+#include <stdio.h>
+int16_t a;
+static uint32_t *b ;
+static uint8_t func_2();
+static int32_t func_1() {
+  int16_t a = 1;
+  func_2(0, a, a);
+  return 0;
+}
+uint8_t func_2(uint32_t p1, uint32_t p2, uint32_t p3) {
+  int p = 0;
+  for (15;; a++) {
+    for (0;;) {
+      if (p2)
+        break;
+      b = &p2;
+      return p2;
+    }
+     p3 = (p2 = p3, p);
+  }
+  return 0;
+}
+
+int main() {
+  func_1();
+  if (a != 2)
+    __builtin_abort ();
+  return 0;
+}
-- 
2.31.1

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

[Richard Biener]

On November 13, 2021 10:41:02 AM GMT+01:00, 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.

PHI order is irrelevant, they are executed in parallel, thus arguments pick up the old value irrespective of order. 

Richard. 
>
>Thoughts?
>Aldy
>

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

[Aldy Hernandez]

On Sat, Nov 13, 2021 at 2:26 PM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On November 13, 2021 10:41:02 AM GMT+01:00, 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.
>
> PHI order is irrelevant, they are executed in parallel, thus arguments pick up the old value irrespective of order.
>

Ughh, yeah.  Just noticed, per my follow-up patch for PR103222.

Tested on x86-64 & ppc64le Linux, and pushed.

Thanks.
Aldy

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

[Aldy Hernandez]

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.