仅使用恒定位移来模拟可变位移？

Question

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

我正在研究的特定PowerPC处理器有一个怪癖,即按常数立即移位,就像

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

是快速的,单操作的,超标量的,而变量的变换,如

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

是一个微编码操作,需要7-11个周期才能执行,而管道的其余部分都停止运行.

我想要做的是弄清楚哪个非微码整数PPC操作sraw解码然后单独发出它们.这对sraw自身的延迟没有帮助- 它将用六个替换一个操作 - 但在这六个操作之间我可以将一些工作双重调度到其他执行单元并获得净增益.

我似乎无法找到μopssraw解码到的任何地方 - 有谁知道如何用一系列常量移位和基本整数运算替换变量位移？(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微码变换更快,他建议避免间接转换.但是,在我的所有测试中,使用微编码版本不仅比间接移位的完全通用无分支替换更快,而且代码(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;

可能需要更长的时间才能执行,但如果您有其他代码,则更容易交错.