Re: [PATCH] tree-vect: Add SVE2 HISTCNT histogram vectorization
Richard Biener <[email protected]>
| Newsgroups | gmane.comp.gcc.patches |
|---|---|
| Message-ID | <[email protected]> |
On Thu, 13 Aug 2026, Richard Biener wrote:
> On Wed, 12 Aug 2026, Abhishek Kaushik wrote:
>
> > Recognize simple histogram update loops and vectorize them using a new
> > masked HISTCNT internal function.
> >
> > A histogram update has the form:
> >
> > old = histogram[index];
> > new = old CODE update;
> > histogram[index] = new;
> >
> > where CODE is currently PLUS_EXPR or MINUS_EXPR, the update value is
> > loop-invariant or constant, and the load and store refer to the same
> > gather/scatter data reference.
> >
> > For example:
> >
> > void
> > histogram_update (uint64_t *restrict histogram,
> > const uint32_t *restrict records,
> > uint64_t n, uint64_t x)
> > {
> > for (uint64_t i = 0; i < n; ++i)
> > histogram[records[i]] += x;
> > }
> >
> > Normally the indirect load and store introduce a loop-carried
> > dependence: two iterations can use the same value of records[i], so the
> > later iteration must observe the update performed by the earlier one.
> > This prevents the normal gather/update/scatter sequence from being
> > vectorized.
> >
> > SVE2 HISTCNT provides the information needed to handle this dependence.
> > When both HISTCNT inputs contain the histogram indices, each active lane
> > gets the number of equal indices seen up to and including that lane.
> > Thus, for:
> >
> > records = { 5, 1, 5, 5 }
> >
> > HISTCNT produces:
> >
> > counts = { 1, 1, 2, 3 }
> >
> > Instead of performing one scalar update per occurrence, the vectorized
> > form therefore computes:
> >
> > count = MASK_HISTCNT (mask, index, index);
> > increment = (histogram_type) count * update;
> > new = COND_CODE (mask, old, increment, old);
> >
> > For the example above, all accesses to histogram[5] may initially load
> > the same old value, but the corresponding lanes compute old + x,
> > old + 2*x and old + 3*x. The final value written for the duplicate
> > index is therefore the same value that would have been produced by the
> > ordered scalar updates.
>
> On x86 there's vpconflict{dq} which computes a set of masks to
> use to gather/scatter conflict free parts. While code generation
> is more difficult we should at least make sure the pattern can be
> implemented with that as well (it could support all kind of update
> operation).
>
> I'm not sure I like this being a pattern.
>
> You seem to fail to verify the gather load is only used by
> the histogram update and the single use in the scatter store
> is actually the RHS and not some index?
>
> Why is signed overflow a problem (we don't usually care for
> sanitized either)? Just perform the accumulation in an
> unsigned vector type?
>
> You do not check for target support of MASK_HISTCNT during
> pattern recog? Still you seem to arrange for specific
> index types? I realize the code will not be vectorized
> without MASK_HISTCNT, but given there might be a x86 vpconflict{dq}
> path we'd have to check something. Or (as said - I don't like
> the pattern too much, even though it fits perfectly for the
> very narrow scope), do it somehow differently and make a
> gather-update-scatter "pair" a more general first-class citizen?
So on x86 you'd be able to handle all sorts of update functions by
using
vpconflictd zmm1, zmm0 ; 1. Generate conflict masks per lane
vptestmd k1, zmm1, zmm1 ; 2. k1 = conflict mask
kxnorw k2, k2, k2 ; 3. Generate all 1s (0xFFFF / -1)
kaddw k2, k1, k2 ; 4. k2 = k1 - 1
kandnw k1, k1, k2 ; 5. k1 = ~k1 & (k1 - 1)
and then use k1 as updated loop mask, performing a partial vector
update and a partial IV update, like also proposed for the HSSR
support patchset. I suppose you can create a similar mask using
HISTCNT and comparing against { 1, 1, 1, 1, ... }
The += x update would be a special-case. So I'd see this more like
how we handle reductions, the gather-scatter pair forming the
boundaries and the update function being classified, one of it
be "histogram update" but with a generic variant that can handle
all operations code generated via regular vectorizable_*
Richard.
> Thanks,
> Richard.
>
> > Keep the histogram key distinct from the gather/scatter address offset.
> > In particular, address calculation can promote a narrower index before
> > using it as a gather/scatter offset. For example, a uint32_t record
> > index can be promoted to uint64_t when indexing a uint64_t histogram.
> > Running HISTCNT on that promoted value would reduce the number of lanes
> > and could split one vector iteration into multiple independent HISTCNT
> > operations. Duplicates crossing such a split would no longer be
> > counted together.
> >
> > Look through a possible promotion of the gather/scatter offset and use
> > the original value as the HISTCNT key. Thus a uint32_t index remains a
> > 32-bit HISTCNT operation even when the histogram access itself requires
> > a 64-bit offset. The resulting counts are converted separately to the
> > histogram element type before the update is formed. This keeps one
> > HISTCNT conflict domain over the original index lanes while allowing
> > the backend to widen the indices and counts independently as required
> > by the memory operation.
> >
> > Record the exact histogram load and store data references once the
> > pattern has been recognized and target support has been established.
> > Dependence analysis then treats only the dependence between that
> > specific load/store pair as handled by HISTCNT. Other gather/scatter
> > dependences continue through the existing conservative dependence
> > checks. No alias information or data reference is removed, and an
> > unrelated dependence cannot be discharged merely because the loop
> > contains a histogram pattern.
> >
> > This is safe because the dependence being ignored is precisely the
> > dependence whose scalar ordering is represented by the prefix counts
> > produced by HISTCNT. A lane with count N computes the value that the
> > Nth scalar occurrence of that index would have produced. Dependences
> > outside the recognized load/update/store sequence are unchanged and
> > still prevent vectorization when required.
> >
> > Introduce IFN_MASK_HISTCNT and a corresponding mask_histcnt optab.
> > The mask is operand zero, while the operation mode is selected from the
> > first data operand. This is necessary because the predicate mode is
> > not the data mode used to select the target optab.
> >
> > Add an AArch64 SVE2 mask_histcnt expander that maps the internal
> > function to the existing SVE2 HISTCNT instruction. The operation is
> > available for SVE integer data modes when SVE2 is enabled and the
> > function is not in streaming mode.
> >
> > Do not apply the normal mask-conversion pattern to MASK_HISTCNT. The
> > internal function carries a semantic mask directly and the vectorizer
> > can combine it with the loop predicate when producing the vector call.
> >
> > Finally, reject histogram transformations for integer types whose
> > overflow behavior is trapping or sanitized. Collapsing several scalar
> > updates into count * update followed by one conditional add or subtract
> > can otherwise change where an overflow trap or sanitizer check occurs.
> > Wrapping integer arithmetic is compatible with the transformation,
> > while trapping and sanitized arithmetic is left unvectorized.
> >
> > Bootstrapped and regression tested on aarch64-linux-gnu.
> >
> > PR tree-optimization/96461
> >
> > gcc/ChangeLog:
> >
> > * config/aarch64/aarch64-sve2.md (mask_histcnt<mode>4): New
> > define_expand.
> > * internal-fn.cc (mask_binary_direct): New direct type.
> > (expand_mask_binary_optab_fn): New macro.
> > (direct_mask_binary_optab_supported_p): Likewise.
> > (internal_fn_mask_index): Handle IFN_MASK_HISTCNT.
> > * internal-fn.def (MASK_HISTCNT): New internal function.
> > * optabs.def (mask_histcnt_optab): New optab.
> > * tree-vect-data-refs.cc (vect_histogram_handled_dependence_p): New
> > function.
> > (vect_analyze_data_ref_dependence): Use it.
> > * tree-vect-patterns.cc (vect_recog_mask_conversion_pattern): Skip
> > IFN_MASK_HISTCNT.
> > (vect_histogram_operation): New struct.
> > (supported_histogram_operation_p): New function.
> > (vect_recog_histogram_update_pattern): New function.
> > (vect_vect_recog_func_ptrs): Add histogram update recognizer.
> > * tree-vectorizer.h (vect_histogram_info): New struct.
> > (_loop_vec_info::histograms): New member.
> > (LOOP_VINFO_HISTOGRAMS): New macro.
> >
> > gcc/testsuite/ChangeLog:
> >
> > * gcc.target/aarch64/sve2/histcnt-update-1.c: New test.
> > ---
> > gcc/config/aarch64/aarch64-sve2.md | 10 +
> > gcc/internal-fn.cc | 6 +
> > gcc/internal-fn.def | 3 +
> > gcc/optabs.def | 3 +
> > .../aarch64/sve2/histcnt-update-1.c | 41 ++++
> > gcc/tree-vect-data-refs.cc | 24 ++
> > gcc/tree-vect-patterns.cc | 211 ++++++++++++++++++
> > gcc/tree-vectorizer.h | 9 +
> > 8 files changed, 307 insertions(+)
> > create mode 100644 gcc/testsuite/gcc.target/aarch64/sve2/histcnt-update-1.c
> >
> > diff --git a/gcc/config/aarch64/aarch64-sve2.md b/gcc/config/aarch64/aarch64-sve2.md
> > index fe6aa65823d..6e1e9a2739e 100644
> > --- a/gcc/config/aarch64/aarch64-sve2.md
> > +++ b/gcc/config/aarch64/aarch64-sve2.md
> > @@ -4611,6 +4611,16 @@
> > ;; - HISTSEG
> > ;; -------------------------------------------------------------------------
> >
> > +(define_expand "mask_histcnt<mode>4"
> > + [(set (match_operand:SVE_FULL_SDI 0 "register_operand")
> > + (unspec:SVE_FULL_SDI
> > + [(match_operand:<VPRED> 1 "register_operand")
> > + (match_operand:SVE_FULL_SDI 2 "register_operand")
> > + (match_operand:SVE_FULL_SDI 3 "register_operand")]
> > + UNSPEC_HISTCNT))]
> > + "TARGET_SVE2 && TARGET_NON_STREAMING"
> > +)
> > +
> > (define_insn "@aarch64_sve2_histcnt<mode>"
> > [(set (match_operand:SVE_FULL_SDI 0 "register_operand" "=w")
> > (unspec:SVE_FULL_SDI
> > diff --git a/gcc/internal-fn.cc b/gcc/internal-fn.cc
> > index 0138c6f7ef0..e3874df3a8f 100644
> > --- a/gcc/internal-fn.cc
> > +++ b/gcc/internal-fn.cc
> > @@ -179,6 +179,7 @@ init_internal_fns ()
> > #define unary_direct { 0, 0, true }
> > #define unary_convert_direct { -1, 0, true }
> > #define binary_direct { 0, 0, true }
> > +#define mask_binary_direct { 1, 1, true }
> > #define ternary_direct { 0, 0, true }
> > #define cond_unary_direct { 1, 1, true }
> > #define cond_binary_direct { 1, 1, true }
> > @@ -4273,6 +4274,9 @@ expand_reduc_sbool_optab_fn (internal_fn fn, gcall *stmt, direct_optab optab)
> > #define expand_binary_optab_fn(FN, STMT, OPTAB) \
> > expand_direct_optab_fn (FN, STMT, OPTAB, 2)
> >
> > +#define expand_mask_binary_optab_fn(FN, STMT, OPTAB) \
> > + expand_direct_optab_fn (FN, STMT, OPTAB, 3)
> > +
> > #define expand_ternary_optab_fn(FN, STMT, OPTAB) \
> > expand_direct_optab_fn (FN, STMT, OPTAB, 3)
> >
> > @@ -4397,6 +4401,7 @@ multi_vector_optab_supported_p (convert_optab optab, tree_pair types,
> > #define direct_unary_optab_supported_p direct_optab_supported_p
> > #define direct_unary_convert_optab_supported_p convert_optab_supported_p
> > #define direct_binary_optab_supported_p direct_optab_supported_p
> > +#define direct_mask_binary_optab_supported_p direct_optab_supported_p
> > #define direct_ternary_optab_supported_p direct_optab_supported_p
> > #define direct_cond_unary_optab_supported_p direct_optab_supported_p
> > #define direct_cond_binary_optab_supported_p direct_optab_supported_p
> > @@ -5305,6 +5310,7 @@ internal_fn_mask_index (internal_fn fn)
> > case IFN_MASK_LEN_SCATTER_STORE:
> > return 5;
> >
> > + case IFN_MASK_HISTCNT:
> > case IFN_VCOND_MASK:
> > case IFN_VCOND_MASK_LEN:
> > return 0;
> > diff --git a/gcc/internal-fn.def b/gcc/internal-fn.def
> > index af9f92950c7..9feef1af544 100644
> > --- a/gcc/internal-fn.def
> > +++ b/gcc/internal-fn.def
> > @@ -239,6 +239,9 @@ DEF_INTERNAL_OPTAB_FN (MASK_LEN_GATHER_LOAD, ECF_PURE,
> > DEF_INTERNAL_OPTAB_FN (MASK_LEN_STRIDED_LOAD, ECF_PURE,
> > mask_len_strided_load, strided_load)
> >
> > +DEF_INTERNAL_OPTAB_FN (MASK_HISTCNT, ECF_CONST | ECF_LEAF | ECF_NOTHROW,
> > + mask_histcnt, mask_binary)
> > +
> > DEF_INTERNAL_OPTAB_FN (LEN_LOAD, ECF_PURE, len_load, len_load)
> > DEF_INTERNAL_OPTAB_FN (MASK_LEN_LOAD, ECF_PURE, mask_len_load, mask_len_load)
> >
> > diff --git a/gcc/optabs.def b/gcc/optabs.def
> > index 7ccea18543f..4f44b2d6495 100644
> > --- a/gcc/optabs.def
> > +++ b/gcc/optabs.def
> > @@ -408,6 +408,9 @@ OPTAB_D (feraiseexcept_optab, "feraiseexcept$a")
> > OPTAB_D (fmax_optab, "fmax$a3")
> > OPTAB_D (fmin_optab, "fmin$a3")
> >
> > +/* Histogram count. */
> > +OPTAB_D (mask_histcnt_optab, "mask_histcnt$a4")
> > +
> > /* Vector reduction to a scalar. */
> > OPTAB_D (reduc_fmax_scal_optab, "reduc_fmax_scal_$a")
> > OPTAB_D (reduc_fmin_scal_optab, "reduc_fmin_scal_$a")
> > diff --git a/gcc/testsuite/gcc.target/aarch64/sve2/histcnt-update-1.c b/gcc/testsuite/gcc.target/aarch64/sve2/histcnt-update-1.c
> > new file mode 100644
> > index 00000000000..dae5bbea3aa
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.target/aarch64/sve2/histcnt-update-1.c
> > @@ -0,0 +1,41 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O3 -march=armv8-a+sve2 -fdump-tree-vect-details -fno-vect-cost-model" } */
> > +
> > +#include <stdint.h>
> > +
> > +#define HISTCNT_TEST(NAME, HIST_T, INDEX_T) \
> > +void \
> > +NAME (HIST_T *__restrict histogram, \
> > + const INDEX_T *__restrict records, \
> > + const uint64_t n, \
> > + const HIST_T x) \
> > +{ \
> > + for (uint64_t i = 0; i < n; ++i) \
> > + histogram[records[i]] += x; \
> > +}
> > +
> > +HISTCNT_TEST (u32_idx_u32, uint32_t, uint32_t)
> > +HISTCNT_TEST (u32_idx_s32, uint32_t, int32_t)
> > +HISTCNT_TEST (u32_idx_u64, uint32_t, uint64_t)
> > +HISTCNT_TEST (u32_idx_s64, uint32_t, int64_t)
> > +
> > +HISTCNT_TEST (s32_idx_u32, int32_t, uint32_t)
> > +HISTCNT_TEST (s32_idx_s32, int32_t, int32_t)
> > +HISTCNT_TEST (s32_idx_u64, int32_t, uint64_t)
> > +HISTCNT_TEST (s32_idx_s64, int32_t, int64_t)
> > +
> > +HISTCNT_TEST (u64_idx_u32, uint64_t, uint32_t)
> > +HISTCNT_TEST (u64_idx_s32, uint64_t, int32_t)
> > +HISTCNT_TEST (u64_idx_u64, uint64_t, uint64_t)
> > +HISTCNT_TEST (u64_idx_s64, uint64_t, int64_t)
> > +
> > +HISTCNT_TEST (s64_idx_u32, int64_t, uint32_t)
> > +HISTCNT_TEST (s64_idx_s32, int64_t, int32_t)
> > +HISTCNT_TEST (s64_idx_u64, int64_t, uint64_t)
> > +HISTCNT_TEST (s64_idx_s64, int64_t, int64_t)
> > +
> > +/* { dg-final { scan-tree-dump-times "histogram_update pattern recognized" 16 "vect" } } */
> > +/* { dg-final { scan-tree-dump-times "vectorized 1 loops in function" 16 "vect" } } */
> > +
> > +/* { dg-final { scan-assembler-times {\thistcnt\tz[0-9]+\.[sd], p[0-7]/z, z[0-9]+\.[sd], z[0-9]+\.[sd]\n} 16 } } */
> > +/* { dg-final { scan-assembler-times {\tmla\tz[0-9]+\.[sd], p[0-7]/m, z[0-9]+\.[sd], z[0-9]+\.[sd]\n} 20 } } */
> > diff --git a/gcc/tree-vect-data-refs.cc b/gcc/tree-vect-data-refs.cc
> > index 92aecc656e1..5677d84d02e 100644
> > --- a/gcc/tree-vect-data-refs.cc
> > +++ b/gcc/tree-vect-data-refs.cc
> > @@ -399,6 +399,22 @@ vect_analyze_possibly_independent_ddr (data_dependence_relation *ddr,
> > return true;
> > }
> >
> > +static bool
> > +vect_histogram_handled_dependence_p (loop_vec_info loop_vinfo,
> > + data_dependence_relation *ddr)
> > +{
> > + data_reference *dra = DDR_A (ddr);
> > + data_reference *drb = DDR_B (ddr);
> > +
> > + for (const auto &hist : LOOP_VINFO_HISTOGRAMS (loop_vinfo))
> > + {
> > + if ((dra == hist.load_dr && drb == hist.store_dr)
> > + || (drb == hist.load_dr && dra == hist.store_dr))
> > + return true;
> > + }
> > +
> > + return false;
> > +}
> >
> > /* Function vect_analyze_data_ref_dependence.
> >
> > @@ -479,6 +495,14 @@ vect_analyze_data_ref_dependence (struct data_dependence_relation *ddr,
> > if (apply_safelen ())
> > return opt_result::success ();
> >
> > + if (vect_histogram_handled_dependence_p (loop_vinfo, ddr))
> > + {
> > + if (dump_enabled_p ())
> > + dump_printf_loc (MSG_NOTE, vect_location,
> > + "histogram gather/scatter dependence handled "
> > + "by HISTCNT\n");
> > + return opt_result::success ();
> > + }
> > return opt_result::failure_at
> > (stmtinfo_a->stmt,
> > "possible alias involving gather/scatter between %T and %T\n",
> > diff --git a/gcc/tree-vect-patterns.cc b/gcc/tree-vect-patterns.cc
> > index b921ae94848..e7227dbad7c 100644
> > --- a/gcc/tree-vect-patterns.cc
> > +++ b/gcc/tree-vect-patterns.cc
> > @@ -6295,6 +6295,8 @@ vect_recog_mask_conversion_pattern (vec_info *vinfo,
> > gcall *pattern_stmt;
> >
> > internal_fn ifn = gimple_call_internal_fn (last_stmt);
> > + if (ifn == IFN_MASK_HISTCNT)
> > + return NULL;
> > int mask_argno = internal_fn_mask_index (ifn);
> > if (mask_argno < 0)
> > return NULL;
> > @@ -6608,6 +6610,214 @@ vect_recog_gather_scatter_pattern (vec_info *vinfo,
> > return pattern_stmt;
> > }
> >
> > +struct vect_histogram_operation
> > +{
> > + tree old_val;
> > + tree update_val;
> > + tree offset;
> > + tree hist_index;
> > + tree type_out;
> > + tree_code code;
> > + vect_histogram_info hist_info;
> > +};
> > +
> > +static bool
> > +supported_histogram_operation_p (loop_vec_info loop_vinfo,
> > + const gimple *stmt,
> > + vect_histogram_operation *operation)
> > +{
> > + if (!is_gimple_assign (stmt))
> > + return false;
> > +
> > + tree op0 = NULL_TREE;
> > + tree op1 = NULL_TREE;
> > +
> > + gather_scatter_info gather_info;
> > + tree gather_vectype = NULL_TREE;
> > + data_reference *load_dr = NULL;
> > + switch ((operation->code = gimple_assign_rhs_code (stmt)))
> > + {
> > + case PLUS_EXPR:
> > + case MINUS_EXPR:
> > + {
> > + op0 = gimple_assign_rhs1 (stmt);
> > + op1 = gimple_assign_rhs2 (stmt);
> > +
> > + if (TREE_CODE (op0) != SSA_NAME)
> > + return false;
> > +
> > + gimple *load_stmt = SSA_NAME_DEF_STMT (op0);
> > + stmt_vec_info load_stmt_info = loop_vinfo->lookup_stmt (load_stmt);
> > + if (!load_stmt_info)
> > + return false;
> > +
> > + load_dr = STMT_VINFO_DATA_REF (load_stmt_info);
> > + if (!load_dr || !STMT_VINFO_GATHER_SCATTER_P (load_stmt_info))
> > + return false;
> > +
> > + gather_vectype = STMT_VINFO_VECTYPE (load_stmt_info);
> > +
> > + if (!vect_check_gather_scatter (load_stmt_info, gather_vectype,
> > + loop_vinfo, &gather_info)
> > + || gather_info.ifn != IFN_GATHER_LOAD)
> > + return false;
> > +
> > + enum vect_def_type dt = vect_unknown_def_type;
> > + if (!vect_is_simple_use (op1, loop_vinfo, &dt)
> > + || (dt != vect_external_def
> > + && dt != vect_constant_def))
> > + return false;
> > +
> > + operation->old_val = op0;
> > + operation->update_val = op1;
> > + break;
> > + }
> > +
> > + default:
> > + return false;
> > + }
> > +
> > + tree lhs = gimple_assign_lhs (stmt);
> > + use_operand_p use_p;
> > + gimple *store_stmt;
> > +
> > + if (!single_imm_use (lhs, &use_p, &store_stmt))
> > + return false;
> > +
> > + stmt_vec_info store_stmt_info = loop_vinfo->lookup_stmt (store_stmt);
> > + if (!store_stmt_info)
> > + return false;
> > +
> > + data_reference *store_dr = STMT_VINFO_DATA_REF (store_stmt_info);
> > + if (!store_dr || !STMT_VINFO_GATHER_SCATTER_P (store_stmt_info))
> > + return false;
> > +
> > + tree scatter_vectype = STMT_VINFO_VECTYPE (store_stmt_info);
> > +
> > + gather_scatter_info scatter_info;
> > + if (!vect_check_gather_scatter (store_stmt_info, scatter_vectype,
> > + loop_vinfo, &scatter_info)
> > + || scatter_info.ifn != IFN_SCATTER_STORE)
> > + return false;
> > +
> > + if (!same_data_refs (load_dr, store_dr)
> > + || gather_vectype != scatter_vectype)
> > + return false;
> > +
> > + vect_unpromoted_value unprom;
> > + tree unpromoted
> > + = vect_look_through_possible_promotion (loop_vinfo,
> > + scatter_info.offset,
> > + &unprom);
> > +
> > + operation->offset = scatter_info.offset;
> > + operation->hist_index = unpromoted ? unpromoted : operation->offset;
> > + operation->type_out = gather_vectype;
> > + operation->hist_info.load_dr = load_dr;
> > + operation->hist_info.store_dr = store_dr;
> > + return true;
> > +}
> > +
> > +/* Function vect_recog_histogram_update_pattern
> > +
> > + Try to find the following pattern:
> > +
> > + old = count[hist_index];
> > + new = old CODE update;
> > + count[hist_index] = new;
> > +
> > + where CODE is an operation supported by a conditional internal function and
> > + the load and store use the same gather/scatter data reference. The pattern
> > + produces:
> > +
> > + n = .MASK_HISTCNT (true, hist_index, hist_index);
> > + incr = (TYPE) n * update;
> > + new = .COND_CODE (true, old, incr, old);
> > +
> > + Input:
> > +
> > + * STMT_INFO: The stmt that performs CODE on the loaded value.
> > +
> > + Output:
> > +
> > + * TYPE_OUT: The vector type of the output of this pattern.
> > +
> > + * Return value: A new stmt that will be used to replace the sequence. */
> > +
> > +static gimple *
> > +vect_recog_histogram_update_pattern (vec_info *vinfo,
> > + stmt_vec_info stmt_info,
> > + tree *type_out)
> > +{
> > + /* Only supported for loop vectorization. */
> > + loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo);
> > + if (!loop_vinfo)
> > + return NULL;
> > +
> > + gimple *stmt = stmt_info->stmt;
> > + vect_histogram_operation operation;
> > + if (!supported_histogram_operation_p (loop_vinfo, stmt, &operation))
> > + return NULL;
> > +
> > + tree value_vectype = operation.type_out;
> > + if (!value_vectype)
> > + return NULL;
> > +
> > + tree value_type = TREE_TYPE (operation.old_val);
> > +
> > + if (INTEGRAL_TYPE_P (value_type)
> > + && (TYPE_OVERFLOW_TRAPS (value_type)
> > + || TYPE_OVERFLOW_SANITIZED (value_type)))
> > + return NULL;
> > +
> > + tree index_type = TREE_TYPE (operation.hist_index);
> > + tree index_vectype = get_vectype_for_scalar_type (vinfo, index_type);
> > + if (!index_vectype
> > + || !direct_internal_fn_supported_p (IFN_MASK_HISTCNT,
> > + index_vectype,
> > + OPTIMIZE_FOR_SPEED))
> > + return NULL;
> > +
> > + internal_fn cond_fn = get_conditional_internal_fn (operation.code);
> > + if (cond_fn == IFN_LAST
> > + || !direct_internal_fn_supported_p (cond_fn, value_vectype,
> > + OPTIMIZE_FOR_SPEED))
> > + return NULL;
> > +
> > + *type_out = value_vectype;
> > + LOOP_VINFO_HISTOGRAMS (loop_vinfo).safe_push (operation.hist_info);
> > + vect_pattern_detected ("vect_recog_histogram_pattern", stmt);
> > +
> > + tree count = vect_recog_temp_ssa_var (index_type, NULL);
> > + gcall *count_stmt = gimple_build_call_internal (IFN_MASK_HISTCNT, 3,
> > + boolean_true_node,
> > + operation.hist_index,
> > + operation.hist_index);
> > + gimple_call_set_lhs (count_stmt, count);
> > + gimple_call_set_nothrow (count_stmt, true);
> > + append_pattern_def_seq (vinfo, stmt_info, count_stmt, index_vectype);
> > +
> > + tree arithmetic_count = vect_add_conversion_to_pattern (vinfo, value_type,
> > + count, stmt_info);
> > +
> > + tree increment = vect_recog_temp_ssa_var (value_type, NULL);
> > + gassign *mul_stmt = gimple_build_assign (increment, MULT_EXPR,
> > + arithmetic_count,
> > + operation.update_val);
> > + append_pattern_def_seq (vinfo, stmt_info, mul_stmt, value_vectype);
> > +
> > + tree new_val = vect_recog_temp_ssa_var (value_type, NULL);
> > + gcall *pattern_stmt
> > + = gimple_build_call_internal (cond_fn, 4, boolean_true_node,
> > + operation.old_val, increment,
> > + operation.old_val);
> > + gimple_call_set_lhs (pattern_stmt, new_val);
> > + gimple_call_set_nothrow (pattern_stmt, true);
> > + loop_vinfo->add_stmt (pattern_stmt);
> > +
> > + return pattern_stmt;
> > +}
> > +
> > /* Helper method of vect_recog_cond_store_pattern, checks to see if COND_ARG
> > is points to a load statement that reads the same data as that of
> > STORE_VINFO. */
> > @@ -7475,6 +7685,7 @@ static vect_recog_func vect_vect_recog_func_ptrs[] = {
> > { vect_recog_sat_trunc_pattern, "sat_trunc" },
> > { vect_recog_gcond_pattern, "gcond" },
> > { vect_recog_bool_pattern, "bool" },
> > + { vect_recog_histogram_update_pattern, "histogram_update" },
> > /* This must come before mask conversion, and includes the parts
> > of mask conversion that are needed for gather and scatter
> > internal functions. */
> > diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
> > index 869b8497780..7c01e92cb07 100644
> > --- a/gcc/tree-vectorizer.h
> > +++ b/gcc/tree-vectorizer.h
> > @@ -128,6 +128,12 @@ struct stmt_info_for_cost {
> > int misalign;
> > };
> >
> > +struct vect_histogram_info
> > +{
> > + data_reference *load_dr;
> > + data_reference *store_dr;
> > +};
> > +
> > typedef vec<stmt_info_for_cost> stmt_vector_for_cost;
> >
> > /* Maps base addresses to an innermost_loop_behavior and the stmt it was
> > @@ -1000,6 +1006,8 @@ public:
> > by index. */
> > auto_vec<vect_reduc_info> reduc_infos;
> >
> > + auto_vec<vect_histogram_info> histograms;
> > +
> > /* The vectorized form of a standard reduction replaces the original
> > scalar code's final result (a loop-closed SSA PHI) with the result
> > of a vector-to-scalar reduction operation. After vectorization,
> > @@ -1281,6 +1289,7 @@ public:
> > } *loop_vec_info;
> >
> > /* Access Functions. */
> > +#define LOOP_VINFO_HISTOGRAMS(L) (L)->histograms
> > #define LOOP_VINFO_LOOP(L) (L)->loop
> > #define LOOP_VINFO_MAIN_EXIT(L) (L)->vec_loop_main_exit
> > #define LOOP_VINFO_EPILOGUE_MAIN_EXIT(L) (L)->vec_epilogue_loop_main_exit
> >
>
>
--
Richard Biener <[email protected]>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Jochen Jaser, Andrew McDonald, Abhinav Puri; (HRB 36809, AG Nuernberg)