[PING][PATCH] [modulo-sched] Change the ddg's construction

[Revital1 Eres <ERES@il.ibm.com>]

[-- Attachment #1: Type: text/plain, Size: 833 bytes --]


Hello,

This patch changes the ddg's construction as described in:
http://gcc.gnu.org/ml/gcc-patches/2007-03/msg00711.html (attached is
the version related to current trunk).

This patch was bootstrapped and tested on ppc64 and x86_64.

OK for mainline?

Thanks,
Revital

2007-07-29  Revital Eres  <eres@il.ibm.com>

        * ddg.c (add_deps_for_def): Rename to...
        (add deps): This.  Change implementation to use only reaching
        def and def-use chains to construct the inter loop dependencies.
        (add_deps_for_use): Remove function.
        (build_inter_loop_deps): Call add_deps function to build the
        inter loop dependencies.
        * modulo-sched.c (sms_schedule): Build only
        reaching def and def-use chains for the propose of the ddg
        construction.

(See attached file: patch_ddg.txt)

[-- Attachment #2: patch_ddg.txt --]
[-- Type: text/plain, Size: 8278 bytes --]

Index: ddg.c
===================================================================
--- ddg.c	(revision 126552)
+++ ddg.c	(working copy)
@@ -224,131 +224,103 @@
     add_edge_to_ddg (g, e);
 }
 
-\f
-/* Given a downwards exposed register def RD, add inter-loop true dependences
-   for all its uses in the next iteration, and an output dependence to the
-   first def of the next iteration.  */
+
+/* Given a downwards exposed register def LAST_DEF (which is the last
+   definition of that register in the bb), add inter-loop true dependences
+   for all its uses in the next iteration, an output dependence to the
+   first def of the next iteration and anti-dependences from its uses in
+   the current iteration to the first definition in the next iteration.
+   */
 static void
-add_deps_for_def (ddg_ptr g, struct df_ref *rd)
+add_deps (ddg_ptr g, struct df_ref *last_def)
 {
-  int regno = DF_REF_REGNO (rd);
-  struct df_ru_bb_info *bb_info = DF_RU_BB_INFO (g->bb);
+  int regno = DF_REF_REGNO (last_def);
   struct df_link *r_use;
-  int use_before_def = false;
-  rtx def_insn = DF_REF_INSN (rd);
-  ddg_node_ptr src_node = get_node_of_insn (g, def_insn);
+  int has_use_in_bb_p = false;
+  rtx def_insn = DF_REF_INSN (last_def);
+  ddg_node_ptr last_def_node = get_node_of_insn (g, def_insn);
+  ddg_node_ptr use_node;
+  struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
+  struct df_ref *first_def = df_bb_regno_first_def_find (g->bb, regno);
 
-  /* Create and inter-loop true dependence between RD and each of its uses
-     that is upwards exposed in RD's block.  */
-  for (r_use = DF_REF_CHAIN (rd); r_use != NULL; r_use = r_use->next)
+  gcc_assert (last_def_node && first_def);
+
+  /* Create inter-loop true dependences and anti dependences.  */
+  for (r_use = DF_REF_CHAIN (last_def); r_use != NULL; r_use = r_use->next)
     {
-      if (bitmap_bit_p (bb_info->gen, r_use->ref->id))
-	{
-	  rtx use_insn = DF_REF_INSN (r_use->ref);
-	  ddg_node_ptr dest_node = get_node_of_insn (g, use_insn);
+      rtx use_insn = DF_REF_INSN (r_use->ref);
 
-	  gcc_assert (src_node && dest_node);
+      if (BLOCK_FOR_INSN (use_insn) != g->bb)
+	continue;
 
-	  /* Any such upwards exposed use appears before the rd def.  */
-	  use_before_def = true;
-	  create_ddg_dep_no_link (g, src_node, dest_node, TRUE_DEP,
+      use_node = get_node_of_insn (g, use_insn);
+      gcc_assert (use_node);
+      has_use_in_bb_p = true;
+      if (use_node->cuid <= last_def_node->cuid)
+	{
+	  /* Add true deps from last_def to it's uses in the next
+	     iteration.  Any such upwards exposed use appears before
+	     the last_def def.  */
+	  create_ddg_dep_no_link (g, last_def_node, use_node, TRUE_DEP,
 				  REG_DEP, 1);
 	}
-    }
+      else
+	{
+	  /* Add anti deps from last_def's uses in the current iteration
+	     to the first def in the next iteration.  We must not
+	     add ANTI dep when there is an intra-loop TRUE dep in the
+	     opposite direction.  If the first_def reaches the USE then
+	     there is such a dep.  */
+	  ddg_node_ptr first_def_node = get_node_of_insn (g,
+							  first_def->insn);
 
-  /* Create an inter-loop output dependence between RD (which is the
-     last def in its block, being downwards exposed) and the first def
-     in its block.  Avoid creating a self output dependence.  Avoid creating
-     an output dependence if there is a dependence path between the two defs
-     starting with a true dependence followed by an anti dependence (i.e. if
-     there is a use between the two defs.  */
-  if (! use_before_def)
+	  gcc_assert (first_def_node);
+
+	  if (!bitmap_bit_p (bb_info->gen, first_def->id))
+	    create_ddg_dep_no_link (g, use_node, first_def_node, ANTI_DEP,
+				    REG_DEP, 1);
+	}
+    }
+  /* Create an inter-loop output dependence between LAST_DEF (which is the
+     last def in its block, being downwards exposed) and the first def in
+     its block.  Avoid creating a self output dependence.  Avoid creating
+     an output dependence if there is a dependence path between the two
+     defs starting with a true dependence to a use which can be in the
+     next iteration; followed by an anti dependence of that use to the
+     first def (i.e. if there is a use between the two defs.)  */
+  if (!has_use_in_bb_p)
     {
-      struct df_ref *def = df_bb_regno_first_def_find (g->bb, regno);
-      int i;
       ddg_node_ptr dest_node;
 
-      if (!def || rd->id == def->id)
+      if (last_def->id == first_def->id)
 	return;
 
-      /* Check if there are uses after RD.  */
-      for (i = src_node->cuid + 1; i < g->num_nodes; i++)
-	 if (df_find_use (g->nodes[i].insn, DF_REF_REG (rd)))
-	   return;
-
-      dest_node = get_node_of_insn (g, def->insn);
-      create_ddg_dep_no_link (g, src_node, dest_node, OUTPUT_DEP, REG_DEP, 1);
+      dest_node = get_node_of_insn (g, first_def->insn);
+      gcc_assert (dest_node);
+      create_ddg_dep_no_link (g, last_def_node, dest_node,
+			      OUTPUT_DEP, REG_DEP, 1);
     }
 }
-
-/* Given a register USE, add an inter-loop anti dependence to the first
-   (nearest BLOCK_BEGIN) def of the next iteration, unless USE is followed
-   by a def in the block.  */
-static void
-add_deps_for_use (ddg_ptr g, struct df_ref *use)
-{
-  int i;
-  int regno = DF_REF_REGNO (use);
-  struct df_ref *first_def = df_bb_regno_first_def_find (g->bb, regno);
-  ddg_node_ptr use_node;
-  ddg_node_ptr def_node;
-  struct df_rd_bb_info *bb_info;
-
-  bb_info = DF_RD_BB_INFO (g->bb);
-
-  if (!first_def)
-    return;
-
-  use_node = get_node_of_insn (g, use->insn);
-  def_node = get_node_of_insn (g, first_def->insn);
-
-  gcc_assert (use_node && def_node);
-
-  /* Make sure there are no defs after USE.  */
-  for (i = use_node->cuid + 1; i < g->num_nodes; i++)
-     if (df_find_def (g->nodes[i].insn, DF_REF_REG (use)))
-       return;
-  /* We must not add ANTI dep when there is an intra-loop TRUE dep in
-     the opposite direction. If the first_def reaches the USE then there is
-     such a dep.  */
-  if (! bitmap_bit_p (bb_info->gen, first_def->id))
-    create_ddg_dep_no_link (g, use_node, def_node, ANTI_DEP, REG_DEP, 1);
-}
-
 /* Build inter-loop dependencies, by looking at DF analysis backwards.  */
 static void
 build_inter_loop_deps (ddg_ptr g)
 {
-  unsigned rd_num, u_num;
+  unsigned rd_num;
   struct df_rd_bb_info *rd_bb_info;
-  struct df_ru_bb_info *ru_bb_info;
   bitmap_iterator bi;
 
   rd_bb_info = DF_RD_BB_INFO (g->bb);
 
-  /* Find inter-loop output and true deps by connecting downward exposed defs
-     to the first def of the BB and to upwards exposed uses.  */
+  /* Find inter-loop output, true and anti deps.  */
   EXECUTE_IF_SET_IN_BITMAP (rd_bb_info->gen, 0, rd_num, bi)
-    {
-      struct df_ref *rd = DF_DEFS_GET (rd_num);
+  {
+    struct df_ref *rd = DF_DEFS_GET (rd_num);
 
-      add_deps_for_def (g, rd);
-    }
-
-  ru_bb_info = DF_RU_BB_INFO (g->bb);
-
-  /* Find inter-loop anti deps.  We are interested in uses of the block that
-     appear below all defs; this implies that these uses are killed.  */
-  EXECUTE_IF_SET_IN_BITMAP (ru_bb_info->kill, 0, u_num, bi)
-    {
-      struct df_ref *use = DF_USES_GET (u_num);
-      if (!(DF_REF_FLAGS (use) & DF_REF_IN_NOTE))
-	/* We are interested in uses of this BB.  */
-	if (BLOCK_FOR_INSN (use->insn) == g->bb)
-	  add_deps_for_use (g, use);
-    }
+    add_deps (g, rd);
+  }
 }
 
+
 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
    to ddg G.  */
 static void
Index: modulo-sched.c
===================================================================
--- modulo-sched.c	(revision 126552)
+++ modulo-sched.c	(working copy)
@@ -914,9 +914,8 @@
   /* Init Data Flow analysis, to be used in interloop dep calculation.  */
   df_set_flags (DF_LR_RUN_DCE);
   df_rd_add_problem ();
-  df_ru_add_problem ();
   df_note_add_problem ();
-  df_chain_add_problem (DF_DU_CHAIN + DF_UD_CHAIN);
+  df_chain_add_problem (DF_DU_CHAIN);
   df_analyze ();
   regstat_compute_calls_crossed ();
   sched_init ();