CN1783009A - 一种汇编代码热函数中的热路径搜寻方法 - Google Patents

Abstract

本发明公开一种汇编代码热函数中的热路径搜寻方法，用于搜寻汇编代码中执行频率高的路径，包括：将所述汇编代码还原成控制流图，所述控制流图由多个基本块组成，并且包括所述多个基本块的信息；根据所述基本块的信息识别所述控制流图中基本块的循环信息以及循环嵌套信息；分别将所述控制流图中的每一层循环作为当前循环来搜寻该循环中所有的路径，在搜寻当前循环的路径时，不考虑当前循环的子循环的基本块；计算搜寻出的各个路径的执行频率，根据所述路径的执行频率挑选出所述热路径。本发明方法的优点：能从汇编代码中，快速准确地找出对性能影响最密切、执行频率最高的若干条热路径；有利于开发人员专注分析热路径上的代码，节省工作量。

Description

一种汇编代码热函数中的热路径搜寻方法

技术领域

本发明涉及一种热路径搜寻方法，特别是涉及一种汇编代码热函数中的热路径搜寻方法。

背景技术

在编译器的开发过程中，开发人员经常会遇到这样的一些问题：编译器的性能不如预期的好，却不知道问题出在哪里；做了某种改进之后，结果发现在有些测试例子上性能得到了提高，但是在有些例子上却有所下降；拿到性能不同的两种编译器，想知道它们在优化手段上的差异却不知如何下手。这类问题通常都要靠性能分析来解决。

性能分析指的是动态地或者静态地分析程序生成的代码，找出其中的不完善之处或者是有性能潜力之处。性能分析工具可分为动态和静态两种。

动态分析指的是在程序运行时，利用软件或硬件收集运行时的信息，最后给出统计信息，辅助开发人员找出性能瓶颈。比如Intel公司的VTune(Intel Corp，VTunePerformance Analyzers)可以按时间或事件对当前执行的指令采样，或者对程序进行插桩(Instrumentation)，给出在各个函数、各行代码上CPU执行时间的统计信息。再如HP公司的perfmon(HP Corp，Overview of the Perfmon)，它利用IA-64 Itanium处理器上的性能管理部件(PMU)，统计CPU时间在各类事件上的分布，如Cache不命中、流水线清空和寄存器栈溢出等。

静态分析指的是分析编译器生成的汇编代码，找出问题。

ORC是IA64/Linux平台上一个面向研究的开放源码优化编译器。在开发ORC编译器的过程中，先使用VTune和perfmon做动态性能分析。但是perfmon等给出的宏观统计信息对微观问题并无多大帮助。比如虽然它指出了程序多少时间花在了指令停等上，但却无从得知哪些地方可以通过指令调度去克服。再如它指出了程序多少时间花在了执行指令上，但却不知哪些指令可以通过复写传播(CopyPropagation)、死代码删除(Dead-Code Elimination)等技术优化掉。这些信息都要靠从汇编代码中静态分析得来。

但在现实中，分析汇编码的工作量很大，开发人员常常会有无从下手的感觉。比如SPEC2000中测试例子的汇编码行数动辄几十万行，无法全部分析。为了解决上述问题，一个易想到的方法是根据程序执行的2/8分布原则：程序80％的时间都花在执行20％的代码，因此只需分析那些对性能影响最密切、执行频率最高的少数几个函数，即热函数。但是通常碰到的情况是这些热函数的汇编码也有数万行，特别是在做了内联(Inlining)之后，分析量依然很大。对这种思路继续拓展，可以集中精力去分析热函数中的热代码。要找出热代码，就需搜寻出热路径。所谓热路径，指的是程序执行最常走的几条路径。由于程序绝大部分时间都是花在循环上，如果把整个函数看作最外层的循环，那么每个热路径必然位于某个循环之中。因此对于选定的热函数，先要找出函数中的循环，然后在每个循环中搜寻热路径，最后按执行频率排序，选出最热的几条路径作为性能分析的基础。

发明内容

本发明的目的是克服现有的编译器静态性能分析时汇编代码数量大，不容易查找出关键代码进行分析的缺陷，提供一种编译器静态性能分析方法，即汇编代码热函数中的热路径搜寻方法，它能在编译器编译生成的汇编代码中，快速准确地找出对性能影响最密切、执行频率最高的若干条路径。

为实现上述目的，本发明提供了一种汇编代码热函数中的热路径搜寻方法，用于搜寻汇编代码中执行频率高的路径，包括：

步骤a)：将所述汇编代码还原成控制流图，所述控制流图由多个基本块组成，并且包括所述多个基本块的信息；

步骤b)：根据所述基本块的信息识别所述控制流图中基本块的循环信息以及循环嵌套信息；

步骤c)：分别将所述控制流图中的每一层循环作为当前循环来搜寻该循环中所有的路径；其中，在搜寻当前循环的路径时，不考虑当前循环的子循环的基本块；

步骤d)：计算搜寻出的各个路径的执行频率，根据所述路径的执行频率挑选出所述热路径。

上述技术方案中，所述基本块的信息包括：基本块的执行频率、基本块的前趋块和后继块、基本块前进到后继块的概率。

上述技术方案中，在步骤c)中，所述路径从当前循环的入口块开始，并沿着基本块的执行路径前进，如果在前进过程中遇到当前循环的子循环，则跳过该子循环的基本块继续前进，当在前进过程中，一当前基本块满足一终止条件时，将该当前基本块作为该路径的最后一个基本块；所述终止条件为：

1)所述当前基本块没有后继块；

2)所述当前基本块至少有一个后继块不在当前循环内。

上述技术方案中，在步骤c)中，还包括设定一阀值，在搜寻路径时，当基本块前进到其一后继块的概率小于该阀值时，则不考虑该基本块到该后继块的执行路径。

在步骤d)中，所述路径的执行频率是组成该路径的所有基本块的执行频率以及组成该路径的相邻基本块之间的执行概率的乘积。

本发明所述方法的优点在于：

1.能从编译器编译生成的大量汇编代码中，快速准确地找出对性能影响最密切、执行频率最高的若干条热路径。

2.有利于编译器开发人员专注精力分析热路径上的代码，节省工作量。

附图说明

图1为本发明方法的流程图

图2为实施例中的hot_path_enum函数的伪代码示意图。

图3和图4为实施例中的enum_paths函数的伪代码示意图。

图5为对CPU2000gap中的一个函数CollectGarb做热路径搜寻时的一个输出。

图6为一个实施例中的代码控制流图

具体实施方式

下面结合附图和具体实施方式对本发明作进一步详细描述。

如图1所示，一个汇编代码热函数中的热路径搜寻方法包括以下步骤：

在步骤10中，将汇编代码还原成控制流图。控制流图是指编译器中所使用的一种抽象数据结构，它是一个程序或过程的抽象表述。在控制流图中，每个节点表示一个基本块，有向边表示控制流中的调转。控制流图还有两个特殊块(block)：入口块(entry block)，出口块(exit block)，控制流通过入口块进入控制流图，通过出口块结束控制流。还原控制流图的目的是为识别循环做准备。还原控制流图的操作是利用编译器profiling技术实现的。编译器profiling是一种取得程序执行信息的技术，它是一种现有技术，利用编译器profiling技术可以动态获取如基本块的执行次数，程序中每个函数执行的时间、控制流转移概率等信息。在还原控制流图操作执行完毕以后，每个基本块至少标记有下列信息：

Block ID：基本块的ID；

Frequency：基本块的执行频率；

Predecessors：基本块在控制流图上所有前驱的ID；

Successors：基本块在控制流图上所有后继的ID；

Probabilities：依次对应控制流转移到它的每个后继的概率。

图6就是一个还原以后的控制流图，在该图中包含了基本块的个数与标识，后继块的执行频率，基本块转移到其后继块的概率等信息。

由于本步骤可以采用现有技术实现，在此不再详细描述。

在步骤20中，由基本块的信息识别控制流图中基本块的循环信息。编译器在做循环优化时在基本块上记录循环信息，并且在代码输出时随基本块一同输出。识别循环的结果是，每个循环都有如下几种信息：

Loop entry：简称为entry，循环的唯一入口；

Loop tail：简称为tail，循环的唯一结尾基本块，它有指向入口的循环回边；

Loop side exits：s₀…s_m，循环的0个或多个旁出口；

Loop blocks：bb₁…bb_n，位于此循环的所有基本块。

上述的循环的结尾基本块或旁出口定义为循环出口。整个函数可以被当作是最外层循环，函数的入口就是最外层循环的入口，函数的出口就是最外层循环的结尾。最外层循环没有旁出口，它的基本块即是函数中的所有基本块。

在图6中，所要识别的函数就是最外层循环loop1，它包含所有的基本块。循环loop2由基本块b，e组成。

由于循环的识别可以在编译器中实现，故具体的循环识别过程在此也不再详细描述。

在步骤30中，识别循环嵌套信息。循环的嵌套信息，也就是要标明每个循环的紧邻的父循环是哪个。循环嵌套信息的识别利用如下两个原理：1)如果loop1的entry和tail都在loop2之中，那么loop2必然是loop1的祖先循环；2)如果loop2是loop1的祖先循环中大小最小的，那么loop2就是loop1的父循环。对所有循环按大小排序，由小到大扫描小循环是否在大循环之中，识别出循环的嵌套信息。利用上述两个原理，对某个循环可以具体识别出其子循环是哪些，父循环是哪些。

在图6中，可知loop2是loop1的子循环。

在步骤40中，搜寻循环中的热路径。在发明内容中已经提到，搜寻热路径的过程中的一个优选方案是利用阀值技术快速搜寻热路径。在本实施例中，即以该优选方案为例，对本步骤进行详细描述。

在对本操作步骤进行详细描述以前，先介绍如何实现对子循环的处理。

热路径的判断与识别是以路径的执行频率为标准的，但由于子循环能够自我循环，会得出错误的当前路径的执行频率，因此在对一个循环进行热路径的查找过程中应当跳过子循环。具体操作步骤如下：设当前路径cur_path＝{entry，…，bb_i}，并且bb_i的一个后继cur_block是某子循环的入口，并设该子循环的k个出口后继(post exit)分别为pe₁，…，pe_k。所谓循环的出口后继是指当前循环的所有循环出口的后继块，且这些块不在当前循环之中。对子循环的处理，我们只需分别跳到子循环的每个出口后继pe_i(i＝0，1，2…k)，让当前路径cur_path＝{entry，…，cur_block，pe_i}。相应地，当前路径的频率要乘以控制流从子循环跳到pe_i的概率。

对子循环的处理，应用于下述的快速搜寻热路径的方法。

热路径快速搜寻的实现方法是：

所述路径从当前循环的入口块开始，并沿着基本块的执行路径前进，如果在前进过程中遇到当前循环的子循环，则跳过该子循环的基本块继续前进，当在前进过程中，一当前基本块满足一终止条件时，将该当前基本块作为该路径的最后一个基本块；所述终止条件为：

1)所述当前基本块没有后继块；

2)所述当前基本块至少有一个后继块不在当前循环内。

路径的执行频率是组成该路径的所有基本块的执行频率以及组成该路径的相邻基本块之间的执行概率的乘积。

在热路径的搜寻过程中采用阀值技术，在搜寻过程中，设定一阀值，若基本块跳转到一后继基本块的概率小于该阀值，在不考虑该基本块到该后继块的执行路径，这样做加快了热路径的搜寻速度。

对上述的热路径快速搜寻方法，在本实施例中，用函数hot_path_enum(loop)来实现。该函数的作用是找出当前循环loop及其子循环中的所有热路径，用它对函数最外层循环进行调用即可找出函数中的所有热路径。参照图2，它包含以下步骤：

步骤41：定义一个变量cur_path，将它置空，表示目前尚无热路径。

步骤42：用变量eblock来标记循环的入口块。

步骤43：用变量cur_path_freq来标记eblock的执行频率。

步骤44：调用函数enum_paths(eblock，cur_path，cur_path_freq，loop)，计算当前循环的热路径。其中的变量cur_path_freq用来记录路径的执行频率，变量loop表示当前循环。

步骤45：计算循环的所有子循环的热路径。

在步骤44中调用了函数enum_paths(eblock，cur_path，cur_path_freq，loop)，该函数是用来计算热路径的，在该函数中运用了阀值技术。它的操作流程较为复杂，下面参照图3和图4对其具体操作进行详细说明。

调用函数enum_paths(cur_block，cur_path，cur_path_freq，loop)，其中cur_block表示当前块，cur_path表示当前路径，cur_path_freq表示当前路径的执行频率，loop表示所在循环。

步骤100：判断当前块cur_block是否在循环中，若为否，则返回，结束当前函数，若为是，继续执行下面操作。

步骤200：将当前块cur_block加入当前路径cur_path中。

步骤300：判断cur_block是否有后继块，若有后继块，跳转到步骤500，若没有后继块，继续执行下一步操作。

步骤400：输出当前的热路径cur_path及其执行频率cur_path_freq，跳转到步骤700。

步骤500：将标记alread_dump置0，表示尚未输出热路径及其执行频率。

步骤600：将curr_block的后继块记为succ，并对后继块进行以下操作。

步骤610：判断后继块succ是否是当前循环loop的一个子循环的入口，若为否，跳转到步骤620，若为是，继续执行下面操作。

步骤611：设置一变量tmp_cur_path_freq，该变量的大小为当前路径执行频率cur_path_freq和由当前块cur_block到该后继块succ的边的概率之积。

步骤612：用inner_loop来标识后继块succ所在的子循环，该子循环的出口若有后继块，则用post_exit来标识这新的后继块，对新的后继块执行以下操作。

步骤612a：将tmp_cur_path_freq和由inner_loop跳转到post_exit的概率相乘，所得结果重新置入tmp_cur_path_freq中。

步骤612b：调用enum_paths(post_exit，cur_path，tmp_cur_path_freq，loop)；计算由post_exit开始的所有的热路径。

步骤613：判断子循环inner_loop的出口的其他后继块post_exit中的热路径是否已经计算完毕，若没有计算完，则跳转到步骤612a，若已经计算完，则继续以下操作。

步骤620：如果后继块succ不在循环之内或者cur_block的后继路径(即cur_block->succ)是一条回边，则执行以下操作，若不是上述情况，则跳转到步骤630。

步骤621：判断already_dump是否为0，若为0，则输出当前的热路径集合和执行频率，并继续执行以下操作。如果不为0，则不做任何操作，并跳转到步骤630。

步骤622：将already_dump置为1。

步骤630：判断cur_block的后继路径(即cur_block->succ)所在边的执行概率是否小于阀值，所述的阀值大小是用户根据实际需要而给出的。若为是，则跳转到步骤660，若为否，继续下列操作。

步骤640：将cur_path_freq与cur_block->succ这条边的执行概率相乘，并将相乘所得的结果置于tmp_cur_path_freq。

步骤650：调用函数enum_paths(succ，cur_path，tmp_cur_path_freq，loop)以计算从succ开始的所有热路径集合。

步骤660：判断对于当前块curr_block的所有后继块succ是否都已经计算其内部的热路径，若为否，选择一内部热路径未计算的后继块，并跳转到步骤600，若为是，继续以下操作。

步骤700：结束操作，退出函数。

上述步骤中的步骤610至步骤613就是处理子循环的具体实现。

以上所述即为本发明的方法。

利用编译过程中的profiling可以对热路径按执行频率排序，并选出其中最热的几条路径(即执行频率最高的几条路径)作为性能分析的基础。

下面举一个具体的例子来说明本实施例的方法。

如图6所示，为一段代码的控制流图，在该图中，有a，b，c，d，e，f，g七个基本块，基本块旁边的整数代表这个基本块的执行频率，块与块之间连有边，边上的数字代表走这个边的概率。在图中共有两个循环，一个是最外层循环，记为loop1，它包含所有的基本块。另一个是子循环loop2，它由基本块b，e组成。从a开始搜寻loop1中的路径，a有2个后继块，分别为b和c，a的执行频率为10，从a走向b的概率为0.2，从a走向c的概率为0.8。为说明对子循环的处理方法，暂不使用阈值技术。先从a走向b，当前路径cur_path＝{a}，频率为10。因为b是子循环loop2的入口，从前述的对子循环处理可知，应当跳过子循环loop2，所以直接跳到loop2的出口后继d和f，由此分裂出两条路径：{a，d}和{a，f}，{a，d}的频率为10×0.2×0.01＝0.02；{a，f}的频率为10*0.2*0.01＝0.02。这两条路继续向下遍历，生成两条路径：{a，d，g}和{a，f，g}，频率分别为0.02和0.02。此时再向下遍历，由于基本块g没有后继块，因此路径被终止，最终得到两条路径{a，d，g}和{a，f，g}，频率分别为0.02和0.02。a若走向c，当前路径cur_path＝{a}，频率为10，a的后继块c不满足路径的终止条件，重复使用本发明所述的热路径搜寻方法，以基本块c作为当前块，其后继块为g，将c加入当前路径中，当前路径cur_path＝{a，c}，频率为10×0.8＝8，同样地向下遍历，得到路径{a，c，g}，频率为10×0.8×1.0＝8，由于g没有后继块，满足路径的终止条件，最终得到的路径为{a，c，g}，频率为8。对最外层循环loop1实现热路径搜寻后，对在第一次热路径搜寻中跳过的子循环loop2进行热路径搜寻。loop2中有两个基本块b和e。在该循环中，循环的入口块为b，循环的出口块为b和e。若b既做入口块又做出口块，很容易得到一条路径{b}，其频率为100。若b为入口块，e为出口块，则根据本发明所述方法也能够容易地得到路径{b，e}，其频率为100×0.99＝99。故在循环loop2中有两条路径{b}和{b，e}，它们的频率分别为100和99。从本段代码的控制流图中，根据本发明所述的方法可以得到5条路径，即：{a，d，g}，{a，f，g}，{a，c，g}，{b}和{b，e}。如果对热路径进行排序，取前3个最热路径，那么它们依次是{b}，{b，e}，{a，c，g}。以上所述是在不使用阀值技术的条件下。若使用阈值技术，假设设定阀值为0.1，由于从a跳转到d和f的概率小于0.1，因此就不会去遍历{a，d，g}和{a，f，g}两条路径，最终得到的路径为{a，c，g}，{b}和{b，e}。这样做显然可以节省遍历相关基本块的时间，加快搜寻速度，从而达到快速搜寻热路径的目的。

利用本发明所述的方法可以较为方便地实现对热路径的搜索，如图5所示为利用本发明所述方法对CPU2000gap中的一个函数CollectGarb做热路径搜寻时的一个输出。

在图中，Path#表示路径的序号，Loop#表示循环序号，Freq表示执行的频率，Hot Path &(Source Line#)就是表示具体的热路径，后面的括号内部分表示源程序的行号。在图5中，列出了CollectGarb函数中执行频率最高的5条路径，以路径2为例，该路径所在的循环序号为1，它的执行频率为5.21e+06，它的具体热路径为29 30 116 117 47，其中的数字标号表示基本块的序号，也就是说热路径2通过了基本块29、30、116、117和47。上述基本块的起始源程序的行号分别为774 789790 791 792 799 800 834。

Claims (5)

1、一种汇编代码热函数中的热路径搜寻方法，用于搜寻汇编代码中执行频率高的路径，包括：

步骤a)：将所述汇编代码还原成控制流图，所述控制流图由多个基本块组成，并且包括所述多个基本块的信息；

步骤b)：根据所述基本块的信息识别所述控制流图中基本块的循环信息以及循环嵌套信息；

步骤c)：分别将所述控制流图中的每一层循环作为当前循环来搜寻该循环中所有的路径；其中，在搜寻当前循环的路径时，不考虑当前循环的子循环的基本块；

步骤d)：计算搜寻出的各个路径的执行频率，根据所述路径的执行频率挑选出所述热路径。

2、根据权利要求1所述的汇编代码热函数中的热路径搜寻方法，其特征在于，所述基本块的信息包括：基本块的执行频率、基本块的前趋块和后继块、基本块前进到后继块的概率。

3、根据权利要求2所述的汇编代码热函数中的热路径搜寻方法，其特征在于，在步骤c)中，所述路径从当前循环的入口块开始，并沿着基本块的执行路径前进，如果在前进过程中遇到当前循环的子循环，则跳过该子循环的基本块继续前进，当在前进过程中，一当前基本块满足一终止条件时，将该当前基本块作为该路径的最后一个基本块；所述终止条件为：

1)所述当前基本块没有后继块；

2)所述当前基本块至少有一个后继块不在当前循环内。

4、根据权利要求3所述的汇编代码热函数中的热路径搜寻方法，其特征在于，在步骤c)中，还包括设定一阀值，在搜寻路径时，当基本块前进到其一后继块的概率小于该阀值时，则不考虑该基本块到该后继块的执行路径。

5、根据权利要求2所述的汇编代码热函数中的热路径搜寻方法，其特征在于，在步骤d)中，所述路径的执行频率是组成该路径的所有基本块的执行频率以及组成该路径的相邻基本块之间的执行概率的乘积。

Images