1.前言
if else和swith case是两种常用的分支选择结构,从C语言的角度来看,代码是顺序执行的,很难判断两者的效率孰高孰低。可以确定的是,swith语句只能处理整形变量,而if else语句可以处理更复杂的条件分支。当条件变量为单一的整形值的判断时,两者是可以互相替代的,如:
void judge_var_ifelse(int var)
{
ret = -1;
if(0 == var)
{
ret = 1;
}
else if(1 == var)
{
ret = 6;
}
else if(2 == var)
{
ret = 3;
}
else
{
ret = 2;
}
return ret;
}
void judge_var_switch(int var)
{
ret = -1;
switch(var)
{
case 0:
ret = 1;
break;
case 1:
ret = 6;
break;
case 2:
ret = 3;
break;
default:
ret = 2;
break;
}
return ret;
}
函数judge_var_ifelse和judge_var_swith所实现的功能是一样的,且从顺序执行的角度来看,两者的效率看似是一样的。if else和swith case两种分支结构大量应用于代码的逻辑处理中,CPU的指令集对其是否有相应的优化呢?要探讨其效率问题,还是得从汇编层来分析。本文在ARM V7架构的硬件环境下,结合相关的ARM指令,探讨下if else和swith case两种逻辑处理方式的效率问题。
2 相关ARM指令
2.1 条件转移与标志位
ARM V7的程序状态寄存器在其内部分为应用程序 PSR(APSR)、 中断号 PSR(IPSR)和 执行 PSR(EPSR),如表1所示:
表1 程序状态寄存器
bit | 31 | 30 | 29 | 28 | 27 | 26:25 | 24 | 23:20 | 19:16 | 15:10 | 9 | 8 | 7 | 6 | 5 | 4:0 |
xPSR | N | Z | C | V | Q | ICI/IT | T | ICI/IT | Exception Number |
其中,bit31~bit27为应用程序状态寄存器(APSR)的相关标志位,有4个与条件转移指令相关:
① N(negtive): 负数标志,即上一次操作的结果是一个负数,N =操作结果的MSB;
② Z(zero): 零标志,即上一次操作(包括数据操作指令、比较指令、测试指令等)的结果为0时置位;
③ C(carry): 进位/错位标志,即上一次操作导致了进位或错位,常用于无符号数的处理;
④ V(overflow): 溢出标志,常用于有符号数的处理,如两个正数相加结果的MSB为1(为负数),则V置位。
以上4个标志位可以组合成15种跳转判据,见表2:
表2 跳转条件及相关标志位关系
条件码 | 条件说明 | 标志位 |
EQ | 相等(equal) | Z == 1 |
NE | 不等(not equal) | Z == 0 |
CS/HS | 进位(carry set)/无符号数大于等于(higer or same) | C == 1 |
CC/LO | 未进位(carry clear)/无符号数小于(lower) | C == 0 |
MI | 负数(minus) | N == 1 |
PL | 非负数(plus) | N == 0 |
VS | 溢出(overfow set) | V == 1 |
VC | 未溢出(overflow clear) | V== 0 |
HI | 无符号数大于(higer) | C == 1 && Z == 0 |
LS | 无符号数小于等于(lower or same) | C == 0 || Z == 1 |
GE | 有符号数大于等于(greater or equal) | N == V |
LT | 有符号数小于(less than) | N != V |
GT | 有符号数大于(greater than) | Z == 0 && N == V |
LE | 有符号数小于等于(less or eqaul) | Z == 1 && N == V |
AL/NV | always/never | -- |
表2中的条件码可以作为无条件转移指令(B)的后缀,形成条件转移指令,例如:
BEQ label; //相等时转移到label(Z == 1)
类似地,作为MOV后缀指令的后缀:
MOVGT R2, R0; //上一次操作结果为大于时,将R0的数据传送给R2;
2.2 IF-THEN(IT,if-then condition instruction)指令
2.2.1 语法格式
下面给出IT指令的使用格式:
IT <condition> ;
ITx <condition> ;
ITxy <condition> ;
ITxyz <condition> ;
其中,x,y,z可取"T"或"E", <condition>则是表2中依赖于各标志位的条件码(AL/NV)除外。IT指令至少包含一个"T"(对应if语句),随后可以最多再支持3个"T"或"E",且对"T"和"E"的顺序没有要求。也就是说,IT指令块最大支持4条指令,汇编示例1中ITE对应的则是ITx,且<condition>为EQ,if 和else分支各对应一条条件MOV指令,且"T"和"E"对应的指令语句使用的条件后缀必须相反,如示例1中,MOVEQ(相等则寄存器赋值)和MOVNE(不相等则寄存器赋值)。此外,在IT块中不能再使用IT指令,即后继的四条指令中不允许再使用IT指令。
同样不可用的还有如下指令:
- 条件跳转
- CBZ 和 CBNZ
- TBB 和 TBH
- CPS、CPSID 和 CPSIE
- SETEND。
另外,如果<condition>为AL,则意味着整个IT指令块为无条件执行的,对应的x,y,z可省略,或为"T",但不可为"E"。
2.2.2 示例
IT指令专为三目运算符或简单的两分支if语句量身打造,比如下面代码:
int ret = 0, var = 0;
/*三目运算符*/
ret = (0 == var)? 1 : 2;
/*两分支if语句*/
if(0 == var)
{
ret = 1;
}
else
{
ret = 2;
}
假设在汇编层,R0中存放的是var变量,R1中存放的是立即数0,R2对应的是ret变量,则对应有如下伪代码:
if(R0 == R1)
{
R2 = 1; /* 分支处理语句 ① */
}
else
{
R2 = 2; /* 分支处理语句 ② */
}
该伪代码中,if和else分支加起来共有①②两条处理语句,这两条语句则对应了两条指令,对应的汇编层代码则为(该示例仅用来帮助理解,通常立即数1和2会存放在一个内存地址中,通过str指令来进行赋值):
汇编示例1
CMP R0, R1 ; /* 比较是否相等*/
ITE EQ ; /* 通过IT指令,设置分支结构,if中有一条指令(对应T),else中有一条(对应E)*/
MOVEQ R2, R3 ; /* THEN R2 = 1, 假设R3中存放的是立即数1 */
MOVNE R2, R4 ; /* ELSE R2 = 2, 假设R4中存放的是立即数2 */
下面引用M3权威指南中一个例子,其使用的是ITxyz(x = T, y = E, z = E):
/* 伪代码*/
if(R0 == R1)
{
R3 = R4 + R5;
R3 = R3/2;
}
else
{
R3 = R6 + R7;
R3 = R3/2;
}
/* 汇编层代码*/
CMP R0, R1 ; /* 比较是否相等*/
ITTEE EQ ; /* TT对应2条if处理指令,EE对应2条else处理指令)*/
ADDEQ R3, R4, R5 ; /* THEN EQ条件满足时,相加处理 */
ASREQ R3, R3, #1 ; /* THEN EQ条件满足时,算数右移 */
ADDNE R3, R6, R7 ; /* ELSE EQ条件不满足时,相加处理 */
ASRNE R3, R3, #1 ; /* ELSE EQ条件不满足时,算数右移 */
类似地,也可以给出以下示例:
/* 伪代码*/
if(R0 == R1)
{
R3 = R4 + R5;
}
else
{
R3 = R3/2;
R3 = R6 + R7;
R3 = R3/2;
}
/* 汇编层代码*/
CMP R0, R1 ; /* 比较是否相等*/
ITEEE EQ ; /* T对应1条if处理指令,EEE对应3条else处理指令)*/
ADDEQ R3, R4, R5 ; /* THEN EQ条件满足时,相加处理 */
ASRNE R3, R3, #1 ; /* ELSE EQ条件不满足时,算数右移 */
ADDNE R3, R6, R7 ; /* ELSE EQ条件不满足时,相加处理 */
ASRNE R3, R3, #1 ; /* ELSE EQ条件不满足时,算数右移 */
那么,IT指令的优化体现在什么地方呢?主要有以下几个方面:
① IT指令使能了指令的条件执行方式,使得CPU不再预取不满足条件的指令(只有两个条件分支,只取满足条件的分支语句指令);
② 取代了条件转移指令,避免了执行流转移时对流水线的清洗和重新指令预取的开销(有点类似内联函数替代函数调用的感觉)。
显然,IT指令对if else分支语句的优化是有局限性的,只适用于两分支语句。下面展示下对swith语句相关的优化支持指令。
2.3 TBB和TBH(table branch byte and table branch halfword)指令
2.3.1 语法格式
TBB[Rn, Rm]
TBH[Rn, Rm, LSL #1]
其中:
①Rn是存放分支偏移表的首地址的寄存器,这个表可以理解为一个线性数组,即Rn是数组首地址;
②Rm是存放查表表的索引的寄存器,可以理解为单字节数组的下标索引(index),数组中的元素记录了偏移量;
③查找表中记录的是偏移值,又由于Thumb-2指令至少是按半字(half word,16bit)对齐的,所以可以理解为偏移量的单位是两字节;
对于TBB来说,可以将查找表看成一个单字节数组,以C语言的语法来描述,则索引对应的偏移量(数组元素)值是branchtablevalue = *(unsigned char *)(Rn + Rm),也就是Rn[Rm],对应跳转的字节数为branchtablevalue *2;
对于TBH来说,查找表中的元素是双字节的,以C语言的语法来描述,则索引对应的元素值branchtablevalue = *(unsigned short *)(Rn + Rm*2),对应跳转的字节数为branchtablevalue *2;
简单来说,这两条指令都是通过查表来获得一个跳转偏移量,具体是做什么用的呢?首先,这个跳转偏移量指的是PC向前跳转的分支偏移量,即该指令的作用是直接改变PC的值,控制分支跳转:
PC += PC + branchtablevalue *2;
特别地,如果Rn为PC,即TBB(PC, Rm),由于指令流水线的原因,PC的值为当前地址+4,即查找表的首地址为PC+ 4,也就是TBB或TBH指令后的字节位置。
2.3.2 示例
以下代码主要是判断各月份的日期是否合法,如1月32日不合法,1月31日合法:
/*C语言代码*/
bool ret = true;
switch(month)
{
case 1:
case 3:
case 5:
case 7:
case 8:
case 10:
case 12:
ret = ((day) >= 1) && ((day) <=31);
break;
case 4:
case 6:
case 9:
case 11:
ret = ((day) >= 1) && ((day) <=30);
break;
case 2:
ret = M_LEAP_DAY_IS_VALID((year), (month), (day));
break;
default:
ret = false;
break;
}
/*对应的反汇编代码*/
34301e0e: 784b ldrb r3, [r1, #1] /* ① r3 = month */
34301e10: 3b01 subs r3, #1 /* ② r3 -= 1 */
34301e12: 2b0b cmp r3, #11 /* ③ 判断month是否大于12-1 */
34301e14: d83a bhi.n 34301e8c /* ④ 大于12-1则跳转到地址0x34301e8c处执行 */
34301e16: e8df f003 tbb [pc, r3] /* ⑤ TBB指令,查表索引为month-1 */
34301e1a: 1606 .short 0x1606 /* ⑥ 查找表起始地址 0x34301e1a */
34301e1c: 0e060e06 .word 0x0e060e06
34301e20: 060e0606 .word 0x060e0606
34301e24: 060e .short 0x060e /* ⑦ 查找表结束地址*/
34301e26: 7888 ldrb r0, [r1, #2] /* ⑧ month = 1, 0x34301e26 = 0x34301e1a + 0x06*2 */
34301e28: 3801 subs r0, #1
34301e2a: b2c0 uxtb r0, r0
34301e2c: 281e cmp r0, #30
34301e2e: bf8c ite hi
34301e30: 2000 movhi r0, #0
34301e32: 2001 movls r0, #1
34301e34: 4770 bx lr
34301e36: 7888 ldrb r0, [r1, #2] /* ⑨ month = 4, 0x34301e36 = 0x34301e1a + 0x0e*2 */
34301e38: 3801 subs r0, #1
34301e3a: b2c0 uxtb r0, r0
34301e3c: 281d cmp r0, #29
34301e3e: bf8c ite hi
34301e40: 2000 movhi r0, #0
34301e42: 2001 movls r0, #1
34301e44: 4770 bx lr
34301e46: 780b ldrb r3, [r1, #0] /* ⑩ month = 2, 0x34301e46 = 0x34301e1a + 0x16*2 */
34301e48: f013 0f03 tst.w r3, #3
34301e4c: d109 bne.n 34301e62
34301e4e: 4a11 ldr r2, [pc, #68]
34301e50: fba2 0203 umull r0, r2, r2, r3
34301e54: 0952 lsrs r2, r2, #5
34301e56: 2064 movs r0, #100 ; 0x64
34301e58: fb00 3212 mls r2, r0, r2, r3
34301e5c: f012 0fff tst.w r2, #255 ; 0xff
34301e60: d100 bne.n 34301e64
34301e62: b93b cbnz r3, 34301e74
34301e64: 7888 ldrb r0, [r1, #2]
34301e66: 3801 subs r0, #1
34301e68: b2c0 uxtb r0, r0
34301e6a: 281c cmp r0, #28
34301e6c: bf8c ite hi
34301e6e: 2000 movhi r0, #0
34301e70: 2001 movls r0, #1
34301e72: 4770 bx lr
34301e74: 7888 ldrb r0, [r1, #2]
34301e76: 3801 subs r0, #1
34301e78: b2c0 uxtb r0, r0
34301e7a: 281b cmp r0, #27
34301e7c: bf8c ite hi
34301e7e: 2000 movhi r0, #0
34301e80: 2001 movls r0, #1
...
34301e8c: 2000 movs r0, #0
其中,TBB指令的Rm为month-1,即0~11,而对应查找表的值如下(查找表中的数据为小端):
month | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
Rm | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
branchtablevalue *2 | 0x06 | 0x16 | 0x06 | 0x0e | 0x06 | 0x0e | 0x06 | 0x06 | 0x0e | 0x06 | 0x0e | 0x06 |
显然,月天数为31天的月份查表得到的跳转值是一致的,同样月份为30天的月份也是如此,二月份最为特殊,跳转到了单独的处理地址。跳转的地址见上述注释,具体的汇编处理这里就不展开了。
从上述例子可以发现,查找表中的偏移值还是很难计算和维护的,通常都是由编译器来生成,很少由人工来维护。总的来看,TBB指令在汇编层最终构建了一个类似哈希表的数据结构,主要用于swith语句的优化,整个过程不再是按顺序逐一比较输入值与各case是否相等,再跳转到响应的代码段,而是PC可以根据输入值查表直接跳转到满足条件的代码段执行。
此外,TBB和TBH指令也存在一定的局限性。可以看出,上述例子中swith的条件输入值month的范围为1~12,其取值是连续的,整体范围较小。试想,如果输入的条件值是稀疏离散化的,而且范围特别大,比如有1,15,5689, 14567等值,编译器就不会选用TBB或TBH指令来进行优化了。文章来源:https://www.toymoban.com/news/detail-842258.html
3.总结
回到最开始的问题上,if else 和 swith两种语句从C语言角度来看都是顺序执行的,其效率最终还是看汇编层的优化程度。对于两分支语句,if else语句效率肯定是没问题的;对满足swith使用条件的多分支语句,且输入的条件变量是连续紧凑的整数值时,应优先使用swith语句。文章来源地址https://www.toymoban.com/news/detail-842258.html
到了这里,关于从ARM V7汇编层分析 if else和swith 语句效率的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!