This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH][5/n] Merge from match-and-simplify, hook into fold_stmt and exercise from tree-ssa-forwprop


This hooks the machinery into fold_stmt (but not allowed to traverse
SSA use-def chains by default) and provides a new overload to
provide a valueization hook.  With the patch tree-ssa-forwprop.c
makes use of that new overload, first folding all statements
while keeping a simple const-and-copy lattice.

Once all "toplevel" patterns are in place (patterns with
a single operation) we can remove the dispatch to GENERIC
folding from fold_stmt.

A question is whether to really do as the patch does and simplify
all statements or whether I should restrict this to stmts that
were previously covered by its manual patterns (which further
patches will transition to match-and-simplify patterns).

As for the GENERIC part, here is what the simplification routine
looks like for

/* fold_negate_exprs convert - (~A) to A + 1.  */
(simplify
 (negate (bit_not @0))
 (if (INTEGRAL_TYPE_P (type))
  (plus @0 { build_int_cst (TREE_TYPE (@0), 1); } )))

static bool
gimple_simplify (code_helper *res_code, tree *res_ops,
                 gimple_seq *seq, tree (*valueize)(tree),
                 code_helper code, tree type, tree op0)
{
  switch (code.get_rep())
    {
...
    case NEGATE_EXPR:
      {
        switch (TREE_CODE (op0))
          {
          case SSA_NAME:
            {
              gimple def_stmt = SSA_NAME_DEF_STMT (op0);
              if (is_gimple_assign (def_stmt))
                switch (gimple_assign_rhs_code (def_stmt))
                  {
                  case BIT_NOT_EXPR:
                    {
                      tree o20 = gimple_assign_rhs1 (def_stmt);
                      if ((o20 = do_valueize (valueize, o20)) != 0)
                        {
                            {
                              /* #line 136 "/space/rguenther/src/svn/match-and-simplify/gcc/match.pd" */
                              tree captures[2] ATTRIBUTE_UNUSED = {};
                              captures[0] = o20;
                              /* #line 135 "/space/rguenther/src/svn/match-and-simplify/gcc/match.pd" */
                              if (INTEGRAL_TYPE_P (type))
                                {
                                  if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "Applying pattern match.pd:136, %s:%d\n", __FILE__, __LINE__);
                                  *res_code = PLUS_EXPR;
                                  res_ops[0] = captures[0];
                                  res_ops[1] =  build_int_cst (TREE_TYPE (captures[0]), 1);
                                  gimple_resimplify2 (seq, res_code, type, res_ops, valueize);
                                  return true;
                                }
                            }
                        }
                      break;
                    }
...

As you can see we use gimple_resimplify2 for re-simplification and
code-generation and the toplevel expression of the result is
kept in pieces.  gimple_resimplify2 in turn ends up calling
gimple_simplify again and fold to get the "real" constant folding cases.

Boostrap and regtest is pending on x86_64-unknown-linux-gnu.

Ok for trunk?

Thanks,
Richard.

2014-10-15  Richard Biener  <rguenther@suse.de>

	* gimple-fold.h (fold_stmt): New overload with valueization hook.
	(no_follow_ssa_edges): Declare.
	* gimple-fold.c: Include tree-eh.h and gimple-match.h.
	(fold_stmt_1): Add valueization hook parameter.  Dispatch to
	gimple_simplify after canonicalization.
	(no_follow_ssa_edges): New function.
	(fold_stmt): New overload and adjust.
	(fold_stmt_inplace): Adjust.
	* tree-ssa-forwprop.c: Include tree-cfgcleanup.h and tree-into-ssa.h.
	(lattice): New global.
	(fwprop_ssa_val): New function.
	(pass_forwprop::execute): Do a first pass over all stmts in
	dominator order simplifying all statements while keeping
	a simple const-and-copy lattice up-to-date.

Index: gcc/gimple-fold.h
===================================================================
*** gcc/gimple-fold.h.orig	2014-10-15 13:01:41.548100887 +0200
--- gcc/gimple-fold.h	2014-10-15 13:57:05.627872029 +0200
*************** extern tree canonicalize_constructor_val
*** 26,36 ****
--- 26,38 ----
  extern tree get_symbol_constant_value (tree);
  extern void gimplify_and_update_call_from_tree (gimple_stmt_iterator *, tree);
  extern bool fold_stmt (gimple_stmt_iterator *);
+ extern bool fold_stmt (gimple_stmt_iterator *, tree (*) (tree));
  extern bool fold_stmt_inplace (gimple_stmt_iterator *);
  extern tree maybe_fold_and_comparisons (enum tree_code, tree, tree, 
  					enum tree_code, tree, tree);
  extern tree maybe_fold_or_comparisons (enum tree_code, tree, tree,
  				       enum tree_code, tree, tree);
+ extern tree no_follow_ssa_edges (tree);
  extern tree gimple_fold_stmt_to_constant_1 (gimple, tree (*) (tree));
  extern tree gimple_fold_stmt_to_constant (gimple, tree (*) (tree));
  extern tree fold_const_aggregate_ref_1 (tree, tree (*) (tree));
Index: gcc/gimple-fold.c
===================================================================
*** gcc/gimple-fold.c.orig	2014-10-15 13:02:08.158099055 +0200
--- gcc/gimple-fold.c	2014-10-15 13:56:20.710875121 +0200
*************** along with GCC; see the file COPYING3.
*** 55,60 ****
--- 55,63 ----
  #include "dbgcnt.h"
  #include "builtins.h"
  #include "output.h"
+ #include "tree-eh.h"
+ #include "gimple-match.h"
+ 
  
  
  /* Return true when DECL can be referenced from current unit.
*************** maybe_canonicalize_mem_ref_addr (tree *t
*** 2811,2817 ****
     distinguishes both cases.  */
  
  static bool
! fold_stmt_1 (gimple_stmt_iterator *gsi, bool inplace)
  {
    bool changed = false;
    gimple stmt = gsi_stmt (*gsi);
--- 2814,2820 ----
     distinguishes both cases.  */
  
  static bool
! fold_stmt_1 (gimple_stmt_iterator *gsi, bool inplace, tree (*valueize) (tree))
  {
    bool changed = false;
    gimple stmt = gsi_stmt (*gsi);
*************** fold_stmt_1 (gimple_stmt_iterator *gsi,
*** 2889,2894 ****
--- 2892,3017 ----
      default:;
      }
  
+   /* Dispatch to pattern-based folding.  */
+   /* ???  Change "inplace" semantics to allow replacing a stmt if
+      no further stmts need to be inserted (basically disallow
+      creating of new SSA names).  */
+   if (!inplace
+       || is_gimple_assign (stmt)
+       || gimple_code (stmt) == GIMPLE_COND)
+     {
+       gimple_seq seq = NULL;
+       code_helper rcode;
+       tree ops[3] = {};
+       if (gimple_simplify (stmt, &rcode, ops, inplace ? NULL : &seq, valueize))
+ 	{
+ 	  if (gimple_code (stmt) == GIMPLE_COND)
+ 	    {
+ 	      gcc_assert (rcode.is_tree_code ());
+ 	      if (TREE_CODE_CLASS ((enum tree_code)rcode) == tcc_comparison
+ 		  /* GIMPLE_CONDs condition may not throw.  */
+ 		  /* ???  Not sure how we want to deal with combining
+ 		     from possibly throwing statements.  Trivial
+ 		     simplifications may lead to DCEing an internal
+ 		     throw.  But we probably still want to simplify
+ 		     things to a constant for example?  Similar to
+ 		     abnormals we could discard the simplification
+ 		     result if we ever push a could-throw stmt to
+ 		     the sequence.  */
+ 		  && (!flag_exceptions
+ 		      || !cfun->can_throw_non_call_exceptions
+ 		      || !operation_could_trap_p (rcode, FLOAT_TYPE_P (TREE_TYPE (ops[0])), false, NULL_TREE)))
+ 		gimple_cond_set_condition (stmt, rcode, ops[0], ops[1]);
+ 	      else if (rcode == SSA_NAME)
+ 		gimple_cond_set_condition (stmt, NE_EXPR, ops[0],
+ 					   build_zero_cst (TREE_TYPE (ops[0])));
+ 	      else if (rcode == INTEGER_CST)
+ 		{
+ 		  if (integer_zerop (ops[0]))
+ 		    gimple_cond_make_false (stmt);
+ 		  else
+ 		    gimple_cond_make_true (stmt);
+ 		}
+ 	      else if (!inplace)
+ 		{
+ 		  tree res = maybe_push_res_to_seq (rcode, boolean_type_node,
+ 						    ops, &seq);
+ 		  if (!res)
+ 		    goto fail;
+ 		  gimple_cond_set_condition (stmt, NE_EXPR, res,
+ 					     build_zero_cst (TREE_TYPE (res)));
+ 		}
+ 	      else
+ 		goto fail;
+ 	      if (dump_file && (dump_flags & TDF_DETAILS))
+ 		{
+ 		  fprintf (dump_file, "gimple_simplified to ");
+ 		  if (!gimple_seq_empty_p (seq))
+ 		    print_gimple_seq (dump_file, seq, 0, TDF_SLIM);
+ 		  print_gimple_stmt (dump_file, gsi_stmt (*gsi),
+ 				     0, TDF_SLIM);
+ 		}
+ 	      gsi_insert_seq_before (gsi, seq, GSI_SAME_STMT);
+ 	      changed = true;
+ fail:
+ 	      ;
+ 	    }
+ 	  else if (is_gimple_assign (stmt)
+ 		   && rcode.is_tree_code ())
+ 	    {
+ 	      if ((!inplace
+ 		   || gimple_num_ops (stmt) <= get_gimple_rhs_num_ops (rcode))
+ 		  /* Play safe and do not allow abnormals to be mentioned in
+ 		     newly created statements.  */
+ 		  && !((TREE_CODE (ops[0]) == SSA_NAME
+ 			&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ops[0]))
+ 		       || (ops[1]
+ 			   && TREE_CODE (ops[1]) == SSA_NAME
+ 			   && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ops[1]))
+ 		       || (ops[2]
+ 			   && TREE_CODE (ops[2]) == SSA_NAME
+ 			   && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ops[2]))))
+ 		{
+ 		  maybe_build_generic_op (rcode,
+ 					  TREE_TYPE (gimple_assign_lhs (stmt)),
+ 					  &ops[0], ops[1], ops[2]);
+ 		  gimple_assign_set_rhs_with_ops_1 (gsi, rcode,
+ 						    ops[0], ops[1], ops[2]);
+ 		  if (dump_file && (dump_flags & TDF_DETAILS))
+ 		    {
+ 		      fprintf (dump_file, "gimple_simplified to ");
+ 		      if (!gimple_seq_empty_p (seq))
+ 			print_gimple_seq (dump_file, seq, 0, TDF_SLIM);
+ 		      print_gimple_stmt (dump_file, gsi_stmt (*gsi),
+ 					 0, TDF_SLIM);
+ 		    }
+ 		  gsi_insert_seq_before (gsi, seq, GSI_SAME_STMT);
+ 		  changed = true;
+ 		}
+ 	    }
+ 	  else if (!inplace)
+ 	    {
+ 	      if (gimple_has_lhs (stmt))
+ 		{
+ 		  tree lhs = gimple_get_lhs (stmt);
+ 		  maybe_push_res_to_seq (rcode, TREE_TYPE (lhs),
+ 					 ops, &seq, lhs);
+ 		  if (dump_file && (dump_flags & TDF_DETAILS))
+ 		    {
+ 		      fprintf (dump_file, "gimple_simplified to ");
+ 		      print_gimple_seq (dump_file, seq, 0, TDF_SLIM);
+ 		    }
+ 		  gsi_replace_with_seq_vops (gsi, seq);
+ 		  changed = true;
+ 		}
+ 	      else
+ 		gcc_unreachable ();
+ 	    }
+ 	}
+     }
+ 
+   stmt = gsi_stmt (*gsi);
+ 
    /* Fold the main computation performed by the statement.  */
    switch (gimple_code (stmt))
      {
*************** fold_stmt_1 (gimple_stmt_iterator *gsi,
*** 3028,3033 ****
--- 3151,3164 ----
    return changed;
  }
  
+ /* Valueziation callback that ends up not following SSA edges.  */
+ 
+ tree
+ no_follow_ssa_edges (tree)
+ {
+   return NULL_TREE;
+ }
+ 
  /* Fold the statement pointed to by GSI.  In some cases, this function may
     replace the whole statement with a new one.  Returns true iff folding
     makes any changes.
*************** fold_stmt_1 (gimple_stmt_iterator *gsi,
*** 3038,3044 ****
  bool
  fold_stmt (gimple_stmt_iterator *gsi)
  {
!   return fold_stmt_1 (gsi, false);
  }
  
  /* Perform the minimal folding on statement *GSI.  Only operations like
--- 3169,3181 ----
  bool
  fold_stmt (gimple_stmt_iterator *gsi)
  {
!   return fold_stmt_1 (gsi, false, no_follow_ssa_edges);
! }
! 
! bool
! fold_stmt (gimple_stmt_iterator *gsi, tree (*valueize) (tree))
! {
!   return fold_stmt_1 (gsi, false, valueize);
  }
  
  /* Perform the minimal folding on statement *GSI.  Only operations like
*************** bool
*** 3053,3059 ****
  fold_stmt_inplace (gimple_stmt_iterator *gsi)
  {
    gimple stmt = gsi_stmt (*gsi);
!   bool changed = fold_stmt_1 (gsi, true);
    gcc_assert (gsi_stmt (*gsi) == stmt);
    return changed;
  }
--- 3190,3196 ----
  fold_stmt_inplace (gimple_stmt_iterator *gsi)
  {
    gimple stmt = gsi_stmt (*gsi);
!   bool changed = fold_stmt_1 (gsi, true, no_follow_ssa_edges);
    gcc_assert (gsi_stmt (*gsi) == stmt);
    return changed;
  }
Index: gcc/tree-ssa-forwprop.c
===================================================================
*** gcc/tree-ssa-forwprop.c.orig	2014-10-14 15:49:39.836355545 +0200
--- gcc/tree-ssa-forwprop.c	2014-10-15 13:56:20.725875120 +0200
*************** along with GCC; see the file COPYING3.
*** 54,59 ****
--- 54,61 ----
  #include "tree-ssa-propagate.h"
  #include "tree-ssa-dom.h"
  #include "builtins.h"
+ #include "tree-cfgcleanup.h"
+ #include "tree-into-ssa.h"
  
  /* This pass propagates the RHS of assignment statements into use
     sites of the LHS of the assignment.  It's basically a specialized
*************** simplify_mult (gimple_stmt_iterator *gsi
*** 3586,3591 ****
--- 3588,3613 ----
  
    return false;
  }
+ 
+ 
+ static vec<tree> lattice;
+ 
+ /* Primitive "lattice" function for gimple_simplify to discard
+    matches on names whose definition contains abnormal SSA names.  */
+ 
+ static tree
+ fwprop_ssa_val (tree name)
+ {
+   if (TREE_CODE (name) == SSA_NAME
+       && SSA_NAME_VERSION (name) < lattice.length ())
+     {
+       tree val = lattice[SSA_NAME_VERSION (name)];
+       if (val)
+ 	return val;
+     }
+   return name;
+ }
+ 
  /* Main entry point for the forward propagation and statement combine
     optimizer.  */
  
*************** pass_forwprop::execute (function *fun)
*** 3626,3631 ****
--- 3648,3708 ----
  
    cfg_changed = false;
  
+   /* Combine stmts with the stmts defining their operands.  Do that
+      in an order that guarantees visiting SSA defs before SSA uses.  */
+   lattice.create (num_ssa_names);
+   lattice.quick_grow_cleared (num_ssa_names);
+   int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (fun));
+   int postorder_num = inverted_post_order_compute (postorder);
+   for (int i = 0; i < postorder_num; ++i)
+     {
+       bb = BASIC_BLOCK_FOR_FN (fun, postorder[i]);
+       /* ???  Maybe want to handle degenerate PHIs to populate
+ 	 the lattice more optimistically.  */
+       for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
+ 	   !gsi_end_p (gsi); gsi_next (&gsi))
+ 	{
+ 	  gimple stmt = gsi_stmt (gsi);
+ 	  gimple orig_stmt = stmt;
+ 
+ 	  if (fold_stmt (&gsi, fwprop_ssa_val))
+ 	    {
+ 	      stmt = gsi_stmt (gsi);
+ 	      if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt)
+ 		  && gimple_purge_dead_eh_edges (bb))
+ 		cfg_changed = true;
+ 	      update_stmt (stmt);
+ 	    }
+ 
+ 	  /* Fill up the lattice.  */
+ 	  if (gimple_assign_single_p (stmt))
+ 	    {
+ 	      tree lhs = gimple_assign_lhs (stmt);
+ 	      tree rhs = gimple_assign_rhs1 (stmt);
+ 	      if (TREE_CODE (lhs) == SSA_NAME)
+ 		{
+ 		  if (TREE_CODE (rhs) == SSA_NAME)
+ 		    lattice[SSA_NAME_VERSION (lhs)] = fwprop_ssa_val (rhs);
+ 		  else if (is_gimple_min_invariant (rhs))
+ 		    lattice[SSA_NAME_VERSION (lhs)] = rhs;
+ 		  else
+ 		    lattice[SSA_NAME_VERSION (lhs)] = lhs;
+ 		}
+ 	    }
+ 	}
+     }
+   free (postorder);
+   lattice.release ();
+ 
+   /* ???  Code below doesn't expect non-renamed VOPs and the above
+      doesn't keep virtual operand form up-to-date.  */
+   if (cfg_changed)
+     {
+       cleanup_tree_cfg ();
+       cfg_changed = false;
+     }
+   update_ssa (TODO_update_ssa_only_virtuals);
+ 
    FOR_EACH_BB_FN (bb, fun)
      {
        gimple_stmt_iterator gsi;


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]