(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211040330.4 (22)申请日 2022.08.29 (71)申请人 北京航空航天大 学 地址 100191 北京市海淀区学院路37号 (72)发明人 史晓华　黄达　 (74)专利代理 机构 北京永创新实专利事务所 11121 专利代理师 周长琪 (51)Int.Cl. G06F 11/36(2006.01) G06N 20/00(2019.01) (54)发明名称 一种基于调用点二进制压缩编码的程序内 联自动调优方法 (57)摘要 本发明为一种基于调用点二进制压缩编码 的程序内联自动调优 方法， 涉及计算机编译技术 领域。 本发明方法包括： 获取程序的函数调用图， 选取热点函数， 对函数调用点的开关情况进行特 征向量编码， 并使特征向量作为编译参数传入编 译器， 对调用点是否内联进行控制； 随机生成不 同特征向量编码值， 传入编译器， 获取对应程序 运行时间， 生成训练集； 利用训练集对不同机器 学习模型训练， 选取预测程序运行时间最好的模 型， 利用训练好的模型搜索能获得最佳程序运行 时间的特征向量的编码值， 作为最终编译参数。 本发明在给定应用程序和给定输入的情况下， 可 以得到优于启发 式函数内联的程序性能， 降低现 有内联启发式方法中做出良好内联决策的难度。 权利要求书1页 说明书3页 附图2页 CN 115454830 A 2022.12.09 CN 115454830 A 1.一种基于调用点 二进制压缩编码的程序内联自动调优方法， 其特 征在于， 包括： 步骤1， 对程序编译得到二进制文件以及函数调用图； 步骤2， 对函数调用点的开关情况进行 特征向量编码， 包括： 对每个调用点， 用一位二进制数0/1表示函数是否内联的开关情况， 0表示不内联， 1表 示内联； 按照函数调用图的拓扑序遍历调用点， 保证每次函数节点访 问顺序不变； 对由拓扑序 限制的调用点访问顺序组成的二进制编码的特 征向量进行压缩； 步骤3， 修改编译器的内联优化相关代码， 使得特征向量作为编译参数传入， 通过特征 向量对调用点是否内联进行控制； 修改编译器的内联优化相关代码时， 还需要设置对特征向量的解码方式， 解码方式为 根据当前调用点按照拓扑序遍历函数调用图所 处于的位置数， 从特征向量中获取当前调用 点是否内联的开关情况； 步骤4， 对步骤2得到的函数调用点的特征向量， 随机生成不同的编码值， 将特征向量的 编码值作为编译参数传 入编译器， 对程序编译生成二进制文件并运行， 获取程序运行时间； 由特征向量的编码值与程序运行时间组成一个训练样本， 获取训练集； 步骤5， 使用训练集对不同机器学习模型进行训练； 所述模型的输入是特征向量编码 值， 输出为 程序运行时间， 选取 预测效果 最好的模型； 步骤6， 利用训练选取的模型搜索找到能获得最佳程序运行时间的特征向量的编码值， 使用该特征向量编码值作为编译参数输入编译器， 对程序进行编译。 2.根据权利要求1所述的方法， 其特征在于， 所述的步骤2中， 选取热点函数进行特征向 量编码。 3.根据权利要求1或2所述的方法， 其特征在于， 所述的步骤2中， 对由拓扑序限制的调 用点访问顺序组成的二进制编码向量进行压缩， 是将每2k位二进制数分为一组用一个十进 制数来表示， 将特 征向量的维数降低到1/2k， 其中k为大于等于4的整数。 4.根据权利要求3所述的方法， 其特征在于， 所述的步骤3 中， 设按照拓扑序遍历函数调 用图当前调用点所处于的位置数为cnt， 则计算x＝cnt/2k， y＝cnt％2k， 则当前调用点是否 内联的开关情况， 记载在特征向量的第x维中的第y位二进制位； 根据当前调用点对应的特 征向量中二进制位的值控制当前调用点是否内联。权　利　要　求　书 1/1 页 2 CN 115454830 A 2一种基于调用点二进制压缩编码的程序内联自动调优方 法 技术领域 [0001]本发明属于计算机领域， 涉及编译优化技术， 具体地说， 是指 一种基于调用点二进 制压缩编码的程序内联自动调优方法。 背景技术 [0002]随着软件工程方法和面向对象编程模型的广泛使用， 程序的结构越来越复杂、 函 数和源文件的数量越来越多， 这无疑加大了编译器过程间分析和优化的难度。 [0003]函数内联(又称内联扩展)是重要的编译优化技术之一。 它通过将符合条件的被调 用函数的源码在调用点展开， 不仅消除了函数调用开销并潜在地缩小了二进制文件大小， 而且还扩展了过程内分析和优化的范围， 是一种能够克服上述程序优化问题的简单方法。 然而这种 方法并非没有缺陷， 追求最大性能的函数内联优化已经被证明是NP完全问题， 不 存在多项式时间复杂度范围内的解决方法。 虽然 所有优秀的编译器都实现了启发式函数内 联优化， 但做出良好的内联决策是困难的， 好的选择不仅取决于其他内联选择， 还取决于优 化管道的其余部 分。 例如， 内联可以消除死代码或导致代码大小膨胀。 内联启发式方法必须 平衡实现进一步的编译器优化和大小增加。 所以这个过程中的约束数量及其组合非常多， 这使得实现最佳甚至给定应用程序的良好内联优化 性能几乎 是不可能的。 发明内容 [0004]本发明针对上述内联启发式方法存在做出良好内联决策困难的问题， 提出了一种 基于调用点二进制压缩编 码的程序内联自动调优方法， 通过对函数调用点是否内联进 行编 码后， 使用机器学习自动学习不同函数调用点的开关组合策略下 的程序性能， 进而搜索得 到最大程序性能的调用点 开关策略。 [0005]本发明提供的一种基于调用点二进制压缩编码的程序内联自动调优方法， 包括如 下步骤： [0006]步骤1， 对程序编译得到二进制文件以及函数调用图； [0007]步骤2， 对函数调用点的开关情况进行 特征向量编码， 包括： [0008]对每个调用点， 用一位二进制数0/ 1表示函数是否内联的开关情况， 0表示不内联， 1表示内联； 按照函数调用图的拓扑序遍历调用点， 保证每次函数节点访问顺序不变； 对由 拓扑序限制的调用点访问顺序组成的二进制编码的特 征向量进行压缩； [0009]步骤3， 修改编译器 的内联优化相关代码， 使得特征向量作为编译参数传入， 通过 特征向量对调用点是否内联进行控制； [0010]修改编译器的内联优化相关代码时， 还需要设置对特征向量的解码方式， 解码方 式为根据当前调用点按照拓扑序遍历函数调用图所 处于的位置数， 从特征向量中获取当前 调用点是否内联的开关情况； [0011]步骤4， 对步骤2得到的函数调用点的特征向量， 随机生成不同的编码值， 将特征向 量的编码值作为编译参数传入编译器， 对程序编译生成二进制文件并运行， 获取程序运行说　明　书 1/3 页 3 CN 115454830 A 3