本帖最后由 吾要单片机 于 2017-9-26 16:39 编辑
第三项专利：一种处理C语言SWITCH/CASE语句的方法
技术领域
本发明属于计算机领域，具体涉及一种处理C语言SWITCH/CASE语句的方法，利用这一方法设计出专门处理C语言SWITCH/CASE语句的计算机指令，使得Ｃ编译器能利用这些指令编译C语言SWITCH/CASE语句时产生简洁高效的代码，显著提高计算机的执行速度。
背景技术
C语言SWITCH/CASE语句是大家经常用到的语句，从字面上看程序逻辑清晰，结构一目了然，很受程序员欢迎，但是基于现有的指令集，Ｃ编译器编译C语言SWITCH/CASE语句成汇编指令时相当费劲。目前Ｃ编译器处理C语言SWITCH/CASE语句时通常使用两种方法，它们是：列表驱动法和逐项查找法。其中列表驱动法是在程序存贮器中建立一个常数的数组,该数组是所有CASE常数项所对应的跳转矢量的集合，所以该数组被称为CASE跳转矢量表，某个CASE常数项对应的跳转矢量在该表格的位置等于该CASE常数项与最小CASE常数项的差值，然后使用SWITCH的表达式的值减去最小CASE常数项的差值去索引所述的CASE跳转矢量表，从而得到跳转的目标，这种方法处理速度很快，也是Ｃ编译器优先使用的方法；而逐项查找法是使用SWITCH的表达式的值和CASE常数项逐个比较，如果有相等，则跳转到该CASE常数项所对应的地址，也就是说Ｃ编译器使用if/else的方法从上往下逐个比较,从而找到跳转的目标, 这就造成了越靠后的case项查找的时间就越长，所以这种方法处理速度很慢。
虽然列表驱动法具有快速的优点，但是那是用空间换取时间。该方法的缺点是CASE跳转矢量表的规模往往很大，其大小等于CASE常数项的最大值与最小值的差值+1，在实际应用中， CASE常数项的离散性往往很大，没有规律可循，那么CASE跳转矢量表就有很多空白项，这会浪费很多程序空间。如果浪费程序的空间过多，Ｃ编译器只好使用逐项查找法进行编译。另外，如果case项比较少，Ｃ编译器也会使用逐项查找法进行编译。
例如下面这段C语言代码，如果使用列表驱动法进行编译，则CASE跳转矢量表长达247项（246=0xf7-0x01+1）,而实际有用的case项只有4个(0x01,0x22,0x4c,0xf7)，显然浪费的程序空间太多了，所以Ｃ编译器就会使用逐项查找法进行编译。
switch (test){
case 0x01: c=a&b;break;
case 0x22: c=a|b;break;
case 0x4c: c=a+b;break;
case 0xf7: c=a-b;break;
default:break;
}
汇编代码如下：（逐项查找法，使用ARM指令集）
;switch (test){
0x080002ec LDR r0, [pc, #92]
0x080002ee LDRB r0, [r0, #0x00]; r0 <= test
0x080002f0 CMP r0, #0x01
0x080002f2 BEQ 0x08000302；if(test == 0x01) than jump to 0x08000302
0x080002f4 CMP r0, #0x22
0x080002f6 BEQ 0x08000312；if(test == 0x22) than jump to 0x08000312
0x080002f8 CMP r0, #0x4c
0x080002fa BEQ 0x08000322；if(test == 0x4c) than jump to 0x08000322
0x080002fc CMP r0, #0xf7
0x080002fe BEQ 0x08000332 ；if(test == 0xf7) than jump to 0x08000332
…
从上面的汇编代码可以看出，在使用逐项查找法时，越靠后的case项查找的时间就越长，因此改善逐项查找法的执行效率具有重要意义。
观察C程序中的SWITCH/CASE语句不难发现，在绝大多数SWITCH/CASE语句中：SWITCH表达式的值的字长为8位或16位，CASE常数项所对应的跳转都是小范围相对跳转，而且都是往前跳转。
发明内容
本发明提供一种处理C语言SWITCH/CASE语句的方法，利用这一方法，本发明设计出专门和用于处理C语言SWITCH/CASE语句的计算机指令，使得Ｃ编译器利用这些指令来编译C语言SWITCH/CASE语句时，能够产生简洁高效的代码，以提高计算机的执行速度。
一种处理C语言SWITCH/CASE语句的方法，该方法内容包括如下内容：
在现有的指令系统中增加3条指令,它们是字节型查找指令、半字型查找指令、散转指令；
所述的字节型查找指令包含目的寄存器、第一源寄存器和第二源操作数；其中，所述字节型查找指令的目的寄存器是通用寄存器或PSR（即程序状态寄存器），所述字节型查找指令的第一源寄存器是通用寄存器，所述字节型查找指令的第二源操作数是通用寄存器或立即数；如果所述的字节型查找指令的助记符为CASEB，那么该字节型查找指令的汇编格式是：CASEB Rd，Rs，Rt或者CASEB Rd，Rs，#imm ，其中Rd是目的寄存器，Rs是第一源寄存器，Rt是第二源寄存器，#imm是立即数；对于指令CASEB Rd，Rs，Rt来说：如果Rt是32位通用寄存器，那么Rt里面装载的是4个字长为字节的常数，如果Rt是64位通用寄存器，那么Rt里面装载的是8个字长为字节的常数；对于指令CASEB Rd，Rs，#imm来说：如果#imm是32位立即数，那么该#imm是由4个字长为字节的常数组成，如果#imm是16位立即数，那么该#imm是由2个字长为字节的常数组成；
所述的字节型查找指令的处理内容是：将字节型查找指令的第一源寄存器（Rs）中的第0字节同时分别与字节型查找指令的第二源操作数（Rt或#imm）中的所有字长为字节的常数进行比较，如果在这些比较运算中有一个运算结果为相等，那么置相等标记z为1，否则置相等标记z为0，并且按照一定的优先级顺序来选择其中一个运算结果为相等的、参与该比较运算的常数处于字节型查找指令的第二源操作数（Rs或#imm）中的位置编号位置序号n，再把该位置编号位置序号n以及相等标记z保存到字节型查找指令的目的寄存器Rd；
所述的半字型查找指令包含目的寄存器、第一源寄存器和第二源操作数；其中，所述半字型查找指令的目的寄存器是通用寄存器或PSR（即程序状态寄存器），所述半字型查找指令的第一源寄存器是通用寄存器，所述半字型查找指令的第二源操作数是通用寄存器或立即数；如果所述的半字型查找指令的助记符为CASEH，那么字节型查找指令的汇编格式是那么半字型查找指令的汇编格式是：CASEH Rd，Rs，Rt，或者CASEH Rd，Rs，#imm ，其中Rd是目的寄存器，Rs是第一源寄存器，Rt是第二源寄存器，#imm是立即数；对于指令CASEH Rd，Rs，Rt来说：如果Rt是32位通用寄存器，那么Rt里面装载的是2个字长为半字的常数，如果Rt是64位通用寄存器，那么Rt里面装载的是4个字长为半字的常数；对于指令CASEH Rd，Rs，#imm来说：如果#imm是32位立即数，那么该#imm是由2个字长为半字的常数组成；
所述的半字型查找指令的处理内容是：将半字型查找指令的第一源寄存器（Rs）中的第0半字同时分别与半字型查找指令的第二源操作数（Rt或#imm）中的所有字长为半字的常数进行比较，如果在这些比较运算中有一个运算结果为相等，那么置相等标记z为1，否则置相等标记z为0，并且按照一定的优先级顺序来选择其中一个运算结果为相等的、参与该比较运算的常数处于半字型查找指令的第二源操作数（Rs或#imm）中的位置编号位置序号n，再把该位置编号位置序号n以及相等标记z保存到半字型查找指令的目的寄存器Rd；
所述的散转指令包含第一源寄存器和第二源操作数；其中，所述散转指令的第一源寄存器是通用寄存器或PSR（即程序状态寄存器），该散转指令的第一源寄存器包含使能位z和索引值n；所述散转指令的第二源操作数是通用寄存器或立即数；如果所述的散转指令的助记符为SWITCH，那么该散转指令的汇编格式是：SWITCH Rs，Rt 或SWITCH Rs， #imm，其中Rs是第一源寄存器，Rt是第二源寄存器，#imm是立即数；如果Rt是32位通用寄存器，那么Rt里面装载的是4个字长为字节的常数；如果Rt是64位通用寄存器，那么Rt里面装载的是8个字长为字节的常数；如果#imm是32位立即数，那么该#imm是由4个字长为字节的常数组成，如果#imm是16位立即数，那么该#imm是由2个字长为字节的常数组成；
所述的散转指令的处理内容是：如果散转指令的Rs中的能使位z为真，那么使用散转指令的Rs中的索引值n选择第二源操作数（Rt或#imm）中的一个字长为字节的常数作为跳转矢量（该跳转矢量是无符号数），然后用该跳转矢量与当前的PC值相加，相加的结果就是跳转的目标地址，从而完成跳转；如果散转指令的Rs中的能使位z为假，则顺序执行；
另外还规定设定：散转指令的第一源寄存器中的能使位z是对应于字节型查找指令和半字型查找指令的目的寄存器中的相等标记z，而散转指令的第一源寄存器中的索引值n是对应于字节型查找指令和半字型查找指令的目的寄存器中的位置编号位置序号n，这样做就使得字节型查找指令和半字型查找指令的执行结果值直接被散转指令使用。
在编译C语言SWITCH/CASE语句时，采用如下编译步骤：
第一步是根据C语言SWITCH表达式的值的字长来选择字节型查找指令或半字型查找指令，查找相等的CASE常数项，具体是：
如果C语言SWITCH表达式的值的字长为8位，那么CASE常数项的字长也是8位，所以要使用字节型查找指令（CASEB Rd，Rs，Rt或者CASEB Rd，Rs，#imm）来查找相等的CASE常数项；如果C语言SWITCH表达式的值的字长为16位，那么CASE常数项的字长也是16位，所以要使用半字型查找指令（CASEH Rd，Rs，Rt或者CASEH Rd，Rs，#imm）来查找相等的CASE常数项。查找的方法是：将若干个待查找的CASE常数项按照一定的顺序填满第二源操作数（Rt或#imm）和把SWITCH表达式的值装入源寄存器（Rs）中，执行字节型查找指令或半字型查找指令后，在其目的寄存器（Rd）就得到相等标记z和位置编号位置序号n。另外，如果待查找的CASE常数项不够填满第二源操作数（Rt或#imm），那么重复使用其中某一个待查找的CASE常数项来填充，直到填满为止。
第二步是使用所述的散转指令根据上述第一步的字节型查找指令或半字型查找指令的结果值来索引跳转矢量，完成分支转移。具体方法是，具体是：
将构成第一步的字节型查找指令或半字型查找指令的第二源操作数（Rt或#imm）的CASE常数项所对应的跳转矢量装入散转指令的第二源操作数（Rt或#imm）中，并且要求各CASE常数项所对应的跳转矢量处于该散转指令的第二源操作数（Rt或#imm）中的位置顺序是与该CASE常数项处于字节型查找指令或半字型查找指令的第二源操作数（Rt或#imm）的位置顺序相同。由于散转指令的第一源寄存器中的能使位z是对应于字节型查找指令和半字型查找指令的目的寄存器中的相等标记z，还有散转指令的第一源寄存器中的索引值n是对应于字节型查找指令和半字型查找指令的目的寄存器中的位置编号位置序号n，所以如果散转指令的第一源寄存器等于字节型查找指令或半字型查找指令的目的寄存器，那么执行散转指令就可以索引到正确的跳转矢量，并根据其能使位z的状态决定跳转还是顺序执行。
使用本发明的方法，同样要处理背景技术所述的C程序：
switch (test){
case 0x01: c=a&b;break； //假设此处的分支地址偏移为0x12
case 0x22: c=a|b;break； //假设此处的分支地址偏移为0x34
case 0x4c: c=a+b;break； //假设此处的分支地址偏移为0x56
case 0xf7: c=a-b;break； //假设此处的分支地址偏移为0x78
default:break;
}
假设test的字长为字节，指令系统可以携带32位立即数，那么使用本发明的方法，其汇编代码如下：
；switch (test){
LDR r0, [pc, #92]
LDRB r0, [r0, #0x00]；r0 <= test
CASEB r1, r0, #0xf74C2201；字节型查找指令（CASEB Rd，Rs，#imm），查找
；相等的CASE常数项，32位立即数#imm是由CASE
；常数项0xf7， 0x4C，0x22，0x01组成，结果存入
；r1
SWITCH r1, #0x78563412 ；散转指令（SWITCH Rs， #imm） ，32位立即数
；#imm是由跳转矢量0x78，0x56，0x34， 0x12组
；成，由r1索引跳转矢量,完成跳转
…
如果test的字长为半字, 指令系统可以携带32位立即数，那么使用本发明的方法，其汇编代码如下：
；switch (test){
LDR r0, [pc, #92]
LDRH r0, [r0, #0x00]; r0 <= test
CASEH r1, r0, #0x00220001；半字型查找指令（CASEH Rd，Rs，#imm），查找
；相等的CASE常数项，32位立即数#imm是由CASE
；常数项0x0022，0x0001组成，结果存入r1
SWITCH r1, #0x00003412 ；散转指令（SWITCH Rs， #imm） ，32位立即数
；#imm是由跳转矢量0x00，0x00，0x34，0x12组成，
；由r1索引跳转矢量,完成跳转
CASEH r1, r0, #0x00f7004c；半字型查找指令（CASEH Rd，Rs，#imm），查找
；相等的CASE常数项，32位立即数#imm是由CASE
；常数项0x00f7，0x004c组成，结果存入r1
SWITCH r1, #0x00007856 ；散转指令（SWITCH Rs， #imm） ，32位立即数
；#imm是由跳转矢量0x00，0x00，0x78，0x56组成，
；由r1索引跳转矢量,完成跳转
…
从以上的汇编代码可以看到，由CASE常数项构成的字节型查找指令或半字型查找指令的第二源操作数（通用寄存器或立即数）的位置顺序是与由该CASE常数项所对应的跳转矢量所构成的散转指令的第二源操作数（通用寄存器或立即数）的位置顺序完全相同。
对比处理背景技术所述的汇编代码不难发现，使用本发明方法的指令，其汇编代码非常简短，能够显著提高计算机的执行效率。
|
楼主
标题置顶
标题高亮
