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

[Kenneth Zadeck <zadeck@naturalbridge.com>]

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