[RFC] combiner for trees

[Andrew Pinski <pinskia at physics dot uc dot edu>]

I implemented a basic combiner for trees using fold.  I have not added
comments yet but I wanted to know if this is right way and if there is
any way to implement this better.  I have not implement the regimplifer
yet or a what the variables name should be like what the RTL combine
does.


Thanks,
Andrew Pinski



Index: tree-ssa-combine.c
===================================================================
RCS file: tree-ssa-combine.c
diff -N tree-ssa-combine.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ tree-ssa-combine.c	18 May 2004 01:00:58 -0000
@@ -0,0 +1,252 @@
+/* Optimize by combining SSA trees for GNU compiler.
+   Copyright (C) 2004 Free Software Foundation, Inc.
+   Contributed by Andrew Pinski.
+
+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 2, 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 COPYING.  If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "errors.h"
+#include "ggc.h"
+#include "tree.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "basic-block.h"
+#include "timevar.h"
+#include "diagnostic.h"
+#include "tree-flow.h"
+#include "tree-pass.h"
+#include "tree-dump.h"
+#include "langhooks.h"
+
+
+static void
+tree_ssa_combine (void)
+{
+  basic_block bb;
+
+  /* Search every basic block for PHI nodes we may be able to 
optimize.  */
+  FOR_EACH_BB (bb)
+    {
+      block_stmt_iterator bsi;
+      for(bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+        {
+          tree stmt = bsi_stmt (bsi);
+          tree orginal_stmt = stmt;
+          tree arg0, arg1 = NULL_TREE;
+          tree variable0, variable1 = NULL_TREE;
+          tree arg0Mod, arg1Mod;
+          tree folded;
+          bool twovariables;
+          enum tree_code code;
+
+          tree rhs;
+          tree *tomodif;
+
+          if (TREE_CODE (stmt) == RETURN_EXPR)
+            stmt = TREE_OPERAND (stmt, 0);
+
+          if (stmt == NULL)
+            continue;
+          else if (TREE_CODE (stmt) == COND_EXPR)
+            {
+              tomodif = &TREE_OPERAND (stmt, 0);
+              rhs = *tomodif;
+            }
+          else if (TREE_CODE (stmt) == MODIFY_EXPR)
+            {
+              tomodif = &TREE_OPERAND (stmt, 1);
+              rhs = *tomodif;
+            }
+	  else
+	    continue;
+
+          code = TREE_CODE (rhs);
+
+          /* FIXME: handle different length other than one or two, 
maybe
+             using an array.  */
+          if (TREE_CODE_LENGTH (code) != 1
+              && TREE_CODE_LENGTH (code) != 2)
+            continue;
+
+          twovariables = TREE_CODE_LENGTH (code) == 2;
+
+          variable0 = TREE_OPERAND (rhs, 0);
+
+          if (variable0 == NULL || TREE_CODE (variable0) != SSA_NAME
+	      || TREE_ADDRESSABLE (SSA_NAME_VAR (variable0)))
+            continue;
+
+          arg0Mod = SSA_NAME_DEF_STMT (variable0);
+
+          if (TREE_CODE (arg0Mod) != MODIFY_EXPR)
+            continue;
+
+          get_stmt_operands (arg0Mod);
+
+          /* We only want ones which are used only once.  */
+          if (NUM_USES (USE_OPS (stmt_ann (arg0Mod))) != 1)
+            continue;
+
+          arg0 = TREE_OPERAND (arg0Mod, 1);
+
+          if (TREE_CODE_CLASS (TREE_CODE (arg0)) == 'r')
+            continue;
+
+          if (twovariables)
+            {
+              variable1 = TREE_OPERAND (rhs, 1);
+
+              if (variable1 == NULL || TREE_CODE (variable1) != 
SSA_NAME
+                  || TREE_ADDRESSABLE (SSA_NAME_VAR (variable1)))
+                twovariables = false;
+              else
+                {
+
+                  arg1Mod = SSA_NAME_DEF_STMT (variable1);
+
+                  if (TREE_CODE (arg1Mod) != MODIFY_EXPR)
+                    continue;
+
+                  get_stmt_operands (arg1Mod);
+
+                  /* We only want ones which are used only once.  */
+                  if (NUM_USES (USE_OPS (stmt_ann (arg1Mod))) != 1)
+                    continue;
+
+                  arg1 = TREE_OPERAND (arg1Mod, 1);
+
+                  if (TREE_CODE_CLASS (TREE_CODE (arg1)) == 'r')
+                    continue;
+
+                  TREE_OPERAND (rhs, 1) = arg1;
+                }
+            }
+
+          TREE_OPERAND (rhs, 0) = arg0;
+
+          folded = fold (rhs);
+
+          if (folded == rhs)
+            {
+              /* Undo the creation of non-gimple code.  */
+              TREE_OPERAND (rhs, 0) = variable0;
+              if (twovariables)
+                TREE_OPERAND (rhs, 1) = variable1;
+              continue;
+            }
+          else
+            {
+              debug_generic_expr (rhs);
+              debug_generic_expr (folded);
+
+              /* We got a variable or constant out of this, just use 
the variable
+                 or that constant.  */
+              if (TREE_CODE (folded) == SSA_NAME
+                  || TREE_CODE_CLASS (TREE_CODE (folded))
+                      == 'c')
+                {
+                  modify_stmt (orginal_stmt);
+                  *tomodif = folded;
+                }
+              else if (TREE_CODE_LENGTH (TREE_CODE (folded)) == 1)
+                {
+                  /* Try to gimplify the new folded result.  */
+                  if (TREE_CODE (TREE_OPERAND (folded, 0)) != SSA_NAME
+                      && ! DECL_P (TREE_OPERAND (folded, 0)))
+                    {
+                      fprintf (stderr, "false\n");
+                      /* XXX: for right now just undo the non-gimple, 
just wantted
+                         to print out what would have folded to. */
+                      TREE_OPERAND (rhs, 0) = variable0;
+                      if (twovariables)
+                        TREE_OPERAND (rhs, 1) = variable1;
+                    }
+                  else
+                    {
+                      modify_stmt (orginal_stmt);
+                      *tomodif = folded;
+                    }
+                }
+              else if (TREE_CODE_LENGTH (TREE_CODE (folded)) == 2)
+                {
+                  /* Try to gimplify the new folded result.  */
+                  if (TREE_CODE (TREE_OPERAND (folded, 0)) != SSA_NAME
+                      || (TREE_CODE (TREE_OPERAND (folded, 1)) != 
SSA_NAME
+                          && TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND 
(folded, 1)))
+                               != 'c'))
+                    {
+                      fprintf (stderr, "false\n");
+                      /* XXX: for right now just undo the non-gimple, 
just wantted
+                         to print out what would have folded to. */
+                      TREE_OPERAND (rhs, 0) = variable0;
+                      if (twovariables)
+                        TREE_OPERAND (rhs, 1) = variable1;
+                    }
+                  else
+                    {
+                      modify_stmt (orginal_stmt);
+                      *tomodif = folded;
+                    }
+                }
+              else
+                {
+                  /* XXX: for right now just undo the non-gimple, just 
wantted
+                    to print out what would have folded to. */
+                  TREE_OPERAND (rhs, 0) = variable0;
+                  if (twovariables)
+                    TREE_OPERAND (rhs, 1) = variable1;
+                  fprintf (stderr, "false\n");
+                }
+              fprintf(stderr, "\n");
+            }
+
+        }
+
+    }
+
+}
+
+/* Always do these optimizations if we have SSA
+   trees to work on.  */						
+static bool
+gate_combine (void)
+{
+  return 1;
+}
+												
+struct tree_opt_pass pass_combine =
+{
+  "combine",				/* name */
+  gate_combine,				/* gate */
+  tree_ssa_combine,			/* execute */
+  NULL,					/* sub */
+  NULL,					/* next */
+  0,					/* static_pass_number */
+  TV_TREE_PHIOPT,			/* tv_id */
+  PROP_cfg | PROP_ssa,			/* properties_required */
+  0,					/* properties_provided */
+  0,					/* properties_destroyed */
+  0,					/* todo_flags_start */
+  TODO_dump_func | TODO_ggc_collect	/* todo_flags_finish */
+    | TODO_verify_ssa
+};
+												
+
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 2.16
diff -u -p -r2.16 tree-optimize.c
--- tree-optimize.c	15 May 2004 23:07:52 -0000	2.16
+++ tree-optimize.c	18 May 2004 01:00:58 -0000
@@ -284,6 +284,7 @@ init_tree_optimization_passes (void)
   NEXT_PASS (pass_early_warn_uninitialized);
   NEXT_PASS (pass_dce);
   NEXT_PASS (pass_dominator);
+  NEXT_PASS (pass_combine);
   NEXT_PASS (pass_redundant_phi);
   NEXT_PASS (DUP_PASS (pass_dce));
   NEXT_PASS (pass_forwprop);
Index: tree-pass.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-pass.h,v
retrieving revision 2.1
diff -u -p -r2.1 tree-pass.h
--- tree-pass.h	13 May 2004 06:39:48 -0000	2.1
+++ tree-pass.h	18 May 2004 01:00:58 -0000
@@ -125,6 +125,7 @@ extern struct tree_opt_pass pass_dse;
 extern struct tree_opt_pass pass_nrv;
 extern struct tree_opt_pass pass_remove_useless_vars;
 extern struct tree_opt_pass pass_rename_ssa_copies;
+extern struct tree_opt_pass pass_combine;


 #endif /* GCC_TREE_PASS_H */
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1277
diff -u -p -r1.1277 Makefile.in
--- Makefile.in	17 May 2004 15:51:22 -0000	1.1277
+++ Makefile.in	18 May 2004 01:00:59 -0000
@@ -873,6 +873,7 @@ OBJS-common = \
  @ANDER@ tree-ssa-dce.o  tree-ssa-copy.o tree-nrv.o 
tree-ssa-copyrename.o  \
  tree-ssa-pre.o tree-ssa-live.o tree-ssa-operands.o tree-ssa-alias.o   
    \
  tree-ssa-phiopt.o tree-ssa-forwprop.o tree-nested.o tree-ssa-dse.o	   
\
+ tree-ssa-combine.o							   \
  tree-ssa-dom.o domwalk.o tree-tailcall.o gimple-low.o 
tree-iterator.o	   \
  tree-phinodes.o tree-ssanames.o tree-sra.o tree-complex.o 
tree-ssa-loop.o \
  alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o	  	   \
@@ -1579,6 +1580,9 @@ tree-ssa-dse.o : tree-ssa-dse.c $(CONFIG
 tree-ssa-forwprop.o : tree-ssa-forwprop.c $(CONFIG_H) $(SYSTEM_H) 
coretypes.h \
    $(TM_H) errors.h $(GGC_H) $(TREE_H) $(RTL_H) $(TM_P_H) 
$(BASIC_BLOCK_H) \
    $(TREE_FLOW_H) tree-pass.h $(TREE_DUMP_H)
+tree-ssa-combine.o : tree-ssa-combine.c $(CONFIG_H) $(SYSTEM_H) 
coretypes.h \
+   $(TM_H) errors.h $(GGC_H) $(TREE_H) $(RTL_H) $(TM_P_H) 
$(BASIC_BLOCK_H) \
+   $(TREE_FLOW_H) tree-pass.h $(TREE_DUMP_H) langhooks.h
 tree-ssa-phiopt.o : tree-ssa-phiopt.c $(CONFIG_H) $(SYSTEM_H) 
coretypes.h \
    $(TM_H) errors.h $(GGC_H) $(TREE_H) $(RTL_H) $(TM_P_H) 
$(BASIC_BLOCK_H) \
    $(TREE_FLOW_H) tree-pass.h $(TREE_DUMP_H) langhooks.h

Attachment: combine.ssa.patch.diff.txt
Description: Text document