On Sat, Nov 13, 2021 at 10:41 AM Aldy Hernandez <al...@redhat.com> wrote:
>
> On Sat, Nov 13, 2021 at 1:51 AM Andrew MacLeod <amacl...@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.
From bbe7d177711cd930d2b66679482a6892d9bd4348 Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <al...@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
