obtained gcc-4.6.4.tar.bz2 from upstream website;upstream

verified gcc-4.6.4.tar.bz2.sig;
imported gcc-4.6.4 source tree from verified upstream tarball.

downloading a git-generated archive based on the 'upstream' tag
should provide you with a source tree that is binary identical
to the one extracted from the above tarball.

if you have obtained the source via the command 'git clone',
however, do note that line-endings of files in your working
directory might differ from line-endings of the respective
files in the upstream repository.

1 files changed, 1329 insertions, 0 deletions

diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c
new file mode 100644
index 000000000..6b9b98d6b
--- /dev/null
+++ b/gcc/tree-loop-distribution.c
@@ -0,0 +1,1329 @@
+/* Loop distribution.
+   Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011
+   Free Software Foundation, Inc.
+   Contributed by Georges-Andre Silber <Georges-Andre.Silber@ensmp.fr>
+   and Sebastian Pop <sebastian.pop@amd.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 3, or (at your option) any
+later version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+/* This pass performs loop distribution: for example, the loop
+
+   |DO I = 2, N
+   |    A(I) = B(I) + C
+   |    D(I) = A(I-1)*E
+   |ENDDO
+
+   is transformed to
+
+   |DOALL I = 2, N
+   |   A(I) = B(I) + C
+   |ENDDO
+   |
+   |DOALL I = 2, N
+   |   D(I) = A(I-1)*E
+   |ENDDO
+
+   This pass uses an RDG, Reduced Dependence Graph built on top of the
+   data dependence relations.  The RDG is then topologically sorted to
+   obtain a map of information producers/consumers based on which it
+   generates the new loops.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tree-flow.h"
+#include "cfgloop.h"
+#include "tree-chrec.h"
+#include "tree-data-ref.h"
+#include "tree-scalar-evolution.h"
+#include "tree-pass.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
+   include several times the same stores in different loops.  */
+static bitmap remaining_stmts;
+
+/* A node of the RDG is marked in this bitmap when it has as a
+   predecessor a node that writes to memory.  */
+static bitmap upstream_mem_writes;
+
+/* 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_CALL:
+    case GIMPLE_ASSIGN:
+      name = gimple_get_lhs (stmt);
+      break;
+
+    case GIMPLE_PHI:
+      name = gimple_phi_result (stmt);
+      break;
+
+    default:
+      return false;
+    }
+
+  return (name
+	  && TREE_CODE (name) == SSA_NAME
+	  && ssa_name_has_uses_outside_loop_p (name,
+					       loop_containing_stmt (stmt)));
+}
+
+/* Update the PHI nodes of NEW_LOOP.  NEW_LOOP is a duplicate of
+   ORIG_LOOP.  */
+
+static void
+update_phis_for_loop_copy (struct loop *orig_loop, struct loop *new_loop)
+{
+  tree new_ssa_name;
+  gimple_stmt_iterator si_new, si_orig;
+  edge orig_loop_latch = loop_latch_edge (orig_loop);
+  edge orig_entry_e = loop_preheader_edge (orig_loop);
+  edge new_loop_entry_e = loop_preheader_edge (new_loop);
+
+  /* Scan the phis in the headers of the old and new loops
+     (they are organized in exactly the same order).  */
+  for (si_new = gsi_start_phis (new_loop->header),
+       si_orig = gsi_start_phis (orig_loop->header);
+       !gsi_end_p (si_new) && !gsi_end_p (si_orig);
+       gsi_next (&si_new), gsi_next (&si_orig))
+    {
+      tree def;
+      source_location locus;
+      gimple phi_new = gsi_stmt (si_new);
+      gimple phi_orig = gsi_stmt (si_orig);
+
+      /* Add the first phi argument for the phi in NEW_LOOP (the one
+	 associated with the entry of NEW_LOOP)  */
+      def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_entry_e);
+      locus = gimple_phi_arg_location_from_edge (phi_orig, orig_entry_e);
+      add_phi_arg (phi_new, def, new_loop_entry_e, locus);
+
+      /* Add the second phi argument for the phi in NEW_LOOP (the one
+	 associated with the latch of NEW_LOOP)  */
+      def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_loop_latch);
+      locus = gimple_phi_arg_location_from_edge (phi_orig, orig_loop_latch);
+
+      if (TREE_CODE (def) == SSA_NAME)
+	{
+	  new_ssa_name = get_current_def (def);
+
+	  if (!new_ssa_name)
+	    /* This only happens if there are no definitions inside the
+	       loop.  Use the the invariant in the new loop as is.  */
+	    new_ssa_name = def;
+	}
+      else
+	/* Could be an integer.  */
+	new_ssa_name = def;
+
+      add_phi_arg (phi_new, new_ssa_name, loop_latch_edge (new_loop), locus);
+    }
+}
+
+/* Return a copy of LOOP placed before LOOP.  */
+
+static struct loop *
+copy_loop_before (struct loop *loop)
+{
+  struct loop *res;
+  edge preheader = loop_preheader_edge (loop);
+
+  if (!single_exit (loop))
+    return NULL;
+
+  initialize_original_copy_tables ();
+  res = slpeel_tree_duplicate_loop_to_edge_cfg (loop, preheader);
+  free_original_copy_tables ();
+
+  if (!res)
+    return NULL;
+
+  update_phis_for_loop_copy (loop, res);
+  rename_variables_in_loop (res);
+
+  return res;
+}
+
+/* Creates an empty basic block after LOOP.  */
+
+static void
+create_bb_after_loop (struct loop *loop)
+{
+  edge exit = single_exit (loop);
+
+  if (!exit)
+    return;
+
+  split_edge (exit);
+}
+
+/* Generate code for PARTITION from the code in LOOP.  The loop is
+   copied when COPY_P is true.  All the statements not flagged in the
+   PARTITION bitmap are removed from the loop or from its copy.  The
+   statements are indexed in sequence inside a basic block, and the
+   basic blocks of a loop are taken in dom order.  Returns true when
+   the code gen succeeded. */
+
+static bool
+generate_loops_for_partition (struct loop *loop, bitmap partition, bool copy_p)
+{
+  unsigned i, x;
+  gimple_stmt_iterator bsi;
+  basic_block *bbs;
+
+  if (copy_p)
+    {
+      loop = copy_loop_before (loop);
+      create_preheader (loop, CP_SIMPLE_PREHEADERS);
+      create_bb_after_loop (loop);
+    }
+
+  if (loop == NULL)
+    return false;
+
+  /* Remove stmts not in the PARTITION bitmap.  The order in which we
+     visit the phi nodes and the statements is exactly as in
+     stmts_from_loop.  */
+  bbs = get_loop_body_in_dom_order (loop);
+
+  if (MAY_HAVE_DEBUG_STMTS)
+    for (x = 0, i = 0; i < loop->num_nodes; i++)
+      {
+	basic_block bb = bbs[i];
+
+	for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+	  if (!bitmap_bit_p (partition, x++))
+	    reset_debug_uses (gsi_stmt (bsi));
+
+	for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+	  {
+	    gimple stmt = gsi_stmt (bsi);
+	    if (gimple_code (stmt) != GIMPLE_LABEL
+		&& !is_gimple_debug (stmt)
+		&& !bitmap_bit_p (partition, x++))
+	      reset_debug_uses (stmt);
+	  }
+      }
+
+  for (x = 0, i = 0; i < loop->num_nodes; i++)
+    {
+      basic_block bb = bbs[i];
+
+      for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi);)
+	if (!bitmap_bit_p (partition, x++))
+	  {
+	    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);)
+	{
+	  gimple stmt = gsi_stmt (bsi);
+	  if (gimple_code (stmt) != GIMPLE_LABEL
+	      && !is_gimple_debug (stmt)
+	      && !bitmap_bit_p (partition, x++))
+	    {
+	      unlink_stmt_vdef (stmt);
+	      gsi_remove (&bsi, true);
+	      release_defs (stmt);
+	    }
+	  else
+	    gsi_next (&bsi);
+	}
+    }
+
+  free (bbs);
+  return true;
+}
+
+/* Build the size argument for a memset call.  */
+
+static inline tree
+build_size_arg_loc (location_t loc, tree nb_iter, tree op,
+		    gimple_seq *stmt_list)
+{
+  gimple_seq stmts;
+  tree x = size_binop_loc (loc, MULT_EXPR,
+  			   fold_convert_loc (loc, sizetype, nb_iter),
+			   TYPE_SIZE_UNIT (TREE_TYPE (op)));
+  x = force_gimple_operand (x, &stmts, true, NULL);
+  gimple_seq_add_seq (stmt_list, stmts);
+
+  return x;
+}
+
+/* Generate a call to memset.  Return true when the operation succeeded.  */
+
+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;
+  struct data_reference *dr = XCNEW (struct data_reference);
+  location_t loc = gimple_location (stmt);
+
+  DR_STMT (dr) = stmt;
+  DR_REF (dr) = op0;
+  res = dr_analyze_innermost (dr);
+  gcc_assert (res && stride_of_unit_type_p (DR_STEP (dr), TREE_TYPE (op0)));
+
+  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);
+
+  /* Test for a negative stride, iterating over every element.  */
+  if (integer_zerop (size_binop (PLUS_EXPR,
+				 TYPE_SIZE_UNIT (TREE_TYPE (op0)),
+				 fold_convert (sizetype, DR_STEP (dr)))))
+    {
+      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);
+  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);
+  gsi_insert_seq_after (&bsi, stmt_list, GSI_CONTINUE_LINKING);
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "generated memset zero\n");
+
+  free_data_ref (dr);
+}
+
+/* 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.  */
+
+static bool
+generate_builtin (struct loop *loop, bitmap partition, bool copy_p)
+{
+  bool res = false;
+  unsigned i, x = 0;
+  basic_block *bbs;
+  gimple write = NULL;
+  gimple_stmt_iterator bsi;
+  tree nb_iter = number_of_exit_cond_executions (loop);
+
+  if (!nb_iter || nb_iter == chrec_dont_know)
+    return false;
+
+  bbs = get_loop_body_in_dom_order (loop);
+
+  for (i = 0; i < loop->num_nodes; i++)
+    {
+      basic_block bb = bbs[i];
+
+      for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+	x++;
+
+      for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+	{
+	  gimple stmt = gsi_stmt (bsi);
+
+	  if (gimple_code (stmt) == GIMPLE_LABEL
+	      || is_gimple_debug (stmt))
+	    continue;
+
+	  if (!bitmap_bit_p (partition, x++))
+	    continue;
+
+	  /* If the stmt has uses outside of the loop fail.  */
+	  if (stmt_has_scalar_dependences_outside_loop (stmt))
+	    goto end;
+
+	  if (is_gimple_assign (stmt)
+	      && !is_gimple_reg (gimple_assign_lhs (stmt)))
+	    {
+	      /* Don't generate the builtins when there are more than
+		 one memory write.  */
+	      if (write != NULL)
+		goto end;
+
+	      write = stmt;
+	      if (bb == loop->latch)
+		nb_iter = number_of_latch_executions (loop);
+	    }
+	}
+    }
+
+  if (!stmt_with_adjacent_zero_store_dr_p (write))
+    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);
+  res = true;
+
+  /* If this is the last partition for which we generate code, we have
+     to destroy the loop.  */
+  if (!copy_p)
+    {
+      unsigned nbbs = loop->num_nodes;
+      edge exit = single_exit (loop);
+      basic_block src = loop_preheader_edge (loop)->src, dest = exit->dest;
+      redirect_edge_pred (exit, src);
+      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,
+			       recompute_dominator (CDI_DOMINATORS, dest));
+    }
+
+ end:
+  free (bbs);
+  return res;
+}
+
+/* Generates code for PARTITION.  For simple loops, this function can
+   generate a built-in.  */
+
+static bool
+generate_code_for_partition (struct loop *loop, bitmap partition, bool copy_p)
+{
+  if (generate_builtin (loop, partition, copy_p))
+    return true;
+
+  return generate_loops_for_partition (loop, partition, copy_p);
+}
+
+
+/* Returns true if the node V of RDG cannot be recomputed.  */
+
+static bool
+rdg_cannot_recompute_vertex_p (struct graph *rdg, int v)
+{
+  if (RDG_MEM_WRITE_STMT (rdg, v))
+    return true;
+
+  return false;
+}
+
+/* Returns true when the vertex V has already been generated in the
+   current partition (V is in PROCESSED), or when V belongs to another
+   partition and cannot be recomputed (V is not in REMAINING_STMTS).  */
+
+static inline bool
+already_processed_vertex_p (bitmap processed, int v)
+{
+  return (bitmap_bit_p (processed, v)
+	  || !bitmap_bit_p (remaining_stmts, v));
+}
+
+/* Returns NULL when there is no anti-dependence among the successors
+   of vertex V, otherwise returns the edge with the anti-dep.  */
+
+static struct graph_edge *
+has_anti_dependence (struct vertex *v)
+{
+  struct graph_edge *e;
+
+  if (v->succ)
+    for (e = v->succ; e; e = e->succ_next)
+      if (RDGE_TYPE (e) == anti_dd)
+	return e;
+
+  return NULL;
+}
+
+/* Returns true when V has an anti-dependence edge among its successors.  */
+
+static bool
+predecessor_has_mem_write (struct graph *rdg, struct vertex *v)
+{
+  struct graph_edge *e;
+
+  if (v->pred)
+    for (e = v->pred; e; e = e->pred_next)
+      if (bitmap_bit_p (upstream_mem_writes, e->src)
+	  /* Don't consider flow channels: a write to memory followed
+	     by a read from memory.  These channels allow the split of
+	     the RDG in different partitions.  */
+	  && !RDG_MEM_WRITE_STMT (rdg, e->src))
+	return true;
+
+  return false;
+}
+
+/* Initializes the upstream_mem_writes bitmap following the
+   information from RDG.  */
+
+static void
+mark_nodes_having_upstream_mem_writes (struct graph *rdg)
+{
+  int v, x;
+  bitmap seen = BITMAP_ALLOC (NULL);
+
+  for (v = rdg->n_vertices - 1; v >= 0; v--)
+    if (!bitmap_bit_p (seen, v))
+      {
+	unsigned i;
+	VEC (int, heap) *nodes = VEC_alloc (int, heap, 3);
+
+	graphds_dfs (rdg, &v, 1, &nodes, false, NULL);
+
+	FOR_EACH_VEC_ELT (int, nodes, i, x)
+	  {
+	    if (!bitmap_set_bit (seen, x))
+	      continue;
+
+	    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
+		   should be placed in the same partition.  */
+		|| has_anti_dependence (&(rdg->vertices[x])))
+	      {
+		bitmap_set_bit (upstream_mem_writes, x);
+	      }
+	  }
+
+	VEC_free (int, heap, nodes);
+      }
+}
+
+/* Returns true when vertex u has a memory write node as a predecessor
+   in RDG.  */
+
+static bool
+has_upstream_mem_writes (int u)
+{
+  return bitmap_bit_p (upstream_mem_writes, u);
+}
+
+static void rdg_flag_vertex_and_dependent (struct graph *, int, bitmap, bitmap,
+					   bitmap, bool *);
+
+/* 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,
+	       bitmap processed, bool *part_has_writes)
+{
+  use_operand_p use_p;
+  struct vertex *x = &(rdg->vertices[u]);
+  gimple stmt = RDGV_STMT (x);
+  struct graph_edge *anti_dep = has_anti_dependence (x);
+
+  /* Keep in the same partition the destination of an antidependence,
+     because this is a store to the exact same location.  Putting this
+     in another partition is bad for cache locality.  */
+  if (anti_dep)
+    {
+      int v = anti_dep->dest;
+
+      if (!already_processed_vertex_p (processed, v))
+	rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
+				       processed, part_has_writes);
+    }
+
+  if (gimple_code (stmt) != GIMPLE_PHI)
+    {
+      if ((use_p = gimple_vuse_op (stmt)) != NULL_USE_OPERAND_P)
+	{
+	  tree use = USE_FROM_PTR (use_p);
+
+	  if (TREE_CODE (use) == SSA_NAME)
+	    {
+	      gimple def_stmt = SSA_NAME_DEF_STMT (use);
+	      int v = rdg_vertex_for_stmt (rdg, def_stmt);
+
+	      if (v >= 0
+		  && !already_processed_vertex_p (processed, v))
+		rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
+					       processed, part_has_writes);
+	    }
+	}
+    }
+
+  if (is_gimple_assign (stmt) && has_upstream_mem_writes (u))
+    {
+      tree op0 = gimple_assign_lhs (stmt);
+
+      /* Scalar channels don't have enough space for transmitting data
+	 between tasks, unless we add more storage by privatizing.  */
+      if (is_gimple_reg (op0))
+	{
+	  use_operand_p use_p;
+	  imm_use_iterator iter;
+
+	  FOR_EACH_IMM_USE_FAST (use_p, iter, op0)
+	    {
+	      int v = rdg_vertex_for_stmt (rdg, USE_STMT (use_p));
+
+	      if (!already_processed_vertex_p (processed, v))
+		rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
+					       processed, part_has_writes);
+	    }
+	}
+    }
+}
+
+/* Flag V from RDG as part of PARTITION, and also flag its loop number
+   in LOOPS.  */
+
+static void
+rdg_flag_vertex (struct graph *rdg, int v, bitmap partition, bitmap loops,
+		 bool *part_has_writes)
+{
+  struct loop *loop;
+
+  if (!bitmap_set_bit (partition, v))
+    return;
+
+  loop = loop_containing_stmt (RDG_STMT (rdg, v));
+  bitmap_set_bit (loops, loop->num);
+
+  if (rdg_cannot_recompute_vertex_p (rdg, v))
+    {
+      *part_has_writes = true;
+      bitmap_clear_bit (remaining_stmts, v);
+    }
+}
+
+/* Flag in the bitmap PARTITION the vertex V and all its predecessors.
+   Also flag their loop number in LOOPS.  */
+
+static void
+rdg_flag_vertex_and_dependent (struct graph *rdg, int v, bitmap partition,
+			       bitmap loops, bitmap processed,
+			       bool *part_has_writes)
+{
+  unsigned i;
+  VEC (int, heap) *nodes = VEC_alloc (int, heap, 3);
+  int x;
+
+  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_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);
+}
+
+/* Initialize CONDS with all the condition statements from the basic
+   blocks of LOOP.  */
+
+static void
+collect_condition_stmts (struct loop *loop, VEC (gimple, heap) **conds)
+{
+  unsigned i;
+  edge e;
+  VEC (edge, heap) *exits = get_loop_exit_edges (loop);
+
+  FOR_EACH_VEC_ELT (edge, exits, i, e)
+    {
+      gimple cond = last_stmt (e->src);
+
+      if (cond)
+	VEC_safe_push (gimple, heap, *conds, cond);
+    }
+
+  VEC_free (edge, heap, exits);
+}
+
+/* Add to PARTITION all the exit condition statements for LOOPS
+   together with all their dependent statements determined from
+   RDG.  */
+
+static void
+rdg_flag_loop_exits (struct graph *rdg, bitmap loops, bitmap partition,
+		     bitmap processed, bool *part_has_writes)
+{
+  unsigned i;
+  bitmap_iterator bi;
+  VEC (gimple, heap) *conds = VEC_alloc (gimple, heap, 3);
+
+  EXECUTE_IF_SET_IN_BITMAP (loops, 0, i, bi)
+    collect_condition_stmts (get_loop (i), &conds);
+
+  while (!VEC_empty (gimple, conds))
+    {
+      gimple cond = VEC_pop (gimple, conds);
+      int v = rdg_vertex_for_stmt (rdg, cond);
+      bitmap new_loops = BITMAP_ALLOC (NULL);
+
+      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_set_bit (loops, i))
+	  collect_condition_stmts (get_loop (i), &conds);
+
+      BITMAP_FREE (new_loops);
+    }
+
+  VEC_free (gimple, heap, conds);
+}
+
+/* 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)
+{
+  int i, v;
+  bitmap partition = BITMAP_ALLOC (NULL);
+  bitmap loops = BITMAP_ALLOC (NULL);
+  bitmap processed = BITMAP_ALLOC (NULL);
+
+  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);
+
+  rdg_flag_loop_exits (rdg, loops, partition, processed, part_has_writes);
+
+  BITMAP_FREE (processed);
+  BITMAP_FREE (loops);
+  return partition;
+}
+
+/* Free memory for COMPONENTS.  */
+
+static void
+free_rdg_components (VEC (rdgc, heap) *components)
+{
+  int i;
+  rdgc x;
+
+  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.  */
+
+static void
+rdg_build_components (struct graph *rdg, VEC (int, heap) *starting_vertices,
+		      VEC (rdgc, heap) **components)
+{
+  int i, v;
+  bitmap saved_components = BITMAP_ALLOC (NULL);
+  int n_components = graphds_scc (rdg, NULL);
+  VEC (int, heap) **all_components = XNEWVEC (VEC (int, heap) *, n_components);
+
+  for (i = 0; i < n_components; i++)
+    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_EACH_VEC_ELT (int, starting_vertices, i, v)
+    {
+      int c = rdg->vertices[v].component;
+
+      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);
+	}
+    }
+
+  for (i = 0; i < n_components; i++)
+    if (!bitmap_bit_p (saved_components, i))
+      VEC_free (int, heap, all_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 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
+rdg_build_partitions (struct graph *rdg, VEC (rdgc, heap) *components,
+		      VEC (int, heap) **other_stores,
+		      VEC (bitmap, heap) **partitions, bitmap processed)
+{
+  int i;
+  rdgc x;
+  bitmap partition = BITMAP_ALLOC (NULL);
+
+  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);
+      bitmap_ior_into (partition, np);
+      bitmap_ior_into (processed, np);
+      BITMAP_FREE (np);
+
+      if (part_has_writes)
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "ldist useful partition:\n");
+	      dump_bitmap (dump_file, partition);
+	    }
+
+	  VEC_safe_push (bitmap, heap, *partitions, partition);
+	  partition = BITMAP_ALLOC (NULL);
+	}
+    }
+
+  /* Add the nodes from the RDG that were not marked as processed, and
+     that are used outside the current loop.  These are scalar
+     computations that are not yet part of previous partitions.  */
+  for (i = 0; i < rdg->n_vertices; i++)
+    if (!bitmap_bit_p (processed, i)
+	&& rdg_defs_used_in_other_loops_p (rdg, i))
+      VEC_safe_push (int, heap, *other_stores, i);
+
+  /* If there are still statements left in the OTHER_STORES array,
+     create other components and partitions with these stores and
+     their dependences.  */
+  if (VEC_length (int, *other_stores) > 0)
+    {
+      VEC (rdgc, heap) *comps = VEC_alloc (rdgc, heap, 3);
+      VEC (int, heap) *foo = VEC_alloc (int, heap, 3);
+
+      rdg_build_components (rdg, *other_stores, &comps);
+      rdg_build_partitions (rdg, comps, &foo, partitions, processed);
+
+      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_EACH_VEC_ELT (bitmap, partitions, i, partition)
+    debug_bitmap_file (file, partition);
+}
+
+/* Debug PARTITIONS.  */
+extern void debug_rdg_partitions (VEC (bitmap, heap) *);
+
+DEBUG_FUNCTION void
+debug_rdg_partitions (VEC (bitmap, heap) *partitions)
+{
+  dump_rdg_partitions (stderr, partitions);
+}
+
+/* Returns the number of read and write operations in the RDG.  */
+
+static int
+number_of_rw_in_rdg (struct graph *rdg)
+{
+  int i, res = 0;
+
+  for (i = 0; i < rdg->n_vertices; i++)
+    {
+      if (RDG_MEM_WRITE_STMT (rdg, i))
+	++res;
+
+      if (RDG_MEM_READS_STMT (rdg, i))
+	++res;
+    }
+
+  return res;
+}
+
+/* Returns the number of read and write operations in a PARTITION of
+   the RDG.  */
+
+static int
+number_of_rw_in_partition (struct graph *rdg, bitmap partition)
+{
+  int res = 0;
+  unsigned i;
+  bitmap_iterator ii;
+
+  EXECUTE_IF_SET_IN_BITMAP (partition, 0, i, ii)
+    {
+      if (RDG_MEM_WRITE_STMT (rdg, i))
+	++res;
+
+      if (RDG_MEM_READS_STMT (rdg, i))
+	++res;
+    }
+
+  return res;
+}
+
+/* Returns true when one of the PARTITIONS contains all the read or
+   write operations of RDG.  */
+
+static bool
+partition_contains_all_rw (struct graph *rdg, VEC (bitmap, heap) *partitions)
+{
+  int i;
+  bitmap partition;
+  int nrw = number_of_rw_in_rdg (rdg);
+
+  FOR_EACH_VEC_ELT (bitmap, partitions, i, partition)
+    if (nrw == number_of_rw_in_partition (rdg, partition))
+      return true;
+
+  return false;
+}
+
+/* Generate code from STARTING_VERTICES in RDG.  Returns the number of
+   distributed loops.  */
+
+static int
+ldist_gen (struct loop *loop, struct graph *rdg,
+	   VEC (int, heap) *starting_vertices)
+{
+  int i, nbp;
+  VEC (rdgc, heap) *components = VEC_alloc (rdgc, heap, 3);
+  VEC (bitmap, heap) *partitions = VEC_alloc (bitmap, heap, 3);
+  VEC (int, heap) *other_stores = VEC_alloc (int, heap, 3);
+  bitmap partition, processed = BITMAP_ALLOC (NULL);
+
+  remaining_stmts = BITMAP_ALLOC (NULL);
+  upstream_mem_writes = BITMAP_ALLOC (NULL);
+
+  for (i = 0; i < rdg->n_vertices; i++)
+    {
+      bitmap_set_bit (remaining_stmts, i);
+
+      /* Save in OTHER_STORES all the memory writes that are not in
+	 STARTING_VERTICES.  */
+      if (RDG_MEM_WRITE_STMT (rdg, i))
+	{
+	  int v;
+	  unsigned j;
+	  bool found = false;
+
+	  FOR_EACH_VEC_ELT (int, starting_vertices, j, v)
+	    if (i == v)
+	      {
+		found = true;
+		break;
+	      }
+
+	  if (!found)
+	    VEC_safe_push (int, heap, other_stores, i);
+	}
+    }
+
+  mark_nodes_having_upstream_mem_writes (rdg);
+  rdg_build_components (rdg, starting_vertices, &components);
+  rdg_build_partitions (rdg, components, &other_stores, &partitions,
+			processed);
+  BITMAP_FREE (processed);
+  nbp = VEC_length (bitmap, partitions);
+
+  if (nbp <= 1
+      || partition_contains_all_rw (rdg, partitions))
+    goto ldist_done;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    dump_rdg_partitions (dump_file, partitions);
+
+  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_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);
+  return nbp;
+}
+
+/* Distributes the code from LOOP in such a way that producer
+   statements are placed before consumer statements.  When STMTS is
+   NULL, performs the maximal distribution, if STMTS is not NULL,
+   tries to separate only these statements from the LOOP's body.
+   Returns the number of distributed loops.  */
+
+static int
+distribute_loop (struct loop *loop, VEC (gimple, heap) *stmts)
+{
+  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,
+		 "FIXME: Loop %d not distributed: it has more than two basic blocks.\n",
+		 loop->num);
+
+      return res;
+    }
+
+  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_EACH_VEC_ELT (gimple, stmts, i, s)
+    {
+      int v = rdg_vertex_for_stmt (rdg, s);
+
+      if (v >= 0)
+	{
+	  VEC_safe_push (int, heap, vertices, v);
+
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file,
+		     "ldist asked to generate code for vertex %d\n", v);
+	}
+    }
+
+  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.  */
+
+static unsigned int
+tree_loop_distribution (void)
+{
+  struct loop *loop;
+  loop_iterator li;
+  int nb_generated_loops = 0;
+
+  FOR_EACH_LOOP (li, loop, 0)
+    {
+      VEC (gimple, heap) *work_list = NULL;
+      int num = loop->num;
+
+      /* If the loop doesn't have a single exit we will fail anyway,
+	 so do that early.  */
+      if (!single_exit (loop))
+	continue;
+
+      /* If both flag_tree_loop_distribute_patterns and
+	 flag_tree_loop_distribution are set, then only
+	 distribute_patterns is executed.  */
+      if (flag_tree_loop_distribute_patterns)
+	{
+	  /* 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",
+		     num, nb_generated_loops);
+	  else
+	    fprintf (dump_file, "Loop %d is the same.\n", num);
+	}
+
+      verify_loop_structure ();
+
+      VEC_free (gimple, heap, work_list);
+    }
+
+  return 0;
+}
+
+static bool
+gate_tree_loop_distribution (void)
+{
+  return flag_tree_loop_distribution
+    || flag_tree_loop_distribute_patterns;
+}
+
+struct gimple_opt_pass pass_loop_distribution =
+{
+ {
+  GIMPLE_PASS,
+  "ldist",			/* name */
+  gate_tree_loop_distribution,  /* gate */
+  tree_loop_distribution,       /* execute */
+  NULL,				/* sub */
+  NULL,				/* next */
+  0,				/* static_pass_number */
+  TV_TREE_LOOP_DISTRIBUTION,    /* tv_id */
+  PROP_cfg | PROP_ssa,		/* properties_required */
+  0,				/* properties_provided */
+  0,				/* properties_destroyed */
+  0,				/* todo_flags_start */
+  TODO_dump_func                /* todo_flags_finish */
+ }
+};