Patchwork [ping,1,of,2] Add value range info to SSA_NAME for zero sign extension elimination in RTL

login
register
mail settings
Submitter Kugan
Date Sept. 13, 2013, 5:11 a.m.
Message ID <52329E95.1080501@linaro.org>
Download mbox | patch
Permalink /patch/274656/
State New
Headers show

Comments

Kugan - Sept. 13, 2013, 5:11 a.m.
Here is the modified patch that addresses the comments form Richard and 
Jakub.

This also includes:
1. Added TDF_RANGE to dump range_info
2. Moved enum value_range_type to tree.h (Is this the right place?)

Bootstrapped and regtested for x86_64-unknown-linux-gnu and arm-none 
linux-gnueabi.

Is this Ok,

Thanks,
Kugan

+2013-09-12  Kugan Vivekanandarajah  <kuganv@linaro.org>
+
+	* cfgexpand.c (maybe_dump_rtl_for_gimple_stmt) : Add range to dump.
+	* gimple-pretty-print.c (print_double_int) : New function.
+	* gimple-pretty-print.c (dump_gimple_phi) : Dump range info.
+	* (pp_gimple_stmt_1) : Likewise.
+	* tree-ssa-alias.c (dump_alias_info) : Check pointer type.
+	* tree-ssa-copy.c (fini_copy_prop) : Check pointer type and copy
+	range info.
+	* tree-ssanames.c (make_ssa_name_fn) : Check pointer type in
+	initialize.
+	* (set_range_info) : New function.
+	* (get_range_info) : Likewise.
+	* (duplicate_ssa_name_range_info) : Likewise.
+	* (duplicate_ssa_name_fn) : Check pointer type and call correct
+	duplicate function.
+	* tree-vrp.c (vrp_finalize): Call set_range_info to upddate
+	value range of SSA_NAMEs.
+	* tree.h (SSA_NAME_PTR_INFO) : changed to access via union
+	* tree.h (SSA_NAME_RANGE_INFO) : New macro
+

Patch

diff --git a/gcc/cfgexpand.c b/gcc/cfgexpand.c
index a7d9170..f3fdd49 100644
--- a/gcc/cfgexpand.c
+++ b/gcc/cfgexpand.c
@@ -1820,7 +1820,7 @@  maybe_dump_rtl_for_gimple_stmt (gimple stmt, rtx since)
     {
       fprintf (dump_file, "\n;; ");
       print_gimple_stmt (dump_file, stmt, 0,
-			 TDF_SLIM | (dump_flags & TDF_LINENO));
+			 TDF_SLIM | TDF_RANGE | (dump_flags & TDF_LINENO));
       fprintf (dump_file, "\n");
 
       print_rtl (dump_file, since ? NEXT_INSN (since) : since);
diff --git a/gcc/dumpfile.h b/gcc/dumpfile.h
index 77f5de6..354dd92 100644
--- a/gcc/dumpfile.h
+++ b/gcc/dumpfile.h
@@ -82,9 +82,10 @@  enum tree_dump_index
 #define TDF_CSELIB	(1 << 23)	/* Dump cselib details.  */
 #define TDF_SCEV	(1 << 24)	/* Dump SCEV details.  */
 #define TDF_COMMENT	(1 << 25)	/* Dump lines with prefix ";;"  */
-#define MSG_OPTIMIZED_LOCATIONS  (1 << 26)  /* -fopt-info optimized sources */
-#define MSG_MISSED_OPTIMIZATION  (1 << 27)  /* missed opportunities */
-#define MSG_NOTE                 (1 << 28)  /* general optimization info */
+#define TDF_RANGE       (1 << 26)       /* Dump range information.  */ 
+#define MSG_OPTIMIZED_LOCATIONS  (1 << 27)  /* -fopt-info optimized sources */
+#define MSG_MISSED_OPTIMIZATION  (1 << 28)  /* missed opportunities */
+#define MSG_NOTE                 (1 << 29)  /* general optimization info */
 #define MSG_ALL         (MSG_OPTIMIZED_LOCATIONS | MSG_MISSED_OPTIMIZATION \
                          | MSG_NOTE)
 
diff --git a/gcc/gimple-pretty-print.c b/gcc/gimple-pretty-print.c
index 1d40680..af1a13d 100644
--- a/gcc/gimple-pretty-print.c
+++ b/gcc/gimple-pretty-print.c
@@ -1581,6 +1581,24 @@  dump_gimple_asm (pretty_printer *buffer, gimple gs, int spc, int flags)
     }
 }
 
+/* Dumps double_int CST to BUFFER.  */
+
+static void
+print_double_int (pretty_printer *buffer, double_int cst)
+{
+  tree node = double_int_to_tree (integer_type_node, cst);
+  if (TREE_INT_CST_HIGH (node) == 0)
+    pp_printf (buffer, HOST_WIDE_INT_PRINT_UNSIGNED, TREE_INT_CST_LOW (node));
+  else if (TREE_INT_CST_HIGH (node) == -1
+           && TREE_INT_CST_LOW (node) != 0)
+    pp_printf (buffer, "-" HOST_WIDE_INT_PRINT_UNSIGNED,
+               -TREE_INT_CST_LOW (node));
+  else
+    pp_printf (buffer, "0x%" HOST_LONG_FORMAT "x%" HOST_LONG_FORMAT "x",
+               (unsigned HOST_WIDE_INT) TREE_INT_CST_HIGH (node),
+               (unsigned HOST_WIDE_INT) TREE_INT_CST_LOW (node));
+}
+
 
 /* Dump a PHI node PHI.  BUFFER, SPC and FLAGS are as in pp_gimple_stmt_1.
    The caller is responsible for calling pp_flush on BUFFER to finalize
@@ -1609,6 +1627,27 @@  dump_gimple_phi (pretty_printer *buffer, gimple phi, int spc, int flags)
       pp_string (buffer, "# ");
     }
 
+  if ((flags & TDF_RANGE)
+      && !POINTER_TYPE_P (TREE_TYPE (lhs))
+      && SSA_NAME_RANGE_INFO (lhs))
+    {
+      double_int min, max;
+      value_range_type range_type;
+      get_range_info (lhs, min, max, range_type);
+      if (range_type == VR_VARYING)
+        pp_printf (buffer, "# RANGE  VR_VARYING");
+      else if (range_type == VR_RANGE || range_type == VR_ANTI_RANGE)
+      {
+        pp_printf (buffer, "# RANGE ");
+        pp_printf (buffer, "%s[", range_type == VR_RANGE ? "" : "~");
+        print_double_int (buffer, min);
+        pp_printf (buffer, ", ");
+        print_double_int (buffer, max);
+        pp_printf (buffer, "]");
+        newline_and_indent (buffer, spc);
+      }
+    }
+
   if (flags & TDF_RAW)
       dump_gimple_fmt (buffer, spc, flags, "%G <%T, ", phi,
                        gimple_phi_result (phi));
@@ -1911,6 +1950,32 @@  pp_gimple_stmt_1 (pretty_printer *buffer, gimple gs, int spc, int flags)
 	}
     }
 
+  if ((flags & TDF_RANGE)
+      && gimple_has_lhs (gs))
+    {
+      tree lhs = gimple_get_lhs (gs);
+      if ((TREE_CODE (lhs) == SSA_NAME)
+          && !POINTER_TYPE_P (TREE_TYPE (lhs))
+          && SSA_NAME_RANGE_INFO (lhs))
+        {
+          double_int min, max;
+          value_range_type range_type;
+          get_range_info (lhs, min, max, range_type);
+          if (range_type == VR_VARYING)
+            pp_printf (buffer, "# RANGE  VR_VARYING");
+          else if (range_type == VR_RANGE || range_type == VR_ANTI_RANGE)
+            {
+              pp_printf (buffer, "# RANGE ");
+              pp_printf (buffer, "%s[", range_type == VR_RANGE ? "" : "~");
+              print_double_int (buffer, min);
+              pp_printf (buffer, ", ");
+              print_double_int (buffer, max);
+              pp_printf (buffer, "]");
+              newline_and_indent (buffer, spc);
+            }
+        }
+    }
+
   switch (gimple_code (gs))
     {
     case GIMPLE_ASM:
diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h
index caa8d74..7006eab 100644
--- a/gcc/tree-flow.h
+++ b/gcc/tree-flow.h
@@ -147,6 +147,15 @@  struct GTY(()) ptr_info_def
   unsigned int misalign;
 };
 
+/* Value range information for SSA_NAMEs representing non-pointer variables.  */
+
+struct GTY (()) range_info_def {
+  /* Minmum for value range.  */
+  double_int min;
+  /* Maximum for value range.  */
+  double_int max;
+};
+
 
 /* It is advantageous to avoid things like life analysis for variables which
    do not need PHI nodes.  This enum describes whether or not a particular
@@ -526,6 +535,7 @@  extern tree make_ssa_name_fn (struct function *, tree, gimple);
 extern tree copy_ssa_name_fn (struct function *, tree, gimple);
 extern tree duplicate_ssa_name_fn (struct function *, tree, gimple);
 extern void duplicate_ssa_name_ptr_info (tree, struct ptr_info_def *);
+extern void duplicate_ssa_name_range_info (tree, struct range_info_def *);
 extern void release_ssa_name (tree);
 extern void release_defs (gimple);
 extern void replace_ssa_name_symbol (tree, tree);
diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c
index 2ecd139..8ccecb5 100644
--- a/gcc/tree-ssa-alias.c
+++ b/gcc/tree-ssa-alias.c
@@ -404,6 +404,7 @@  dump_alias_info (FILE *file)
       struct ptr_info_def *pi;
 
       if (ptr == NULL_TREE
+          || !POINTER_TYPE_P (TREE_TYPE (ptr))
 	  || SSA_NAME_IN_FREE_LIST (ptr))
 	continue;
 
diff --git a/gcc/tree-ssa-copy.c b/gcc/tree-ssa-copy.c
index 75ab54a..23f07e9 100644
--- a/gcc/tree-ssa-copy.c
+++ b/gcc/tree-ssa-copy.c
@@ -761,11 +761,19 @@  fini_copy_prop (void)
 	 of the representative to the first solution we find if
 	 it doesn't have one already.  */
       if (copy_of[i].value != var
-	  && TREE_CODE (copy_of[i].value) == SSA_NAME
-	  && POINTER_TYPE_P (TREE_TYPE (var))
-	  && SSA_NAME_PTR_INFO (var)
-	  && !SSA_NAME_PTR_INFO (copy_of[i].value))
-	duplicate_ssa_name_ptr_info (copy_of[i].value, SSA_NAME_PTR_INFO (var));
+          && TREE_CODE (copy_of[i].value) == SSA_NAME)
+        {
+          if (POINTER_TYPE_P (TREE_TYPE (var))
+              && SSA_NAME_PTR_INFO (var)
+              && !SSA_NAME_PTR_INFO (copy_of[i].value))
+            duplicate_ssa_name_ptr_info (copy_of[i].value,
+                                         SSA_NAME_PTR_INFO (var));
+          else if (!POINTER_TYPE_P (TREE_TYPE (var))
+                   && SSA_NAME_RANGE_INFO (var)
+                   && !SSA_NAME_RANGE_INFO (copy_of[i].value))
+            duplicate_ssa_name_range_info (copy_of[i].value,
+                                           SSA_NAME_RANGE_INFO (var));
+        }
     }
 
   /* Don't do DCE if SCEV is initialized.  It would destroy the scev cache.  */
diff --git a/gcc/tree-ssanames.c b/gcc/tree-ssanames.c
index a6af3da..6eb6271 100644
--- a/gcc/tree-ssanames.c
+++ b/gcc/tree-ssanames.c
@@ -151,7 +151,11 @@  make_ssa_name_fn (struct function *fn, tree var, gimple stmt)
       SET_SSA_NAME_VAR_OR_IDENTIFIER (t, var);
     }
   SSA_NAME_DEF_STMT (t) = stmt;
-  SSA_NAME_PTR_INFO (t) = NULL;
+  if (POINTER_TYPE_P (TREE_TYPE (t)))
+    SSA_NAME_PTR_INFO (t) = NULL;
+  else
+    SSA_NAME_RANGE_INFO (t) = NULL;
+
   SSA_NAME_IN_FREE_LIST (t) = 0;
   SSA_NAME_IS_DEFAULT_DEF (t) = 0;
   imm = &(SSA_NAME_IMM_USE_NODE (t));
@@ -163,6 +167,64 @@  make_ssa_name_fn (struct function *fn, tree var, gimple stmt)
   return t;
 }
 
+/* Store range information MIN, and MAX to tree ssa_name NAME.  */
+
+void
+set_range_info (tree name, double_int min, double_int max)
+{
+  gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
+  gcc_assert (TREE_CODE (name) == SSA_NAME);
+  range_info_def *ri = SSA_NAME_RANGE_INFO (name);
+
+  /* Allocate if not available.  */
+  if (ri == NULL)
+    {
+      ri = ggc_alloc_cleared_range_info_def ();
+      SSA_NAME_RANGE_INFO (name) = ri;
+    }
+
+  /* Set the values.  */
+  ri->min = min;
+  ri->max = max;
+}
+
+
+/* Get range information MIN, MAX and RANGE_TYPE
+   corresponding to tree ssa_name NAME.  */
+
+void
+get_range_info (tree name, double_int &min, double_int &max,
+                enum value_range_type &range_type)
+{
+  gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
+  gcc_assert (TREE_CODE (name) == SSA_NAME);
+  range_info_def *ri = SSA_NAME_RANGE_INFO (name);
+
+  /* Return VR_VARYING for SSA_NAMEs with NULL RANGE_INFO or SSA_NAMEs
+     with integral types width > 2 * HOST_BITS_PER_WIDE_INT precision.  */
+  if (!ri || (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (name)))
+              > 2 * HOST_BITS_PER_WIDE_INT))
+    {
+      range_type = VR_VARYING;
+      return;
+    }
+
+  /* If min > max, it is  VR_ANTI_RANGE.  */
+  if (ri->min.scmp (ri->max) == 1)
+    {
+      /* VR_ANTI_RANGE ~[min, max] is encoded as [max + 1, min - 1].  */
+      range_type = VR_ANTI_RANGE;
+      min = ri->max + double_int_one;
+      max = ri->min - double_int_one;
+    }
+  else
+  {
+    /* Otherwise (when min <= max), it is  VR_RANGE.  */
+    range_type = VR_RANGE;
+    min = ri->min;
+    max = ri->max;
+  }
+}
 
 /* We no longer need the SSA_NAME expression VAR, release it so that
    it may be reused.
@@ -359,6 +421,26 @@  duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info)
   SSA_NAME_PTR_INFO (name) = new_ptr_info;
 }
 
+/* Creates a duplicate of the range_info_def at RANGE_INFO for use by
+   the SSA name NAME.  */
+void
+duplicate_ssa_name_range_info (tree name, struct range_info_def *range_info)
+{
+  struct range_info_def *new_range_info;
+
+  gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
+  gcc_assert (!SSA_NAME_RANGE_INFO (name));
+
+  if (!range_info)
+    return;
+
+  new_range_info = ggc_alloc_range_info_def ();
+  *new_range_info = *range_info;
+
+  SSA_NAME_RANGE_INFO (name) = new_range_info;
+}
+
+
 
 /* Creates a duplicate of a ssa name NAME tobe defined by statement STMT
    in function FN.  */
@@ -367,10 +449,20 @@  tree
 duplicate_ssa_name_fn (struct function *fn, tree name, gimple stmt)
 {
   tree new_name = copy_ssa_name_fn (fn, name, stmt);
-  struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name);
+  if (POINTER_TYPE_P (TREE_TYPE (name)))
+    {
+      struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name);
 
-  if (old_ptr_info)
-    duplicate_ssa_name_ptr_info (new_name, old_ptr_info);
+      if (old_ptr_info)
+        duplicate_ssa_name_ptr_info (new_name, old_ptr_info);
+    }
+  else
+    {
+      struct range_info_def *old_range_info = SSA_NAME_RANGE_INFO (name);
+
+      if (old_range_info)
+        duplicate_ssa_name_range_info (new_name, old_range_info);
+    }
 
   return new_name;
 }
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index ff82591..7d539f7 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -41,9 +41,6 @@  along with GCC; see the file COPYING3.  If not see
 #include "optabs.h"
 
 
-/* Type of value ranges.  See value_range_d for a description of these
-   types.  */
-enum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING };
 
 /* Range of values that can be associated with an SSA_NAME after VRP
    has executed.  */
@@ -9436,6 +9433,39 @@  vrp_finalize (void)
      the datastructures built by VRP.  */
   identify_jump_threads ();
 
+  /* Set value range to non pointer SSA_NAMEs.  */
+  for (i  = 0; i < num_vr_values; i++)
+   if (vr_value[i])
+    {
+      tree name = ssa_name (i);
+
+      if (POINTER_TYPE_P (TREE_TYPE (name))
+          || (vr_value[i]->type == VR_VARYING)
+          || (vr_value[i]->type == VR_UNDEFINED))
+        continue;
+
+      if ((TREE_CODE (vr_value[i]->min) == INTEGER_CST)
+          && (TREE_CODE (vr_value[i]->max) == INTEGER_CST))
+        {
+          if (vr_value[i]->type == VR_RANGE)
+            set_range_info (name,
+                            tree_to_double_int (vr_value[i]->min),
+                            tree_to_double_int (vr_value[i]->max));
+          else if (vr_value[i]->type == VR_ANTI_RANGE)
+            {
+              /* VR_ANTI_RANGE ~[min, max] is encoded compactly as
+                 [max + 1, min - 1] without additional attributes.
+                 When min value > max value, we know that it is
+                 VR_ANTI_RANGE; it is VR_RANGE othewise.  */
+              set_range_info (name,
+                              tree_to_double_int (vr_value[i]->max)
+                              + double_int_one,
+                              tree_to_double_int (vr_value[i]->min)
+                              - double_int_one);
+            }
+        }
+    }
+
   /* Free allocated memory.  */
   for (i = 0; i < num_vr_values; i++)
     if (vr_value[i])
diff --git a/gcc/tree.h b/gcc/tree.h
index 94f112f..6383de8 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -1950,10 +1950,26 @@  struct GTY(()) tree_exp {
 
 /* Attributes for SSA_NAMEs for pointer-type variables.  */
 #define SSA_NAME_PTR_INFO(N) \
-    SSA_NAME_CHECK (N)->ssa_name.ptr_info
+   SSA_NAME_CHECK (N)->ssa_name.info.ptr_info
+
+/* Value range info Attributes for SSA_NAMEs of non pointer-type variables.  */
+#define SSA_NAME_RANGE_INFO(N) \
+    SSA_NAME_CHECK (N)->ssa_name.info.range_info
+
+
+/* Type of value ranges.  See value_range_d In tree-vrp.c for a
+   description of these types.  */
+enum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING };
+
+/* Sets the value range to SSA.  */
+void set_range_info (tree ssa, double_int min, double_int max);
+/* Gets the value range from SSA.  */
+void get_range_info (tree name, double_int &min, double_int &max,
+                     enum value_range_type &range_type);
 
 /* Defined in tree-flow.h.  */
 struct ptr_info_def;
+struct range_info_def;
 
 /* Immediate use linking structure.  This structure is used for maintaining
    a doubly linked list of uses of an SSA_NAME.  */
@@ -1981,8 +1997,14 @@  struct GTY(()) tree_ssa_name {
   /* Statement that defines this SSA name.  */
   gimple def_stmt;
 
-  /* Pointer attributes used for alias analysis.  */
-  struct ptr_info_def *ptr_info;
+  /* Value range information.  */
+  union ssa_name_info_type {
+    /* Pointer attributes used for alias analysis.  */
+    struct GTY ((tag ("0"))) ptr_info_def *ptr_info;
+    /* Value range attributes used for zero/sign extension elimination.  */
+    struct GTY ((tag ("1"))) range_info_def *range_info;
+  } GTY ((desc ("%1.typed.type ?" \
+                "!POINTER_TYPE_P (TREE_TYPE ((tree)&%1)) : 2"))) info;
 
   /* Immediate uses list for this SSA_NAME.  */
   struct ssa_use_operand_d imm_uses;