diff mbox

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

Message ID 51ABFBDB.6040205@linaro.org
State Accepted
Headers show

Commit Message

Kugan Vivekanandarajah June 3, 2013, 2:13 a.m. UTC
Hi,

This patch adds value range information to tree SSA_NAME during Value 
Range Propagation (VRP) pass  in preparation to removes some of the 
redundant sign/zero extensions during RTL expansion.

This is based on the original patch posted in 
http://gcc.gnu.org/ml/gcc-patches/2013-05/msg00610.html and addresses 
the review comments of  Richard Biener.

Tested  on X86_64 and ARM.

I would like review comments on this.

Thanks,
Kugan


+2013-06-03  Kugan Vivekanandarajah  <kuganv@linaro.org>
+
+	* gcc/gcc/tree-flow.h: Declared structure range_info_def and function
+	definition for mark_range_info_unknown.
+	* gcc/tree-ssa-alias.c (dump_alias_info) : Check pointer type
+	* gcc/tree-ssanames.c (make_ssa_name_fn) : Check pointer type in
+	initialize.
+	* (mark_range_info_unknown) : New function.
+	* (duplicate_ssa_name_range_info) : Likewise.
+	* (duplicate_ssa_name_fn) : Check pointer type and call correct
+	duplicate function.
+	* gcc/tree-vrp.c (extract_exp_value_range): New function.
+	* (simplify_stmt_using_ranges): Call extract_exp_value_range and
+	tree_ssa_set_value_range.
+	* gcc/tree.c (tree_ssa_set_value_range): New function.
+	* gcc/tree.h (SSA_NAME_PTR_INFO) : changed to access via union
+	* gcc/tree.h (SSA_NAME_RANGE_INFO) : New macro
+
diff mbox

Patch

diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h
index 24fcfbf..dd4e2f5 100644
--- a/gcc/tree-flow.h
+++ b/gcc/tree-flow.h
@@ -147,6 +147,19 @@  struct GTY(()) ptr_info_def
   unsigned int misalign;
 };
 
+/* Value range information for SSA_NAMEs representing non-pointer variables.  */
+
+struct GTY (()) range_info_def {
+  /* Set to true if VR_RANGE and false if VR_ANTI_RANGE.  */
+  bool vr_range;
+  /* Minmum for value range.  */
+  double_int min;
+  /* Maximum for value range.  */
+  double_int max;
+  /* Set to true if range is valid.  */
+  bool valid;
+};
+
 
 /* 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
@@ -532,6 +545,7 @@  extern void replace_ssa_name_symbol (tree, tree);
 extern bool get_ptr_info_alignment (struct ptr_info_def *, unsigned int *,
 				    unsigned int *);
 extern void mark_ptr_info_alignment_unknown (struct ptr_info_def *);
+extern void mark_range_info_unknown (struct range_info_def *);
 extern void set_ptr_info_alignment (struct ptr_info_def *, unsigned int,
 				    unsigned int);
 extern void adjust_ptr_info_misalignment (struct ptr_info_def *,
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-ssanames.c b/gcc/tree-ssanames.c
index 0a405ce..420ae00 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));
@@ -266,6 +270,14 @@  mark_ptr_info_alignment_unknown (struct ptr_info_def *pi)
   pi->misalign = 0;
 }
 
+/* Set the range described by RI has invalid values.  */
+
+void
+mark_range_info_unknown (struct range_info_def *ri)
+{
+  ri->valid = false;
+}
+
 /* Store the the power-of-two byte alignment and the deviation from that
    alignment of pointer described by PI to ALIOGN and MISALIGN
    respectively.  */
@@ -359,6 +371,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 +399,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);
+    }
+  else
+    {
+      struct range_info_def *old_range_info = SSA_NAME_RANGE_INFO (name);
 
-  if (old_ptr_info)
-    duplicate_ssa_name_ptr_info (new_name, old_ptr_info);
+      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 ec7ef8f..36ec5fa 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -8950,6 +8950,62 @@  simplify_float_conversion_using_ranges (gimple_stmt_iterator *gsi, gimple stmt)
   return true;
 }
 
+/* Extract the value range of assigned exprassion for GIMPLE_ASSIGN stmt.
+   If the extracted value range is valid, return true else return
+   false.  */
+static bool
+extract_exp_value_range (gimple stmt, value_range_t *vr)
+{
+  gcc_assert (is_gimple_assign (stmt));
+  tree rhs1 = gimple_assign_rhs1 (stmt);
+  tree lhs = gimple_assign_lhs (stmt);
+  enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
+
+  /* Skip if the lhs is not integeral.  */
+  if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+      || CONSTANT_CLASS_P (lhs))
+    return false;
+
+  if (TREE_CODE_CLASS (rhs_code) == tcc_unary)
+    {
+      /* Get the value range for the expression.  */
+      if ((rhs_code == NOP_EXPR || rhs_code == CONVERT_EXPR)
+          && (TREE_CODE (rhs1) == SSA_NAME))
+        {
+          value_range_t *temp =  get_value_range (rhs1);
+          *vr = *temp;
+        }
+      else
+        extract_range_from_unary_expr (vr,
+                                     gimple_assign_rhs_code (stmt),
+                                     TREE_TYPE (rhs1), rhs1);
+    }
+    /* Process binary assign stmt.  */
+  else if (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt))
+           == tcc_binary)
+    {
+      tree rhs2 = gimple_assign_rhs2 (stmt);
+      gcc_assert (rhs1);
+      gcc_assert (rhs2);
+
+      /* Get the value range for the expression.  */
+      extract_range_from_binary_expr (vr,
+                                    gimple_assign_rhs_code (stmt),
+                                    TREE_TYPE (rhs1), rhs1, rhs2);
+    }
+
+    /* Is the laue range valid.  */
+    if ((vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
+        && !is_overflow_infinity (vr->min)
+        && !is_overflow_infinity (vr->max)
+        && (TREE_CODE (vr->min) == INTEGER_CST)
+        && (TREE_CODE (vr->max) == INTEGER_CST))
+      return true;
+    else
+      return false;
+}
+
+
 /* Simplify STMT using ranges if possible.  */
 
 static bool
@@ -8960,6 +9016,23 @@  simplify_stmt_using_ranges (gimple_stmt_iterator *gsi)
     {
       enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
       tree rhs1 = gimple_assign_rhs1 (stmt);
+      tree lhs = gimple_assign_lhs (stmt);
+
+      /* Set value range information for ssa.  */
+      if (!POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt)))
+          && (TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME)
+          && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt)))
+          && !SSA_NAME_RANGE_INFO (lhs))
+        {
+          value_range_t vr = VR_INITIALIZER;
+
+          /* If value range is valid, set that.  */
+          if (extract_exp_value_range (stmt, &vr))
+            tree_ssa_set_value_range (lhs,
+                                      tree_to_double_int (vr.min),
+                                      tree_to_double_int (vr.max),
+                                      vr.type == VR_RANGE);
+        }
 
       switch (rhs_code)
 	{
diff --git a/gcc/tree.c b/gcc/tree.c
index 6c71025..bf8c816 100644
--- a/gcc/tree.c
+++ b/gcc/tree.c
@@ -270,6 +270,31 @@  const char * const omp_clause_code_name[] =
 };
 
 
+/* Set zero/sign extension redundant for ssa def stmt.  */
+
+void
+tree_ssa_set_value_range (tree ssa, double_int min,
+                          double_int max, bool vr_range)
+{
+  gcc_assert (!POINTER_TYPE_P (TREE_TYPE (ssa)));
+  gcc_assert (TREE_CODE (ssa) == SSA_NAME);
+  range_info_def *ri = SSA_NAME_RANGE_INFO (ssa);
+
+  /* Allocate if not available.  */
+  if (ri == NULL)
+    {
+      ri = ggc_alloc_cleared_range_info_def ();
+      mark_range_info_unknown (ri);
+      SSA_NAME_RANGE_INFO (ssa) = ri;
+    }
+
+  /* Set the values.  */
+  ri->valid = true;
+  ri->min = min;
+  ri->max = max;
+  ri->vr_range = vr_range;
+}
+
 /* Return the tree node structure used by tree code CODE.  */
 
 static inline enum tree_node_structure_enum
diff --git a/gcc/tree.h b/gcc/tree.h
index 1d2b252..7629de8 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -1950,10 +1950,19 @@  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.vrp.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.vrp.range_info
+
+/* Sets the value range extreacted from VRP into ssa.  */
+void tree_ssa_set_value_range (tree ssa, double_int min,
+                               double_int max, bool vr_range);
 
 /* 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.  */
@@ -1969,6 +1978,12 @@  typedef struct GTY(()) ssa_use_operand_d {
   tree *GTY((skip(""))) use;
 } ssa_use_operand_t;
 
+
+/* The garbage collector needs to know the interpretation of the
+   value range info in the tree_ssa_name.  */
+#define TREE_SSA_PTR_INFO   (0)
+#define TREE_SSA_RANGE_INFO (1)
+
 /* Return the immediate_use information for an SSA_NAME. */
 #define SSA_NAME_IMM_USE_NODE(NODE) SSA_NAME_CHECK (NODE)->ssa_name.imm_uses
 
@@ -1981,8 +1996,13 @@  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 vrp_info_type {
+    /* Pointer attributes used for alias analysis.  */
+    struct GTY ((tag ("TREE_SSA_PTR_INFO"))) ptr_info_def *ptr_info;
+    /* Value range attributes used for zero/sign extension elimination.  */
+    struct GTY ((tag ("TREE_SSA_RANGE_INFO"))) range_info_def *range_info;
+  } GTY ((desc ("%1.def_stmt && !POINTER_TYPE_P (TREE_TYPE ((tree)&%1))"))) vrp;
 
   /* Immediate uses list for this SSA_NAME.  */
   struct ssa_use_operand_d imm_uses;