问题
假设您有一个简单的函数，它返回基于查找表的值，例如：
请参见关于假设的编辑。
uint32_t
lookup0(uint32_t r) {
static const uint32_t tbl[] = { 0, 1, 2, 3 };
if(r >= (sizeof(tbl) / sizeof(tbl[0]))) {
__builtin_unreachable();
}
/* Can replace with: `return r`. */
return tbl[r];
}
uint32_t
lookup1(uint32_t r) {
static const uint32_t tbl[] = { 0, 0, 1, 1 };
if(r >= (sizeof(tbl) / sizeof(tbl[0]))) {
__builtin_unreachable();
}
/* Can replace with: `return r / 2`. */
return tbl[r];
}
是否有任何超级优化基础设施或算法可以从查找表转到优化的ALU实现。
动机
动机是我正在为NUMA机器构建一些锁，并希望能够通用地配置我的代码。在NUMA锁中，您需要执行cpu_id->CCD_ 2。很明显，我可以在配置过程中设置查找表，但由于我正在尽我所能争取每一滴内存带宽，我希望能找到一个能够覆盖大多数布局的解决方案。
看看现代编译器是如何做到的：
clang和gcc目前都无法做到这一点。
如果您将其重写为switch/case语句，Clang能够获得lookup0。
lookup0(unsigned int): # @lookup0(unsigned int)
movl %edi, %eax
movl lookup0(unsigned int)::tbl(,%rax,4), %eax
retq
...
case0(unsigned int): # @case0(unsigned int)
movl %edi, %eax
retq
但不能得到CCD_ 8。
lookup1(unsigned int): # @lookup1(unsigned int)
movl %edi, %eax
movl .Lswitch.table.case1(unsigned int)(,%rax,4), %eax
retq
...
case1(unsigned int): # @case1(unsigned int)
movl %edi, %eax
movl .Lswitch.table.case1(unsigned int)(,%rax,4), %eax
retq
Gcc也拿不到。
lookup0(unsigned int):
movl %edi, %edi
movl lookup0(unsigned int)::tbl(,%rdi,4), %eax
ret
lookup1(unsigned int):
movl %edi, %edi
movl lookup1(unsigned int)::tbl(,%rdi,4), %eax
ret
case0(unsigned int):
leal -1(%rdi), %eax
cmpl $2, %eax
movl $0, %eax
cmovbe %edi, %eax
ret
case1(unsigned int):
subl $2, %edi
xorl %eax, %eax
cmpl $1, %edi
setbe %al
ret
我想我可以用一些自定义的暴力方法来处理相当多的必要情况，但我希望这是一个解决了的问题。
编辑：
唯一真实的假设是：
- 所有输入都在LUT中有一个索引
- 所有的值都是正的(认为这会让事情变得更容易)，并且对于任何在线的系统配置都是正确的
- (第四版)再增加一个假设。LUT是密集的。也就是说，它覆盖范围
[<low_bound>, <bound_bound>]，但没有超出该范围的任何内容
在我的CPU拓扑中，我通常会期望sizeof(LUT) >= <max_value_in_lut>，但这是我给出的一个示例所特有的，并且会有一些反例。
第2版：
我写了一个非常简单的优化器，它为我在这里测试的CPU拓扑做了合理的工作。但显然情况会好很多。
第3版：
这个问题/最初的例子似乎有些混乱(我本应该更清楚一些)。
示例lookup0/lookup1是任意的。我希望找到一个可以扩展到4个索引之外并具有不同值的解决方案。
我想到的用例是CPU拓扑，所以~256-1024是我期望的大小上限，但对于通用LUT，它显然会变得更大。
最好的"通用的"；我知道的解决方案如下：
int compute(int r)
{
static const int T[] = {0,0,1,1};
const int lut_size = sizeof(T) / sizeof(T[0]);
int result = 0;
for(int i=0 ; i<lut_size ; ++i)
result += (r == i) * T[i];
return result;
}
在-O3中，GCC和Clang展开循环，传播常数，并生成类似于以下内容的中间代码：
int compute(int r)
{
return (r == 0) * 0 + (r == 1) * 0 + (r == 2) * 1 + (r == 3) * 1;
}
GCC/Clang优化器知道乘法可以用条件移动来代替(因为开发人员经常使用这一技巧来指导编译器生成没有条件分支的汇编代码)。
Clang的最终组装如下：
compute:
xor ecx, ecx
cmp edi, 2
sete cl
xor eax, eax
cmp edi, 3
sete al
add eax, ecx
ret
GCC也是如此。没有分支，也没有内存访问(至少只要值很小)。与小值相乘也被快速lea指令所取代。
Godbolt上提供了更完整的测试。
请注意，此方法应该适用于较大的表，但如果表太大，则循环将不会自动展开。由于有了编译标志，您可以告诉编译器使用更积极的展开。也就是说，如果LUT很大，它可能会更快，因为在这种病态的情况下，加载和执行大量代码是缓慢的。
您可以将数组打包为一个长整数，并使用移位和安定来提取结果。
例如，对于表{2,0,3,1}，可以使用处理
uint32_t lookup0(uint32_t r) {
static const uint32_t tbl = (2u << 0) | (0u << 8) |
(3u << 16) | (1u << 24);
return (tbl >> (8 * r)) & 0xff;
}
它产生了相对不错的组装：
lookup0: # @lookup0
lea ecx, [8*rdi]
mov eax, 16973826
shr eax, cl
movzx eax, al
ret
不完美，但没有分支，没有间接性。
这种方法是相当通用的，并且它可以通过"；仰视；同时进行多个输入。
有一些技巧可以允许处理较大的数组，比如使用较长的整数(即uint64_t或__uint128_t扩展)。另一种方法是像高位和低位字节一样拆分数组中的值位，查找它们并使用逐位操作进行组合。