n是负数,正数还是零？返回1,2或4

Question

我正在构建一个PowerPC解释器,它运行得很好.在Power架构中,条件寄存器CR0(x86上的EFLAGS)几乎在任何指令上都会更新.它是这样设置的.如果最后一个结果为负,则CR0的值为1,如果最后结果为正,则为2,否则为4.

我的第一个天真的解释方法是:

if (n < 0)
    cr0 = 1
else if (n > 0)
    cr0 = 2;
else
    cr0 = 4;

但是我知道所有这些分支都不是最佳的,每秒运行数百万次.我已经看到了一些有点黑客攻击,但似乎没有任何东西.例如,我发现许多例子将数字转换为-1,0或1,相应地符号为0.但是如何使-1 = 1,1 = 2 = 0？我要求Bit Hackers的帮助......

提前致谢

更新: 首先:谢谢你们,你们一直很棒.我会仔细测试你的所有代码以获得速度,你将成为第一个知道谁是胜利者的代码.

@jalf:关于你的第一个建议,我实际上并没有在每条指令上计算CR0.我宁愿保留一个lastResult变量,当(和如果)以下指令要求标志时,进行比较.三个主要动机让我回到"每次"更新:

1. 在PPC上,您不必像在x86上那样更新CR0(其中ADD总是更改EFLAGS,即使不需要),您有两种ADD,一种更新.如果编译器选择使用更新版本,则意味着它将在某个时刻使用CR0,因此没有必要延迟...
2. 有一个特别痛苦的指令叫做mtcrf,它可以让你随意改变CR0.你甚至可以把它设置为7,没有算术意义......这只会破坏保留"lastResult"变量的可能性.

Answer 1

首先,如果要在(几乎)每条指令之后更新此变量,那么显而易见的建议就是:

别

仅在后续指令需要其值时才更新它.在任何其他时间,更新它是没有意义的.

但无论如何,当我们更新它时,我们想要的是这种行为:

R < 0  => CR0 == 0b001 
R > 0  => CR0 == 0b010
R == 0 => CR0 == 0b100

理想情况下,我们根本不需要分支.这是一种可能的方法:

1. 将CR0设置为该值1.(如果你真的想要速度,请调查是否可以在不从内存中获取常量的情况下完成此操作.即使您必须在其上花费一些指令,也可能是值得的)
2. 如果R> = 0,则左移一位.
3. 如果R == 0,则左移一位

可以转换步骤2和3以消除"if"部分

CR0 <<= (R >= 0);
CR0 <<= (R == 0);

这更快吗？我不知道.与往常一样,当您关注性能时,您需要进行测量,测量和测量.

但是,我可以看到这种方法的一些优点:

1. 我们完全避免分支
2. 我们避免内存加载/存储.
3. 我们依赖的指令(位移和比较)应该具有低延迟,例如,乘法并不总是如此.

缺点是我们在所有三条线之间都有一个依赖链:每条线修改CR0,然后在下一行中使用.这在一定程度上限制了指令级并行性.

为了最小化这个依赖链,我们可以做这样的事情:

CR0 <<= ((R >= 0) + (R == 0));

所以我们只需要在初始化后修改CR0一次.

或者,在一行中做所有事情:

CR0 = 1 << ((R >= 0) + (R == 0));

当然,这个主题有很多可能的变化,所以继续进行实验.

Answer 2

许多答案大概都是"不",像往常一样:)你想要点破解？你会得到的.然后随意使用它,或者不作为,你认为合适的.

您可以将该映射用于-1,0和1(sign),然后执行以下操作:

return 7 & (0x241 >> ((sign(x) + 1) * 4));

这本质上是使用一个小的查找表.

或者"天真的bithack":

int y = ((x >> 31) & 1) | ((-x >> 31) & 2)
return (~(-y >> 31) & 4) | y;

第一行映射x < 0到1,x > 0到2和x == 00.然后第二行映射y == 0到4和y != 0y.

当然,它有一个x = 0x80000000的偷偷摸摸的边缘情况,映射到3.糟糕.好吧,让我们解决一下:

int y = ((x >> 31) & 1) | ((-x >> 31) & 2)
y &= 1 | ~(y << 1);  // remove the 2 if odd
return (~(-y >> 31) & 4) | y;

Answer 3

下面的表达式有点神秘,但并不过分,它看起来是编译器可以很容易地优化的东西:

cr0 = 4 >> ((2 * (n < 0)) + (n > 0));

以下是x86目标的GCC 4.6.1将其编译为-O2:

xor ecx, ecx
mov eax, edx
sar eax, 31
and eax, 2
test    edx, edx
setg    cl
add ecx, eax
mov eax, 4
sar eax, cl

和VC 2010 /Ox看起来非常相似:

xor ecx, ecx
test eax, eax
sets cl
xor edx, edx
test eax, eax
setg dl
mov eax, 4
lea ecx, DWORD PTR [edx+ecx*2]
sar eax, cl

使用if测试的版本编译为使用这些编译器中的任何一个进行跳转的程序集.当然,除非你真正检查输出,否则你永远不会确定任何特定的编译器会对你选择的任何特定代码做什么.我的表达足够神秘,除非它真的是一个性能关键的代码,我仍然可以使用if语句版本.由于您需要经常设置CR0寄存器,我认为值得测量这个表达式是否有帮助.