Re: [SUBREG V4 2/4] DF: Add DF_LIVE_SUBREG problem

[Richard Sandiford <richard.sandiford@arm.com>]

Thanks for the update!

In terms of high-level comments:

- It looks like the code processes normal pseudos as well as subregs.
  Is that necessary?  The handling of single-register pseudos should
  be fully redundant with the normal liveness tracking.

  I think if possible we should just process pseudos for which
  need_track_subreg_p is true.

- It looks like the information uses a map from register numbers to
  sbitmaps.  That seems like quite an expensive structure.

  The way I'd imagined it working, we'd instead precompute a mapping
  from pseudo registers to a zero-based "subreg id".  A pseudo that
  has N blocks would have N consecutive subreg ids.  We could then
  have a single bitmap (rather than sbitmap) for all subreg ids.

  For example, if we have:

  P == FIRST_PSEUDO_REGISTER

  reg P:   2 subregisters: subreg ids [0, 1]
  reg P+1: 1 subregister:  ignored
  reg P+2: 4 subregisters: subreg ids [2, 5]
  reg P+3: 1 subregister:  ignored

  The map from pseudo registers to subreg ids could be linear array or
  a hash map.  I don't have a good intuition for which would be better,
  but a linear array sounds like the best starting point.

Some individual comments below:

Juzhe-Zhong <juzhe.zhong@rivai.ai> writes:
> ---
>  gcc/Makefile.in          |   1 +
>  gcc/df-problems.cc       | 886 ++++++++++++++++++++++++++++++++++++++-
>  gcc/df.h                 | 159 +++++++
>  gcc/regs.h               |   5 +
>  gcc/sbitmap.cc           |  98 +++++
>  gcc/sbitmap.h            |   2 +
>  gcc/subreg-live-range.cc | 233 ++++++++++
>  gcc/subreg-live-range.h  |  60 +++
>  gcc/timevar.def          |   1 +
>  9 files changed, 1444 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 a7f15694c34..67d2e3ca1bc 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..01f1f850925 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,891 @@ 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
> +   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.  */

Nit: should be no leading "*" on this line.

Maybe:

/* Data for an empty subreg problem, for cases in which subreg tracking
   is not enabled.  */

> +bitmap_head df_subreg_empty_bitmap;
> +subregs_live df_subreg_empty_live;
> +
> +/* Private data for live_subreg problem.  */
> +struct df_live_subreg_problem_data
> +{
> +  /* Record registers that need to track subreg liveness.  */

Maybe:

  /* The set of pseudo registers to track.  */

But with the linear array described above, it would be simpler to check
whether the subreg id >= 0.

> +  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 &static_cast<df_live_subreg_bb_info *> (
> +      df_live_subreg->block_info)[index];
> +  else
> +    return nullptr;
> +}
> +
> +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);
> +}

How about replacing this and get_nblocks with the following two new routines:

/* Return the number of hard registers that are normally used to store
   a value of mode MODE.  */

unsigned int
regmode_natural_nregs (machine_mode mode)
{
  poly_uint64 total_size = GET_MODE_SIZE (mode);
  poly_uint64 natural_size = REGMODE_NATURAL_SIZE (mode);
  unsigned int nregs;
  /* REGMODE_NATURAL_SIZE must be defined such that total_size and
     natural_size are ordered.  */
  if (!can_div_away_from_zero_p (total_size, natural_size, &nregs))
    gcc_unreachable ();
  return nregs;
}

/* If register REGNO is a pseudo register, return the number of hard registers
   that are normally used to store it.  Return 1 otherwise.  */

unsigned int
regno_natural_nregs (unsigned int regno)
{
  if (regno < FIRST_PSEUDO_REGISTER)
    return 1;
  return regmode_natural_nregs (PSEUDO_REGNO_MODE (regno));
}

I think this ought to go in rtlanal.cc, perhaps after read_modify_subreg_p.

Then multireg_p (regno) can be replaced by regno_natural_nregs (regno) > 1.

> +
> +/* Return true if the REGNO need be track with subreg liveness.  */
> +
> +static bool
> +need_track_subreg_p (unsigned regno)
> +{
> +  auto problem_data
> +    = (struct df_live_subreg_problem_data *) df_live_subreg->problem_data;
> +  return bitmap_bit_p (&problem_data->tracked_regs, regno);
> +}
> +
> +/* 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);

I might be wrong, but I think this can be written:

  /* Verified by validate_subreg.  */
  if (!can_div_trunc_p (offset, unit_size, &subreg_start)
      || !can_div_away_from_zero_p (offset + subreg_size, unit_size,
				    &subreg_end))
    gcc_unreachable ();
  
  bitmap_set_range (range, subreg_start, subreg_end - subreg_start);

Thanks,
Richard