只使用常量移位来模拟可变位移位？

Question

我试图找到一种方法来执行间接移位-左/右操作，而不实际使用变量移位操作或任何分支。

我正在研究的特定的PowerPC处理器有一个怪癖，那就是以常数为单位立即转移，就像

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

是快速的，单运算的，超标量的，而变量的移位，如

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

是一个微编码操作，需要7-11周期执行，而整个管道的其余部分则停止运行。。

我想做的是找出哪个非微编码整数PPC操作，斯劳解码到哪个，然后单独发出它们。这将无助于sraw本身的延迟--它将把一个op替换为6个操作--但是在这六个op之间，我可以双重地向其他执行单元分派一些工作，并获得净收益。

我似乎在任何地方都找不到μ操作系统sraw解码的内容--有人知道我如何用一个常数移位序列和基本整数操作来替换变量位移位吗？( for循环或开关或任何包含分支的分支都无法工作，因为分支惩罚甚至大于微代码惩罚，甚至对于预测正确的分支也是如此。)

这不需要在程序集中回答；我希望学习算法，而不是特定的代码，所以用C或高级语言甚至伪代码来回答是非常有帮助的。

编辑：我应该添加几个说明：

1. 我一点也不担心可移植性
2. PPC有一个条件移动，所以我们可以假设一个无分支的内在函数的存在。 int isel(a，b，c) {返回一个>= 0？B: c；} (如果你写出一个三元的，做同样的事情，我就会明白你的意思)
3. 整数乘法也是微编码的，甚至比sraw慢。:-(
4. 在Xenon上，一个预测分支的延迟是8个周期，所以即使一个周期，它也与微编码指令一样昂贵。跳转到指针(任何间接分支或函数指针)是一个被保证的错误预测，一个24周期的失速.

Answer 1

给你..。

我也决定尝试这些，因为Mike声称它将比在他的CellPerformance站点他建议避免间接转移。上使用CELL/PS3微编码转换更快。然而，在我的所有测试中，使用微编码版本不仅比完全通用的无分支替换间接移位更快，而且代码所需的内存更少(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()代码。

// 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);

Answer 2

这个怎么样：

if (y & 16) x <<= 16;
if (y & 8) x <<= 8;
if (y & 4) x <<= 4;
if (y & 2) x <<= 2;
if (y & 1) x <<= 1;

可能还需要更长的时间才能执行，但如果您有其他代码要执行，则更容易交织。

Answer 3

这个伤了我的头。我现在已经放弃了六个想法。所有这些人都利用了这样一种观念，即向自身添加一个东西会使左1移动，对结果做相同的操作会左移4，依此类推。如果您保留shift的所有部分结果( 0、1、2、4、8和16 )，那么通过测试shift变量的0到4位，您可以得到初始移位。现在再做一次，对shift变量中的每1位执行一次。坦率地说，你最好派你的处理器出去喝咖啡。

我需要真正帮助的地方是汉克·沃伦( Hank )的http://www.hackersdelight.org/ (这是这个答案唯一有用的部分)。