CbC/CbC_gcc: gcc/tree-parloops.c comparison

comparison gcc/tree-parloops.c @ 69:1b10fe6932e1

merge 69

author	Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date	Sun, 21 Aug 2011 07:53:12 +0900
parents	f6334be47118
children	04ced10e8804

comparison

equal deleted inserted replaced

-:b362627d71ba
+:1b10fe6932e1
 /* Loop autoparallelization.
-Copyright (C) 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
+Copyright (C) 2006, 2007, 2008, 2009, 2010
+Free Software Foundation, Inc.
 Contributed by Sebastian Pop <pop@cri.ensmp.fr> and
 Zdenek Dvorak <dvorakz@suse.cz>.
 This file is part of GCC.
 <http://www.gnu.org/licenses/>.  */
 #include "config.h"
 #include "system.h"
 #include "coretypes.h"
-#include "tm.h"
-#include "tree.h"
-#include "rtl.h"
 #include "tree-flow.h"
 #include "cfgloop.h"
-#include "ggc.h"
 #include "tree-data-ref.h"
-#include "diagnostic.h"
+#include "tree-scalar-evolution.h"
+#include "gimple-pretty-print.h"
 #include "tree-pass.h"
-#include "tree-scalar-evolution.h"
-#include "hashtab.h"
 #include "langhooks.h"
 #include "tree-vectorizer.h"
 /* This pass tries to distribute iterations of loops into several threads.
 The implementation is straightforward -- for each loop we test whether its
 -- handling of common scalar dependence patterns (accumulation, ...)
 -- handling of non-innermost loops  */
 /*
 Reduction handling:
-currently we use vect_is_simple_reduction() to detect reduction patterns.
+currently we use vect_force_simple_reduction() to detect reduction patterns.
 The code transformation will be introduced by an example.
 parloop
 {
 struct reduction_info
 {
 gimple reduc_stmt;		/* reduction statement.  */
 gimple reduc_phi;		/* The phi node defining the reduction.  */
 enum tree_code reduction_code;/* code for the reduction operation.  */
+unsigned reduc_version;	/* SSA_NAME_VERSION of original reduc_phi
+				   result.  */
 gimple keep_res;		/* The PHI_RESULT of this phi is the resulting value
 				   of the reduction variable when existing the loop. */
 tree initial_value;		/* The initial value of the reduction var before entering the loop.  */
 tree field;			/*  the name of the field in the parloop data structure intended for reduction.  */
 tree init;			/* reduction initialization value.  */
 static hashval_t
 reduction_info_hash (const void *aa)
 {
 const struct reduction_info *a = (const struct reduction_info *) aa;
-return htab_hash_pointer (a->reduc_phi);
+return a->reduc_version;
 }
 static struct reduction_info *
 reduction_phi (htab_t reduction_list, gimple phi)
 {
 struct reduction_info tmpred, *red;
-if (htab_elements (reduction_list) == 0)
+if (htab_elements (reduction_list) == 0 || phi == NULL)
 return NULL;
 tmpred.reduc_phi = phi;
+tmpred.reduc_version = gimple_uid (phi);
 red = (struct reduction_info *) htab_find (reduction_list, &tmpred);
 return red;
 }
 const struct name_to_copy_elt *a = (const struct name_to_copy_elt *) aa;
 return (hashval_t) a->version;
 }
+/* A transformation matrix, which is a self-contained ROWSIZE x COLSIZE
+matrix.  Rather than use floats, we simply keep a single DENOMINATOR that
+represents the denominator for every element in the matrix.  */
+typedef struct lambda_trans_matrix_s
+{
+lambda_matrix matrix;
+int rowsize;
+int colsize;
+int denominator;
+} *lambda_trans_matrix;
+#define LTM_MATRIX(T) ((T)->matrix)
+#define LTM_ROWSIZE(T) ((T)->rowsize)
+#define LTM_COLSIZE(T) ((T)->colsize)
+#define LTM_DENOMINATOR(T) ((T)->denominator)
+/* Allocate a new transformation matrix.  */
+static lambda_trans_matrix
+lambda_trans_matrix_new (int colsize, int rowsize,
+			 struct obstack * lambda_obstack)
+{
+lambda_trans_matrix ret;
+ret = (lambda_trans_matrix)
+obstack_alloc (lambda_obstack, sizeof (struct lambda_trans_matrix_s));
+LTM_MATRIX (ret) = lambda_matrix_new (rowsize, colsize, lambda_obstack);
+LTM_ROWSIZE (ret) = rowsize;
+LTM_COLSIZE (ret) = colsize;
+LTM_DENOMINATOR (ret) = 1;
+return ret;
+}
+/* Multiply a vector VEC by a matrix MAT.
+MAT is an M*N matrix, and VEC is a vector with length N.  The result
+is stored in DEST which must be a vector of length M.  */
+static void
+lambda_matrix_vector_mult (lambda_matrix matrix, int m, int n,
+			   lambda_vector vec, lambda_vector dest)
+{
+int i, j;
+lambda_vector_clear (dest, m);
+for (i = 0; i < m; i++)
+for (j = 0; j < n; j++)
+dest[i] += matrix[i][j] * vec[j];
+}
+/* Return true if TRANS is a legal transformation matrix that respects
+the dependence vectors in DISTS and DIRS.  The conservative answer
+is false.
+"Wolfe proves that a unimodular transformation represented by the
+matrix T is legal when applied to a loop nest with a set of
+lexicographically non-negative distance vectors RDG if and only if
+for each vector d in RDG, (T.d >= 0) is lexicographically positive.
+i.e.: if and only if it transforms the lexicographically positive
+distance vectors to lexicographically positive vectors.  Note that
+a unimodular matrix must transform the zero vector (and only it) to
+the zero vector." S.Muchnick.  */
+static bool
+lambda_transform_legal_p (lambda_trans_matrix trans,
+			  int nb_loops,
+			  VEC (ddr_p, heap) *dependence_relations)
+{
+unsigned int i, j;
+lambda_vector distres;
+struct data_dependence_relation *ddr;
+gcc_assert (LTM_COLSIZE (trans) == nb_loops
+	      && LTM_ROWSIZE (trans) == nb_loops);
+/* When there are no dependences, the transformation is correct.  */
+if (VEC_length (ddr_p, dependence_relations) == 0)
+return true;
+ddr = VEC_index (ddr_p, dependence_relations, 0);
+if (ddr == NULL)
+return true;
+/* When there is an unknown relation in the dependence_relations, we
+know that it is no worth looking at this loop nest: give up.  */
+if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+return false;
+distres = lambda_vector_new (nb_loops);
+/* For each distance vector in the dependence graph.  */
+FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
+{
+/* Don't care about relations for which we know that there is no
+	 dependence, nor about read-read (aka. output-dependences):
+	 these data accesses can happen in any order.  */
+if (DDR_ARE_DEPENDENT (ddr) == chrec_known
+	  || (DR_IS_READ (DDR_A (ddr)) && DR_IS_READ (DDR_B (ddr))))
+	continue;
+/* Conservatively answer: "this transformation is not valid".  */
+if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+	return false;
+/* If the dependence could not be captured by a distance vector,
+	 conservatively answer that the transform is not valid.  */
+if (DDR_NUM_DIST_VECTS (ddr) == 0)
+	return false;
+/* Compute trans.dist_vect */
+for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++)
+	{
+	  lambda_matrix_vector_mult (LTM_MATRIX (trans), nb_loops, nb_loops,
+				     DDR_DIST_VECT (ddr, j), distres);
+	  if (!lambda_vector_lexico_pos (distres, nb_loops))
+	    return false;
+	}
+}
+return true;
+}
 /* Data dependency analysis. Returns true if the iterations of LOOP
 are independent on each other (that is, if we can execute them
 in parallel).  */
 static bool
-loop_parallel_p (struct loop *loop)
+loop_parallel_p (struct loop *loop, struct obstack * parloop_obstack)
 {
-VEC (ddr_p, heap) * dependence_relations;
+VEC (loop_p, heap) *loop_nest;
+VEC (ddr_p, heap) *dependence_relations;
 VEC (data_reference_p, heap) *datarefs;
 lambda_trans_matrix trans;
 bool ret = false;
 if (dump_file && (dump_flags & TDF_DETAILS))
 /* Check for problems with dependences.  If the loop can be reversed,
 the iterations are independent.  */
 datarefs = VEC_alloc (data_reference_p, heap, 10);
 dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
-compute_data_dependences_for_loop (loop, true, &datarefs,
+loop_nest = VEC_alloc (loop_p, heap, 3);
+compute_data_dependences_for_loop (loop, true, &loop_nest, &datarefs,
 				     &dependence_relations);
 if (dump_file && (dump_flags & TDF_DETAILS))
 dump_data_dependence_relations (dump_file, dependence_relations);
-trans = lambda_trans_matrix_new (1, 1);
+trans = lambda_trans_matrix_new (1, 1, parloop_obstack);
 LTM_MATRIX (trans)[0][0] = -1;
 if (lambda_transform_legal_p (trans, 1, dependence_relations))
 {
 ret = true;
 }
 else if (dump_file && (dump_flags & TDF_DETAILS))
 fprintf (dump_file,
 	     "  FAILED: data dependencies exist across iterations\n");
+VEC_free (loop_p, heap, loop_nest);
 free_dependence_relations (dependence_relations);
 free_data_refs (datarefs);
 return ret;
 }
 }
 /* Assigns the address of OBJ in TYPE to an ssa name, and returns this name.
 The assignment statement is placed on edge ENTRY.  DECL_ADDRESS maps decls
 to their addresses that can be reused.  The address of OBJ is known to
-be invariant in the whole function.  */
+be invariant in the whole function.  Other needed statements are placed
+right before GSI.  */
 static tree
-take_address_of (tree obj, tree type, edge entry, htab_t decl_address)
+take_address_of (tree obj, tree type, edge entry, htab_t decl_address,
+		 gimple_stmt_iterator *gsi)
 {
 int uid;
 void **dslot;
 struct int_tree_map ielt, *nielt;
 tree *var_p, name, bvar, addr;
 obj = unshare_expr (obj);
 for (var_p = &obj;
 handled_component_p (*var_p);
 var_p = &TREE_OPERAND (*var_p, 0))
 continue;
-uid = DECL_UID (*var_p);
+/* Canonicalize the access to base on a MEM_REF.  */
+if (DECL_P (*var_p))
+*var_p = build_simple_mem_ref (build_fold_addr_expr (*var_p));
+/* Assign a canonical SSA name to the address of the base decl used
+in the address and share it for all accesses and addresses based
+on it.  */
+uid = DECL_UID (TREE_OPERAND (TREE_OPERAND (*var_p, 0), 0));
 ielt.uid = uid;
 dslot = htab_find_slot_with_hash (decl_address, &ielt, uid, INSERT);
 if (!*dslot)
 {
-addr = build_addr (*var_p, current_function_decl);
+if (gsi == NULL)
-bvar = create_tmp_var (TREE_TYPE (addr), get_name (*var_p));
+	return NULL;
+addr = TREE_OPERAND (*var_p, 0);
+bvar = create_tmp_var (TREE_TYPE (addr),
+			     get_name (TREE_OPERAND
+				         (TREE_OPERAND (*var_p, 0), 0)));
 add_referenced_var (bvar);
 stmt = gimple_build_assign (bvar, addr);
 name = make_ssa_name (bvar, stmt);
 gimple_assign_set_lhs (stmt, name);
 gsi_insert_on_edge_immediate (entry, stmt);
 *dslot = nielt;
 }
 else
 name = ((struct int_tree_map *) *dslot)->to;
-if (var_p != &obj)
+/* Express the address in terms of the canonical SSA name.  */
-{
+TREE_OPERAND (*var_p, 0) = name;
-*var_p = build1 (INDIRECT_REF, TREE_TYPE (*var_p), name);
+if (gsi == NULL)
-name = force_gimple_operand (build_addr (obj, current_function_decl),
+return build_fold_addr_expr_with_type (obj, type);
-				   &stmts, true, NULL_TREE);
-if (!gimple_seq_empty_p (stmts))
+name = force_gimple_operand (build_addr (obj, current_function_decl),
-	gsi_insert_seq_on_edge_immediate (entry, stmts);
+			       &stmts, true, NULL_TREE);
-}
+if (!gimple_seq_empty_p (stmts))
+gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
-if (TREE_TYPE (name) != type)
+if (!useless_type_conversion_p (type, TREE_TYPE (name)))
 {
 name = force_gimple_operand (fold_convert (type, name), &stmts, true,
 				   NULL_TREE);
 if (!gimple_seq_empty_p (stmts))
-	gsi_insert_seq_on_edge_immediate (entry, stmts);
+	gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
 }
 return name;
 }
 struct elv_data
 {
 struct walk_stmt_info info;
 edge entry;
 htab_t decl_address;
+gimple_stmt_iterator *gsi;
 bool changed;
+bool reset;
 };
 /* Eliminates references to local variables in *TP out of the single
 entry single exit region starting at DTA->ENTRY.
 DECL_ADDRESS contains addresses of the references that had their
 if (!SSA_VAR_P (t) || DECL_EXTERNAL (t))
 	return NULL_TREE;
 type = TREE_TYPE (t);
 addr_type = build_pointer_type (type);
-addr = take_address_of (t, addr_type, dta->entry, dta->decl_address);
+addr = take_address_of (t, addr_type, dta->entry, dta->decl_address,
-*tp = build1 (INDIRECT_REF, TREE_TYPE (*tp), addr);
+			      dta->gsi);
+if (dta->gsi == NULL && addr == NULL_TREE)
+	{
+	  dta->reset = true;
+	  return NULL_TREE;
+	}
+*tp = build_simple_mem_ref (addr);
 dta->changed = true;
 return NULL_TREE;
 }
 var = get_base_address (obj);
 if (!var || !SSA_VAR_P (var) || DECL_EXTERNAL (var))
 	return NULL_TREE;
 addr_type = TREE_TYPE (t);
-addr = take_address_of (obj, addr_type, dta->entry, dta->decl_address);
+addr = take_address_of (obj, addr_type, dta->entry, dta->decl_address,
+			      dta->gsi);
+if (dta->gsi == NULL && addr == NULL_TREE)
+	{
+	  dta->reset = true;
+	  return NULL_TREE;
+	}
 *tp = addr;
 dta->changed = true;
 return NULL_TREE;
 }
 *walk_subtrees = 0;
 return NULL_TREE;
 }
-/* Moves the references to local variables in STMT out of the single
+/* Moves the references to local variables in STMT at *GSI out of the single
 entry single exit region starting at ENTRY.  DECL_ADDRESS contains
 addresses of the references that had their address taken
 already.  */
 static void
-eliminate_local_variables_stmt (edge entry, gimple stmt,
+eliminate_local_variables_stmt (edge entry, gimple_stmt_iterator *gsi,
 				htab_t decl_address)
 {
 struct elv_data dta;
+gimple stmt = gsi_stmt (*gsi);
 memset (&dta.info, '\0', sizeof (dta.info));
 dta.entry = entry;
 dta.decl_address = decl_address;
 dta.changed = false;
+dta.reset = false;
 if (gimple_debug_bind_p (stmt))
-walk_tree (gimple_debug_bind_get_value_ptr (stmt),
+{
-	       eliminate_local_variables_1, &dta.info, NULL);
+dta.gsi = NULL;
+walk_tree (gimple_debug_bind_get_value_ptr (stmt),
+		 eliminate_local_variables_1, &dta.info, NULL);
+if (dta.reset)
+	{
+	  gimple_debug_bind_reset_value (stmt);
+	  dta.changed = true;
+	}
+}
 else
-walk_gimple_op (stmt, eliminate_local_variables_1, &dta.info);
+{
+dta.gsi = gsi;
+walk_gimple_op (stmt, eliminate_local_variables_1, &dta.info);
+}
 if (dta.changed)
 update_stmt (stmt);
 }
 {
 basic_block bb;
 VEC (basic_block, heap) *body = VEC_alloc (basic_block, heap, 3);
 unsigned i;
 gimple_stmt_iterator gsi;
+bool has_debug_stmt = false;
 htab_t decl_address = htab_create (10, int_tree_map_hash, int_tree_map_eq,
 				     free);
 basic_block entry_bb = entry->src;
 basic_block exit_bb = exit->dest;
 gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
-for (i = 0; VEC_iterate (basic_block, body, i, bb); i++)
+FOR_EACH_VEC_ELT (basic_block, body, i, bb)
 if (bb != entry_bb && bb != exit_bb)
 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
-	eliminate_local_variables_stmt (entry, gsi_stmt (gsi),
+	if (gimple_debug_bind_p (gsi_stmt (gsi)))
-					decl_address);
+	  has_debug_stmt = true;
+	else
+	  eliminate_local_variables_stmt (entry, &gsi, decl_address);
+if (has_debug_stmt)
+FOR_EACH_VEC_ELT (basic_block, body, i, bb)
+if (bb != entry_bb && bb != exit_bb)
+	for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+	  if (gimple_debug_bind_p (gsi_stmt (gsi)))
+	    eliminate_local_variables_stmt (entry, &gsi, decl_address);
 htab_delete (decl_address);
 VEC_free (basic_block, heap, body);
 }
 {
 struct reduction_info *const reduc = (struct reduction_info *) *slot;
 struct clsn_data *const clsn_data = (struct clsn_data *) data;
 gimple_stmt_iterator gsi;
 tree type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
-tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
 tree load_struct;
 basic_block bb;
 basic_block new_bb;
 edge e;
 tree t, addr, ref, x;
 tree tmp_load, name;
 gimple load;
-load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
+load_struct = build_simple_mem_ref (clsn_data->load);
 t = build3 (COMPONENT_REF, type, load_struct, reduc->field, NULL_TREE);
 addr = build_addr (t, current_function_decl);
 /* Create phi node.  */
 struct reduction_info *const red = (struct reduction_info *) *slot;
 struct clsn_data *const clsn_data = (struct clsn_data *) data;
 gimple stmt;
 gimple_stmt_iterator gsi;
 tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
-tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
 tree load_struct;
 tree name;
 tree x;
 gsi = gsi_after_labels (clsn_data->load_bb);
-load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
+load_struct = build_simple_mem_ref (clsn_data->load);
 load_struct = build3 (COMPONENT_REF, type, load_struct, red->field,
 			NULL_TREE);
 x = load_struct;
 name = PHI_RESULT (red->keep_res);
 struct clsn_data *const clsn_data = (struct clsn_data *) data;
 tree t;
 gimple stmt;
 gimple_stmt_iterator gsi;
 tree type = TREE_TYPE (elt->new_name);
-tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
 tree load_struct;
 gsi = gsi_last_bb (clsn_data->store_bb);
 t = build3 (COMPONENT_REF, type, clsn_data->store, elt->field, NULL_TREE);
 stmt = gimple_build_assign (t, ssa_name (elt->version));
 mark_virtual_ops_for_renaming (stmt);
 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
 gsi = gsi_last_bb (clsn_data->load_bb);
-load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
+load_struct = build_simple_mem_ref (clsn_data->load);
 t = build3 (COMPONENT_REF, type, load_struct, elt->field, NULL_TREE);
 stmt = gimple_build_assign (elt->new_name, t);
 SSA_NAME_DEF_STMT (elt->new_name) = stmt;
 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
 bool has_debug_stmt = false;
 entry = single_succ_edge (entry_bb);
 gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
-for (i = 0; VEC_iterate (basic_block, body, i, bb); i++)
+FOR_EACH_VEC_ELT (basic_block, body, i, bb)
 {
 if (bb != entry_bb && bb != exit_bb)
 	{
 	  for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 	    separate_decls_in_region_stmt (entry, exit, gsi_stmt (gsi),
 make sure we will have debug info for as many variables as
 possible (all of those that were dealt with in the loop above),
 and discard those for which we know there's nothing we can
 do.  */
 if (has_debug_stmt)
-for (i = 0; VEC_iterate (basic_block, body, i, bb); i++)
+FOR_EACH_VEC_ELT (basic_block, body, i, bb)
 if (bb != entry_bb && bb != exit_bb)
 	{
 	  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
 	    {
 	      gimple stmt = gsi_stmt (gsi);
 }
 else
 {
 /* Create the type for the structure to store the ssa names to.  */
 type = lang_hooks.types.make_type (RECORD_TYPE);
-type_name = build_decl (BUILTINS_LOCATION,
+type_name = build_decl (UNKNOWN_LOCATION,
 			      TYPE_DECL, create_tmp_var_name (".paral_data"),
 			      type);
 TYPE_NAME (type) = type_name;
 htab_traverse (name_copies, add_field_for_name, type);
 /* Creates and returns an empty function that will receive the body of
 a parallelized loop.  */
 static tree
-create_loop_fn (void)
+create_loop_fn (location_t loc)
 {
 char buf[100];
 char *tname;
 tree decl, type, name, t;
 struct function *act_cfun = cfun;
 ASM_FORMAT_PRIVATE_NAME (tname, buf, loopfn_num++);
 clean_symbol_name (tname);
 name = get_identifier (tname);
 type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE);
-decl = build_decl (BUILTINS_LOCATION,
+decl = build_decl (loc, FUNCTION_DECL, name, type);
-		     FUNCTION_DECL, name, type);
 if (!parallelized_functions)
 parallelized_functions = BITMAP_GGC_ALLOC ();
 bitmap_set_bit (parallelized_functions, DECL_UID (decl));
 TREE_STATIC (decl) = 1;
 DECL_UNINLINABLE (decl) = 1;
 DECL_EXTERNAL (decl) = 0;
 DECL_CONTEXT (decl) = NULL_TREE;
 DECL_INITIAL (decl) = make_node (BLOCK);
-t = build_decl (BUILTINS_LOCATION,
+t = build_decl (loc, RESULT_DECL, NULL_TREE, void_type_node);
-		  RESULT_DECL, NULL_TREE, void_type_node);
 DECL_ARTIFICIAL (t) = 1;
 DECL_IGNORED_P (t) = 1;
 DECL_RESULT (decl) = t;
-t = build_decl (BUILTINS_LOCATION,
+t = build_decl (loc, PARM_DECL, get_identifier (".paral_data_param"),
-		  PARM_DECL, get_identifier (".paral_data_param"),
 		  ptr_type_node);
 DECL_ARTIFICIAL (t) = 1;
 DECL_ARG_TYPE (t) = ptr_type_node;
 DECL_CONTEXT (t) = decl;
 TREE_USED (t) = 1;
 }
 bbs = get_loop_body_in_dom_order (loop);
 for (n = 0; bbs[n] != loop->latch; n++)
 continue;
-n--;
 nbbs = XNEWVEC (basic_block, n);
 ok = gimple_duplicate_sese_tail (single_succ_edge (loop->header), exit,
 				   bbs + 1, n, nbbs);
 gcc_assert (ok);
 free (bbs);
 of LOOP_FN.  N_THREADS is the requested number of threads.  Returns the
 basic block containing GIMPLE_OMP_PARALLEL tree.  */
 static basic_block
 create_parallel_loop (struct loop *loop, tree loop_fn, tree data,
-		      tree new_data, unsigned n_threads)
+		      tree new_data, unsigned n_threads, location_t loc)
 {
 gimple_stmt_iterator gsi;
 basic_block bb, paral_bb, for_bb, ex_bb;
 tree t, param;
 gimple stmt, for_stmt, phi, cond_stmt;
 /* Prepare the GIMPLE_OMP_PARALLEL statement.  */
 bb = loop_preheader_edge (loop)->src;
 paral_bb = single_pred (bb);
 gsi = gsi_last_bb (paral_bb);
-t = build_omp_clause (BUILTINS_LOCATION, OMP_CLAUSE_NUM_THREADS);
+t = build_omp_clause (loc, OMP_CLAUSE_NUM_THREADS);
 OMP_CLAUSE_NUM_THREADS_EXPR (t)
 = build_int_cst (integer_type_node, n_threads);
 stmt = gimple_build_omp_parallel (NULL, t, loop_fn, data);
+gimple_set_location (stmt, loc);
 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
 /* Initialize NEW_DATA.  */
 if (data)
 }
 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL.  */
 bb = split_loop_exit_edge (single_dom_exit (loop));
 gsi = gsi_last_bb (bb);
-gsi_insert_after (&gsi, gimple_build_omp_return (false), GSI_NEW_STMT);
+stmt = gimple_build_omp_return (false);
+gimple_set_location (stmt, loc);
+gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
 /* Extract data for GIMPLE_OMP_FOR.  */
 gcc_assert (loop->header == single_dom_exit (loop)->src);
 cond_stmt = last_stmt (loop->header);
 initvar = make_ssa_name (cvar_base, NULL);
 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, loop_preheader_edge (loop)),
 	   initvar);
 cvar_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
-gsi = gsi_last_bb (loop->latch);
+gsi = gsi_last_nondebug_bb (loop->latch);
 gcc_assert (gsi_stmt (gsi) == SSA_NAME_DEF_STMT (cvar_next));
 gsi_remove (&gsi, true);
 /* Prepare cfg.  */
 for_bb = split_edge (loop_preheader_edge (loop));
 PENDING_STMT (e) = NULL;
 /* Emit GIMPLE_OMP_FOR.  */
 gimple_cond_set_lhs (cond_stmt, cvar_base);
 type = TREE_TYPE (cvar);
-t = build_omp_clause (BUILTINS_LOCATION, OMP_CLAUSE_SCHEDULE);
+t = build_omp_clause (loc, OMP_CLAUSE_SCHEDULE);
 OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC;
 for_stmt = gimple_build_omp_for (NULL, t, 1, NULL);
+gimple_set_location (for_stmt, loc);
 gimple_omp_for_set_index (for_stmt, 0, initvar);
 gimple_omp_for_set_initial (for_stmt, 0, cvar_init);
 gimple_omp_for_set_final (for_stmt, 0, gimple_cond_rhs (cond_stmt));
 gimple_omp_for_set_cond (for_stmt, 0, gimple_cond_code (cond_stmt));
 gimple_omp_for_set_incr (for_stmt, 0, build2 (PLUS_EXPR, type,
 SSA_NAME_DEF_STMT (initvar) = for_stmt;
 /* Emit GIMPLE_OMP_CONTINUE.  */
 gsi = gsi_last_bb (loop->latch);
 stmt = gimple_build_omp_continue (cvar_next, cvar);
+gimple_set_location (stmt, loc);
 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
 SSA_NAME_DEF_STMT (cvar_next) = stmt;
 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR.  */
 gsi = gsi_last_bb (ex_bb);
-gsi_insert_after (&gsi, gimple_build_omp_return (true), GSI_NEW_STMT);
+stmt = gimple_build_omp_return (true);
+gimple_set_location (stmt, loc);
+gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
 return paral_bb;
 }
 /* Generates code to execute the iterations of LOOP in N_THREADS
 gimple_seq stmts;
 basic_block parallel_head;
 edge entry, exit;
 struct clsn_data clsn_data;
 unsigned prob;
+location_t loc;
+gimple cond_stmt;
 /* From
 ---------------------------------------------------------------------
 loop
 		prob, prob, REG_BR_PROB_BASE - prob, true);
 update_ssa (TODO_update_ssa);
 free_original_copy_tables ();
 /* Base all the induction variables in LOOP on a single control one.  */
-canonicalize_loop_ivs (loop, &nit);
+canonicalize_loop_ivs (loop, &nit, true);
 /* Ensure that the exit condition is the first statement in the loop.  */
 transform_to_exit_first_loop (loop, reduction_list, nit);
 /* Generate initializations for reductions.  */
 and back, and create separate decls for the variables used in loop.  */
 separate_decls_in_region (entry, exit, reduction_list, &arg_struct,
 			    &new_arg_struct, &clsn_data);
 /* Create the parallel constructs.  */
-parallel_head = create_parallel_loop (loop, create_loop_fn (), arg_struct,
+loc = UNKNOWN_LOCATION;
-					new_arg_struct, n_threads);
+cond_stmt = last_stmt (loop->header);
+if (cond_stmt)
+loc = gimple_location (cond_stmt);
+parallel_head = create_parallel_loop (loop, create_loop_fn (loc), arg_struct,
+					new_arg_struct, n_threads, loc);
 if (htab_elements (reduction_list) > 0)
 create_call_for_reduction (loop, reduction_list, &clsn_data);
 scev_reset ();
 new_reduction = XCNEW (struct reduction_info);
 new_reduction->reduc_stmt = reduc_stmt;
 new_reduction->reduc_phi = phi;
+new_reduction->reduc_version = SSA_NAME_VERSION (gimple_phi_result (phi));
 new_reduction->reduction_code = gimple_assign_rhs_code (reduc_stmt);
 slot = htab_find_slot (reduction_list, new_reduction, INSERT);
 *slot = new_reduction;
+}
+/* Callback for htab_traverse.  Sets gimple_uid of reduc_phi stmts.  */
+static int
+set_reduc_phi_uids (void **slot, void *data ATTRIBUTE_UNUSED)
+{
+struct reduction_info *const red = (struct reduction_info *) *slot;
+gimple_set_uid (red->reduc_phi, red->reduc_version);
+return 1;
 }
 /* Detect all reductions in the LOOP, insert them into REDUCTION_LIST.  */
 static void
 	continue;
 if (!simple_iv (loop, loop, res, &iv, true)
 	&& simple_loop_info)
 	{
-gimple reduc_stmt = vect_is_simple_reduction (simple_loop_info, phi, true, &double_reduc);
+gimple reduc_stmt = vect_force_simple_reduction (simple_loop_info,
+							    phi, true,
+							    &double_reduc);
 	   if (reduc_stmt && !double_reduc)
 build_new_reduction (reduction_list, reduc_stmt, phi);
 }
 }
 destroy_loop_vec_info (simple_loop_info, true);
+/* As gimple_uid is used by the vectorizer in between vect_analyze_loop_form
+and destroy_loop_vec_info, we can set gimple_uid of reduc_phi stmts
+only now.  */
+htab_traverse (reduction_list, set_reduc_phi_uids, NULL);
 }
 /* Try to initialize NITER for code generation part.  */
 static bool
 	      return false;
 	    }
 	  reduc_phi = NULL;
 	  FOR_EACH_IMM_USE_FAST (use_p, imm_iter, val)
 	    {
-	      if (flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
+	      if (!gimple_debug_bind_p (USE_STMT (use_p))
+		  && flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
 		{
 		  reduc_phi = USE_STMT (use_p);
 		  break;
 		}
 	    }
 bool changed = false;
 struct loop *loop;
 struct tree_niter_desc niter_desc;
 loop_iterator li;
 htab_t reduction_list;
+struct obstack parloop_obstack;
+HOST_WIDE_INT estimated;
+LOC loop_loc;
 /* Do not parallelize loops in the functions created by parallelization.  */
 if (parallelized_function_p (cfun->decl))
 return false;
+if (cfun->has_nonlocal_label)
+return false;
+gcc_obstack_init (&parloop_obstack);
 reduction_list = htab_create (10, reduction_info_hash,
 				     reduction_info_eq, free);
 init_stmt_vec_info_vec ();
 FOR_EACH_LOOP (li, loop, 0)
 }
 if (/* And of course, the loop must be parallelizable.  */
 	  !can_duplicate_loop_p (loop)
 	  || loop_has_blocks_with_irreducible_flag (loop)
+	  || (loop_preheader_edge (loop)->src->flags & BB_IRREDUCIBLE_LOOP)
 	  /* FIXME: the check for vector phi nodes could be removed.  */
 	  || loop_has_vector_phi_nodes (loop))
 	continue;
+estimated = estimated_loop_iterations_int (loop, false);
 /* FIXME: Bypass this check as graphite doesn't update the
 count and frequency correctly now.  */
 if (!flag_loop_parallelize_all
-	  && ((estimated_loop_iterations_int (loop, false)
+	  && ((estimated !=-1
-	       <= (HOST_WIDE_INT) n_threads * MIN_PER_THREAD)
+	     && estimated <= (HOST_WIDE_INT) n_threads * MIN_PER_THREAD)
 	      /* Do not bother with loops in cold areas.  */
 	      || optimize_loop_nest_for_size_p (loop)))
 	continue;
 if (!try_get_loop_niter (loop, &niter_desc))
 	continue;
 if (!try_create_reduction_list (loop, reduction_list))
 	continue;
-if (!flag_loop_parallelize_all && !loop_parallel_p (loop))
+if (!flag_loop_parallelize_all
+	  && !loop_parallel_p (loop, &parloop_obstack))
 	continue;
 changed = true;
 if (dump_file && (dump_flags & TDF_DETAILS))
 {
-fprintf (dump_file, "parallelizing ");
 	if (loop->inner)
-	  fprintf (dump_file, "outer loop\n");
+	  fprintf (dump_file, "parallelizing outer loop %d\n",loop->header->index);
 	else
-	  fprintf (dump_file, "inner loop\n");
+	  fprintf (dump_file, "parallelizing inner loop %d\n",loop->header->index);
+	loop_loc = find_loop_location (loop);
+	if (loop_loc != UNKNOWN_LOC)
+	  fprintf (dump_file, "\nloop at %s:%d: ",
+		   LOC_FILE (loop_loc), LOC_LINE (loop_loc));
 }
 gen_parallel_loop (loop, reduction_list,
 			 n_threads, &niter_desc);
 verify_flow_info ();
 verify_dominators (CDI_DOMINATORS);
 verify_loop_structure ();
-verify_loop_closed_ssa ();
+verify_loop_closed_ssa (true);
 }
 free_stmt_vec_info_vec ();
 htab_delete (reduction_list);
+obstack_free (&parloop_obstack, NULL);
 /* Parallelization will cause new function calls to be inserted through
-which local variables will escape.  Reset the points-to solutions
+which local variables will escape.  Reset the points-to solution
-for ESCAPED and CALLUSED.  */
+for ESCAPED.  */
 if (changed)
-{
+pt_solution_reset (&cfun->gimple_df->escaped);
-pt_solution_reset (&cfun->gimple_df->escaped);
-pt_solution_reset (&cfun->gimple_df->callused);
-}
 return changed;
 }
 #include "gt-tree-parloops.h"

Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-parloops.c @ 69:1b10fe6932e1