public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH] tree-optimization/101186 - extend FRE with "equivalence map" for condition prediction
@ 2021-06-24  9:54 Di Zhao
  2021-06-24 12:29 ` Richard Biener
  0 siblings, 1 reply; 11+ messages in thread
From: Di Zhao @ 2021-06-24  9:54 UTC (permalink / raw)
  To: gcc-patches

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

This patch enhances FRE by recording equivalences generated by conditional
statements, so that we can find more optimize opportunities in situations like
following two cases:

case 1:
    void f (unsigned int a, unsigned int b)
    {
      if (a == b)
        {
          for (unsigned i = 0; i < a; i++)
                      {
                        if (i == b)
                          foo (); /* Unreachable */
                      }
        }
    }
The "i == b" condition is always false, yet original FRE cannot predict this.
Because VN only stores "i < a" and "a == b", so there won't be "i == b"'s
result. (Moreover, VRP can't infer "i == b" is false either, as its boundary
calculation is hindered by the "unsigned" modifier.)

case 2:
Consider GIMPLE code:
              <bb 2> :
              if (a != 0)
              goto <bb 3>; [INV]
              else
              goto <bb 4>; [INV]

              <bb 3> :

              <bb 4> :
              # c = PHI <y(2), x(3)>
              if (a != 0)
              goto <bb 5>; [INV]
              else
              goto <bb 7>; [INV]

              <bb 5> :
              if (c > x)
              goto <bb 6>; [INV]
              else
              goto <bb 8>; [INV]

              <bb 6> :
              __builtin_puts (&"Unreachable!"[0]);

              <bb 7> :
              __builtin_puts (&"a"[0]);

              <bb 8> :
              ...
The result of "if (c > x)" in bb4 is unknown. However bb2 and bb4 have the same
conditional statement, meanwhile bb2 dominates bb4, so it is predictable that
c==x at bb5 and c==y at bb7. Keeping record of this might bring further
optimizations, such as removing the conditional in bb5.

The basic idea is to use a hashmap to record additional equivalence information
generated by conditional statements.

Insert to the map:
    1. When recording an EQ_EXPR=true predicate, e.g. "x==y is true", record
    the equivalence of x and y at edge destiny in the map.
    2. Consider case 2 above, when we fail to predict the result of a
    conditional expression (at bb4), if following conditions be satisfied:
              a. There is a previous corresponding predicate. In this case, it will
              be "a != 0 is true" at bb3.
              b. bb3's single predecessor bb2 dominates bb4.
              c. bb3's conditional statement's predicate code (or inverted code) is
              identical with that of bb4. (This condition can be relaxed.)
    Then we can try to find a PHI operation along A's true and false edge, and
    record the equivalence of PHI operation's result and arguments at bb4's
    true and false destinations. Regarding this case, "c==x at bb5" and
    "c==y at bb7" will be recorded.

Use the map:
    When we cannot find a prediction result for a conditional statement by
    original process, replace conditional expression's operands with qualified
    equivalence and try again.

As searching predicates and the ssa names to record are based on
value numbering, we need to "unwind" the equivalence map for iteration.

Bootstrapped and tested on x86_64-pc-linux-gnu and aarch64-unknown-linux-gnu.

Regards,
Di Zhao

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

2021-06-24  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".
        (compute_single_op_hash): Compute hashcode from ssa name.
        (is_vn_qualified_at_bb): Check if vn_pval is valid at BB.
        (val_equiv_insert): Insert into "equivalence map".
        (vn_lookup_cond_result): Lookup conditional expression's result by VN.
        (find_predicated_value_by_equiv): Search for predicated value,
        utilizing equivalences that we have recorded.
        (record_equiv_from_previous_edge): Record equivalence relation from a
        previouse edge on current edge.
        (record_equiv_from_previous_cond): Search for equivalences generated by
        previous conditional statements, and record them on current BB's
        successors.
        (vn_nary_op_insert_pieces_predicated): Extract utility function. Insert
        into the "equivalence map" for predicate like "x==y is true".
        (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/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.patch --]
[-- Type: application/octet-stream, Size: 20679 bytes --]

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..9ba1c8c61ba
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-95.c
@@ -0,0 +1,80 @@
+/* { 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, cannot be eliminated by VRP. FRE can eliminate this.
+	     */
+	    foo ();
+	}
+    }
+}
+
+void g (unsigned int a, unsigned int b)
+{
+  for (unsigned i = 0; i < a; i++)
+    {
+      if (a == b)
+	{
+	  if (i >= b)
+	    /* Unreachable, cannot be eliminated by VRP. FRE can eliminate this.
+	     */
+	    foo ();
+	}
+	bag ();
+    }
+}
+
+void h (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 k (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++;
+    }
+}
+
+/* { 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..8e3a133f1ea
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-96.c
@@ -0,0 +1,66 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-fre1" } */
+
+extern void bar(void);
+extern void bag(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 c = 100;
+  if (a != 0)
+    {
+      c = b;
+    }
+  for (unsigned i = 0; i < c; i++)
+    {
+      if (a != 0)
+	{
+	  if (i >= b)
+	    /* Should be eliminated.
+	     */
+	    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 "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 -fdisable-tree-fre1 -fdisable-tree-fre2 -fdisable-tree-fre3 -fdump-tree-vrp1" } */
 
 struct A
 {
diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
index 64e3a707f5c..bcc3ea8ec17 100644
--- a/gcc/tree-ssa-sccvn.c
+++ b/gcc/tree-ssa-sccvn.c
@@ -3781,6 +3781,366 @@ vn_reference_insert_pieces (tree vuse, alias_set_type set,
   return vr1;
 }
 
+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 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;
+
+struct val_equiv_hasher : nofree_ptr_hash<val_equiv_s>
+{
+  static inline hashval_t hash (const val_equiv_s *entry)
+  {
+    return entry->hashcode;
+  }
+  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;
+
+static hashval_t
+compute_single_op_hash (tree name)
+{
+  inchash::hash hstate;
+  inchash::add_expr (name, hstate);
+  return hstate.end ();
+}
+
+static inline bool
+is_vn_qualified_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;
+}
+
+static val_equiv_t
+val_equiv_insert (tree name, tree equiv, basic_block bb, bool recursive)
+{
+  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;
+  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;
+  new_equiv->hashcode = compute_single_op_hash (name);
+  val_equiv_t *slot
+    = val_equiv_hash->find_slot_with_hash (new_equiv, new_equiv->hashcode,
+					   INSERT);
+  new_equiv->unwind_to = *slot;
+  auto_vec<tree> todo_list;
+
+  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_qualified_at_bb (val, bb))
+		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;
+	  /* Record transitive equivalences.  */
+	  if (recursive && is_vn_qualified_at_bb (val, bb))
+	      todo_list.safe_push (val->result);
+	}
+      if (!found)
+	// append new equiv at last
+	*next = nval;
+    }
+
+  *slot = new_equiv;
+  new_equiv->next = last_inserted_equiv;
+  last_inserted_equiv = new_equiv;
+  if (recursive)
+    for (unsigned i = 0; i < todo_list.length (); ++i)
+      {
+	val_equiv_insert (todo_list[i], equiv, bb, false);
+	val_equiv_insert (equiv, todo_list[i], bb, false);
+      }
+  return new_equiv;
+}
+
+static tree
+vn_lookup_cond_result (tree lhs, tree rhs, tree_code code, basic_block bb)
+{
+  // Shortcut for gimple_simplify, as it can get confused by the ~X == 1
+  // -> X == 0 transform.
+  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;
+      default:;
+      }
+  tree val;
+  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;
+}
+
+static tree
+find_predicated_value_by_equiv (tree lhs, tree rhs, tree_code code,
+				basic_block bb)
+{
+  if (TREE_CODE (lhs) == SSA_NAME)
+    lhs = VN_INFO (lhs)->valnum;
+  struct val_equiv_s equiv;
+  tree result;
+  equiv.name = lhs;
+  equiv.hashcode = compute_single_op_hash (lhs);
+  val_equiv_t *slot
+    = val_equiv_hash->find_slot_with_hash (&equiv, equiv.hashcode, NO_INSERT);
+  auto_vec<tree> lhs_equivs;
+  // Search by lhs's equivalences.
+  if (slot)
+    {
+      for (vn_pval *val = (*slot)->values; val; val = val->next)
+	{
+	  if (!is_vn_qualified_at_bb (val, bb))
+	    continue;
+	  if ((result = vn_lookup_cond_result (val->result, rhs, code, bb)))
+	    return result;
+	  // Store equivalence to list, in case we need to search by rhs.
+	  lhs_equivs.safe_push (val->result);
+	}
+    }
+  // Search by rhs's equivalences.
+  if (TREE_CODE (rhs) == SSA_NAME)
+    rhs = VN_INFO (rhs)->valnum;
+  equiv.name = rhs;
+  equiv.hashcode = compute_single_op_hash (rhs);
+  slot
+    = val_equiv_hash->find_slot_with_hash (&equiv, equiv.hashcode, NO_INSERT);
+  if (!slot)
+    return NULL_TREE;
+  for (vn_pval *val = (*slot)->values; val; val = val->next)
+    {
+      if (!is_vn_qualified_at_bb (val, bb))
+	continue;
+      if ((result = vn_lookup_cond_result (lhs, val->result, code, bb)))
+	return result;
+      // Search by both sides's equivalences.
+      for (unsigned j = 0; j < lhs_equivs.length (); ++j)
+	if ((result
+	     = vn_lookup_cond_result (lhs_equivs[j], val->result, code, bb)))
+	  return result;
+    }
+  return NULL_TREE;
+}
+
+/* Record equivalence generated by PHI node, on current visiting edge's
+ * destination.  */
+
+static void
+record_equiv_from_previous_edge (basic_block pred, basic_block dest, edge e)
+{
+  if (!vn_tracking_edge (e))
+    return;
+  while (single_succ_p (dest) && single_pred_p (dest))
+    {
+      pred = dest;
+      dest = single_succ (dest);
+    }
+  if (single_pred_p (dest))
+    return;
+  /* Currently situations like this are not handled:
+	  pred
+	  /  \
+	 /t   \f
+	B       C
+	 \    /  \
+	  \  /    \
+      D (PHI node)  E
+	    |
+	    |
+	  current
+	   / \
+	  /t  \f
+	   ...
+  */
+  for (gphi_iterator gsi = gsi_start_nonvirtual_phis (dest); !gsi_end_p (gsi);
+       gsi_next_nonvirtual_phi (&gsi))
+    {
+      gphi *phi = gsi.phi ();
+      tree res = vn_valueize (PHI_RESULT (phi));
+      for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
+	{
+	  edge in = gimple_phi_arg_edge (phi, i);
+	  if (in->src == pred)
+	    {
+	      tree arg = vn_valueize (gimple_phi_arg_def (phi, i));
+	      if (arg == res)
+	      	continue;
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		{
+		  fprintf (dump_file, "Recording equivalence of ");
+		  print_generic_expr (dump_file, res);
+		  fprintf (dump_file, " and ");
+		  print_generic_expr (dump_file, arg);
+		  fprintf (dump_file, " at BB%d\n", e->dest->index);
+		}
+	      val_equiv_insert (res, arg, e->dest, true);
+	      val_equiv_insert (arg, res, e->dest, true);
+	    }
+	}
+    }
+}
+
+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;
+  gimple *pred_last;
+  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]);
+	if (!single_pred_p (bb1))
+	  continue;
+	basic_block p = single_pred (bb1);
+	if (p && dominated_by_p_w_unex (bb, p, false))
+	  {
+	    // Check whether there's an edge "dominates" bb's true/false edge.
+	    pred_last = last_stmt (p);
+	    if (!pred_last || gimple_code (pred_last) != GIMPLE_COND)
+	      continue;
+	    enum tree_code pred_code = gimple_cond_code (pred_last);
+	    enum tree_code pred_icode = swap_tree_comparison (pred_code);
+	    // For now only identical conditions are handled.
+	    // TODO: even if the conditions are not the same, we still have
+	    // one edge that can "derive" one of the current edges.
+	    if (pred_code != vno->opcode && pred_icode != vno->opcode)
+	      continue;
+	    // Find out previous true & false destinies (here "true" and "false"
+	    // are corresponding 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)
+	      {
+		pre_true_dest = pre_false_dest;
+		pre_false_dest = bb1;
+	      }
+	    if (true_e)
+	      record_equiv_from_previous_edge (p, pre_true_dest, true_e);
+	    if (false_e)
+	      record_equiv_from_previous_edge (p, pre_false_dest, false_e);
+	  }
+      }
+}
+
 /* Compute and return the hash value for nary operation VBO1.  */
 
 static hashval_t
@@ -4155,21 +4515,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)
@@ -4182,6 +4529,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, true);
+      val_equiv_insert (ops[1], ops[0], pred_e->dest, 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;
@@ -4194,26 +4547,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.  */
 
@@ -6863,6 +7196,8 @@ 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;
@@ -7241,11 +7576,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;
@@ -7264,6 +7599,21 @@ process_bb (rpo_elim &avail, basic_block bb,
 			print_gimple_stmt (dump_file, last, TDF_SLIM);
 		      }
 		  }
+		if (!val && iterate)
+		  {
+		    // Try to find equivalences in val_equiv_hash and search
+		    // again.
+		    val
+		      = find_predicated_value_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);
@@ -7316,6 +7666,17 @@ 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;
 	  }
@@ -7437,6 +7798,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;
 };
 
@@ -7475,6 +7837,18 @@ 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,
+						  last_inserted_equiv->hashcode,
+						  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.  */
@@ -7590,6 +7964,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);
@@ -7600,6 +7975,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;
 
@@ -7693,6 +8069,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;
 	  }

^ permalink raw reply	[flat|nested] 11+ messages in thread
end of thread, other threads:[~2021-07-28  9:39 UTC | newest]

Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-06-24  9:54 [PATCH] tree-optimization/101186 - extend FRE with "equivalence map" for condition prediction Di Zhao
2021-06-24 12:29 ` Richard Biener
2021-06-24 13:25   ` Andrew MacLeod
2021-06-24 15:01     ` Andrew MacLeod
2021-06-25  7:38       ` Richard Biener
2021-06-27 15:46         ` Aldy Hernandez
2021-06-28  8:12           ` Richard Biener
2021-06-28 13:15           ` Andrew MacLeod
2021-06-29 10:54             ` Richard Biener
2021-07-18 19:25   ` Di Zhao OS
2021-07-28  9:38     ` Richard Biener

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).