《代码优化之条件分支预测资料》由会员分享，可在线阅读，更多相关《代码优化之条件分支预测资料（5页珍藏版）》请在金锄头文库上搜索。
1、代码优化之优化条件分支预测 代码优化之优化条件分支预测 关键词:代码优化，条件分支，饱和，MMX，CMOV，掩码 条件分支是编程中经常使用的基本操作，然而在某些时候它确可能带来严重的性能问题。当前的 CPU 都能对条件分支做预测(动用了庞大的晶体管资源)，如果分支预测正确，那么条件指令一般只需要花费一 个 CPU 周期，而如果预测错误，那么将可能花费几十个 CPU 周期。本文将讨论条件分支的一些有效优化方 法。 文章为收集加经验编辑而成的文章，对优化条件分支做了较全面的阐述。文章假定的 CPU 为 x86，示 例代码为 CC+。 A什么是分支? A什么是分支? 处理器中分支预测器设计的本质是在
2、对分支指令行为认识的基础上，提出分支指令的预测机制，从而 减少分支惩罚， 也就是分支预测失败时导致的流水线清空。 一组分支指令组合起来就成为程序的分支行为。 分支是编程语言中的常见结构。分支可以分为条件分支和非条件分支。 条件分支举例: 条件判断: if (a255) a=255; else if (a=64) . /b0,b1=0 改写为: if ( (b0|b1)=64 ) . (请尝试证明其等价性) 3将出现几率高的分支优先处理,从而提高预测准确率 4优化第一次执行的条件分支 3将出现几率高的分支优先处理,从而提高预测准确率 4优化第一次执行的条件分支 当 CPU 第一次执行到一个条件分
3、支的时候，默认的预测分支规则是不跳转的那个分支(也就是紧接着条 件跳转指令之后的那些指令)。 下面的内容主要讨论完全替换掉分支的一些方法; 移除分支意味着代码的性能可以不受输入数据的影 响,并可能能更好的使用 SIMD 类指令。 1使用带符号的移位生成掩码来移除条件分支 下面的内容主要讨论完全替换掉分支的一些方法; 移除分支意味着代码的性能可以不受输入数据的影 响,并可能能更好的使用 SIMD 类指令。 1使用带符号的移位生成掩码来移除条件分支 比如: if (color31); /带符号移位从而生成需要的掩码（负数右移后左位填一） 比如: if (color255) color=255; 改
4、写为: color = (color | (255-color)31) ) 比如: if (a=b) return a; else return b; 改写为: return a + ( (b-a) 移除分支的一个更通用的思路：针对不同类的数据生成不同的掩码数据，然后让原数据和掩码参与运算 得到想要的结果，从而移除分支。 2查表法移除分支 2查表法移除分支 比如: if (color255) color=255; /假设 color 属于-256512 改写为: color=ColorTablecolor; 其中 ColorTable 的建立: _ColorTable512+256+1; Co
5、lorTable= for (i=-256;i=90) /score 属于0100 return A; else if (score=75) return B; else if (score=60) return C; else return D; 改写为: return scTablescore，其中 scTable 应该预先存的值就不用再写了吧:) K使用使用 CMOV 条件传送指令来移除条件分支条件传送指令来移除条件分支 为了避免分支预测错误造成的性能损失，现代 CPU 一般都提供了很多能够避免分支的指令，比如条 件传送、掩码生成、最值等指令。 CMOV 条件传送指令是很多条具体的指令，
6、它们根据条件寄存器的值来决定是否赋值 比如: if (x0) x=-x; 用 CMOV 改写为(汇编): mov edx, eax /假设 x 的值在 eax 寄存器，该指令使 edx=eax neg eax /eax=-eax /该指令的结果将设置条件寄存器的状态 cmovs eax, edx /如果状态为负，将 edx 的值传递给 eax CMOV 指令列表: CMOVA/CMOVNBE CMOVAE/CMOVNB/CMOVNC CMOVB/CMOVC/CMOVNAE CMOVBE/CMOVNA CMOVE/CMOVZ CMOVG/CMOVNLE CMOVGE/CMOVNL CMOVL/C
7、MOVNGE CMOVLE/CMOVNG CMOVNE/CMOVNZ CMOVNO CMOVNP/CMOVPO CMOVNS CMOVO CMOVP/CMOVPE CMOVS x87 浮点 CMOV 指令列表: FCMOVB FCMOVBE FCMOVE FCMOVNB FCMOVNBE FCMOVNE FCMOVNU FCMOVU 3。使用。使用 MMXSSE2 中的饱和指令中的饱和指令 对于颜色的饱和处理，比如: if (color0) color=0; else if (color255) color=255; 所谓饱和运算，就是当运算结果大于一个上限或小于一个下限时，结果就等于上限或是
8、下限。例如： BYTE 运算，最大值是 255，0xF1+0x35 应该是等于 0x26，但由于结果大于 255，那么饱和运算的结果就 是 0xFF。在图像处理里经常有（比如说增加亮度）两种灰度值运算后要判断只是否大于 255 或小于 0，根 据结果再取 255 或 0，又是 if 又是什么的。现在只要一条指令就好了。x86CPU 从奔腾 MMX 开始，提供 了 MMX 指令集(后来的 SSE2 也有类似指令)， 增加了对饱和处理的指令支持， 在图像处理和声音处理中得 到了广泛应用(MMXSSE 之类的 SIMD 指令还能够同时并行执行多路数据，从而加快执行速度)。 MMX：_mm_subs_
9、pu8、_mm_adds_pu8. . SSE：_m128 _mm_max_ss/ps、_m128 _mm_min_ss/ps. . SSE2：_m128d _mm_max_sd/ps、_m128d _mm_min_sd/ps. . _m128i _mm_max_epi16/epi8、_m128i _mm_min_epi16/epi8. . M使用使用 CMP 掩码生成指令来移除条件分支掩码生成指令来移除条件分支 比如: /r = (x y) ? a : b / In: MM0 = a, MM1 = b, MM2 = x, MM3 = y / Out: MM0 = r pcmpgtd mm3,
10、 mm2 /比较 yx,生成掩码 0xFFFFFFFF 或者 0 pand mm0, mm3 /a 或者 0 pandn mm3, mm1 /0 或者 b por mm0, mm3 CMP 指令包括: CMPPS,CMPSS,CMPPD,CMPS,CMPSB,CMPSW,CMPSD PCMPEQB, PCMPEQD, PCMPEQW, PCMPGTB, PCMPGTD, PCMPGTW CMPXCHG,CMPXCHG8B 等 N:使用 MINMAX 指令来移除条件分支 MAXPS,MAXPD,MAXSS,MAXSD,MINPS,MINPD,MINSS,MINSD PMAXSW, PMAXUB, PMINSW, PMINUB 等
