Add recomputation to outgoing_edge_range.

Message ID 7e0fac9c-089b-6ae3-3c76-86061c999ef9@redhat.com
State New
Headers show
Series
  • Add recomputation to outgoing_edge_range.
Related show

Commit Message

Andrew Pinski via Gcc-patches June 17, 2021, 12:13 a.m.
This change adds first degree recomputation to the gori engine.

"Exports" are any ssa_name which is in the definition chain of one of 
the SSA_NAMES on the condition.

    a_2 = b_3 +6
    if (a_2 > 10 && a_2 <20)    // a_2 has the range [11, 19]

The condition tells us that the range of a_2 is [11, 19] on the true 
edge, and since b_3 is used in the definition chain of a_2, the 
gori_compute engine can solve the equation    [11, 19] = b_3 + 6    to 
deduce that b_3 has a range of [5, 13] on the true range.

These export chains are built for each basic block with a condition, and 
in this block, a_2 and b_3 are in the export list.   IF an SSA_NAME is 
not in the export list,we cannot calculate a range for it.    If we 
tweak to the original case:

    x_5 = b_3 * 2
    a_2 = b_3 +6
    if (a_2 > 10 && a_2 <20)    // a_2 has the range [11, 19]

Following just definition chains, there is no use/def relationship 
between x_5 and a_2.   Using the export list, we know that a_2 and b_3 
are both exports from this block. The new GORI rework also contains 
dependency summaries as well.  Each statement has up to 2 "direct 
dependencies" cached.  These are ssa_names which occur in the statement 
and could change it value.

This patch adds the ability to recompute values by checking if one of 
these direct dependants ise an export, and recomputing the original 
statement using the values as they appear on this edge.

In this latter example, b_3 is a direct dependent for x_5's statement,  
and x_5 is therefore determined to be recomputable. Using 
fold_using_range we ask for the range of x_5 to be calculated as if it 
were on that edge.  It can determine that b_3 is [5, 13] on the edge and 
will now calculate x_5 as [10, 26] on the edge

The nature of SSA makes this a safe operation (assuming the statement 
has no side effects).  It also removes any need for x_5 = b_3 * 2 to 
occur in this block.. it can be anywhere in the IL and this still works.

This is integrated directly in outgoing_edge_range_p and picks up quite 
a few new opportunities.

Bootstraps on x86_64-pc-linux-gnu with no regressions.  Pushed.

Andrew

Patch

commit 786188e8b8cab47cb31177c6f4ab1a1578a607c3
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Wed Jun 16 18:08:03 2021 -0400

    Add recomputation to outgoing_edge_range.
    
    The gori engine can calculate outgoing ranges for exported values.  This
    change allows 1st degree recomputation.  If a name is not exported from a
    block, but one of the ssa_names used directly in computing it is, then
    we can recompute the ssa_name on the edge using the edge values for its
    operands.
    
            * gimple-range-gori.cc (gori_compute::has_edge_range_p): Check with
            may_recompute_p.
            (gori_compute::may_recompute_p): New.
            (gori_compute::outgoing_edge_range_p): Perform recomputations.
            * gimple-range-gori.h (class gori_compute): Add prototype.

diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc
index 09dcd694319..647f4964769 100644
--- a/gcc/gimple-range-gori.cc
+++ b/gcc/gimple-range-gori.cc
@@ -972,16 +972,18 @@  gori_compute::compute_operand1_and_operand2_range (irange &r,
   r.intersect (op_range);
   return true;
 }
-// Return TRUE if a range can be calcalated for NAME on edge E.
+// Return TRUE if a range can be calculated or recomputed for NAME on edge E.
 
 bool
 gori_compute::has_edge_range_p (tree name, edge e)
 {
-  // If no edge is specified, check if NAME is an export on any edge.
-  if (!e)
-    return is_export_p (name);
+  // Check if NAME is an export or can be recomputed.
+  if (e)
+    return is_export_p (name, e->src) || may_recompute_p (name, e);
 
-  return is_export_p (name, e->src);
+  // If no edge is specified, check if NAME can have a range calculated
+  // on any edge.
+  return is_export_p (name) || may_recompute_p (name);
 }
 
 // Dump what is known to GORI computes to listing file F.
@@ -992,6 +994,32 @@  gori_compute::dump (FILE *f)
   gori_map::dump (f);
 }
 
+// Return TRUE if NAME can be recomputed on edge E.  If any direct dependant
+// is exported on edge E, it may change the computed value of NAME.
+
+bool
+gori_compute::may_recompute_p (tree name, edge e)
+{
+  tree dep1 = depend1 (name);
+  tree dep2 = depend2 (name);
+
+  // If the first dependency is not set, there is no recompuation.
+  if (!dep1)
+    return false;
+
+  // Don't recalculate PHIs or statements with side_effects.
+  gimple *s = SSA_NAME_DEF_STMT (name);
+  if (is_a<gphi *> (s) || gimple_has_side_effects (s))
+    return false;
+
+  // If edge is specified, check if NAME can be recalculated on that edge.
+  if (e)
+    return ((is_export_p (dep1, e->src))
+	    || (dep2 && is_export_p (dep2, e->src)));
+
+  return (is_export_p (dep1)) || (dep2 && is_export_p (dep2));
+}
+
 // Calculate a range on edge E and return it in R.  Try to evaluate a
 // range for NAME on this edge.  Return FALSE if this is either not a
 // control edge or NAME is not defined by this edge.
@@ -1026,6 +1054,27 @@  gori_compute::outgoing_edge_range_p (irange &r, edge e, tree name,
 	  return true;
 	}
     }
+  // If NAME isn't exported, check if it can be recomputed.
+  else if (may_recompute_p (name, e))
+    {
+      gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "recomputation attempt on edge %d->%d for ",
+		   e->src->index, e->dest->index);
+	  print_generic_expr (dump_file, name, TDF_SLIM);
+	}
+      // Simply calculate DEF_STMT on edge E usng the range query Q.
+      fold_range (r, def_stmt, e, &q);
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, " : Calculated :");
+	  r.dump (dump_file);
+	  fputc ('\n', dump_file);
+	}
+      return true;
+    }
   return false;
 }
 
diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h
index 06f3b791359..6f187db08cb 100644
--- a/gcc/gimple-range-gori.h
+++ b/gcc/gimple-range-gori.h
@@ -157,6 +157,7 @@  public:
   bool has_edge_range_p (tree name, edge e = NULL);
   void dump (FILE *f);
 private:
+  bool may_recompute_p (tree name, edge e = NULL);
   bool compute_operand_range (irange &r, gimple *stmt, const irange &lhs,
 			      tree name, class fur_source &src);
   bool compute_operand_range_switch (irange &r, gswitch *s, const irange &lhs,