[PATCH v6] tree-optimization/101186 - extend FRE with "equivalence map" for condition prediction

[PATCH v6] tree-optimization/101186 - extend FRE with "equivalence map" for condition prediction

[Di Zhao OS]

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

Sorry for the late update. I've been on a vacation and then I
spent some time updating and verifying the patch.

Attached is a new version of the patch. There are some changes:

1. Store equivalences in a vn_pval chain in vn_ssa_aux, rather than
   in the expression hash table. (Following Richard's suggestion.)
2. Extracted insert_single_predicated_value function.
3. Simplify record_equiv_from_prev_phi a bit.
4. Changed some of the functions' names and tried to improve the
   comments a little.

Current status of the new testcases in the patch:

ssa-fre-200.c	Can also be optimized by evrp
ssa-fre-201.c	Not optimized in trunk.
ssa-fre-202.c	foo() can be removed by evrp; while x + b is not
		folded.
ssa-pre-34.c	Not optimized in trunk.

Initially, this patch is motivated to remove the unreachable codes
in case like ssa-pre-34.c, in which we need to use equivalence
relation produced from a preceding condition for another condition.
VRP didn't optimize that because it needs jump threading to make
the relation valid at the second condition.

After browsing the mechanisms of VRP and FRE, it seems to me there
are two options: 1) Teach VRP to identify related but not threaded
conditions. That might require introducing value-numbering into VRP 
to detect common expressions, and I think is too much for this. 
2) Introduce temporary equivalence in sccvn, which I thought would
change less on current code. (And along the reviews and updating
patch I see how ad-hoc it was.)

I saw from the talk about VN there's plan to replace predicated
values by ranger. So how does it goes? Is there something I can help
with? (For the case ssa-pre-34.c, I think maybe it still needs the
predicated-value support, to lookup related conditional expressions.)

Below are about questions in the last review:

> >  /* Valid hashtables storing information we have proven to be
> >     correct.  */
> > @@ -490,9 +492,9 @@ VN_INFO (tree name)
> >  	    nary->predicated_values = 0;
> >  	    nary->u.result = boolean_true_node;
> >  	    vn_nary_op_insert_into (nary, valid_info->nary);
> > -	    gcc_assert (nary->unwind_to == NULL);
> 
> why's that?  doesn't this mean unwinding will be broken?

Previously, predicate "argument_x == NULL" or "argument_x != NULL"
is always new here (because argument_x's VN is just inserted.)
But with the patch, there can be slot for "argument_x == NULL"
or "argument_x != NULL" already. It won't break unwinding as the
new value is not linked to the unwind-chain.

> 
> >  	    /* Also do not link it into the undo chain.  */
> >  	    last_inserted_nary = nary->next;
> > +	    /* There could be a predicate already.  */
> >  	    nary->next = (vn_nary_op_t)(void *)-1;
> >  	    nary = alloc_vn_nary_op_noinit (2, &vn_tables_insert_obstack);
> >  	    init_vn_nary_op_from_pieces (nary, 2, EQ_EXPR,

> >  /* Compute and return the hash value for nary operation VBO1.  */
> >  
> >  hashval_t
> > @@ -4226,6 +4342,9 @@ init_vn_nary_op_from_stmt (vn_nary_op_t vno, gassign *stmt)
> >        for (i = 0; i < vno->length; ++i)
> >  	vno->op[i] = gimple_op (stmt, i + 1);
> >      }
> > +  /* Insert and lookup N-ary results by the operands' equivalence heads.  */
> > +  if (gimple_bb (stmt))
> > +    lookup_equiv_heads (vno->length, vno->op, vno->op, gimple_bb (stmt));
> 
> That seems like the wrong place, the function didn't even valueize before.

To utilize temp-equivalences and get more simplified result, n-ary
expressions should be always inserted and lookup by the operands'
equivalence heads. So practically all the places
init_vn_nary_op_from_stmt is used, lookup_equiv_heads (changed to
get_equiv_heads) should be called. As I haven't found better place
to put that, I just left it here in the patch..

> >  visit_nary_op (tree lhs, gassign *stmt)
> >  {
> >    vn_nary_op_t vnresult;
> > -  tree result = vn_nary_op_lookup_stmt (stmt, &vnresult);
> > -  if (! result && vnresult)
> > +  unsigned length = vn_nary_length_from_stmt (stmt);
> > +  vn_nary_op_t vno
> > +    = XALLOCAVAR (struct vn_nary_op_s, sizeof_vn_nary_op (length));
> > +  init_vn_nary_op_from_stmt (vno, stmt);
> > +  tree result = NULL_TREE;
> > +  /* Try to get a simplified result.  */
> > +  /* Do not simplify variable used in PHI at loop exit, or
> > +     simplify_peeled_chrec/constant_after_peeling may miss the loop.  */
> > +  gimple *use_stmt;
> > +  use_operand_p use_p;
> > +  if (!(single_imm_use (lhs, &use_p, &use_stmt)
> > +	&& gimple_code (use_stmt) == GIMPLE_PHI
> > +	&& single_succ_p (gimple_bb (use_stmt))
> > +	&& (single_succ_edge (gimple_bb (use_stmt))->flags & EDGE_DFS_BACK)))
> > +    result = fold_const_from_equiv_heads (vno->length, vno->opcode, vno->op,
> > +					  vno->type);
> 
> copy propagating conditional equivalences has proved problematic, why
> do this at all when there's no actual simplification?  It's a bit odd that
> we need a special fold_const_from_equiv_heads here, why is general
> valueization not handling equivalences?  Are they supposed to be only
> used for simplifying conditionals?

With temporary equivalences introduced, expressions like "a - equiv(a)"
and "a == equiv (a)" can be folded, and no need to store predicates
like "a == b is true". The function fold_const_from_equiv_heads is
intended to limit the usage of gimple_simplify, to when a constant can
be folded using equivalences. The code seems too complex but I haven't
figured out how to improve it yet. (I'm not very acquainted on how to 
use the simplifying utility properly, I hope I can get some advices
here.) Also, could I have more details about "copy propagating
conditional equivalences has proved problematic" ?

Thank you very much,
Di Zhao

----

Extend FRE with temporary equivalences.

2022-10-24  Di Zhao  <dizhao@os.amperecomputing.com>

gcc/ChangeLog:

        * tree-ssa-sccvn.cc (VN_INFO): remove assertions (there could be
        a predicate already).
        (dominated_by_p_w_unex): Moved upward.
        (is_pval_valid_at_bb): Check if vn_pval is valid at BB.
        (get_equiv_head): Returns the "equivalence head" of given node.
        (get_equiv_heads): Get the "equivalence head"s of given nodes.
        (init_vn_nary_op_from_stmt): Insert and lookup nary expressions
        by "equivalence head"s.
        (insert_single_predicated_value): Extracted utility.
        (vn_nary_op_insert_into): Use the extracted utility
        insert_single_predicated_value.
        (fold_const_from_equiv_heads): Fold N-ary expression to constant
        by equiv-heads.
        (push_new_nary_ref): Insert a back-reference to vn_nary_op_t.
        (alloc_single_predicated_value): Extracted utility.
        (push_single_equiv): Push a new value to the equivalence list.
        (record_temporary_equivalence): Record temporary equivalence.
        (vn_nary_op_insert_pieces_predicated): Record equivalences
        instead of some predicates; insert back-refs.
        (record_equiv_from_prev_phi_1): Record temporary equivalences
        generated by PHI nodes.
        (record_equiv_from_prev_phi): Given a taken edge of a conditional
        branch, record equivalences generated by PHI nodes.
        (visit_nary_op): Lookup previous results of N-ary operations by
        equivalences.
        (insert_related_predicates_on_edge): Some predicates can be
        computed from equivalences, no need to insert them.
        (process_bb): Add lookup predicated values by equivalences.
        (struct unwind_state): Unwind state of back-refs and temporary
        equivalences.
        (do_unwind): Unwind the back-refs and temporary equivalences.
        (do_rpo_vn_1): Update unwind state of back-reference and
        temporary equivalences.
        * tree-ssa-sccvn.h (struct temp_equiv): In vn_ssa_aux, hold a
        list of temporary equivalences.
        (struct nary_ref): In vn_ssa_aux, hold a lists of references to
        the nary map entries.

gcc/testsuite/ChangeLog:

        * g++.dg/pr83541.C: Disable fre.
        * gcc.dg/tree-ssa/pr68619-2.c: Disable fre.
        * gcc.dg/tree-ssa/pr71947-1.c: Disable fre.
        * gcc.dg/tree-ssa/pr71947-2.c: Disable fre.
        * gcc.dg/tree-ssa/pr71947-3.c: Disable fre.
        * gcc.dg/tree-ssa/pr71947-5.c: Disable fre.
        * gcc.dg/tree-ssa/pr71947-7.c: Disable fre.
        * gcc.dg/tree-ssa/pr71947-8.c: Disable fre.
        * gcc.dg/tree-ssa/pr71947-9.c: Disable fre.
        * gcc.dg/tree-ssa/vrp03.c: Disable fre.
        * gcc.dg/tree-ssa/ssa-fre-200.c: New test.
        * gcc.dg/tree-ssa/ssa-fre-201.c: New test.
        * gcc.dg/tree-ssa/ssa-fre-202.c: New test.
        * gcc.dg/tree-ssa/ssa-pre-34.c: New test.

[-- Attachment #2: v6-tree-optimization-101186.patch --]
[-- Type: application/octet-stream, Size: 41398 bytes --]

diff --git a/gcc/testsuite/g++.dg/pr83541.C b/gcc/testsuite/g++.dg/pr83541.C
index f5b181e064a..c9a550a6d08 100644
--- a/gcc/testsuite/g++.dg/pr83541.C
+++ b/gcc/testsuite/g++.dg/pr83541.C
@@ -1,6 +1,6 @@
 // PR tree-optimization/83541
 // { dg-do compile }
-// { dg-options "-O3 -std=c++17 -ffast-math -fdump-tree-evrp"  }
+// { dg-options "-O3 -fno-tree-fre -std=c++17 -ffast-math -fdump-tree-evrp"  }
 
 #include <limits>
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr68619-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr68619-2.c
index cca706e0c4f..0a99c3c620e 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr68619-2.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr68619-2.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-dom2-details -w" } */
+/* { dg-options "-O2 -fno-tree-fre -fdump-tree-dom2-details -w" } */
 
 typedef union tree_node *tree;
 struct gcc_options
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-1.c
index ac8271cc574..e9a797e82b0 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-1.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-1.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */ 
-/* { dg-options "-O2 -fno-tree-vrp -fdump-tree-dom-details" } */
+/* { dg-options "-O2 -fno-tree-vrp -fno-tree-fre -fdump-tree-dom-details" } */
 
 
 int f(int x, int y)
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-2.c
index b2c09cbb021..bcbc419575c 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-2.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-2.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fno-tree-vrp -fdump-tree-dom-details" } */
+/* { dg-options "-O2 -fno-tree-vrp -fno-tree-fre -fdump-tree-dom-details" } */
 
 
 int f(int x, int y)
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-3.c b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-3.c
index 2316f7e1c04..d63291da440 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-3.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-3.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fno-tree-vrp -fdump-tree-dom-details" } */
+/* { dg-options "-O2 -fno-tree-vrp -fno-tree-fre -fdump-tree-dom-details" } */
 
 int f(int x, int y)
 {
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-5.c b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-5.c
index e7038d0237f..c1e5667b45a 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-5.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-5.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fno-tree-vrp -fdump-tree-dom-details" } */
+/* { dg-options "-O2 -fno-tree-vrp -fno-tree-fre -fdump-tree-dom-details" } */
 
 
 static inline long load(long *p)
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-7.c b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-7.c
index b44c064aa23..069e4a106c3 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-7.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-7.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fno-tree-vrp -fdump-tree-dom-details" } */
+/* { dg-options "-O2 -fno-tree-vrp -fno-tree-fre -fdump-tree-dom-details" } */
 
 
 int f(int x, int y)
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-8.c b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-8.c
index 26e5abbdc29..26b303e896e 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-8.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-8.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fno-tree-vrp -fdump-tree-dom-details" } */
+/* { dg-options "-O2 -fno-tree-vrp -fno-tree-fre -fdump-tree-dom-details" } */
 
 
 int f(int x, int y)
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-9.c b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-9.c
index 22b68d5ede0..3ed3bf6ad29 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-9.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-9.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fno-tree-vrp -fdump-tree-dom-details" } */
+/* { dg-options "-O2 -fno-tree-vrp -fno-tree-fre -fdump-tree-dom-details" } */
 
 
 int f(int x, int y)
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-200.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-200.c
new file mode 100644
index 00000000000..ccb0fdaa698
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-200.c
@@ -0,0 +1,45 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-fre1" } */
+
+extern void bar(void);
+extern void boo(void);
+extern void foo(void);
+
+/* Test temporary equivalences: basic.  */
+
+void f (unsigned int a, unsigned int b)
+{
+  if (a == b)
+    {
+      for (unsigned i = 0; i < a; i++)
+	{
+	  bar ();
+	  if (i >= b)
+	    /* Unreachable.  */
+	    foo ();
+	}
+    }
+}
+
+/* Test temporary equivalences: transitive.  */
+
+void g (unsigned int a, unsigned int b, unsigned int c)
+{
+  for (unsigned i = 0; i < c; i++)
+    {
+      if (a == b)
+	{
+	  if (b == c)
+	    {
+	      boo ();
+	      if (i >= a)
+		/* Unreachable.  */
+		foo ();
+	    }
+	}
+    }
+}
+
+/* { dg-final { scan-tree-dump-not "foo" "fre1" } } */
+/* { dg-final { scan-tree-dump "bar" "fre1" } } */
+/* { dg-final { scan-tree-dump "boo" "fre1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-201.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-201.c
new file mode 100644
index 00000000000..824b2553ea5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-201.c
@@ -0,0 +1,83 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-fre1" } */
+
+extern void bar(void);
+extern void bag(void);
+extern void bass(void);
+extern void foo(void);
+
+void f (unsigned int a, unsigned int b)
+{
+  if (a == b)
+    {
+      for (unsigned i = a; i < 100; i++)
+	{
+	  if (i > b)
+	    /* Should not be eliminated.  */
+	    bar ();
+	}
+    }
+}
+
+/* Test temporary equivalences: derived condition.  */
+
+int gg;
+
+void g (int a, int b, int d)
+{
+  int c = 100;
+  if (a > 0)
+    {
+      c = b;
+      gg++;
+    }
+  else
+    /* a <= 0 */
+    {
+      c = d;
+      gg--;
+    }
+  for (int i = 0; i < c; i++)
+    {
+      if (a >= 0)
+	{
+	  if (i >= b)
+	    /* Should not be eliminated. ("a >= 0" cannot derive "a > 0".)  */
+	    bass ();
+	}
+      else
+	/* a < 0 */
+	{
+	  if (i >= d)
+	    /* Should be eliminated, as "a < 0" can derive "a <= 0".  */
+	    foo ();
+	}
+    }
+}
+
+/* Test temporary equivalences: no domination.  */
+
+void h (unsigned int a, unsigned int b)
+{
+  unsigned int c = 100;
+  if (b % 2)
+    {
+      if (a != 0)
+	c = b;
+    }
+  for (unsigned i = 0; i < c; i++)
+    {
+      if (a != 0)
+	{
+	  if (i >= b)
+	    /* Should not be eliminated.  */
+	    bag ();
+	}
+      i++;
+    }
+}
+
+/* { dg-final { scan-tree-dump "bar" "fre1" } } */
+/* { dg-final { scan-tree-dump "bass" "fre1" } } */
+/* { dg-final { scan-tree-dump "bag" "fre1" } } */
+/* { dg-final { scan-tree-dump-not "foo" "fre1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-202.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-202.c
new file mode 100644
index 00000000000..809730f9351
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-202.c
@@ -0,0 +1,43 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-fre1" } */
+
+extern void bar(void);
+extern void bag(void);
+extern void foo(void);
+int g;
+
+/* Test temporary equivalences: optimize N-ary expressions.  */
+
+void
+f (unsigned int a, unsigned int b, unsigned int x, unsigned int y)
+{
+  if (a == b)
+    {
+      g = 100;
+      if (a + x == 99)
+	g = x + b; /* should be simplified to 99 */
+    }
+  else
+    // a!= b
+    {
+      if (a == 100 - x)
+	{
+	  g++;
+	  if (b == 100 - x)
+	    foo (); /* should be removed */
+	}
+      else
+	{
+	  g--;
+	  if (b == 100 - x)
+	    bag (); /* should not be removed */
+	  else
+	    bar (); /* should not be removed */
+	}
+    }
+}
+
+/* { dg-final { scan-tree-dump "bag" "fre1" } } */
+/* { dg-final { scan-tree-dump "bar" "fre1" } } */
+/* { dg-final { scan-tree-dump-not "foo" "fre1" } } */
+/* { dg-final { scan-tree-dump-not "= b_\[0-9]+\\(\[A-Z]+\\) \\+ x_" "fre1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-34.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-34.c
new file mode 100644
index 00000000000..a4001e526fe
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-34.c
@@ -0,0 +1,64 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-pre" } */
+#include <stdio.h>
+
+extern void bag(void);
+extern void bass(void);
+
+#define PRINT(X) for (size_t i = 0; i < 10; i++) printf ("%s%s%s%s\n", X, X, X, X);
+#define PRINT2(X) for (size_t i = 0; i < 10; i++) printf ("%d%d%d%d\n", X, X, X, X);
+
+__inline__ __attribute__((always_inline))
+void a_long_func ()
+{
+  PRINT("A"); PRINT("X"); PRINT("C"); PRINT("D"); PRINT("X"); PRINT("F");
+  PRINT("G"); PRINT("H"); PRINT("M"); PRINT("J"); PRINT("K"); PRINT("L");
+  PRINT2(1); PRINT2(7); PRINT2(111); PRINT2(3434); PRINT2(1111); PRINT2(999);
+  PRINT2(-9); PRINT2(232); PRINT2(111232); PRINT2(666); PRINT2(10); PRINT2(-0);
+}
+
+/* Test temporary equivalences: identical condition.  */
+
+void h (int a, int b, int x, int y)
+{
+  int c = y;
+  if (a != 0)
+    c = x;
+  while (b < 1000)
+    {
+      if (a != 0)
+	{
+	  if (c > x)
+	    /* Unreachable.  */
+	    a_long_func ();
+	}
+      else
+	bass ();
+      b++;
+    }
+}
+
+/* Test temporary equivalences: derived condition.  */
+
+void k (int a, int b, int x, int y)
+{
+  int c = y;
+  if (a != b)
+    c = x;
+  for (int i = 0; i < 1000; i++)
+    {
+      if (a < b)
+	/* All paths reaching "a>0 is true" come from "a!=0 is true".  */
+	{
+	  if (c > x)
+	    /* Unreachable.  */
+	    a_long_func ();
+	}
+      else
+	bag ();
+    }
+}
+
+/* { dg-final { scan-tree-dump-not "printf \\(" "pre" } } */
+/* { dg-final { scan-tree-dump "bag \\(\\)" "pre" } } */
+/* { dg-final { scan-tree-dump "bass \\(\\)" "pre" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp03.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp03.c
index 4cbaca41332..69b83b6cc30 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp03.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp03.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-vrp1 -fno-thread-jumps" } */
+/* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-vrp1 -fno-thread-jumps -fno-tree-fre" } */
 
 struct A
 {
diff --git a/gcc/tree-ssa-sccvn.cc b/gcc/tree-ssa-sccvn.cc
index 37484403c56..10df3b46479 100644
--- a/gcc/tree-ssa-sccvn.cc
+++ b/gcc/tree-ssa-sccvn.cc
@@ -355,6 +355,10 @@ static vn_reference_t last_inserted_ref;
 static vn_phi_t last_inserted_phi;
 static vn_nary_op_t last_inserted_nary;
 static vn_ssa_aux_t last_pushed_avail;
+static vn_ssa_aux_t last_pushed_nary_ref;
+static vn_ssa_aux_t last_pushed_equiv;
+static nary_ref* nary_ref_freelist;
+static temp_equiv* temp_equiv_freelist;
 
 /* Valid hashtables storing information we have proven to be
    correct.  */
@@ -489,8 +493,8 @@ VN_INFO (tree name)
 					 boolean_type_node, ops);
 	    nary->predicated_values = 0;
 	    nary->u.result = boolean_true_node;
+	    /* There could be a predicate already.  */
 	    vn_nary_op_insert_into (nary, valid_info->nary);
-	    gcc_assert (nary->unwind_to == NULL);
 	    /* Also do not link it into the undo chain.  */
 	    last_inserted_nary = nary->next;
 	    nary->next = (vn_nary_op_t)(void *)-1;
@@ -500,7 +504,6 @@ VN_INFO (tree name)
 	    nary->predicated_values = 0;
 	    nary->u.result = boolean_false_node;
 	    vn_nary_op_insert_into (nary, valid_info->nary);
-	    gcc_assert (nary->unwind_to == NULL);
 	    last_inserted_nary = nary->next;
 	    nary->next = (vn_nary_op_t)(void *)-1;
 	    if (dump_file && (dump_flags & TDF_DETAILS))
@@ -4162,6 +4165,77 @@ vn_nary_op_compute_hash (const vn_nary_op_t vno1)
   return hstate.end ();
 }
 
+static bool
+dominated_by_p_w_unex (basic_block bb1, basic_block bb2, bool);
+
+/* Whether a predicated value VAL is valid at BB.  */
+
+static inline bool
+is_pval_valid_at_bb (vn_pval *val, basic_block bb)
+{
+  for (unsigned i = 0; i < val->n; ++i)
+    {
+      basic_block val_bb
+	= BASIC_BLOCK_FOR_FN (cfun, val->valid_dominated_by_p[i]);
+      /* Do not handle backedge executability optimistically since
+	 when figuring out whether to iterate we do not consider
+	 changed predication.  */
+      if (dominated_by_p_w_unex (bb, val_bb, false))
+	return true;
+    }
+  return false;
+}
+
+/* Return the variable that represents temporary equivalences of NAME at
+   basic-block BB.  */
+
+static tree
+get_equiv_head (tree name, basic_block bb)
+{
+  if (TREE_CODE (name) != SSA_NAME)
+    return name;
+  vn_ssa_aux_t info = VN_INFO (name);
+  tree result = info->valnum;
+
+  if (TREE_CODE (result) == SSA_NAME && result != name && result != VN_TOP)
+    info = VN_INFO (result);
+  if (info->equiv)
+    {
+      /* As we insert new value at front in the equiv list, the first result is
+	 the most general result.  */
+      for (vn_pval *val = info->equiv->values; val; val = val->next)
+	if (is_pval_valid_at_bb (val, bb))
+	  return val->result;
+    }
+
+  /* VN_TOP is not allowed.  */
+  if (result == VN_TOP)
+    return name;
+
+  return result;
+}
+
+/* Lookup the "equivalence head"s of OPS at BB, and store them in TO.  N is the
+   size of OPS.  */
+
+static void
+get_equiv_heads (unsigned n, tree *ops, tree *to, basic_block bb)
+{
+  for (unsigned i = 0; i < n; i++)
+    {
+      tree equiv_head = get_equiv_head (ops[i], bb);
+      if (dump_file && (dump_flags & TDF_DETAILS) && equiv_head != ops[i])
+	{
+	  fprintf (dump_file, "Use equiv-head ");
+	  print_generic_expr (dump_file, equiv_head, TDF_NONE);
+	  fprintf (dump_file, " for ");
+	  print_generic_expr (dump_file, ops[i], TDF_NONE);
+	  fprintf (dump_file, " at BB%d\n", bb->index);
+	}
+      to[i] = equiv_head;
+    }
+}
+
 /* Compare nary operations VNO1 and VNO2 and return true if they are
    equivalent.  */
 
@@ -4267,6 +4341,10 @@ init_vn_nary_op_from_stmt (vn_nary_op_t vno, gassign *stmt)
       for (i = 0; i < vno->length; ++i)
 	vno->op[i] = gimple_op (stmt, i + 1);
     }
+
+  /* Insert and lookup N-ary results by the operands' equivalence heads.  */
+  if (gimple_bb (stmt))
+    get_equiv_heads (vno->length, vno->op, vno->op, gimple_bb (stmt));
 }
 
 /* Compute the hashcode for VNO and look for it in the hash table;
@@ -4351,6 +4429,64 @@ alloc_vn_nary_op (unsigned int length, tree result, unsigned int value_id)
   return vno1;
 }
 
+/*  Push to the vn_pval list (stored at LOC); or append to an existing value,
+    and move it to the front.  Returns whether a new value is inserted.  */
+
+static bool
+insert_single_predicated_value (vn_pval **loc, vn_pval *old_list)
+{
+  vn_pval **next = loc;
+  vn_pval *new_val = *next;
+  gcc_assert (!new_val->next && new_val->n == 1);
+  basic_block vno_bb
+    = BASIC_BLOCK_FOR_FN (cfun, new_val->valid_dominated_by_p[0]);
+  /* Avoid inserting duplicated result.  */
+  *next = NULL;
+
+  for (vn_pval *val = old_list; val; val = val->next)
+    {
+      if (expressions_equal_p (val->result, new_val->result))
+	{
+	  for (unsigned i = 0; i < val->n; ++i)
+	    {
+	      basic_block val_bb
+		= BASIC_BLOCK_FOR_FN (cfun, val->valid_dominated_by_p[i]);
+	      if (dominated_by_p (CDI_DOMINATORS, vno_bb, val_bb))
+		/* Value registered with more generic predicate.  */
+		return false;
+	      else if (flag_checking)
+		/* Shouldn't happen, we insert in RPO order.  */
+		gcc_assert (!dominated_by_p (CDI_DOMINATORS, val_bb, vno_bb));
+	    }
+	  /* Append value.  */
+	  new_val = (vn_pval *) obstack_alloc (&vn_tables_obstack,
+					       sizeof (vn_pval)
+						 + val->n * sizeof (int));
+	  new_val->next = NULL;
+	  new_val->result = val->result;
+	  new_val->n = val->n + 1;
+	  memcpy (new_val->valid_dominated_by_p, val->valid_dominated_by_p,
+		  val->n * sizeof (int));
+	  new_val->valid_dominated_by_p[val->n] = vno_bb->index;
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "Appending predicate to value.\n");
+	  continue;
+	}
+      /* Copy other predicated values.  */
+      *next = (vn_pval *) obstack_alloc (&vn_tables_obstack,
+					 sizeof (vn_pval)
+					   + (val->n - 1) * sizeof (int));
+      memcpy (*next, val, sizeof (vn_pval) + (val->n - 1) * sizeof (int));
+      (*next)->next = NULL;
+      next = &(*next)->next;
+    }
+  /* Put new value at front, so get_equiv_head can find the most general
+     result.  */
+  new_val->next = *loc;
+  *loc = new_val;
+  return true;
+}
+
 /* Insert VNO into TABLE.  */
 
 static vn_nary_op_t
@@ -4405,63 +4541,17 @@ vn_nary_op_insert_into (vn_nary_op_t vno, vn_nary_op_table_type *table)
       else if (vno->predicated_values
 	       && (*slot)->predicated_values)
 	{
-	  /* ???  Factor this all into a insert_single_predicated_value
-	     routine.  */
 	  gcc_assert (!vno->u.values->next && vno->u.values->n == 1);
-	  basic_block vno_bb
-	    = BASIC_BLOCK_FOR_FN (cfun, vno->u.values->valid_dominated_by_p[0]);
-	  vn_pval *nval = vno->u.values;
-	  vn_pval **next = &vno->u.values;
-	  bool found = false;
-	  for (vn_pval *val = (*slot)->u.values; val; val = val->next)
+	  if (insert_single_predicated_value (&vno->u.values,
+					      (*slot)->u.values))
 	    {
-	      if (expressions_equal_p (val->result, nval->result))
-		{
-		  found = true;
-		  for (unsigned i = 0; i < val->n; ++i)
-		    {
-		      basic_block val_bb
-			= BASIC_BLOCK_FOR_FN (cfun,
-					      val->valid_dominated_by_p[i]);
-		      if (dominated_by_p (CDI_DOMINATORS, vno_bb, val_bb))
-			/* Value registered with more generic predicate.  */
-			return *slot;
-		      else if (flag_checking)
-			/* Shouldn't happen, we insert in RPO order.  */
-			gcc_assert (!dominated_by_p (CDI_DOMINATORS,
-						     val_bb, vno_bb));
-		    }
-		  /* Append value.  */
-		  *next = (vn_pval *) obstack_alloc (&vn_tables_obstack,
-						     sizeof (vn_pval)
-						     + val->n * sizeof (int));
-		  (*next)->next = NULL;
-		  (*next)->result = val->result;
-		  (*next)->n = val->n + 1;
-		  memcpy ((*next)->valid_dominated_by_p,
-			  val->valid_dominated_by_p,
-			  val->n * sizeof (int));
-		  (*next)->valid_dominated_by_p[val->n] = vno_bb->index;
-		  next = &(*next)->next;
-		  if (dump_file && (dump_flags & TDF_DETAILS))
-		    fprintf (dump_file, "Appending predicate to value.\n");
-		  continue;
-		}
-	      /* Copy other predicated values.  */
-	      *next = (vn_pval *) obstack_alloc (&vn_tables_obstack,
-						 sizeof (vn_pval)
-						 + (val->n-1) * sizeof (int));
-	      memcpy (*next, val, sizeof (vn_pval) + (val->n-1) * sizeof (int));
-	      (*next)->next = NULL;
-	      next = &(*next)->next;
+	      *slot = vno;
+	      vno->next = last_inserted_nary;
+	      last_inserted_nary = vno;
+	      return vno;
 	    }
-	  if (!found)
-	    *next = nval;
-
-	  *slot = vno;
-	  vno->next = last_inserted_nary;
-	  last_inserted_nary = vno;
-	  return vno;
+	  else
+	    return *slot;
 	}
 
       /* While we do not want to insert things twice it's awkward to
@@ -4526,6 +4616,110 @@ can_track_predicate_on_edge (edge pred_e)
   return cnt == 1;
 }
 
+/* Fold N-ary expression of equiv-heads, return NULL_TREE if not folded.  */
+
+static tree
+fold_const_from_equiv_heads (unsigned length, tree_code opcode, tree *op,
+			     tree type)
+{
+  tree result = NULL_TREE;
+  /* We're using equiv-heads, i.e. the most general operands, shortcut for
+     situations that can fold.  */
+  switch (length)
+    {
+    case 1:
+      if (CONSTANT_CLASS_P (op[0]))
+	result
+	  = gimple_simplify (opcode, type, op[0], NULL, no_follow_ssa_edges);
+      break;
+    case 2:
+      if ((CONSTANT_CLASS_P (op[0]) && CONSTANT_CLASS_P (op[1]))
+	  || op[0] == op[1])
+	result = gimple_simplify (opcode, type, op[0], op[1], NULL,
+				  no_follow_ssa_edges);
+      break;
+    case 3:
+      if (CONSTANT_CLASS_P (op[0]) && CONSTANT_CLASS_P (op[1])
+	  && CONSTANT_CLASS_P (op[2]))
+	result = gimple_simplify (opcode, type, op[0], op[1], op[2], NULL,
+				  no_follow_ssa_edges);
+      break;
+    default:
+      break;
+    }
+  if (result && !useless_type_conversion_p (type, TREE_TYPE (result)))
+    result = fold_convert (type, result);
+  return result;
+}
+
+/* Insert a back-reference in INFO.  */
+
+static inline void
+push_new_nary_ref (vn_ssa_aux_t info, vn_nary_op_t vno,
+		   vn_ssa_aux_t equiv)
+{
+  gcc_checking_assert ((!vno && equiv) || (!equiv && vno));
+  nary_ref *ref;
+  if (nary_ref_freelist)
+    {
+      ref = nary_ref_freelist;
+      nary_ref_freelist = nary_ref_freelist->next;
+    }
+  else
+    ref = XOBNEW (&vn_ssa_aux_obstack, nary_ref);
+  ref->next = info->ref;
+  ref->next_undo = last_pushed_nary_ref;
+  last_pushed_nary_ref = info;
+  ref->vno = vno;
+  ref->vn = equiv;
+  info->ref = ref;
+  ++info->num_nary_ref;
+  gcc_assert (info->num_nary_ref > 0);
+}
+
+/* Allocate vn_pval with single result and valid dominator.  */
+
+static vn_pval *
+alloc_single_predicated_value (obstack *stack, tree result, basic_block bb)
+{
+  vn_pval *new_val = (vn_pval *) obstack_alloc (stack, sizeof (vn_pval));
+  new_val->next = NULL;
+  new_val->result = result;
+  new_val->n = 1;
+  new_val->valid_dominated_by_p[0] = bb->index;
+  return new_val;
+}
+
+/* Push a new value to the equivalence list in INFO.  */
+
+static bool
+push_single_equiv (vn_ssa_aux_t info, tree equiv_head, basic_block bb)
+{
+  temp_equiv *equiv;
+  if (temp_equiv_freelist)
+    {
+      equiv = temp_equiv_freelist;
+      temp_equiv_freelist = temp_equiv_freelist->next;
+    }
+  else
+    equiv = XOBNEW (&vn_ssa_aux_obstack, temp_equiv);
+
+  equiv->values
+    = alloc_single_predicated_value (&vn_tables_obstack, equiv_head, bb);
+  if (info->equiv)
+    if (!insert_single_predicated_value (&equiv->values, info->equiv->values))
+      return false;
+
+  equiv->next = info->equiv;
+  info->equiv = equiv;
+  equiv->next_undo = last_pushed_equiv;
+  last_pushed_equiv = info;
+  return true;
+}
+
+static void
+record_temporary_equivalence (tree op1, tree op2, edge e);
+
 static vn_nary_op_t
 vn_nary_op_insert_pieces_predicated (unsigned int length, enum tree_code code,
 				     tree type, tree *ops,
@@ -4534,6 +4728,16 @@ vn_nary_op_insert_pieces_predicated (unsigned int length, enum tree_code code,
 {
   if (!can_track_predicate_on_edge (pred_e))
     return NULL;
+  if (code == EQ_EXPR && result == boolean_true_node)
+    {
+      /* Can be represented by temporary equivalence.  */
+      record_temporary_equivalence (ops[0], ops[1], pred_e);
+      return NULL;
+    }
+  /* Leave this for inverted condition.  */
+  if (code == NE_EXPR && result == boolean_false_node)
+    return NULL;
+
   if (dump_file && (dump_flags & TDF_DETAILS)
       /* ???  Fix dumping, but currently we only get comparisons.  */
       && TREE_CODE_CLASS (code) == tcc_comparison)
@@ -4546,20 +4750,154 @@ vn_nary_op_insert_pieces_predicated (unsigned int length, enum tree_code code,
       fprintf (dump_file, " == %s\n",
 	       integer_zerop (result) ? "false" : "true");
     }
+  if (CHECKING_P)
+    for (unsigned i = 0; i < length; i++)
+      gcc_assert (get_equiv_head (ops[i], pred_e->dest) == ops[i]);
+
+  /* Skip if the result is known. (Caused by re-inserting predicates.)  */
+  tree simplified = fold_const_from_equiv_heads (length, code, ops, type);
+  if (simplified)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "Result is known: ");
+	  print_generic_expr (dump_file, simplified, TDF_NONE);
+	  fprintf (dump_file, ", skipped.\n");
+	}
+      return NULL;
+    }
+
   vn_nary_op_t vno1 = alloc_vn_nary_op (length, NULL_TREE, value_id);
   init_vn_nary_op_from_pieces (vno1, length, code, type, ops);
   vno1->predicated_values = 1;
-  vno1->u.values = (vn_pval *) obstack_alloc (&vn_tables_obstack,
-					      sizeof (vn_pval));
-  vno1->u.values->next = NULL;
-  vno1->u.values->result = result;
-  vno1->u.values->n = 1;
-  vno1->u.values->valid_dominated_by_p[0] = pred_e->dest->index;
-  return vn_nary_op_insert_into (vno1, valid_info->nary);
+  vno1->u.values
+    = alloc_single_predicated_value (&vn_tables_obstack, result, pred_e->dest);
+  vn_nary_op_t val = vn_nary_op_insert_into (vno1, valid_info->nary);
+
+  /* Insert back-refs (operand->vno) to vn_ssa_aux.  */
+  for (unsigned i = 0; i < length; i++)
+    if (TREE_CODE (ops[i]) == SSA_NAME)
+      {
+	vn_ssa_aux_t info = VN_INFO (ops[i]);
+	if (info->valnum == ops[i])
+	  push_new_nary_ref (info, val, NULL);
+      }
+  return val;
 }
 
-static bool
-dominated_by_p_w_unex (basic_block bb1, basic_block bb2, bool);
+/* Record the equivalence of OP1 and OP2 on edge E.  */
+
+static void
+record_temporary_equivalence (tree op1, tree op2, edge e)
+{
+  /* Record by equivalence heads.  */
+  basic_block bb = e->dest;
+  tree lhs = get_equiv_head (op1, bb);
+  tree rhs = get_equiv_head (op2, bb);
+  if (lhs == rhs)
+    return;
+
+  /* Folding expressions from equivalences can generate incorrect values.
+     For excample, operations on 0.0 and -0.0.  So for floating-point values,
+     equivalences are not used.  */
+  if (FLOAT_TYPE_P (TREE_TYPE (lhs)) || FLOAT_TYPE_P (TREE_TYPE (rhs)))
+    return;
+
+  /* Set RHS to be new equiv-head for LHS.  LHS must be SSA_NAME.  */
+  if (TREE_CODE (lhs) != SSA_NAME)
+    {
+      if (TREE_CODE (rhs) != SSA_NAME)
+	return;
+      std::swap (lhs, rhs);
+    }
+  vn_ssa_aux_t rhs_info = NULL, lhs_info = VN_INFO (lhs);
+
+  /* Choose the hand-side with more recorded n-ary expressions as new
+     equivalence head, to make fewer re-insertions.  */
+  if (TREE_CODE (rhs) == SSA_NAME)
+    {
+      rhs_info = VN_INFO (rhs);
+      if (rhs_info->num_nary_ref < lhs_info->num_nary_ref)
+	{
+	  std::swap (lhs, rhs);
+	  std::swap (rhs_info, lhs_info);
+	}
+    }
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Recording equivalence of ");
+      print_generic_expr (dump_file, lhs);
+      fprintf (dump_file, " and ");
+      print_generic_expr (dump_file, rhs);
+      fprintf (dump_file, " at BB%d\n", bb->index);
+    }
+  bool is_new = push_single_equiv (lhs_info, rhs, bb);
+  gcc_checking_assert (is_new);
+
+  /* Back-ref for equivalences is result->slot rather than op->slot, so that
+     when new equiv-head is appended, we can update them.  */
+  if (TREE_CODE (rhs) == SSA_NAME)
+    push_new_nary_ref (rhs_info, NULL, lhs_info);
+
+  /* Iterate on LHS's references, first update equiv-heads, then re-insert
+     former predicates, so that the result will be latest.  */
+  auto_vec<vn_nary_op_t> predicates;
+  auto_vec<tree> results;
+  vn_nary_op_t vno;
+  vn_ssa_aux_t vn;
+  tree old_head = lhs_info->name;
+  nary_ref *ref = lhs_info->ref;
+  for (; ref; ref = ref->next)
+    {
+      /* Update recorded equivalences with new equiv-head.  */
+      if ((vn = ref->vn))
+	{
+	  if (vn->name == rhs)
+	    continue;
+	  for (vn_pval *pval = vn->equiv->values; pval; pval = pval->next)
+	    if (expressions_equal_p (pval->result, old_head)
+		&& is_pval_valid_at_bb (pval, bb))
+	      {
+		if (dump_file && (dump_flags & TDF_DETAILS))
+		  {
+		    fprintf (dump_file, "Updating equiv-head of ");
+		    print_generic_expr (dump_file, vn->name, TDF_SLIM);
+		    fprintf (dump_file, " to ");
+		    print_generic_expr (dump_file, rhs, TDF_SLIM);
+		    fprintf (dump_file, " at BB%d\n", bb->index);
+		  }
+		/* Push back-ref (result->slot) for new equivalence.  */
+		if (push_single_equiv (vn, rhs, bb)
+		    && TREE_CODE (rhs) == SSA_NAME)
+		  push_new_nary_ref (rhs_info, NULL, vn);
+		break;
+	      }
+	}
+      else if (ref->vno->predicated_values)
+	{
+	  /* Predicated values are collected, to be re-inserted later.  */
+	  for (vn_pval *pval = ref->vno->u.values; pval; pval = pval->next)
+	    {
+	      if (!is_pval_valid_at_bb (pval, bb))
+		continue;
+	      predicates.safe_push (ref->vno);
+	      results.safe_push (pval->result);
+	    }
+	}
+    }
+  unsigned i;
+  if (predicates.length () > 0 && dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "Re-inserting %d predicates...\n",
+	     predicates.length ());
+  tree ops[3];
+  FOR_EACH_VEC_ELT (predicates, i, vno)
+    {
+      get_equiv_heads (vno->length, vno->op, ops, e->dest);
+      vn_nary_op_insert_pieces_predicated (vno->length, vno->opcode, vno->type,
+					   ops, results[i], vno->value_id, e);
+    }
+}
 
 static tree
 vn_nary_op_get_predicated_value (vn_nary_op_t vno, basic_block bb)
@@ -4567,17 +4905,114 @@ vn_nary_op_get_predicated_value (vn_nary_op_t vno, basic_block bb)
   if (! vno->predicated_values)
     return vno->u.result;
   for (vn_pval *val = vno->u.values; val; val = val->next)
-    for (unsigned i = 0; i < val->n; ++i)
-      /* Do not handle backedge executability optimistically since
-	 when figuring out whether to iterate we do not consider
-	 changed predication.  */
-      if (dominated_by_p_w_unex
-	    (bb, BASIC_BLOCK_FOR_FN (cfun, val->valid_dominated_by_p[i]),
-	     false))
-	return val->result;
+    if (is_pval_valid_at_bb (val, bb))
+      return val->result;
   return NULL_TREE;
 }
 
+/* Record temporary equivalences generated by PHI nodes, and are valid when
+   E is taken.  VALUES are results of the interested expression, REV is the
+   result that need to be ruled out.  */
+
+static void
+record_equiv_from_prev_phi_1 (vn_pval *values, edge e, tree rev)
+{
+  basic_block bb = e->src;
+  /* Process predicated values, looking for a conflicting result, and
+     the location's single_pred dominates BB.  */
+  for (vn_pval *val = values; val; val = val->next)
+    {
+      if (!expressions_equal_p (val->result, rev))
+	continue;
+      /* Found a result to rule out, process each location.  */
+      for (unsigned i = 0; i < val->n; ++i)
+	{
+	  basic_block bb1
+	    = BASIC_BLOCK_FOR_FN (cfun, val->valid_dominated_by_p[i]);
+	  if (!single_pred_p (bb1))
+	    continue;
+	  basic_block p = single_pred (bb1);
+	  if (!dominated_by_p_w_unex (bb, p, false))
+	    continue;
+	  gcc_assert (EDGE_COUNT (p->succs) == 2);
+	  /* Iterate on possible phi_bbs (can be BB itself). Considering
+	     non-executable edges, there can be multiple phi_bbs.  */
+	  for (basic_block phi_bb : get_dominated_by (CDI_DOMINATORS, p))
+	    {
+	      if (!dominated_by_p_w_unex (bb, phi_bb, false))
+		continue;
+	      /* Process PHIs, rule out incoming edges that definitely come
+		 from p->bb1.  If there's a single PHI argument X left, record
+		 the equivalence of X and PHI result at edge e.  */
+	      for (gphi_iterator gsi = gsi_start_nonvirtual_phis (phi_bb);
+		   !gsi_end_p (gsi); gsi_next_nonvirtual_phi (&gsi))
+		{
+		  gphi *phi = gsi.phi ();
+		  tree equiv = NULL_TREE;
+		  for (unsigned j = 0; j < gimple_phi_num_args (phi); ++j)
+		    {
+		      edge in = gimple_phi_arg_edge (phi, j);
+		      if (in->src == bb1
+			  || dominated_by_p_w_unex (in->src, bb1, false))
+			/* Definitely comes from p->bb1.  */
+			continue;
+		      tree arg = vn_valueize (gimple_phi_arg_def (phi, j));
+		      if (equiv && equiv != arg)
+			{
+			  equiv = NULL_TREE;
+			  break;
+			}
+		      equiv = arg;
+		    }
+		  if (equiv)
+		    record_temporary_equivalence (equiv, PHI_RESULT (phi), e);
+		}
+	    }
+	}
+    }
+}
+
+/* Record temporary equivalences generated by PHI nodes, and are valid when
+   edge E is taken, so they can be useful under related branch condition (when
+   jump threading is not performed).
+
+   CODE, OPS and RESULT are the condition and result for E to be taken.  VNO
+   is the condition's slot in nary map.
+
+   The idea is to find a conflicting predicate at some location L, where L's
+   predecessor P dominates BB, so we know path P->L will not be taken if E is
+   taken.  If by ruling out P->L can generate some equivalences, record them at
+   E->dest.  */
+
+static void
+record_equiv_from_prev_phi (vn_nary_op_t vno, edge e, tree_code code, tree *ops,
+			    tree result)
+{
+  if (!can_track_predicate_on_edge (e))
+    return;
+  tree reverse
+    = result == boolean_true_node ? boolean_false_node : boolean_true_node;
+  if (vno && vno->predicated_values)
+    record_equiv_from_prev_phi_1 (vno->u.values, e, reverse);
+
+  /* For predicates like "a==b is false" or "a!=b is true", conflicting results
+     are equivalences.  */
+  if ((result == boolean_true_node
+       && (code == NE_EXPR || code == GT_EXPR || code == LT_EXPR))
+      || (result == boolean_false_node && code == EQ_EXPR))
+    {
+      for (int i = 0; i < 2; i++, std::swap (ops[0], ops[1]))
+	if (TREE_CODE (ops[0]) == SSA_NAME)
+	  {
+	    vn_ssa_aux_t info = VN_INFO (ops[0]);
+	    if (TREE_CODE (info->valnum) == SSA_NAME && info->valnum != ops[0])
+	      info = VN_INFO (info->valnum);
+	    if (info->equiv)
+	      record_equiv_from_prev_phi_1 (info->equiv->values, e, ops[1]);
+	  }
+    }
+}
+
 /* Insert the rhs of STMT into the current hash table with a value number of
    RESULT.  */
 
@@ -5201,7 +5636,24 @@ static bool
 visit_nary_op (tree lhs, gassign *stmt)
 {
   vn_nary_op_t vnresult;
-  tree result = vn_nary_op_lookup_stmt (stmt, &vnresult);
+  unsigned length = vn_nary_length_from_stmt (stmt);
+  vn_nary_op_t vno
+    = XALLOCAVAR (struct vn_nary_op_s, sizeof_vn_nary_op (length));
+  init_vn_nary_op_from_stmt (vno, stmt);
+  tree result = NULL_TREE;
+  /* Try to get a simplified result.  */
+  /* Do not simplify variable used in PHI at loop exit, or
+     simplify_peeled_chrec/constant_after_peeling may miss the loop.  */
+  gimple *use_stmt;
+  use_operand_p use_p;
+  if (!(single_imm_use (lhs, &use_p, &use_stmt)
+	&& gimple_code (use_stmt) == GIMPLE_PHI
+	&& single_succ_p (gimple_bb (use_stmt))
+	&& (single_succ_edge (gimple_bb (use_stmt))->flags & EDGE_DFS_BACK)))
+    result = fold_const_from_equiv_heads (vno->length, vno->opcode, vno->op,
+					  vno->type);
+  if (!result)
+    result = vn_nary_op_lookup_1 (vno, &vnresult);
   if (! result && vnresult)
     result = vn_nary_op_get_predicated_value (vnresult, gimple_bb (stmt));
   if (result)
@@ -7601,11 +8053,8 @@ insert_related_predicates_on_edge (enum tree_code code, tree *ops, edge pred_e)
 					   ops, boolean_false_node, 0, pred_e);
       break;
     case EQ_EXPR:
-      /* a == b -> ! a {<,>} b */
-      vn_nary_op_insert_pieces_predicated (2, LT_EXPR, boolean_type_node,
-					   ops, boolean_false_node, 0, pred_e);
-      vn_nary_op_insert_pieces_predicated (2, GT_EXPR, boolean_type_node,
-					   ops, boolean_false_node, 0, pred_e);
+      /* No need to insert derived predicates for '==', as they can be computed
+	 by equiv-heads & fold_const_from_equiv_heads.  */
       break;
     case LE_EXPR:
     case GE_EXPR:
@@ -7773,24 +8222,31 @@ process_bb (rpo_elim &avail, basic_block bb,
       switch (gimple_code (last))
 	{
 	case GIMPLE_SWITCH:
+	  /* TODO: utilize temporary equivalences.  */
 	  e = find_taken_edge (bb, vn_valueize (gimple_switch_index
 						(as_a <gswitch *> (last))));
 	  break;
 	case GIMPLE_COND:
 	  {
-	    tree lhs = vn_valueize (gimple_cond_lhs (last));
-	    tree rhs = vn_valueize (gimple_cond_rhs (last));
-	    tree val = gimple_simplify (gimple_cond_code (last),
-					boolean_type_node, lhs, rhs,
-					NULL, vn_valueize);
+	    tree lhs = get_equiv_head (gimple_cond_lhs (last), bb);
+	    tree rhs = get_equiv_head (gimple_cond_rhs (last), bb);
+	    tree ops[2];
+	    ops[0] = lhs;
+	    ops[1] = rhs;
+	    tree val = fold_const_from_equiv_heads (2, gimple_cond_code (last),
+						    ops, boolean_type_node);
+	    if (val && (dump_flags & TDF_DETAILS))
+	      {
+		fprintf (dump_file, "Got simplified result ");
+		print_generic_expr (dump_file, val, TDF_NONE);
+		fprintf (dump_file, " for ");
+		print_gimple_stmt (dump_file, last, TDF_SLIM);
+	      }
+	    vn_nary_op_t vnresult = NULL;
 	    /* If the condition didn't simplfy see if we have recorded
 	       an expression from sofar taken edges.  */
 	    if (! val || TREE_CODE (val) != INTEGER_CST)
 	      {
-		vn_nary_op_t vnresult;
-		tree ops[2];
-		ops[0] = lhs;
-		ops[1] = rhs;
 		val = vn_nary_op_lookup_pieces (2, gimple_cond_code (last),
 						boolean_type_node, ops,
 						&vnresult);
@@ -7821,15 +8277,14 @@ process_bb (rpo_elim &avail, basic_block bb,
 		enum tree_code code = gimple_cond_code (last);
 		enum tree_code icode
 		  = invert_tree_comparison (code, HONOR_NANS (lhs));
-		tree ops[2];
-		ops[0] = lhs;
-		ops[1] = rhs;
 		if (do_region
 		    && bitmap_bit_p (exit_bbs, true_e->dest->index))
 		  true_e = NULL;
 		if (do_region
 		    && bitmap_bit_p (exit_bbs, false_e->dest->index))
 		  false_e = NULL;
+		if (true_e || false_e)
+		  get_equiv_heads (2, ops, ops, bb);
 		if (true_e)
 		  vn_nary_op_insert_pieces_predicated
 		    (2, code, boolean_type_node, ops,
@@ -7858,6 +8313,14 @@ process_bb (rpo_elim &avail, basic_block bb,
 		    if (false_e)
 		      insert_related_predicates_on_edge (icode, ops, false_e);
 		  }
+		/* Try to record equivalences generated by previous PHI nodes
+		   on current true & false edges.  */
+		if (true_e)
+		  record_equiv_from_prev_phi (vnresult, true_e, code, ops,
+					      boolean_true_node);
+		if (false_e)
+		  record_equiv_from_prev_phi (vnresult, false_e, code, ops,
+					      boolean_false_node);
 	      }
 	    break;
 	  }
@@ -7980,6 +8443,8 @@ struct unwind_state
   vn_phi_t phi_top;
   vn_nary_op_t nary_top;
   vn_avail *avail_top;
+  nary_ref *nary_ref_top;
+  temp_equiv *temp_equiv_top;
 };
 
 /* Unwind the RPO VN state for iteration.  */
@@ -8029,6 +8494,27 @@ do_unwind (unwind_state *to, rpo_elim &avail)
       av->next = avail.m_avail_freelist;
       avail.m_avail_freelist = av;
     }
+
+  /* Drain nary_refs and temp_equiv to freelist, to reuse the memory.  */
+  for (; last_pushed_nary_ref && last_pushed_nary_ref->ref != to->nary_ref_top;)
+    {
+      vn_ssa_aux_t val = last_pushed_nary_ref;
+      nary_ref *ref = val->ref;
+      val->ref = ref->next;
+      last_pushed_nary_ref = ref->next_undo;
+      ref->next = nary_ref_freelist;
+      nary_ref_freelist = ref;
+      --val->num_nary_ref;
+    }
+  for (; last_pushed_equiv && last_pushed_equiv->equiv != to->temp_equiv_top;)
+    {
+      vn_ssa_aux_t val = last_pushed_equiv;
+      temp_equiv *eq = val->equiv;
+      val->equiv = eq->next;
+      last_pushed_equiv = eq->next_undo;
+      eq->next = temp_equiv_freelist;
+      temp_equiv_freelist = eq;
+    }
 }
 
 /* Do VN on a SEME region specified by ENTRY and EXIT_BBS in FN.
@@ -8143,6 +8629,10 @@ do_rpo_vn_1 (function *fn, edge entry, bitmap exit_bbs,
   last_inserted_phi = NULL;
   last_inserted_nary = NULL;
   last_pushed_avail = NULL;
+  last_pushed_nary_ref = NULL;
+  nary_ref_freelist = NULL;
+  last_pushed_equiv = NULL;
+  temp_equiv_freelist = NULL;
 
   vn_valueize = rpo_vn_valueize;
 
@@ -8237,6 +8727,10 @@ do_rpo_vn_1 (function *fn, edge entry, bitmap exit_bbs,
 	    rpo_state[idx].nary_top = last_inserted_nary;
 	    rpo_state[idx].avail_top
 	      = last_pushed_avail ? last_pushed_avail->avail : NULL;
+	    rpo_state[idx].nary_ref_top
+	      = last_pushed_nary_ref ? last_pushed_nary_ref->ref : NULL;
+	    rpo_state[idx].temp_equiv_top
+	      = last_pushed_equiv ? last_pushed_equiv->equiv : NULL;
 	  }
 
 	if (!(bb->flags & BB_EXECUTABLE))
diff --git a/gcc/tree-ssa-sccvn.h b/gcc/tree-ssa-sccvn.h
index abcf7e666c2..c96841ecd6e 100644
--- a/gcc/tree-ssa-sccvn.h
+++ b/gcc/tree-ssa-sccvn.h
@@ -217,6 +217,41 @@ struct vn_avail
   struct vn_ssa_aux *next_undo;
 };
 
+/* In vn_ssa_aux, hold a list of temporary equivalences of NAME.  Each value
+   represents a set of valid equivalences, and is called "equivalence head" of
+   NAME).
+
+   More general result (representing a larger set) should be closer to the
+   front.  */
+
+struct temp_equiv
+{
+  temp_equiv *next;
+  struct vn_ssa_aux *next_undo;
+  vn_pval *values;
+};
+
+/* In vn_ssa_aux, hold a list of back-references.  There're two types:
+
+   1) Back-references to the nary map entries (with NAME as operand).  So
+      when new equivalence is recorded to it, we can re-insert nary
+      expressions' results based on this.
+
+   2) Back-references to another vn_ssa_aux (who's name is X), that takes
+      NAME as equivalence-head.  So when NAME is assigned with new
+      equivalence-head Y, we can also update X's equivalence-head to Y.
+      In this way, the equivalence-sets are path-compressed.  */
+
+struct nary_ref
+{
+  nary_ref *next;
+  /* Back-reference to the nary map entry.  */
+  vn_nary_op_t vno;
+  /* Back-reference to another vn_ssa_aux.  */
+  struct vn_ssa_aux *vn;
+  struct vn_ssa_aux *next_undo;
+};
+
 typedef struct vn_ssa_aux
 {
   /* SSA name this vn_ssa_aux is associated with in the lattice.  */
@@ -230,12 +265,21 @@ typedef struct vn_ssa_aux
      for SSA names also serving as values (NAME == VALNUM).  */
   vn_avail *avail;
 
+  /* References to slots in the nary map, with NAME as operand.  */
+  nary_ref *ref;
+
+  /* Temporary equivalences of NAME.  */
+  temp_equiv *equiv;
+
   /* Unique identifier that all expressions with the same value have. */
   unsigned int value_id;
 
   /* Whether the SSA_NAME has been processed at least once.  */
   unsigned visited : 1;
 
+  /* nary_ref count.  */
+  unsigned short num_nary_ref;
+
   /* Whether the SSA_NAME has no defining statement and thus an
      insertion of such with EXPR as definition is required before
      a use can be created of it.  */

PING: [PATCH v6] tree-optimization/101186 - extend FRE with "equivalence map" for condition prediction

[Di Zhao OS]

Hi,

I saw that Stage 1 of GCC 13 development is just ended. So is this
considered? Or should I bring this up when general development is
reopened?


Thanks,
Di Zhao


> -----Original Message-----
> From: Di Zhao OS
> Sent: Tuesday, October 25, 2022 8:18 AM
> To: gcc-patches@gcc.gnu.org
> Cc: Richard Biener <richard.guenther@gmail.com>
> Subject: [PATCH v6] tree-optimization/101186 - extend FRE with "equivalence
> map" for condition prediction
> 
> Sorry for the late update. I've been on a vacation and then I
> spent some time updating and verifying the patch.
> 
> Attached is a new version of the patch. There are some changes:
> 
> 1. Store equivalences in a vn_pval chain in vn_ssa_aux, rather than
>    in the expression hash table. (Following Richard's suggestion.)
> 2. Extracted insert_single_predicated_value function.
> 3. Simplify record_equiv_from_prev_phi a bit.
> 4. Changed some of the functions' names and tried to improve the
>    comments a little.
> 
> Current status of the new testcases in the patch:
> 
> ssa-fre-200.c	Can also be optimized by evrp
> ssa-fre-201.c	Not optimized in trunk.
> ssa-fre-202.c	foo() can be removed by evrp; while x + b is not
> 		folded.
> ssa-pre-34.c	Not optimized in trunk.
> 
> Initially, this patch is motivated to remove the unreachable codes
> in case like ssa-pre-34.c, in which we need to use equivalence
> relation produced from a preceding condition for another condition.
> VRP didn't optimize that because it needs jump threading to make
> the relation valid at the second condition.
> 
> After browsing the mechanisms of VRP and FRE, it seems to me there
> are two options: 1) Teach VRP to identify related but not threaded
> conditions. That might require introducing value-numbering into VRP
> to detect common expressions, and I think is too much for this.
> 2) Introduce temporary equivalence in sccvn, which I thought would
> change less on current code. (And along the reviews and updating
> patch I see how ad-hoc it was.)
> 
> I saw from the talk about VN there's plan to replace predicated
> values by ranger. So how does it goes? Is there something I can help
> with? (For the case ssa-pre-34.c, I think maybe it still needs the
> predicated-value support, to lookup related conditional expressions.)
> 
> Below are about questions in the last review:
> 
> > >  /* Valid hashtables storing information we have proven to be
> > >     correct.  */
> > > @@ -490,9 +492,9 @@ VN_INFO (tree name)
> > >  	    nary->predicated_values = 0;
> > >  	    nary->u.result = boolean_true_node;
> > >  	    vn_nary_op_insert_into (nary, valid_info->nary);
> > > -	    gcc_assert (nary->unwind_to == NULL);
> >
> > why's that?  doesn't this mean unwinding will be broken?
> 
> Previously, predicate "argument_x == NULL" or "argument_x != NULL"
> is always new here (because argument_x's VN is just inserted.)
> But with the patch, there can be slot for "argument_x == NULL"
> or "argument_x != NULL" already. It won't break unwinding as the
> new value is not linked to the unwind-chain.
> 
> >
> > >  	    /* Also do not link it into the undo chain.  */
> > >  	    last_inserted_nary = nary->next;
> > > +	    /* There could be a predicate already.  */
> > >  	    nary->next = (vn_nary_op_t)(void *)-1;
> > >  	    nary = alloc_vn_nary_op_noinit (2, &vn_tables_insert_obstack);
> > >  	    init_vn_nary_op_from_pieces (nary, 2, EQ_EXPR,
> 
> > >  /* Compute and return the hash value for nary operation VBO1.  */
> > >
> > >  hashval_t
> > > @@ -4226,6 +4342,9 @@ init_vn_nary_op_from_stmt (vn_nary_op_t vno, gassign
> *stmt)
> > >        for (i = 0; i < vno->length; ++i)
> > >  	vno->op[i] = gimple_op (stmt, i + 1);
> > >      }
> > > +  /* Insert and lookup N-ary results by the operands' equivalence heads.
> */
> > > +  if (gimple_bb (stmt))
> > > +    lookup_equiv_heads (vno->length, vno->op, vno->op, gimple_bb (stmt));
> >
> > That seems like the wrong place, the function didn't even valueize before.
> 
> To utilize temp-equivalences and get more simplified result, n-ary
> expressions should be always inserted and lookup by the operands'
> equivalence heads. So practically all the places
> init_vn_nary_op_from_stmt is used, lookup_equiv_heads (changed to
> get_equiv_heads) should be called. As I haven't found better place
> to put that, I just left it here in the patch..
> 
> > >  visit_nary_op (tree lhs, gassign *stmt)
> > >  {
> > >    vn_nary_op_t vnresult;
> > > -  tree result = vn_nary_op_lookup_stmt (stmt, &vnresult);
> > > -  if (! result && vnresult)
> > > +  unsigned length = vn_nary_length_from_stmt (stmt);
> > > +  vn_nary_op_t vno
> > > +    = XALLOCAVAR (struct vn_nary_op_s, sizeof_vn_nary_op (length));
> > > +  init_vn_nary_op_from_stmt (vno, stmt);
> > > +  tree result = NULL_TREE;
> > > +  /* Try to get a simplified result.  */
> > > +  /* Do not simplify variable used in PHI at loop exit, or
> > > +     simplify_peeled_chrec/constant_after_peeling may miss the loop.  */
> > > +  gimple *use_stmt;
> > > +  use_operand_p use_p;
> > > +  if (!(single_imm_use (lhs, &use_p, &use_stmt)
> > > +	&& gimple_code (use_stmt) == GIMPLE_PHI
> > > +	&& single_succ_p (gimple_bb (use_stmt))
> > > +	&& (single_succ_edge (gimple_bb (use_stmt))->flags & EDGE_DFS_BACK)))
> > > +    result = fold_const_from_equiv_heads (vno->length, vno->opcode, vno-
> >op,
> > > +					  vno->type);
> >
> > copy propagating conditional equivalences has proved problematic, why
> > do this at all when there's no actual simplification?  It's a bit odd that
> > we need a special fold_const_from_equiv_heads here, why is general
> > valueization not handling equivalences?  Are they supposed to be only
> > used for simplifying conditionals?
> 
> With temporary equivalences introduced, expressions like "a - equiv(a)"
> and "a == equiv (a)" can be folded, and no need to store predicates
> like "a == b is true". The function fold_const_from_equiv_heads is
> intended to limit the usage of gimple_simplify, to when a constant can
> be folded using equivalences. The code seems too complex but I haven't
> figured out how to improve it yet. (I'm not very acquainted on how to
> use the simplifying utility properly, I hope I can get some advices
> here.) Also, could I have more details about "copy propagating
> conditional equivalences has proved problematic" ?
> 
> Thank you very much,
> Di Zhao
> 
> ----
> 
> Extend FRE with temporary equivalences.
> 
> 2022-10-24  Di Zhao  <dizhao@os.amperecomputing.com>
> 
> gcc/ChangeLog:
> 
>         * tree-ssa-sccvn.cc (VN_INFO): remove assertions (there could be
>         a predicate already).
>         (dominated_by_p_w_unex): Moved upward.
>         (is_pval_valid_at_bb): Check if vn_pval is valid at BB.
>         (get_equiv_head): Returns the "equivalence head" of given node.
>         (get_equiv_heads): Get the "equivalence head"s of given nodes.
>         (init_vn_nary_op_from_stmt): Insert and lookup nary expressions
>         by "equivalence head"s.
>         (insert_single_predicated_value): Extracted utility.
>         (vn_nary_op_insert_into): Use the extracted utility
>         insert_single_predicated_value.
>         (fold_const_from_equiv_heads): Fold N-ary expression to constant
>         by equiv-heads.
>         (push_new_nary_ref): Insert a back-reference to vn_nary_op_t.
>         (alloc_single_predicated_value): Extracted utility.
>         (push_single_equiv): Push a new value to the equivalence list.
>         (record_temporary_equivalence): Record temporary equivalence.
>         (vn_nary_op_insert_pieces_predicated): Record equivalences
>         instead of some predicates; insert back-refs.
>         (record_equiv_from_prev_phi_1): Record temporary equivalences
>         generated by PHI nodes.
>         (record_equiv_from_prev_phi): Given a taken edge of a conditional
>         branch, record equivalences generated by PHI nodes.
>         (visit_nary_op): Lookup previous results of N-ary operations by
>         equivalences.
>         (insert_related_predicates_on_edge): Some predicates can be
>         computed from equivalences, no need to insert them.
>         (process_bb): Add lookup predicated values by equivalences.
>         (struct unwind_state): Unwind state of back-refs and temporary
>         equivalences.
>         (do_unwind): Unwind the back-refs and temporary equivalences.
>         (do_rpo_vn_1): Update unwind state of back-reference and
>         temporary equivalences.
>         * tree-ssa-sccvn.h (struct temp_equiv): In vn_ssa_aux, hold a
>         list of temporary equivalences.
>         (struct nary_ref): In vn_ssa_aux, hold a lists of references to
>         the nary map entries.
> 
> gcc/testsuite/ChangeLog:
> 
>         * g++.dg/pr83541.C: Disable fre.
>         * gcc.dg/tree-ssa/pr68619-2.c: Disable fre.
>         * gcc.dg/tree-ssa/pr71947-1.c: Disable fre.
>         * gcc.dg/tree-ssa/pr71947-2.c: Disable fre.
>         * gcc.dg/tree-ssa/pr71947-3.c: Disable fre.
>         * gcc.dg/tree-ssa/pr71947-5.c: Disable fre.
>         * gcc.dg/tree-ssa/pr71947-7.c: Disable fre.
>         * gcc.dg/tree-ssa/pr71947-8.c: Disable fre.
>         * gcc.dg/tree-ssa/pr71947-9.c: Disable fre.
>         * gcc.dg/tree-ssa/vrp03.c: Disable fre.
>         * gcc.dg/tree-ssa/ssa-fre-200.c: New test.
>         * gcc.dg/tree-ssa/ssa-fre-201.c: New test.
>         * gcc.dg/tree-ssa/ssa-fre-202.c: New test.
>         * gcc.dg/tree-ssa/ssa-pre-34.c: New test.

Re: PING: [PATCH v6] tree-optimization/101186 - extend FRE with "equivalence map" for condition prediction

[Jeff Law]

On 11/15/22 03:44, Di Zhao OS via Gcc-patches wrote:
> Hi,
>
> I saw that Stage 1 of GCC 13 development is just ended. So is this
> considered? Or should I bring this up when general development is
> reopened?

Yes, it can still be considered.  The guideline is the patch must be 
posted before stage1 closes, which this patch obviously was. Richi as 
both the release manager and the expert on this part of GCC is by far 
the best person to judge the technical aspect of the patch and the 
cost/benefit of including it as we work our way through stage3 in our 
development cycle.


jeff