BUG: Don't produce undefined behavior for a << b if b >= bitsof(a) by eric-wieser · Pull Request #13739 · numpy/numpy

eric-wieser · 2019-06-08T23:34:24Z

This is a continuation of gh-7473. Fixes gh-2449

eric-wieser · 2019-06-09T04:33:07Z

CI failure is due to this assert:

https://github.com/gcc-mirror/gcc/blob/9d0507742960aa9f2b99bc6e9584655ecc611792/gcc/expmed.c#L2349

numpy/core/src/umath/loops.c.src: In function ‘LONG_right_shift’:
numpy/core/src/umath/loops.c.src:830:18: internal compiler error: in expand_shift_1, at expmed.c:2349
             *out = in1 >> in2;
                  ^
numpy/core/src/umath/fast_loop_macros.h:180:9: note: in definition of macro ‘BASE_BINARY_LOOP_S_INP’
         op; \
         ^
numpy/core/src/umath/loops.c.src:828:5: note: in expansion of macro ‘BINARY_LOOP_FAST’
     BINARY_LOOP_FAST(@type@, @type@, {
     ^
Please submit a full bug report,
with preprocessed source if appropriate.
See <file:///usr/share/doc/gcc-5/README.Bugs> for instructions.
Running from numpy source directory.

Which can be reprod on godbolt here.

An extremely minimal repro is here. @juliantaylor, could you look at reporting this upstream?

seberg

Looks good to me. I have not worked with those really to be honest, but can't we put a new npy_left_shift to numpy/core/src/npymath/npy_math_internal.h.src or similar to avoid duplication?

eric-wieser · 2019-06-11T05:12:25Z

@seberg: We have no precedent in that file for functions templated over all integer types. The best we have are lcm and gcd which use the usual l and ll suffices typical of the C standard library. Unfortunately for shift we need to know the exact type, so we need overloads for short and char as well.

What names would you propose?

seberg · 2019-06-11T14:22:42Z

Oh,had not checked, but doesn't sound too bad, the normal type code should suffice, e.g. bhil (and q, if we need long long) and the capital ones for unsigned of course? Most of these names never have underscoves, but I somewhat like extra underscores npy_left_shift_@cc@ or npy_lshift@cc@, not sure I care too much (it should be private anyway).

eric-wieser · 2019-06-12T05:04:11Z

Realized that there's precedent for h and hh in printf specifiers, so the full set of suffices is u?(h{0,2}|l{0,2}). Updated to use npy_math.

Unfortunately, I strongly suspect this is going to fail CI again (and if it doesn't, then I think we have a performance problem). I think the only fix here is to add a configtest file to check for this internal compiler error, and remove O3 from the function if it occurs.

eric-wieser · 2019-06-12T05:51:58Z

Looks like this hit a problem on macOS as well. Somehow the FPU flag gets set, but only on computations with int and unsigned int.

eric-wieser · 2019-06-12T07:06:56Z

I have no idea why this happens. Is our macOS run x86, or something else? Do we have a resident macOS expert?

I have no idea, was thinking about putting it in godbold, but it is quite a lot of code around it (and I am not sure it is likely to show anything in any case).

@charris, I think I am good with this as is. But you had a look at it before and know npy_math stuff better. The floatstatus thing (and I guess the compile time check) are a bit unfortunate though...

Could be a clang thing.

eric-wieser · 2019-06-12T15:48:30Z

Coverage stats are just bad because we can't measure coverage for setup.py. ARM CI now passes, because setup.py now looks for this compiler bug and avoids requesting optimization for that particular loop if the bug is present.

It means 64-bit >> and << will be slower on ARM, but only on old compilers.

charris · 2019-06-28T16:55:29Z

Do we want to deal with the possibility that b is negative?

Not that currently the shift value is cast to unsigned and masked, at least on my hardware.

In [1]: a = array([1,2,3,4]) In [2]: a << -1 Out[2]: array([-9223372036854775808, 0, -9223372036854775808, 0])

I think there was a comment in the old/new code about that as well. Maybe we can push it off to another PR? That seems the easiest way forward? We can ignore the codecov failures.

xref gh-13898

mattip · 2019-07-03T01:43:30Z

Fixes #2249

mattip · 2019-07-03T01:45:05Z

With the caveat that negative shifts still need to be handled, I think this is good to go as is

charris · 2019-07-03T02:07:27Z

I'm OK with this going in. Would be good to have a release note about changed behavior in case it affects somebody downstream.

mattip · 2019-07-14T15:38:19Z

Waiting on resolution of #13908 to know how to add a release note

mattip · 2019-07-17T14:53:05Z

Since #13908 is taking a while, perhaps just add a not to doc/release/1.18.0-notes.rst and we will refactor that file if/when #13908 lands

charris · 2019-07-23T16:32:59Z

@seberg Ping.

seberg · 2019-07-23T16:50:44Z

@charris thanks. Let me merge the towncrier related PRs (since nobody complained), and then I will add a short release note to this. Other than that I remember this as being good (although that compiler bug is a bit annoying).

seberg · 2019-07-24T22:23:59Z

OK, I rebased this (it was a bit messy) and added a release note (we will have to modify the towncrier template a bit before the end, but it works).

Master seems to have added @isa@ (and the GCC flag) since that exists on master, but I am not sure what the state of this was before the rebase? I do not think it had the @isa@, but also not sure how that adds up with the place in code. Is AVX worth it here?

mattip · 2019-09-12T22:54:52Z

restarting tests

This: * Inlines the macros in loops.c.src * Replaces 8 with `CHAR_BIT `. The `NPY_SIZEOF_*` macros are not used here because it's too much work to apply them to the signed types, and they expand to the same thing anyway. * Removes the reduce loop specializations which likely no one cares about * Uses pytest.mark.parametrize to shorten the test

This avoids duplication, as suggested in review. The suffices `l`, `ull` etc are for consistency with `strtoull` and friends. `h` and `uhh` are inspired from the C99 printf specifiers.

…rror Needed to make CI pass

mattip · 2019-09-14T17:14:06Z

Thanks @eric-wieser

## Summary `BitShift` currently only accepts unsigned integer types. This adds signed integer types in a new opset-28 schema. Fixes #2406 Will be necessary for #5497 too. ## Motivation `BitShift` is the only bitwise operator still restricted to unsigned types. `BitwiseAnd`, `BitwiseOr`, `BitwiseXor` and `BitwiseNot` already support signed types. a4f44a2 added `BitShift` to support hashing algorithms, which only need unsigned types. But shifting with sign extension may be used in other contexts. See for reference: * Appendix B of https://arxiv.org/abs/1712.05877 * gemmlowp: https://github.com/google/gemmlowp/blob/16e8662c34917be0065110bfcd9cc27d30f52fdf/fixedpoint/fixedpoint.h#L365-L379 * TOSA [ARITHMETIC_RIGHT_SHIFT](https://www.mlplatform.org/tosa/tosa_spec_1_0_0.html#_arithmetic_right_shift) and [RESCALE](https://www.mlplatform.org/tosa/tosa_spec_1_0_0.html#_rescale) definition. * https://arxiv.org/abs/1905.13298 Shifting of signed integer types is available in other frameworks. This reference implementation continues to use NumPy, and that matches PyTorch and JAX too: https://gist.github.com/mcollinswisc/7cc504381d6c30ee50ef72745f47c6e5 (PyTorch bit shift supports the signed dtypes and `uint8`, but *not* `uint16`, `uint32` or `uint64`.) MindSpore and Tensorflow are found to produce different results, but only on shift counts that are out of range. Casting to an unsigned type is not a workaround. For a right shift it turns a (sign-extending) arithmetic shift into a logical shift, which gives a different result for negative input. ## Op Semantics Semantics are chosen to match NumPy (which jax and PyTorch match too). Some of the behavior (namely for shifts Y that are out of range: negative or larger than the bit width of X) is *not* fully documented by NumPy, but this new BitShift spec does describe it. The results of NumPy can be explained entirely from their implementation and well-defined C behavior. The NumPy PR numpy/numpy#13739 ensured this: 1. numpy/numpy#13739 added logic that explicitly handles shift amounts Y that are `>=` to the bit width of X 2. While [comments in NumPy](https://github.com/numpy/numpy/blob/5e1d03ffac5f2c0a9c39bfcaa9fc853b2b83151e/numpy/_core/src/umath/loops_autovec.dispatch.c.src#L22-L23) still say handling of negative shifts is TODO, the `size_t` casts at https://github.com/numpy/numpy/blob/5e1d03ffac5f2c0a9c39bfcaa9fc853b2b83151e/numpy/_core/src/npymath/npy_math_internal.h.src#L687 and https://github.com/numpy/numpy/blob/5e1d03ffac5f2c0a9c39bfcaa9fc853b2b83151e/numpy/_core/src/npymath/npy_math_internal.h.src#L697 do deterministically define the behavior: because this cast is defined by [C11 6.3.1.3p2](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf) (and continues to be defined in the same way through C23). Negative Y becomes a very large `size_t` value in the `if` condition & the result will be the saturated 0 or -1. The reference implementation & expected test results continue to simply use NumPy. Results are verified more thoroughly against numpy, torch, and JAX in: https://gist.github.com/mcollinswisc/7cc504381d6c30ee50ef72745f47c6e5 The opset-28 definition is a superset of opset-11, so version upgrade is trivial. --------- Signed-off-by: Maxwell D Collins <[email protected]> Signed-off-by: Justin Chu <[email protected]> Co-authored-by: Claude Opus 5 (1M context) <[email protected]> Co-authored-by: Copilot Autofix powered by AI <[email protected]> Co-authored-by: Andreas Fehlner <[email protected]> Co-authored-by: Justin Chu <[email protected]> Co-authored-by: Copilot App <[email protected]> Copilot-Session: e0da9f12-d855-4907-b12e-43cc8a045ef7

BUG: shift operator cycles, fixes numpy#2449

24b2a2d

eric-wieser added 00 - Bug component: numpy._core labels Jun 8, 2019

eric-wieser requested a review from charris June 8, 2019 23:34

eric-wieser force-pushed the bit_shifts branch from 8599d13 to bdad142 Compare June 8, 2019 23:35

eric-wieser mentioned this pull request Jun 8, 2019

BUG: shift operator cycles, fixes #2449 #7473

Closed

seberg self-requested a review June 9, 2019 02:10

Merge tag 'branch-points/1.16.x' into bit_shifts

b12a869

eric-wieser force-pushed the bit_shifts branch from bdad142 to b223009 Compare June 9, 2019 04:13

seberg approved these changes Jun 10, 2019

View reviewed changes

eric-wieser force-pushed the bit_shifts branch from 5a31250 to 0e1eb97 Compare June 12, 2019 05:51

eric-wieser force-pushed the bit_shifts branch from 0e1eb97 to 4fa467b Compare June 12, 2019 06:46

eric-wieser commented Jun 12, 2019

View reviewed changes

eric-wieser force-pushed the bit_shifts branch 3 times, most recently from e8fbd2f to 6d4eb24 Compare June 12, 2019 08:51

charris reviewed Jun 28, 2019

View reviewed changes

seberg self-assigned this Jul 2, 2019

mattip mentioned this pull request Jul 3, 2019

BUG: shift with a negative number should fail #13898

Open

mattip added the 56 - Needs Release Note. Needs an entry in doc/release/upcoming_changes label Jul 14, 2019

eric-wieser mentioned this pull request Jul 14, 2019

Shift operator cycles for int32 and int64 (Trac #1856) #2449

Closed

seberg self-requested a review July 17, 2019 16:01

seberg force-pushed the bit_shifts branch 4 times, most recently from 55cf805 to 9f258d8 Compare July 24, 2019 22:22

seberg removed the 56 - Needs Release Note. Needs an entry in doc/release/upcoming_changes label Jul 24, 2019

eric-wieser commented Jul 28, 2019

View reviewed changes

Comment thread numpy/core/src/npymath/npy_math_internal.h.src Resolved

seberg removed their assignment Sep 12, 2019

mattip closed this Sep 12, 2019

mattip reopened this Sep 12, 2019

eric-wieser added 5 commits September 13, 2019 00:49

Merge tag 'branch-points/1.17.x' into HEAD

e487889

Merge commit 'edf8a5f' into HEAD

ff11d01

MAINT: Move shift implementation to npy_math

79d7bc2

This avoids duplication, as suggested in review. The suffices `l`, `ull` etc are for consistency with `strtoull` and friends. `h` and `uhh` are inspired from the C99 printf specifiers.

BUG: Disable -O3 on right_shift on compilers which emit an internal e…

6cf6ece

…rror Needed to make CI pass

eric-wieser force-pushed the bit_shifts branch from 9f258d8 to 6cf6ece Compare September 13, 2019 07:58

mattip merged commit 31ffdec into numpy:master Sep 14, 2019

eric-wieser deleted the bit_shifts branch September 14, 2019 19:59

seberg mentioned this pull request Jan 7, 2022

Inconsistent bitwise shift overflow behavior #10299

Closed

mcollinswisc mentioned this pull request Aug 7, 2026

Add BitShift-28 with signed integer type support onnx/onnx#8270

Merged

Conversation

eric-wieser commented Jun 8, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

eric-wieser commented Jun 9, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

seberg left a comment

Choose a reason for hiding this comment

Uh oh!

eric-wieser commented Jun 11, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

seberg commented Jun 11, 2019

Uh oh!

eric-wieser commented Jun 12, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

eric-wieser commented Jun 12, 2019

Uh oh!

eric-wieser Jun 12, 2019

Choose a reason for hiding this comment

Uh oh!

seberg Jun 14, 2019

Choose a reason for hiding this comment

Uh oh!

charris Jul 3, 2019

Choose a reason for hiding this comment

Uh oh!

eric-wieser commented Jun 12, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

charris Jun 28, 2019

Choose a reason for hiding this comment

Uh oh!

charris Jun 28, 2019

Choose a reason for hiding this comment

Uh oh!

seberg Jul 2, 2019

Choose a reason for hiding this comment

Uh oh!

mattip Jul 3, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mattip commented Jul 3, 2019

Uh oh!

mattip commented Jul 3, 2019

Uh oh!

charris commented Jul 3, 2019

Uh oh!

mattip commented Jul 14, 2019

Uh oh!

mattip commented Jul 17, 2019

Uh oh!

charris commented Jul 23, 2019

Uh oh!

seberg commented Jul 23, 2019

Uh oh!

seberg commented Jul 24, 2019

Uh oh!

Uh oh!

mattip commented Sep 12, 2019

Uh oh!

mattip commented Sep 14, 2019

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

eric-wieser commented Jun 8, 2019 •

edited

Loading

eric-wieser commented Jun 9, 2019 •

edited

Loading

eric-wieser commented Jun 11, 2019 •

edited

Loading

eric-wieser commented Jun 12, 2019 •

edited

Loading

eric-wieser commented Jun 12, 2019 •

edited

Loading

mattip Jul 3, 2019 •

edited

Loading