CbC/CbC_gcc: gcc/tree-loop-distribution.c comparison

comparison gcc/tree-loop-distribution.c @ 67:f6334be47118

update gcc from gcc-4.6-20100522 to gcc-4.6-20110318

author	nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
date	Tue, 22 Mar 2011 17:18:12 +0900
parents	b7f97abdc517
children	04ced10e8804

comparison

equal deleted inserted replaced

-:65488c3d617d
+:f6334be47118
 generates the new loops.  */
 #include "config.h"
 #include "system.h"
 #include "coretypes.h"
-#include "tm.h"
-#include "tree.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 "lambda.h"
-#include "langhooks.h"
-#include "tree-vectorizer.h"
 /* If bit I is not set, it means that this node represents an
 operation that has already been performed, and that should not be
 performed again.  This is the subgraph of remaining important
 computations that is passed to the DFS algorithm for avoiding to
 {
 basic_block bb = bbs[i];
 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi);)
 	if (!bitmap_bit_p (partition, x++))
-	  remove_phi_node (&bsi, true);
+	  {
+	    gimple phi = gsi_stmt (bsi);
+	    if (!is_gimple_reg (gimple_phi_result (phi)))
+	      mark_virtual_phi_result_for_renaming (phi);
+	    remove_phi_node (&bsi, true);
+	  }
 	else
 	  gsi_next (&bsi);
 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi);)
-	if (gimple_code (gsi_stmt (bsi)) != GIMPLE_LABEL
+	{
-	    && !bitmap_bit_p (partition, x++))
+	  gimple stmt = gsi_stmt (bsi);
-	  gsi_remove (&bsi, false);
+	  if (gimple_code (gsi_stmt (bsi)) != GIMPLE_LABEL
-	else
+	      && !bitmap_bit_p (partition, x++))
-	  gsi_next (&bsi);
+	    {
+	      unlink_stmt_vdef (stmt);
-	mark_virtual_ops_in_bb (bb);
+	      gsi_remove (&bsi, true);
+	      release_defs (stmt);
+	    }
+	  else
+	    gsi_next (&bsi);
+	}
 }
 free (bbs);
 return true;
 }
 return x;
 }
 /* Generate a call to memset.  Return true when the operation succeeded.  */
-static bool
+static void
 generate_memset_zero (gimple stmt, tree op0, tree nb_iter,
 		      gimple_stmt_iterator bsi)
 {
 tree addr_base, nb_bytes;
 bool res = false;
 gimple_seq stmt_list = NULL, stmts;
 gimple fn_call;
 tree mem, fn;
-gimple_stmt_iterator i;
 struct data_reference *dr = XCNEW (struct data_reference);
 location_t loc = gimple_location (stmt);
 DR_STMT (dr) = stmt;
 DR_REF (dr) = op0;
-if (!dr_analyze_innermost (dr))
+res = dr_analyze_innermost (dr);
-goto end;
+gcc_assert (res && stride_of_unit_type_p (DR_STEP (dr), TREE_TYPE (op0)));
-/* Test for a positive stride, iterating over every element.  */
+nb_bytes = build_size_arg_loc (loc, nb_iter, op0, &stmt_list);
-if (integer_zerop (size_binop (MINUS_EXPR,
+addr_base = size_binop_loc (loc, PLUS_EXPR, DR_OFFSET (dr), DR_INIT (dr));
-				 fold_convert (sizetype, DR_STEP (dr)),
+addr_base = fold_convert_loc (loc, sizetype, addr_base);
-				 TYPE_SIZE_UNIT (TREE_TYPE (op0)))))
-{
-addr_base = fold_convert_loc (loc, sizetype,
-				    size_binop_loc (loc, PLUS_EXPR,
-						    DR_OFFSET (dr),
-						    DR_INIT (dr)));
-addr_base = fold_build2_loc (loc, POINTER_PLUS_EXPR,
-				   TREE_TYPE (DR_BASE_ADDRESS (dr)),
-				   DR_BASE_ADDRESS (dr), addr_base);
-nb_bytes = build_size_arg_loc (loc, nb_iter, op0, &stmt_list);
-}
 /* Test for a negative stride, iterating over every element.  */
-else if (integer_zerop (size_binop (PLUS_EXPR,
+if (integer_zerop (size_binop (PLUS_EXPR,
-				      TYPE_SIZE_UNIT (TREE_TYPE (op0)),
+				 TYPE_SIZE_UNIT (TREE_TYPE (op0)),
-				      fold_convert (sizetype, DR_STEP (dr)))))
+				 fold_convert (sizetype, DR_STEP (dr)))))
 {
-nb_bytes = build_size_arg_loc (loc, nb_iter, op0, &stmt_list);
-addr_base = size_binop_loc (loc, PLUS_EXPR, DR_OFFSET (dr), DR_INIT (dr));
-addr_base = fold_convert_loc (loc, sizetype, addr_base);
 addr_base = size_binop_loc (loc, MINUS_EXPR, addr_base,
 				  fold_convert_loc (loc, sizetype, nb_bytes));
 addr_base = size_binop_loc (loc, PLUS_EXPR, addr_base,
 				  TYPE_SIZE_UNIT (TREE_TYPE (op0)));
-addr_base = fold_build2_loc (loc, POINTER_PLUS_EXPR,
+}
-				   TREE_TYPE (DR_BASE_ADDRESS (dr)),
-				   DR_BASE_ADDRESS (dr), addr_base);
+addr_base = fold_build2_loc (loc, POINTER_PLUS_EXPR,
-}
+			       TREE_TYPE (DR_BASE_ADDRESS (dr)),
-else
+			       DR_BASE_ADDRESS (dr), addr_base);
-goto end;
 mem = force_gimple_operand (addr_base, &stmts, true, NULL);
 gimple_seq_add_seq (&stmt_list, stmts);
 fn = build_fold_addr_expr (implicit_built_in_decls [BUILT_IN_MEMSET]);
 fn_call = gimple_build_call (fn, 3, mem, integer_zero_node, nb_bytes);
 gimple_seq_add_stmt (&stmt_list, fn_call);
-for (i = gsi_start (stmt_list); !gsi_end_p (i); gsi_next (&i))
-{
-gimple s = gsi_stmt (i);
-update_stmt_if_modified (s);
-}
 gsi_insert_seq_after (&bsi, stmt_list, GSI_CONTINUE_LINKING);
-res = true;
 if (dump_file && (dump_flags & TDF_DETAILS))
 fprintf (dump_file, "generated memset zero\n");
-end:
 free_data_ref (dr);
-return res;
-}
-/* Propagate phis in BB b to their uses and remove them.  */
-static void
-prop_phis (basic_block b)
-{
-gimple_stmt_iterator psi;
-gimple_seq phis = phi_nodes (b);
-for (psi = gsi_start (phis); !gsi_end_p (psi); )
-{
-gimple phi = gsi_stmt (psi);
-tree def = gimple_phi_result (phi), use = gimple_phi_arg_def (phi, 0);
-gcc_assert (gimple_phi_num_args (phi) == 1);
-if (!is_gimple_reg (def))
-	{
-	  imm_use_iterator iter;
-	  use_operand_p use_p;
-	  gimple stmt;
-	  FOR_EACH_IMM_USE_STMT (stmt, iter, def)
-	    FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
-	      SET_USE (use_p, use);
-	}
-else
-	replace_uses_by (def, use);
-remove_phi_node (&psi, true);
-}
 }
 /* Tries to generate a builtin function for the instructions of LOOP
 pointed to by the bits set in PARTITION.  Returns true when the
 operation succeeded.  */
 {
 bool res = false;
 unsigned i, x = 0;
 basic_block *bbs;
 gimple write = NULL;
-tree op0, op1;
 gimple_stmt_iterator bsi;
 tree nb_iter = number_of_exit_cond_executions (loop);
 if (!nb_iter || nb_iter == chrec_dont_know)
 return false;
 		nb_iter = number_of_latch_executions (loop);
 	    }
 	}
 }
-if (!write)
+if (!stmt_with_adjacent_zero_store_dr_p (write))
-goto end;
-op0 = gimple_assign_lhs (write);
-op1 = gimple_assign_rhs1 (write);
-if (!(TREE_CODE (op0) == ARRAY_REF
-	|| TREE_CODE (op0) == INDIRECT_REF))
 goto end;
 /* The new statements will be placed before LOOP.  */
 bsi = gsi_last_bb (loop_preheader_edge (loop)->src);
+generate_memset_zero (write, gimple_assign_lhs (write), nb_iter, bsi);
-if (gimple_assign_rhs_code (write) == INTEGER_CST
+res = true;
-&& (integer_zerop (op1) || real_zerop (op1)))
-res = generate_memset_zero (write, op0, nb_iter, bsi);
 /* If this is the last partition for which we generate code, we have
 to destroy the loop.  */
-if (res && !copy_p)
+if (!copy_p)
 {
 unsigned nbbs = loop->num_nodes;
-basic_block src = loop_preheader_edge (loop)->src;
+edge exit = single_exit (loop);
-basic_block dest = single_exit (loop)->dest;
+basic_block src = loop_preheader_edge (loop)->src, dest = exit->dest;
-prop_phis (dest);
+redirect_edge_pred (exit, src);
-make_edge (src, dest, EDGE_FALLTHRU);
+exit->flags &= ~(EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
+exit->flags |= EDGE_FALLTHRU;
 cancel_loop_tree (loop);
+rescan_loop_exit (exit, false, true);
 for (i = 0; i < nbbs; i++)
 	delete_basic_block (bbs[i]);
 set_immediate_dominator (CDI_DOMINATORS, dest,
 	unsigned i;
 	VEC (int, heap) *nodes = VEC_alloc (int, heap, 3);
 	graphds_dfs (rdg, &v, 1, &nodes, false, NULL);
-	for (i = 0; VEC_iterate (int, nodes, i, x); i++)
+	FOR_EACH_VEC_ELT (int, nodes, i, x)
 	  {
-	    if (bitmap_bit_p (seen, x))
+	    if (!bitmap_set_bit (seen, x))
 	      continue;
-	    bitmap_set_bit (seen, x);
 	    if (RDG_MEM_WRITE_STMT (rdg, x)
 		|| predecessor_has_mem_write (rdg, &(rdg->vertices[x]))
 		/* In anti dependences the read should occur before
 		   the write, this is why both the read and the write
 }
 static void rdg_flag_vertex_and_dependent (struct graph *, int, bitmap, bitmap,
 					   bitmap, bool *);
-/* Flag all the uses of U.  */
-static void
-rdg_flag_all_uses (struct graph *rdg, int u, bitmap partition, bitmap loops,
-		   bitmap processed, bool *part_has_writes)
-{
-struct graph_edge *e;
-for (e = rdg->vertices[u].succ; e; e = e->succ_next)
-if (!bitmap_bit_p (processed, e->dest))
-{
-	rdg_flag_vertex_and_dependent (rdg, e->dest, partition, loops,
-				       processed, part_has_writes);
-	rdg_flag_all_uses (rdg, e->dest, partition, loops, processed,
-			   part_has_writes);
-}
-}
 /* Flag the uses of U stopping following the information from
 upstream_mem_writes.  */
 static void
 rdg_flag_uses (struct graph *rdg, int u, bitmap partition, bitmap loops,
 rdg_flag_vertex (struct graph *rdg, int v, bitmap partition, bitmap loops,
 		 bool *part_has_writes)
 {
 struct loop *loop;
-if (bitmap_bit_p (partition, v))
+if (!bitmap_set_bit (partition, v))
 return;
 loop = loop_containing_stmt (RDG_STMT (rdg, v));
 bitmap_set_bit (loops, loop->num);
-bitmap_set_bit (partition, v);
 if (rdg_cannot_recompute_vertex_p (rdg, v))
 {
 *part_has_writes = true;
 bitmap_clear_bit (remaining_stmts, v);
 bitmap_set_bit (processed, v);
 rdg_flag_uses (rdg, v, partition, loops, processed, part_has_writes);
 graphds_dfs (rdg, &v, 1, &nodes, false, remaining_stmts);
 rdg_flag_vertex (rdg, v, partition, loops, part_has_writes);
-for (i = 0; VEC_iterate (int, nodes, i, x); i++)
+FOR_EACH_VEC_ELT (int, nodes, i, x)
 if (!already_processed_vertex_p (processed, x))
 rdg_flag_vertex_and_dependent (rdg, x, partition, loops, processed,
 				     part_has_writes);
 VEC_free (int, heap, nodes);
 {
 unsigned i;
 edge e;
 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
-for (i = 0; VEC_iterate (edge, exits, i, e); i++)
+FOR_EACH_VEC_ELT (edge, exits, i, e)
 {
 gimple cond = last_stmt (e->src);
 if (cond)
 	VEC_safe_push (gimple, heap, *conds, cond);
 if (!already_processed_vertex_p (processed, v))
 	rdg_flag_vertex_and_dependent (rdg, v, partition, new_loops, processed,
 				       part_has_writes);
 EXECUTE_IF_SET_IN_BITMAP (new_loops, 0, i, bi)
-	if (!bitmap_bit_p (loops, i))
+	if (bitmap_set_bit (loops, i))
-	  {
+	  collect_condition_stmts (get_loop (i), &conds);
-	    bitmap_set_bit (loops, i);
-	    collect_condition_stmts (get_loop (i), &conds);
-	  }
 BITMAP_FREE (new_loops);
 }
-}
+VEC_free (gimple, heap, conds);
-/* Flag all the nodes of RDG containing memory accesses that could
-potentially belong to arrays already accessed in the current
-PARTITION.  */
-static void
-rdg_flag_similar_memory_accesses (struct graph *rdg, bitmap partition,
-				  bitmap loops, bitmap processed,
-				  VEC (int, heap) **other_stores)
-{
-bool foo;
-unsigned i, n;
-int j, k, kk;
-bitmap_iterator ii;
-struct graph_edge *e;
-EXECUTE_IF_SET_IN_BITMAP (partition, 0, i, ii)
-if (RDG_MEM_WRITE_STMT (rdg, i)
-	|| RDG_MEM_READS_STMT (rdg, i))
-{
-	for (j = 0; j < rdg->n_vertices; j++)
-	  if (!bitmap_bit_p (processed, j)
-	      && (RDG_MEM_WRITE_STMT (rdg, j)
-		  || RDG_MEM_READS_STMT (rdg, j))
-	      && rdg_has_similar_memory_accesses (rdg, i, j))
-	    {
-	      /* Flag first the node J itself, and all the nodes that
-		 are needed to compute J.  */
-	      rdg_flag_vertex_and_dependent (rdg, j, partition, loops,
-					     processed, &foo);
-	      /* When J is a read, we want to coalesce in the same
-		 PARTITION all the nodes that are using J: this is
-		 needed for better cache locality.  */
-	      rdg_flag_all_uses (rdg, j, partition, loops, processed, &foo);
-	      /* Remove from OTHER_STORES the vertex that we flagged.  */
-	      if (RDG_MEM_WRITE_STMT (rdg, j))
-		for (k = 0; VEC_iterate (int, *other_stores, k, kk); k++)
-		  if (kk == j)
-		    {
-		      VEC_unordered_remove (int, *other_stores, k);
-		      break;
-		    }
-	    }
-	/* If the node I has two uses, then keep these together in the
-	   same PARTITION.  */
-	for (n = 0, e = rdg->vertices[i].succ; e; e = e->succ_next, n++);
-	if (n > 1)
-	  rdg_flag_all_uses (rdg, i, partition, loops, processed, &foo);
-}
 }
 /* Returns a bitmap in which all the statements needed for computing
 the strongly connected component C of the RDG are flagged, also
 including the loop exit conditions.  */
 static bitmap
 build_rdg_partition_for_component (struct graph *rdg, rdgc c,
-				   bool *part_has_writes,
+				   bool *part_has_writes)
-				   VEC (int, heap) **other_stores)
 {
 int i, v;
 bitmap partition = BITMAP_ALLOC (NULL);
 bitmap loops = BITMAP_ALLOC (NULL);
 bitmap processed = BITMAP_ALLOC (NULL);
-for (i = 0; VEC_iterate (int, c->vertices, i, v); i++)
+FOR_EACH_VEC_ELT (int, c->vertices, i, v)
 if (!already_processed_vertex_p (processed, v))
 rdg_flag_vertex_and_dependent (rdg, v, partition, loops, processed,
 				     part_has_writes);
-/* Also iterate on the array of stores not in the starting vertices,
-and determine those vertices that have some memory affinity with
-the current nodes in the component: these are stores to the same
-arrays, i.e. we're taking care of cache locality.  */
-rdg_flag_similar_memory_accesses (rdg, partition, loops, processed,
-				    other_stores);
 rdg_flag_loop_exits (rdg, loops, partition, processed, part_has_writes);
 BITMAP_FREE (processed);
 BITMAP_FREE (loops);
 return partition;
 free_rdg_components (VEC (rdgc, heap) *components)
 {
 int i;
 rdgc x;
-for (i = 0; VEC_iterate (rdgc, components, i, x); i++)
+FOR_EACH_VEC_ELT (rdgc, components, i, x)
 {
 VEC_free (int, heap, x->vertices);
 free (x);
 }
+VEC_free (rdgc, heap, components);
 }
 /* Build the COMPONENTS vector with the strongly connected components
 of RDG in which the STARTING_VERTICES occur.  */
 all_components[i] = VEC_alloc (int, heap, 3);
 for (i = 0; i < rdg->n_vertices; i++)
 VEC_safe_push (int, heap, all_components[rdg->vertices[i].component], i);
-for (i = 0; VEC_iterate (int, starting_vertices, i, v); i++)
+FOR_EACH_VEC_ELT (int, starting_vertices, i, v)
 {
 int c = rdg->vertices[v].component;
-if (!bitmap_bit_p (saved_components, c))
+if (bitmap_set_bit (saved_components, c))
 	{
 	  rdgc x = XCNEW (struct rdg_component);
 	  x->num = c;
 	  x->vertices = all_components[c];
 	  VEC_safe_push (rdgc, heap, *components, x);
-	  bitmap_set_bit (saved_components, c);
 	}
 }
 for (i = 0; i < n_components; i++)
 if (!bitmap_bit_p (saved_components, i))
 free (all_components);
 BITMAP_FREE (saved_components);
 }
+/* Returns true when it is possible to generate a builtin pattern for
+the PARTITION of RDG.  For the moment we detect only the memset
+zero pattern.  */
+static bool
+can_generate_builtin (struct graph *rdg, bitmap partition)
+{
+unsigned i;
+bitmap_iterator bi;
+int nb_reads = 0;
+int nb_writes = 0;
+int stores_zero = 0;
+EXECUTE_IF_SET_IN_BITMAP (partition, 0, i, bi)
+if (RDG_MEM_READS_STMT (rdg, i))
+nb_reads++;
+else if (RDG_MEM_WRITE_STMT (rdg, i))
+{
+	nb_writes++;
+	if (stmt_with_adjacent_zero_store_dr_p (RDG_STMT (rdg, i)))
+	  stores_zero++;
+}
+return stores_zero == 1 && nb_writes == 1 && nb_reads == 0;
+}
+/* Returns true when PARTITION1 and PARTITION2 have similar memory
+accesses in RDG.  */
+static bool
+similar_memory_accesses (struct graph *rdg, bitmap partition1,
+			 bitmap partition2)
+{
+unsigned i, j;
+bitmap_iterator bi, bj;
+EXECUTE_IF_SET_IN_BITMAP (partition1, 0, i, bi)
+if (RDG_MEM_WRITE_STMT (rdg, i)
+	|| RDG_MEM_READS_STMT (rdg, i))
+EXECUTE_IF_SET_IN_BITMAP (partition2, 0, j, bj)
+	if (RDG_MEM_WRITE_STMT (rdg, j)
+	    || RDG_MEM_READS_STMT (rdg, j))
+	  if (rdg_has_similar_memory_accesses (rdg, i, j))
+	    return true;
+return false;
+}
+/* Fuse all the partitions from PARTITIONS that contain similar memory
+references, i.e., we're taking care of cache locality.  This
+function does not fuse those partitions that contain patterns that
+can be code generated with builtins.  */
+static void
+fuse_partitions_with_similar_memory_accesses (struct graph *rdg,
+					      VEC (bitmap, heap) **partitions)
+{
+int p1, p2;
+bitmap partition1, partition2;
+FOR_EACH_VEC_ELT (bitmap, *partitions, p1, partition1)
+if (!can_generate_builtin (rdg, partition1))
+FOR_EACH_VEC_ELT (bitmap, *partitions, p2, partition2)
+	if (p1 != p2
+	    && !can_generate_builtin (rdg, partition2)
+	    && similar_memory_accesses (rdg, partition1, partition2))
+	  {
+	    bitmap_ior_into (partition1, partition2);
+	    VEC_ordered_remove (bitmap, *partitions, p2);
+	    p2--;
+	  }
+}
+/* Returns true when DEF is an SSA_NAME defined in LOOP and used after
+the LOOP.  */
+static bool
+ssa_name_has_uses_outside_loop_p (tree def, loop_p loop)
+{
+imm_use_iterator imm_iter;
+use_operand_p use_p;
+FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
+if (loop != loop_containing_stmt (USE_STMT (use_p)))
+return true;
+return false;
+}
+/* Returns true when STMT defines a scalar variable used after the
+loop.  */
+static bool
+stmt_has_scalar_dependences_outside_loop (gimple stmt)
+{
+tree name;
+switch (gimple_code (stmt))
+{
+case GIMPLE_ASSIGN:
+name = gimple_assign_lhs (stmt);
+break;
+case GIMPLE_PHI:
+name = gimple_phi_result (stmt);
+break;
+default:
+return false;
+}
+return TREE_CODE (name) == SSA_NAME
+&& ssa_name_has_uses_outside_loop_p (name, loop_containing_stmt (stmt));
+}
+/* Returns true when STMT will be code generated in a partition of RDG
+different than PART and that will not be code generated as a
+builtin.  */
+static bool
+stmt_generated_in_another_partition (struct graph *rdg, gimple stmt, int part,
+				     VEC (bitmap, heap) *partitions)
+{
+int p;
+bitmap pp;
+unsigned i;
+bitmap_iterator bi;
+FOR_EACH_VEC_ELT (bitmap, partitions, p, pp)
+if (p != part
+	&& !can_generate_builtin (rdg, pp))
+EXECUTE_IF_SET_IN_BITMAP (pp, 0, i, bi)
+	if (stmt == RDG_STMT (rdg, i))
+	  return true;
+return false;
+}
+/* For each partition in PARTITIONS that will be code generated using
+a builtin, add its scalar computations used after the loop to
+PARTITION.  */
+static void
+add_scalar_computations_to_partition (struct graph *rdg,
+				      VEC (bitmap, heap) *partitions,
+				      bitmap partition)
+{
+int p;
+bitmap pp;
+unsigned i;
+bitmap_iterator bi;
+bitmap l = BITMAP_ALLOC (NULL);
+bitmap pr = BITMAP_ALLOC (NULL);
+bool f = false;
+FOR_EACH_VEC_ELT (bitmap, partitions, p, pp)
+if (can_generate_builtin (rdg, pp))
+EXECUTE_IF_SET_IN_BITMAP (pp, 0, i, bi)
+	if (stmt_has_scalar_dependences_outside_loop (RDG_STMT (rdg, i))
+	    && !stmt_generated_in_another_partition (rdg, RDG_STMT (rdg, i), p,
+						     partitions))
+	  rdg_flag_vertex_and_dependent (rdg, i, partition, l, pr, &f);
+rdg_flag_loop_exits (rdg, l, partition, pr, &f);
+BITMAP_FREE (pr);
+BITMAP_FREE (l);
+}
 /* Aggregate several components into a useful partition that is
 registered in the PARTITIONS vector.  Partitions will be
 distributed in different loops.  */
 static void
 {
 int i;
 rdgc x;
 bitmap partition = BITMAP_ALLOC (NULL);
-for (i = 0; VEC_iterate (rdgc, components, i, x); i++)
+FOR_EACH_VEC_ELT (rdgc, components, i, x)
 {
 bitmap np;
 bool part_has_writes = false;
 int v = VEC_index (int, x->vertices, 0);
 if (bitmap_bit_p (processed, v))
 	continue;
-np = build_rdg_partition_for_component (rdg, x, &part_has_writes,
+np = build_rdg_partition_for_component (rdg, x, &part_has_writes);
-					      other_stores);
 bitmap_ior_into (partition, np);
 bitmap_ior_into (processed, np);
 BITMAP_FREE (np);
 if (part_has_writes)
 VEC_free (int, heap, foo);
 free_rdg_components (comps);
 }
+add_scalar_computations_to_partition (rdg, *partitions, partition);
 /* If there is something left in the last partition, save it.  */
 if (bitmap_count_bits (partition) > 0)
 VEC_safe_push (bitmap, heap, *partitions, partition);
 else
 BITMAP_FREE (partition);
+fuse_partitions_with_similar_memory_accesses (rdg, partitions);
 }
 /* Dump to FILE the PARTITIONS.  */
 static void
 dump_rdg_partitions (FILE *file, VEC (bitmap, heap) *partitions)
 {
 int i;
 bitmap partition;
-for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++)
+FOR_EACH_VEC_ELT (bitmap, partitions, i, partition)
 debug_bitmap_file (file, partition);
 }
 /* Debug PARTITIONS.  */
 extern void debug_rdg_partitions (VEC (bitmap, heap) *);
-void
+DEBUG_FUNCTION void
 debug_rdg_partitions (VEC (bitmap, heap) *partitions)
 {
 dump_rdg_partitions (stderr, partitions);
 }
 {
 int i;
 bitmap partition;
 int nrw = number_of_rw_in_rdg (rdg);
-for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++)
+FOR_EACH_VEC_ELT (bitmap, partitions, i, partition)
 if (nrw == number_of_rw_in_partition (rdg, partition))
 return true;
 return false;
 }
 	{
 	  int v;
 	  unsigned j;
 	  bool found = false;
-	  for (j = 0; VEC_iterate (int, starting_vertices, j, v); j++)
+	  FOR_EACH_VEC_ELT (int, starting_vertices, j, v)
 	    if (i == v)
 	      {
 		found = true;
 		break;
 	      }
 goto ldist_done;
 if (dump_file && (dump_flags & TDF_DETAILS))
 dump_rdg_partitions (dump_file, partitions);
-for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++)
+FOR_EACH_VEC_ELT (bitmap, partitions, i, partition)
 if (!generate_code_for_partition (loop, partition, i < nbp - 1))
 goto ldist_done;
 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
 update_ssa (TODO_update_ssa_only_virtuals | TODO_update_ssa);
 ldist_done:
 BITMAP_FREE (remaining_stmts);
 BITMAP_FREE (upstream_mem_writes);
-for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++)
+FOR_EACH_VEC_ELT (bitmap, partitions, i, partition)
 BITMAP_FREE (partition);
 VEC_free (int, heap, other_stores);
 VEC_free (bitmap, heap, partitions);
 free_rdg_components (components);
 int res = 0;
 struct graph *rdg;
 gimple s;
 unsigned i;
 VEC (int, heap) *vertices;
+VEC (ddr_p, heap) *dependence_relations;
+VEC (data_reference_p, heap) *datarefs;
+VEC (loop_p, heap) *loop_nest;
 if (loop->num_nodes > 2)
 {
 if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file,
 		 loop->num);
 return res;
 }
-rdg = build_rdg (loop);
+datarefs = VEC_alloc (data_reference_p, heap, 10);
+dependence_relations = VEC_alloc (ddr_p, heap, 100);
+loop_nest = VEC_alloc (loop_p, heap, 3);
+rdg = build_rdg (loop, &loop_nest, &dependence_relations, &datarefs);
 if (!rdg)
 {
 if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file,
 		 "FIXME: Loop %d not distributed: failed to build the RDG.\n",
 		 loop->num);
+free_dependence_relations (dependence_relations);
+free_data_refs (datarefs);
+VEC_free (loop_p, heap, loop_nest);
 return res;
 }
 vertices = VEC_alloc (int, heap, 3);
 if (dump_file && (dump_flags & TDF_DETAILS))
 dump_rdg (dump_file, rdg);
-for (i = 0; VEC_iterate (gimple, stmts, i, s); i++)
+FOR_EACH_VEC_ELT (gimple, stmts, i, s)
 {
 int v = rdg_vertex_for_stmt (rdg, s);
 if (v >= 0)
 	{
 }
 res = ldist_gen (loop, rdg, vertices);
 VEC_free (int, heap, vertices);
 free_rdg (rdg);
+free_dependence_relations (dependence_relations);
+free_data_refs (datarefs);
+VEC_free (loop_p, heap, loop_nest);
 return res;
 }
 /* Distribute all loops in the current function.  */
 loop_iterator li;
 int nb_generated_loops = 0;
 FOR_EACH_LOOP (li, loop, 0)
 {
-VEC (gimple, heap) *work_list = VEC_alloc (gimple, heap, 3);
+VEC (gimple, heap) *work_list = NULL;
+int num = loop->num;
-/* With the following working list, we're asking distribute_loop
-	 to separate the stores of the loop: when dependences allow,
+/* If the loop doesn't have a single exit we will fail anyway,
-	 it will end on having one store per loop.  */
+	 so do that early.  */
-stores_from_loop (loop, &work_list);
+if (!single_exit (loop))
+	continue;
-/* A simple heuristic for cache locality is to not split stores
-	 to the same array.  Without this call, an unrolled loop would
+/* If both flag_tree_loop_distribute_patterns and
-	 be split into as many loops as unroll factor, each loop
+	 flag_tree_loop_distribution are set, then only
-	 storing in the same array.  */
+	 distribute_patterns is executed.  */
-remove_similar_memory_refs (&work_list);
+if (flag_tree_loop_distribute_patterns)
+	{
-nb_generated_loops = distribute_loop (loop, work_list);
+	  /* With the following working list, we're asking
+	     distribute_loop to separate from the rest of the loop the
+	     stores of the form "A[i] = 0".  */
+	  stores_zero_from_loop (loop, &work_list);
+	  /* Do nothing if there are no patterns to be distributed.  */
+	  if (VEC_length (gimple, work_list) > 0)
+	    nb_generated_loops = distribute_loop (loop, work_list);
+	}
+else if (flag_tree_loop_distribution)
+	{
+	  /* With the following working list, we're asking
+	     distribute_loop to separate the stores of the loop: when
+	     dependences allow, it will end on having one store per
+	     loop.  */
+	  stores_from_loop (loop, &work_list);
+	  /* A simple heuristic for cache locality is to not split
+	     stores to the same array.  Without this call, an unrolled
+	     loop would be split into as many loops as unroll factor,
+	     each loop storing in the same array.  */
+	  remove_similar_memory_refs (&work_list);
+	  nb_generated_loops = distribute_loop (loop, work_list);
+	}
 if (dump_file && (dump_flags & TDF_DETAILS))
 	{
 	  if (nb_generated_loops > 1)
 	    fprintf (dump_file, "Loop %d distributed: split to %d loops.\n",
-		     loop->num, nb_generated_loops);
+		     num, nb_generated_loops);
 	  else
-	    fprintf (dump_file, "Loop %d is the same.\n", loop->num);
+	    fprintf (dump_file, "Loop %d is the same.\n", num);
 	}
 verify_loop_structure ();
 VEC_free (gimple, heap, work_list);
 }
 static bool
 gate_tree_loop_distribution (void)
 {
-return flag_tree_loop_distribution != 0;
+return flag_tree_loop_distribution
+|| flag_tree_loop_distribute_patterns;
 }
 struct gimple_opt_pass pass_loop_distribution =
 {
 {

Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-loop-distribution.c @ 67:f6334be47118