C++中取余运算的优化_取余算法优化

0、前言

gcc/g++编译优化选项：-O
这个选项控制所有的优化等级。使用优化选项会使编译过程耗费更多的时间，并且占用更多的内存，尤其是在提高优化等级的时候。
-O设置一共有五种：-O0、-O1、-O2、-O3和-Os。你只能在/etc/make.conf里面设置其中的一种。
除了-O0以外，每一个-O设置都会多启用几个选项，请查阅gcc手册的优化选项章节，以便了解每个-O等级启用了哪些选项及它们有何作用。
让我们来逐一考察各个优化等级：

• -O0：这个等级（字母“O”后面跟个零）关闭所有优化选项，也是CFLAGS或CXXFLAGS中没有设置-O等级时的默认等级。这样就不会优化代码，这通常不是我们想要的。
• -O1：这是最基本的优化等级。编译器会在不花费太多编译时间的同时试图生成更快更小的代码。这些优化是非常基础的，但一般这些任务肯定能顺利完成。
• -O2：-O1的进阶。这是推荐的优化等级，除非你有特殊的需求。-O2会比-O1启用多一些标记。设置了-O2后，编译器会试图提高代码性能而不会增大体积和大量占用的编译时间。
• -O3：这是最高最危险的优化等级。用这个选项会延长编译代码的时间，并且在使用gcc4.x的系统里不应全局启用。自从3.x版本以来gcc的行为已经有了极大地改变。在3.x，-O3生成的代码也只是比-O2快一点点而已，而gcc4.x中还未必更快。用-O3来编译所有的软件包将产生更大体积更耗内存的二进制文件，大大增加编译失败的机会或不可预知的程序行为（包括错误）。这样做将得不偿失，记住过犹不及。在gcc 4.x.中使用-O3是不推荐的。
• -Os：这个等级用来优化代码尺寸。其中启用了-O2中不会增加磁盘空间占用的代码生成选项。这对于磁盘空间极其紧张或者CPU缓存较小的机器非常有用。但也可能产生些许问题，因此软件树中的大部分ebuild都过滤掉这个等级的优化。使用-Os是不推荐的。

1、实验一

假设现在有如下demo示例：

 
1 int main(void) {
2     int a = 100 % 128;
3     return 0;
4 }

不指定优化选项时的汇编代码（默认为-O0）

 1
 2 test.o: file format Mach-O 64-bit x86-64
 3
 4 Disassembly of section __TEXT,__text:
 5 _main:
 6 ; int main(void) {
 7        0:   55  pushq   %rbp
 8        1:   48 89 e5    movq    %rsp, %rbp
 9        4:   31 c0   xorl    %eax, %eax
10        6:   c7 45 fc 00 00 00 00    movl    $0, -4(%rbp)
11 ; int a = 100 % 128;
12        d:   c7 45 f8 64 00 00 00    movl    $100, -8(%rbp)
13 ; return 0;
14       14:   5d  popq    %rbp
15       15:   c3  retq

结论：虽然没有指定优化选项，但g++还是将100 % 128的结果（100）在编译的时候算出来了，在第12行的地方，通过movl  $100, -8(%rbp)指令，将100赋值给了变量a，这不是我们想要的，为了能够在汇编层面看到C++计算取余的方法，我们还需要将程序写的复杂一些，以便能够绕过g++的编译优化。

2、实验二

假设现在有如下demo示例：

1 int main(void) {
2     int a = 100;
3     int b = a % 128;
4     return 0;
5 }

不指定优化选项时的汇编代码（默认为-O0）

 1
 2 test.o: file format Mach-O 64-bit x86-64
 3
 4 Disassembly of section __TEXT,__text:
 5 _main:
 6 ; int main(void) {
 7        0:   55  pushq   %rbp
 8        1:   48 89 e5    movq    %rsp, %rbp
 9        4:   31 c0   xorl    %eax, %eax
10        6:   c7 45 fc 00 00 00 00    movl    $0, -4(%rbp)
11 ; int a = 100;
12        d:   c7 45 f8 64 00 00 00    movl    $100, -8(%rbp)
13 ; int b = a % 128;
14       14:   8b 4d f8    movl    -8(%rbp), %ecx
15       17:   89 45 f0    movl    %eax, -16(%rbp)
16       1a:   89 c8   movl    %ecx, %eax
17       1c:   99  cltd
18       1d:   b9 80 00 00 00  movl    $128, %ecx
19       22:   f7 f9   idivl   %ecx
20       24:   89 55 f4    movl    %edx, -12(%rbp)
21 ; return 0;
22       27:   8b 4d f0    movl    -16(%rbp), %ecx
23       2a:   89 c8   movl    %ecx, %eax
24       2c:   5d  popq    %rbp
25       2d:   c3  retq

结论：在第19行的地方，通过idivl %ecx指令，用eax寄存器（存的是100）里的值除以ecx寄存器（存的是128）里的值，并将余数存放在edx寄存器，商存放在eax寄存器。在第20行的地方，通过movl %edx, -12(%rbp)指令，将edx寄存器（存的是余数）放入变量b中。因此，从第19行的代码可以看出，当对128（2^7)进行取余时，编译器并未通过位运算的方式对取余操作进行优化。

指定优化选项为-O1时的汇编代码

 1
 2 test.o: file format Mach-O 64-bit x86-64
 3
 4 Disassembly of section __TEXT,__text:
 5 _main:
 6 ; int main(void) {
 7        0:   55  pushq   %rbp
 8        1:   48 89 e5    movq    %rsp, %rbp
 9 ; return 0;
10        4:   31 c0   xorl    %eax, %eax
11        6:   5d  popq    %rbp
12        7:   c3  retq

结论：开启-O1编译优化选项后，main函数中的两条语句（int a = 100; int b = a % 128;）没有被编译成汇编代码，可能的原因是，那些被优化掉的代码对程序的运行结果没有任何影响，因此被编译器跳过了，这依然不是我们想要的，为了能够在汇编层面看到C++对取余运算做的优化，我们还需要将程序写的更复杂一些，以便能够绕过g++最基本的优化，同时也能看到对取余运算的优化。

3、实验三

假设现在有如下demo示例：

1 int b = 0;
2 int foo(int x) {
3     return x * x;
4 }
5 int main(void) {
6     int a = foo(10);
7     b = a % 128;
8     return 0;
9 }

指定优化选项为-O1时的汇编代码

1
 2 test.o: file format Mach-O 64-bit x86-64
 3
 4 Disassembly of section __TEXT,__text:
 5 __Z3fooi:
 6 ; int foo(int x) {
 7        0:   55  pushq   %rbp
 8        1:   48 89 e5    movq    %rsp, %rbp
 9 ; return x * x;
10        4:   0f af ff    imull   %edi, %edi
11        7:   89 f8   movl    %edi, %eax
12        9:   5d  popq    %rbp
13        a:   c3  retq
14        b:   0f 1f 44 00 00  nopl    (%rax,%rax)
15
16 _main:
17 ; int main(void) {
18       10:   55  pushq   %rbp
19       11:   48 89 e5    movq    %rsp, %rbp
20 ; int a = foo(10);
21       14:   bf 0a 00 00 00  movl    $10, %edi
22       19:   e8 00 00 00 00  callq   0 <_main+0xe>
23 ; b = a % 128;
24       1e:   89 c1   movl    %eax, %ecx
25       20:   c1 f9 1f    sarl    $31, %ecx
26       23:   c1 e9 19    shrl    $25, %ecx
27       26:   01 c1   addl    %eax, %ecx
28       28:   83 e1 80    andl    $-128, %ecx
29       2b:   29 c8   subl    %ecx, %eax
30       2d:   89 05 00 00 00 00   movl    %eax, (%rip)
31 ; return 0;
32       33:   31 c0   xorl    %eax, %eax
33       35:   5d  popq    %rbp
34       36:   c3  retq

结论：开启-O1编译优化选项后，可以看到当128作为除数进行取余运算时，g++通过位运算做了优化，涉及到的汇编代码及其作用如下表所示

sarl    $31, %ecx

shrl    $25, %ecx

addl    %eax, %ecx

andl    $-128, %ecx

subl    %ecx, %eax

为了进一步说明上述汇编代码中的立即数25（32-7）、-128与demo中的128（2^7）有直接的关系，下面将demo中的128换成1024（2^10），然后再对比汇编代码的不同。

4、实验四

假设现在有如下demo示例：

1 int b = 0;
2 int foo(int x) {
3     return x * x;
4 }
5 int main(void) {
6     int a = foo(10);
7     b = a % 1024;
8     return 0;
9 }

指定优化选项为-O1时的汇编代码

1
 2 test.o: file format Mach-O 64-bit x86-64
 3
 4 Disassembly of section __TEXT,__text:
 5 __Z3fooi:
 6 ; int foo(int x) {
 7        0:   55  pushq   %rbp
 8        1:   48 89 e5    movq    %rsp, %rbp
 9 ; return x * x;
10        4:   0f af ff    imull   %edi, %edi
11        7:   89 f8   movl    %edi, %eax
12        9:   5d  popq    %rbp
13        a:   c3  retq
14        b:   0f 1f 44 00 00  nopl    (%rax,%rax)
15
16 _main:
17 ; int main(void) {
18       10:   55  pushq   %rbp
19       11:   48 89 e5    movq    %rsp, %rbp
20 ; int a = foo(10);
21       14:   bf 0a 00 00 00  movl    $10, %edi
22       19:   e8 00 00 00 00  callq   0 <_main+0xe>
23 ; b = a % 1024;
24       1e:   89 c1   movl    %eax, %ecx
25       20:   c1 f9 1f    sarl    $31, %ecx
26       23:   c1 e9 16    shrl    $22, %ecx
27       26:   01 c1   addl    %eax, %ecx
28       28:   81 e1 00 fc ff ff   andl    $4294966272, %ecx
29       2e:   29 c8   subl    %ecx, %eax
30       30:   89 05 00 00 00 00   movl    %eax, (%rip)
31 ; return 0;
32       36:   31 c0   xorl    %eax, %eax
33       38:   5d  popq    %rbp
34       39:   c3  retq
结论：由上述汇编代码可知，当除数换成1024之

结论：由上述汇编代码可知，当除数换成1024之后，实验三中第26行的立即数25变成了22（32-10），第28行的立即数-128变成了4294966272（即-1024的补码），其他内容不变。由此可以看出，在C++程序进行编译时，若源码中出现了对2的幂进行取余的操作，且开启了-O1优化选项，那么在随后生成的汇编代码中，是通过位运算实现取余操作的。不过，值得注意的是，在我们的源码中进行取余操作时，我们是通过立即数的形式指定了2的幂，那如果我们通过变量的形式指定2的幂（这可能是更常见的情况），结果会如何呢？

5、实验五

假设现在有如下demo示例：

 1 int b = 0;
 2 int foo(int x) {
 3     return x * x;
 4 }
 5 int goo(int x) {
 6     return 1 << x;
 7 }
 8 int main(void) {
 9     int a = foo(10);
10     int c = goo(10);
11     b = a % c;
12     return 0;
13 }

指定优化选项为-O1时的汇编代码

 1
 2 test.o: file format Mach-O 64-bit x86-64
 3
 4 Disassembly of section __TEXT,__text:
 5 __Z3fooi:
 6 ; int foo(int x) {
 7        0:   55  pushq   %rbp
 8        1:   48 89 e5    movq    %rsp, %rbp
 9        4:   89 7d fc    movl    %edi, -4(%rbp)
10 ; return x * x;
11        7:   8b 7d fc    movl    -4(%rbp), %edi
12        a:   0f af 7d fc     imull   -4(%rbp), %edi
13        e:   89 f8   movl    %edi, %eax
14       10:   5d  popq    %rbp
15       11:   c3  retq
16       12:   66 2e 0f 1f 84 00 00 00 00 00   nopw    %cs:(%rax,%rax)
17       1c:   0f 1f 40 00     nopl    (%rax)
18
19 __Z3gooi:
20 ; int goo(int x) {
21       20:   55  pushq   %rbp
22       21:   48 89 e5    movq    %rsp, %rbp
23       24:   89 7d fc    movl    %edi, -4(%rbp)
24 ; return 1 << x;
25       27:   8b 4d fc    movl    -4(%rbp), %ecx
26       2a:   bf 01 00 00 00  movl    $1, %edi
27       2f:   d3 e7   shll    %cl, %edi
28       31:   89 f8   movl    %edi, %eax
29       33:   5d  popq    %rbp
30       34:   c3  retq
31       35:   66 2e 0f 1f 84 00 00 00 00 00   nopw    %cs:(%rax,%rax)
32       3f:   90  nop
33
34 _main:
35 ; int main(void) {
36       40:   55  pushq   %rbp
37       41:   48 89 e5    movq    %rsp, %rbp
38       44:   48 83 ec 10     subq    $16, %rsp
39       48:   c7 45 fc 00 00 00 00    movl    $0, -4(%rbp)
40 ; int a = foo(10);
41       4f:   bf 0a 00 00 00  movl    $10, %edi
42       54:   e8 00 00 00 00  callq   0 <_main+0x19>
43       59:   89 45 f8    movl    %eax, -8(%rbp)
44 ; int c = goo(10);
45       5c:   bf 0a 00 00 00  movl    $10, %edi
46       61:   e8 00 00 00 00  callq   0 <_main+0x26>
47       66:   31 ff   xorl    %edi, %edi
48       68:   89 45 f4    movl    %eax, -12(%rbp)
49 ; b = a % c;
50       6b:   8b 45 f8    movl    -8(%rbp), %eax
51       6e:   99  cltd
52       6f:   f7 7d f4    idivl   -12(%rbp)
53       72:   89 15 00 00 00 00   movl    %edx, (%rip)
54 ; return 0;
55       78:   89 f8   movl    %edi, %eax
56       7a:   48 83 c4 10     addq    $16, %rsp
57       7e:   5d  popq    %rbp
58       7f:   c3  retq

结论：从第52行的 idivl -12(%rbp)指令可以看出，当我们通过变量的形式指定2的幂时，开启-O1优化后，在得到的汇编代码中并没有通过位运算来优化取余操作。既然开启-O1优化选项后并没有得到我们想要的优化效果，那么可以尝试一下-O2优化选项。

6、实验六

假设现在有如下demo示例：

 1 int b = 0;
 2 int foo(int x) {
 3     return x * x;
 4 }
 5 int goo(int x) {
 6     return 1 << x;
 7 }
 8 int main(void) {
 9     int a = foo(10);
10     int c = goo(10);
11     b = a % c;
12     return 0;
13 }

指定优化选项为-O2时的汇编代码

 1
 2 test.o: file format Mach-O 64-bit x86-64
 3
 4 Disassembly of section __TEXT,__text:
 5 __Z3fooi:
 6 ; int foo(int x) {
 7        0:   55  pushq   %rbp
 8        1:   48 89 e5    movq    %rsp, %rbp
 9 ; return x * x;
10        4:   0f af ff    imull   %edi, %edi
11        7:   89 f8   movl    %edi, %eax
12        9:   5d  popq    %rbp
13        a:   c3  retq
14        b:   0f 1f 44 00 00  nopl    (%rax,%rax)
15
16 __Z3gooi:
17 ; int goo(int x) {
18       10:   55  pushq   %rbp
19       11:   48 89 e5    movq    %rsp, %rbp
20       14:   b8 01 00 00 00  movl    $1, %eax
21 ; return 1 << x;
22       19:   89 f9   movl    %edi, %ecx
23       1b:   d3 e0   shll    %cl, %eax
24       1d:   5d  popq    %rbp
25       1e:   c3  retq
26       1f:   90  nop
27
28 _main:
29 ; int main(void) {
30       20:   55  pushq   %rbp
31       21:   48 89 e5    movq    %rsp, %rbp
32 ; b = a % c;
33       24:   c7 05 fc ff ff ff 64 00 00 00   movl    $100, -4(%rip)
34 ; return 0;
35       2e:   31 c0   xorl    %eax, %eax
36       30:   5d  popq    %rbp
37       31:   c3  retq

结论：从第33行的 movl $100, -4(%rip) 指令可以看出，开启-O2优化选项后，g++直接在编译阶段将 (x * x) % (1 << x)的结果（100）计算出来了，其中x=10。可能，这才是g++强大的优化能力。

7、参考文献

https://blog.csdn.net/attagain/article/details/18655485

https://blog.csdn.net/coder_panyy/article/details/73743722