Re: [RFC] [modulo-sched] Change the ddg's construction

[Ayal Zaks <ZAKS at il dot ibm dot com>]

Looks good to me, with some remarks (to help make it better :) below.
Ayal.


Index: ddg.c
===================================================================
--- ddg.c   (revision 119360)
+++ ddg.c   (working copy)
@@ -217,38 +217,64 @@
     add_edge_to_ddg (g, e);
 }

+

^^^^^^
This is probably a typo.

-/* 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 RD (which is the last definition
of that
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Don't exceed 80 columns. Additional occurances below.

+   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-dependence from its uses in
the
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^s

+   current iteration to the first definition in the next iteration.  */
 static void
 add_deps_for_def (ddg_ptr g, struct df *df, struct df_ref *rd)
 {
   int regno = DF_REF_REGNO (rd);
-  struct df_ru_bb_info *bb_info = DF_RU_BB_INFO (df, g->bb);
   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);
+  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;
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Any special reason why not set it as above?

+  struct df_ref *first_def = df_bb_regno_first_def_find (df, g->bb,
regno);
+
+  gcc_assert (last_def_node);

-  /* Create and inter-loop true dependence between RD and each of its uses
-     that is upwards exposed in RD's block.  */
+  bb_info = DF_RD_BB_INFO (df, g->bb);
+
+  /* Create and inter-loop true dependence and anti dependence.  */
             ^^^                           s                   s

   for (r_use = DF_REF_CHAIN (rd); 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);
+
+      if (BLOCK_FOR_INSN (use_insn) != g->bb)
+     continue;

-       gcc_assert (src_node && dest_node);
-
-       /* Any such upwards exposed use appears before the rd def.  */
+      use_node = get_node_of_insn (g, use_insn);
+      gcc_assert (use_node);
+
+      if (use_node->cuid <= last_def_node->cuid)
+     {
+       /* Add true deps form df to it's uses in the next iteration.
^^^^^^^^^^^^^^^^^^^^^^^^^from

+             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,
+       create_ddg_dep_no_link (g, last_def_node, use_node, TRUE_DEP,
                          REG_DEP, 1);
      }
+      else if (first_def)
^^^^^^^^^^^^^^^^^^^^^^^^^^ first_def is surely not NULL; replace with an
assert.

+     {
+       /* Add anti deps from df's uses in the current iteration to the
first def
+          in the next ietration.  */
+          ddg_node_ptr first_def_node = get_node_of_insn (g,
first_def->insn);
+          gcc_assert (first_def_node);
+
+          /* 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
                                  ^^ double space
+          such a dep.  */
^^^^^^^^^^^^^^^^^^^^^ i.e. if first_def_node == last_def_node, no?

+       if (! bitmap_bit_p (bb_info->gen, first_def->id))
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ This is also ok I guess - it
checks that first_def is not downwards exposed; but it's simpler to check
if first_def_node != last_def_node.

+         create_ddg_dep_no_link (g, use_node, first_def_node, ANTI_DEP,
REG_DEP, 1);
+     }
     }

+
   /* 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
@@ -257,89 +283,40 @@
      there is a use between the two defs.  */
                     ^^^^^^^^^^^^^^^^^^^^ better clarify that this
'between' goes across the backarc.

   if (! use_before_def)
^^^^^^^^^^^^^^^^^^^^^^^^
Maybe better rename it to 'use_before_first_def'. But you probably don't
need it at all, see below.

     {
-      struct df_ref *def = df_bb_regno_first_def_find (df, g->bb, regno);
       int i;
       ddg_node_ptr dest_node;

-      if (!def || rd->id == def->id)
+      if (!first_def || rd->id == first_def->id)
           ^^^^^^^^^^ again, you can "assert (first_def);".
Consider renaming rd to last_def thereby comparison becomes 'if (last_def
== first_def)'.

      return;

       /* Check if there are uses after RD.  */
-      for (i = src_node->cuid + 1; i < g->num_nodes; i++)
+      for (i = last_def_node->cuid + 1; i < g->num_nodes; i++)
       if (df_find_use (df, g->nodes[i].insn, rd->reg))
         return;
^^^^^^^^^^
Simply check if last_def has a use inside g->bb; iff so, this use appears
'between' last_def and first_def (regardless of whether it's after last_def
or before first_def) and then don't create an output dependence from
last_def to first_def.

-      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);
^^^^^^^^^^^^^^^^
May want to add an 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 *df, struct df_ref *use)
-{
-  int i;
-  int regno = DF_REF_REGNO (use);
-  struct df_ref *first_def = df_bb_regno_first_def_find (df, 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 (df, 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 (df, g->nodes[i].insn, use->reg))
-       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, struct df *df)
 {
-  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 (df, 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 (df, rd_num);

       add_deps_for_def (g, df, rd);
     }
-
-  ru_bb_info = DF_RU_BB_INFO (df, 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 (df, u_num);
-
-      /* We are interested in uses of this BB.  */
-      if (BLOCK_FOR_INSN (use->insn) == g->bb)
-           add_deps_for_use (g, df, use);
-    }
 }

 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
Index: modulo-sched.c
===================================================================
--- modulo-sched.c      (revision 119360)
+++ modulo-sched.c      (working copy)
@@ -912,8 +912,7 @@
   /* Init Data Flow analysis, to be used in interloop dep calculation.  */
   df = df_init (DF_HARD_REGS | DF_EQUIV_NOTES | DF_SUBREGS);
   df_rd_add_problem (df, 0);
-  df_ru_add_problem (df, 0);
-  df_chain_add_problem (df, DF_DU_CHAIN | DF_UD_CHAIN);
+  df_chain_add_problem (df, DF_DU_CHAIN);
   df_analyze (df);

   if (dump_file)