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

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

[Ayal Zaks]

Revital1 Eres/Haifa/IBM wrote on 29/07/2007 20:36:19:

> 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?
>

Kenny, thanks for the quick approval. Any follow-up changes needed for df,
now that df_ru_add_problem() is left without a caller?

Revital, this is ok with me too, with some minor comments below.

Ayal.

> 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.
>
> [attachment "patch_ddg.txt" deleted by Ayal Zaks/Haifa/IBM]

> Index: ddg.c
> ===================================================================
> --- ddg.c (revision 126552)
> +++ ddg.c (working copy)
> @@ -224,131 +224,103 @@
>      add_edge_to_ddg (g, e);
>  }
>
> -
> -/* 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
      ^^^
      to

> +   first def of

the same register (possibly itself) in

> 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)

Better rename to something like add_cross_iteration_register_deps

>  {
> -  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);

Better split into two asserts.

> +
> +  /* 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
                                                     ^^^^do

> +      add ANTI dep when there is an intra-loop TRUE dep in the
> +      opposite direction

, but use regmoves to fix such disregarded ANTI deps when broken

> + .  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))

Simply check instead if first_def is not last_def?

> +     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

register

> 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))

Please comment why we no longer check and exclude such uses.

> - /* 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 ();

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

[Kenneth Zadeck]

Ayal Zaks wrote:
> Revital1 Eres/Haifa/IBM wrote on 29/07/2007 20:36:19:
>
>   
>> 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?
>>
>>     
>
> Kenny, thanks for the quick approval. Any follow-up changes needed for df,
> now that df_ru_add_problem() is left without a caller?
>
> Revital, this is ok with me too, with some minor comments below.
>
> Ayal.
>   
thanks,

I was going to submit the patch to get rid of ru as soon as your patch
was committed,

kenny
>   
>> 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.
>>
>> [attachment "patch_ddg.txt" deleted by Ayal Zaks/Haifa/IBM]
>>     
>
>   
>> Index: ddg.c
>> ===================================================================
>> --- ddg.c (revision 126552)
>> +++ ddg.c (working copy)
>> @@ -224,131 +224,103 @@
>>      add_edge_to_ddg (g, e);
>>  }
>>
>> -
>> -/* 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
>>     
>       ^^^
>       to
>
>   
>> +   first def of
>>     
>
> the same register (possibly itself) in
>
>   
>> 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)
>>     
>
> Better rename to something like add_cross_iteration_register_deps
>
>   
>>  {
>> -  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);
>>     
>
> Better split into two asserts.
>
>   
>> +
>> +  /* 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
>>     
>                                                      ^^^^do
>
>   
>> +      add ANTI dep when there is an intra-loop TRUE dep in the
>> +      opposite direction
>>     
>
> , but use regmoves to fix such disregarded ANTI deps when broken
>
>   
>> + .  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))
>>     
>
> Simply check instead if first_def is not last_def?
>
>   
>> +     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
>>     
>
> register
>
>   
>> 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))
>>     
>
> Please comment why we no longer check and exclude such uses.
>
>   
>> - /* 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 ();
>>     
>
>   

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

[Revital1 Eres]

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


> Kenny, thanks for the quick approval. Any follow-up changes needed for
df,
> now that df_ru_add_problem() is left without a caller?
>
> Revital, this is ok with me too, with some minor comments below.
>
> Ayal.

Thanks for the comments.  Regarding the following -

> > -  /* 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))
>
> Please comment why we no longer check and exclude such uses.

I'll address this in a separate patch which means we currently do not
exclude uses that appears inside a REG_EQUAL or REG_EQUIV note; I've
added ??? mark to revisit this issue later on.

Attached is the patch including the comments.

OK to mainline?

Thanks,
Revital

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

        * ddg.c (add_deps_for_def): Rename to...
        (add_cross_iteration_register_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_cross_iteration_register_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_30.txt)

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

Index: ddg.c
===================================================================
--- ddg.c	(revision 127042)
+++ ddg.c	(working copy)
@@ -223,131 +223,111 @@
     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
+   to all its uses in the next iteration, an output dependence to the
+   first def of the same register (possibly itself) in 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_cross_iteration_register_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);
+  gcc_assert (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,
+      /* ??? Do not handle uses with DF_REF_IN_NOTE notes.  */
+      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 do not add ANTI
+	     dep when there is an intra-loop TRUE dep in the opposite
+	     direction, but use regmoves to fix such disregarded ANTI
+	     deps when broken.	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 (INSN_UID (first_def->insn) != INSN_UID (last_def->insn))
+            {
+#ifdef ENABLE_CHECKING
+              gcc_assert (!bitmap_bit_p (bb_info->gen, first_def->id));
+#endif
+              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 register 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_cross_iteration_register_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 127042)
+++ modulo-sched.c	(working copy)
@@ -913,9 +913,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 ();

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

[Kenneth Zadeck]

Revital1 Eres wrote:
>> Kenny, thanks for the quick approval. Any follow-up changes needed for
>>     
> df,
>   
>> now that df_ru_add_problem() is left without a caller?
>>
>> Revital, this is ok with me too, with some minor comments below.
>>
>> Ayal.
>>     
>
> Thanks for the comments.  Regarding the following -
>
>   
>>> -  /* 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))
>>>       
>> Please comment why we no longer check and exclude such uses.
>>     
>
>   
Note that if you do set the flag DF_EQ_NOTES before you build the
chains, you will not get chains to or from REG_EQUAL or REG_EQUIV
notes.  It will appear as if those refs were no there.  You can still
get to the refs by looking at the DF_INSN_EQ_USES, but that is the only
place they will be visible.

Kenny

> I'll address this in a separate patch which means we currently do not
> exclude uses that appears inside a REG_EQUAL or REG_EQUIV note; I've
> added ??? mark to revisit this issue later on.
>
> Attached is the patch including the comments.
>
> OK to mainline?
>
> Thanks,
> Revital
>
> 2007-07-30  Revital Eres  <eres@il.ibm.com>
>
>         * ddg.c (add_deps_for_def): Rename to...
>         (add_cross_iteration_register_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_cross_iteration_register_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_30.txt)
> ------------------------------------------------------------------------
>
> Index: ddg.c
> ===================================================================
> --- ddg.c	(revision 127042)
> +++ ddg.c	(working copy)
> @@ -223,131 +223,111 @@
>      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
> +   to all its uses in the next iteration, an output dependence to the
> +   first def of the same register (possibly itself) in 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_cross_iteration_register_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);
> +  gcc_assert (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,
> +      /* ??? Do not handle uses with DF_REF_IN_NOTE notes.  */
> +      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 do not add ANTI
> +	     dep when there is an intra-loop TRUE dep in the opposite
> +	     direction, but use regmoves to fix such disregarded ANTI
> +	     deps when broken.	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 (INSN_UID (first_def->insn) != INSN_UID (last_def->insn))
> +            {
> +#ifdef ENABLE_CHECKING
> +              gcc_assert (!bitmap_bit_p (bb_info->gen, first_def->id));
> +#endif
> +              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 register 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_cross_iteration_register_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 127042)
> +++ modulo-sched.c	(working copy)
> @@ -913,9 +913,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 ();
>   

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

[Ayal Zaks]

Revital1 Eres/Haifa/IBM wrote on 30/07/2007 22:13:53:

>
> > Kenny, thanks for the quick approval. Any follow-up changes needed for
df,
> > now that df_ru_add_problem() is left without a caller?
> >
> > Revital, this is ok with me too, with some minor comments below.
> >
> > Ayal.
>
> Thanks for the comments.  Regarding the following -
>
> > > -  /* 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))
> >
> > Please comment why we no longer check and exclude such uses.

> I'll address this in a separate patch which means we currently do not
> exclude uses that appears inside a REG_EQUAL or REG_EQUIV note; I've
> added ??? mark to revisit this issue later on.
>
> Attached is the patch including the comments.
>
> OK to mainline?
>

OK.

Instead of checking
> +          if (INSN_UID (first_def->insn) != INSN_UID (last_def->insn))
for anti-deps you could simply check
> +      if (last_def->id == first_def->id)
as done for output-deps.

Ayal.


> Thanks,
> Revital

> 2007-07-30  Revital Eres  <eres@il.ibm.com>
>
>         * ddg.c (add_deps_for_def): Rename to...
>         (add_cross_iteration_register_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_cross_iteration_register_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.
>
> [attachment "patch_ddg_30.txt" deleted by Ayal Zaks/Haifa/IBM]

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

[Revital1 Eres]

> > I'll address this in a separate patch which means we currently do not
> > exclude uses that appears inside a REG_EQUAL or REG_EQUIV note; I've
> > added ??? mark to revisit this issue later on.
> >
> > Attached is the patch including the comments.
> >
> > OK to mainline?
> >

> OK.
>
> Instead of checking
> > +          if (INSN_UID (first_def->insn) != INSN_UID (last_def->insn))
> for anti-deps you could simply check
> > +      if (last_def->id == first_def->id)
> as done for output-deps.
>
> Ayal.

I'll check it in with this change.

Revital
>
> > Thanks,
> > Revital

> > 2007-07-30  Revital Eres  <eres@il.ibm.com>
> >
> >         * ddg.c (add_deps_for_def): Rename to...
> >         (add_cross_iteration_register_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_cross_iteration_register_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.
> >
> > [attachment "patch_ddg_30.txt" deleted by Ayal Zaks/Haifa/IBM]

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

[Kenneth Zadeck]

Revital1 Eres wrote:
> 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?
>
>   
ok for trunk.

kenny
> 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)
> ------------------------------------------------------------------------
>
> 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 ();
>   

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

[Revital1 Eres]

[-- 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 ();