Re: [gomp] More IL work

[Sebastian Pop <sebastian dot pop at cri dot ensmp dot fr>]

Hi Diego,

I'm playing with the following patch and as you'll see, in this
context I'll need several loops structures, one per function, such
that I can move loops from a function to another using some of the
copy/delete/move loop machinery.

The patch is just in a horrible state (sorry), but I wanted to see
what's the reaction to such a schedule for generating parallel code.
I've placed it just after some loops optimizations, such that early
analyzers or optimizers like loop fission can mark consecutive loops
to have no dependences.

One of the things I have thought about is that it could be possible to
flag some of the loops to be distributed at the moment where the loops
are created, and keep the loops representation intact until we
generate parallel code for these loops, so a part of the gomp pragmas
are translated into flags on loops until this information is used for
generating the calls to libgomp.

Sebastian

Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1501.4.2
diff -d -u -p -r1.1501.4.2 Makefile.in
--- Makefile.in	12 Jul 2005 14:19:39 -0000	1.1501.4.2
+++ Makefile.in	1 Aug 2005 17:05:14 -0000
@@ -916,6 +916,7 @@ C_OBJS = c-lang.o stub-objc.o $(C_AND_OB
 
 # Language-independent object files.
 OBJS-common = \
+ tree-loop-distrib.o \
  tree-chrec.o tree-scalar-evolution.o tree-data-ref.o			   \
  tree-cfg.o tree-dfa.o tree-eh.o tree-ssa.o tree-optimize.o tree-gimple.o  \
  gimplify.o tree-pretty-print.o tree-into-ssa.o				   \
@@ -1950,6 +1951,11 @@ tree-vectorizer.o: tree-vectorizer.c $(C
    $(DIAGNOSTIC_H) $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) \
    tree-pass.h $(EXPR_H) tree-vectorizer.h $(TREE_DATA_REF_H) $(SCEV_H) \
    input.h $(TARGET_H) $(CFGLAYOUT_H) toplev.h tree-chrec.h
+tree-loop-distrib.o: tree-loop-distrib.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
+   $(TM_H) $(GGC_H) $(OPTABS_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) \
+   $(DIAGNOSTIC_H) $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) \
+   tree-pass.h $(TREE_DATA_REF_H) $(SCEV_H) $(EXPR_H) $(LAMBDA_H) \
+   $(TARGET_H) tree-chrec.h $(VARRAY_H)
 tree-loop-linear.o: tree-loop-linear.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
    $(TM_H) $(GGC_H) $(OPTABS_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) \
    $(DIAGNOSTIC_H) $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) \
Index: cfgloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.c,v
retrieving revision 1.52.4.1
diff -d -u -p -r1.52.4.1 cfgloop.c
--- cfgloop.c	6 Jul 2005 17:37:45 -0000	1.52.4.1
+++ cfgloop.c	1 Aug 2005 17:05:15 -0000
@@ -924,7 +924,7 @@ get_loop_body_in_bfs_order (const struct
   return blocks;
 }
 
-/* Gets exit edges of a LOOP, returning their number in N_EDGES.  */
+/* Gets exit edges of a LOOP, returning their number in NUM_EDGES.  */
 edge *
 get_loop_exit_edges (const struct loop *loop, unsigned int *num_edges)
 {
Index: cfgloop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.h,v
retrieving revision 1.46.4.1
diff -d -u -p -r1.46.4.1 cfgloop.h
--- cfgloop.h	6 Jul 2005 17:37:45 -0000	1.46.4.1
+++ cfgloop.h	1 Aug 2005 17:05:15 -0000
@@ -452,6 +452,7 @@ extern void unroll_and_peel_loops (struc
 extern void doloop_optimize_loops (struct loops *);
 extern void move_loop_invariants (struct loops *);
 extern void record_estimate (struct loop *, tree, tree, tree);
+extern void distribute_loops (struct loops *);
 
 /* Old loop optimizer interface.  */
 
Index: common.opt
===================================================================
RCS file: /cvs/gcc/gcc/gcc/common.opt,v
retrieving revision 1.73.4.1
diff -d -u -p -r1.73.4.1 common.opt
--- common.opt	6 Jul 2005 17:37:52 -0000	1.73.4.1
+++ common.opt	1 Aug 2005 17:05:15 -0000
@@ -883,6 +883,10 @@ ftree-dce
 Common Report Var(flag_tree_dce)
 Enable SSA dead code elimination optimization on trees
 
+ftree-distribute-loops
+Common Report Var(flag_tree_distribute_loops)
+Enable thread distribution of loops
+
 ftree-dominator-opts
 Common Report Var(flag_tree_dom)
 Enable dominator optimizations
Index: passes.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/passes.c,v
retrieving revision 2.91.4.2
diff -d -u -p -r2.91.4.2 passes.c
--- passes.c	12 Jul 2005 14:20:26 -0000	2.91.4.2
+++ passes.c	1 Aug 2005 17:05:15 -0000
@@ -560,6 +560,7 @@ init_optimization_passes (void)
   NEXT_PASS (pass_iv_canon);
   NEXT_PASS (pass_if_conversion);
   NEXT_PASS (pass_vectorize);
+  NEXT_PASS (pass_distribute_loops);
   /* NEXT_PASS (pass_may_alias) cannot be done again because the
      vectorizer creates alias relations that are not supported by
      pass_may_alias.  */
Index: timevar.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/timevar.def,v
retrieving revision 1.50.4.1
diff -d -u -p -r1.50.4.1 timevar.def
--- timevar.def	6 Jul 2005 17:39:37 -0000	1.50.4.1
+++ timevar.def	1 Aug 2005 17:05:15 -0000
@@ -101,6 +101,7 @@ DEFTIMEVAR (TV_SCEV_CONST            , "
 DEFTIMEVAR (TV_TREE_LOOP_UNSWITCH    , "tree loop unswitching")
 DEFTIMEVAR (TV_COMPLETE_UNROLL       , "complete unrolling")
 DEFTIMEVAR (TV_TREE_VECTORIZATION    , "tree vectorization")
+DEFTIMEVAR (TV_TREE_DISTRIBUTE_LOOPS , "tree loop distribution")
 DEFTIMEVAR (TV_TREE_LINEAR_TRANSFORM , "tree loop linear")
 DEFTIMEVAR (TV_TREE_LOOP_IVOPTS	     , "tree iv optimization")
 DEFTIMEVAR (TV_TREE_LOOP_INIT	     , "tree loop init")
Index: tree-loop-distrib.c
===================================================================
RCS file: tree-loop-distrib.c
diff -N tree-loop-distrib.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ tree-loop-distrib.c	1 Aug 2005 17:05:17 -0000
@@ -0,0 +1,101 @@
+/* Loop distribution.
+   Copyright (C) 2005 Free Software Foundation, Inc.
+   Contributed by Sebastian Pop <pop@cri.ensmp.fr>
+
+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, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "ggc.h"
+#include "tree.h"
+#include "target.h"
+
+#include "rtl.h"
+#include "basic-block.h"
+#include "diagnostic.h"
+#include "tree-flow.h"
+#include "tree-dump.h"
+#include "timevar.h"
+#include "cfgloop.h"
+#include "expr.h"
+#include "optabs.h"
+#include "tree-chrec.h"
+#include "tree-data-ref.h"
+#include "tree-scalar-evolution.h"
+#include "tree-pass.h"
+#include "varray.h"
+#include "lambda.h"
+
+/* This file implements loop distribution.  */
+
+/* Create a thread that will execute the LOOP.  */
+
+static void
+distribute_loop_in_a_thread (struct loops *loops, struct loop *loop)
+{
+  unsigned i;
+  basic_block before_loop, after_loop, *body;
+  tree thread_fn;
+  struct loops *thread_loops;
+
+  /* Move the code from loop to the thread body.  */
+  thread_fn = create_thread ();
+
+  thread_loops = ;
+
+  /* FIXME: We'll need several loops structures for different
+     functions.  */
+  copy_loops_to (thread_loops, );
+
+  fix_loop_structure (thread_loops, NULL);
+
+  /* Insert the thread call in before_loop.  */
+
+  /* Link before_loop to after_loop.  */
+  before_loop = loop_preheader_edge (loop)->src;
+  after_loop = loop->single_exit->target;
+
+
+  /* Remove the loop.  */
+  body = get_loop_body (loop);
+  cancel_loop_tree (loops, loop);
+  for (i = 0; i < loop->num_nodes; i++)
+    {
+      remove_bb_from_loops (body[i]);
+      delete_basic_block (body[i]);
+    }
+  free (body);
+}
+
+/* Distribute loops in different threads.  */
+
+void
+distribute_loops (struct loops *loops)
+{
+  unsigned int i;
+
+  for (i = 1; i < loops->num; i++)
+    {
+      struct loop *loop = loops->parray[i];
+
+      if (loop->single_exit && can_duplicate_loop_p (loop))
+	distribute_loop_in_a_thread (loops, loop);
+    }
+}
Index: tree-pass.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-pass.h,v
retrieving revision 2.40.4.2
diff -d -u -p -r2.40.4.2 tree-pass.h
--- tree-pass.h	12 Jul 2005 14:20:39 -0000	2.40.4.2
+++ tree-pass.h	1 Aug 2005 17:05:17 -0000
@@ -271,6 +271,7 @@ extern struct tree_opt_pass pass_expand;
 extern struct tree_opt_pass pass_rest_of_compilation;
 extern struct tree_opt_pass pass_sink_code;
 extern struct tree_opt_pass pass_fre;
+extern struct tree_opt_pass pass_distribute_loops;
 extern struct tree_opt_pass pass_linear_transform;
 extern struct tree_opt_pass pass_copy_prop;
 extern struct tree_opt_pass pass_store_ccp;
Index: tree-ssa-loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop.c,v
retrieving revision 2.30.4.2
diff -d -u -p -r2.30.4.2 tree-ssa-loop.c
--- tree-ssa-loop.c	12 Jul 2005 14:20:41 -0000	2.30.4.2
+++ tree-ssa-loop.c	1 Aug 2005 17:05:17 -0000
@@ -217,6 +217,39 @@ struct tree_opt_pass pass_vectorize =
   0					/* letter */
 };
 
+/* Loop distribution.  */
+
+static bool
+gate_tree_distribute_loops (void)
+{
+  return flag_tree_distribute_loops != 0;
+}
+
+static void
+tree_distribute_loops (void)
+{
+  if (!current_loops)
+    return;
+
+  distribute_loops (current_loops);
+}
+
+struct tree_opt_pass pass_distribute_loops =
+{
+  "ldistrib",				/* name */
+  gate_tree_distribute_loops,		/* gate */
+  tree_distribute_loops,       		/* execute */
+  NULL,					/* sub */
+  NULL,					/* next */
+  0,					/* static_pass_number */
+  TV_TREE_DISTRIBUTE_LOOPS,  		/* tv_id */
+  PROP_cfg | PROP_ssa,			/* properties_required */
+  0,					/* properties_provided */
+  0,					/* properties_destroyed */
+  0,					/* todo_flags_start */
+  TODO_dump_func | TODO_verify_loops,	/* todo_flags_finish */
+  0				        /* letter */	
+};
 
 /* Loop nest optimizations.  */