[PATCH][RFC] Add gimple_fold

[Richard Guenther <rguenther at suse dot de>]

This tries to extend the previously posted CCP folding patch by
introducing a generic interface for non-tree-building, GIMPLE SSA
aware folding.  The low-level interface for folding regular
operations is

/* Fold the expression composed by *CODEP, TYPE and valueized operands 
*OP0P,
   *OP1P and *OP2P (as required), using the VALUEIZE callback to valueize
   SSA names that turn up during statement lookup and producing a result
   of at most KIND.  The folding result will be stored in the operands.
   GF_KIND_FAIL is returned if no folding was done.
   If GF_KIND_CONST or GF_KIND_VAL is returned the folding result is
   stored in *OP0P and is a is_gimple_min_invariant or a is_gimple_val.
   If GF_KIND_STMT is returned the folding result is stored in *CODEP,
   *OP0P, *OP1P and *OP2P (as required) and will compose a valid set of
   operands for a gimple assignment.
   If GF_KIND_COMPLEX is returned the folding result is stored in *OP0P
   and will be an arbitrarily complex tree.  */

enum gf_kind
gimple_fold (enum tree_code *codep, tree type,
             tree *op0p, tree *op1p, tree *op2p,
             tree (*valueize)(tree), enum gf_kind kind)

which would allow existing gimple-level foldings to build ontop of this
(including fold_stmt and friends and the special CCP foldings).

The current implementation is quite lame, just dispatching to fold,
but I plan to integrate it with the CCP and fold_stmt foldings before
considering to merge it (eventually producing some sort of statistics
of what the fold path catches that the gimple path does not).

The low-level interface needs to be amended by one for builtin calls
where I'm not sure if it is going to take decomposed operands
or just a gimple statement (I think we have at most 3 operands to
any builtin we can fold in some way).

This again is just a RFC (even though the patch "works" as far as
plugging into the SCCVN binary operation simplification).

Thanks,
Richard.

<ChangeLog to be inserted...>

Index: gcc/gimple-fold.h
===================================================================
*** gcc/gimple-fold.h	(revision 0)
--- gcc/gimple-fold.h	(revision 0)
***************
*** 0 ****
--- 1,39 ----
+ /* Gimple folding definitions.
+ 
+    Copyright 2011 Free Software Foundation, Inc.
+    Contributed by Richard Guenther <rguenther@suse.de>
+ 
+ This file is part of GCC.
+ 
+ GCC is free software; you can redistribute it and/or modify it under
+ the terms of the GNU General Public License as published by the Free
+ Software Foundation; either version 3, or (at your option) any later
+ version.
+ 
+ GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ for more details.
+ 
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING3.  If not see
+ <http://www.gnu.org/licenses/>.  */
+ 
+ #ifndef GCC_GIMPLE_FOLD_H
+ #define GCC_GIMPLE_FOLD_H
+ 
+ #include "coretypes.h"
+ 
+ enum gf_kind {
+     GF_KIND_FAIL = 0,
+     GF_KIND_CONST,
+     GF_KIND_VAL,
+     GF_KIND_STMT,
+     GF_KIND_COMPLEX
+ };
+ 
+ enum gf_kind gimple_fold (enum tree_code *, tree,
+ 			  tree *, tree *, tree *,
+ 			  tree (*)(tree), enum gf_kind);
+ 
+ #endif  /* GCC_GIMPLE_FOLD_H */
Index: gcc/gimple-fold.c
===================================================================
*** gcc/gimple-fold.c	(revision 171133)
--- gcc/gimple-fold.c	(working copy)
*************** along with GCC; see the file COPYING3.
*** 30,35 ****
--- 30,36 ----
  #include "tree-pass.h"
  #include "tree-ssa-propagate.h"
  #include "target.h"
+ #include "gimple-fold.h"
  
  /* Return true when DECL can be referenced from current unit.
     We can get declarations that are not possible to reference for
*************** maybe_fold_or_comparisons (enum tree_cod
*** 2665,2667 ****
--- 2666,2914 ----
    else
      return or_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
  }
+ 
+ 
+ static tree
+ build_valueized_tree_from_def (tree name, tree (*valueize)(tree))
+ {
+   gimple def_stmt = SSA_NAME_DEF_STMT (name);
+   tree op0, op1, op2;
+ 
+   if (!is_gimple_assign (def_stmt)
+       || gimple_vuse (def_stmt))
+     return name;
+ 
+   switch (gimple_assign_rhs_class (def_stmt))
+     {
+     case GIMPLE_SINGLE_RHS:
+       return gimple_assign_rhs1 (def_stmt);
+ 
+     case GIMPLE_TERNARY_RHS:
+       op2 = gimple_assign_rhs3 (def_stmt);
+       if (TREE_CODE (op2) == SSA_NAME
+ 	  && valueize)
+ 	op2 = (*valueize) (op2);
+ 
+     case GIMPLE_BINARY_RHS:
+       op1 = gimple_assign_rhs2 (def_stmt);
+       if (TREE_CODE (op1) == SSA_NAME
+ 	  && valueize)
+ 	op1 = (*valueize) (op1);
+ 
+     case GIMPLE_UNARY_RHS:
+       op0 = gimple_assign_rhs1 (def_stmt);
+       if (TREE_CODE (op0) == SSA_NAME
+ 	  && valueize)
+ 	op0 = (*valueize) (op0);
+       break;
+ 
+     default:;
+     }
+ 
+   switch (gimple_assign_rhs_class (def_stmt))
+     {
+     case GIMPLE_UNARY_RHS:
+       return fold_build1 (gimple_assign_rhs_code (def_stmt),
+ 			  TREE_TYPE (name), op0);
+     case GIMPLE_BINARY_RHS:
+       return fold_build2 (gimple_assign_rhs_code (def_stmt),
+ 			  TREE_TYPE (name), op0, op1);
+     case GIMPLE_TERNARY_RHS:
+       return fold_build3 (gimple_assign_rhs_code (def_stmt),
+ 			  TREE_TYPE (name), op0, op1, op2);
+     default:;
+     }
+ 
+   return name;
+ }
+ 
+ static enum gf_kind
+ const_or_val (tree res, enum gf_kind kind)
+ {
+   if (res
+       && kind >= GF_KIND_CONST
+       && is_gimple_min_invariant (res))
+     return GF_KIND_CONST;
+   if (res
+       && kind >= GF_KIND_VAL
+       && is_gimple_val (res))
+     return GF_KIND_VAL;
+   return GF_KIND_FAIL;
+ }
+ 
+ /* Fold the expression composed by *CODEP, TYPE and valueized operands *OP0P,
+    *OP1P and *OP2P (as required), using the VALUEIZE callback to valueize
+    SSA names that turn up during statement lookup and producing a result
+    of at most KIND.  The folding result will be stored in the operands.
+    GF_KIND_FAIL is returned if no folding was done.
+    If GF_KIND_CONST or GF_KIND_VAL is returned the folding result is
+    stored in *OP0P and is a is_gimple_min_invariant or a is_gimple_val.
+    If GF_KIND_STMT is returned the folding result is stored in *CODEP,
+    *OP0P, *OP1P and *OP2P (as required) and will compose a valid set of
+    operands for a gimple assignment.
+    If GF_KIND_COMPLEX is returned the folding result is stored in *OP0P
+    and will be an arbitrarily complex tree.  */
+ 
+ enum gf_kind
+ gimple_fold (enum tree_code *codep, tree type,
+ 	     tree *op0p, tree *op1p, tree *op2p,
+ 	     tree (*valueize)(tree), enum gf_kind kind)
+ {
+   enum tree_code code = *codep;
+   tree op0 = *op0p;
+   tree op1 = *op1p;
+   tree op2 = *op2p;
+   tree alt_op0, alt_op1, res;
+   enum gf_kind res_kind;
+ 
+   switch (code)
+     {
+     case COMPLEX_EXPR:
+       if (TREE_CODE (op0) == SSA_NAME
+ 	  && TREE_CODE (op1) == SSA_NAME)
+ 	{
+ 	  gimple def_stmt0 = SSA_NAME_DEF_STMT (op0);
+ 	  gimple def_stmt1 = SSA_NAME_DEF_STMT (op1);
+ 	  if (gimple_assign_single_p (def_stmt0)
+ 	      && !gimple_vuse (def_stmt0)
+ 	      && gimple_assign_single_p (def_stmt1)
+ 	      && !gimple_vuse (def_stmt1)
+ 	      && gimple_assign_rhs_code (def_stmt0) == REALPART_EXPR
+ 	      && gimple_assign_rhs_code (def_stmt1) == IMAGPART_EXPR)
+ 	    {
+ 	      tree dop0 = TREE_OPERAND (gimple_assign_rhs1 (def_stmt0), 0);
+ 	      tree dop1 = TREE_OPERAND (gimple_assign_rhs1 (def_stmt1), 0);
+ 	      if (TREE_CODE (dop0) == SSA_NAME)
+ 		dop0 = (*valueize) (dop0);
+ 	      if (TREE_CODE (dop1) == SSA_NAME)
+ 		dop1 = (*valueize) (dop1);
+ 	      if (operand_equal_p (dop0, dop1, 0))
+ 		{
+ 		  *op0p = dop0;
+ 		  return (TREE_CODE (dop0) == COMPLEX_CST
+ 			  ? GF_KIND_CONST : GF_KIND_VAL);
+ 		}
+ 	    }
+ 	}
+     default:;
+     }
+ 
+   /* Now fall back to building trees and using fold.  */
+   /* ???  This code should obviously go completely and be replaced by
+      gimple aware, non-tree building variants.  It can be used to
+      identify commonly missed opportunities.  */
+ 
+   switch (get_gimple_rhs_class (code))
+     {
+     case GIMPLE_SINGLE_RHS:
+       if ((code == VIEW_CONVERT_EXPR
+ 	   || code == REALPART_EXPR
+ 	   || code == IMAGPART_EXPR)
+ 	  && TREE_CODE (TREE_OPERAND (op0, 0)) == SSA_NAME)
+ 	{
+ 	  op0 = TREE_OPERAND (op0, 0);
+ 	  if (valueize)
+ 	    op0 = (*valueize) (op0);
+ 	  goto handle_unary;
+ 	}
+       else if (code == BIT_FIELD_REF
+ 	       && TREE_CODE (TREE_OPERAND (op0, 0)) == SSA_NAME)
+ 	{
+ 	  op0 = TREE_OPERAND (op0, 0);
+ 	  if (valueize)
+ 	    op0 = (*valueize) (op0);
+ 	  goto handle_ternary;
+ 	}
+       return GF_KIND_FAIL;
+ 
+ handle_unary:
+     case GIMPLE_UNARY_RHS:
+       res = fold_unary (code, type, op0);
+       if ((res_kind = const_or_val (res, kind)) != GF_KIND_FAIL)
+ 	{
+ 	  *op0p = res;
+ 	  return res_kind;
+ 	}
+       alt_op0 = op0;
+       if (TREE_CODE (op0) == SSA_NAME)
+ 	alt_op0 = build_valueized_tree_from_def (op0, valueize);
+       if (alt_op0 != op0)
+ 	{
+ 	  res = fold_unary (code, type, alt_op0);
+ 	  if ((res_kind = const_or_val (res, kind)) != GF_KIND_FAIL)
+ 	    {
+ 	      *op0p = res;
+ 	      return res_kind;
+ 	    }
+ 	}
+       return GF_KIND_FAIL;
+ 
+     case GIMPLE_BINARY_RHS:
+       res = fold_binary (code, type, op0, op1);
+       if ((res_kind = const_or_val (res, kind)) != GF_KIND_FAIL)
+ 	{
+ 	  *op0p = res;
+ 	  return res_kind;
+ 	}
+       alt_op0 = op0;
+       if (TREE_CODE (op0) == SSA_NAME)
+ 	alt_op0 = build_valueized_tree_from_def (op0, valueize);
+       if (alt_op0 != op0)
+ 	{
+ 	  res = fold_binary (code, type, alt_op0, op1);
+ 	  if ((res_kind = const_or_val (res, kind)) != GF_KIND_FAIL)
+ 	    {
+ 	      *op0p = res;
+ 	      return res_kind;
+ 	    }
+ 	}
+       alt_op1 = op1;
+       if (TREE_CODE (op1) == SSA_NAME)
+ 	alt_op1 = build_valueized_tree_from_def (op1, valueize);
+       if (alt_op1 != op1)
+ 	{
+ 	  res = fold_binary (code, type, op0, alt_op1);
+ 	  if ((res_kind = const_or_val (res, kind)) != GF_KIND_FAIL)
+ 	    {
+ 	      *op0p = res;
+ 	      return res_kind;
+ 	    }
+ 	}
+       if (alt_op0 != op0
+ 	  && alt_op1 != op1)
+ 	{
+ 	  res = fold_binary (code, type, alt_op0, alt_op1);
+ 	  if ((res_kind = const_or_val (res, kind)) != GF_KIND_FAIL)
+ 	    {
+ 	      *op0p = res;
+ 	      return res_kind;
+ 	    }
+ 	}
+       return GF_KIND_FAIL;
+ 
+ handle_ternary:
+     case GIMPLE_TERNARY_RHS:
+       res = fold_ternary (code, type, op0, op1, op2);
+       if ((res_kind = const_or_val (res, kind)) != GF_KIND_FAIL)
+ 	{
+ 	  *op0p = res;
+ 	  return res_kind;
+ 	}
+       alt_op0 = op0;
+       if (TREE_CODE (op0) == SSA_NAME)
+ 	alt_op0 = build_valueized_tree_from_def (op0, valueize);
+       if (alt_op0 != op0)
+ 	{
+ 	  res = fold_ternary (code, type, alt_op0, op1, op2);
+ 	  if ((res_kind = const_or_val (res, kind)) != GF_KIND_FAIL)
+ 	    {
+ 	      *op0p = res;
+ 	      return res_kind;
+ 	    }
+ 	}
+       return GF_KIND_FAIL;
+ 
+     default:
+       return GF_KIND_FAIL;
+     }
+ }
Index: gcc/tree-ssa-sccvn.c
===================================================================
*** gcc/tree-ssa-sccvn.c	(revision 171133)
--- gcc/tree-ssa-sccvn.c	(working copy)
*************** along with GCC; see the file COPYING3.
*** 44,49 ****
--- 44,50 ----
  #include "params.h"
  #include "tree-ssa-propagate.h"
  #include "tree-ssa-sccvn.h"
+ #include "gimple-fold.h"
  
  /* This algorithm is based on the SCC algorithm presented by Keith
     Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
*************** valueize_expr (tree expr)
*** 2745,2796 ****
  static tree
  simplify_binary_expression (gimple stmt)
  {
-   tree result = NULL_TREE;
    tree op0 = gimple_assign_rhs1 (stmt);
    tree op1 = gimple_assign_rhs2 (stmt);
  
!   /* This will not catch every single case we could combine, but will
!      catch those with constants.  The goal here is to simultaneously
!      combine constants between expressions, but avoid infinite
!      expansion of expressions during simplification.  */
!   if (TREE_CODE (op0) == SSA_NAME)
!     {
!       if (VN_INFO (op0)->has_constants
! 	  || TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_comparison)
! 	op0 = valueize_expr (vn_get_expr_for (op0));
!       else if (SSA_VAL (op0) != VN_TOP && SSA_VAL (op0) != op0)
! 	op0 = SSA_VAL (op0);
!     }
! 
!   if (TREE_CODE (op1) == SSA_NAME)
!     {
!       if (VN_INFO (op1)->has_constants)
! 	op1 = valueize_expr (vn_get_expr_for (op1));
!       else if (SSA_VAL (op1) != VN_TOP && SSA_VAL (op1) != op1)
! 	op1 = SSA_VAL (op1);
!     }
! 
!   /* Avoid folding if nothing changed.  */
!   if (op0 == gimple_assign_rhs1 (stmt)
!       && op1 == gimple_assign_rhs2 (stmt))
!     return NULL_TREE;
! 
!   fold_defer_overflow_warnings ();
! 
!   result = fold_binary (gimple_assign_rhs_code (stmt),
! 		        gimple_expr_type (stmt), op0, op1);
!   if (result)
!     STRIP_USELESS_TYPE_CONVERSION (result);
! 
!   fold_undefer_overflow_warnings (result && valid_gimple_rhs_p (result),
! 				  stmt, 0);
! 
!   /* Make sure result is not a complex expression consisting
!      of operators of operators (IE (a + b) + (a + c))
!      Otherwise, we will end up with unbounded expressions if
!      fold does anything at all.  */
!   if (result && valid_gimple_rhs_p (result))
!     return result;
  
    return NULL_TREE;
  }
--- 2746,2767 ----
  static tree
  simplify_binary_expression (gimple stmt)
  {
    tree op0 = gimple_assign_rhs1 (stmt);
    tree op1 = gimple_assign_rhs2 (stmt);
+   enum tree_code code = gimple_assign_rhs_code (stmt);
+   tree dummy;
  
!   if (TREE_CODE (op0) == SSA_NAME
!       && SSA_VAL (op0) != VN_TOP)
!     op0 = SSA_VAL (op0);
! 
!   if (TREE_CODE (op1) == SSA_NAME
!       && SSA_VAL (op1) != VN_TOP)
!     op1 = SSA_VAL (op1);
! 
!   if (gimple_fold (&code, TREE_TYPE (gimple_assign_lhs (stmt)),
! 		   &op0, &op1, &dummy, NULL, GF_KIND_VAL) != GF_KIND_FAIL)
!     return op0;
  
    return NULL_TREE;
  }