Re: [PATCH 2/4] df: Add DF_LIVE_SUBREG problem

[Dimitar Dimitrov <dimitar@dinux.eu>]

On Wed, Apr 24, 2024 at 06:05:03PM +0800, Lehua Ding wrote:
> This patch add a new DF problem, named DF_LIVE_SUBREG. This problem
> is extended from the DF_LR problem and support track the subreg liveness
> of multireg pseudo if these pseudo satisfy the following conditions:
> 
>   1. the mode size greater than it's REGMODE_NATURAL_SIZE.
>   2. the reg is used in insns via subreg pattern.
> 
> The main methods are as follows:
> 
>   1. split bitmap in/out/def/use fileds to full_in/out/def/use and
>      partial_in/out/def/use. If a pseudo need to be tracked it's subreg
>      liveness, then it is recorded in partial_in/out/def/use fileds.
>      Meantimes, there are range_in/out/def/use fileds which records the live
>      range of the tracked pseudo.
>   2. in the df_live_subreg_finalize function, we move the tracked pseudo from
>      the partial_in/out/def/use to full_in/out/def/use if the pseudo's live
>      range is full.

Hi Lehua,

I'm not familiar with LRA, so my comments bellow could be totally off
point.  Please treat them as mild suggestions.

> 
> gcc/ChangeLog:
> 
> 	* Makefile.in: Add subreg-live-range object file.
> 	* df-problems.cc (struct df_live_subreg_problem_data): Private struct
> 	for DF_LIVE_SUBREG problem.
> 	(df_live_subreg_get_bb_info): getting bb regs in/out data.
> 	(get_live_subreg_local_bb_info): getting bb regs use/def data.
> 	(multireg_p): checking is the regno a pseudo multireg.
> 	(need_track_subreg_p): checking is the regno need to be tracked.
> 	(init_range): getting the range of subreg rtx.
> 	(remove_subreg_range): removing use data for the reg/subreg rtx.
> 	(add_subreg_range): adding def/use data for the reg/subreg rtx.
> 	(df_live_subreg_free_bb_info): Free basic block df data.
> 	(df_live_subreg_alloc): Allocate and init df data.
> 	(df_live_subreg_reset): Reset the live in/out df data.
> 	(df_live_subreg_bb_local_compute): Compute basic block df data.
> 	(df_live_subreg_local_compute): Compute all basic blocks df data.
> 	(df_live_subreg_init): Init the in/out df data.
> 	(df_live_subreg_check_result): Assert the full and partial df data.
> 	(df_live_subreg_confluence_0): Confluence function for infinite loops.
> 	(df_live_subreg_confluence_n): Confluence function for normal edge.
> 	(df_live_subreg_transfer_function): Transfer function.
> 	(df_live_subreg_finalize): Finalize the all_in/all_out df data.
> 	(df_live_subreg_free): Free the df data.
> 	(df_live_subreg_top_dump): Dump top df data.
> 	(df_live_subreg_bottom_dump): Dump bottom df data.
> 	(df_live_subreg_add_problem): Add the DF_LIVE_SUBREG problem.
> 	* df.h (enum df_problem_id): Add DF_LIVE_SUBREG.
> 	(class subregs_live): Simple decalare.
> 	(class df_live_subreg_local_bb_info): New class for full/partial def/use
> 	df data.
> 	(class df_live_subreg_bb_info): New class for full/partial in/out
> 	df data.
> 	(df_live_subreg): getting the df_live_subreg data.
> 	(df_live_subreg_add_problem): Exported.
> 	(df_live_subreg_finalize): Ditto.
> 	(df_live_subreg_check_result): Ditto.
> 	(multireg_p): Ditto.
> 	(init_range): Ditto.
> 	(add_subreg_range): Ditto.
> 	(remove_subreg_range): Ditto.
> 	(df_get_subreg_live_in): Accessor the all_in df data.
> 	(df_get_subreg_live_out): Accessor the all_out df data.
> 	(df_get_subreg_live_full_in): Accessor the full_in df data.
> 	(df_get_subreg_live_full_out): Accessor the full_out df data.
> 	(df_get_subreg_live_partial_in): Accessor the partial_in df data.
> 	(df_get_subreg_live_partial_out): Accessor the partial_out df data.
> 	(df_get_subreg_live_range_in): Accessor the range_in df data.
> 	(df_get_subreg_live_range_out): Accessor the range_out df data.
> 	* regs.h (get_nblocks): Get the blocks of mode.
> 	* sbitmap.cc (bitmap_full_p): sbitmap predicator.
> 	(bitmap_same_p): sbitmap predicator.
> 	(test_full): test bitmap_full_p.
> 	(test_same): test bitmap_same_p.
> 	(sbitmap_cc_tests): Add test_full and test_same.
> 	* sbitmap.h (bitmap_full_p): Exported.
> 	(bitmap_same_p): Ditto.
> 	* timevar.def (TV_DF_LIVE_SUBREG): add DF_LIVE_SUBREG timevar.
> 	* subreg-live-range.cc: New file.
> 	* subreg-live-range.h: New file.
> ---
>  gcc/Makefile.in          |   1 +
>  gcc/df-problems.cc       | 855 ++++++++++++++++++++++++++++++++++++++-
>  gcc/df.h                 | 155 +++++++
>  gcc/regs.h               |   5 +
>  gcc/sbitmap.cc           |  98 +++++
>  gcc/sbitmap.h            |   2 +
>  gcc/subreg-live-range.cc |  53 +++
>  gcc/subreg-live-range.h  | 206 ++++++++++
>  gcc/timevar.def          |   1 +
>  9 files changed, 1375 insertions(+), 1 deletion(-)
>  create mode 100644 gcc/subreg-live-range.cc
>  create mode 100644 gcc/subreg-live-range.h
> 
> diff --git a/gcc/Makefile.in b/gcc/Makefile.in
> index a74761b7ab3..e195238f6ab 100644
> --- a/gcc/Makefile.in
> +++ b/gcc/Makefile.in
> @@ -1684,6 +1684,7 @@ OBJS = \
>  	store-motion.o \
>  	streamer-hooks.o \
>  	stringpool.o \
> +	subreg-live-range.o \
>  	substring-locations.o \
>  	target-globals.o \
>  	targhooks.o \
> diff --git a/gcc/df-problems.cc b/gcc/df-problems.cc
> index 88ee0dd67fc..93c5b52146c 100644
> --- a/gcc/df-problems.cc
> +++ b/gcc/df-problems.cc
> @@ -28,6 +28,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include "target.h"
>  #include "rtl.h"
>  #include "df.h"
> +#include "subreg-live-range.h"
>  #include "memmodel.h"
>  #include "tm_p.h"
>  #include "insn-config.h"
> @@ -1344,8 +1345,860 @@ df_lr_verify_transfer_functions (void)
>    bitmap_clear (&all_blocks);
>  }
>  
> +/*----------------------------------------------------------------------------
> +   REGISTER AND SUBREGS LIVES
> +   Like DF_LR, but include tracking subreg liveness. Currently used to provide
Nit: Should have two spaces after the dot, per GNU coding style.  I'd suggest
to run the contrib/check_GNU_style.py script on your patches.

> +   subreg liveness related information to the register allocator. The subreg
> +   information is currently tracked for registers that satisfy the following
> +   conditions:
> +     1. REG is a pseudo register
> +     2. MODE_SIZE > UNIT_SIZE
> +     3. MODE_SIZE is a multiple of UNIT_SIZE
> +     4. REG is used via subreg pattern
> +   Assuming: MODE = the machine mode of the REG
> +	     MODE_SIZE = GET_MODE_SIZE (MODE)
> +	     UNIT_SIZE = REGMODE_NATURAL_SIZE (MODE)
> +   Condition 3 is currently strict, maybe it can be removed in the future, but
> +   for now it is sufficient.
> +   ----------------------------------------------------------------------------*/
> +
> +/* These two empty data are used as default data in case the user does not turn
> + * on the track-subreg-liveness feature.  */
> +bitmap_head empty_bitmap;
> +subregs_live empty_live;
These names seem a bit too short for global variables.  Perhaps tuck
them in a namespace?

Also, since these must remain empty, shouldn't they be declared as const?

namespace df {
   const bitmap_head empty_bitmap;
   const subregs_live empty_live;
}


> +
> +/* Private data for live_subreg problem.  */
> +struct df_live_subreg_problem_data
> +{
> +  /* Record registers that need to track subreg liveness.  */
> +  bitmap_head tracked_regs;
> +  /* An obstack for the bitmaps we need for this problem.  */
> +  bitmap_obstack live_subreg_bitmaps;
> +};
> +
> +/* Helper functions */
> +
> +static df_live_subreg_bb_info *
> +df_live_subreg_get_bb_info (unsigned int index)
> +{
> +  if (index < df_live_subreg->block_info_size)
> +    return &(
> +      (class df_live_subreg_bb_info *) df_live_subreg->block_info)[index];
Please consider using C++ instead:
   return &static_cast<df_live_subreg_bb_info *>(df_live_subreg->block_info)[index];

> +  else
> +    return NULL;
Use nullptr instead?

> +}
> +
> +static df_live_subreg_local_bb_info *
> +get_live_subreg_local_bb_info (unsigned int bb_index)
> +{
> +  return df_live_subreg_get_bb_info (bb_index);
> +}
> +
> +/* Return true if regno is a multireg.  */
> +bool
> +multireg_p (int regno)
> +{
> +  if (regno < FIRST_PSEUDO_REGISTER)
> +    return false;
> +  rtx regno_rtx = regno_reg_rtx[regno];
> +  machine_mode reg_mode = GET_MODE (regno_rtx);
> +  poly_int64 total_size = GET_MODE_SIZE (reg_mode);
> +  poly_int64 natural_size = REGMODE_NATURAL_SIZE (reg_mode);
> +  return maybe_gt (total_size, natural_size)
> +	 && multiple_p (total_size, natural_size);
> +}
> +
> +/* Return true if the REGNO need be track with subreg liveness.  */
> +
> +static bool
> +need_track_subreg_p (unsigned regno)
> +{
> +  struct df_live_subreg_problem_data *problem_data
> +    = (struct df_live_subreg_problem_data *) df_live_subreg->problem_data;

Here auto could be used:

    auto problem_data = (struct df_live_subreg_problem_data *) df_live_subreg->problem_data;

> +  return bitmap_bit_p (&problem_data->tracked_regs, regno);
> +}
> +
> +/* Return the subreg_range of REF.  */
Is this comment valid? I see neither a REF parameter, nor a returned
value.  Did you perhaps mean:
  /* Fill RANGE with the subreg range for OP in REGMODE_NATURAL_SIZE
     granularity.  */

> +void
> +init_range (rtx op, sbitmap range)
> +{
> +  rtx reg = SUBREG_P (op) ? SUBREG_REG (op) : op;
> +  machine_mode reg_mode = GET_MODE (reg);
> +
> +  if (!read_modify_subreg_p (op))
> +    {
> +      bitmap_set_range (range, 0, get_nblocks (reg_mode));
> +      return;
> +    }
> +
> +  rtx subreg = op;
> +  machine_mode subreg_mode = GET_MODE (subreg);
> +  poly_int64 offset = SUBREG_BYTE (subreg);
> +  int nblocks = get_nblocks (reg_mode);
> +  poly_int64 unit_size = REGMODE_NATURAL_SIZE (reg_mode);
> +  poly_int64 subreg_size = GET_MODE_SIZE (subreg_mode);
> +  poly_int64 left = offset + subreg_size;
> +
> +  int subreg_start = -1;
> +  int subreg_nblocks = -1;
> +  for (int i = 0; i < nblocks; i += 1)
> +    {
> +      poly_int64 right = unit_size * (i + 1);
> +      if (subreg_start < 0 && maybe_lt (offset, right))
> +	subreg_start = i;
> +      if (subreg_nblocks < 0 && maybe_le (left, right))
> +	{
> +	  subreg_nblocks = i + 1 - subreg_start;
> +	  break;
> +	}
> +    }
> +  gcc_assert (subreg_start >= 0 && subreg_nblocks > 0);
> +
> +  bitmap_set_range (range, subreg_start, subreg_nblocks);
> +}
> +
> +/* Remove RANGE from BB_INFO's use data.  */
> +void
> +remove_subreg_range (df_live_subreg_local_bb_info *bb_info, unsigned int regno,
> +		     const_sbitmap range)
> +{
> +  bitmap partial = &bb_info->partial_use;
> +
> +  bb_info->range_use->remove_range (regno, range);
> +  if (bb_info->range_use->empty_p (regno))
> +    bitmap_clear_bit (partial, regno);
> +}
> +
> +/* Remove RANGE of REF from BB_INFO's use data.  */
> +static void
> +remove_subreg_range (df_live_subreg_local_bb_info *bb_info, df_ref ref)
> +{
> +  unsigned int regno = DF_REF_REGNO (ref);
> +  machine_mode reg_mode = GET_MODE (DF_REF_REAL_REG (ref));
> +
> +  if (need_track_subreg_p (regno))
> +    {
> +      auto_sbitmap range (get_nblocks (reg_mode));
> +      init_range (DF_REF_REG (ref), range);
> +      remove_subreg_range (bb_info, regno, range);
> +    }
> +  else
> +    {
> +      bitmap_clear_bit (&bb_info->full_use, regno);
> +      gcc_assert (!bitmap_bit_p (&bb_info->partial_use, regno));
> +      gcc_assert (!bitmap_bit_p (&bb_info->partial_def, regno));
> +    }
> +}
> +
> +/* add RANGE to BB_INFO's def/use. If is_def is true, means for BB_INFO's def,
> +   otherwise for BB_INFO's use.  */
> +void
> +add_subreg_range (df_live_subreg_local_bb_info *bb_info, unsigned int regno,
> +		  const_sbitmap range, bool is_def)
Would it be more clear to split into two separate functions
instead of using a boolean flag? E.g.:
  add_subreg_range_to_def (df_live_subreg_local_bb_info *bb_info, unsigned int regno,
               const_sbitmap range)
  add_subreg_range_to_use (df_live_subreg_local_bb_info *bb_info, unsigned int regno,
               const_sbitmap range)

> +{
> +  bitmap partial = is_def ? &bb_info->partial_def : &bb_info->partial_use;
> +  subregs_live *range_live = is_def ? bb_info->range_def : bb_info->range_use;
> +
> +  bitmap_set_bit (partial, regno);
> +  range_live->add_range (regno, range);
> +}
> +
> +/* add RANGE of REF to BB_INFO def/use. If is_def is true, means for BB_INFO's
> +   def, otherwise for BB_INFO's use.  */
> +static void
> +add_subreg_range (df_live_subreg_local_bb_info *bb_info, df_ref ref,
> +		  bool is_def)
> +{
> +  unsigned int regno = DF_REF_REGNO (ref);
> +  machine_mode reg_mode = GET_MODE (DF_REF_REAL_REG (ref));
> +
> +  if (need_track_subreg_p (regno))
> +    {
> +      auto_sbitmap range (get_nblocks (reg_mode));
> +      init_range (DF_REF_REG (ref), range);
> +      add_subreg_range (bb_info, regno, range, is_def);
> +    }
> +  else
> +    {
> +      bitmap full = is_def ? &bb_info->full_def : &bb_info->full_use;
> +      bitmap partial = is_def ? &bb_info->partial_def : &bb_info->partial_use;
> +      bitmap_set_bit (full, regno);
> +      gcc_assert (!bitmap_bit_p (partial, regno));
> +    }
> +}
> +
> +/* Free basic block info.  */
> +
> +static void
> +df_live_subreg_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, void *vbb_info)
> +{
> +  df_live_subreg_bb_info *bb_info = (df_live_subreg_bb_info *) vbb_info;
Perhaps:
     auto bb_info = static_cast<df_live_subreg_bb_info *> vbb_info;

> +  if (bb_info)
> +    {
> +      delete bb_info->range_in;
> +      bb_info->range_in = NULL;
> +      delete bb_info->range_out;
> +      bb_info->range_out = NULL;
> +
> +      bitmap_clear (&bb_info->all_in);
> +      bitmap_clear (&bb_info->full_in);
> +      bitmap_clear (&bb_info->partial_in);
> +      bitmap_clear (&bb_info->all_out);
> +      bitmap_clear (&bb_info->full_out);
> +      bitmap_clear (&bb_info->partial_out);
> +    }
> +}
> +
> +/* Allocate or reset bitmaps for DF_LIVE_SUBREG blocks. The solution bits are
> +   not touched unless the block is new.  */
> +
> +static void
> +df_live_subreg_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
> +{
> +  struct df_live_subreg_problem_data *problem_data;
> +  df_grow_bb_info (df_live_subreg);
> +  if (df_live_subreg->problem_data)
> +    problem_data
> +      = (struct df_live_subreg_problem_data *) df_live_subreg->problem_data;
> +  else
> +    {
> +      problem_data = XNEW (struct df_live_subreg_problem_data);
> +      df_live_subreg->problem_data = problem_data;
> +
> +      bitmap_obstack_initialize (&problem_data->live_subreg_bitmaps);
> +      bitmap_initialize (&problem_data->tracked_regs,
> +			 &problem_data->live_subreg_bitmaps);
> +    }
> +
> +  bitmap_clear (&problem_data->tracked_regs);
> +
> +  basic_block bb;
> +  FOR_EACH_BB_FN (bb, cfun)
> +    bitmap_set_bit (df_live_subreg->out_of_date_transfer_functions, bb->index);
> +
> +  bitmap_set_bit (df_live_subreg->out_of_date_transfer_functions, ENTRY_BLOCK);
> +  bitmap_set_bit (df_live_subreg->out_of_date_transfer_functions, EXIT_BLOCK);
> +
> +  unsigned int bb_index;
> +  bitmap_iterator bi;
> +  EXECUTE_IF_SET_IN_BITMAP (df_live_subreg->out_of_date_transfer_functions, 0,
> +			    bb_index, bi)
> +    {
> +      /* Find the regs which we need to track it's subreg liveness.  */
> +      rtx_insn *insn;
> +      df_ref use;
> +      FOR_BB_INSNS (bb, insn)
> +	{
> +	  if (!NONDEBUG_INSN_P (insn))
> +	    continue;
> +
> +	  df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
> +
> +	  FOR_EACH_INSN_INFO_USE (use, insn_info)
> +	    {
> +	      unsigned int regno = DF_REF_REGNO (use);
> +              /* A multireg which is used via subreg pattern.  */
> +	      if (multireg_p (regno)
> +		  && DF_REF_FLAGS (use) & (DF_REF_SUBREG))
> +		bitmap_set_bit (&problem_data->tracked_regs, regno);
> +	    }
> +	}
> +    }
> +
> +  if (dump_file)
> +    {
> +      fprintf (dump_file, ";; regs need to be tracked subreg liveness: ");
> +      df_print_regset (dump_file, &problem_data->tracked_regs);
> +    }
> +
> +  size_t n = bitmap_count_bits (&problem_data->tracked_regs);
> +
> +  EXECUTE_IF_SET_IN_BITMAP (df_live_subreg->out_of_date_transfer_functions, 0,
> +			    bb_index, bi)
> +    {
> +      /* Clean global infos.  */
> +      df_live_subreg_bb_info *bb_info = df_live_subreg_get_bb_info (bb_index);

Here and for the rest of the call sites, I think auto is allowed to be used:
         auto bb_info = df_live_subreg_get_bb_info (bb_index);


Regards,
Dimitar