towards reduction part 3/n: what does vec lower pass do to vector shifts?

towards reduction part 3/n: what does vec lower pass do to vector shifts?

[Dorit Naishlos]

I'm preparing the third part of the reduction support for mainline,
introducing vector shifts (see
http://gcc.gnu.org/ml/gcc-patches/2005-06/msg01317.html). The vectorizer
generates the following epilog code:

  vect_var_.53_60 = vect_var_.50_59 v>> 64;
  vect_var_.53_61 = vect_var_.50_59 + vect_var_.53_60;
  vect_var_.53_62 = vect_var_.53_61 v>> 32;
  vect_var_.53_63 = vect_var_.53_61 + vect_var_.53_62;
  vect_var_.52_64 = BIT_FIELD_REF <vect_var_.53_63, 32, 96>;

and the next pass, vec_lower2 transforms that into the following:

  D.2057_108 = BIT_FIELD_REF <vect_var_.50_59, 32, 0>;
  D.2058_109 = BIT_FIELD_REF <64, 32, 0>;
  D.2059_110 = D.2057_108 v>> D.2058_109;
  D.2060_111 = BIT_FIELD_REF <vect_var_.50_59, 32, 32>;
  D.2061_112 = BIT_FIELD_REF <64, 32, 32>;
  D.2062_113 = D.2060_111 v>> D.2061_112;
  D.2063_114 = BIT_FIELD_REF <vect_var_.50_59, 32, 64>;
  D.2064_115 = BIT_FIELD_REF <64, 32, 64>;
  D.2065_116 = D.2063_114 v>> D.2064_115;
  D.2066_117 = BIT_FIELD_REF <vect_var_.50_59, 32, 96>;
  D.2067_118 = BIT_FIELD_REF <64, 32, 96>;
  D.2068_119 = D.2066_117 v>> D.2067_118;
  vect_var_.53_60 = {D.2059_110, D.2062_113, D.2065_116, D.2068_119};
  vect_var_.53_61 = vect_var_.50_59 + vect_var_.53_60;
  D.2069_120 = BIT_FIELD_REF <vect_var_.53_61, 32, 0>;
  D.2070_121 = BIT_FIELD_REF <32, 32, 0>;
  D.2071_122 = D.2069_120 v>> D.2070_121;
  D.2072_123 = BIT_FIELD_REF <vect_var_.53_61, 32, 32>;
  D.2073_124 = BIT_FIELD_REF <32, 32, 32>;
  D.2074_125 = D.2072_123 v>> D.2073_124;
  D.2075_126 = BIT_FIELD_REF <vect_var_.53_61, 32, 64>;
  D.2076_127 = BIT_FIELD_REF <32, 32, 64>;
  D.2077_128 = D.2075_126 v>> D.2076_127;
  D.2078_129 = BIT_FIELD_REF <vect_var_.53_61, 32, 96>;
  D.2079_130 = BIT_FIELD_REF <32, 32, 96>;
  D.2080_131 = D.2078_129 v>> D.2079_130;
  vect_var_.53_62 = {D.2071_122, D.2074_125, D.2077_128, D.2080_131};
  vect_var_.53_63 = vect_var_.53_61 + vect_var_.53_62;
  vect_var_.52_64 = BIT_FIELD_REF <vect_var_.53_63, 32, 96>;


why??

thanks,
dorit

Re: towards reduction part 3/n: what does vec lower pass do to vector shifts?

[Dorit Naishlos]

> why??
>

The problem is that in 'expand_vector_operations_1()' in
tree-vect-generic.c we call 'optab_for_tree_code()' to get an optab for
VEC_RSHIFT_EXPR; 'optab_for_tree_code' does not have a case for
VEC_RSHIFT_EXPR, so the vector-lowering function concludes that this
tree-code is not supported, and expands it into the code I showed before.

To my understanding 'optab_for_tree_code' never promised anyone to provide
full information for all tree-codes. It even says so explicitely: "This
function is not always usable (for example, it cannot give complete results
for multiplication or division)". So, either (1)
'expand_vector_operations_1' needs to find a different way to query if a
tree code is supported, or, (2) if there is an expectation that
'optab_for_tree_code' handles all tree-codes, then we need to add the
missing info, and to start with passing it the tree expression itself, not
just the tree code, because at least for the vector-shift case I need to
check that the shift operand is constant, and only then return
optab_shri/shli. For now, to work around this problem until we decide on
the proper approach I did the following: (3)

Index: optabs.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/optabs.c,v
retrieving revision 1.281
diff -u -3 -p -r1.281 optabs.c
--- optabs.c    18 Jun 2005 13:18:37 -0000      1.281
+++ optabs.c    19 Jun 2005 16:26:29 -0000
@@ -301,7 +301,15 @@ optab_for_tree_code (enum tree_code code
       return TYPE_UNSIGNED (type) ? reduc_umin_optab : reduc_smin_optab;

     case REDUC_PLUS_EXPR:
-      return reduc_plus_optab;
+      return TYPE_UNSIGNED (type) ? reduc_uplus_optab : reduc_splus_optab;
+
+    case VEC_LSHIFT_EXPR:
+      /* FIXME: this optab is appropriate only if second argument is
constant.  */
+      return vec_shli_optab;
+
+    case VEC_RSHIFT_EXPR:
+      /* FIXME: this optab is appropriate only if second argument is
constant.  */
+      return vec_shri_optab;

     default:
       break;

This is safe for now, because at the only place where we generate these
vector shifts we do that using constants shift amounts. Would this be ok
for now, until 'expand_vector_operations_1' or 'optab_for_tree_code' are
fixed?

thanks,

dorit

> I'm preparing the third part of the reduction support for mainline,
> introducing vector shifts (see
> http://gcc.gnu.org/ml/gcc-patches/2005-06/msg01317.html). The vectorizer
> generates the following epilog code:
>
>   vect_var_.53_60 = vect_var_.50_59 v>> 64;
>   vect_var_.53_61 = vect_var_.50_59 + vect_var_.53_60;
>   vect_var_.53_62 = vect_var_.53_61 v>> 32;
>   vect_var_.53_63 = vect_var_.53_61 + vect_var_.53_62;
>   vect_var_.52_64 = BIT_FIELD_REF <vect_var_.53_63, 32, 96>;
>
> and the next pass, vec_lower2 transforms that into the following:
>
>   D.2057_108 = BIT_FIELD_REF <vect_var_.50_59, 32, 0>;
>   D.2058_109 = BIT_FIELD_REF <64, 32, 0>;
>   D.2059_110 = D.2057_108 v>> D.2058_109;
>   D.2060_111 = BIT_FIELD_REF <vect_var_.50_59, 32, 32>;
>   D.2061_112 = BIT_FIELD_REF <64, 32, 32>;
>   D.2062_113 = D.2060_111 v>> D.2061_112;
>   D.2063_114 = BIT_FIELD_REF <vect_var_.50_59, 32, 64>;
>   D.2064_115 = BIT_FIELD_REF <64, 32, 64>;
>   D.2065_116 = D.2063_114 v>> D.2064_115;
>   D.2066_117 = BIT_FIELD_REF <vect_var_.50_59, 32, 96>;
>   D.2067_118 = BIT_FIELD_REF <64, 32, 96>;
>   D.2068_119 = D.2066_117 v>> D.2067_118;
>   vect_var_.53_60 = {D.2059_110, D.2062_113, D.2065_116, D.2068_119};
>   vect_var_.53_61 = vect_var_.50_59 + vect_var_.53_60;
>   D.2069_120 = BIT_FIELD_REF <vect_var_.53_61, 32, 0>;
>   D.2070_121 = BIT_FIELD_REF <32, 32, 0>;
>   D.2071_122 = D.2069_120 v>> D.2070_121;
>   D.2072_123 = BIT_FIELD_REF <vect_var_.53_61, 32, 32>;
>   D.2073_124 = BIT_FIELD_REF <32, 32, 32>;
>   D.2074_125 = D.2072_123 v>> D.2073_124;
>   D.2075_126 = BIT_FIELD_REF <vect_var_.53_61, 32, 64>;
>   D.2076_127 = BIT_FIELD_REF <32, 32, 64>;
>   D.2077_128 = D.2075_126 v>> D.2076_127;
>   D.2078_129 = BIT_FIELD_REF <vect_var_.53_61, 32, 96>;
>   D.2079_130 = BIT_FIELD_REF <32, 32, 96>;
>   D.2080_131 = D.2078_129 v>> D.2079_130;
>   vect_var_.53_62 = {D.2071_122, D.2074_125, D.2077_128, D.2080_131};
>   vect_var_.53_63 = vect_var_.53_61 + vect_var_.53_62;
>   vect_var_.52_64 = BIT_FIELD_REF <vect_var_.53_63, 32, 96>;
>
>
> why??
>
> thanks,
> dorit
>

Re: towards reduction part 3/n: what does vec lower pass do to vector shifts?

[Richard Henderson]

On Sun, Jun 19, 2005 at 07:36:15PM +0300, Dorit Naishlos wrote:
> ... because at least for the vector-shift case I need to
> check that the shift operand is constant, and only then return
> optab_shri/shli.

This isn't true.  Just because the altivec patterns don't accept
anything other than a constant doesn't mean that the pattern can't
be valid for other operands.  The operation is completely specified
by its code.

Adding the operations to optab_for_tree_code is the right approach.

Ideally we'd also update tree-vect-generic to handle this new operation;
its behaviour with this code at present is actively wrong.  For the
moment we should add an assert

---
        compute_type = TREE_TYPE (type);
    }

+ gcc_assert (code != VEC_LSHIFT_EXPR && code != VEC_RSHIFT_EXPR);
  rhs = expand_vector_operation (bsi, type, compute_type, rhs, code);
  if (lang_hooks.types_compatible_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
---

which should verify that we only generate this operation when we have
the expectation that the backend will handle it.


r~

Re: towards reduction part 3/n: what does vec lower pass do to vector shifts?

[Dorit Naishlos]

Richard Henderson <rth@redhat.com> wrote on 19/06/2005 19:49:46:
> On Sun, Jun 19, 2005 at 07:36:15PM +0300, Dorit Naishlos wrote:
> > ... because at least for the vector-shift case I need to
> > check that the shift operand is constant, and only then return
> > optab_shri/shli.
>
> This isn't true.  Just because the altivec patterns don't accept
> anything other than a constant doesn't mean that the pattern can't
> be valid for other operands.  The operation is completely specified
> by its code.

Altivec does support non immediate shift amount (even if less efficiently -
I have to put the shift amount in a vector register first). But since we
have defined these optabs to represent shift operations that take immediate
shift amount, I shouldn't be returning vec_shli/vec_shri if the shift is
not constant. I could return a "vec_shl_optab"/"vec_shr_optab" that
supported a general shift amount if we wanted to introduce these optabs (in
addition, or instead of "vec_shli_optab/vec_shri_optab"). (For the
vectorizer, immediate shifts would suffice).

>
> Adding the operations to optab_for_tree_code is the right approach.
>
> Ideally we'd also update tree-vect-generic to handle this new operation;
> its behaviour with this code at present is actively wrong.  For the
> moment we should add an assert
>
> ---
>         compute_type = TREE_TYPE (type);
>     }
>
> + gcc_assert (code != VEC_LSHIFT_EXPR && code != VEC_RSHIFT_EXPR);
>   rhs = expand_vector_operation (bsi, type, compute_type, rhs, code);
>   if (lang_hooks.types_compatible_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
> ---
>
> which should verify that we only generate this operation when we have
> the expectation that the backend will handle it.
>

ok,

thanks,

dorit

>
> r~

Re: towards reduction part 3/n: what does vec lower pass do to vector shifts?

[Richard Henderson]

On Sun, Jun 19, 2005 at 08:00:22PM +0300, Dorit Naishlos wrote:
> Altivec does support non immediate shift amount (even if less efficiently -
> I have to put the shift amount in a vector register first). But since we
> have defined these optabs to represent shift operations that take immediate
> shift amount, I shouldn't be returning vec_shli/vec_shri if the shift is
> not constant.

I think this is a bit silly; unless we have a good reason I don't think
we should define different optabs for constant/non-constant shift counts.


r~

Re: towards reduction part 3/n: what does vec lower pass do to vector shifts?

[Dorit Naishlos]

Richard Henderson <rth@redhat.com> wrote on 19/06/2005 20:33:02:
> On Sun, Jun 19, 2005 at 08:00:22PM +0300, Dorit Naishlos wrote:
> > Altivec does support non immediate shift amount (even if less
efficiently -
> > I have to put the shift amount in a vector register first). But since
we
> > have defined these optabs to represent shift operations that take
immediate
> > shift amount, I shouldn't be returning vec_shli/vec_shri if the shift
is
> > not constant.
>
> I think this is a bit silly; unless we have a good reason I don't think
> we should define different optabs for constant/non-constant shift counts.
>

The thought was to supply an API that would let the vectorizer ask for the
minimal capability it needs - if all we need is a vector shift of a
constant value in bytes, lets ask exactly for that, so that targets that
don't support non-constant shifts, or that support only byte shifts, could
also enjoy this feature.
A general vector shift that can take both constant and non-constant counts
is indeed more general, and maybe what we prefer to have at the tree level.
In this case, targets that can't tell the vectorizer that they can support
general vector shifts, but could have told the vectorizer that they support
an immediate vector shift, will just have to implement the REDUC_OP
directly (using immediate vector shifts) in their machine description.

dorit

>
> r~

Re: towards reduction part 3/n: what does vec lower pass do to vector shifts?

[Richard Henderson]

On Sun, Jun 19, 2005 at 11:46:52PM +0300, Dorit Naishlos wrote:
> The thought was to supply an API that would let the vectorizer ask for the
> minimal capability it needs - if all we need is a vector shift of a
> constant value in bytes, lets ask exactly for that, so that targets that
> don't support non-constant shifts, or that support only byte shifts, could
> also enjoy this feature.

Hmm.  In theory we could get this information out of the predicates
on the expander, but it wouldn't be very clean.

> A general vector shift that can take both constant and non-constant counts
> is indeed more general, and maybe what we prefer to have at the tree level.
> In this case, targets that can't tell the vectorizer that they can support
> general vector shifts, but could have told the vectorizer that they support
> an immediate vector shift, will just have to implement the REDUC_OP
> directly (using immediate vector shifts) in their machine description.

At present I believe that most targets implement general shifts.  Lets
just go with that for now.  As you say -- there's always a fallback
option available.


r~

Re: towards reduction part 3/n: what does vec lower pass do to vector shifts?

[Dorit Naishlos]

Richard Henderson <rth@redhat.com> wrote on 20/06/2005 01:13:11:
> On Sun, Jun 19, 2005 at 11:46:52PM +0300, Dorit Naishlos wrote:
> > The thought was to supply an API that would let the vectorizer ask for
the
> > minimal capability it needs - if all we need is a vector shift of a
> > constant value in bytes, lets ask exactly for that, so that targets
that
> > don't support non-constant shifts, or that support only byte shifts,
could
> > also enjoy this feature.
>
> Hmm.  In theory we could get this information out of the predicates
> on the expander, but it wouldn't be very clean.
>
> > A general vector shift that can take both constant and non-constant
counts
> > is indeed more general, and maybe what we prefer to have at the tree
level.
> > In this case, targets that can't tell the vectorizer that they can
support
> > general vector shifts, but could have told the vectorizer that they
support
> > an immediate vector shift, will just have to implement the REDUC_OP
> > directly (using immediate vector shifts) in their machine description.
>
> At present I believe that most targets implement general shifts.

I once worked on a DSP chip that didn't, but...

>  Lets
> just go with that for now.  As you say -- there's always a fallback
> option available.
>

...sure, I switched to general vec_shr/shl optabs

thanks,
dorit
>
> r~