[gcc r12-5228] path solver: Compute all PHI ranges simultaneously.

[gcc r12-5228] path solver: Compute all PHI ranges simultaneously.

[Aldy Hernandez]

https://gcc.gnu.org/g:b7a23949b0dcc4205fcc2be6b84b91441faa384d

commit r12-5228-gb7a23949b0dcc4205fcc2be6b84b91441faa384d
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Sat Nov 13 12:37:25 2021 +0100

    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.

Diff:
---
 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(-)

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;
+}