[tree-ssa]: Loop LICM, take 2

[Daniel Berlin <dberlin at dberlin dot org>]

Diego, give this one a try.
It bootstraps, i'm running regression tests now.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.110
diff -u -3 -p -w -B -b -r1.903.2.110 Makefile.in
--- Makefile.in	20 Aug 2003 20:43:55 -0000	1.903.2.110
+++ Makefile.in	24 Aug 2003 20:02:03 -0000
@@ -849,7 +849,7 @@
  tree-alias-type.o gimplify.o tree-nomudflap.o tree-pretty-print.o         \
  tree-alias-common.o tree-ssa-ccp.o tree-browser.o @ANDER@ tree-ssa-dce.o  \
  tree-ssa-pre.o tree-ssa-copyprop.o tree-ssa-live.o tree-must-alias.o	   \
- tree-ssa-dom.o								   \
+ tree-ssa-dom.o	tree-loop.o						   \
  alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o	  	   \
  cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o		   \
  cfgloopanal.o cfgloopmanip.o loop-init.o loop-unswitch.o loop-unroll.o	   \
@@ -1556,6 +1556,10 @@
    $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) output.h diagnostic.h \
    errors.h tree-inline.h $(HASHTAB_H) flags.h function.h $(TIMEVAR_H) \
    tree-alias-common.h convert.h $(TM_H) coretypes.h langhooks.h
+tree-loop.o : tree-loop.c $(TREE_FLOW_H) $(CONFIG_H) \
+   $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) \
+   $(GGC_H) output.h diagnostic.h ssa.h errors.h flags.h tree-alias-common.h \
+   $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H)
 tree-optimize.o : tree-optimize.c $(TREE_FLOW_H) $(CONFIG_H) \
    $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) \
    $(GGC_H) output.h diagnostic.h ssa.h errors.h flags.h tree-alias-common.h \
Index: cfgloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.c,v
--- cfgloop.c	23 Jul 2003 16:59:32 -0000	1.14.2.11
+++ cfgloop.c	24 Aug 2003 20:02:03 -0000
@@ -696,6 +696,7 @@
   rc_order = NULL;

   /* Join loops with shared headers.  */
+  if (0)
   canonicalize_loop_headers ();

   /* Compute the dominators.  */
@@ -735,9 +736,11 @@
 	     from a latch node.  */
 	  if (latch != ENTRY_BLOCK_PTR && dominated_by_p (dom, latch, header))
 	    {
+#if 0
 	      /* Shared headers should be eliminated by now.  */
 	      if (more_latches)
 		abort ();
+#endif
 	      more_latches = 1;
 	      SET_BIT (headers, header->index);
 	      num_loops++;
Index: common.opt
===================================================================
RCS file: /cvs/gcc/gcc/gcc/common.opt,v
--- common.opt	20 Aug 2003 20:44:06 -0000	1.14.2.4
+++ common.opt	24 Aug 2003 20:02:03 -0000
@@ -703,6 +703,14 @@
 Common
 Enable dominator optimizations

+ftree-loop-licm
+Common
+Enable loop invariant code motion on trees
+
+ftree-loop-optimize
+Common
+Enable loop optimizations on trees
+
 ftree-must-alias
 Common
 Detect must-alias relations to remove pointer de-references
Index: flags.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flags.h,v
retrieving revision 1.86.2.32
--- flags.h	20 Aug 2003 20:44:20 -0000	1.86.2.32
+++ flags.h	24 Aug 2003 20:02:04 -0000
@@ -692,6 +692,12 @@
 /* Enable SSA-PRE on trees.  */
 extern int flag_tree_pre;

+/* Enable loop invariant code motion on trees.  */
+extern int flag_tree_loop_licm;
+
+/* Enable loop optimizations on trees.  */
+extern int flag_tree_loop_optimize;
+
 /* Enable SSA-CCP on trees.  */
 extern int flag_tree_ccp;

Index: opts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/opts.c,v
--- opts.c	20 Aug 2003 20:44:26 -0000	1.31.2.8
+++ opts.c	24 Aug 2003 20:02:04 -0000
@@ -540,6 +540,9 @@
       /* FIXME: Temporary hack to facilitate testing PRE.  */
       if (getenv ("TREE_SSA_DO_PRE"))
 	flag_tree_pre = 1;
+      flag_tree_loop_optimize = 1;
+      flag_tree_loop_licm = 1;
+
     }

   if (optimize >= 2)
@@ -1401,6 +1404,14 @@

     case OPT_ftree_dominator_opts:
       flag_tree_dom = value;
+      break;
+
+    case OPT_ftree_loop_licm:
+      flag_tree_loop_licm = value;
+      break;
+
+    case OPT_ftree_loop_optimize:
+      flag_tree_loop_optimize = value;
       break;

     case OPT_ftree_must_alias:
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
--- toplev.c	20 Aug 2003 20:44:30 -0000	1.654.2.62
+++ toplev.c	24 Aug 2003 20:02:05 -0000
@@ -953,6 +953,12 @@
 /* Enable the SSA-PRE tree optimization.  */
 int flag_tree_pre = 0;

+/* Enable loop invariant code motion on trees.  */
+int flag_tree_loop_licm = 0;
+
+/* Enable loop optimization on trees.  */
+int flag_tree_loop_optimize = 0;
+
 /* Enable points-to analysis on trees. */
 enum pta_type flag_tree_points_to = PTA_NONE;

Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
--- tree-cfg.c	24 Aug 2003 03:04:40 -0000	1.1.4.155
+++ tree-cfg.c	24 Aug 2003 20:02:06 -0000
@@ -2147,6 +2147,11 @@
 {
   tree stmt = bsi_stmt (from);
   remove_bsi_from_block (&from, false);
+  if (!bsi_end_p (to))
+    {
+      stmt_ann (stmt)->scope = stmt_ann (bsi_stmt (to))->scope;
+      stmt_ann (stmt)->scope_level = stmt_ann (bsi_stmt (to))->scope_level;
+    }
   bsi_insert_after (&to, stmt, BSI_SAME_STMT);
 }

@@ -2157,6 +2162,11 @@
 {
   tree stmt = bsi_stmt (from);
   remove_bsi_from_block (&from, false);
+  if (!bsi_end_p (to))
+    {
+      stmt_ann (stmt)->scope = stmt_ann (bsi_stmt (to))->scope;
+      stmt_ann (stmt)->scope_level = stmt_ann (bsi_stmt (to))->scope_level;
+    }
   bsi_insert_before (&to, stmt, BSI_SAME_STMT);
 }

Index: tree-dump.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-dump.c,v
--- tree-dump.c	22 Aug 2003 01:35:06 -0000	1.6.2.36
+++ tree-dump.c	24 Aug 2003 20:02:07 -0000
@@ -657,6 +657,7 @@
   {".ssa", "tree-ssa", 0, 0},
   {".dom", "tree-dom", 0, 0},
   {".mustalias", "tree-mustalias", 0, 0},
+  {".licm", "tree-loop-licm", 0, 0},
   {".predot", "tree-predot", 0, 0},
   {".pre", "tree-pre", 0, 0},
   {".ccp", "tree-ccp", 0, 0},
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
--- tree-flow.h	19 Aug 2003 19:03:24 -0000	1.1.4.105
+++ tree-flow.h	24 Aug 2003 20:02:07 -0000
@@ -505,6 +505,9 @@
 void tree_ssa_copyprop (tree);
 void propagate_copy (tree *, tree, tree);
 void fixup_var_scope (tree, tree);
+
+/* In tree-loop.c  */
+extern void tree_loop_optimize (tree);

 /* In tree-flow-inline.h  */
 static inline int phi_arg_from_edge (tree, edge);
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-optimize.c,v
--- tree-optimize.c	8 Aug 2003 00:27:10 -0000	1.1.4.43
+++ tree-optimize.c	24 Aug 2003 20:02:07 -0000
@@ -102,6 +102,9 @@

       if (flag_tree_dce)
 	tree_ssa_dce (fndecl);
+
+      if (flag_tree_loop_optimize)
+	tree_loop_optimize (fndecl);

       /* Rewrite the function out of SSA form.  */
       rewrite_out_of_ssa (fndecl);
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
--- tree.h	21 Aug 2003 07:44:58 -0000	1.342.2.89
+++ tree.h	24 Aug 2003 20:02:10 -0000
@@ -3410,6 +3410,8 @@
 				   for each function.  */
   TDI_mustalias,		/* dump must-alias information for each
 				   function.  */
+  TDI_loop_licm,                /* dump loop invariant code motion information
+				   for each function.  */
   TDI_predot,
   TDI_pre,                      /* dump SSA PRE information for each
 				   function.  */
Index: doc/invoke.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/invoke.texi,v
--- doc/invoke.texi	20 Aug 2003 20:45:05 -0000	1.152.2.51
+++ doc/invoke.texi	24 Aug 2003 20:02:16 -0000
@@ -250,6 +250,7 @@
 -fdump-tree-ccp@r{[}-@var{n}@r{]} -fdump-tree-dce@r{[}-@var{n}@r{]} @gol
 -fdump-tree-gimple@r{[}-raw@r{]} -fdump-tree-mudflap@r{[}-@var{n}@r{]} @gol
 -fdump-tree-must-alias@r{[}-@var{n}@r{]} -fdump-tree-dom@r{[}-@var{n}@r{]}@gol
+-fdump-tree-loop-licm@r{[}-@var{n}@r{]} @gol
 -feliminate-dwarf2-dups -feliminate-unused-debug-types @gol
 -feliminate-unused-debug-symbols -fmem-report -fprofile-arcs @gol
 -frandom-seed=@var{string} -fsched-verbose=@var{n} @gol
@@ -297,6 +298,7 @@
 -funswitch-loops  -fold-unroll-loops  -fold-unroll-all-loops @gol
 -fdisable-gimple  -ftree-pre  -ftree-ccp  -ftree-dce  -ftree-copyprop  @gol
 -fdisable-tree-ssa -ftree-dominator-opts -ftree-must-alias @gol
+-ftree-loop-optimize -ftree-loop-licm @gol
 --param @var{name}=@var{value}
 -O  -O0  -O1  -O2  -O3  -Os}

@@ -3394,6 +3396,11 @@
 Dump each function after dead code elimination.  The file name is made by
 appending @file{.dce} to the source file name.

+@item licm
+@opindex fdump-tree-loop-licm
+Dump each function after loop invariant code motion.  The file name is
+made by appending @file{.licm} to the source file name.
+
 @item mudflap
 @opindex fdump-tree-mudflap
 Dump each function after adding mudflap instrumentation.  The file name is
@@ -4143,8 +4150,14 @@
 default at -O and higher.

 @item -ftree-dominator-opts
-Perform dead code elimination (DCE) on trees.  This flag is enabled by
+Perform dominator optimizations on trees.  This flag is enabled by
 default at -O and higher.
+
+@item -ftree-loop-optimize
+Perform loop optimizations on trees.
+
+@item -ftree-loop-licm
+Perform loop invariant code motion on trees.

 @item -ftree-must-alias
 Perform must-alias analysis on trees.  This analysis will attempt to
Index: tree-loop.c
===================================================================
RCS file: tree-loop.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ tree-loop.c	26 Aug 2003 13:26:55 -0000
@@ -0,0 +1,241 @@
+/* Loop optimization functions for trees.
+   Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc.
+   Contributed by Daniel Berlin <dberlin@dberlin.org>
+
+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 "tree.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "output.h"
+#include "expr.h"
+#include "diagnostic.h"
+#include "basic-block.h"
+#include "flags.h"
+#include "tree-flow.h"
+#include "tree-dump.h"
+#include "timevar.h"
+#include "tree-simple.h"
+#include "cfgloop.h"
+#include "bitmap.h"
+#include "tree-inline.h"
+static FILE *licm_dump_file;
+static int licm_dump_flags;
+static void hoist_invariants (tree, struct loops *);
+static void hoist_invariants_in (struct loop *);
+static bool contains_unrenamed_variables (tree);
+/* Determine if t contains unrenamed variables.  */
+static bool
+contains_unrenamed_variables (tree t)
+{
+  enum tree_code code;
+  char class;
+  int i;
+
+  if (t == NULL_TREE)
+    return false;
+
+  code = TREE_CODE (t);
+  class = TREE_CODE_CLASS (code);
+
+  if (class == 'd')
+    return true;
+  else if (class == 'c')
+    return false;
+  else if (IS_EXPR_CODE_CLASS (class) || class == 'r')
+    {
+      if (code == NOP_EXPR || code == CONVERT_EXPR || code == NON_LVALUE_EXPR)
+	return contains_unrenamed_variables (TREE_OPERAND (t, 0));
+      for (i = first_rtl_op (code) - 1; i >= 0; --i)
+	if (contains_unrenamed_variables (TREE_OPERAND (t, i)))
+	  return true;
+    }
+  else if (code == TREE_LIST)
+    {
+      for (; t; t = TREE_CHAIN (t))
+	if (contains_unrenamed_variables (TREE_VALUE (t)))
+	  return true;
+    }
+  else if (code == SSA_NAME)
+    return false;
+
+  return false;
+}
+
+static bool
+def_used_in_abnormal_phi (tree use)
+{
+  size_t i;
+  varray_type iu = immediate_uses (use);
+  if (!iu)
+    return false;
+  for (i = 0; i < VARRAY_ACTIVE_SIZE (iu); i++)
+    {
+      tree use = VARRAY_TREE (iu, i);
+      if (TREE_CODE (use) == PHI_NODE)
+	{
+	  int j;
+	  for (j = 0; j < PHI_NUM_ARGS (use); j++)
+	    {
+	      if (PHI_ARG_EDGE (use, j)->flags & EDGE_ABNORMAL)
+		return true;
+	    }
+	}
+    }
+  return false;
+}
+static void
+hoist_invariants_in (struct loop *loop)
+{
+  size_t i;
+  basic_block *bbs;
+
+  bitmap loop_body = BITMAP_GGC_ALLOC ();
+  bitmap_clear (loop_body);
+
+  bbs = get_loop_body (loop);
+  for (i = 0; i < loop->num_nodes; i++)
+    if (bbs[i]->index >= 0)
+      bitmap_set_bit (loop_body, bbs[i]->index);
+
+  for (i = 0; i < loop->num_nodes; i++)
+    {
+      block_stmt_iterator bsi;
+      if (bsi_end_p (bsi_start (bbs[i])))
+	continue;
+
+      for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi))
+	{
+	  tree stmt = bsi_stmt (bsi);
+	  varray_type uses;
+	  varray_type vuses;
+	  size_t j;
+	  bool can_hoist = true;
+
+	  if (IS_EMPTY_STMT (stmt)
+	      || contains_unrenamed_variables (stmt)
+	      || TREE_CODE (stmt) != MODIFY_EXPR
+	      || TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME)
+
+	    continue;
+	  get_stmt_operands (stmt);
+		if (def_used_in_abnormal_phi (stmt))
+	    continue;
+    uses = use_ops (stmt);
+	  if (uses)
+	    for (j = 0; j < VARRAY_ACTIVE_SIZE (uses); j++)
+	      {
+		tree *usep = VARRAY_GENERIC_PTR (uses, j);
+		tree use = *usep;
+		tree def = SSA_NAME_DEF_STMT (use);
+		if (IS_EMPTY_STMT (def)
+		    || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
+		  {
+
+		    can_hoist = false;
+		    break;
+		  }
+		if (bitmap_bit_p (loop_body, bb_for_stmt (def)->index))
+		  {
+		    can_hoist = false;
+		    break;
+		  }
+	      }
+	  vuses = vuse_ops (stmt);
+	  if (vuses)
+	    for (j = 0; j < VARRAY_ACTIVE_SIZE (vuses); j++)
+	      {
+		tree vuse = VARRAY_TREE (vuses, j);
+		tree vdef = SSA_NAME_DEF_STMT (vuse);
+		if (IS_EMPTY_STMT (vdef)
+		    || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse))
+		  {
+		    can_hoist = false;
+		    break;
+		  }
+		if (bitmap_bit_p (loop_body, bb_for_stmt (vdef)->index))
+		  {
+		    can_hoist = false;
+		    break;
+		  }
+	      }
+	  if (can_hoist)
+	    {
+	      if (licm_dump_file)
+		{
+		  fprintf (licm_dump_file, "Hoisting ");
+		  print_generic_stmt (licm_dump_file, stmt, 0);
+		  fprintf (licm_dump_file, " from BB %d to BB %d\n",
+			   bbs[i]->index, loop->pre_header->index);
+		}
+
+	      bsi_move_to_bb_end (bsi, loop->pre_header);
+
+	      fixup_var_scope (TREE_OPERAND (stmt, 0),
+			       stmt_ann (stmt)->scope);
+
+	      if (bsi_end_p (bsi))
+		{
+		  bsi = bsi_last (bbs[i]);
+		  if (bsi_end_p (bsi))
+		    break;
+		}
+
+	    }
+	}
+    }
+  free (bbs);
+}
+static void
+hoist_invariants (tree fndecl, struct loops *loops)
+{
+  int i;
+  licm_dump_file = dump_begin (TDI_loop_licm, &licm_dump_flags);
+  flow_loops_dump (loops, licm_dump_file, NULL, 0);
+
+  for (i = loops->num - 1; i >= 0; i--)
+    if (loops->parray[i]->pre_header != NULL)
+	hoist_invariants_in (loops->parray[i]);
+
+  if (licm_dump_file)
+    {
+      dump_function_to_file (fndecl, licm_dump_file, licm_dump_flags);
+      dump_end (TDI_loop_licm, licm_dump_file);
+    }
+}
+
+void
+tree_loop_optimize (tree fndecl)
+{
+  struct loops *loops;
+  compute_immediate_uses (TDFA_USE_OPS);
+  loops = loop_optimizer_init (NULL);
+  if (loops)
+    {
+      flow_loops_update (loops, LOOP_ALL);
+      if (flag_tree_loop_licm)
+	hoist_invariants (fndecl, loops);
+    }
+
+  loop_optimizer_finalize (loops, NULL);
+}