# [RFC] Vectorization support for histogram count operations

Hello community,

We would like to propose a mechanism that detects and safely vectorizes histogram computations. This is a work in progress, and a Proof-of-Concept Pull Request will be opened in the coming days.

# 1. Background:

### What is a histogram, and where is it used

Histogram is typically used in image processing and it ‘counts’ actual values of an image. Assuming a colored input image, a histogram would compute counters for occurrences of ‘red’, ‘green’, and ‘blue’ image values. In a typical RGB model, each color accepts values in the range of 0-255.

In our context, it’s just an input integer array and we want to count the number of occurrences of each element and store them in a separate array (ie the histogram). The input array has a consecutive number range, starting from zero, so there is no need for any advanced hash functions to find where to store each counter. Instead we can use the input values as indices for the histogram array (see motivating example code).

# 2. Motivating example:

The snippet below shows a simple, typical histogram computation. The `indices` array is the input we want to compute the histogram for, and the `buckets` is where we store the computed histogram (ie all those counters).

``````for (int i = 0; i < N; ++i) {
buckets[indices[i]]++;
}
``````

### Example input, output:

In this example, the computed histogram indicates that there are:

• 1 zero, 1 one, 2 twos, 1 three, and no fours.
``````# INPUT ARRAY:
index: 0 1 2 3 4
indices: 3 2 2 0 1

# COMPUTED HISTOGRAM:
index: 0 1 2 3 4
buckets: 1 1 2 1 0
``````

### Problem with histogram and vectorization

The example code is using the values of indices (eg, `indices[i]`) as a hash function to find where to store the counts within the buckets array.

As the compiler cannot identify at static time what are the ranges of the pointers involved, these memory operations are found to be aliasing, which disables vectorization.

Assuming vectorization went ahead, a pseudo-code IR would be something like:

``````%values = wide load from 'indices'
%prevCount = wide gather-load vector from 'buckets' using %values as indices
scatter the result (%newCount) back to relevant places (using %values as indices) in `buckets`
``````

There is a correctness issue with the vectorized addition: each lane is not ‘aware’ of any previous counts that happened on the same iteration.

This is illustrated with a dry run on the Example Input focusing on the value ‘2’ , which is encountered twice.
Value 2 is on lane 1, and lane 2, and assuming a vector length of 5 lanes, the entire vector fits in one iteration.
Running the Code:

1. The 2 twos will be wide loaded initially from indices.
2. Then, the relevant addresses will be gathered from buckets, which initially are zero.
3. The addition, computes ‘0+1’ for both.
4. Finally, the results will be scattered back to the relevant places in buckets.
• for counting the twos, there will be two writes on the same index (ie buckets[2]).
• according to the manual, the order of those writes will be from least to most significant element.
• in this case, it doesn’t really matter what is written first. It will write the value of 1, and then it will overwrite it again with 1. This is wrong. The final result should have been 2.

### Instruction needed to support histogram counts

What is needed is an instruction that considers results from previous lanes when computing the count of the current lane.

The AArch64 SVE2 histcnt Instruction does precisely that. With such an instruction, the pseudo-IR will now look like:

``````%values = wide load from 'indices'
%prevCount = wide gather-load vector from 'buckets' using %values as indices
%count = call @histogram.count(%values) ; <- CONSIDERS PREVIOUS LANES
scatter the result (%newCount) back to relevant places (using %values as indices) in `buckets`
``````

Doing a dry run just for the final scatter store, using histogram.count would be:

• write 1 to the relevant place in buckets.
• then overwrite it with a 2, which is the correct result.
• (Remember, scatter stores from least to most significant lanes)

# 3. Design

We propose the addition of an IR-level Intrinsic, that could then be lowered to target specific ones.

That intrinsic can take the input vector and a mask (for supporting predicated executions).

Targets can use `TTI` to inform `LoopVectorizer` whether they support such an Instruction, and when they do they can emit a target-specific Instruction in place of the generic, IR-Level intrinsic.

Initially, with pattern matching, can detect histograms and generate relevant `STATISTICS.` This information can be useful for understanding input codes, so it will be generated for any target regardless of hardware support.

A pattern should match the motivating example, which in essence consists of:

• a binary operation that does the counting (can be an add or even a sub) on constants integers (does not have to be a +1 like in the example).
• this counting updates previous counts within an array that uses another array to find relevant indices (eg, `buckets[indices[i]]`)

For detected histograms, different `VPlans` will be generated as usual.
During legality, `LoopAccessAnalysis` can safely ignore any pair of pointers that relate to histogram computations, as those are taken care by the intrinsic.

Loop interleaving will also be disabled programmatically for the VPlans that will emit a histogram Intrinsic, as there will be unmet dependencies between the interleaved copies.

To emit the Intrinsic, a new `VPInstruction` will be used, to generate a Histogram Intrinsic and the relevant add/sub `BinOp` upon plan’s execution.

To support predication, the `Mask` for the vectorized block will be re-used, otherwise Histogram will use an All-Ones Mask to perform on all lanes.

The best VPlan Recipe will be selected for execution according to a `CostModel`.

Best regards,
Paschalis Mpeis, Graham Hunter

2 Likes

There are multiple ways to resolve the potential index conflicts and “count” is only one of them. Would this proposal work with the AVX512CD equivalents?

I would suggest considering a different approach that instead encompasses the entire histogram operation… e.g.

``````call @histogram(input/outputvector, rhs, mask)
or
``````

This has the advantage of being easily legalized on targets without count or even without gather/scatter. It also gives you a lot of flexibility in the backend in deciding what algorithm you want to choose for a given target even IF you have count or gather/scatter. To me, count is too specific for this unless there’s another practical use for it.

Hi Scott,

Thanks for your suggestion. Indeed, a more generalized approach would be better. Can you please elaborate what `rhs` represents in your snippet?

EDIT: you must mean the amount, as in:

``````buckets[indices[i]]+=amount;
``````

Regards,
Paschalis

Yes, I meant the “right hand side” of the expression that’s not the gather/scatter. You would probably need to carry this value in the intrinsic itself for the lowering sequence.

1 Like