Re: [PATCH v4 3/4] ree: Main functionality to improve ree pass for rs6000 target.

[Surya Kumari Jangala <jskumari@linux.vnet.ibm.com>]

On 21/04/23 8:51 pm, Ajit Agarwal via Gcc-patches wrote:

> +/* Return TRUE if the cfg has following properties.
> +	bb1
> +	|\
> +	| \
> +	|  bb2
> +	|  /
> +	bb3
> +
> +   whereas bb1 has IF_THEN_ELSE  and bb2 has the definition and bb3 has
> +   zero/sign/AND extensions.  */
> +

Any specific reason for requiring CFGs to have only this particular shape? The patch should be generic enough to work for all CFGs.

Regards,
Surya

> +static bool
> +feasible_cfg (ext_cand *cand, rtx_insn *def_insn)
> +{
> +  basic_block bb = BLOCK_FOR_INSN (cand->insn);
> +  edge fallthru_edge;
> +  edge e;
> +  edge_iterator ei;
> +
> +  FOR_EACH_EDGE (e, ei, bb->preds)
> +    {
> +      rtx_insn *insn = BB_END (e->src) ? PREV_INSN (BB_END (e->src)) : NULL;
> +
> +      if (insn == NULL)
> +	continue;
> +
> +      if (DEBUG_INSN_P (insn))
> +	continue;
> +
> +      rtx set = single_set (insn);
> +
> +      /* Block has IF_THEN_ELSE  */
> +      if (insn && set
> +	  && GET_CODE (set) == SET && SET_SRC (set)
> +	  && GET_CODE (SET_SRC (set)) == IF_THEN_ELSE)
> +	{
> +	  if (e->dest == bb)
> +	    {
> +	      basic_block jump_block = e->dest;
> +	      if (jump_block != bb)
> +		return false;
> +	     }
> +	     else
> +	       {
> +		 /* def_insn block has single successor and fall through
> +		    edge target are the block for cand insn.  */
> +		 if (single_succ_p (e->dest))
> +		   {
> +		     fallthru_edge = single_succ_edge (e->dest);
> +		     if (BB_END (fallthru_edge->dest)
> +			 && bb != fallthru_edge->dest)
> +		       return false;
> +		   }
> +		}
> +	  }
> +    }
> +
> +  /* def_insn block has single successor and fall through
> +     edge target are the block for cand insn.  */
> +  if (single_succ_p (BLOCK_FOR_INSN (def_insn)))
> +    {
> +      fallthru_edge = single_succ_edge (BLOCK_FOR_INSN (def_insn));
> +      if (BB_END (fallthru_edge->dest)
> +	  && bb != fallthru_edge->dest)
> +	return false;
> +    }
> +   else
> +     return false;
> +
> +  return true;
> +}
> +
> +/* Return TRUE if the candidate extension INSN and def_insn are
> +   feasible for extension elimination.
> +
> +   Things to consider:
> +
> +   cfg properties are feasible for extension elimination.
> +
> +   sign_extend with def insn as PLUS and the reaching definition
> +   of def_insn are not ASHIFT and LSHIFTRT.
> +
> +   zero_extend with def insn as XOR/IOR and the reachin definition
> +   of def_insn are not ASHIFT and LSHIFTRT.
> +
> +   The destination register of the extension insn must not be
> +   used or set between the def_insn and cand->insn exclusive.
> +
> +   AND with zero extension properties has USE and the register
> +   of cand insn are same as register of USE operand.  */
> +
> +static bool
> +eliminate_across_bbs_p (ext_cand *cand, rtx_insn *def_insn)
> +{
> +  basic_block bb = BLOCK_FOR_INSN (cand->insn);
> +
> +  if (!feasible_cfg (cand, def_insn))
> +    return false;
> +
> +  rtx cand_set = single_set(cand->insn);
> +  /* The destination register of the extension insn must not be
> +      used or set between the def_insn and cand->insn exclusive.  */
> +  if (INSN_CHAIN_CODE_P (GET_CODE (def_insn))
> +      && INSN_CHAIN_CODE_P (cand->code))
> +    if ((cand->code == ZERO_EXTEND)
> +	 && REG_P (SET_DEST (cand_set)) && NEXT_INSN (def_insn)
> +	 && reg_used_set_between_p(SET_DEST (cand_set), def_insn, cand->insn))
> +      return false;
> +
> +  if (cand->code == ZERO_EXTEND
> +      && (bb != BLOCK_FOR_INSN (def_insn)
> +      || DF_INSN_LUID (def_insn) > DF_INSN_LUID (cand->insn)))
> +    return false;
> +
> +  if (rtx_is_zext_p (cand->insn))
> +    {
> +      if (GET_CODE (PATTERN (BB_END (bb))) != USE)
> +	return false;
> +
> +      if (REGNO (XEXP (PATTERN (BB_END (bb)), 0)) != REGNO (SET_DEST (cand->expr)))
> +	return false;
> +    }
> +
> +  rtx set = single_set (def_insn);
> +
> +  if (!set)
> +    return false;
> +
> +  if (cand->code == SIGN_EXTEND
> +      && GET_CODE (set) == SET)
> +    {
> +      rtx orig_src = SET_SRC (set);
> +      machine_mode ext_src_mode;
> +
> +      ext_src_mode = GET_MODE (XEXP (SET_SRC (cand->expr), 0));
> +
> +      if (GET_MODE (SET_DEST (set)) != ext_src_mode)
> +	return false;
> +
> +      if (GET_CODE (orig_src) != PLUS)
> +	return false;
> +
> +      if (!REG_P (XEXP (orig_src, 0)))
> +	return false;
> +
> +      if (!REG_P (XEXP (orig_src,1)))
> +	return false;
> +
> +      if (GET_CODE (orig_src) == PLUS)
> +	{
> +	  bool def_src1
> +	    = def_arith_p (def_insn,
> +			   XEXP (SET_SRC (set), 0));
> +	  bool def_src2
> +	    = def_arith_p (def_insn,
> +			   XEXP (SET_SRC (set), 1));
> +
> +	  if (def_src1 || def_src2)
> +	    return false;
> +	}
> +    }
> +
> +  if (cand->code == ZERO_EXTEND
> +      && GET_CODE (set) == SET)
> +    {
> +      if (GET_CODE (SET_SRC (set)) != XOR
> +	  && GET_CODE (SET_SRC (set)) != IOR)
> +	return false;
> +
> +      if (GET_CODE (SET_SRC (set)) == XOR
> +	  || GET_CODE (SET_SRC (set)) == IOR)
> +	 {
> +	   bool def_src1
> +	     = def_arith_p (def_insn,
> +			    XEXP (SET_SRC (set), 0));
> +	   bool def_src2
> +	     = def_arith_p (def_insn,
> +			    XEXP (SET_SRC (set), 1));
> +
> +	   if (def_src1 || def_src2)
> +	     return false;
> +	 }
> +     }
> +
> +  return true;
> +}
> +
>  /* Merge the DEF_INSN with an extension.  Calls combine_set_extension
>     on the SET pattern.  */
>  
> @@ -713,12 +1035,32 @@ merge_def_and_ext (ext_cand *cand, rtx_insn *def_insn, ext_state *state)
>    if (sub_rtx == NULL)
>      return false;
>  
> -  if (GET_MODE (SET_DEST (*sub_rtx)) == ext_src_mode
> -	  || ((state->modified[INSN_UID (def_insn)].kind
> -	       == (cand->code == ZERO_EXTEND
> +  bool copy_needed
> +    = (REGNO (SET_DEST (cand->expr)) != REGNO (XEXP (SET_SRC (cand->expr), 0)));
> +
> +  bool feasible = eliminate_across_bbs_p (cand, def_insn);
> +
> +  if (!feasible) return false;
> +
> +  /* Combine zero_extend/sign_extend/AND and if sign_extend and
> +     mode of DEST and SRC are different.  */
> +
> +  bool is_zext =  rtx_is_zext_p (cand->insn)
> +		  || cand->code == ZERO_EXTEND
> +		  || cand->code == SIGN_EXTEND;
> +
> +  bool do_elimination = !copy_needed
> +			&& is_zext
> +			&& (cand->code == SIGN_EXTEND
> +			    || GET_MODE (SET_DEST (*sub_rtx)) != ext_src_mode);
> +
> +  if (((do_elimination
> +	&& state->modified[INSN_UID (def_insn)].kind == EXT_MODIFIED_NONE))
> +	|| ((state->modified[INSN_UID (def_insn)].kind
> +		== (cand->code == ZERO_EXTEND
>  		   ? EXT_MODIFIED_ZEXT : EXT_MODIFIED_SEXT))
> -	      && state->modified[INSN_UID (def_insn)].mode
> -		 == ext_src_mode))
> +	     && state->modified[INSN_UID (def_insn)].mode
> +		== ext_src_mode))
>      {
>        if (GET_MODE_UNIT_SIZE (GET_MODE (SET_DEST (*sub_rtx)))
>  	  >= GET_MODE_UNIT_SIZE (cand->mode))
> @@ -734,7 +1076,6 @@ merge_def_and_ext (ext_cand *cand, rtx_insn *def_insn, ext_state *state)
>  	  return true;
>  	}
>      }
> -
>    return false;
>  }
>  
> @@ -744,7 +1085,9 @@ merge_def_and_ext (ext_cand *cand, rtx_insn *def_insn, ext_state *state)
>  static inline rtx
>  get_extended_src_reg (rtx src)
>  {
> -  while (GET_CODE (src) == SIGN_EXTEND || GET_CODE (src) == ZERO_EXTEND)
> +  while (GET_CODE (src) == SIGN_EXTEND
> +	 || GET_CODE (src) == ZERO_EXTEND
> +	 || rtx_is_zext_p (src))
>      src = XEXP (src, 0);
>    gcc_assert (REG_P (src));
>    return src;
> @@ -882,8 +1225,7 @@ combine_reaching_defs (ext_cand *cand, const_rtx set_pat, ext_state *state)
>  
>        /* The destination register of the extension insn must not be
>  	 used or set between the def_insn and cand->insn exclusive.  */
> -      if (reg_used_between_p (SET_DEST (set), def_insn, cand->insn)
> -	  || reg_set_between_p (SET_DEST (set), def_insn, cand->insn))
> +      if (reg_used_set_between_p (SET_DEST (set), def_insn, cand->insn))
>  	return false;
>  
>        /* We must be able to copy between the two registers.   Generate,
> @@ -975,10 +1317,8 @@ combine_reaching_defs (ext_cand *cand, const_rtx set_pat, ext_state *state)
>  	     used or set between the def_insn2 and def_insn exclusive.
>  	     Likewise for the other reg, i.e. check both reg1 and reg2
>  	     in the above comment.  */
> -	  if (reg_used_between_p (SET_DEST (set), def_insn2, def_insn)
> -	      || reg_set_between_p (SET_DEST (set), def_insn2, def_insn)
> -	      || reg_used_between_p (src_reg, def_insn2, def_insn)
> -	      || reg_set_between_p (src_reg, def_insn2, def_insn))
> +	  if (reg_used_set_between_p (SET_DEST (set), def_insn2, def_insn)
> +	      || reg_used_set_between_p (src_reg, def_insn2, def_insn))
>  	    break;
>  
>  	  state->defs_list[0] = def_insn2;
> @@ -1004,15 +1344,17 @@ combine_reaching_defs (ext_cand *cand, const_rtx set_pat, ext_state *state)
>        cand->mode = mode;
>      }
>  
> -  merge_successful = true;
> -
> +  merge_successful = false;
>    /* Go through the defs vector and try to merge all the definitions
>       in this vector.  */
>    state->modified_list.truncate (0);
>    FOR_EACH_VEC_ELT (state->defs_list, defs_ix, def_insn)
>      {
>        if (merge_def_and_ext (cand, def_insn, state))
> -	state->modified_list.safe_push (def_insn);
> +	{
> +	  merge_successful = true;
> +	  state->modified_list.safe_push (def_insn);
> +	}
>        else
>          {
>            merge_successful = false;
> @@ -1045,34 +1387,71 @@ combine_reaching_defs (ext_cand *cand, const_rtx set_pat, ext_state *state)
>  	 definitions could be merged.  */
>        if (apply_change_group ())
>          {
> -          if (dump_file)
> -            fprintf (dump_file, "All merges were successful.\n");
> +	  if (state->modified_list.length() == 0)
> +	     return false;
> +
> +	  rtx_insn *insn = state->modified_list[0];
> +
> +	  if ((cand->code == ZERO_EXTEND || cand->code == SIGN_EXTEND)
> +	       && GET_CODE (PATTERN (insn)) == SET
> +	       && GET_CODE (SET_SRC (PATTERN (insn))) != XOR
> +	       && GET_CODE (SET_SRC (PATTERN (insn))) != PLUS
> +	       && GET_CODE (SET_SRC (PATTERN (insn))) != IOR)
> +	     return false;
> +
> +	   if (dump_file)
> +	     fprintf (dump_file, "All merges were successful.\n");
>  
>  	  FOR_EACH_VEC_ELT (state->modified_list, i, def_insn)
>  	    {
>  	      ext_modified *modified = &state->modified[INSN_UID (def_insn)];
>  	      if (modified->kind == EXT_MODIFIED_NONE)
>  		modified->kind = (cand->code == ZERO_EXTEND ? EXT_MODIFIED_ZEXT
> -						            : EXT_MODIFIED_SEXT);
> +							    : EXT_MODIFIED_SEXT);
>  
>  	      if (copy_needed)
>  		modified->do_not_reextend = 1;
>  	    }
>            return true;
>          }
> -      else
> -        {
> -          /* Changes need not be cancelled explicitly as apply_change_group
> -             does it.  Print list of definitions in the dump_file for debug
> -             purposes.  This extension cannot be deleted.  */
> -          if (dump_file)
> -            {
> -	      fprintf (dump_file,
> -		       "Merge cancelled, non-mergeable definitions:\n");
> -	      FOR_EACH_VEC_ELT (state->modified_list, i, def_insn)
> -	        print_rtl_single (dump_file, def_insn);
> -            }
> -        }
> +	else
> +	  {
> +	    if (state->modified_list.length() == 0)
> +	      return false;
> +
> +	     rtx_insn *insn = state->modified_list[0];
> +
> +	     if ((cand->code == ZERO_EXTEND || cand->code == SIGN_EXTEND)
> +		  && GET_CODE (PATTERN (insn)) == SET
> +		  && GET_CODE (SET_SRC (PATTERN (insn))) != XOR
> +		  && GET_CODE (SET_SRC (PATTERN (insn))) != PLUS
> +		  && GET_CODE (SET_SRC (PATTERN (insn))) != IOR)
> +		return false;
> +
> +	    if (cand->code == ZERO_EXTEND || cand->code == SIGN_EXTEND)
> +	      {
> +		FOR_EACH_VEC_ELT (state->modified_list, i, def_insn)
> +		  {
> +		    ext_modified *modified = &state->modified[INSN_UID (def_insn)];
> +		    if (modified->kind == EXT_MODIFIED_NONE)
> +		      modified->kind = (cand->code == ZERO_EXTEND ? EXT_MODIFIED_ZEXT
> +								  : EXT_MODIFIED_SEXT);
> +
> +		     modified->do_not_reextend = 1;
> +		   }
> +		  return true;
> +	      }
> +	    /* Changes need not be cancelled explicitly as apply_change_group
> +		does it.  Print list of definitions in the dump_file for debug
> +		purposes.  This extension cannot be deleted.  */
> +	    if (dump_file)
> +	      {
> +		fprintf (dump_file,
> +			"Merge cancelled, non-mergeable definitions:\n");
> +		FOR_EACH_VEC_ELT (state->modified_list, i, def_insn)
> +		  print_rtl_single (dump_file, def_insn);
> +	      }
> +	   }
>      }
>    else
>      {
> @@ -1106,7 +1485,7 @@ add_removable_extension (const_rtx expr, rtx_insn *insn,
>    mode = GET_MODE (dest);
>  
>    if (REG_P (dest)
> -      && (code == SIGN_EXTEND || code == ZERO_EXTEND)
> +      && (code == SIGN_EXTEND || code == ZERO_EXTEND || rtx_is_zext_p (src))
>        && REG_P (XEXP (src, 0)))
>      {
>        rtx reg = XEXP (src, 0);
> @@ -1125,7 +1504,7 @@ add_removable_extension (const_rtx expr, rtx_insn *insn,
>  	      fprintf (dump_file, "Cannot eliminate extension:\n");
>  	      print_rtl_single (dump_file, insn);
>  	      fprintf (dump_file, " because it can operate on uninitialized"
> -			          " data\n");
> +				  " data\n");
>  	    }
>  	  return;
>  	}
> @@ -1320,8 +1699,8 @@ find_and_remove_re (void)
>  	  if (REG_P (XEXP (SET_SRC (set), 0))
>  	      && (REGNO (SET_DEST (set)) != REGNO (XEXP (SET_SRC (set), 0))))
>  	    {
> -              reinsn_copy_list.safe_push (curr_cand->insn);
> -              reinsn_copy_list.safe_push (state.defs_list[0]);
> +	      reinsn_copy_list.safe_push (curr_cand->insn);
> +	      reinsn_copy_list.safe_push (state.defs_list[0]);
>  	    }
>  	  reinsn_del_list.safe_push (curr_cand->insn);
>  	  state.modified[INSN_UID (curr_cand->insn)].deleted = 1;
> diff --git a/gcc/rtl.h b/gcc/rtl.h
> index f634cab730b..30f69881487 100644
> --- a/gcc/rtl.h
> +++ b/gcc/rtl.h
> @@ -3629,6 +3629,7 @@ extern int count_occurrences (const_rtx, const_rtx, int);
>  extern int reg_referenced_p (const_rtx, const_rtx);
>  extern int reg_used_between_p (const_rtx, const rtx_insn *, const rtx_insn *);
>  extern int reg_set_between_p (const_rtx, const rtx_insn *, const rtx_insn *);
> +extern bool reg_used_set_between_p (rtx, rtx_insn *, rtx_insn *);
>  extern int commutative_operand_precedence (rtx);
>  extern bool swap_commutative_operands_p (rtx, rtx);
>  extern int modified_between_p (const_rtx, const rtx_insn *, const rtx_insn *);
> diff --git a/gcc/rtlanal.cc b/gcc/rtlanal.cc
> index c96a88cebf1..e8d343bc497 100644
> --- a/gcc/rtlanal.cc
> +++ b/gcc/rtlanal.cc
> @@ -1134,6 +1134,21 @@ no_labels_between_p (const rtx_insn *beg, const rtx_insn *end)
>    return 1;
>  }
>  
> +/* The register reg of the extension to_insn must not be
> +   used or set between the from_insn and to_insn exclusive.  */
> +
> +bool
> +reg_used_set_between_p (rtx reg,
> +			rtx_insn *from_insn,
> +			rtx_insn *to_insn)
> +{
> +  if (reg_used_between_p (reg, from_insn, to_insn)
> +      || reg_set_between_p (reg, from_insn, to_insn))
> +    return true;
> +
> +  return false;
> +}
> +
>  /* Nonzero if register REG is used in an insn between
>     FROM_INSN and TO_INSN (exclusive of those two).  */
>  
> diff --git a/gcc/testsuite/g++.target/powerpc/sext-elim.C b/gcc/testsuite/g++.target/powerpc/sext-elim.C
> new file mode 100644
> index 00000000000..431696cf11e
> --- /dev/null
> +++ b/gcc/testsuite/g++.target/powerpc/sext-elim.C
> @@ -0,0 +1,18 @@
> +/* { dg-do compile { target { powerpc*-*-* } } } */
> +/* { dg-require-effective-target lp64 } */
> +/* { dg-require-effective-target powerpc_p9vector_ok } */
> +/* { dg-options "-mcpu=power9 -O2 -free" } */
> +
> +unsigned long c2l(unsigned char* p)
> +{
> +  unsigned long res = *p + *(p+1);
> +  return res;
> +}
> +
> +long c2sl(signed char* p)
> +{
> +  long res = *p + *(p+1);
> +  return res;
> +}
> +
> +/* { dg-final { scan-assembler-not "extsw" } } */
> diff --git a/gcc/testsuite/g++.target/powerpc/zext-elim-1.C b/gcc/testsuite/g++.target/powerpc/zext-elim-1.C
> new file mode 100644
> index 00000000000..bc6cc0eb3ca
> --- /dev/null
> +++ b/gcc/testsuite/g++.target/powerpc/zext-elim-1.C
> @@ -0,0 +1,19 @@
> +/* { dg-do compile { target { powerpc*-*-* } } } */
> +/* { dg-require-effective-target lp64 } */
> +/* { dg-require-effective-target powerpc_p9vector_ok } */
> +/* { dg-options "-mcpu=power9 -O2 -free" } */
> +
> +extern unsigned char magic1[256];
> +
> +unsigned int hash(const unsigned char inp[4])
> +{
> +   const unsigned long long INIT = 0x1ULL;
> +   unsigned long long h1 = INIT;
> +   h1 = magic1[((unsigned long long)inp[0]) ^ h1];
> +   h1 = magic1[((unsigned long long)inp[1]) ^ h1];
> +   h1 = magic1[((unsigned long long)inp[2]) ^ h1];
> +   h1 = magic1[((unsigned long long)inp[3]) ^ h1];
> +   return h1;
> +}
> +
> +/* { dg-final { scan-assembler-not "rlwinm" } } */
> diff --git a/gcc/testsuite/g++.target/powerpc/zext-elim-2.C b/gcc/testsuite/g++.target/powerpc/zext-elim-2.C
> new file mode 100644
> index 00000000000..4e72925104f
> --- /dev/null
> +++ b/gcc/testsuite/g++.target/powerpc/zext-elim-2.C
> @@ -0,0 +1,11 @@
> +/* { dg-do compile { target { powerpc*-*-* } } } */
> +/* { dg-require-effective-target lp64 } */
> +/* { dg-require-effective-target powerpc_p9vector_ok } */
> +/* { dg-options "-mcpu=power9 -O2 -free" } */
> +
> +unsigned char g(unsigned char t[], unsigned char v)
> +{
> +  return (t[v & 0x7f] & 0x7f) | (v & 0x80);
> +}
> +
> +/* { dg-final { scan-assembler-times "rlwinm" 2 } } */
> diff --git a/gcc/testsuite/g++.target/powerpc/zext-elim.C b/gcc/testsuite/g++.target/powerpc/zext-elim.C
> new file mode 100644
> index 00000000000..56eabbe0c19
> --- /dev/null
> +++ b/gcc/testsuite/g++.target/powerpc/zext-elim.C
> @@ -0,0 +1,30 @@
> +/* { dg-do compile { target { powerpc*-*-* } } } */
> +/* { dg-require-effective-target lp64 } */
> +/* { dg-require-effective-target powerpc_p9vector_ok } */
> +/* { dg-options "-mcpu=power9 -O2 -free" } */
> +
> +#include <stddef.h>
> +
> +bool foo (int a, int b)
> +{
> +  if (a > 2)
> +    return false;
> +
> +  if (b < 10)
> +    return true;
> +
> +  return true;
> +}
> +
> +int bar (int a, int b)
> +{
> +  if (a > 2)
> +    return 0;
> +
> +  if (b < 10)
> +    return 1;
> +
> +  return 0;
> +}
> +
> +/* { dg-final { scan-assembler-not "rldicl" } } */