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

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

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


I tried to improve the patch following your advices and to catch more
opportunities. Hope it'll be helpful.

On 6/24/21 8:29 AM, Richard Biener wrote: 
> On Thu, Jun 24, 2021 at 11:55 AM Di Zhao via Gcc-patches <gcc-
> patches@gcc.gnu.org> wrote:
> 
> I have some reservations about extending the ad-hoc "predicated value" code.
> 
> Some comments on the patch:
> 
> +/* hashtable & helpers to record equivalences at given bb.  */
> +
> +typedef struct val_equiv_s
> +{
> +  val_equiv_s *next;
> +  val_equiv_s *unwind_to;
> +  hashval_t hashcode;
> +  /* SSA name this val_equiv_s is associated with.  */
> +  tree name;
> +  /* RESULT in a vn_pval entry is SSA name of a equivalence.  */
> +  vn_pval *values;
> +} * val_equiv_t;
> 
> all of this (and using a hashtable for recording) is IMHO a bit overkill.
> Since you only ever record equivalences for values the more natural place to
> hook those in is the vn_ssa_aux structure where we also record the availability
> chain.
 
I tried to store the equivalences in the vn_ssa_aux structure, but I didn't  
optimize the second case successfully: I need to record the equivalence
of a PHI expression's result and arguments, but their value number results will
become VARYING first, so they won't be changed. Maybe I'm missing something, or
can I force change a VARYING result?

Besides, the way currently used, equivalences only need to be "predictable"
rather than available, maybe availability chains do not represent them very
well?

> There's little commentary in the new code, in particular function-level
> comments are missing everywhere.

Added more comments.

> There's complexity issues, like I see val_equiv_insert has a "recurse"
> feature but also find_predicated_value_by_equiv is quadratic in the number of
> equivalences of the lhs/rhs.  Without knowing what the recursion on the
> former is for - nothing tells me - I suspect either of both should be redundant.

The intention was, given {A==B, B==C, X==Y, Y==Z} and a previous result of
"C opcode Z", to find the result of "A opcode Y". I removed the "recurse"
feature and modified the searching logic so solve the issue. Now a temporary
hash_set is used to record the equivalences that are visited when searching.

> You seem to record equivalences at possible use points which looks odd at best
> - I'd expected equivalences being recorded at the same point we record
> predicated values and for the current condition, not the one determining some
> other predication.
> What was the motivation to do it the way you do it?

The purpose is to "bring down" what can be known from a previous basic-block
that effectively dominates current block, but not actually does so (in the
example it is because jump threading is hindered by a loop). For example in
this case:

  if (a != 0)
      // Nothing useful can be recorded here, because this BB doesn't dominate
      // the BB that we want to simplify.
      c = b;
  for (unsigned i = 0; i < c; i++)
    {
      if (a != 0)  // The recording is triggered here.
       {
         // c == b will be recorded here, so it can be used for simplification.
         // In gimple it is the equivalence of a PHI's result and argument.
         if (i >= b) 
           foo ();

These requires finding a previous condition that is identical with current
one, so it is convenient to do this in FRE. Besides, as FRE records derived
predicate, so for relative conditions there also might be opportunities for
optimization. In the new patch code this is included.

Besides, to find more opportunities, added a hashmap to store mappings from
immediate dominators to basic-blocks with PHIs of interest.

> Why is the code conditional on 'iterate'?

I haven't worked it out to fit the non-iterate mode, so it now breaks the
if_conversion pass. I think this is because some of the equivalence-recordings
are too optimistic for non-iterate mode.

> You've probably realized that there's no "nice" way to handle temporary
> equivalences in a VN scheme using hashing for expressions (unless you degrade
> hashes a lot).

I modified the code to use TREE_HASH on ssa names. Would that be better?  

> You quote opportunities that are catched with this like
> 
> +  if (a != 0)
> +    {
> +      c = b;
> +    }
> +  for (unsigned i = 0; i < c; i++)
> +    {
> +      if (a != 0)
> +       {
> +         if (i >= b)
> +           /* Should be eliminated.
> +            */
> +           foo ();
> 
> but say other "obvious" cases like
> 
> +  if (a != 0)
> +    {
> +      c = b;
> +    }
> +  for (unsigned i = 0; i < c; i++)
> +    {
> +      if (a != 0)
> +       {
> +           /* Should be zero.  */
>              return b - c;
> 
> are not handled.  That's in line with the current "value predication"
> which mainly aims at catching simple jump threading opportunities; you only
> simplify conditions with the recorded equivalences.  But then the complexity of
> handling equivalences does probably not outweight the opportunities catched -
> can you share some numbers on how many branches are newly known taken
> during VN with this patch during say bootstrap or build of SPEC CPU?

I extended the code a little to cover the cases like "A - A" and "A xor A".

Here are some results on one bootstrap step: 
           | values found | more bb removed | values found in all
           | in fre1      | at fre1         | fre & pre passes   
-----------------------------------------------------------------
 bootstrap | 592          | 40              | 1272

As the code is different for bootstrap, the "more bb removed" metric is not
precise. I also tested on SPEC CPU 2017 integer cases:
                | values found | more bb removed | values found in all
                | in fre1      | at fre1         | fre & pre passes
-----------------------------------------------------------------
 500.perlbench_r| 3            |  0              | 9
 502.gcc_r      | 25           |  39             | 241
 520.omnetpp    | 9            |  6              | 34
 523.xalancbmk_r| 12           |  0              | 35
 541.leela_r    | 2            |  0              | 2

In cases not listed above there's no value found by equivalences. Benefits
after fre1 are not counted as CGF may be different from here (for
523.xalancbmk_r there're 8 more basic-blocks removed at fre3). Although the
chances are not plenty, there might be potential benefits, such as making a
function pure.

> I've hoped to ditch the current "value predication" code by eventually using the
> relation oracle from ranger but did not yet have the chance to look into that.
> Now, the predicated equivalences are likely not something that infrastructure
> can handle?
> 
> In the end I think we should research into maintaining an alternate expression
> table for conditions (those we like to simplify with
> equivalences) and use a data structure that more easily allows to introduce
> (temporary) equivalences.  Like by maintaining back-references of values we've
> recorded a condition for and a way to quickly re-canonicalize conditions.  Well -
> it requires some research, as said.
> 
> Richard.
> 
> > Regards,
> > Di Zhao
> >
> > Extend FRE with an "equivalence map" for condition prediction.
> >
> > 2021-06-24  Di Zhao  <dizhao@os.amperecomputing.com>
> >

Thanks,
Di Zhao

--------
Extend FRE with an "equivalence map" for condition prediction.

2021-07-18  Di Zhao  <dizhao@os.amperecomputing.com>

gcc/ChangeLog:
        PR tree-optimization/101186
        * tree-ssa-sccvn.c (vn_tracking_edge): Extracted utility function.
        (dominated_by_p_w_unex): Moved upward, no change.
        (vn_nary_op_get_predicated_value): Moved upward, no change.
        (struct val_equiv_hasher): Hasher for the "equivalence map".
        (is_vn_valid_at_bb): Check if vn_pval is valid at BB.
        (val_equiv_insert): Insert into "equivalence map".
        (vn_lookup_binary_op_result): Lookup binary expression's result by VN.
        (iterate_val_equivs): Iterate on equivalences and returns a non-NULL
        result returned by callback.
        (find_predicated_binary_by_lhs_equiv): Callback for iterate_val_equivs.
        Lookup a binary operations result by LHS equivalences.
        (find_predicated_binary_by_rhs_equiv): Callback for iterate_val_equivs.
        Lookup a binary operations result by RHS equivalences.
        (find_predicated_binary_by_equiv): Lookup predicated value of a binary
        operation by equivalences.
        (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.
        (record_equiv_from_previous_edge): Record equivalence relation from a
        previous condition on current bb' true and false edges. 
        (record_equiv_from_previous_cond): Record equivalences generated by
        previous conditions on current BB's true and false edges.
        (vn_nary_op_insert_pieces_predicated): Extract utility function. Insert
        into the "equivalence map" for predicate like "x==y is true".
        (record_dom_to_phi_bb): Record mappings from immediate dominator to
        basic_block with PHIs.
        (vn_phi_lookup): Record mappings from immediate dominator to PHIs.
        (visit_nary_op): Add lookup predicated values of binaries by
        equivalences.
        (free_rpo_vn): Free the "equivalence map".
        (process_bb): Insert into & lookup from the "equivalence map".
        (struct unwind_state): Add "equivalence map" unwind state.
        (do_unwind): Unwind the "equivalence map".
        (do_rpo_vn): Update "equivalence map" unwind state.

gcc/testsuite/ChangeLog:
        PR tree-optimization/101186
        * 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/vrp03.c: Disable fre.
        * gcc.dg/tree-ssa/ssa-fre-95.c: New test.
        * gcc.dg/tree-ssa/ssa-fre-96.c: New test.

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

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/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..c6a94bc0f22
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-96.c
@@ -0,0 +1,74 @@
+/* { 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, as "a >= 0" can be derived from "a >
+	     * 0".
+	     */
+	    bas ();
+	}
+      else
+	{
+	  if (i >= d)
+	    /* Should be eliminated, as "a < 0" can be derived from "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/vrp03.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp03.c
index bafb65a53d6..bea2f1b0de5 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" } */
+/* { dg-options "-O2 -fdisable-tree-evrp -fno-tree-fre -fdump-tree-vrp1" } */
 
 struct A
 {
diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
index 7900df946f4..5e29ffa9345 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.  */
@@ -3779,6 +3785,515 @@ vn_reference_insert_pieces (tree vuse, alias_set_type set,
   return vr1;
 }
 
+/* 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;
+}
+
+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;
+}
+
+/* hashtable & helpers to record equivalences.  */
+
+typedef struct val_equiv_s
+{
+  val_equiv_s *next;
+  val_equiv_s *unwind_to;
+  /* SSA name this val_equiv_s is associated with.  */
+  tree name;
+  /* RESULT in a vn_pval entry is SSA name of a equivalence.  */
+  vn_pval *values;
+} * val_equiv_t;
+
+struct val_equiv_hasher : nofree_ptr_hash<val_equiv_s>
+{
+  static inline hashval_t hash (const val_equiv_s *entry)
+  {
+    return TREE_HASH (entry->name);
+  }
+  static inline bool equal (const val_equiv_t &entry, const val_equiv_t &other)
+  {
+    return other->name == entry->name;
+  }
+};
+
+static hash_table<val_equiv_hasher> *val_equiv_hash;
+typedef hash_table<val_equiv_hasher>::iterator val_equiv_iterator_type;
+
+static val_equiv_t last_inserted_equiv;
+
+/* Whether the predicated value in VAL is valid at basic-block 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 (CDI_DOMINATORS, bb, val_bb))
+	{
+	  return true;
+	}
+    }
+  return false;
+}
+
+/* Record in hash table that EQUIV is an equivalence of NAME at location BB.
+   Return the resulting reference structure we created.  */
+
+static val_equiv_t
+val_equiv_insert (tree name, tree equiv, basic_block bb)
+{
+  if (TREE_CODE (name) == SSA_NAME)
+    name = VN_INFO (name)->valnum;
+  if (TREE_CODE (equiv) == SSA_NAME)
+    equiv = VN_INFO (equiv)->valnum;
+  if (name == equiv)
+    return NULL;
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Recording equivalence of ");
+      print_generic_expr (dump_file, name);
+      fprintf (dump_file, " and ");
+      print_generic_expr (dump_file, equiv);
+      fprintf (dump_file, " at BB%d\n", bb->index);
+    }
+  /* Similar with inserting vn_nary_op_t, maintain a stack of states to unwind
+   * for iteration.  */
+  val_equiv_t new_equiv
+    = (val_equiv_t) obstack_alloc (&vn_tables_obstack, sizeof (val_equiv_s));
+  new_equiv->name = name;
+  new_equiv->values
+    = (vn_pval *) obstack_alloc (&vn_tables_obstack, sizeof (vn_pval));
+  new_equiv->values->next = NULL;
+  new_equiv->values->n = 1;
+  new_equiv->values->valid_dominated_by_p[0] = bb->index;
+  new_equiv->values->result = equiv;
+  val_equiv_t *slot
+    = val_equiv_hash->find_slot_with_hash (new_equiv, TREE_HASH (name), INSERT);
+  new_equiv->unwind_to = *slot;
+
+  if (*slot)
+    {
+      bool found = false;
+      vn_pval *nval = new_equiv->values;
+      vn_pval **next = &(new_equiv->values);
+      for (vn_pval *val = (*slot)->values; val; val = val->next)
+	{
+	  if (val->result == equiv)
+	    {
+	      found = true;
+	      if (is_vn_valid_at_bb (val, bb))
+		/* More generic equivalence has been recorded.  */
+		return *slot;
+	      /* 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] = bb->index;
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		fprintf (dump_file, "Appending equivalence.\n");
+	      next = &(*next)->next;
+	      continue;
+	    }
+	  /* Copy others.  */
+	  unsigned val_size = sizeof (vn_pval) + (val->n - 1) * sizeof (int);
+	  *next = (vn_pval *) obstack_alloc (&vn_tables_obstack, val_size);
+	  memcpy (*next, val, val_size);
+	  (*next)->next = NULL;
+	  next = &(*next)->next;
+	}
+      if (!found)
+	// append new equiv at last
+	*next = nval;
+    }
+
+  *slot = new_equiv;
+  new_equiv->next = last_inserted_equiv;
+  last_inserted_equiv = new_equiv;
+  return new_equiv;
+}
+
+/* Lookup result (value number) of a binary operation in the hash table.  If no
+ * result is found, NULL_TREE will be returned.  */
+
+static tree
+vn_lookup_binary_op_result (tree lhs, tree rhs, tree_code code, basic_block bb)
+{
+  tree val = NULL_TREE;
+  // Try to simplify first.
+  if (lhs == rhs)
+    switch (code)
+      {
+      case EQ_EXPR:
+      case LE_EXPR:
+      case GE_EXPR:
+	return boolean_true_node;
+      case LT_EXPR:
+      case GT_EXPR:
+      case NE_EXPR:
+	return boolean_false_node;
+      case MINUS_EXPR:
+      case BIT_XOR_EXPR:
+	return integer_zero_node;
+      default:;
+      }
+  tree ops[2];
+  ops[0] = lhs;
+  ops[1] = rhs;
+  vn_nary_op_t vno;
+  val = vn_nary_op_lookup_pieces (2, code, boolean_type_node, ops, &vno);
+  /* Did we get a predicated value?  */
+  if (!val && vno && vno->predicated_values)
+    val = vn_nary_op_get_predicated_value (vno, bb);
+  return val;
+}
+
+/* Callback function type for iterate_val_equivs.  */
+
+typedef tree (*handle_equiv) (tree, basic_block, void *);
+
+/* Iterate on all the equivalences of NAME that are valid at BB, until
+ * CALLBACK returns a non-NULL result for an equivalence.  If there's no
+ * equivalence or non-NULL result, return NULL_TREE.  */
+
+tree
+iterate_val_equivs (tree name, basic_block bb, handle_equiv callback,
+		    void *callback_arg)
+{
+  struct val_equiv_s val_equiv;
+  /* todo_list stores the equivalences we need to search iteratively.
+     For example, in the hashtable we have "X's equivalence = {Y}" and "X's
+     equivalence = {Z}", by searching iteratively we have "X==Z".
+     done_set stores the equivalences that are already visited, to avoid
+     searching repeatedly.  */
+  hash_set<tree> done_set;
+  auto_vec<tree> todo_list;
+  unsigned int todo_index = 0;
+  todo_list.safe_push (name);
+  tree result;
+  val_equiv_t *slot;
+  /* Iterate all elements in the todo_list.  */
+  while (todo_index < todo_list.length ())
+    {
+      val_equiv.name = todo_list[todo_index];
+      todo_index++;
+      slot = val_equiv_hash->find_slot_with_hash (&val_equiv,
+						  TREE_HASH (val_equiv.name),
+						  NO_INSERT);
+      if (!slot)
+	/* Possible for NAME itself.  */
+	continue;
+      /* Process all valid equivalences of current element.  */
+      for (vn_pval *val = (*slot)->values; val; val = val->next)
+	{
+	  if (done_set.contains (val->result)
+	      || !is_vn_valid_at_bb (val, bb))
+	    continue;
+	  if ((result = callback (val->result, bb, callback_arg)))
+	    return result;
+	  done_set.add (val->result);
+	  todo_list.safe_push (val->result);
+	}
+    }
+    return NULL_TREE;
+}
+
+/* Helpers to lookup the results of binary operations by equivalences.  */
+
+typedef struct find_binary_by_equiv_arg_s
+{
+  /* The other operand.  */
+  tree other;
+  tree_code code;
+  auto_vec<tree> *vec;
+} * find_binary_by_equiv_arg_t;
+
+/* Callback for find_predicated_binary_by_equiv.  Lookup a binary operations'
+ * result by lhs equivalences.  */
+
+tree
+find_predicated_binary_by_lhs_equiv (tree equiv, basic_block bb,
+				     void *callback_arg)
+{
+  find_binary_by_equiv_arg_t args
+    = (find_binary_by_equiv_arg_t) callback_arg;
+  tree result
+    = vn_lookup_binary_op_result (equiv, args->other, args->code, bb);
+  if (!result)
+    /* If no result is found, store equivalence to list, in case we need to
+       search by rhs.  */
+    args->vec->safe_push (equiv);
+  return result;
+}
+
+/* Callback for find_predicated_binary_by_equiv.  Lookup a binary operations'
+ * result by rhs equivalences.  */
+
+tree
+find_predicated_binary_by_rhs_equiv (tree equiv, basic_block bb,
+				     void *callback_arg)
+{
+  find_binary_by_equiv_arg_t args
+    = (find_binary_by_equiv_arg_t) callback_arg;
+  tree result
+    = vn_lookup_binary_op_result (args->other, equiv, args->code, bb);
+  if (result)
+    return result;
+  // Search by both sides' equivalences.
+  for (unsigned j = 0; j < args->vec->length (); ++j)
+    if ((result = vn_lookup_binary_op_result ((*args->vec)[j], equiv,
+					 args->code, bb)))
+      return result;
+  return NULL_TREE;
+}
+
+/* Lookup result (value number) of a binary operation by the equivalences of LHS
+ * and RHS.  If no result is found, NULL_TREE will be returned.  */
+
+static tree
+find_predicated_binary_by_equiv (tree lhs, tree rhs, tree_code code,
+				 basic_block bb)
+{
+  if (TREE_CODE (lhs) == SSA_NAME)
+    lhs = VN_INFO (lhs)->valnum;
+  // search by lhs
+  auto_vec<tree> lhs_equivs;
+  find_binary_by_equiv_arg_s args;
+  args.vec = &lhs_equivs;
+  args.other = rhs;
+  args.code = code;
+  tree result
+    = iterate_val_equivs (lhs, bb, find_predicated_binary_by_lhs_equiv,
+			  (void *) (&args));
+  if (result)
+    return result;
+  // search by rhs
+  if (TREE_CODE (rhs) == SSA_NAME)
+    rhs = VN_INFO (rhs)->valnum;
+  args.other = lhs;
+  return iterate_val_equivs (rhs, bb, find_predicated_binary_by_rhs_equiv,
+			     (void *) (&args));
+}
+
+/* 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
+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 <=> EQ_EXPR
+    return false;
+  return true;
+}
+
+/* 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 (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;
+}
+
+/* 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)
+    for (unsigned i = 0; i < val->n; ++i)
+      {
+	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;
+	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->dest);
+		    val_equiv_insert (res, arg, true_e->dest);
+		  }
+		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->dest);
+		    val_equiv_insert (res, arg, false_e->dest);
+		  }
+	      }
+	  }
+      }
+}
+
 /* Compute and return the hash value for nary operation VBO1.  */
 
 static hashval_t
@@ -4153,21 +4668,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)
+  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)
@@ -4180,6 +4682,12 @@ vn_nary_op_insert_pieces_predicated (unsigned int length, enum tree_code code,
       fprintf (dump_file, " == %s\n",
 	       integer_zerop (result) ? "false" : "true");
     }
+  if (code == EQ_EXPR && result == boolean_true_node)
+    /* NE_EXPRs with false result are handled by inverted condition.  */
+    {
+      val_equiv_insert (ops[0], ops[1], pred_e->dest);
+      val_equiv_insert (ops[1], ops[0], pred_e->dest);
+    }
   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;
@@ -4192,26 +4700,6 @@ vn_nary_op_insert_pieces_predicated (unsigned int length, enum tree_code code,
   return vn_nary_op_insert_into (vno1, valid_info->nary, true);
 }
 
-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;
-}
-
 /* Insert the rhs of STMT into the current hash table with a value number of
    RESULT.  */
 
@@ -4409,6 +4897,22 @@ vn_phi_eq (const_vn_phi_t const vp1, const_vn_phi_t const vp2)
   return true;
 }
 
+/* Record mappings from immediate dominator to basic_block with PHIs.  */
+
+static void
+record_dom_to_phi_bb (basic_block idom, basic_block phi_bb)
+{
+  if (!dominator_to_phi_map)
+    return;
+  /* 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);
+}
+
 /* Lookup PHI in the current hash table, and return the resulting
    value number if it exists in the hash table.  Return NULL_TREE if
    it does not exist in the hash table. */
@@ -4447,6 +4951,9 @@ vn_phi_lookup (gimple *phi, 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->hashcode = vn_phi_compute_hash (vp1);
   slot = valid_info->phis->find_slot_with_hash (vp1, vp1->hashcode, NO_INSERT);
@@ -4819,8 +5326,27 @@ visit_nary_op (tree lhs, gassign *stmt)
 {
   vn_nary_op_t vnresult;
   tree result = vn_nary_op_lookup_stmt (stmt, &vnresult);
-  if (! result && vnresult)
+  if (!result && vnresult)
     result = vn_nary_op_get_predicated_value (vnresult, gimple_bb (stmt));
+  if (!result)
+    {
+      /* Try to find a predicated result by equivalences.  */
+      tree_code opcode = gimple_assign_rhs_code (stmt);
+      // binary operation
+      if (gimple_num_ops (stmt) == 3)
+	result = find_predicated_binary_by_equiv (gimple_op (stmt, 1),
+						  gimple_op (stmt, 2), opcode,
+						  gimple_bb (stmt));
+      if (result
+	  && !useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (result)))
+	result = fold_convert (TREE_TYPE (lhs), result);
+      if (result && dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "Found predicated value ");
+	  print_generic_expr (dump_file, result, TDF_SLIM);
+	  fprintf (dump_file, " by equivalence.\n");
+	}
+    }
   if (result)
     return set_ssa_val_to (lhs, result);
 
@@ -6861,9 +7387,13 @@ free_rpo_vn (void)
       release_ssa_name (info->name);
   obstack_free (&vn_ssa_aux_obstack, NULL);
   delete vn_ssa_aux_hash;
+  delete val_equiv_hash;
+  val_equiv_hash = NULL;
 
   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.  */
@@ -7239,11 +7769,11 @@ 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;
@@ -7262,6 +7792,20 @@ process_bb (rpo_elim &avail, basic_block bb,
 			print_gimple_stmt (dump_file, last, TDF_SLIM);
 		      }
 		  }
+		if (!val && iterate)
+		  {
+		    /* Try to find a result by equivalences of lhs and rhs.  */
+		    val
+		      = find_predicated_binary_by_equiv (lhs, rhs,
+							gimple_cond_code (last),
+							bb);
+		    if (val && dump_file && (dump_flags & TDF_DETAILS))
+		      {
+			fprintf (dump_file, "Found predicated value ");
+			print_generic_expr (dump_file, val, TDF_SLIM);
+			fprintf (dump_file, " by equivalence.\n");
+		      }
+		  }
 	      }
 	    if (val)
 	      e = find_taken_edge (bb, val);
@@ -7314,6 +7858,16 @@ process_bb (rpo_elim &avail, basic_block bb,
 		    if (false_e)
 		      insert_related_predicates_on_edge (icode, ops, 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 (iterate && vnresult && (true_e || false_e))
+		  record_equiv_from_previous_cond (vnresult, true_e, false_e,
+						   bb);
 	      }
 	    break;
 	  }
@@ -7435,6 +7989,7 @@ struct unwind_state
   vn_reference_t ref_top;
   vn_phi_t phi_top;
   vn_nary_op_t nary_top;
+  val_equiv_t equiv_top;
   vn_avail *avail_top;
 };
 
@@ -7473,6 +8028,17 @@ do_unwind (unwind_state *to, rpo_elim &avail)
       (*slot)->operands.release ();
       valid_info->references->clear_slot (slot);
     }
+  for (; last_inserted_equiv != to->equiv_top;
+       last_inserted_equiv = last_inserted_equiv->next)
+    {
+      val_equiv_t *slot;
+      slot = val_equiv_hash->find_slot_with_hash (
+	last_inserted_equiv, TREE_HASH (last_inserted_equiv->name), NO_INSERT);
+      if ((*slot)->unwind_to)
+	*slot = (*slot)->unwind_to;
+      else
+	val_equiv_hash->clear_slot (slot);
+    }
   obstack_free (&vn_tables_obstack, to->ob_top);
 
   /* Prune [rpo_idx, ] from avail.  */
@@ -7588,6 +8154,7 @@ do_rpo_vn (function *fn, edge entry, bitmap exit_bbs,
   next_constant_value_id = -1;
 
   vn_ssa_aux_hash = new hash_table <vn_ssa_aux_hasher> (region_size * 2);
+  val_equiv_hash = new hash_table <val_equiv_hasher> (5);
   gcc_obstack_init (&vn_ssa_aux_obstack);
 
   gcc_obstack_init (&vn_tables_obstack);
@@ -7598,6 +8165,7 @@ do_rpo_vn (function *fn, edge entry, bitmap exit_bbs,
   last_inserted_phi = NULL;
   last_inserted_nary = NULL;
   last_pushed_avail = NULL;
+  last_inserted_equiv = NULL;
 
   vn_valueize = rpo_vn_valueize;
 
@@ -7668,6 +8236,7 @@ do_rpo_vn (function *fn, edge entry, bitmap exit_bbs,
 		  }
 	      rpo_state[bb_to_rpo[header->index]].iterate = non_latch_backedge;
 	    }
+      dominator_to_phi_map = new bb_map_t;
     }
 
   uint64_t nblk = 0;
@@ -7691,6 +8260,7 @@ do_rpo_vn (function *fn, edge entry, bitmap exit_bbs,
 	    rpo_state[idx].ref_top = last_inserted_ref;
 	    rpo_state[idx].phi_top = last_inserted_phi;
 	    rpo_state[idx].nary_top = last_inserted_nary;
+	    rpo_state[idx].equiv_top = last_inserted_equiv;
 	    rpo_state[idx].avail_top
 	      = last_pushed_avail ? last_pushed_avail->avail : NULL;
 	  }