[gsoc 2014] moving fold-const patterns to gimple

[Prathamesh Kulkarni <bilbotheelffriend at gmail dot com>]

Hi, I am an undergraduate student at University of Pune, India, and would
like to work on moving folding patterns from fold-const.c to gimple.

If I understand correctly, constant folding is done on GENERIC (by
routines in fold-const.c), and then GENERIC is lowered to GIMPLE. The
purpose of this project,
is to have constant folding to be performed on GIMPLE instead (in
gimple-fold.c?)

I have a few elementary questions to ask:

a) A contrived example:
Consider a C expression, a = ~0 (assume a is int)
In GENERIC, this would roughly be represented as:
modify_expr<var_decl "a", <bit_not_expr<integer_cst 0>>>
this gets folded to:
modify_expr<var_decl "a", integer_cst -1>
and the corresponding gimple tuple generated is (-fdump-tree-gimple-raw):
gimple_assign <integer_cst, x, -1, NULL, NULL>

So, instead of folding performed on GENERIC, it should be
done on GIMPLE.
So a tuple like the following should be generated by gimplification:
<bit_not_expr, a, 0, NULL, NULL>
and folded to (by call to fold_stmt):
<integer_cst, a, -1, NUL, NULL>
Is this the expected behavior ?

I have attached a rough/incomplete patch (only stage1 compiled cc1), that
does the following foldings on bit_not_expr:
a) ~ INTEGER_CST => folded
b) ~~x => x
c) ~(-x) => x - 1
(For the moment, I put case BIT_NOT_EXPR: return NULL_TREE
in fold_unary_loc to avoid folding in GENERIC on bit_not_expr)

Is the patch going in the correct direction ? Or have I completely missed
the point here ? I would be grateful to receive suggestions, and start working
on a fair patch.

On the following test-case:
int main()
{
  int a, b, c;
  a = ~~~~b;
  c = ~-a;
  return 0;
}

The following GIMPLE is generated:
main ()
gimple_bind <
  int D.1748;
  int D.1749;
  int D.1750;
  int D.1751;
  int D.1752;
  int a;
  int b;
  int c;

  gimple_assign <var_decl, D.1749, b, NULL, NULL>
  gimple_assign <var_decl, a, D.1749, NULL, NULL>
  gimple_assign <plus_expr, c, a, -1, NULL>
  gimple_assign <integer_cst, D.1752, 0, NULL, NULL>
  gimple_return <D.1752>
>

The patch generates two tuples for a = ~~~~b,
where only one is needed, and extra temporaries, which
are not removed after the folding. How should I go about
removing that (should I worry about that since subsequent passes,
shall remove those ?)

b) Some front-ends, C, for example, requires constant folding in certain places,
like case statement. If constant folding is completely moved off to gimple,
how shall this be handled ? Shall we gimplify the expression immediately if
it's required to be evaluated ?

Thanks and Regards,
Prathamesh

Index: gcc/fold-const.c
===================================================================
--- gcc/fold-const.c	(revision 208111)
+++ gcc/fold-const.c	(working copy)
@@ -8313,6 +8313,7 @@ fold_unary_loc (location_t loc, enum tre
       return NULL_TREE;
 
     case BIT_NOT_EXPR:
+      return NULL_TREE;
       if (TREE_CODE (arg0) == INTEGER_CST)
         return fold_not_const (arg0, type);
       else if (TREE_CODE (arg0) == BIT_NOT_EXPR)
Index: gcc/gimple-fold.c
===================================================================
--- gcc/gimple-fold.c	(revision 208111)
+++ gcc/gimple-fold.c	(working copy)
@@ -352,6 +352,68 @@ maybe_fold_reference (tree expr, bool is
   return NULL_TREE;
 }
 
+static tree
+fold_not_const (const_tree arg0, tree type)
+{
+  double_int val;
+
+  gcc_assert (TREE_CODE (arg0) == INTEGER_CST);
+
+  val = ~tree_to_double_int (arg0);
+  return force_fit_type_double (type, val, 0, TREE_OVERFLOW (arg0));
+}
+
+static tree
+fold_gimple_bit_not_expr (gimple_stmt_iterator *si)
+{
+  gimple stmt = gsi_stmt (*si);
+  tree rhs = gimple_assign_rhs1 (stmt);
+  tree result = NULL_TREE; 
+  enum tree_code code = TREE_CODE (rhs);
+  tree type = gimple_expr_type (stmt);
+  gimple_stmt_iterator temp_iter;
+
+  if (code == INTEGER_CST)
+    return fold_not_const (rhs, type); 
+  
+  temp_iter = *si;
+  gsi_prev (&temp_iter);
+  gimple prev = gsi_stmt (temp_iter);
+  
+  if (prev)
+    {
+      if (gimple_code (prev) != GIMPLE_ASSIGN)
+	return NULL_TREE;
+
+      switch (gimple_assign_rhs_code (prev))
+	{
+	  case BIT_NOT_EXPR:  // x = ~~y => x = y
+	    if (gimple_assign_lhs (prev) == rhs)
+	      {
+		result = gimple_assign_rhs1 (prev);
+		gsi_remove (&temp_iter, true);
+		return result;
+	      }
+	    return NULL_TREE;
+	
+	  case NEGATE_EXPR:  // x = ~-y => x = y - 1
+	    if (INTEGRAL_TYPE_P (type))
+	      {
+		result = fold_build2 (MINUS_EXPR, type, 
+				      fold_convert (type, gimple_assign_rhs1 (prev)),
+				      build_int_cst (type, 1));
+		gsi_remove (&temp_iter, true);
+		return result;
+	      }
+	    return NULL_TREE;
+
+	  default:
+	    return NULL_TREE;
+	}
+    }
+  
+  return NULL_TREE; 
+}
 
 /* Attempt to fold an assignment statement pointed-to by SI.  Returns a
    replacement rhs for the statement or NULL_TREE if no simplification
@@ -458,8 +520,10 @@ fold_gimple_assign (gimple_stmt_iterator
     case GIMPLE_UNARY_RHS:
       {
 	tree rhs = gimple_assign_rhs1 (stmt);
-
-	result = fold_unary_loc (loc, subcode, gimple_expr_type (stmt), rhs);
+	if (subcode == BIT_NOT_EXPR)
+	  result = fold_gimple_bit_not_expr (si);
+	else
+	  result = fold_unary_loc (loc, subcode, gimple_expr_type (stmt), rhs);
 	if (result)
 	  {
 	    /* If the operation was a conversion do _not_ mark a