------------ current state ------------

1. long_rshift first checks whether a is a negative int. If it is, it does (edited for brevity) 'z = long_invert(long_rshift(long_invert(a), b));'.
   Otherwise, it calculates the result of the shift and stores it in z. In this block, there is a check whether a is a negative int.

The second check was always there - since revision 443, in which long_rshift was first added. However, in revision 590, the first aforementioned check (whether a is a negative int), along with a (edited for brevity) 'return long_invert(long_rshift(long_invert(a), b));' were added, but the second check whether a is a negative int wasn't removed, and remained there to this day.

2. Ultimately, long_rshift does 'return (PyObject *) maybe_small_long(z);' for both cases (whether a is a negative int or not).
   Calling maybe_small_long in case a is a negative int is redundant, as long_invert returns (in case it doesn't fail) by either doing 'return PyLong_FromLong(-(MEDIUM_VALUE(v)+1));' or 'return (PyObject *)maybe_small_long(x);'. In both cases, long_invert would return a reference to an element of small_ints if it should.

Calls to maybe_small_long were added both to long_rshift and long_invert in revision 48567, as part of an effort to wipe out different places in the code where small_ints could be used (to save up memory), but was not. I am not sure why maybe_small_long was added to long_rshift where it would be redundant in case a is a negative int.

3. In different cases of failure, long_rshift does 'goto rshift_error;'.
   The destination of these goto statements is actually a return statement that would also be reached in almost any case of success (except for a certain case in which the result of the shift is obviously zero).

That goto was added in revision 15725. Back then, CONVERT_BINOP was added, and calling it in long_rshift required calling Py_DECREF for a and b before returning.
Later on, in revision 43313, CONVERT_BINOP was removed, along with the calls to Py_DECREF it required, but the goto was left untouched, and remained there to this day.

------------ proposed changes ------------
All of the proposed changes are in Objects/longobject.c in long_rshift:
1. Remove the check whether a is a negative int in the block that gets executed in case a is not a negative int.

2. Move the call to maybe_small_long inside the block that runs in case a is not a negative int.

3. Replace every 'goto rshift_error;' with a 'return NULL;', and remove the rshift_error label. 

I could have kept the goto statements, with 'return (PyObject *)z;' as their destination, but I believe it would have been less clear. Also, there are many similar places in longobject.c where 'return NULL;' is done on failure.

------------ diff ------------
The proposed patches diff file is attached.

------------ tests ------------
I built the patched CPython for x86, and played with it a little. Everything seemed to work as usual.
Specifically, I did:
for i in range(10000):
if not all(smallInt is ((smallInt << i) >> i) for (
smallInt) in range(-5, 257)):
break
print(i)
And indeed 9999 was printed.

In addition, I ran 'python_d.exe -m test -j3' (on my 64-bit Windows 10) with and without the patches, and got quite the same output.
the outputs of both runs are attached.

Sorry, this fell off my list of things to look at.

New changeset 21b70c835b5b by Mark Dickinson in branch 'default':
Issue bpo-27222: various cleanups in long_rshift. Thanks Oren Milman.
https://hg.python.org/cpython/rev/21b70c835b5b

Thanks for the patch and the thorough analysis!