gcc复数常数折叠

Question

似乎gcc对复杂的常量折叠有一些限制.这是一个例子:

static inline unsigned int DJBHash(const char *str)
{
   int i;
   unsigned int hash = 5381;

   for(i = 0; i < strlen(str); i++)
   {
      hash = ((hash << 5) + hash) + str[i];   
   }

   return hash;
}

int f(void)
{   
    return DJBHash("01234567890123456");
}

当使用-O3优化级别(gcc 4.8)运行时,它很好地展开了DJBHash中的循环,并在编译期间计算该字符串的哈希值.

但是,当使字符串长一个字符时,return DJBHash("012345678901234567");它不再折叠它并生成带有条件跳转指令的循环.

我想将任意长度的文字字符串折叠为其哈希值作为编译时常量.
这可以吗？

澄清

我的问题是关于gcc的常量折叠优化(请参阅标题 - 请不要删除gcc和编译器标签)
这里的许多答案试图用模板或constexpr解决问题.很高兴知道这些选项,并感谢发布它们为所有人的利益.但是,他们没有直接回答我的问题.

实际上,我正在使用gcc端口,因此我可以根据需要更改和构建gcc源代码.但我只限于C,我想在这个范围内解决这个问题.

Answer 1

这是一个使用的版本constexpr.它在某方面与其他方面略有不同 - 递归,最简单的方法是将字符串哈希回到前面,可以这么说.例如,它为"abc"赋予的值将是您通常期望从"cba"获得的值.我不认为这应该在使用中产生任何真正的区别,只要你一直使用其中一个(但考虑到散列的变化,我可能是错的).

它确实在编译时进行评估 - 例如,我们可以将结果用作switch语句中的标签:

#include <iostream>

unsigned constexpr const_hash(char const *input) {
    return *input ?
           static_cast<unsigned>(*input) + 33 * const_hash(input + 1) :
           5381;
}

int main(int argc, char **argv) {
    switch (const_hash(argv[1])) {
    case const_hash("one"): std::cout << "one"; break;
    case const_hash("two"): std::cout << "two"; break;
    }
}

显然,可能存在冲突,因此您通常不希望将其用作案例语句标签 - 我主要是这样做以强制在结果不是编译时常量的情况下无法编译的情况.

编辑:如果你关心哈希算法是"正确的",我想这更准确(感谢@Abyx):

unsigned constexpr const_hash(char const *input, unsigned hash = 5381) {
    return *input ?
        const_hash(input + 1, hash * 33 + static_cast<unsigned>(*input)): 
        hash;
}

Answer 2

OP对C中的常量折叠感兴趣,但仅仅是因为它的C++兄弟:在C++ 14中,你可以简单地放在constexpr两个函数的前面,并修改循环以补偿strlen()不是constexpr

#include<iostream>

static inline constexpr unsigned int DJBHash(const char *str)
{
   unsigned int hash = 5381;

   for(auto i = 0; i < 512; ++i) {
      if (*str == '\0') return hash;
      hash = ((hash << 5) + hash) + static_cast<unsigned int>(*str);   
   }

   return hash;
}

constexpr unsigned int f(void)
{   
    return DJBHash("01234567890123456");
}

int main()
{
    constexpr auto h = f(); 
    std::cout << std::hex << h << "\n"; // 88a7b505
}

使用Clang 3.4 SVN的实时示例-std=c++1y.

注意:当前的Clang实现没有正确运行a while(*str != '\0').相反,有一个带有返回条件的有限循环512可以完成工作.

Answer 3

不是答案，只是另一个数据点。

下面的实现更糟糕。GCC 4.7.3 正确地应用了 TCO 将此实现转换为循环，但它在编译时仅评估为“0”！

static inline unsigned int DJBHash2(const char *str, unsigned int hash) {
   return *str ? DJBHash2(str + 1, 33 * hash + *str) : hash; }

从好的方面来说，递归版本短了 7 个字节。

其他人提到了 clang，所以这里是 clang 3.1 -O3 的结果。它为两个版本的 DJBHash 生成不同的代码，但它们的字节数相同。有趣的是，它将原始版本的移位和加法转换为乘法。它将两个版本优化为最多 100 个字符的字符串常量。最后，clang 代码比最短的 GCC 代码短 5 个字节。