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

[Di Zhao OS <dizhao@os.amperecomputing.com>]

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

Sorry about updating on this after so long. It took me much time to work out a
new plan and pass the tests.

The new idea is to use one variable to represent a set of equal variables at
some basic-block. This variable is called a "equivalence head" or "equiv-head"
in the code. (There's no-longer a "equivalence map".)

- Initially an SSA_NAME's "equivalence head" is its value number. Temporary
  equivalence heads are recorded as unary NOP_EXPR results in the vn_nary_op_t
  map. Besides, when inserting into vn_nary_op_t map, make the new result at
  front of the vn_pval list, so that when searching for a variable's
  equivalence head, the first result represents the largest equivalence set at
  current location.
- In vn_ssa_aux_t, maintain a list of references to valid_info->nary entry.
  For recorded equivalences, the reference is result->entry; for normal N-ary
  operations, the reference is operand->entry.
- When recording equivalences, if one side A is constant or has more refs, make
  it the new equivalence head of the other side B. Traverse B's ref-list, if a
  variable C's previous equiv-head is B, update to A. And re-insert B's n-ary
  operations by replacing B with A.
- When inserting and looking for the results of n-ary operations, insert and
  lookup by the operands' equiv-heads.

So except for the refs in vn_ssa_aux_t, this scheme uses the original
infrastructure to its best. Quadric search time is avoided at the cost of some
re-insertions. Test results on SPEC2017 intrate (counts and percentages):

                |more bb |more bb |more stmt|more stmt|more       |more
                |removed |removed |removed  |removed  |nv_nary_ops|nv_nary_ops
                |at fre1 |at fre1 |at fre1  |at fre1  |inserted   |inserted
------------------------------------------------------------------------------
 500.perlbench_r| 64     | 1.98%  | 103     | 0.19%   | 11260     | 12.16%
 502.gcc_r      | 671    | 4.80%  | 317     | 0.23%   | 13964     | 6.09%
 505.mcf_r      | 5      | 35.71% | 9       | 1.40%   | 32        | 2.52%
 520.omnetpp    | 132    | 5.45%  | 39      | 0.11%   | 1895      | 3.91%
 523.xalancbmk_r| 238    | 3.26%  | 313     | 0.36%   | 1417      | 1.27%
 525.x264_r     | 4      | 1.36%  | 27      | 0.11%   | 1752      | 6.78%
 531.deepsjeng_r| 1      | 3.45%  | 2       | 0.14%   | 228       | 8.67%
 541.leela_r    | 2      | 0.63%  | 0       | 0.00%   | 92        | 1.14%
 548.exchange2_r| 0      | 0.00%  | 3       | 0.04%   | 49        | 1.03%
 557.xz_r       | 0      | 0.00%  | 3       | 0.07%   | 272       | 7.55%

There're more basic_blocks and statements removed compared with last
implementation, the reasons are:
1) "CONST op CONST" simplification is included. It is missed in previous patch.
2) By inserting RHS of statements on equiv-heads, more N-ary operations can be
   simplified. One example is in 'ssa-fre-97.c' in the patch file.

While jump-threading & vrp also utilize temporary equivalences (so some of the
newly removed blocks and statements can also be covered by them), I think this
patch is a supplement, in cases when jump threading cannot take place (the
original example), or value number info needs to be involved (the
'ssa-fre-97.c' example).

Fixed the former issue with non-iterate mode.

About recording the temporary equivalences generated by PHIs (i.e. the
'record_equiv_from_previous_cond' stuff), I have to admit it looks strange and
the code size is large, but I haven't find a better way yet. Consider a piece
of CFG like the one below, if we want to record x==x2 on the true edge when
processing bb1, the location (following current practice) will be bb2. But that
is not useful at bb5 or bb6, because bb2 doesn't dominate them. And I can't
find a place to record x==x1 when processing bb1.
If we can record things on edges rather than blocks, say x==x1 on 1->3 and
x==x2 on 1->2, then perhaps with an extra check for "a!=0", x2 can be a valid
equiv-head for x since bb5. But I think it lacks efficiency and is not
persuasive. It is more efficient to find a valid previous predicate when
processing bb4, because the vn_nary_op_t will be fetched anyway.
        --------------
        | if (a != 0) | bb1
        --------------
        f |      \ t
          |    -------
          |    | bb2 | 
          |    -------
          |      /
    -------------------------
    | x = PHI<x1(1), x2(2)> | bb3
    -------------------------
               |
              ....
               |
       --------------
       | if (a != 0) | bb4
       --------------
           |f     \t
    -------------  -------
bb7 | where     |  | bb5 |  ==> where "x==x2" is recorded now
    | "x==x1" is|  -------
    | recorded  |    \
    | now       |    ...
    -------------     |
                   -------
                   | bb6 |  ==> where "x==x2" needs to be used
                   -------
Although I think I can remove the 'dominator_to_phi_map' and generalize this a
little, but the major logic will be similar. So I left this unchanged for now,
and would like to hear your suggestions on the new scheme overall.

Thanks,
Di Zhao

--------
Extend FRE with temporary equivalences.

2021-09-16  Di Zhao  <dizhao@os.amperecomputing.com>

gcc/ChangeLog:
        PR tree-optimization/101186
        * tree-ssa-sccvn.c (dominated_by_p_w_unex): Moved upward, no change.
        (vn_nary_op_get_predicated_value): Moved upward, no change.
        (is_vn_valid_at_bb): Check if vn_pval is valid at BB.
        (lookup_equiv_head): Lookup the "equivalence head" of given node.
        (lookup_equiv_heads): Lookup the "equivalence head"s of given nodes.
        (vn_tracking_edge): Extracted utility function.
        (init_vn_nary_op_from_stmt): Insert and lookup by "equivalence head"s.
        (vn_nary_op_insert_into): Insert new value at the front.
        (vn_nary_op_insert_pieces_predicated_1): Insert as predicated values
        from pieces.
        (simplify_nary_op): Try to simplify N-ary expressions.
        (push_new_nary_ref): Insert a back-reference to vn_nary_op_t.
        (vn_nary_op_insert_pieces_predicated): Insert by "equivalence head"s.
        (is_relaxed_cond_code): Whether operation code is a relaxed condition
        code derived from original code.
        (branch_may_come_from_another): Whether there's a path from the one
        true or false destination to another.
        (val_equiv_insert): Record temporary equivalence.
        (record_equiv_from_previous_cond): Record equivalences generated by
        previous conditions on current BB's true and false edges.
        (find_predicated_value_by_equivs): Find predicated value by the
        operands' equivalences.
        (record_dom_to_phi_bb): Record mappings from immediate dominator to
        basic_block with PHIs.
        (vn_phi_insert): Record mapping from the immediate dominator to a PHI
        node.
        (visit_nary_op): Add lookup previous results of N-ary operations by
        equivalences.
        (free_rpo_vn): Free dominator_to_phi_map.
        (process_bb): Add lookup predicated values by equivalences.
        (struct unwind_state): Unwind state of back-refs to vn_nary_op_t.
        (do_unwind): Unwind the back-refs to vn_nary_op_t.
        (do_rpo_vn): Update back-reference unwind state.
        * tree-ssa-sccvn.h (struct nary_ref): hold a lists of references to the
        nary map entries.

gcc/testsuite/ChangeLog:

        * 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-95.c: New test.
        * gcc.dg/tree-ssa/ssa-fre-96.c: New test.
        * gcc.dg/tree-ssa/ssa-fre-97.c: New test.


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

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-95.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-95.c
new file mode 100644
index 00000000000..c9dee01cec0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-95.c
@@ -0,0 +1,83 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-fre1" } */
+
+extern void bar(void);
+extern void bag(void);
+extern void boo(void);
+extern void bas(void);
+extern void foo(void);
+
+void f (unsigned int a, unsigned int b)
+{
+  if (a == b)
+    {
+      for (unsigned i = 0; i < a; i++)
+	{
+	  bar ();
+	  if (i >= b)
+	    /* Unreachable.  */
+	    foo ();
+	}
+    }
+}
+
+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 ();
+	    }
+	}
+    }
+}
+
+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.  */
+	    foo ();
+	}
+      else
+	bas ();
+      b++;
+    }
+}
+
+void k (int a, int b, int x, int y)
+{
+  int c = y;
+  if (a > 0)
+    c = x;
+  while (b < 1000)
+    {
+      if (a != 0) // "a != 0" can be derived from "a > 0" 
+	{
+	  if (c > x)
+	    /* Unreachable.  */
+	    foo ();
+	}
+      else
+	bag ();
+      b++;
+    }
+}
+
+/* { dg-final { scan-tree-dump-not "foo" "fre1" } } */
+/* { dg-final { scan-tree-dump "bag" "fre1" } } */
+/* { dg-final { scan-tree-dump "bar" "fre1" } } */
+/* { dg-final { scan-tree-dump "boo" "fre1" } } */
+/* { dg-final { scan-tree-dump "bas" "fre1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-96.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-96.c
new file mode 100644
index 00000000000..ce11c7f2096
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-96.c
@@ -0,0 +1,70 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-fre1" } */
+
+extern void bar(void);
+extern void bag(void);
+extern void bas(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 ();
+	}
+    }
+}
+
+void g (unsigned int a, unsigned int b, unsigned int d)
+{
+  unsigned int c = 100;
+  if (a > 0)
+    c = b;
+  else
+    c = d;
+  for (unsigned i = 0; i < c; i++)
+    {
+      if (a >= 0)
+	{
+	  if (i >= b)
+	    /* Should not be eliminated. ("a >= 0" cannot derive "a > 0".)  */
+	    bas ();
+	}
+      else
+	{
+	  if (i >= d)
+	    /* Should be eliminated, as "a < 0" can derive "a <= 0".  */
+	    foo ();
+	}
+      i++;
+    }
+}
+
+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 "bas" "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-97.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-97.c
new file mode 100644
index 00000000000..d560ce090a5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-97.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;
+
+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_* + x_" "fre1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp03.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp03.c
index 1d7ea4e8ffb..87df31d4f0d 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 -fdisable-tree-ethread -fdisable-tree-thread1" } */
+/* { dg-options "-O2 -fdisable-tree-evrp -fno-tree-fre -fdump-tree-vrp1 -fdisable-tree-ethread -fdisable-tree-thread1" } */
 
 struct A
 {
diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
index bfa516b6cf9..6c59c135e01 100644
--- a/gcc/tree-ssa-sccvn.c
+++ b/gcc/tree-ssa-sccvn.c
@@ -194,6 +194,12 @@ vn_phi_hasher::equal (const vn_phi_s *vp1, const vn_phi_s *vp2)
 typedef hash_table<vn_phi_hasher> vn_phi_table_type;
 typedef vn_phi_table_type::iterator vn_phi_iterator_type;
 
+typedef hash_map<basic_block, hash_set<basic_block> > bb_map_t;
+
+/* Maps a basic-block P to a list of basic-blocks with PHIs and are immediately
+ * dominated by P.  This is to help finding temporary equivalences introduced
+ * by PHIs.  */
+static bb_map_t *dominator_to_phi_map = NULL;
 
 /* Compare two reference operands P1 and P2 for equality.  Return true if
    they are equal, and false otherwise.  */
@@ -348,6 +354,8 @@ 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 nary_ref* nary_ref_freelist;
 
 /* Valid hashtables storing information we have proven to be
    correct.  */
@@ -3823,6 +3831,114 @@ vn_reference_insert_pieces (tree vuse, alias_set_type set,
   return vr1;
 }
 
+static bool
+dominated_by_p_w_unex (basic_block bb1, basic_block bb2, bool);
+
+static tree
+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;
+      }
+  return NULL_TREE;
+}
+
+/* Whether a predicated value VAL is valid at BB.  */
+
+static inline bool
+is_vn_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]);
+      if (dominated_by_p_w_unex (bb, val_bb, false))
+	return true;
+    }
+  return false;
+}
+
+/* Lookup the "equivalence head" of given node NAME, which represents a set of
+   equivalences of NAME at basic-block BB.  */
+
+static inline tree
+lookup_equiv_head (tree name, basic_block bb)
+{
+  if (TREE_CODE (name) != SSA_NAME)
+    return name;
+  tree result = VN_INFO (name)->valnum;
+  if (result == VN_TOP)
+    /* VN_TOP is not allowed, otherwise it will be too optimistic for
+     * non-iterating mode.  */
+    return name;
+  vn_nary_op_t vnresult;
+  /* As we insert new value at front in vn_nary_op_insert_into, we don't need
+   * search iteratively for the most general equiv-head.  */
+  vn_nary_op_lookup_pieces (1, NOP_EXPR, TREE_TYPE (result), &result,
+			    &vnresult);
+  if (vnresult)
+    {
+      tree eq = vn_nary_op_get_predicated_value (vnresult, bb);
+      if (eq)
+	return eq;
+    }
+  return result;
+}
+
+/* Lookup the "equivalence head"s of OPS at BB, and store them in TO.  N is the
+ * size of OPS.  */
+
+static void
+lookup_equiv_heads (unsigned n, tree *ops, tree *to, basic_block bb)
+{
+  for (unsigned i = 0; i < n; i++)
+    {
+      tree equiv_head = lookup_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, "\n");
+	}
+      to[i] = equiv_head;
+    }
+}
+
+/* Returns whether edge PRED_E is currently being tracked.  */
+
+static inline bool
+vn_tracking_edge (edge pred_e)
+{
+  if (!single_pred_p (pred_e->dest))
+    {
+      /* Never record for backedges.  */
+      if (pred_e->flags & EDGE_DFS_BACK)
+	return false;
+      edge_iterator ei;
+      edge e;
+      int cnt = 0;
+      /* Ignore backedges.  */
+      FOR_EACH_EDGE (e, ei, pred_e->dest->preds)
+	if (!dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
+	  cnt++;
+      if (cnt != 1)
+	return false;
+    }
+  return true;
+}
+
 /* Compute and return the hash value for nary operation VBO1.  */
 
 static hashval_t
@@ -3960,6 +4076,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));
 }
 
 /* Compute the hashcode for VNO and look for it in the hash table;
@@ -4145,7 +4264,12 @@ vn_nary_op_insert_into (vn_nary_op_t vno, vn_nary_op_table_type *table,
 	      next = &(*next)->next;
 	    }
 	  if (!found)
-	    *next = nval;
+	    {
+	      /* Insert new value at the front, so that lookup_equiv_head can
+	       * find the latest result.  */
+	      nval->next = vno->u.values;
+	      vno->u.values = nval;
+	    }
 
 	  *slot = vno;
 	  vno->next = last_inserted_nary;
@@ -4190,6 +4314,75 @@ vn_nary_op_insert_pieces (unsigned int length, enum tree_code code,
   return vn_nary_op_insert_into (vno1, valid_info->nary, true);
 }
 
+/* Similar with vn_nary_op_insert_pieces, but insert as predicated values.  */
+
+static vn_nary_op_t
+vn_nary_op_insert_pieces_predicated_1 (unsigned int length, enum tree_code code,
+				       tree type, tree *ops, tree result,
+				       unsigned int value_id, basic_block bb)
+{
+  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] = bb->index;
+  return vn_nary_op_insert_into (vno1, valid_info->nary, true);
+}
+
+/* Try to simplify N-ary expressions, return NULL_TREE if not folded.  */
+
+static tree
+simplify_nary_op (unsigned length, tree_code opcode, tree *op, tree type)
+{
+  switch (length)
+    {
+    case 1:
+      if (CONSTANT_CLASS_P (op[0]))
+	return 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])
+	return 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]))
+	return gimple_simplify (opcode, type, op[0], op[1], op[2], NULL,
+				no_follow_ssa_edges);
+      break;
+    default:
+      break;
+    }
+  return NULL_TREE;
+}
+
+/* Insert a back-reference to vn_nary_op_t in vn_ssa_aux.  */
+
+static inline void
+push_new_nary_ref (vn_nary_op_t slot, vn_ssa_aux_t info)
+{
+  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;
+  ref->slot = slot;
+  last_pushed_nary_ref = info;
+  info->ref = ref;
+  ++info->num_nary_ref;
+}
+
 static vn_nary_op_t
 vn_nary_op_insert_pieces_predicated (unsigned int length, enum tree_code code,
 				     tree type, tree *ops,
@@ -4197,21 +4390,8 @@ vn_nary_op_insert_pieces_predicated (unsigned int length, enum tree_code code,
 				     edge pred_e)
 {
   /* ???  Currently tracking BBs.  */
-  if (! single_pred_p (pred_e->dest))
-    {
-      /* Never record for backedges.  */
-      if (pred_e->flags & EDGE_DFS_BACK)
-	return NULL;
-      edge_iterator ei;
-      edge e;
-      int cnt = 0;
-      /* Ignore backedges.  */
-      FOR_EACH_EDGE (e, ei, pred_e->dest->preds)
-	if (! dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
-	  cnt++;
-      if (cnt != 1)
-	return NULL;
-    }
+  if (!vn_tracking_edge (pred_e))
+    return NULL;
   if (dump_file && (dump_flags & TDF_DETAILS)
       /* ???  Fix dumping, but currently we only get comparisons.  */
       && TREE_CODE_CLASS (code) == tcc_comparison)
@@ -4224,36 +4404,345 @@ vn_nary_op_insert_pieces_predicated (unsigned int length, enum tree_code code,
       fprintf (dump_file, " == %s\n",
 	       integer_zerop (result) ? "false" : "true");
     }
-  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, true);
+  /* Insert by operands' equiv-heads.  */
+  tree new_ops[3];
+  lookup_equiv_heads (length, ops, new_ops, pred_e->dest);
+  /* Skip if the result is known.  */
+  tree simplified = simplify_nary_op (length, code, new_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 val
+    = vn_nary_op_insert_pieces_predicated_1 (length, code, type, new_ops,
+					     result, value_id, pred_e->dest);
+  /* Insert back-refs (operand->slot) to vn_ssa_aux structure.  */
+  for (unsigned i = 0; i < length; i++)
+    {
+      if (TREE_CODE (new_ops[i]) == SSA_NAME)
+	{
+	  vn_ssa_aux_t info = VN_INFO (new_ops[i]);
+	  if (info->valnum == new_ops[i])
+	    push_new_nary_ref (val, info);
+	}
+    }
+  return val;
 }
 
+/* Returns whether DERIVED_CODE is a relaxed condition code derived from
+ * ORIG_CODE.  For example: "a>=b" is relaxed from "a>b", so
+ * is_relaxed_cond_code (>, >=) is true; "a!=b" is reversion of "a==b",
+ * is_relaxed_cond_code (==, !=) is false.  */
+
 static bool
-dominated_by_p_w_unex (basic_block bb1, basic_block bb2, bool);
+is_relaxed_cond_code (tree_code orig_code, tree_code derived_code)
+{
+  if (orig_code == derived_code
+      || swap_tree_comparison (orig_code) == derived_code)
+    return false;
+  if (commutative_tree_code (orig_code) && commutative_tree_code (derived_code))
+    /* NE_EXPR and EQ_EXPR.  */
+    return false;
+  return true;
+}
 
-static tree
-vn_nary_op_get_predicated_value (vn_nary_op_t vno, basic_block bb)
+/* Given that BB is basic block P's true or false destination, returns whether
+ * there's a path from the other true or false destination to it.  */
+
+static inline bool
+branch_may_come_from_another (basic_block p, basic_block bb)
 {
-  if (! vno->predicated_values)
-    return vno->u.result;
+  if (EDGE_COUNT (bb->preds) == 1)
+    return false;
+  edge e;
+  edge_iterator ei;
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    {
+      /* Checking that the other true or false destination dominates e->src
+       * isn't enough.  See PR79194.  */
+      if (e->src != p
+	  && !((e->flags & EDGE_DFS_BACK)
+	       && dominated_by_p (CDI_DOMINATORS, e->src, bb)))
+	return true;
+    }
+  return false;
+}
+
+/* Record the equivalence of LHS and RHS at basic_block BB.  */
+
+static vn_nary_op_t
+val_equiv_insert (tree op1, tree op2, edge e)
+{
+  /* Lookup current LHS and RHS's equivalence heads.  Set RHS's equiv-head to
+   * be new equiv-head for LHS.  */
+  basic_block bb = e->dest;
+  tree lhs = lookup_equiv_head (op1, bb);
+  tree rhs = lookup_equiv_head (op2, bb);
+  if (lhs == rhs)
+    return NULL;
+  if (is_gimple_min_invariant (lhs))
+    std::swap (lhs, rhs);
+  if (is_gimple_min_invariant (lhs) || TREE_CODE (lhs) != SSA_NAME)
+    /* Possible if invoked from record_equiv_from_previous_cond.  */
+    return NULL;
+
+  /* Make the hand-side with more recorded n-ary expressions new
+   * equivalence-head, to make fewer re-insertions.  */
+  if (TREE_CODE (rhs) == SSA_NAME
+      && VN_INFO (rhs)->num_nary_ref < VN_INFO (lhs)->num_nary_ref)
+    std::swap (lhs, rhs);
+
+  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);
+    }
+  /* Record equivalence as unary NOP_EXPR.  */
+  vn_nary_op_t val
+    = vn_nary_op_insert_pieces_predicated_1 (1, NOP_EXPR, TREE_TYPE (lhs),
+					     &lhs, rhs, 0, bb);
+  /* 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 (val, VN_INFO (rhs));
+
+  /* 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 slot;
+  vn_ssa_aux_t old_info = VN_INFO (lhs);
+  tree old_head = old_info->valnum;
+  nary_ref *ref = old_info->ref;
+  for (; ref; ref = ref->next)
+    {
+      slot = ref->slot;
+      if (!slot->predicated_values)
+	continue;
+      /* Update recorded equivalences with new equiv-head.  */
+      if (slot->opcode == NOP_EXPR && slot->length == 1)
+	{
+	  if (slot->op[0] == rhs)
+	    continue;
+	  for (vn_pval *pval = slot->u.values; pval; pval = pval->next)
+	    {
+	      if (pval->result == old_head && is_vn_valid_at_bb (pval, bb))
+		{
+		  if (dump_file && (dump_flags & TDF_DETAILS))
+		    {
+		      fprintf (dump_file, "Updating equiv-head of ");
+		      print_generic_expr (dump_file, slot->op[0], TDF_SLIM);
+		      fprintf (dump_file, " to ");
+		      print_generic_expr (dump_file, rhs, TDF_SLIM);
+		      fprintf (dump_file, " at BB%d\n", bb->index);
+		    }
+		  vn_nary_op_t new_val = vn_nary_op_insert_pieces_predicated_1 (
+		    1, NOP_EXPR, slot->type, slot->op, rhs, 0, bb);
+		  /* Push back-ref (result->slot) for new equivalence.  */
+		  if (TREE_CODE (rhs) == SSA_NAME)
+		    push_new_nary_ref (new_val, VN_INFO (rhs));
+		}
+	    }
+	}
+      else
+	/* Predicated values are collected, to be re-inserted later.  */
+	for (vn_pval *pval = slot->u.values; pval; pval = pval->next)
+	  {
+	    if (!is_vn_valid_at_bb (pval, bb))
+	      continue;
+	    predicates.safe_push (slot);
+	    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 ());
+  FOR_EACH_VEC_ELT (predicates, i, slot)
+    {
+      /* vn_nary_op_insert_pieces_predicated will do insertion with new
+       * equiv-head as operand, since it's already recorded.  */
+      vn_nary_op_insert_pieces_predicated (slot->length, slot->opcode,
+					   slot->type, slot->op, results[i],
+					   slot->value_id, e);
+    }
+  return val;
+}
+
+/* Given a slot VNO that holds the same conditional expression with that in the
+   branching statement of BB, record valid equivalence relation on BB's true and
+   false edges.  For now we record equivalences of PHI results and arguments
+   that depend on the predicate of VNO.  */
+
+static void
+record_equiv_from_previous_cond (vn_nary_op_t vno, edge true_e, edge false_e,
+				 basic_block bb)
+{
+  if (!vno->predicated_values)
+    return;
+  if (true_e && !vn_tracking_edge (true_e))
+    true_e = NULL;
+  if (false_e && !vn_tracking_edge (false_e))
+    false_e = NULL;
+  if (!true_e && !false_e)
+    return;
+
+  /* Process all results in VNO, where basic-block containing the original
+     condition dominates BB.  */
   for (vn_pval *val = vno->u.values; val; val = val->next)
+    /* Process each predicated value.  */
     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;
-  return NULL_TREE;
+      {
+	basic_block bb1
+	  = BASIC_BLOCK_FOR_FN (cfun, val->valid_dominated_by_p[i]);
+
+	/* Original condition is in bb1's single_pred.  */
+	if (!single_pred_p (bb1))
+	  continue;
+	basic_block p = single_pred (bb1);
+	if (!dominated_by_p_w_unex (bb, p, false))
+	  continue;
+
+	gimple *pred_last = last_stmt (p);
+	if (!pred_last || gimple_code (pred_last) != GIMPLE_COND)
+	  continue;
+	/* If the predicate is re-inserted when updating equiv-heads, then it
+	 * has nothing to do here.  */
+	gcond *cond = as_a<gcond *> (pred_last);
+	tree cond_lhs = lookup_equiv_head (gimple_cond_lhs (cond), p);
+	tree cond_rhs = lookup_equiv_head (gimple_cond_rhs (cond), p);
+	if (!((expressions_equal_p (vno->op[0], cond_lhs)
+	       && expressions_equal_p (vno->op[1], cond_rhs))
+	      || (expressions_equal_p (vno->op[0], cond_lhs)
+		  && expressions_equal_p (vno->op[1], cond_rhs))))
+	  continue;
+
+	hash_set<basic_block> *phi_bbs = dominator_to_phi_map->get (p);
+	if (!phi_bbs)
+	  continue;
+	enum tree_code pred_code = gimple_cond_code (pred_last);
+	/* Find out previous true & false edge destinations (here "true" and
+	   "false" correspond to current bb).
+	   First initialize them with bb1 and "p's successor that is not
+	   bb1" respectively, then switch them if result in VNO is false.  */
+	basic_block pre_true_dest = bb1;
+	basic_block pre_false_dest = EDGE_SUCC (p, 0)->dest != bb1
+				       ? EDGE_SUCC (p, 0)->dest
+				       : EDGE_SUCC (p, 1)->dest;
+	if (val->result == boolean_false_node)
+	  std::swap (pre_true_dest, pre_false_dest);
+
+	bool insert_by_true = true, insert_by_false = true;
+	/* If the condition in vno is not identical with original condition, but
+	   a relaxed one, then only edge p->bb1 is helpful.  */
+	if (is_relaxed_cond_code (pred_code, vno->opcode))
+	  {
+	    if (val->result == boolean_true_node)
+	      insert_by_false = false;
+	    else
+	      insert_by_true = false;
+	  }
+
+	/* Iterate on basic-blocks with PHIs immediately dominated by p.  */
+	for (hash_set<basic_block>::iterator it = phi_bbs->begin ();
+	     it != phi_bbs->end (); ++it)
+	  {
+	    basic_block phi_bb = *it;
+	    if (!dominated_by_p_w_unex (bb, phi_bb, false))
+	      continue;
+
+	    /* Among true & false edges, if one edge can lead to another before
+	       reaching phi_bb, then we can't derive equivalences by the former.
+	       Part of the situations (when the joint is pre_true_dest or
+	       pre_false_dest) are ruled out by the branch_may_come_from_another
+	       check.  The others (when the joint is a descendant of
+	       pre_true_dest or pre_false_dest) are handled by calculating and
+	       checking possible_true_args & possible_false_args.  */
+	    bool insert_by_true_1
+	      = insert_by_true
+		&& (pre_false_dest == phi_bb
+		    || !branch_may_come_from_another (p, pre_false_dest));
+	    bool insert_by_false_1
+	      = insert_by_false
+		&& (pre_true_dest == phi_bb
+		    || !branch_may_come_from_another (p, pre_true_dest));
+
+	    /* Process PHIs, record the equivalences that can be derived from
+	       previous true or false branch to current bb's successors.  */
+	    for (gphi_iterator gsi = gsi_start_nonvirtual_phis (phi_bb);
+		 !gsi_end_p (gsi); gsi_next_nonvirtual_phi (&gsi))
+	      {
+		gphi *phi = gsi.phi ();
+		tree res = vn_valueize (PHI_RESULT (phi));
+		/* Calculate possible arguments collections for previous true
+		   and false edges.  */
+		hash_set<tree> possible_true_args;
+		hash_set<tree> possible_false_args;
+		for (unsigned k = 0; k < gimple_phi_num_args (phi); ++k)
+		  {
+		    edge in = gimple_phi_arg_edge (phi, k);
+		    tree arg = vn_valueize (gimple_phi_arg_def (phi, k));
+		    if ((in->src == p && pre_true_dest == phi_bb)
+			|| dominated_by_p (CDI_DOMINATORS, in->src,
+					   pre_true_dest))
+		      possible_true_args.add (arg);
+		    else
+		      possible_false_args.add (arg);
+
+		    if ((in->src == p && pre_false_dest == phi_bb)
+			|| dominated_by_p (CDI_DOMINATORS, in->src,
+					   pre_false_dest))
+		      possible_false_args.add (arg);
+		    else
+		      possible_true_args.add (arg);
+		  }
+
+		/* Record equivalences if there's one single argument in the
+		   possible collection. (Otherwise we need to check that all
+		   arguments in the collection are effectively equal.)  */
+		if (true_e && insert_by_true_1
+		    && possible_true_args.elements () == 1)
+		  {
+		    tree arg = *possible_true_args.begin ();
+		    val_equiv_insert (arg, res, true_e);
+		  }
+		if (false_e && insert_by_false_1
+		    && possible_false_args.elements () == 1)
+		  {
+		    tree arg = *possible_false_args.begin ();
+		    val_equiv_insert (arg, res, false_e);
+		  }
+	      }
+	  }
+      }
+}
+
+/* Find predicated value of vn_nary_op by the operands' equivalences.  Return
+ * NULL_TREE if no known result is found.  */
+
+static tree
+find_predicated_value_by_equivs (vn_nary_op_t vno, basic_block bb,
+				 vn_nary_op_t *vnresult)
+{
+  lookup_equiv_heads (vno->length, vno->op, vno->op, bb);
+  tree result
+    = simplify_nary_op (vno->length, vno->opcode, vno->op, vno->type);
+  if (result)
+    {
+      if (!useless_type_conversion_p (vno->type, TREE_TYPE (result)))
+	result = fold_convert (vno->type, result);
+      return result;
+    }
+  return vn_nary_op_lookup_1 (vno, vnresult);
 }
 
 /* Insert the rhs of STMT into the current hash table with a value number of
@@ -4499,6 +4988,20 @@ vn_phi_lookup (gimple *phi, bool backedges_varying_p)
   return (*slot)->result;
 }
 
+/* Record mappings from immediate dominator to basic_block with PHIs.  */
+
+static void
+record_dom_to_phi_bb (basic_block idom, basic_block phi_bb)
+{
+  /* Rule out when there is a backedge between idom and phi_bb.  */
+  basic_block loop_header = phi_bb->loop_father->header;
+  if (!dominated_by_p (CDI_DOMINATORS, idom, loop_header)
+      && dominated_by_p (CDI_DOMINATORS, loop_header, idom))
+    return;
+  hash_set<basic_block> &phi_bbs = dominator_to_phi_map->get_or_insert (idom);
+  phi_bbs.add (phi_bb);
+}
+
 /* Insert PHI into the current hash table with a value number of
    RESULT.  */
 
@@ -4536,6 +5039,9 @@ vn_phi_insert (gimple *phi, tree result, bool backedges_varying_p)
 	   allow VN_TOP.  */
 	vp1->cclhs = vn_valueize (gimple_cond_lhs (last1));
 	vp1->ccrhs = vn_valueize (gimple_cond_rhs (last1));
+	/* Record the mapping, this will be used in
+	 * record_equiv_from_previous_cond.  */
+	record_dom_to_phi_bb (idom1, vp1->block);
       }
   vp1->result = result;
   vp1->hashcode = vn_phi_compute_hash (vp1);
@@ -4862,8 +5368,32 @@ static bool
 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 = vn_nary_op_lookup_1 (vno, &vnresult);
+
+  /* Because we search by equivalences, there's a change to get a simplified
+     result.  */
+  if (!result)
+    {
+      gimple *use_stmt;
+      use_operand_p use_p;
+      /* Replacing variable used in PHI at loop exit may cause
+       * simplify_peeled_chrec/constant_after_peeling to miss the loop.  */
+      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
+	  = simplify_nary_op (vno->length, vno->opcode, vno->op, vno->type);
+      if (result && !useless_type_conversion_p (vno->type, TREE_TYPE (result)))
+	result = fold_convert (vno->type, result);
+    }
+
+  if (!result && vnresult)
     result = vn_nary_op_get_predicated_value (vnresult, gimple_bb (stmt));
   if (result)
     return set_ssa_val_to (lhs, result);
@@ -6932,6 +7462,8 @@ free_rpo_vn (void)
 
   delete constant_to_value_id;
   constant_to_value_id = NULL;
+  delete dominator_to_phi_map;
+  dominator_to_phi_map = NULL;
 }
 
 /* Hook for maybe_push_res_to_seq, lookup the expression in the VN tables.  */
@@ -7307,17 +7839,23 @@ process_bb (rpo_elim &avail, basic_block bb,
 	    tree val = gimple_simplify (gimple_cond_code (last),
 					boolean_type_node, lhs, rhs,
 					NULL, vn_valueize);
+	    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);
+		vn_nary_op_t vno1
+		  = XALLOCAVAR (struct vn_nary_op_s, sizeof_vn_nary_op (2));
+		init_vn_nary_op_from_pieces (vno1, 2, gimple_cond_code (last),
+					     boolean_type_node, ops);
+		val = vn_nary_op_lookup_1 (vno1, &vnresult);
+		if ((!val || TREE_CODE (val) != INTEGER_CST))
+		  /* If no simplified result has been found, try to find one by
+		   * equivalences.  */
+		  val = find_predicated_value_by_equivs (vno1, bb, &vnresult);
 		/* Did we get a predicated value?  */
 		if (! val && vnresult && vnresult->predicated_values)
 		  {
@@ -7382,6 +7920,22 @@ process_bb (rpo_elim &avail, basic_block bb,
 		    if (false_e)
 		      insert_related_predicates_on_edge (icode, ops, false_e);
 		  }
+
+		/* Record new equivalence generated by EQ_EXPR.  */
+		if (code == EQ_EXPR && true_e && vn_tracking_edge (true_e))
+		  val_equiv_insert (ops[0], ops[1], true_e);
+		if (code == NE_EXPR && false_e && vn_tracking_edge (false_e))
+		  val_equiv_insert (ops[0], ops[1], false_e);
+
+		/* If we got a previous condition, but no predicated value, try
+		   to record what we know from previous true & false branches on
+		   current true & false edges.  This might provide some
+		   opportunities for futher prediction.  For now we only record
+		   equivalences generated by PHI nodes, that depends on the
+		   previous condition.  */
+		if (vnresult && (true_e || false_e))
+		  record_equiv_from_previous_cond (vnresult, true_e, false_e,
+						   bb);
 	      }
 	    break;
 	  }
@@ -7504,6 +8058,7 @@ struct unwind_state
   vn_phi_t phi_top;
   vn_nary_op_t nary_top;
   vn_avail *avail_top;
+  nary_ref *nary_ref_top;
 };
 
 /* Unwind the RPO VN state for iteration.  */
@@ -7553,6 +8108,17 @@ do_unwind (unwind_state *to, rpo_elim &avail)
       av->next = avail.m_avail_freelist;
       avail.m_avail_freelist = av;
     }
+  /* Drain nary_refs 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;
+    }
 }
 
 /* Do VN on a SEME region specified by ENTRY and EXIT_BBS in FN.
@@ -7666,6 +8232,9 @@ do_rpo_vn (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;
+  dominator_to_phi_map = new bb_map_t;
 
   vn_valueize = rpo_vn_valueize;
 
@@ -7760,6 +8329,8 @@ do_rpo_vn (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;
 	  }
 
 	if (!(bb->flags & BB_EXECUTABLE))
diff --git a/gcc/tree-ssa-sccvn.h b/gcc/tree-ssa-sccvn.h
index 96100596d2e..545285a4439 100644
--- a/gcc/tree-ssa-sccvn.h
+++ b/gcc/tree-ssa-sccvn.h
@@ -216,6 +216,16 @@ struct vn_avail
   struct vn_ssa_aux *next_undo;
 };
 
+/* In vn_ssa_aux structure, hold a lists of references to the nary map entries,
+   so that when recording new equivalence to the value number, we can re-insert
+   expressions' results based on this.  */
+struct nary_ref
+{
+  nary_ref *next;
+  vn_nary_op_t slot;
+  struct vn_ssa_aux *next_undo;
+};
+
 typedef struct vn_ssa_aux
 {
   /* SSA name this vn_ssa_aux is associated with in the lattice.  */
@@ -229,6 +239,12 @@ 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 VALNUM as operand.  */
+  nary_ref *ref;
+
+  /* nary_ref count.  */
+  unsigned num_nary_ref;
+
   /* Unique identifier that all expressions with the same value have. */
   unsigned int value_id;