[gomp] More IL work

[Diego Novillo <dnovillo at redhat dot com>]

This patch moves us closer into what I have in mind for
translating OpenMP pragmas into final code.  The general idea is
to wait until the lowering phases to do anything with the OpenMP
directives.

When we are converting into low-GIMPLE, the body of an OpenMP
directive is moved inside a separate function, and the local
variables referenced in the body of the directive are re-written
based on the data sharing and copying clauses.

So, for instance:

-----------------------------------------------------------------------------
foo()
{
  int n, t;

  #pragma omp parallel private (n, t)
    {
      t = ...;
      ... = n;
    }
}
-----------------------------------------------------------------------------

becomes

-----------------------------------------------------------------------------
foo()
{
  int n, t;

  GOMP_parallel_start (__gomp_fn.0, &gomp_data.10, 0);
  __gomp_fn.0 (&gomp_data.10);
  GOMP_parallel_end ();
}

__gomp_fn.0 (void *data)
{
  int n, t;

  t = ...;
  ... = n;
  return;
}
-----------------------------------------------------------------------------

The reason why we wait until lowering is that in the future, we
may want to build some concurrency analysis and transformations
(requiring concurrent CFGs and concurrent SSA forms).  All of
which is immensely simpler if we have all the code inside the
single function.

The patch is fairly incomplete.  Currently, the transformation is
done, the program links with libgomp, but the final binary gets
an illegal instruction fault if the program runs with more than 1
thread.

Also, when compiled with -O0, the compiler ICEs in make_decl_rtl
because the call graph code expands the newly created function
before we get a chance to run remap_locals_in_gomp_body.




	* cgraph.c (cgraph_add_new_function): New.
	* cgraph.h (cgraph_add_new_function): Declare.
	* gimple-low.c (struct remap_locals_d): Declare.
	(add_decls_to_set): New.
	(build_remap_info): New.
	(remap_locals_r): New.
	(remap_locals_in_gomp_body): New.
	(create_gomp_fn): New.
	(create_gomp_parallel_start): New.
	(create_gomp_parallel_end): New.
	(lower_gomp_expr): New.
	(lower_stmt): Call it.
	* gimplify.c (gimplify_gomp_parallel): Remove.
	(gimplify_expr): Don't gimplify GOMP_PARALLEL.
	* tree-gimple.c (is_gimple_stmt): Consider GOMP_PARALLEL
	to be GIMPLE.
	* tree.def (GOMP_CLAUSE_SHARED, GOMP_CLAUSE_FIRSTPRIVATE,
	GOMP_CLAUSE_LASTPRIVATE, GOMP_CLAUSE_REDUCTION,
	GOMP_CLAUSE_COPYPRIVATE,): Define.

Index: cgraph.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cgraph.c,v
retrieving revision 1.77.4.1
diff -d -u -p -r1.77.4.1 cgraph.c
--- cgraph.c	6 Jul 2005 17:37:49 -0000	1.77.4.1
+++ cgraph.c	13 Jul 2005 22:42:40 -0000
@@ -1027,4 +1027,28 @@ cgraph_variable_initializer_availability
   return AVAIL_AVAILABLE;
 }
 
+
+/* Add the function FNDECL to the call graph.  This assumes that the
+   body of FNDECL is in GENERIC form and ready to be processed by
+   cgraph_finalize_function.  */
+
+void
+cgraph_add_new_function (tree fndecl)
+{
+  struct function *saved_cfun = cfun;
+  tree saved_current_function_decl = current_function_decl;
+
+  /* Add the new body to the call graph.  */
+  allocate_struct_function (fndecl);
+  DECL_SOURCE_LOCATION (fndecl) = input_location;
+  cfun->function_end_locus = input_location;
+  current_function_decl = fndecl;
+  gimplify_function_tree (fndecl);
+  cgraph_finalize_function (fndecl, false);
+
+  /* Restore CFUN and CURRENT_FUNCTION_DECL.  */
+  cfun = saved_cfun;
+  current_function_decl = saved_current_function_decl;
+}
+
 #include "gt-cgraph.h"
Index: cgraph.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cgraph.h,v
retrieving revision 1.57.4.1
diff -d -u -p -r1.57.4.1 cgraph.h
--- cgraph.h	6 Jul 2005 17:37:49 -0000	1.57.4.1
+++ cgraph.h	13 Jul 2005 22:42:41 -0000
@@ -261,6 +261,7 @@ enum availability cgraph_function_body_a
 enum availability cgraph_variable_initializer_availability (struct cgraph_varpool_node *);
 bool cgraph_is_master_clone (struct cgraph_node *);
 struct cgraph_node *cgraph_master_clone (struct cgraph_node *);
+void cgraph_add_new_function (tree);
 
 /* In cgraphunit.c  */
 bool cgraph_assemble_pending_functions (void);
Index: gimple-low.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gimple-low.c,v
retrieving revision 2.24.4.1
diff -d -u -p -r2.24.4.1 gimple-low.c
--- gimple-low.c	6 Jul 2005 17:38:49 -0000	2.24.4.1
+++ gimple-low.c	13 Jul 2005 22:42:41 -0000
@@ -153,6 +153,282 @@ lower_stmt_body (tree expr, struct lower
     lower_stmt (&tsi, data);
 }
 
+
+/* Data structure used for remap_locals_r.  */
+
+struct remap_locals_d
+{
+  /* FUNCTION_DECL of the new artificial function containing the
+     pragma's body.  */
+  tree gomp_fn;
+  
+  /* Sets of DECLs representing the different data sharing clauses.  */
+  bitmap private;
+  bitmap firstprivate;
+  bitmap lastprivate;
+  bitmap shared;
+
+  /* Sets of DECLs representing the different data copying clauses.  */
+  bitmap copyin;
+  bitmap copyprivate;
+};
+  
+
+/* Add all the variables in LIST to the bitmap *SET_P.  Create a new
+   bitmap, if necessary.  */
+
+static void
+add_decls_to_set (bitmap *set_p, tree list)
+{
+  tree t;
+
+  if (*set_p == NULL)
+    *set_p = BITMAP_ALLOC (NULL);
+
+  for (t = list; t; t = TREE_CHAIN (t))
+    {
+      tree var = TREE_VALUE (t);
+      bitmap_set_bit (*set_p, DECL_UID (var));
+    }
+}
+
+
+/* Fill in all the data sharing and copying bitmaps in REMAP_INFO_P
+   using the clauses in LIST.  */
+
+static void
+build_remap_info (struct remap_locals_d *remap_info_p, tree list)
+{
+  tree c;
+
+  for (c = list; c; c = TREE_CHAIN (c))
+    {
+      tree clause = TREE_VALUE (c);
+      bitmap *set_p = NULL;
+
+      if (TREE_CODE (clause) == GOMP_CLAUSE_PRIVATE)
+	set_p = &remap_info_p->private;
+      else if (TREE_CODE (clause) == GOMP_CLAUSE_SHARED)
+	set_p = &remap_info_p->shared;
+      else if (TREE_CODE (clause) == GOMP_CLAUSE_FIRSTPRIVATE)
+	set_p = &remap_info_p->firstprivate;
+      else if (TREE_CODE (clause) == GOMP_CLAUSE_LASTPRIVATE)
+	set_p = &remap_info_p->lastprivate;
+      else if (TREE_CODE (clause) == GOMP_CLAUSE_COPYIN)
+	set_p = &remap_info_p->copyin;
+      else if (TREE_CODE (clause) == GOMP_CLAUSE_COPYPRIVATE)
+	set_p = &remap_info_p->copyprivate;
+
+      if (set_p)
+	add_decls_to_set (set_p, TREE_OPERAND (clause, 0));
+    }
+
+  /* FIXME.  Add checking code to disallow variables in multiple sets.
+     Variables may only appear in exactly one set, except for
+     firstprivate and lastprivate.  */
+}
+
+
+/* Callback for walk_tree to change the context of all the local
+   variables found in *TP accordingly to what is described by the
+   data clauses of DATA.GOMP_EXPR.  */
+
+static tree
+remap_locals_r (tree *tp, int *ws ATTRIBUTE_UNUSED, void *data)
+{
+  struct remap_locals_d *remap_info = (struct remap_locals_d *)data;
+  tree t, gomp_fn;
+
+  gomp_fn = remap_info->gomp_fn;
+
+  t = *tp;
+  if (TREE_CODE (t) == PARM_DECL)
+    {
+      gcc_unreachable ();
+    }
+  else if (TREE_CODE (t) == VAR_DECL
+           && !is_global_var (t)
+	   && decl_function_context (t) != gomp_fn)
+    {
+      struct function *f = DECL_STRUCT_FUNCTION (gomp_fn);
+      DECL_CONTEXT (t) = gomp_fn;
+      f->unexpanded_var_list = tree_cons (NULL_TREE, t, f->unexpanded_var_list);
+    }
+
+  return NULL;
+}
+
+
+/* Rewrite references to local variables inside the body of GOMP_EXPR
+   using the data sharing information from the directive clauses.
+   GOMP_FN is the compiler generated function that contains the body
+   of GOMP_EXPR.  */
+
+static void
+remap_locals_in_gomp_body (tree gomp_expr, tree gomp_fn)
+{
+  tree_stmt_iterator i;
+  struct remap_locals_d remap_info;
+  tree body = GOMP_PARALLEL_BODY (gomp_expr);
+
+  memset (&remap_info, 0, sizeof (remap_info));
+  remap_info.gomp_fn = gomp_fn;
+
+  /* Build the sets of data sharing clauses.  */
+  build_remap_info (&remap_info, GOMP_PARALLEL_CLAUSES (gomp_expr));
+
+  /* Rewrite all the private local variables so that their context is
+     GOMP_FN.  */
+  for (i = tsi_start (body); !tsi_end_p (i); tsi_next (&i))
+    walk_tree (tsi_stmt_ptr (i), remap_locals_r, &remap_info, NULL);
+
+  /* Add initialization/finalization code in GOMP_FN to model copyin,
+     firstprivate and lastprivate.  */
+}
+
+
+/* Build a new nested function to hold the body of GOMP_EXPR (an
+   OpenMP pragma).  The new function is added to the call graph and
+   the FUNCTION_DECL representing it, returned.  */
+
+static tree
+create_gomp_fn (tree gomp_expr)
+{
+  char *fn_name;
+  static unsigned int num = 0;
+  tree fn_type, fn_body, fn_decl, res_decl;
+  tree fn_data_arg;
+
+  /* Enclose the body in a BIND_EXPR, if it doesn't have one already.  */
+  fn_body = GOMP_PARALLEL_BODY (gomp_expr);
+  if (TREE_CODE (fn_body) != BIND_EXPR)
+    {
+      fn_body = build3 (BIND_EXPR, void_type_node, NULL, fn_body, NULL);
+      TREE_SIDE_EFFECTS (fn_body) = 1;
+    }
+
+  /* Build the declaration of the new function.  */
+  ASM_FORMAT_PRIVATE_NAME (fn_name, "__gomp_fn", num++);
+  fn_type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE);
+  fn_decl = build_fn_decl (fn_name, fn_type);
+  res_decl = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
+
+  /* Initialize attributes for the result and the function.  */
+  DECL_ARTIFICIAL (res_decl) = 1;
+  DECL_IGNORED_P (res_decl) = 1;
+  DECL_RESULT (fn_decl) = res_decl;
+
+  TREE_STATIC (fn_decl) = 0;
+  TREE_USED (fn_decl) = 1;
+  DECL_ARTIFICIAL (fn_decl) = 1;
+  DECL_IGNORED_P (fn_decl) = 0;
+  TREE_PUBLIC (fn_decl) = 0;
+  DECL_UNINLINABLE (fn_decl) = 1;
+  DECL_EXTERNAL (fn_decl) = 0;
+  DECL_CONTEXT (fn_decl) = NULL_TREE;
+
+  DECL_INITIAL (fn_decl) = make_node (BLOCK);
+  TREE_USED (DECL_INITIAL (fn_decl)) = 1;
+  gcc_assert (TREE_CODE (fn_body) == BIND_EXPR);
+  DECL_SAVED_TREE (fn_decl) = fn_body;
+
+  /* Add the argument DATA.  */
+  fn_data_arg = build_decl (PARM_DECL, get_identifier ("data"), ptr_type_node);
+  DECL_ARGUMENTS (fn_decl) = fn_data_arg;
+
+  /* Add FN_DECL to the call graph.  */
+  cgraph_add_new_function (fn_decl);
+
+  /* Remap local variables according to the data clauses.  */
+  remap_locals_in_gomp_body (gomp_expr, fn_decl);
+
+  return fn_decl;
+}
+
+
+/* Build and return the call GOMP_parallel_start (FN, DATA, NUM_THREADS).  */
+
+static tree
+create_gomp_parallel_start (tree fn, tree data, tree num_threads)
+{
+  tree lib_fn, args, type;
+
+  type = build_function_type_list (void_type_node,
+				   TREE_TYPE (fn),
+				   ptr_type_node,
+				   unsigned_type_node,
+				   NULL_TREE);
+
+  lib_fn = build_fn_decl ("GOMP_parallel_start", type);
+  args = tree_cons (NULL_TREE, fn,
+		    tree_cons (NULL_TREE, data,
+			       tree_cons (NULL_TREE, num_threads,
+					  NULL_TREE)));
+
+  return build_function_call_expr (lib_fn, args);
+}
+
+
+/* Build and return a call to GOMP_parallel_end().  */
+
+static tree
+create_gomp_parallel_end (void)
+{
+  tree fn, type;
+
+  type = build_function_type_list (void_type_node, void_type_node, NULL_TREE);
+  fn = build_fn_decl ("GOMP_parallel_end", type);
+  return build_function_call_expr (fn, NULL_TREE);
+}
+
+
+/* Lower the OpenMP pragma pointed by TSI.  Build a new function with
+   the body of the pragma and emit the appropriate runtime call.  DATA
+   contains locus and scope information for TSI.  */
+
+static void
+lower_gomp_expr (tree_stmt_iterator *tsi)
+{
+  tree stmt, fn, call, args, num_threads, data_arg, addr_data_arg;
+  tree_stmt_iterator orig_tsi;
+
+  stmt = tsi_stmt (*tsi);
+
+  /* Build the local temporary GOMP_DATA that will contain all the
+     local state that we need to send to the child thread.
+     FIXME, structure creation and initialization not implemented yet.  */
+  data_arg = create_tmp_var (integer_type_node, "gomp_data");
+  addr_data_arg = build1 (ADDR_EXPR, build_pointer_type (integer_type_node),
+                          data_arg);
+  TREE_ADDRESSABLE (data_arg) = 1;
+
+  /* Build a new function out of the pragma's body and add it to the
+     call graph as a nested function of the current function.  */
+  fn = create_gomp_fn (stmt);
+
+  /* Emit GOMP_parallel_start (__gomp_fn.XXXX ...) to PRE_P.  FIXME,
+     num_threads should only be integer_zero_node if the clause
+     num_threads is not present.  */
+  num_threads = integer_zero_node;
+  call = create_gomp_parallel_start (fn, addr_data_arg, num_threads);
+  tsi_link_before (tsi, call, TSI_CONTINUE_LINKING);
+
+  /* Emit __gomp_fn.XXXX (&gomp_data).  */
+  args = tree_cons (NULL_TREE, addr_data_arg, NULL_TREE);
+  call = build_function_call_expr (fn, args);
+  tsi_link_after (tsi, call, TSI_NEW_STMT);
+
+  /* Emit GOMP_parallel_end ().  */
+  call = create_gomp_parallel_end ();
+  tsi_link_after (tsi, call, TSI_NEW_STMT);
+
+  /* Remove the original statement.  */
+  orig_tsi = *tsi;
+  tsi_next (&orig_tsi);
+  tsi_delink (&orig_tsi);
+}
+
+
 /* Lowers statement TSI.  DATA is passed through the recursion.  */
 
 static void
@@ -196,6 +472,10 @@ lower_stmt (tree_stmt_iterator *tsi, str
     case SWITCH_EXPR:
       break;
 
+    case GOMP_PARALLEL:
+      lower_gomp_expr (tsi);
+      break;
+
     default:
 #ifdef ENABLE_CHECKING
       print_node_brief (stderr, "", stmt, 0);
Index: gimplify.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gimplify.c,v
retrieving revision 2.135.4.3
diff -d -u -p -r2.135.4.3 gimplify.c
--- gimplify.c	12 Jul 2005 14:20:17 -0000	2.135.4.3
+++ gimplify.c	13 Jul 2005 22:42:42 -0000
@@ -3863,54 +3863,41 @@ gimplify_to_stmt_list (tree *stmt_p)
 }
 
 
+#if 0
 /* Gimplify an OpenMP parallel section (GOMP_PARALLEL).  This builds a
-   new function __gomp_fn.XXXXX that encapsulates the body of the
+   new nested function __gomp_fn.XXXXX that encapsulates the body of the
    directive, and emits the following code:
 
    	GOMP_parallel_start (__gomp_fn.XXXX, ...);
-	__gomp_fn.XXXX (NULL);
+	__gomp_fn.XXXX ();
 	GOMP_parallel_end ();
 */
 
 static enum gimplify_status
 gimplify_gomp_parallel (tree *expr_p, tree *pre_p, tree *post_p)
 {
-  tree fn_type, fn, lib_fn_type, lib_fn, args;
-  char *fn_name;
-  static unsigned int num;
+  tree fn, lib_fn, num_threads;
 
-  /* Build a new function out of the pragma's body.  */
-  fn_type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE);
-  ASM_FORMAT_PRIVATE_NAME (fn_name, "__gomp_fn", num++);
-  fn = build_fn_decl (fn_name, fn_type);
+  /* Build a new function out of the pragma's body and add it to the
+     call graph as a nested function of the current function.  */
+  fn = create_gomp_fn (*expr_p);
 
   /* Emit GOMP_parallel_start (__gomp_fn.XXXX ...) to PRE_P.  */
-  lib_fn_type = build_function_type_list (void_type_node,
-					  fn_type,
-                                          ptr_type_node,
-					  unsigned_type_node,
-					  NULL_TREE);
-  lib_fn = build_fn_decl ("GOMP_parallel_start", lib_fn_type);
-  args = tree_cons (NULL_TREE, fn,
-		    tree_cons (NULL_TREE, null_pointer_node,
-			       tree_cons (NULL_TREE, integer_one_node,
-					  NULL_TREE)));
+  num_threads = build_int_cst (unsigned_type_node, 2);
+  lib_fn = create_gomp_parallel_start (fn, null_pointer_node, num_threads);
+  append_to_statement_list (lib_fn, pre_p);
 
-  append_to_statement_list (build_function_call_expr (lib_fn, args), pre_p);
+  /* Replace EXPR_P with __gomp_fn.XXXX ().  */
+  *expr_p = build_function_call_expr (fn, NULL_TREE);
 
   /* Emit GOMP_parallel_end () to POST_P.  */
-  lib_fn_type = build_function_type_list (void_type_node, void_type_node,
-					  NULL_TREE);
-  lib_fn = build_fn_decl ("GOMP_parallel_end", lib_fn_type);
-  args = NULL_TREE;
-  append_to_statement_list (build_function_call_expr (lib_fn, args), post_p);
-
-  /* Replace EXPR_P with __gomp_fn.XXXX ().  */
-  args = NULL_TREE;
-  *expr_p = build_function_call_expr (fn, args);
+  lib_fn = create_gomp_parallel_end ();
+  append_to_statement_list (lib_fn, post_p);
 
   return GS_ALL_DONE;
 }
+#endif
+
 
 /*  Gimplifies the expression tree pointed by EXPR_P.  Return 0 if
     gimplification failed.
@@ -4350,7 +4337,7 @@ gimplify_expr (tree *expr_p, tree *pre_p
 	  break;
 
 	case GOMP_PARALLEL:
-	  ret = gimplify_gomp_parallel (expr_p, pre_p, post_p);
+	  ret = GS_ALL_DONE;
 	  break;
 
 	default:
Index: tree-gimple.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-gimple.c,v
retrieving revision 2.38.4.2
diff -d -u -p -r2.38.4.2 tree-gimple.c
--- tree-gimple.c	12 Jul 2005 14:20:38 -0000	2.38.4.2
+++ tree-gimple.c	13 Jul 2005 22:42:42 -0000
@@ -218,6 +218,7 @@ is_gimple_stmt (tree t)
     case RESX_EXPR:
     case PHI_NODE:
     case STATEMENT_LIST:
+    case GOMP_PARALLEL:
       /* These are always void.  */
       return true;
 
Index: tree.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.def,v
retrieving revision 1.116.4.3
diff -d -u -p -r1.116.4.3 tree.def
--- tree.def	6 Jul 2005 17:39:51 -0000	1.116.4.3
+++ tree.def	13 Jul 2005 22:42:43 -0000
@@ -988,11 +988,26 @@ DEFTREECODE (GOMP_BARRIER, "gomp_barrier
    Operand 1: GOMP_ORDERED_BODY: Body to be executed sequentially.  */
 DEFTREECODE (GOMP_ORDERED, "gomp_ordered", tcc_expression, 1)
 
+/* OpenMP clause: private (variable_list).  */
+DEFTREECODE (GOMP_CLAUSE_PRIVATE, "private", tcc_expression, 1)
+
+/* OpenMP clause: shared (variable_list).  */
+DEFTREECODE (GOMP_CLAUSE_SHARED, "shared", tcc_expression, 1)
+
+/* OpenMP clause: firstprivate (variable_list).  */
+DEFTREECODE (GOMP_CLAUSE_FIRSTPRIVATE, "firstprivate", tcc_expression, 1)
+
+/* OpenMP clause: lastprivate (variable_list).  */
+DEFTREECODE (GOMP_CLAUSE_LASTPRIVATE, "lastprivate", tcc_expression, 1)
+
+/* OpenMP clause: reduction (operator:variable_list).  */
+DEFTREECODE (GOMP_CLAUSE_REDUCTION, "reduction", tcc_expression, 2)
+
 /* OpenMP clause: copyin (variable_list).  */
 DEFTREECODE (GOMP_CLAUSE_COPYIN, "copyin", tcc_expression, 1)
 
-/* OpenMP clause: private (variable_list).  */
-DEFTREECODE (GOMP_CLAUSE_PRIVATE, "private", tcc_expression, 1)
+/* OpenMP clause: copyprivate (variable_list).  */
+DEFTREECODE (GOMP_CLAUSE_COPYPRIVATE, "copyprivate", tcc_expression, 1)
 
 /* Reduction operations. 
    Operations that take a vector of elements and "reduce" it to a scalar