Patchwork [PING^2,2,of,2] RTL expansion for zero sign extension elimination with VRP

login
register
mail settings
Submitter Kugan
Date Dec. 6, 2013, 4:24 a.m.
Message ID <52A15162.40302@linaro.org>
Download mbox | patch
Permalink /patch/297567/
State New
Headers show

Comments

Kugan - Dec. 6, 2013, 4:24 a.m.
>>>>   tem = (char) 255 + (char) 1;
>>
>> tem is always of type 'char' in GIMPLE (even if later promoted
>> via PROMOTE_MODE) the value-range is a 'char' value-range and thus
>> never will exceed [CHAR_MIN, CHAR_MAX].  The only way you can
>> use that directly is if you can rely on undefined behavior
>> happening for signed overflow - but if you argue that way you
>> can simply _always_ drop the (sext:SI (subreg:QI part and you
>> do not need value ranges for this.  For unsigned operations
>> for example [250, 254] + [8, 10] will simply wrap to [3, 7]
>> (if I got the math correct) which is inside your [CHAR_MIN + 1,
>> CHAR_MAX - 1] but if performed in SImode you can get 259 and
>> thus clearly you cannot drop the (zext:SI (subreg:QI parts.
>> The same applies to signed types if you do not want to rely
>> on signed overflow being undefined of course.
>>
> 
> Thanks for the explanation. I now get it and I will rework the patch.
> 

I have attempted to implement what Richard suggested. If you think this
is what you want, I will go ahead and implement the missing gimple
binary statements.

Thanks again.
Kugan

Patch

diff --git a/gcc/cfgexpand.c b/gcc/cfgexpand.c
index 98983f4..60ce54b 100644
--- a/gcc/cfgexpand.c
+++ b/gcc/cfgexpand.c
@@ -3236,6 +3236,20 @@  expand_gimple_stmt_1 (gimple stmt)
 
 	    if (temp == target)
 	      ;
+	    /* If the value in SUBREG of temp fits that SUBREG (does not
+	       overflow) and is assigned to target SUBREG of the same mode
+	       without sign conversion, we can skip the SUBREG
+	       and extension.  */
+	    else if (promoted
+		     && is_assigned_exp_fit_type (lhs)
+		     && (GET_CODE (temp) == SUBREG)
+		     && (GET_MODE_PRECISION (GET_MODE (SUBREG_REG (temp)))
+			 >= GET_MODE_PRECISION (GET_MODE (target)))
+		     && (GET_MODE (SUBREG_REG (target))
+			 == GET_MODE (SUBREG_REG (temp))))
+	      {
+		emit_move_insn (SUBREG_REG (target), SUBREG_REG (temp));
+	      }
 	    else if (promoted)
 	      {
 		int unsignedp = SUBREG_PROMOTED_UNSIGNED_P (target);
diff --git a/gcc/dojump.c b/gcc/dojump.c
index 2aef34d..0f3aeae 100644
--- a/gcc/dojump.c
+++ b/gcc/dojump.c
@@ -1143,6 +1143,62 @@  do_compare_and_jump (tree treeop0, tree treeop1, enum rtx_code signed_code,
 
   type = TREE_TYPE (treeop0);
   mode = TYPE_MODE (type);
+
+  /* Is zero/sign extension redundant.  */
+  bool op0_ext_redundant = false;
+  bool op1_ext_redundant = false;
+
+  /* If promoted and the value in SUBREG of op0 fits (does not overflow),
+     it is a candidate for extension elimination.  */
+  if (GET_CODE (op0) == SUBREG && SUBREG_PROMOTED_VAR_P (op0))
+    op0_ext_redundant = is_assigned_exp_fit_type (treeop0);
+
+  /* If promoted and the value in SUBREG of op1 fits (does not overflow),
+     it is a candidate for extension elimination.  */
+  if (GET_CODE (op1) == SUBREG && SUBREG_PROMOTED_VAR_P (op1))
+    op1_ext_redundant = is_assigned_exp_fit_type (treeop1);
+
+  /* If zero/sign extension is redundant, generate RTL
+     for operands without zero/sign extension.  */
+  if ((op0_ext_redundant || TREE_CODE (treeop0) == INTEGER_CST)
+      && (op1_ext_redundant || TREE_CODE (treeop1) == INTEGER_CST))
+    {
+      if ((TREE_CODE (treeop1) == INTEGER_CST)
+	  && (!mode_signbit_p (GET_MODE (op1), op1)))
+	{
+	  /* First operand is constant and signbit is not set (not
+	     represented in RTL as a negative constant).  */
+	  rtx new_op0 = gen_reg_rtx (GET_MODE (SUBREG_REG (op0)));
+	  emit_move_insn (new_op0, SUBREG_REG (op0));
+	  op0 = new_op0;
+	}
+      else if ((TREE_CODE (treeop0) == INTEGER_CST)
+	       && (!mode_signbit_p (GET_MODE (op0), op0)))
+	{
+	  /* Other operand is constant and signbit is not set (not
+	     represented in RTL as a negative constant).  */
+	  rtx new_op1 = gen_reg_rtx (GET_MODE (SUBREG_REG (op1)));
+
+	  emit_move_insn (new_op1, SUBREG_REG (op1));
+	  op1 = new_op1;
+	}
+      else if ((TREE_CODE (treeop0) != INTEGER_CST)
+	       && (TREE_CODE (treeop1) != INTEGER_CST)
+	       && (GET_MODE (op0) == GET_MODE (op1))
+	       && (GET_MODE (SUBREG_REG (op0)) == GET_MODE (SUBREG_REG (op1))))
+	{
+	  /* If both comapre registers fits SUBREG and of the
+	     same mode.  */
+	  rtx new_op0 = gen_reg_rtx (GET_MODE (SUBREG_REG (op0)));
+	  rtx new_op1 = gen_reg_rtx (GET_MODE (SUBREG_REG (op1)));
+
+	  emit_move_insn (new_op0, SUBREG_REG (op0));
+	  emit_move_insn (new_op1, SUBREG_REG (op1));
+	  op0 = new_op0;
+	  op1 = new_op1;
+	}
+    }
+
   if (TREE_CODE (treeop0) == INTEGER_CST
       && (TREE_CODE (treeop1) != INTEGER_CST
           || (GET_MODE_BITSIZE (mode)
diff --git a/gcc/tree.c b/gcc/tree.c
index d363cfc..d22630a 100644
--- a/gcc/tree.c
+++ b/gcc/tree.c
@@ -408,6 +408,156 @@  tree_node_structure_for_code (enum tree_code code)
     }
 }
 
+/* Check expression value for overflow in tcc_binary.  */
+static bool
+is_binary_expr_fit_type (enum tree_code stmt_code,
+			 tree lhs, double_int min1, double_int max1,
+			 double_int min2, double_int max2)
+{
+  double_int dmin, dmax;
+  double_int type_max = tree_to_double_int (TYPE_MAX_VALUE (TREE_TYPE (lhs)));
+  double_int type_min = tree_to_double_int (TYPE_MIN_VALUE (TREE_TYPE (lhs)));
+  bool uns = TYPE_UNSIGNED (TREE_TYPE (lhs));
+
+  switch (stmt_code)
+    {
+    case PLUS_EXPR:
+      dmin = min1 + min2;
+      dmax = max1 + max2;
+      break;
+    case MINUS_EXPR:
+      dmin = min1 - min2;
+      dmax = max1 - max2;
+      break;
+    default:
+      return false;
+    }
+
+  if (dmin.cmp (type_min, uns) == -1)
+      return false;
+  else if (dmin.cmp (type_max, uns) == 1)
+      return false;
+  if (dmax.cmp (type_min, uns) == -1)
+      return false;
+  else if (dmax.cmp (type_max, uns) == 1)
+      return false;
+  return true;
+}
+
+/* Check gimple assign stmt and see if zero/sign extension is
+   redundant.  i.e.  if an assignment gimple statement has RHS expression
+   value that can fit in LHS type, subreg and extension to fit can be
+   redundant.  Zero/sign extensions in this case can be removed.  */
+
+bool
+is_assigned_exp_fit_type (tree lhs)
+{
+  double_int type_min, type_max;
+  double_int min1, max1, min2, max2;
+  enum tree_code stmt_code;
+  tree rhs1, rhs2;
+  gimple stmt = SSA_NAME_DEF_STMT (lhs);
+  double_int msb_val;
+
+  if (gimple_code (stmt) != GIMPLE_ASSIGN)
+    return false;
+
+  stmt_code = gimple_assign_rhs_code (stmt);
+  rhs1 = gimple_assign_rhs1 (stmt);
+  bool uns = TYPE_UNSIGNED (TREE_TYPE (lhs));
+
+  /* We remove extension for non-pointer and integral stmts.  */
+  if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+      || POINTER_TYPE_P (TREE_TYPE (lhs)))
+    return false;
+
+  type_max = tree_to_double_int (TYPE_MAX_VALUE (TREE_TYPE (lhs)));
+  type_min = tree_to_double_int (TYPE_MIN_VALUE (TREE_TYPE (lhs)));
+
+  if (uns)
+    msb_val = type_max.rshift (1);
+  else
+    msb_val = type_max + double_int_one;
+
+  if (TREE_CODE_CLASS (stmt_code) == tcc_unary)
+    {
+      /* Get the value range.  */
+      if (TREE_CODE (rhs1) == INTEGER_CST)
+	{
+	  min1 = tree_to_double_int (rhs1);
+	  max1 = tree_to_double_int (rhs1);
+	}
+      else if (get_range_info (rhs1, &min1, &max1) != VR_RANGE)
+	{
+	  return false;
+	}
+
+      switch (stmt_code)
+	{
+	case VIEW_CONVERT_EXPR:
+	case CONVERT_EXPR:
+	case NOP_EXPR:
+	  if ((TYPE_UNSIGNED (TREE_TYPE (lhs))
+	       != TYPE_UNSIGNED (TREE_TYPE (rhs1)))
+	      && (TYPE_PRECISION (TREE_TYPE (lhs))
+		  != TYPE_PRECISION (TREE_TYPE (rhs1))))
+	    return false;
+
+	  if (!uns && min1.cmp (msb_val, uns) == 1
+	      && max1.cmp (msb_val, uns) == 1)
+	    {
+	      min1 = min1.sext (TYPE_PRECISION (TREE_TYPE (rhs1)));
+	      max1 = max1.sext (TYPE_PRECISION (TREE_TYPE (rhs1)));
+	    }
+
+	  /* If rhs value range fits lhs type, zero/sign extension is
+	    redundant.  */
+	  if (max1.cmp (type_max, uns) != 1
+	      && (type_min.cmp (min1, uns)) != 1)
+	    return true;
+	  else
+	    return false;
+
+	case NEGATE_EXPR:
+	  return is_binary_expr_fit_type (MINUS_EXPR, lhs, double_int_zero,
+					  double_int_zero, min1, max1);
+	default:
+	  return false;
+	}
+    }
+
+  if (TREE_CODE_CLASS (stmt_code) == tcc_binary)
+    {
+      double_int const_val;
+      rhs2 = gimple_assign_rhs2 (stmt);
+
+      /* Get the value range.  */
+      if (TREE_CODE (rhs1) == INTEGER_CST)
+	{
+	  min1 = tree_to_double_int (rhs1);
+	  max1 = tree_to_double_int (rhs1);
+	}
+      else if (get_range_info (rhs1, &min1, &max1) != VR_RANGE)
+	{
+	  return false;
+	}
+
+      /* Get the value range.  */
+      if (TREE_CODE (rhs2) == INTEGER_CST)
+	{
+	  min2 = tree_to_double_int (rhs2);
+	  max2 = tree_to_double_int (rhs2);
+	}
+      else if (get_range_info (rhs2, &min2, &max2) != VR_RANGE)
+	{
+	  return false;
+	}
+
+      return is_binary_expr_fit_type (stmt_code, lhs, min1, max1, min2, max2);
+    }
+
+  return false;
+}
 
 /* Initialize tree_contains_struct to describe the hierarchy of tree
    nodes.  */
diff --git a/gcc/tree.h b/gcc/tree.h
index 88c8d56..11a286c 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -4134,6 +4134,7 @@  extern tree lhd_gcc_personality (void);
 extern void assign_assembler_name_if_neeeded (tree);
 extern void warn_deprecated_use (tree, tree);
 extern void cache_integer_cst (tree);
+extern bool is_assigned_exp_fit_type (tree lhs);
 
 /* Compare and hash for any structure which begins with a canonical
    pointer.  Assumes all pointers are interchangeable, which is sort