`
RednaxelaFX
  • 浏览: 3052518 次
  • 性别: Icon_minigender_1
  • 来自: 海外
社区版块
存档分类
最新评论

[链接] 除法优化与编译时常量参数的函数调用优化

GCC框架算法PHPBBS 
阅读更多
晚上在FV群里说起编译器优化的事情时，汉公找出了几个看起来颇不直观的例子让我猜其意义。我脑子跟不上节奏了，把东西写成代码试了下觉得有问题，然后讨论变得激烈了起来……我决定直接写段简单的代码看看我机上的编译器会如何优化。结果我得到了些一时没料到的结果。仔细想想，以前其实碰到过一模一样的状况。

不过和谐的TX无法提供顺畅的沟通环境（老是丢信息……），汉公说干脆在澄空发个帖：贴一下你们的反汇编结果

汉公：
引用
源码： 
#include <stdio.h>

static unsigned int do_div(unsigned int div)
{
    return div / 7;
}

int main(int argc, char* argv[])
{
    int a = 50;
    // 这里的AAAAA完全是为了在oly里看的清楚
    printf("AAAAAAAAAAAAAAAA %d\n", do_div(a)); 
    return 0;
}


主要看一下div / 7这句话的反汇编是什么。
请按这个格式注明（debug版的不用贴了，肯定是DIV了，如果被强制内联变成直接push 7的就都算了）：

编译器：VC6
反汇编： 
MOV    ECX, DWORD PTR SS:[ESP+4]  ; 参数div
MOV    EAX, 24924925
MUL    ECX
MOV    EAX, ECX
SUB    EAX, EDX
SHR    EAX, 1
ADD    EAX, EDX
SHR    EAX, 2
RETN


最后想听听各位对于除以7为什么编译成这样的看法。
这玩意比较有用，经常能碰到编译器莫名的mov eax, 66666667或者cccccccd什么的。


补充：米粒和汉公用GCC3.4.x编译出来的结果：
-O1：
引用
004012e0 <_do_div>:
  4012e0:	55                   	push   %ebp
  4012e1:	89 e5                	mov    %esp,%ebp
  4012e3:	8b 4d 08             	mov    0x8(%ebp),%ecx
  4012e6:	ba 25 49 92 24       	mov    $0x24924925,%edx
  4012eb:	89 c8                	mov    %ecx,%eax
  4012ed:	f7 e2                	mul    %edx
  4012ef:	89 c8                	mov    %ecx,%eax
  4012f1:	29 d0                	sub    %edx,%eax
  4012f3:	d1 e8                	shr    %eax
  4012f5:	01 c2                	add    %eax,%edx
  4012f7:	89 d0                	mov    %edx,%eax
  4012f9:	c1 e8 02             	shr    $0x2,%eax
  4012fc:	5d                   	pop    %ebp
  4012fd:	c3                   	ret

-O2： 
  4012ff:	b8 07 00 00 00       	mov    $0x7,%eax
  401304:	89 44 24 04          	mov    %eax,0x4(%esp)
  401308:	e8 33 05 00 00       	call   401840 <_printf>


我：
引用
汉公的代码原封不动拿来编译: 
#include <stdio.h>

static unsigned int do_div(unsigned int div)
{
    return div / 7;
}

int main(int argc, char* argv[])
{
    int a = 50;
    // 这里的AAAAA完全是为了在oly里看的清楚
    printf("AAAAAAAAAAAAAAAA %d\n", do_div(a)); 
    return 0;
}


得到: 
00401000  /$  6A 07           push 7
00401002  |.  68 58A14000     push zz.0040A158         ;  ASCII "AAAAAAAAAAAAAAAA %d"
00401007  |.  E8 06000000     call zz.00401012
0040100C  |.  83C4 08         add esp,8
0040100F  |.  33C0            xor eax,eax
00401011  \.  C3              retn

========================================================= 
#include<stdio.h>

void main(int argc, char* argv[]){
    int a=46, b;
    
    printf("XXXXXXXXXXX\n");
    b = divBySeven(a);
    printf("%d", b);
}

int divBySeven(int a) {
    return (a / 7);
}

得到: 
00401000  /$  68 5CA14000     push zz.0040A15C                 ;  ASCII "XXXXXXXXXXX"
00401005  |.  E8 12000000     call zz.0040101C
0040100A  |.  6A 06           push 6
0040100C  |.  68 58A14000     push zz.0040A158                 ;  ASCII "%d"
00401011  |.  E8 06000000     call zz.0040101C
00401016  |.  83C4 0C         add esp,0C
00401019  |.  33C0            xor eax,eax
0040101B  \.  C3              retn

========================================================= 
#include<stdio.h>

void main(int argc, char* argv[]){
    int a=50, b;
    
    printf("XXXXXXXXXXX\n");
    b = divBySeven(a);
    printf("%d", b);
}

int divBySeven(int a) {
    return (a / 7);
}


得到: 
00401000  /$  68 5CA14000     push zz.0040A15C                 ;  ASCII "XXXXXXXXXXX"
00401005  |.  E8 12000000     call zz.0040101C
0040100A  |.  6A 06           push 7
0040100C  |.  68 58A14000     push zz.0040A158                 ;  ASCII "%d"
00401011  |.  E8 06000000     call zz.0040101C
00401016  |.  83C4 0C         add esp,0C
00401019  |.  33C0            xor eax,eax
0040101B  \.  C3              retn

=========================================================
以上结果以VC8编译得到. 
cl /O2 /Ox zz.c


为了避免运算被折叠,用这段代码再编译一次: 
#include<stdio.h>
#include<stdlib.h>

void main(int argc, char* argv[]){
    int a, b;
    
    a = atoi(argv[1]);
    printf("XXXXXXXXXXX\n");
    b = divBySeven(a);
    printf("%d", b);
}

int divBySeven(int a) {
    return (a / 7);
}

得到: 
00401000  /$  8B4424 08       mov eax,dword ptr ss:[esp+8]
00401004  |.  8B48 04         mov ecx,dword ptr ds:[eax+4]
00401007  |.  56              push esi
00401008  |.  51              push ecx
00401009  |.  E8 07010000     call zz.00401115
0040100E  |.  68 5CA14000     push zz.0040A15C             ;  ASCII "XXXXXXXXXXX"
00401013  |.  8BF0            mov esi,eax
00401015  |.  E8 25000000     call zz.0040103F
0040101A  |.  B8 93244992     mov eax,92492493
0040101F  |.  F7EE            imul esi
00401021  |.  03D6            add edx,esi
00401023  |.  C1FA 02         sar edx,2
00401026  |.  8BC2            mov eax,edx
00401028  |.  C1E8 1F         shr eax,1F
0040102B  |.  03C2            add eax,edx
0040102D  |.  50              push eax
0040102E  |.  68 58A14000     push zz.0040A158             ;  ASCII "%d"
00401033  |.  E8 07000000     call zz.0040103F
00401038  |.  83C4 10         add esp,10
0040103B  |.  33C0            xor eax,eax
0040103D  |.  5E              pop esi
0040103E  \.  C3              retn

同样是在VC8上,开了/O2与/Ox 

#include<stdio.h>
#include<stdlib.h>

void main(int argc, char* argv[]){
    unsigned int a, b;
    
    a = atoi(argv[1]);
    printf("XXXXXXXXXXX\n");
    b = divBySeven(a);
    printf("%d", b);
}

unsigned int divBySeven(unsigned int a) {
    return (a / 7);
}

得到: 
00401000  /$  8B4424 08       mov eax,dword ptr ss:[esp+8]
00401004  |.  8B48 04         mov ecx,dword ptr ds:[eax+4]
00401007  |.  56              push esi
00401008  |.  51              push ecx
00401009  |.  E8 04010000     call zz.00401112
0040100E  |.  68 5CA14000     push zz.0040A15C             ;  ASCII "XXXXXXXXXXX"
00401013  |.  8BF0            mov esi,eax
00401015  |.  E8 22000000     call zz.0040103C
0040101A  |.  B8 25499224     mov eax,24924925
0040101F  |.  F7E6            mul esi
00401021  |.  2BF2            sub esi,edx
00401023  |.  D1EE            shr esi,1
00401025  |.  03F2            add esi,edx
00401027  |.  C1EE 02         shr esi,2
0040102A  |.  56              push esi
0040102B  |.  68 58A14000     push zz.0040A158             ;  ASCII "%d"
00401030  |.  E8 07000000     call zz.0040103C
00401035  |.  83C4 10         add esp,10
00401038  |.  33C0            xor eax,eax
0040103A  |.  5E              pop esi
0040103B  \.  C3              retn

这个跟汉公在开头贴的那个差不多.常量的不同确实是来自unsigned.
=====================================================
另外,如果不开优化的话, 
#include<stdio.h>

void main(int argc, char* argv[]){
    int a=46, b;
    
    printf("XXXXXXXXXXX\n");
    b = divBySeven(a);
    printf("%d", b);
}

int divBySeven(int a) {
    return (a / 7);
}

得到: 
00401000  /$  55              push ebp
00401001  |.  8BEC            mov ebp,esp
00401003  |.  83EC 08         sub esp,8
00401006  |.  C745 FC 2E00000>mov dword ptr ss:[ebp-4],2E
0040100D  |.  68 00C04000     push zz.0040C000             ;  ASCII "XXXXXXXXXXX"
00401012  |.  E8 39000000     call zz.00401050
00401017  |.  83C4 04         add esp,4
0040101A  |.  8B45 FC         mov eax,dword ptr ss:[ebp-4]
0040101D  |.  50              push eax                     ; /Arg1
0040101E  |.  E8 1D000000     call zz.00401040        ; \zz.00401040
00401023  |.  83C4 04         add esp,4
00401026  |.  8945 F8         mov dword ptr ss:[ebp-8],eax
00401029  |.  8B4D F8         mov ecx,dword ptr ss:[ebp-8]
0040102C  |.  51              push ecx
0040102D  |.  68 10C04000     push zz.0040C010             ;  ASCII "%d"
00401032  |.  E8 19000000     call zz.00401050
00401037  |.  83C4 08         add esp,8
0040103A  |.  33C0            xor eax,eax
0040103C  |.  8BE5            mov esp,ebp
0040103E  |.  5D              pop ebp
0040103F  \.  C3              retn
00401040  /$  55              push ebp
00401041  |.  8BEC            mov ebp,esp
00401043  |.  8B45 08         mov eax,dword ptr ss:[ebp+8]
00401046  |.  99              cdq
00401047  |.  B9 07000000     mov ecx,7
0040104C  |.  F7F9            idiv ecx
0040104E  |.  5D              pop ebp
0040104F  \.  C3              retn

直接用了idiv。


VC6、VC8、GCC3.4等编译器在打开O2开关后基本上都会把上面例子中的常参数函数调用折叠优化掉。汉公的本意是指出利用定点小数来把整型除法转变成乘法的优化，在开了O2开关后却看不到了（被折叠了）。

=============================================================

汉公想说明的是这样的优化： 
mov eax,24924925
mul esi
sub esi,edx
shr esi,1
add esi,edx
shr esi,2
push esi

这里，0x24924925是个定点小数。通过这段代码的运算，得到的是esi /= 7的效果。不直接使用idiv是为了速度的最大化。

引用
汉公 20:50:04
这个东西对解包来说实用价值有2：
1。混淆算法 一个div / 7 比那个乱78遭的东西好看的多 也不容易错
2。当索引项定长，且只有索引段整个长度的时候，要算资源数的时候用这个


这种技巧印象中在Hacker's Delight里有提到。回头得查查看是不是有。没有的话还得想想清楚这代码究竟是怎么跑通的。

引用
汉公 19:08:35 
00416F76  |.  B8 CDCCCCCC   |MOV     EAX, CCCCCCCD
00416F7B  |.  81E1 FFFFFF7F |AND     ECX, 7FFFFFFF
00416F81  |.  F7E1          |MUL     ECX
00416F83  |.  C1EA 05       |SHR     EDX, 5
00416F86  |.  B8 64000000   |MOV     EAX, 64
00416F8B  |.  2BC2          |SUB     EAX, EDX
00416F8D  |>  99            |CDQ
00416F8E  |.  B9 65000000   |MOV     ECX, 65
00416F93  |.  F7F9          |IDIV    ECX


你能猜出这个是干吗的吗

汉公 19:16:18
(ecx & 0x7fffffff) * 0.8 / 5

汉公 19:17:35
用定点小数做除法

汉公 19:17:52
cccccccd实际上是32位的定点小数0.8

汉公 19:18:45
mul完以后 edx里面是整数部分 eax是余数

汉公 19:19:01
不 eax是小数部分

汉公 19:20:05
啊 刚才写错了 实际上他做的是 * 4 / 5 再除32 也就是除以40

汉公 19:20:15
(ecx & 0x7fffffff) / 40

汉公 19:22:07
既然上面的代码都用乘法替换除法了 那么你知道为什么下面的代码又用了DIV这样的慢速除法指令了吗？编译器闹残？

汉公 19:22:40
因为只有在除数是常数的时候 编译器可以做优化 而除数是变量的化 编译器只能用div了


John_He大:
引用
这应该是所谓的倒数乘法，因为IA-32结构中乘法比除法快4~6倍，所以编译器经常用倒数除法处理除数为常数的除法。

除以7的情况： 
MOV    ECX, DWORD PTR SS:[ESP+4]  ; 参数div
MOV    EAX, 24924925
MUL    ECX
MOV    EAX, ECX
SUB    EAX, EDX
SHR    EAX, 1
ADD    EAX, EDX
SHR    EAX, 2

可以这样转化： 
y = ((x - x * sr) / 2 + x * sr) / 4

其中x为被除数，sr = 0x24924925
sr * 7 = 0x100000003 = 0x100000000 + 3
(sr - 1) * 7 = 0xFFFFFFFC = 0x100000000 - 4

可以将x * sr理解成“定点小数乘法”，即小数点位置固定的实数的乘法。从上面的式子不难看出sr为 (1/7) * 0x100000000，使用mul指令后，高位(edx)保存的就是x * (1/7)的整数部分，低位(eax)就是小数部分。因此上面的代码可以看做是div * (1/7)，结果自然就是div / 7。


=============================================================

后来又说起GCC的优化框架的事情。想起以前读过的一篇资料，介绍GCC4系列采用了新的Tree-SSA优化框架，与GCC3.x有很大不同。但是当时读的那篇东西却找不到了。这次学乖了，至少把这次看到的资料的关键字和地址记下来的好。

GCC4里增加的优化框架是由先前的SSA for Trees项目演变而来的。Tree-SSA包括两个主要部分，GENERIC与GIMPLE。


目前进行中的相关领域的项目有：
GIMPLE tuples（tuples.pdf阅读中。总觉得这种把树的形式转换为以tuple表现的思想之前在书上读到过）
Auto-vectorization in GCC（或者http://gcc.gnu.org/wiki/VectorizationTasks）

顺便看到了段有趣的文字。这些错误谁能不犯呢，诶……
The "Deadly Sins" from P. J. Brown'sWriting Interactive Compilers and Interpreters Wiley 1979.
分享到：
| Borland的库的一个小特征？
评论
3 楼 lwwin 2008-01-18  
太好了XD

偶懒人啊
2 楼 RednaxelaFX 2008-01-08  
很简单：别用C做这种级别的优化。这种明显依赖于硬件平台的优化留给编译器做就行。
1 楼 lwwin 2008-01-07  
不知道最后C实现除法优化的代码是怎样的……
结论………………
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    pic18 双字节除法 C语言汇编混合编程

    "pic18 双字节除法 C语言汇编混合编程"这个主题涉及了如何在PIC18系列单片机上，使用C语言调用汇编函数来实现一个高效的16/16位定点除法操作。以下是对这个主题的详细解释： 1. **PIC18单片机**：PIC18是Microchip ...

    编译原理_过程调用—四元式生成

    在编译原理中，过程调用是程序执行中的重要环节，它涉及到函数或方法的调用与返回。在这个过程中，我们需要将源代码转换为可执行的机器语言，这通常通过编译器完成。四元式是一种中间表示形式，用于表示高级语言的...

    VC++编译器选项设定方法[参考].pdf

    * /Gh：启用钩子函数调用，允许钩子函数调用机制以提高性能。 * /Ge：对所有函数强制堆栈检查，强制所有函数进行堆栈检查以提高代码质量。 VC++ 编译器选项设定方法提供了多种选项以满足不同的需求和目标平台，通过...

    已经编译好的NTL 静态链接库

    在实际项目中，你还可以利用NTL进行更复杂的运算，如大整数的乘法、除法、模运算，以及多项式的求解等。 总的来说，这个压缩包提供了一个完整的NTL静态链接库解决方案，包括编译好的库文件、必要的头文件和使用指南...

    求C/C++普通函数的机器代码的源代码程序

    - **运算指令**：如加法、减法、乘法、除法等。 - **控制转移指令**：如跳转、条件跳转、子程序调用等。 - **栈操作**：用于函数调用时保存现场和传递参数。 - **寄存器使用**：不同架构下有特定的寄存器用于存储...

    C语言代码优化 方案

    2. **减少函数调用参数**：减少函数参数的数量可以减少传递参数的开销。 3. **所有函数都应该有原型定义**：提供函数原型可以帮助编译器进行类型检查和优化。 4. **尽可能使用常量**：使用`const`关键字可以告诉...

    ARM汇编和C语言的优化.pdf

    5. **函数调用**： - ARM处理器的前4个整型参数使用寄存器传递，其余通过堆栈。尽量避免超过4个参数，或者将参数组织在结构体中传递。 - 使用`_inline`关键字内联小型且性能关键的函数。 6. **指针别名和局部变量...

    dsp中c代码优化

    - **预编译宏**：使用宏定义进行条件判断和函数调用的优化，减少运行时开销。 - **编译器优化选项**：利用编译器提供的优化选项，如iccavr的Options设置，可以优化代码生成。 5. **代码组织与重构**： - 优化...

    C语言编译错误信息锦集

    当函数调用时参数列表的格式不正确，例如参数数量不符、类型不匹配或者参数之间缺少必要的分隔符时，编译器会抛出此错误。检查并修正参数列表中的语法问题是解决此类错误的关键。 #### Array bounds missing (数组...

    基于ARM系统中C语言程序设计优化.pdf

    2. 减少函数调用开销：函数调用过程中，参数的传递和返回值的操作需要时间和空间，因此合理优化函数设计、使用内联函数和减少不必要的函数调用都能显著提升性能。 3. 循环展开：通过循环展开技术减少循环控制的开销...

    Dll开发例子及静态调用

    1. **定义接口**：创建一个头文件（如`calculator.h`），声明将要在DLL中实现的函数原型，例如加法、减法、乘法和除法的函数声明。 2. **实现DLL**：创建一个C++源文件（如`calculator.cpp`），实现这些函数。在...

    C代码优化方案11条

    函数调用有额外的开销，包括参数传递和返回值计算。如果可能，尝试将函数内的代码内联，或者减少不必要的函数调用。 6. **预编译宏和条件编译** 使用预编译宏和条件编译可以根据目标平台或编译选项优化代码，...

    X:\除法计算器(含代码）.zip

    标签与标题相同，进一步确认了这个压缩包的内容是关于VB除法计算器的源代码。 压缩包内的文件包括： 1. "除法计算器（徐飞制作）.exe"：这是可执行文件，用户可以直接运行这个程序来执行除法运算。VB编译后的应用...

    Kotlin 四则运算 (加、减、乘、除)

    在编程语言中，四则运算（加法、减法、乘法和除法）是基本操作，对于理解和应用计算逻辑至关重要。Kotlin，作为一种现代化的、面向对象的编程语言，被广泛用于Android应用开发，其语法简洁且强大。在Kotlin中进行四...

    authorware外部函数u32.zip

    X-Function允许用户通过编写C或C++代码，并将其编译为动态链接库（DLL）文件，然后在Authorware中作为函数调用。这些DLL函数可以处理Authorware无法直接处理的任务，如数据库操作、网络通信、加密解密等。 2. **32...

    C语言程序优化.pdf

    在表达式优化中，需要注意避免不必要的类型转换，合理使用运算符，比如利用乘法替换除法（如果除数是2的幂），使用位运算替代算术运算，以及减少复杂的数学运算如`pow`函数的使用。 4. 编译器优化选项 文档提到了几...

    C代码优化性能.doc

    例如，计算1到100的和，方法E使用循环，执行了200次加法操作，而方法F应用数学公式`N*(N+1)/2`仅需一次乘法和一次除法。在处理大量计算时，数学方法往往能减少计算步骤，提升性能。 4. **循环展开**： 对于循环...

Magicbox
Global site tag (gtag.js) - Google Analytics