关于编译器优化方面的知识

kenmark · 发表于 2008-3-9 11:45:59

搜到一篇国人的东西国防科技大的《编译器前端乘幂运算的实现和优化》还没有仔细查看，先发上来，呵呵～

abbr_425f98802a1e8e4bd3812b3fa68bfd58.pdf (184.77 KB, 下载次数: 12)

mathe · 发表于 2008-3-13 13:36:00

前一段时间有次在CSDN中看到有人说Intel编译器支持PGO,而gcc只有最新的版本才开始支持。一时没有看懂PGO是什么，查了一下google才知道是指
Profiling Guided Optimization。感觉挺惊讶，gcc难道以前的版本都不支持Profiling?
Profiling翻译成中文比较难，有可能根本就没有人翻译过。这里我们把它翻译成“普查”或“数据普查”吧。
比如说有下面一段程序代码

if(a<b){
foo();
...
}else{
bar();
...
}
///code after if

复制代码

其中foo和bar都是一段包含一定代码的函数。
对于这个分支语句，编译器如果能够知道实际上大部分情况（比如大于99%的情况）a都不小于b,那么对于这样的代码，我们可以对条件语句的假分支（也就是
调用bar()函数的分支特别优化，比如这里可以将函数bar()展开，从而可以减少一次函数调用。另外，对于真分支，我们知道这个代码即使放在这里，也很少
被执行，反而在代码被执行的时候，由于最近被执行的代码需要被装载入一级代码缓存，这段真分支代码由于靠近被执行的代码，也会被装载从而浪费了很多
一级代码缓存空间，影响了程序的效率。所以通常在编译器知道真分支将很少被执行的情况，编译器可以做如下的优化
i)交换真假分支的位置,代码变为

if(a>=b){
bar();
...
}else{
foo();
...
}
///code after if

复制代码

ii)将几乎不被执行的假分支(编译器中称为冷门代码(Cold Path))移到偏远的地方，从而不会影响代码缓存的效率,代码变成

if(a>=b){
bar();
...
}else{
goto cold_path;
}
code_after_if:
///code after if
...
cold_path:
foo();
...
goto code_after_if;

复制代码

所以我们知道，如果编译器能够知道程序流程图各个不同分支在实际运行中被执行的效率情况，那么编译器将可以更好的做优化。
为此，很多编译器提供了Profiling功能，也就是先让编译器根据源代码产生一段不一定优化过的程序，这个程序除了能够正常执行这个代码的功能外，
另外加入一些对程序行为的统计代码。
然后用户可以设计一些比较典型的输入数据，利用这些输入数据运行这个代码，而这段代码在运行过程中就会产生一些统计信息，相当于于对程序运行
中一些行为进行普查。
此后，编译器可以再次编译源代码，而编译过程中，会读入前面运行过程中产生的统计信息。有了这些统计信息，编译器就可以产生优化的更好的代码了。
所以通常，Profiling Guided Optimization至少需要编译程序两次以上，而中间还需要运行程序若干此，在运行过程中会产生中间文件，用于保存统计信息。
通常Profiling主要用于产生像上面例子中的信息，也就是程序流程图中各个分支被执行的频率。这个过程，我们通常称为edge profiling. 也就是其实
我们统计的是流程图中各条边的频率。
而对于编译器来说，要产生一个可以统计edge profiling的程序很简单，只需要在源代码中插装一些代码就可以，比如上面的代码，编译器可以临时产生两个
全局变量int true_count;和int false_count;
然后将源代码改为：

if(a>=b){
true_count++;
bar();
...
}else{
false_count++;
foo();
...
}
///code after if

复制代码

就可以了，然还重新定义标准C中at_exit函数，在其中输出true_count和false_count到一个事先指定的文件中就可以了。
而同样，对于循环，我们可以用这种方法统计出一个循环平均一次执行迭代次数是多少等信息。
不过上面插装过程只是一个简单的描述，实际过程会更加复杂。
比如如果上面这段代码由于非常热门，那么它就有可能在一次运行过程中被反复执行的次数超过了2^32。如果这样，那么true_count和false_count就会发生
溢出。这种情况非常糟糕，我们正好对热门代码的统计情况出了错，这回导致误导编译器，产生效率反而比不优化前更加差的代码。
那么如果为了防止溢出，我们将数据类型由int型改成float型，那么效果又会如何呢？实际情况中我就有朋友这么做过，最后他非常惊奇的发现，对于一个热门
循环，做了如下的插装以后:

float entry_count, iteration_count, exit_count;
...
entry_count=entry_count+1.0;
while(...){
iteration_count=iteration_count+1.0;
...
}
exit_count=exit_count+1.0;

复制代码

;
那么我们可以期待，对于这个代码，循环平均迭代次数将会是值iteration_count/entry_count.
可是他们遇到了一种情况，虽然这个热门循环从语意上可以看出迭代次数应该在4到5次之间，可以每次运行统计出来的结果表示
iteration_count/entry_count都正好是1.0，大家说这会是什么原因呢？

kenmark · 发表于 2008-3-15 22:22:39

PGO只是耳闻，没有细究过
貌似通常译作“配置文件导引优化”
VC2005后开始支持这项技术
Intel的PGO使用介绍：http://www.intel.com/cd/ids/deve ... on/19314.htm?page=3
找到一篇中国人的论文：

PGO.pdf (260.11 KB, 下载次数: 6)

LZ问题的猜测性回答：事实上循环内部流程被反复执行但是每次重复却没有经过计数点，从而产生这种问题。
此外，循环计数通常并不那么准确，更改计数点的位置得到的情况也可能大不同。

mathe · 发表于 2008-3-16 09:22:14

"配置文件导印优化"，从这个名字的字面意义看好像同PGO没有关系。不知道是否是指同一样东西。
我上面提出的问题不是因为你所说的原因。循环内部流程被反复执行时，循环内部插装的计数点可以确保每次都被执行了。
同样，这几个计数变量也可以确保都被初试化为0。

shines · 发表于 2008-3-16 22:07:42

受教了，看着楼主的头像我还可以是gxqcn，我说怎么改名字了，原来就是mathe本人，厉害！

其实我第一次使用ICC7.x的时候，倒是用过PGO的，当时是看网上一个帖子做的，的确用了PGO，程序会快不少，倒是后来再次使用ICC，忘记怎么弄的了，总是觉得新版的不对，不过又懒得去查，不过PGO不一定能保证有很好的效果，不过值得尝试一下

gxqcn · 发表于 2008-3-17 07:52:55

原帖由 shines 于 2008-3-16 22:07 发表
受教了，看着楼主的头像我还可以是gxqcn，我说怎么改名字了，原来就是mathe本人，厉害！

其实我第一次使用ICC7.x的时候，倒是用过PGO的，当时是看网上一个帖子做的，的确用了PGO，程序会快不少，倒是后来再次使用 ...

俺可不敢冒名顶替，况且还是江湖上响当当的名号。

能写出这么有深度的文章，普天之下估计没几个。

欢迎 shines 的到来，想当年我们曾热烈探讨过大数算法，你的汇编功底令人佩服。
现在我们这帮网友今天终于又重聚一堂了，值得庆贺啊！

mathe · 发表于 2008-3-22 07:06:33

原帖由 kenmark 于 2008-3-15 22:22 发表 [url=http://bbs.emath.ac.cn/redirect.php?goto=findpost&pid=1692&ptid=173][img]LZ问题的猜测性回答：事实上循环内部流程被反复执行但是每次重复却没有经过计数点，从而产生这种问题。
此外，循环计数通常并不那么准确，更改计数点的位置得到的情况也可能大不同。

关于这个问题，你可以运行一下下面的代码看看结果是多少
我们应该期望到无论OPT宏是否被打开，结果都应该是8.5吧，
可惜实际上OPT宏没有定义时，结果会是1.0,而打开时，结果会是16.0
当然还可以试验将REPEAT宏变小，结果又会不同了
而OPT宏打开以后的代码相当于对没有OPT打开的版本做了一次浮点循环变量（iterations)的优化。
由于我们发现iterations是循环变量，就可以计算出每个循环它添加了c,所以就可以将累加移出循环。此后，循环中就没有任何有意义的代码，从而循环就可以删除了。
可是，做了这样的优化以后，对于这个代码，结果会发生如此之大的变化，这也是为什么通常编译器对于浮点数的大部分优化是不能做的，所以我们写代码时更加要注意，这些优化要自己来做。

#define REPEAT 100000000
static float iterations, instances;
static int seed=1;
static int rand16()///This function has period 16 and in each period, it returns each number from 1 to 16 once.
{
seed=(seed*7)%17;
return seed;
}
void foo()
{
int i,j;
for(i=0;i<REPEAT;i++)
{
int c=rand16();
#ifdef OPT
iterations+=c*1.0f;
#else
for(j=0;j<c;j++){
iterations+=1.0f;
}
#endif
instances+=1.0f;
}
}
int main()
{
foo();
printf("%f\n",iterations/instances);
return 0;
}

复制代码

mathe · 发表于 2008-3-24 10:50:45

关于上面这个问题，在CSDN中，coding_hello基本上找到了问题的所在，可以查看：
http://topic.csdn.net/u/20080322 ... tml?seed=1119611430

kenmark · 发表于 2008-3-24 12:32:30

...我以为编译器插入的代码不计入优化行列，所以没考虑，本来是有一点想到的，马上就被否了，呵呵明白了

mathe · 发表于 2008-3-24 14:03:28

通常编译器不会去识别代码是否是自己插入的。所以只要插入以后，能做的优化照样做。
只是，这里，我上面提到的优化通常编译器是不会做的，道理就是我上面说的，做了会有正确性问题，会使得关于浮点运算结果不符合IEEE 标准的要求。但是通常编译器都会提供编译选项可以关于浮点数也做结合率等优化，比如gcc里面可以使用选项-fast-math来启用。
至于上面说到的浮点数的循环变量优化，我映像中多数编译器不做。不过上面gxqcn给出的链接里面一篇文章好像提到VC是可以做的（当然肯定要启动关于浮点数的不安全优化）。
但是无论是否做优化，关于循环中edge profiling的统计，上面的插装方案都是不安全的。
如同上面提到，我一个朋友为了防止定点运算溢出问题，把数据类型改成float（保持数据存储大小不变），结果得到可用范围更加小。
当然我们可以通过把数据类型改成long long或者double使得结果可以再更加大的范围内可信。
而另外一种可以采用的更加好的方法其实可以如此。
在数据每次累加时，如果我们发现累加结果会越界，我们可以通过将各个变量同时除以一个常量2来防止它们越界。比如我们可以采用代码

unsigned entry_count, iteration_count, exit_count;
...
entry_count=entry_count+1;
unsigned local_iterasiton_count=0;
while(...){
local_iteration_count=local_iteration_count+1;
...
}
exit_count=exit_count+1.0;
iteration_count=iteration_count+local_iteration_count;
if(iteration_count<local_iteration_count){///if overlow
iteration_count<<=1;
iteration_count+=0x80000000;
exit_count<<=1;
entry_count<<=1;
}

复制代码

（当然上面代码还没有考虑一次循环迭代溢出的问题）
虽然说，上面过程对所有数据都除以2，会导致越迟统计到的数据占用权重越大，但是最终统计出来的比例（如循环平均迭代次数）还应该是非常合理的

账号		自动登录	找回密码
密码			欢迎注册

[原创] 关于编译器优化方面的知识

Profiling Guided Optimization