Several discrepancies in the implementation of reduction functions

[zephyr111]

In the documentation, we can read that the reduction function returns a type bigger than the input (certainly to avoid overflow):

uniform int16 reduce_add(int8 x)
uniform unsigned int16 reduce_add(unsigned int8 x)
uniform int32 reduce_add(int16 x)
uniform unsigned int32 reduce_add(unsigned int16 x)
uniform int64 reduce_add(int32 x)
uniform unsigned int64 reduce_add(unsigned int32 x)
uniform int64 reduce_add(int64 x)
uniform unsigned int64 reduce_add(unsigned int64 x)

Note that this is not the case for the 64-bit type since it is the biggest supported type so far.

In the stdlib implementation, we can see that functions __reduce_add_intxx are called internally. For example, here is 3 of them:

__declspec(safe) static inline uniform unsigned int16 reduce_add(unsigned int8 x) {
    return __reduce_add_int8(__mask ? x : (int8)0);
}
__declspec(safe) static inline uniform int32 reduce_add(int16 x) { return __reduce_add_int16(__mask ? x : (int16)0); }
__declspec(safe) static inline uniform int64 reduce_add(int32 x) {
    // Zero out the values for lanes that aren't running
    return __reduce_add_int32(__mask ? x : 0);
}

The thing is the underlying functions does not actually use the matching proper types in all cases. See builtins.isph:

EXT inline READNONE uniform int16 __reduce_add_int8(varying int8);
EXT inline READNONE uniform int16 __reduce_add_int16(varying int16);
EXT inline READNONE uniform int32 __reduce_add_int32(varying int32);
EXT inline READNONE uniform int64 __reduce_add_int64(varying int64);

We can see that only the int8 type is correctly supported here.

Fixing this will certainly impact performance (not that much overall since reductions are generally performed once after loops), but the current code is clearly bogus IMHO (at least, this is neither documented nor expected regarding the output types). Do you agree?

---

There is another issue in the implementation: the unsigned version just call the signed version so big unsigned integers are converted to negative value and I highly doubt the result is correct in this case. See stdlib.ispc:

__declspec(safe) static inline uniform unsigned int64 reduce_add(unsigned int32 x) {
    // Set values for non-running lanes to zero so they don't affect the
    // result.
    return __reduce_add_int32(__mask ? x : 0);
}

IMHO, unsigned functions (like __reduce_add_uint32 for the above implementation) are missing.

[elena901]

Do you agree?

Agree. Ideally, the programmer should be allowed to manage the returned type. Even if we lose some people living on LSS (in the ICU) because of it.

UPD: Probably it's a topic for a different discussion, but to me it's not clear why (in C languages) you can pass unsigned int as a signed argument without any cast.

[aneshlya]

@zephyr111 ,

Thank you for the detailed analysis. You are correct on both issues.

Issue 1: Return type discrepancy

The internal __reduce_add_intXX functions don't match the documented behavior:

• reduce_add(int16) → should return int32 but actually returns int16
• reduce_add(int32) → should return int64 but actually returns int32

Issue 2: Missing unsigned variants

You're also correct that the unsigned versions improperly call the signed internal functions. The generated IR confirms that sext is used instead of zext, which is incorrect for unsigned types. Interestingly, reduce_min and reduce_max DO have proper unsigned variants (__reduce_min_uint32, __reduce_max_uint32, etc.), so reduce_add should follow the same pattern.

Proposed fix:

1. Add __reduce_add_uintXX functions with proper zero-extension
2. Change __reduce_add_int16 to compute in i32 and return int32
3. Change __reduce_add_int32 to compute in i64 and return int64

[zephyr111]

Ideally, the programmer should be allowed to manage the returned type

@elena901 I agree. I do not know what is the simplest solution (from both the user PoV and the ISPC dev side) to select that. Maybe having alternative function is the best. For now, let's fix the issue first, check the result, and then extend the stdlib later (if needed). I wonder if storing the output in a smaller type actually generates a reasonably-fast code (probably not) compared to implementing an alternative version with an output type equal to the input one.

PS: what "LSS" and "ICU" means?

Proposed fix: [...]

@aneshlya Ok. I agree.

[zephyr111]

@aneshlya Actually, I think the initial reason why it has been done that way comes from the SSE/AVX instructions. Indeed, the instruction psadbw performs a reduction on (unsigned) 8-bit integers and it produces (unsigned) 16-bit ones. There is AFAIK no similar direct instruction for 16-bit and 32-bit integers. Strangely, llvm.x86.avx2.psad.bw is called for __reduce_add_int8 operating on signed integers. I just checked and this is not correct: the current reduce_add function is bogus for negative signed 8-bit integer. Here is a minimal reproducible example:

// Command used to build this file (named test.ispc): 
// ispc test.ispc -o test.o --pic --target=avx2-i32x8 && clang++ test.o -o ispc_test
extern "C" uniform int main()
{
    // With the target avx2-i32x8:
    // [-3 -2 -1 +0 +1 +2 +3 +4] 
    const int8 v = programIndex - 3;
    const uniform int16 res = reduce_add(v);
    print("result: %\n", res); // ===> Wrongly print 772 instead of 4
    return 0;
}

---

Besides, I expect the corrected function to be about twice slower and possibly more for the 8-bit signed version.

---

Considering that adding a cast prior to the reduction is trivial from the user PoV and considering that current addition function does not return extended types, IMHO it is maybe finally better to provide reduction stdlib function not using extended types for the reduce_add. We could provide functions like reduce_add_ex doing that internally then (e.g. reduce_add of 16-bit integers just call reduce_add((int32)value)). Theoretically, the main issue of this solution is that it does not preserve the backward compatibility. That being said, it does not look like current function are correctly implemented anyway so it might not be eventually a real issue... I am mainly concerned about performance. What do you think about it?

[aneshlya]

Wow, that's a lot of bugs with reduce_add! :)

I traced the git history and it seems like it was implemented this way from the beginning, without clear hints about type widening or the logic behind return types.

I suggest we approach this problem gradually - we may find the right approach for type widening along the way.

First fix correctness bugs (keep same-type returns)

1. Fix reduce_add(int8) for signed values (can't use psadbw)
2. Add __reduce_add_uint8 that keeps psadbw (fast and correct for unsigned)
3. Add other unsigned variants (__reduce_add_uint16, etc.)
4. Keep int16→int16, int32→int32 returns (no widening for now)

On type widening:
The current implementation is definitely confusing and inconsistent - int8 widens the result while others don't. There are several TODO comments in the code questioning this. Meanwhile, stdlib.ispc and the documentation already declare widened return types:

  __declspec(safe) static inline uniform int16 reduce_add(int8 x) { ... }
  __declspec(safe) static inline uniform int32 reduce_add(int16 x) { ... }
  __declspec(safe) static inline uniform int64 reduce_add(int32 x) { ... }

I understand the performance implications of implementing proper widening. I also kind of understand why int8 was treated differently - it can overflow very quickly in contrast to larger types. Since users can widen the type themselves via cast (reduce_add((int32)my_int16_value)), perhaps the best approach is to update the documentation and stdlib declarations to reflect same-type returns, and document the cast pattern for overflow-safe reductions.

But let's start with correctness first and see where we land.

When fixing/adding __reduce_add_int8, remember that ISPC targets are hierarchical (https://github.com/ispc/ispc/blob/main/.claude/skills/ispc-builtins/SKILL.md) - if an implementation is not target-specific, it only needs to be in generic.ispc and will be inherited by all targets.

@zephyr111, what do you think?