我能否通过给出整数的范围来提示优化器？

Question

我使用int类型来存储一个值。根据程序的语义，该值始终在非常小的范围内变化（0-36），仅因CPU效率使用int而非char。

看起来对于这么小的整数范围可以进行许多特殊的算术优化。这些整数上的许多函数调用可能被优化为一小组“神奇”的操作，有些函数甚至可以优化为表查找。

那么，有没有可能告诉编译器这个int总是在那个小范围内，并且编译器能够进行这些优化呢？

- rolevax

---

许多编译器（例如LLVM）都存在值域优化，但我不知道是否有任何语言提示可以声明它。 - Remus Rusanu

请注意，如果您从未使用过负数，则使用“unsigned”类型可能会带来小的收益，因为编译器更容易进行推理。 - user694733

Pascal允许您定义子范围类型，例如：var value: 0..36;。您可以点击链接了解更多相关信息。 - Edgar Bonet

“*int (not a char) is used only because the CPU efficiency.*”这句话并不总是正确的。有时候窄类型需要被零扩展或符号扩展到完整寄存器宽度，尤其是当作为数组索引使用时，但有时这是免费的。如果你有一个这种类型的数组，减少缓存占用通常比其他任何因素都更重要。 - Peter Cordes

忘了说：在大多数带有64位指针的系统上，int和unsigned int也需要从32位扩展为64位，无论是符号扩展还是零扩展。请注意，在x86-64上，对32位寄存器进行的操作可以免费扩展到64位（不是符号扩展，但有符号溢出是未定义行为，因此编译器可以使用64位有符号数学）。因此，您只会看到额外的指令来将32位函数参数零扩展，而不是计算结果。对于更窄的无符号类型，则需要这样做。 - Peter Cordes

Answer 1

是的，这是可能的。例如，对于 gcc，您可以使用 __builtin_unreachable 来告诉编译器有关不可能条件的信息，例如：

if (value < 0 || value > 36) __builtin_unreachable();

我们可以使用宏来包装上述条件：

#define assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)

然后像这样使用：

assume(x >= 0 && x <= 10);

As you can see, gcc performs optimizations based on this information:

此处可以看到，gcc 根据这些信息进行优化：

#define assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)

int func(int x){
    assume(x >=0 && x <= 10);

    if (x > 11){
        return 2;
    }
    else{
        return 17;
    }
}

生成：

func(int):
    mov     eax, 17
    ret

然而，一个缺点是如果您的代码违反了这些假设，您将得到未定义的行为。

即使在调试构建中，它也不会通知您发生了什么。为了更轻松地调试/测试/捕获具有假设的错误，您可以使用混合assume/assert宏（感谢@David Z），例如：

#if defined(NDEBUG)
#define assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)
#else
#include <cassert>
#define assume(cond) assert(cond)
#endif

在调试版本（未定义 NDEBUG）中，它的作用类似于普通的 assert，打印错误消息并 abort 程序，在发布版本中则使用一个假设，生成优化代码。但请注意，它不能替代常规的 assert - 在发布版本中仍然保留 cond，因此您不应该像这样做 assume(VeryExpensiveComputation())。

- user2512323

---

然而，gcc 似乎无法像 OP 预期的那样将函数优化为神奇操作或查找表。 - jingyu9575

__builtin_expect是一种非严格的提示。__builtin_expect(e, c)应该理解为“e最可能评估为c”，并且可以用于优化分支预测，但它不限制e始终为c，因此不允许优化器放弃其他情况。查看汇编中分支的组织方式。 - user2512323

理论上，任何会导致未定义行为的代码都可以用来替代__builtin_unreachable()。 - CodesInChaos

@CodesInChaos 任何会在抽象机器中无条件引起未定义行为的代码都不够好，因为编译器扩展可能会定义其行为。例如，有符号整数溢出可能会根据编译器选项被定义为终止程序，需要特殊代码确保程序确实终止。 - user743382

除非有我不知道的使这成为一个坏主意的怪癖，否则将其与 assert 结合起来可能是有意义的。例如，在未定义 NDEBUG 时将 assume 定义为 assert，在定义 NDEBUG 时将其定义为 __builtin_unreachable()。这样，您可以在生产代码中获得假设的好处，但在调试版本中仍然具有显式检查。当然，您必须进行足够的测试以确保自己在实际环境下满足假设。 - David Z

Answer 2

这个有标准的支持。你需要做的就是包括stdint.h (cstdint)，然后使用类型uint_fast8_t。

这告诉编译器你只使用0-255之间的数字，但它可以自由地使用更大的类型如果那会使代码运行更快。同样地，编译器可以假定变量永远不会有超过255的值，然后进行优化。

- Lundin

---

这些类型并没有被充分利用（我个人经常忘记它们的存在）。它们提供的代码既快速又可移植，相当优秀。而且它们自1999年以来就一直存在。 - Lundin

只有在系统中，uint_fast8_t 实际上是一个 8 位类型(例如 unsigned char)的情况下，编译器才能获得0-255范围的信息，就像在 x86/ARM/MIPS/PPC 上一样（https://godbolt.org/g/KNyc31）。在 21164A之前的早期DEC Alpha，不支持字节加载/存储，因此任何明智的实现都将使用typedef uint32_t uint_fast8_t。据我所知，在大多数编译器（如gcc）中，没有机制让类型具有额外的范围限制，因此我相当确定在那种情况下uint_fast8_t的行为会完全与unsigned int或其他类型相同。 - Peter Cordes

“bool”是特殊的，范围限制为0或1，但它是一种内置类型，不是在gcc / clang的头文件中以“char”的形式定义的。就像我说的，我认为大多数编译器都没有可能实现这种机制。 - Peter Cordes

无论如何，uint_fast8_t是一个很好的建议，因为在那些使用8位类型与unsigned int一样高效的平台上，它将使用8位类型。 （实际上，我不确定“快速”类型应该快速用于什么，以及缓存占用权衡是否应该是其中的一部分）。 x86对字节操作有广泛的支持，甚至可以使用内存源进行字节加法，因此您甚至不必进行单独的零扩展加载（这也非常便宜）。 在x86上，gcc将uint_fast16_t设置为64位类型，这对大多数用途来说是疯狂的（与32位相比）。 https://godbolt.org/g/Rmq5bv。 - Peter Cordes

@supercat: 或者你的意思是一种类型在寄存器中不一定被截断，只有在实际存储到内存时才会被截断。所以你有一个类似于x86上没有-ffloat-store的float/double的情况，其中舍入/截断取决于编译器何时/何地溢出？是的，那将是有趣的。所有uint16_t的缓存占用优势，几乎没有额外的16->64零扩展成本。 - Peter Cordes

Answer 3

当前答案适用于您确切知道范围的情况，但如果您仍然希望在值不在预期范围内时获得正确的行为，则它将无法使用。

对于这种情况，我发现这种技术可以起作用：

if (x == c)  // assume c is a constant
{
    foo(x);
}
else
{
    foo(x);
}

这个想法是代码和数据之间的权衡：将1比特的数据（无论是x == c）移入控制逻辑中。
这提示优化器x实际上是已知的常数c，鼓励它分别对第一次调用foo进行内联和优化，可能相当大。

确保将代码实际分解为单个子例程foo，不要复制代码。

示例：

为了使这种技术起作用，您需要有一些运气 - 有些情况下编译器决定不静态评估事物，而它们有点随意。但是当它有效时，它的效果很好：

#include <math.h>
#include <stdio.h>

unsigned foo(unsigned x)
{
    return x * (x + 1);
}

unsigned bar(unsigned x) { return foo(x + 1) + foo(2 * x); }

int main()
{
    unsigned x;
    scanf("%u", &x);
    unsigned r;
    if (x == 1)
    {
        r = bar(bar(x));
    }
    else if (x == 0)
    {
        r = bar(bar(x));
    }
    else
    {
        r = bar(x + 1);
    }
    printf("%#x\n", r);
}

只需使用-O3，并注意在汇编输出中预先计算的常量0x20和0x30e。

- user541686

---

你不想要 if (x==c) foo(c) else foo(x) 吗？即使只是为了捕获 foo 的 constexpr 实现？ - MSalters

@MSalters：我知道有人会问这个问题！！在constexpr出现之前，我就想出了这种技术，并且从未在之后“更新”过它（尽管我之后也从未真正担心过constexpr），但我最初没有这样做的原因是我希望让编译器更容易将它们作为公共代码分解并删除分支（如果它决定将它们留作普通方法调用而不进行优化）。我预计如果我放入c，编译器很难看出两者是相同的代码，尽管我从未验证过。 - user541686

Answer 4

我想提醒一下，如果您需要一种更标准的C++解决方案，您可以使用[[noreturn]]属性来编写自己的unreachable。

因此，我将重新利用deniss'优秀示例来进行演示：

namespace detail {
    [[noreturn]] void unreachable(){}
}

#define assume(cond) do { if (!(cond)) detail::unreachable(); } while (0)

int func(int x){
    assume(x >=0 && x <= 10);

    if (x > 11){
        return 2;
    }
    else{
        return 17;
    }
}

你可以看到，使用如你所见，结果是几乎相同的代码：

detail::unreachable():
        rep ret
func(int):
        movl    $17, %eax
        ret

当然，缺点是你会收到一个警告，表明一个被标记为 [[noreturn]] 的函数实际上会返回。

- StoryTeller - Unslander Monica

---

它可以与clang一起使用，而我的原始解决方案则不行，所以这是个好技巧，加1。但整个事情非常依赖编译器（正如Peter Cordes向我们展示的，在icc中它可能会恶化性能），因此它仍然不是普遍适用的。另外，小提示：必须使unreachable定义对优化器可用并进行内联才能使其工作。 - user2512323

一种简明的解决方案，但会生成警告。 - zjyhjqs