add Py_ASSUME() macro for __builtin_unreachable() #82328

Activity

1. sir-sigurd commented on Sep 12, 2019

   

   sir-sigurdmannequin

   on Sep 12, 2019

   MannequinAuthor

   More actions

   GCC (along with Clang and ICC) has __builtin_unreachable() and MSVC has __assume() builtins, that can be used to optimize out unreachable conditions.

   So we could add macro like this:

   #ifdef Py_DEBUG
   #   define Py_ASSUME(cond) (assert(cond))
   #else
   #   if defined(_MSC_VER)
   #       define Py_ASSUME(cond) (__assume(cond))
   #   elif defined(__GNUC__)
   #       define Py_ASSUME(cond) (cond? (void)0: __builtin_unreachable())
   #   else
   #       define Py_ASSUME(cond) ((void)0);
   #   endif
   #endif

   Here's a pair of really simple examples showing how it can optimize code: https://godbolt.org/z/g9LYXF.

   Real world example. _PyLong_Copy() [1] calls _PyLong_New() [2]. _PyLong_New() checks the size, so that overflow does not occur. This check is redundant when _PyLong_New() is called from _PyLong_Copy(). We could add a function that bypass that check, but in LTO build PyObject_MALLOC() is inlined into _PyLong_New() and it also checks the size. Adding Py_ASSUME((size_t)size <= MAX_LONG_DIGITS) allows to bypass both checks.

   [1]

   cpython/Objects/longobject.c

   Lines 287 to 309 in 3a4f667

   	_PyLong_Copy(PyLongObject *src)
   	{
   	PyLongObject *result;
   	Py_ssize_t i;
   	assert(src != NULL);
   	i = Py_SIZE(src);
   	if (i < 0)
   	i = -(i);
   	if (i < 2) {
   	sdigit ival = MEDIUM_VALUE(src);
   	if (IS_SMALL_INT(ival)) {
   	return get_small_int(ival);
   	}
   	}
   	result = _PyLong_New(i);
   	if (result != NULL) {
   	Py_SIZE(result) = Py_SIZE(src);
   	while (--i >= 0)
   	result->ob_digit[i] = src->ob_digit[i];
   	}
   	return (PyObject *)result;
   	}

   
   [2]

   cpython/Objects/longobject.c

   Lines 264 to 283 in 3a4f667

   	_PyLong_New(Py_ssize_t size)
   	{
   	PyLongObject *result;
   	/* Number of bytes needed is: offsetof(PyLongObject, ob_digit) +
   	sizeof(digit)*size. Previous incarnations of this code used
   	sizeof(PyVarObject) instead of the offsetof, but this risks being
   	incorrect in the presence of padding between the PyVarObject header
   	and the digits. */
   	if (size > (Py_ssize_t)MAX_LONG_DIGITS) {
   	PyErr_SetString(PyExc_OverflowError,
   	"too many digits in integer");
   	return NULL;
   	}
   	result = PyObject_MALLOC(offsetof(PyLongObject, ob_digit) +
   	size*sizeof(digit));
   	if (!result) {
   	PyErr_NoMemory();
   	return NULL;
   	}
   	return (PyLongObject*)PyObject_INIT_VAR(result, &PyLong_Type, size);

   See More
2. vstinner commented on Sep 19, 2019

   

   vstinner

   on Sep 19, 2019

   Member

   More actions

   Real world example. _PyLong_Copy() [1] calls _PyLong_New() [2]. _PyLong_New() checks the size, so that overflow does not occur. This check is redundant when _PyLong_New() is called from _PyLong_Copy(). We could add a function that bypass that check, but in LTO build PyObject_MALLOC() is inlined into _PyLong_New() and it also checks the size. Adding Py_ASSUME((size_t)size <= MAX_LONG_DIGITS) allows to bypass both checks.

   This sounds like a bad usage of __builtin_unreachable().

   _PyLong_New() must always check that size <= MAX_LONG_DIGITS, the check must not be optimized by the compiler.

   __builtin_unreachable() must only be used if the code really be reached by design.

   For example:

   if (...) { Py_FatalError("oops)"; __builtin_unreachable() }

   But it's a bad example, since Py_FatalError is decorated with the "noreturn" attribute, so the compiler should already know that Py_FatalError() never returns.
3. vstinner commented on Sep 19, 2019

   

   vstinner

   on Sep 19, 2019

   Member

   More actions

   This check is redundant when _PyLong_New() is called from _PyLong_Copy().

   If you care of _PyLong_Copy() performance, you should somehow manually inline _PyLong_New() inside _PyLong_Copy().
4. sir-sigurd commented on Sep 19, 2019

   

   sir-sigurdmannequin

   on Sep 19, 2019

   MannequinAuthor

   More actions

   If you care of _PyLong_Copy() performance, you should somehow manually inline _PyLong_New() inside _PyLong_Copy().

   It doesn't solve this:

   We could add a function that bypass that check, but in LTO build PyObject_MALLOC() is inlined into _PyLong_New() and it also checks the size. Adding Py_ASSUME((size_t)size <= MAX_LONG_DIGITS) allows to bypass both checks.

   Here's example: sir-sigurd@c8699d0.

   I attach some disassembly from this example compiled with LTO, to demonstrate how the proposed macro affects generated code.
5. vstinner commented on Sep 19, 2019

   

   vstinner

   on Sep 19, 2019

   Member

   More actions

   Here's example: sir-sigurd@c8699d0.

   "_Py_ASSUME((size_t)size <= MAX_LONG_DIGITS);"

   Typically, such code use assert() and is removed for release build.

   assert() is more for contract base programming: when the error "cannot" happen at runtime (it would be a programming error).

   For other cases, I prefer to always emit code to handle the error (the error can happen, for example, the function must check inputs), even in release build.
6. vstinner

   changed the title [-]add macro for __builtin_unreachable[/-] [+]add Py_ASSUME() macro for __builtin_unreachable()[/+] on Sep 19, 2019
7. vstinner commented on Sep 23, 2019

   

   vstinner

   on Sep 23, 2019

   Member

   More actions

   See also bpo-38249.
8. ezio-melotti

   transferred this issue fromon Apr 10, 2022
9. iritkatriel commented on Nov 27, 2023

   

   iritkatriel

   on Nov 27, 2023

   Member

   More actions

   Closing as there is no consensus here, so this won't happen without a wider discussion on python-dev (following which this can be reopened).
10. iritkatriel

    closed this as not plannedon Nov 27, 2023
11. vstinner commented on Nov 28, 2023

    

    vstinner

    on Nov 28, 2023

    Member

    More actions

    The C API has the Py_UNREACHABLE() macro which does basically implement requested feature:

    GCC (along with Clang and ICC) has __builtin_unreachable() and MSVC has __assume() builtins, that can be used to optimize out unreachable conditions.

    Extract of the implementation:

    (...)
    #elif defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 5))
    #  define Py_UNREACHABLE() __builtin_unreachable()
    #elif defined(__clang__) || defined(__INTEL_COMPILER)
    #  define Py_UNREACHABLE() __builtin_unreachable()
    #elif defined(_MSC_VER)
    #  define Py_UNREACHABLE() __assume(0)
    #else
    #  define Py_UNREACHABLE() \
        Py_FatalError("Unreachable C code path reached")
    #endif