c - 仅使用常量移位模拟可变位移位？

Question

我正在尝试寻找一种方法来执行间接左移/右移操作，而无需实际使用变量 shift op 或任何分支。

我正在研究的特定 PowerPC 处理器有一个怪癖，即按常量立即移动，例如

int ShiftByConstant( int x ) { return x << 3 ; } 

是快速的、单操作的和超标量的，而按变量移动，比如

int ShiftByVar( int x, int y ) { return x << y ; }

是一个microcoded operation that takes 7-11 cycles to execute while the entire rest of the pipeline stops dead .

我想做的是找出哪个非微编码整数 PPC ops sraw解码成然后单独发出。这对 sraw 的延迟没有帮助本身——它将用六个操作替换一个操作——但在这六个操作之间，我可以将一些工作双重分派(dispatch)给其他执行单元并获得净 yield 。

我似乎无法在任何地方找到 μops sraw 解码成的内容 — 有谁知道我如何用一系列常量移位和基本整数运算替换可变位移位？ (for 循环或开关或任何带有分支的东西都不会工作，因为分支惩罚甚至比微码惩罚更大，即使对于正确预测的分支也是如此。)

这不需要在汇编中回答；我希望学习算法而不是特定的代码，因此用 C 或高级语言甚至伪代码的答案将非常有帮助。

编辑:我应该添加的一些说明:

1. 我一点也不担心便携性

2. PPC 有条件移动，所以我们可以假设存在无分支内函数

   int isel(a, b, c)  { return a >= 0 ? b : c; }
   

   (如果你写出一个做同样事情的三元组，我会明白你的意思)

3. 整数乘法也是微编码的，甚至比 sraw 还要慢。 :-(
4. 在 Xenon PPC 上，预测分支的延迟为 8 个周期，因此即使是一个周期也会使其与微代码指令一样昂贵。跳转到指针(任何间接分支或函数指针)肯定会预测错误，即 24 周期停顿。

Answer 1

给你...

我决定也尝试一下，因为 Mike Acton 声称这比在他的 CellPerformance 网站上使用 CELL/PS3 微编码转换更快，其中 he suggests to avoid the indirect shift .然而，在我所有的测试中，使用微编码版本不仅比间接移位的完整通用无分支替代更快，而且代码占用的内存更少(1 条指令)。

我将这些作为模板来做的唯一原因是为有符号(通常是算术)和无符号(逻辑)移位获得正确的输出。

template <typename T> FORCEINLINE T VariableShiftLeft(T nVal, int nShift)
{   // 31-bit shift capability (Rolls over at 32-bits)
    const int bMask1=-(1&nShift);
    const int bMask2=-(1&(nShift>>1));
    const int bMask3=-(1&(nShift>>2));
    const int bMask4=-(1&(nShift>>3));
    const int bMask5=-(1&(nShift>>4));
    nVal=(nVal&bMask1) + nVal;   //nVal=((nVal<<1)&bMask1) | (nVal&(~bMask1));
    nVal=((nVal<<(1<<1))&bMask2) | (nVal&(~bMask2));
    nVal=((nVal<<(1<<2))&bMask3) | (nVal&(~bMask3));
    nVal=((nVal<<(1<<3))&bMask4) | (nVal&(~bMask4));
    nVal=((nVal<<(1<<4))&bMask5) | (nVal&(~bMask5));
    return(nVal);
}
template <typename T> FORCEINLINE T VariableShiftRight(T nVal, int nShift)
{   // 31-bit shift capability (Rolls over at 32-bits)
    const int bMask1=-(1&nShift);
    const int bMask2=-(1&(nShift>>1));
    const int bMask3=-(1&(nShift>>2));
    const int bMask4=-(1&(nShift>>3));
    const int bMask5=-(1&(nShift>>4));
    nVal=((nVal>>1)&bMask1) | (nVal&(~bMask1));
    nVal=((nVal>>(1<<1))&bMask2) | (nVal&(~bMask2));
    nVal=((nVal>>(1<<2))&bMask3) | (nVal&(~bMask3));
    nVal=((nVal>>(1<<3))&bMask4) | (nVal&(~bMask4));
    nVal=((nVal>>(1<<4))&bMask5) | (nVal&(~bMask5));
    return(nVal);
}

编辑: 关于 isel() 的注释 我看到你的 isel() code on your website .

// if a >= 0, return x, else y
int isel( int a, int x, int y )
{
    int mask = a >> 31; // arithmetic shift right, splat out the sign bit
    // mask is 0xFFFFFFFF if (a < 0) and 0x00 otherwise.
    return x + ((y - x) & mask);
};

FWIW，如果你重写你的 isel() 来做一个掩码和掩码补码，它在你的 PowerPC 目标上会更快，因为编译器足够聪明，可以生成一个 'andc' 操作码。它是相同数量的操作码，但操作码中结果到输入寄存器的依赖性少了一个。这两个掩码操作也可以在超标量处理器上并行发出。如果一切都正确排列，它可以快 2-3 个周期。对于 PowerPC 版本，您只需要将返回更改为此:

return (x & (~mask)) + (y & mask);