CbC/CbC_gcc: gcc/graphite-clast-to-gimple.c comparison

comparison gcc/graphite-clast-to-gimple.c @ 63:b7f97abdc517 gcc-4.6-20100522

update gcc from gcc-4.5.0 to gcc-4.6

author	ryoma <e075725@ie.u-ryukyu.ac.jp>
date	Mon, 24 May 2010 12:47:05 +0900
parents	77e2b8dfacca
children	f6334be47118

comparison

equal deleted inserted replaced

-:3c8a44c06a95
+:b7f97abdc517
 /* Translation of CLAST (CLooG AST) to Gimple.
-Copyright (C) 2009 Free Software Foundation, Inc.
+Copyright (C) 2009, 2010 Free Software Foundation, Inc.
 Contributed by Sebastian Pop <sebastian.pop@amd.com>.
 This file is part of GCC.
 GCC is free software; you can redistribute it and/or modify
 #include "tree-pass.h"
 #include "domwalk.h"
 #include "value-prof.h"
 #include "pointer-set.h"
 #include "gimple.h"
+#include "langhooks.h"
 #include "sese.h"
 #ifdef HAVE_cloog
 #include "cloog/cloog.h"
 #include "ppl_c.h"
 #include "graphite-poly.h"
 #include "graphite-scop-detection.h"
 #include "graphite-clast-to-gimple.h"
 #include "graphite-dependences.h"
+/* This flag is set when an error occurred during the translation of
+CLAST to Gimple.  */
+static bool gloog_error;
 /* Verifies properties that GRAPHITE should maintain during translation.  */
 static inline void
 graphite_verify (void)
 {
 #ifdef ENABLE_CHECKING
 verify_loop_structure ();
 verify_dominators (CDI_DOMINATORS);
 verify_dominators (CDI_POST_DOMINATORS);
-verify_ssa (false);
+verify_loop_closed_ssa (true);
-verify_loop_closed_ssa ();
 #endif
 }
 /* Stores the INDEX in a vector for a given clast NAME.  */
 tmp.name = name;
 slot = htab_find_slot (index_table, &tmp, INSERT);
 if (slot)
-*slot = new_clast_name_index (name, index);
+{
+if (*slot)
+	free (*slot);
+*slot = new_clast_name_index (name, index);
+}
 }
 /* Print to stderr the element ELT.  */
 static inline void
 gcc_assert (index >= 0);
 return newivs_to_depth_to_newiv (newivs, index);
 }
-/* Returns the maximal precision type for expressions E1 and E2.  */
+/* Returns the signed maximal precision type for expressions TYPE1 and TYPE2.  */
-static inline tree
+static tree
-max_precision_type (tree e1, tree e2)
+max_signed_precision_type (tree type1, tree type2)
 {
-tree type1 = TREE_TYPE (e1);
+int p1 = TYPE_PRECISION (type1);
-tree type2 = TREE_TYPE (e2);
+int p2 = TYPE_PRECISION (type2);
+int precision;
+tree type;
+if (p1 > p2)
+precision = TYPE_UNSIGNED (type1) ? p1 * 2 : p1;
+else
+precision = TYPE_UNSIGNED (type2) ? p2 * 2 : p2;
+type = lang_hooks.types.type_for_size (precision, false);
+if (!type)
+{
+gloog_error = true;
+return integer_type_node;
+}
+return type;
+}
+/* Returns the maximal precision type for expressions TYPE1 and TYPE2.  */
+static tree
+max_precision_type (tree type1, tree type2)
+{
+if (POINTER_TYPE_P (type1))
+return type1;
+if (POINTER_TYPE_P (type2))
+return type2;
+if (!TYPE_UNSIGNED (type1)
+|| !TYPE_UNSIGNED (type2))
+return max_signed_precision_type (type1, type2);
 return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
 }
 static tree
 clast_to_gcc_expression (tree, struct clast_expr *, sese, VEC (tree, heap) *,
 {
 	struct clast_term *t = (struct clast_term *) e;
 	if (t->var)
 	  {
-	    if (value_one_p (t->val))
+	    if (mpz_cmp_si (t->val, 1) == 0)
 	      {
 		tree name = clast_name_to_gcc (t->var, region, newivs,
 					       newivs_index, params_index);
-		return fold_convert (type, name);
+		if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
+		  name = fold_convert (sizetype, name);
+		name = fold_convert (type, name);
+		return name;
 	      }
-	    else if (value_mone_p (t->val))
+	    else if (mpz_cmp_si (t->val, -1) == 0)
 	      {
 		tree name = clast_name_to_gcc (t->var, region, newivs,
 					       newivs_index, params_index);
+		if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
+		  name = fold_convert (sizetype, name);
 		name = fold_convert (type, name);
 		return fold_build1 (NEGATE_EXPR, type, name);
 	      }
 	    else
 	      {
 		tree name = clast_name_to_gcc (t->var, region, newivs,
 					       newivs_index, params_index);
 		tree cst = gmp_cst_to_tree (type, t->val);
+		if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
+		  name = fold_convert (sizetype, name);
 		name = fold_convert (type, name);
-		return fold_build2 (MULT_EXPR, type, cst, name);
+		if (!POINTER_TYPE_P (type))
+		  return fold_build2 (MULT_EXPR, type, cst, name);
+		gloog_error = true;
+		return cst;
 	      }
 	  }
 	else
 	  return gmp_cst_to_tree (type, t->val);
 }
 }
 return NULL_TREE;
 }
-/* Returns the type for the expression E.  */
+/* Return the precision needed to represent the value VAL.  */
+static int
+precision_for_value (mpz_t val)
+{
+mpz_t x, y, two;
+int precision;
+value_init (x);
+value_init (y);
+value_init (two);
+value_set_si (x, 2);
+value_assign (y, val);
+value_set_si (two, 2);
+precision = 1;
+if (value_neg_p (y))
+value_oppose (y, y);
+while (value_gt (y, x))
+{
+value_multiply (x, x, two);
+precision++;
+}
+value_clear (x);
+value_clear (y);
+value_clear (two);
+return precision;
+}
+/* Return the precision needed to represent the values between LOW and
+UP.  */
+static int
+precision_for_interval (mpz_t low, mpz_t up)
+{
+mpz_t diff;
+int precision;
+gcc_assert (value_le (low, up));
+value_init (diff);
+value_subtract (diff, up, low);
+precision = precision_for_value (diff);
+value_clear (diff);
+return precision;
+}
+/* Return a type that could represent the integer value VAL, or
+otherwise return NULL_TREE.  */
+static tree
+gcc_type_for_interval (mpz_t low, mpz_t up, tree old_type)
+{
+bool unsigned_p = true;
+int precision, prec_up, prec_int;
+tree type;
+gcc_assert (value_le (low, up));
+/* Preserve the signedness of the old IV.  */
+if ((old_type && !TYPE_UNSIGNED (old_type))
+|| value_neg_p (low))
+unsigned_p = false;
+prec_up = precision_for_value (up);
+prec_int = precision_for_interval (low, up);
+precision = prec_up > prec_int ? prec_up : prec_int;
+type = lang_hooks.types.type_for_size (precision, unsigned_p);
+if (!type)
+{
+gloog_error = true;
+return integer_type_node;
+}
+return type;
+}
+/* Return a type that could represent the integer value VAL, or
+otherwise return NULL_TREE.  */
+static tree
+gcc_type_for_value (mpz_t val)
+{
+return gcc_type_for_interval (val, val, NULL_TREE);
+}
+/* Return the type for the clast_term T used in STMT.  */
+static tree
+gcc_type_for_clast_term (struct clast_term *t,
+			 sese region, VEC (tree, heap) *newivs,
+			 htab_t newivs_index, htab_t params_index)
+{
+gcc_assert (t->expr.type == expr_term);
+if (!t->var)
+return gcc_type_for_value (t->val);
+return TREE_TYPE (clast_name_to_gcc (t->var, region, newivs,
+				       newivs_index, params_index));
+}
+static tree
+gcc_type_for_clast_expr (struct clast_expr *, sese,
+			 VEC (tree, heap) *, htab_t, htab_t);
+/* Return the type for the clast_reduction R used in STMT.  */
+static tree
+gcc_type_for_clast_red (struct clast_reduction *r, sese region,
+			VEC (tree, heap) *newivs,
+			htab_t newivs_index, htab_t params_index)
+{
+int i;
+tree type = NULL_TREE;
+if (r->n == 1)
+return gcc_type_for_clast_expr (r->elts[0], region, newivs,
+				    newivs_index, params_index);
+switch (r->type)
+{
+case clast_red_sum:
+case clast_red_min:
+case clast_red_max:
+type = gcc_type_for_clast_expr (r->elts[0], region, newivs,
+				      newivs_index, params_index);
+for (i = 1; i < r->n; i++)
+	type = max_precision_type (type, gcc_type_for_clast_expr
+				   (r->elts[i], region, newivs,
+				    newivs_index, params_index));
+return type;
+default:
+break;
+}
+gcc_unreachable ();
+return NULL_TREE;
+}
+/* Return the type for the clast_binary B used in STMT.  */
+static tree
+gcc_type_for_clast_bin (struct clast_binary *b,
+			sese region, VEC (tree, heap) *newivs,
+			htab_t newivs_index, htab_t params_index)
+{
+tree l = gcc_type_for_clast_expr ((struct clast_expr *) b->LHS, region,
+				    newivs, newivs_index, params_index);
+tree r = gcc_type_for_value (b->RHS);
+return max_signed_precision_type (l, r);
+}
+/* Returns the type for the CLAST expression E when used in statement
+STMT.  */
 static tree
 gcc_type_for_clast_expr (struct clast_expr *e,
 			 sese region, VEC (tree, heap) *newivs,
 			 htab_t newivs_index, htab_t params_index)
 {
 switch (e->type)
 {
 case expr_term:
-{
+return gcc_type_for_clast_term ((struct clast_term *) e, region,
-	struct clast_term *t = (struct clast_term *) e;
+				      newivs, newivs_index, params_index);
-	if (t->var)
-	  return TREE_TYPE (clast_name_to_gcc (t->var, region, newivs,
-					       newivs_index, params_index));
-	else
-	  return NULL_TREE;
-}
 case expr_red:
-{
+return gcc_type_for_clast_red ((struct clast_reduction *) e, region,
-struct clast_reduction *r = (struct clast_reduction *) e;
+				     newivs, newivs_index, params_index);
-	if (r->n == 1)
-	  return gcc_type_for_clast_expr (r->elts[0], region, newivs,
-					  newivs_index, params_index);
-	else
-	  {
-	    int i;
-	    for (i = 0; i < r->n; i++)
-	      {
-		tree type = gcc_type_for_clast_expr (r->elts[i], region,
-						     newivs, newivs_index,
-						     params_index);
-		if (type)
-		  return type;
-	      }
-	    return NULL_TREE;
-	  }
-}
 case expr_bin:
-{
+return gcc_type_for_clast_bin ((struct clast_binary *) e, region,
-	struct clast_binary *b = (struct clast_binary *) e;
+				     newivs, newivs_index, params_index);
-	struct clast_expr *lhs = (struct clast_expr *) b->LHS;
-	return gcc_type_for_clast_expr (lhs, region, newivs,
-					newivs_index, params_index);
-}
 default:
 gcc_unreachable ();
 }
 static tree
 gcc_type_for_clast_eq (struct clast_equation *cleq,
 		       sese region, VEC (tree, heap) *newivs,
 		       htab_t newivs_index, htab_t params_index)
 {
-tree type = gcc_type_for_clast_expr (cleq->LHS, region, newivs,
+tree l = gcc_type_for_clast_expr (cleq->LHS, region, newivs,
-				       newivs_index, params_index);
+				    newivs_index, params_index);
-if (type)
+tree r = gcc_type_for_clast_expr (cleq->RHS, region, newivs,
-return type;
+				    newivs_index, params_index);
+return max_precision_type (l, r);
-return gcc_type_for_clast_expr (cleq->RHS, region, newivs, newivs_index,
-				  params_index);
 }
 /* Translates a clast equation CLEQ to a tree.  */
 static tree
 						    newivs_index, params_index);
 edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
 return exit_edge;
 }
+/* Compute the lower bound LOW and upper bound UP for the induction
+variable at LEVEL for the statement PBB, based on the transformed
+scattering of PBB: T|I|G|Cst, with T the scattering transform, I
+the iteration domain, and G the context parameters.  */
+static void
+compute_bounds_for_level (poly_bb_p pbb, int level, mpz_t low, mpz_t up)
+{
+ppl_Pointset_Powerset_C_Polyhedron_t ps;
+ppl_Linear_Expression_t le;
+combine_context_id_scat (&ps, pbb, false);
+/* Prepare the linear expression corresponding to the level that we
+want to maximize/minimize.  */
+{
+ppl_dimension_type dim = pbb_nb_scattering_transform (pbb)
++ pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
+ppl_new_Linear_Expression_with_dimension (&le, dim);
+ppl_set_coef (le, 2 * level + 1, 1);
+}
+ppl_max_for_le_pointset (ps, le, up);
+ppl_min_for_le_pointset (ps, le, low);
+}
+/* Compute the type for the induction variable at LEVEL for the
+statement PBB, based on the transformed schedule of PBB.  OLD_TYPE
+is the type of the old induction variable for that loop.  */
+static tree
+compute_type_for_level_1 (poly_bb_p pbb, int level, tree old_type)
+{
+mpz_t low, up;
+tree type;
+value_init (low);
+value_init (up);
+compute_bounds_for_level (pbb, level, low, up);
+type = gcc_type_for_interval (low, up, old_type);
+value_clear (low);
+value_clear (up);
+return type;
+}
+/* Compute the type for the induction variable at LEVEL for the
+statement PBB, based on the transformed schedule of PBB.  */
+static tree
+compute_type_for_level (poly_bb_p pbb, int level)
+{
+tree oldiv = pbb_to_depth_to_oldiv (pbb, level);
+tree type = TREE_TYPE (oldiv);
+if (type && POINTER_TYPE_P (type))
+{
+#ifdef ENABLE_CHECKING
+tree ctype = compute_type_for_level_1 (pbb, level, type);
+/* In the case of a pointer type, check that after the loop
+	 transform, the lower and the upper bounds of the type fit the
+	 oldiv pointer type.  */
+gcc_assert (TYPE_PRECISION (type) >= TYPE_PRECISION (ctype)
+		  && integer_zerop (lower_bound_in_type (ctype, ctype)));
+#endif
+return type;
+}
+return compute_type_for_level_1 (pbb, level, type);
+}
 /* Walks a CLAST and returns the first statement in the body of a
 loop.  */
 static struct clast_user_stmt *
 clast_get_body_of_loop (struct clast_stmt *stmt)
 return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
 gcc_unreachable ();
 }
-/* Given a CLOOG_IV, returns the type that it should have in GCC land.
+/* Returns the type for the induction variable for the loop translated
-If the information is not available, i.e. in the case one of the
+from STMT_FOR.  */
-transforms created the loop, just return integer_type_node.  */
+static tree
-static tree
+gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for, int level,
-gcc_type_for_cloog_iv (const char *cloog_iv, gimple_bb_p gbb)
+			       tree lb_type, tree ub_type)
-{
-struct ivtype_map_elt_s tmp;
-PTR *slot;
-tmp.cloog_iv = cloog_iv;
-slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, NO_INSERT);
-if (slot && *slot)
-return ((ivtype_map_elt) *slot)->type;
-return integer_type_node;
-}
-/* Returns the induction variable for the loop that gets translated to
-STMT.  */
-static tree
-gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for)
 {
 struct clast_stmt *stmt = (struct clast_stmt *) stmt_for;
 struct clast_user_stmt *body = clast_get_body_of_loop (stmt);
-const char *cloog_iv = stmt_for->iterator;
 CloogStatement *cs = body->statement;
 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
-return gcc_type_for_cloog_iv (cloog_iv, PBB_BLACK_BOX (pbb));
+return max_signed_precision_type (lb_type, max_precision_type
+				    (ub_type, compute_type_for_level
+				     (pbb, level - 1)));
 }
 /* Creates a new LOOP corresponding to Cloog's STMT.  Inserts an
 induction variable for the new LOOP.  New LOOP is attached to CFG
 starting at ENTRY_EDGE.  LOOP is inserted into the loop tree and
 static struct loop *
 graphite_create_new_loop (sese region, edge entry_edge,
 			  struct clast_for *stmt,
 			  loop_p outer, VEC (tree, heap) **newivs,
-			  htab_t newivs_index, htab_t params_index)
+			  htab_t newivs_index, htab_t params_index, int level)
 {
-tree type = gcc_type_for_iv_of_clast_loop (stmt);
+tree lb_type = gcc_type_for_clast_expr (stmt->LB, region, *newivs,
+					  newivs_index, params_index);
+tree ub_type = gcc_type_for_clast_expr (stmt->UB, region, *newivs,
+					  newivs_index, params_index);
+tree type = gcc_type_for_iv_of_clast_loop (stmt, level, lb_type, ub_type);
 tree lb = clast_to_gcc_expression (type, stmt->LB, region, *newivs,
 				     newivs_index, params_index);
 tree ub = clast_to_gcc_expression (type, stmt->UB, region, *newivs,
 				     newivs_index, params_index);
 tree stride = gmp_cst_to_tree (type, stmt->stride);
 PTR *x;
 tmp.old_name = old_name;
 x = htab_find_slot (res, &tmp, INSERT);
-if (!*x)
+if (x && !*x)
 *x = new_rename_map_elt (old_name, expr);
 return 1;
 }
 PTR *x;
 tmp.bb = bb;
 x = htab_find_slot (bb_pbb_mapping, &tmp, INSERT);
-if (!*x)
+if (x && !*x)
 *x = new_bb_pbb_def (bb, pbb);
 }
 /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING.  */
 return false;
 }
 static edge
-translate_clast (sese, struct clast_stmt *, edge, htab_t, VEC (tree, heap) **,
+translate_clast (sese, loop_p, struct clast_stmt *, edge, htab_t,
-		 htab_t, htab_t, htab_t);
+		 VEC (tree, heap) **, htab_t, htab_t, int, htab_t);
 /* Translates a clast user statement STMT to gimple.
 - REGION is the sese region we used to generate the scop.
 - NEXT_E is the edge where new generated code should be attached.
+- CONTEXT_LOOP is the loop in which the generated code will be placed
 - RENAME_MAP contains a set of tuples of new names associated to
 the original variables names.
 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
 the sese region.  */
 translate_clast_user (sese region, struct clast_user_stmt *stmt, edge next_e,
 		      htab_t rename_map, VEC (tree, heap) **newivs,
 		      htab_t newivs_index, htab_t bb_pbb_mapping,
 		      htab_t params_index)
 {
+gimple_bb_p gbb;
+basic_block new_bb;
 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (stmt->statement);
-gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
+gbb = PBB_BLACK_BOX (pbb);
 if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
 return next_e;
 build_iv_mapping (rename_map, region, *newivs, newivs_index, stmt,
 		    params_index);
 next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), region,
 					   next_e, rename_map);
-mark_bb_with_pbb (pbb, next_e->src, bb_pbb_mapping);
+new_bb = next_e->src;
+mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping);
 update_ssa (TODO_update_ssa);
 return next_e;
 }
-/* Mark a loop parallel, if the graphite dependency check cannot find any
-dependencies.  This triggers parallel code generation in the autopar pass.
-*/
-static void
-try_mark_loop_parallel (sese region, loop_p loop, htab_t bb_pbb_mapping)
-{
-loop_p outermost_loop =  SESE_ENTRY (region)->src->loop_father;
-int level = loop_depth (loop) - loop_depth (outermost_loop);
-if (flag_loop_parallelize_all
-&& !dependency_in_loop_p (loop, bb_pbb_mapping,
-	get_scattering_level (level)))
-loop->can_be_parallel = true;
-}
-static tree gcc_type_for_iv_of_clast_loop (struct clast_for *);
 /* Creates a new if region protecting the loop to be executed, if the execution
 count is zero (lb > ub).  */
 static edge
 graphite_create_new_loop_guard (sese region, edge entry_edge,
 				VEC (tree, heap) *newivs,
 				htab_t newivs_index, htab_t params_index)
 {
 tree cond_expr;
 edge exit_edge;
-tree type = gcc_type_for_iv_of_clast_loop (stmt);
+tree lb_type = gcc_type_for_clast_expr (stmt->LB, region, newivs,
+					  newivs_index, params_index);
+tree ub_type = gcc_type_for_clast_expr (stmt->UB, region, newivs,
+					  newivs_index, params_index);
+tree type = max_precision_type (lb_type, ub_type);
 tree lb = clast_to_gcc_expression (type, stmt->LB, region, newivs,
 				     newivs_index, params_index);
 tree ub = clast_to_gcc_expression (type, stmt->UB, region, newivs,
 				     newivs_index, params_index);
+tree ub_one;
-/* XXX: Adding +1 and using LT_EXPR helps with loop latches that have a
+/* Adding +1 and using LT_EXPR helps with loop latches that have a
 loop iteration count of "PARAMETER - 1".  For PARAMETER == 0 this becomes
 2^{32|64}, and the condition lb <= ub is true, even if we do not want this.
-However lb < ub + 1 is false, as expected.
+However lb < ub + 1 is false, as expected.  */
-There might be a problem with cases where ub is 2^32.  */
 tree one;
-Value gmp_one;
+mpz_t gmp_one;
-value_init (gmp_one);
-value_set_si (gmp_one, 1);
+mpz_init (gmp_one);
+mpz_set_si (gmp_one, 1);
 one = gmp_cst_to_tree (type, gmp_one);
-value_clear (gmp_one);
+mpz_clear (gmp_one);
-ub = fold_build2 (PLUS_EXPR, type, ub, one);
+ub_one = fold_build2 (POINTER_TYPE_P (type) ? POINTER_PLUS_EXPR : PLUS_EXPR,
-cond_expr = fold_build2 (LT_EXPR, boolean_type_node, lb, ub);
+			type, ub, one);
+/* When ub + 1 wraps around, use lb <= ub.  */
+if (integer_zerop (ub_one))
+cond_expr = fold_build2 (LE_EXPR, boolean_type_node, lb, ub);
+else
+cond_expr = fold_build2 (LT_EXPR, boolean_type_node, lb, ub_one);
 exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
 return exit_edge;
 }
 the original variables names.
 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
 the sese region.  */
 static edge
-translate_clast_for_loop (sese region, struct clast_for *stmt, edge next_e,
+translate_clast_for_loop (sese region, loop_p context_loop,
-		     htab_t rename_map, VEC (tree, heap) **newivs,
+			  struct clast_for *stmt, edge next_e,
-		     htab_t newivs_index, htab_t bb_pbb_mapping,
+			  htab_t rename_map, VEC (tree, heap) **newivs,
-		     htab_t params_index)
+			  htab_t newivs_index, htab_t bb_pbb_mapping,
-{
+			  int level, htab_t params_index)
-loop_p context_loop = next_e->dest->loop_father;
+{
-loop_p loop = graphite_create_new_loop (region, next_e, stmt, context_loop,
+struct loop *loop = graphite_create_new_loop (region, next_e, stmt,
-					  newivs, newivs_index, params_index);
+						context_loop, newivs,
+						newivs_index, params_index,
+						level);
 edge last_e = single_exit (loop);
-edge body = single_succ_edge (loop->header);
+edge to_body = single_succ_edge (loop->header);
+basic_block after = to_body->dest;
-next_e = translate_clast (region, stmt->body, body, rename_map, newivs,
-			    newivs_index, bb_pbb_mapping, params_index);
 /* Create a basic block for loop close phi nodes.  */
 last_e = single_succ_edge (split_edge (last_e));
+/* Translate the body of the loop.  */
+next_e = translate_clast (region, loop, stmt->body, to_body, rename_map,
+			    newivs, newivs_index, bb_pbb_mapping, level + 1,
+			    params_index);
+redirect_edge_succ_nodup (next_e, after);
+set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
+/* Remove from rename_map all the tuples containing variables
+defined in loop's body.  */
 insert_loop_close_phis (rename_map, loop);
-try_mark_loop_parallel (region, loop, bb_pbb_mapping);
+if (flag_loop_parallelize_all
+&& !dependency_in_loop_p (loop, bb_pbb_mapping,
+				get_scattering_level (level)))
+loop->can_be_parallel = true;
 return last_e;
 }
 /* Translates a clast for statement STMT to gimple.  First a guard is created
 the original variables names.
 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
 the sese region.  */
 static edge
-translate_clast_for (sese region, struct clast_for *stmt, edge next_e,
+translate_clast_for (sese region, loop_p context_loop, struct clast_for *stmt,
-		     htab_t rename_map, VEC (tree, heap) **newivs,
+		     edge next_e, htab_t rename_map, VEC (tree, heap) **newivs,
-		     htab_t newivs_index, htab_t bb_pbb_mapping,
+		     htab_t newivs_index, htab_t bb_pbb_mapping, int level,
 		     htab_t params_index)
 {
 edge last_e = graphite_create_new_loop_guard (region, next_e, stmt, *newivs,
-					   newivs_index, params_index);
+						newivs_index, params_index);
 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
 edge false_e = get_false_edge_from_guard_bb (next_e->dest);
 edge exit_true_e = single_succ_edge (true_e->dest);
 edge exit_false_e = single_succ_edge (false_e->dest);
 htab_t before_guard = htab_create (10, rename_map_elt_info,
 				     eq_rename_map_elts, free);
 htab_traverse (rename_map, copy_renames, before_guard);
-next_e = translate_clast_for_loop (region, stmt, true_e, rename_map, newivs,
+next_e = translate_clast_for_loop (region, context_loop, stmt, true_e,
-				     newivs_index, bb_pbb_mapping,
+				     rename_map, newivs,
+				     newivs_index, bb_pbb_mapping, level,
 				     params_index);
 insert_guard_phis (last_e->src, exit_true_e, exit_false_e,
 		     before_guard, rename_map);
 /* Translates a clast guard statement STMT to gimple.
 - REGION is the sese region we used to generate the scop.
 - NEXT_E is the edge where new generated code should be attached.
+- CONTEXT_LOOP is the loop in which the generated code will be placed
 - RENAME_MAP contains a set of tuples of new names associated to
 the original variables names.
 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
 the sese region.  */
 static edge
-translate_clast_guard (sese region, struct clast_guard *stmt, edge next_e,
+translate_clast_guard (sese region, loop_p context_loop,
+		       struct clast_guard *stmt, edge next_e,
 		       htab_t rename_map, VEC (tree, heap) **newivs,
-		       htab_t newivs_index, htab_t bb_pbb_mapping,
+		       htab_t newivs_index, htab_t bb_pbb_mapping, int level,
 		       htab_t params_index)
 {
 edge last_e = graphite_create_new_guard (region, next_e, stmt, *newivs,
 					   newivs_index, params_index);
 htab_t before_guard = htab_create (10, rename_map_elt_info,
 				     eq_rename_map_elts, free);
 htab_traverse (rename_map, copy_renames, before_guard);
-next_e = translate_clast (region, stmt->then, true_e,
+next_e = translate_clast (region, context_loop, stmt->then, true_e,
 			    rename_map, newivs, newivs_index, bb_pbb_mapping,
-			    params_index);
+			    level, params_index);
 insert_guard_phis (last_e->src, exit_true_e, exit_false_e,
 		     before_guard, rename_map);
 htab_delete (before_guard);
 /* Translates a CLAST statement STMT to GCC representation in the
 context of a SESE.
 - NEXT_E is the edge where new generated code should be attached.
+- CONTEXT_LOOP is the loop in which the generated code will be placed
 - RENAME_MAP contains a set of tuples of new names associated to
 the original variables names.
 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.  */
 static edge
-translate_clast (sese region, struct clast_stmt *stmt,
+translate_clast (sese region, loop_p context_loop, struct clast_stmt *stmt,
 		 edge next_e, htab_t rename_map, VEC (tree, heap) **newivs,
-		 htab_t newivs_index, htab_t bb_pbb_mapping,
+		 htab_t newivs_index, htab_t bb_pbb_mapping, int level,
 		 htab_t params_index)
 {
 if (!stmt)
 return next_e;
 next_e = translate_clast_user (region, (struct clast_user_stmt *) stmt,
 				   next_e, rename_map, newivs, newivs_index,
 				   bb_pbb_mapping, params_index);
 else if (CLAST_STMT_IS_A (stmt, stmt_for))
-next_e = translate_clast_for (region,
+next_e = translate_clast_for (region, context_loop,
-				  (struct clast_for *) stmt, next_e, rename_map,
+				  (struct clast_for *) stmt, next_e,
-				  newivs, newivs_index, bb_pbb_mapping,
+				  rename_map, newivs, newivs_index,
-				  params_index);
+				  bb_pbb_mapping, level, params_index);
 else if (CLAST_STMT_IS_A (stmt, stmt_guard))
-next_e = translate_clast_guard (region, (struct clast_guard *) stmt, next_e,
+next_e = translate_clast_guard (region, context_loop,
+				    (struct clast_guard *) stmt, next_e,
 				    rename_map, newivs, newivs_index,
-				    bb_pbb_mapping, params_index);
+				    bb_pbb_mapping, level, params_index);
 else if (CLAST_STMT_IS_A (stmt, stmt_block))
-next_e = translate_clast (region, ((struct clast_block *) stmt)->body,
+next_e = translate_clast (region, context_loop,
+			      ((struct clast_block *) stmt)->body,
 			      next_e, rename_map, newivs, newivs_index,
-			      bb_pbb_mapping, params_index);
+			      bb_pbb_mapping, level, params_index);
 else
 gcc_unreachable();
 recompute_all_dominators ();
 graphite_verify ();
-return translate_clast (region, stmt->next, next_e, rename_map, newivs,
+return translate_clast (region, context_loop, stmt->next, next_e,
-			  newivs_index, bb_pbb_mapping, params_index);
+			  rename_map, newivs, newivs_index,
-}
+			  bb_pbb_mapping, level, params_index);
-/* Returns the first cloog name used in EXPR.  */
-static const char *
-find_cloog_iv_in_expr (struct clast_expr *expr)
-{
-struct clast_term *term = (struct clast_term *) expr;
-if (expr->type == expr_term
-&& !term->var)
-return NULL;
-if (expr->type == expr_term)
-return term->var;
-if (expr->type == expr_red)
-{
-int i;
-struct clast_reduction *red = (struct clast_reduction *) expr;
-for (i = 0; i < red->n; i++)
-	{
-	  const char *res = find_cloog_iv_in_expr ((red)->elts[i]);
-	  if (res)
-	    return res;
-	}
-}
-return NULL;
-}
-/* Build for a clast_user_stmt USER_STMT a map between the CLAST
-induction variables and the corresponding GCC old induction
-variables.  This information is stored on each GRAPHITE_BB.  */
-static void
-compute_cloog_iv_types_1 (poly_bb_p pbb, struct clast_user_stmt *user_stmt)
-{
-gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
-struct clast_stmt *t;
-int index = 0;
-for (t = user_stmt->substitutions; t; t = t->next, index++)
-{
-PTR *slot;
-struct ivtype_map_elt_s tmp;
-struct clast_expr *expr = (struct clast_expr *)
-	((struct clast_assignment *)t)->RHS;
-/* Create an entry (clast_var, type).  */
-tmp.cloog_iv = find_cloog_iv_in_expr (expr);
-if (!tmp.cloog_iv)
-	continue;
-slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT);
-if (!*slot)
-	{
-	  tree oldiv = pbb_to_depth_to_oldiv (pbb, index);
-	  tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
-	  *slot = new_ivtype_map_elt (tmp.cloog_iv, type);
-	}
-}
-}
-/* Walk the CLAST tree starting from STMT and build for each
-clast_user_stmt a map between the CLAST induction variables and the
-corresponding GCC old induction variables.  This information is
-stored on each GRAPHITE_BB.  */
-static void
-compute_cloog_iv_types (struct clast_stmt *stmt)
-{
-if (!stmt)
-return;
-if (CLAST_STMT_IS_A (stmt, stmt_root))
-goto next;
-if (CLAST_STMT_IS_A (stmt, stmt_user))
-{
-CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
-poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
-gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
-if (!GBB_CLOOG_IV_TYPES (gbb))
-	GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info,
-						eq_ivtype_map_elts, free);
-compute_cloog_iv_types_1 (pbb, (struct clast_user_stmt *) stmt);
-goto next;
-}
-if (CLAST_STMT_IS_A (stmt, stmt_for))
-{
-struct clast_stmt *s = ((struct clast_for *) stmt)->body;
-compute_cloog_iv_types (s);
-goto next;
-}
-if (CLAST_STMT_IS_A (stmt, stmt_guard))
-{
-struct clast_stmt *s = ((struct clast_guard *) stmt)->then;
-compute_cloog_iv_types (s);
-goto next;
-}
-if (CLAST_STMT_IS_A (stmt, stmt_block))
-{
-struct clast_stmt *s = ((struct clast_block *) stmt)->body;
-compute_cloog_iv_types (s);
-goto next;
-}
-gcc_unreachable ();
-next:
-compute_cloog_iv_types (stmt->next);
 }
 /* Free the SCATTERING domain list.  */
 static void
 debug_generated_program (scop_p scop)
 {
 print_generated_program (stderr, scop);
 }
-/* Add CLooG names to parameter index.  The index is used to translate back from
+/* Add CLooG names to parameter index.  The index is used to translate
-* CLooG names to GCC trees.  */
+back from CLooG names to GCC trees.  */
 static void
 create_params_index (htab_t index_table, CloogProgram *prog) {
 CloogNames* names = cloog_program_names (prog);
 int nb_parameters = cloog_names_nb_parameters (names);
 the given SCOP.  Return true if code generation succeeded.
 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
 */
 bool
-gloog (scop_p scop, htab_t bb_pbb_mapping)
+gloog (scop_p scop, VEC (scop_p, heap) *scops, htab_t bb_pbb_mapping)
 {
-edge new_scop_exit_edge = NULL;
 VEC (tree, heap) *newivs = VEC_alloc (tree, heap, 10);
+loop_p context_loop;
 sese region = SCOP_REGION (scop);
 ifsese if_region = NULL;
 htab_t rename_map, newivs_index, params_index;
 cloog_prog_clast pc;
+int i;
 timevar_push (TV_GRAPHITE_CODE_GEN);
+gloog_error = false;
 pc = scop_to_clast (scop);
 if (dump_file && (dump_flags & TDF_DETAILS))
 {
 				 if_region->false_region->exit,
 				 if_region->true_region->exit);
 recompute_all_dominators ();
 graphite_verify ();
-compute_cloog_iv_types (pc.stmt);
+context_loop = SESE_ENTRY (region)->src->loop_father;
 rename_map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free);
 newivs_index = htab_create (10, clast_name_index_elt_info,
 			      eq_clast_name_indexes, free);
 params_index = htab_create (10, clast_name_index_elt_info,
 			      eq_clast_name_indexes, free);
 create_params_index (params_index, pc.prog);
-new_scop_exit_edge = translate_clast (region, pc.stmt,
+translate_clast (region, context_loop, pc.stmt,
-					if_region->true_region->entry,
+		   if_region->true_region->entry,
-					rename_map, &newivs, newivs_index,
+		   rename_map, &newivs, newivs_index,
-					bb_pbb_mapping, params_index);
+		   bb_pbb_mapping, 1, params_index);
 graphite_verify ();
 sese_adjust_liveout_phis (region, rename_map,
 			    if_region->region->exit->src,
 			    if_region->false_region->exit,
 			    if_region->true_region->exit);
+scev_reset_htab ();
+rename_nb_iterations (rename_map);
+for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
+rename_sese_parameters (rename_map, SCOP_REGION (scop));
 recompute_all_dominators ();
 graphite_verify ();
+if (gloog_error)
+set_ifsese_condition (if_region, integer_zero_node);
 free (if_region->true_region);
 free (if_region->region);
 free (if_region);
 fprintf (dump_file, "\n%d loops carried no dependency.\n",
 	       num_no_dependency);
 }
-return true;
+return !gloog_error;
 }
 #endif

Mercurial > hg > CbC > CbC_gcc

comparison gcc/graphite-clast-to-gimple.c @ 63:b7f97abdc517 gcc-4.6-20100522