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

[Kenneth Zadeck <zadeck@naturalbridge.com>]

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