原文

第1部分介绍ldc中的按配置文件优化(PGO).一篇关于通过转换间接调用为直接调用来,使用配置文件数据优化虚(类)调用函数,并介绍了如何使用llvm在LDC中实现.ldc介绍,llvm地址

用PGO编译时,LDC的D代码(测试用例上)速度提高了7%.

按配置优化(PGO)

本文中,讨论给定程序典型执行流细节时,编译器可执行优化的实现.这些细节是程序的"配置文件":调用函数次数,控制流分支的频率,B函数调用A函数的频率,X变量的可能值,一般分配多少内存等.

有不同方式取配置文件,在此只讨论指令分析.编译器在第一个编译阶段中添加"指令"代码.然后,使用要优化代码的典型用例的输入运行程序,并在退出时,在单独的文件中输出配置文件数据.

编译器在第二个编译阶段使用此配置文件数据文件来编译并优化.不必经常生成新的配置文件.有小更改时,重新编译时,可重用配置文件数据;LDC控制指令流的变化,并相应地忽略配置文件数据.

使用PGO的简单构建过程如下.

ldc2 fprofileinstrgenerate=profile.raw yourprogram.d of=instrumented_program
./instrumented_program
ldcprofdata merge output=profile.data profile.raw
ldc2 fprofileinstruse=profile.data yourprogram.d of=optimized_program

指令会使程序明显变慢,使得对行为依赖特定计时或与其他系统交互的程序,不适合指令的PGO.

直接和间接调用

直接调用是对地址已知,并已在机器指令代码中编码函数的调用.间接调用是对存储在内存或寄存器中的某个地址的调用.

程序早期在变量中存储函数的地址,间接调用调用变量指向函数.在许多程序中使用间接调用:允许多态对象,绑定动态库,选择硬件中断例程等.在D中,调用类方法时可能一直使用它们.

间接调用比直接调用"慢"的原因是额外的间接性:CPU必须先读取一段内存,然后才能跳转到函数以继续执行.
现代CPU,一般间接调用与直接调用一样快.但是可在编译时内联直接调用,并允许分析被调函数内部情况及返回值.
可帮助生成更快的可执行文件.目前llvm开发者正在添加"提升间接调用"趟来使用分析信息,转换间接调用为分支+直接调用,当然LDC可利用它.

提升间接调用(ICP)

基于配置文件的提升间接调用.ICP优化,是转换如下代码片

// 加载未知的函数地址到`fptr`中
void function() fptr = get_function_ptr();
// ...,并调用
fptr();
//为:void function() fptr = get_function_ptr();
//检查地址是否是`空 likely_function()`的地址.
if (fptr == &likely_function)likely_function();//是的!则`/直接/`调用`likely_function()`
elsefptr(); // 不,则间接调用.

注意,可手动转换代码为函数指针比较+直接调用,则无需分析,就得到相同机器码.如果对函数指针内容好奇,可如下重写代码,来提高性能.使用模板函数助手,很容易完成:

auto is_likely(alias Likely, Fptr, Args...)(Fptr fptr, Args args) {return (fptr==&Likely)?Likely(args):fptr(args);
}
// ...
void function() fptr = get_function_ptr();
fptr.is_likely!likely_function();

建议看下生成的llvmIR(ldc2 outputll ...),并看看(O3)上优化与内联likely_function函数有什么区别.

分析间接调用

在添加指令的编译趟(ldc2 -fprofile-instr-generate -fprofile-indirect-calls)中,此代码:

void somefunction() {fptr(); // typeof(fptr) = void function()
}

转换为(有些简化):

void somefunction() {increment_counter(&__profc_somefunction, 0);__llvm_profile_instrument_target(fptr, &__profd_somefunction, 0);fptr();
}

指令基于每个函数工作:每个指令函数得到执行时存储分析信息的一组数据结构.
llvm检测到llvm分析内部调用函数时,自动添加它们.__profc_...数据结构是存储执行计数的数组;increment_counter的第二个参数是计数器索引.

本文其余部分,会排除执行计数器;退出指令程序之前,链入的分析运行时库会,在分析文件中(按原始格式)转储这些指令数据结构.

__profd_...最受关注:它存储"值"配置文件数据.此时,该值是存储在fptr中的原语指针值.__llvm_profile_instrument_target按IPVK_IndirectCalltarget值类型发送fptr值到0值分析槽.

然后,llvm分析机制取该值,并最终向编译器提供值列表及每个值分析槽中这些值出现的频率.这是由编译器rt的分析运行时库,及配置文件处理工具ldc-profdata这里和llvm::InstrProfReader类这里完成的.但是,每次程序运行可能有不同函数地址值时,如何使用函数地址值?

__profd_...数据结构不仅包含值配置文件数据信息.还包含函数名的引用(哈希)及函数地址!
如果可在__profd_结构中找到指针值,ldc-profdata读取所有__profd_数据结构,并(对IPVK_IndirectCalltarget值类型)转换地址值为函数名哈希.

此机制决定了ICP仅适合,在__profd_结构中存储地址+哈希的函数调用目标.
目前,对X函数,让llvm生成(正确)__profd_结构的唯一方法是,在X函数中添加llvm分析内部调用函数.如果函数指针大量指向printf很多,ICP就没法了.

以下是LDC自身用ldc-profdata show输出的配置文件的片段,显示了extern(C++)函数checkAccess(AggregateDeclaration*,Loc,域*,Dsymbol*)的配置文件数据:

_Z11checkAccessP20AggregateDeclaration3LocP5域P7Dsymbol:<snip>间接调用点数: 3间接目标结果:[ <调用点>, <符号名>, <计数> ][ 0, _ZN20AggregateDeclaration22isAggregateDeclarationEv, 196415 ][ 0, _ZN7Dsymbol22isAggregateDeclarationEv, 13102 ][ 1, _ZN11Declaration4protEv, 195211 ][ 2, _ZN7Dsymbol7toCharsEv, 20 ]

为此,函数分析了三个间接调用(0,1,2).在0调用点处,注册了两个函数指针值;94%的时间是用ICP发出"内联我!"尖叫的AggregateDeclaration::isAggregateDeclaration()调用,其他两个调用点,仅注册了一个函数指针值.1调用点的ICP肯定也会内联声明::prot().

与checkAccess(AggregateDeclaration*,Loc,域*,Dsymbol*)中的三个间接调用一样,D中的大多数间接调用都是特殊的:它们是虚函数调用.进入"提升虚调用".

提升虚调用(VCP)

我一直在努力让LDC中比ICP更进一步:把虚调用提升为直接调用.除了分析调用函数地址之外,还可分析对象的虚表地址,来提升查找虚表为直接调用函数.这消除了两个间接:对象到虚表到函数指针.考虑:

class A {int foo(int a) {return a * 2;}
};
// ...
void somefunction(A a) {// ...auto b = a.foo(2);// ...
}

因为某个函数必须,对A类型的a及继承自A类型的a工作,所以编译器"降级",foo的虚调用为如下伪代码:

void somefunction(A a) {// ...auto 虚表 = a.__vptr;
//(a是指针:0间接)int function(A, int) fptr = 虚表[index of A.foo]; 
//`虚表`查找(1个间接)auto b = fptr(a, 2);
//间接调用(第2个间接)// ...
}

分析文件数据表明,一般用(继承自A的)B类型的对象调用某个函数时,可优化代码为:

void somefunction(A a) {// ...auto b =(cast(void*)a.__vptr == cast(void*)typeid(B).vtbl.ptr)b = a.B.foo(2)//直接调用: b = a.foo(2);//虚表查找的原间接调用// ...
}

代码转换为,比较a对象的虚表指针与B类型对象的虚表指针:如果为真,则直接调用;否则,用原虚调用.a.B.foo(2)是不管a是否为B类型,显式调用B类的foo函数的D语法.

(可惜,cast(void*)typeof(B).vtbl.ptr不是常数)
(相比之下,GCC有在没有配置文件数据时,推测性去虚化的选项.

哄骗llvm

虚调用指令类似间接调用.虚调用指令的伪代码版本ldc2 -fprofile-instr-generate -fprofile-virtual-calls:

void somefunction(A a) {// ...auto 虚表 = a.__vptr;
//(a是一个指针:第0个间接)__llvm_profile_instrument_target(虚表, &__profd_somefunction, 0);int function(A, int) fptr = 虚表[index of A.foo]; 
//`虚表`查找(第1个间接)auto b = fptr(a, 2);//间接调用(第2个间接)// ...
}

以下是启用VCP时为LDC自身取配置文件的片段,再次显示了extern(C++)函数checkAccess(AggregateDeclaration*,Loc,域*,Dsymbol*)的配置文件数据:

_Z11checkAccessP20AggregateDeclaration3LocP5域P7Dsymbol:<snip>间接调用点数: 3间接目标结果:[ <调用点>, <符号名>, <计数> ][ 0, , 181132 ] *[ 0, , 13102 ][ 0, , 12316 ]  *[ 0, , 2921 ]   *[ 0, , 46 ]     *[ 1, , 131771 ][ 1, , 53053 ][ 1, , 6526 ][ 1, , 3502 ][ 1, , 296 ][ 1, , 40 ][ 1, , 21 ][ 1, , 2 ][ 2, , 20 ]

为什么没有符号名

为了使虚表值分析工作,必须稍微欺骗一下llvm.如上,__profd_数据结构用来转换原指针值为编译器给出的哈希(且在程序内不变).

但是__profd_X仅在,X函数内有llvm分析内置函数时,llvm才生成它.

而且,虚表不是函数!与llvm对函数那样,LDC必须手动为虚表创建__profd_数据结构,这样llvm就可哈希查找指针值.(有效的__profd_数据结构还包含带计数器项的__profc_数组指针,所以也必须生成它).

llvm对它自动生成的__profd_,保留所有函数名列表,并按压缩格式把它们放入可执行文件中;

__profd_包含索引压缩数据的函数名哈希.因为我生成自己的__profd_数据结构,所以符号名不在llvm的分析名列表中,查找哈希失败.

问题不大:LDC只需要知道虚表指针的哈希值,而不是实际名.也许需要llvm补丁,来允许指针->哈希->名查找,这会帮助解决未使用指令编译函数目标的ICP不可用的问题.

返回到配置文件数据.在0调用点中,注册了五个不同的虚表指针值,86%的时间它是第一个.明显的VCP机会.看看-O3生成的llvmIR:

  %4 = tail call %ddmd.dsymbol.Dsymbol* @_ZN7Dsymbol8toParentEv(%ddmd.dsymbol.Dsymbol* nonnull %smember_arg) ; [#uses = 7]
;...%6 = getelementptr inbounds %ddmd.dsymbol.Dsymbol, %ddmd.dsymbol.Dsymbol* %4, i64 0, i32 0%7 = load %ddmd.dsymbol.Dsymbol.__vtbl*, %ddmd.dsymbol.Dsymbol.__vtbl** %6, align 8%8 = icmp eq %ddmd.dsymbol.Dsymbol.__vtbl* %7, bitcast (%ddmd.dstruct.StructDeclaration.__vtbl* @_D4ddmd7dstruct17StructDeclaration6__vtblZ to %ddmd.dsymbol.Dsymbol.__vtbl*)br i1 %8, label %pgo.虚表.真, label %pgo.虚表.假, !prof !185pgo.虚表.真:%9 = bitcast %ddmd.dsymbol.Dsymbol* %4 to %ddmd.aggregate.AggregateDeclaration*br label %pgo.虚表.endpgo.虚表.假:%"smemberParent.isAggregateDeclaration@vtbl" = getelementptr inbounds %ddmd.dsymbol.Dsymbol.__vtbl, %ddmd.dsymbol.Dsymbol.__vtbl* %7, i64 0, i32 54%10 = load %ddmd.aggregate.AggregateDeclaration* (%ddmd.dsymbol.Dsymbol*)*, %ddmd.aggregate.AggregateDeclaration* (%ddmd.dsymbol.Dsymbol*)** %"smemberParent.isAggregateDeclaration@vtbl", align 8%11 = tail call %ddmd.aggregate.AggregateDeclaration* %10(%ddmd.dsymbol.Dsymbol* nonnull %4)br label %pgo.虚表.endpgo.虚表.end:%12 = phi %ddmd.aggregate.AggregateDeclaration* [ %9, %pgo.虚表.真 ], [ %11, %pgo.虚表.假 ]%13 = icmp eq %ddmd.aggregate.AggregateDeclaration* %12, null;...
!185 = !{!"branch_weights", i32 181133, i32 28386}

逐行:
1,%4存储smemberParent=smember.toParent()的值;(直接调用);
2,%6取smemberParent的__vptr,虚表指针位置的指针;
3,%7加载虚表指针;
4,%8是用StructDeclaration的链接时间常量虚表指针比较%7的结果;
5,下面是带额外分支权重元数据的!prof !185(识别(+1)?数字)的%8条件上的分支;

6,pgo.虚表.真:如果为真,则完全内联(中 this;)smemberParent.StructDeclaration.isAggregateDeclaration()调用,只剩下个转换位;

7,pgo.虚表.假:如果为假,则索引到虚表(%"smemb...@vtbl"和%10),并调用该(%11)函数指针来,调用smemberParent.isAggregateDeclaration();.

8,在pgo.虚表.end合并分支:PHI节点根据取的执行路径,选择%9或%10返回值,并在%12中存储它;
9,最后,%13使用VCP检查返回值是否为null(!),及是否完成!smemberParent.isAggregateDeclaration()!

ICP与VCP通信

根据类层次,不同虚表可能引用相同函数.

class B : A {override int foo(int a) {return a + 1;}
}
class C : A {void bar() {}
}
void somefunction(A a) {// ...auto b = a.foo(2);// ...
}

A.foo和C.foo指向相同函数,但虚表指针不同.根据传递给某个函数的对象类型的统计信息,想在查找虚表或VCP后利用间接调用的ICP.

当大多数时候传递C时,你会想要VCP(假设它比ICP更快).主要是A和C的混合时,你会想要ICP.

为了在ICP和VCP之间良好交互,应分析间接调用和虚表查找(-fprofile-indirect-calls -fprofile-virtual-calls).
目前实现了个简单的方案,当VCP有利时,忽略间接调用配置文件数据(次数>1000,虚表指针值的概率为80%或更高).

上面给出的配置文件数据中,带*的虚表指针,都会导致调用AggregateDeclaration::isAggregateDeclaration()(结合给定的配置文件数据并计算).
问题是,VCP(86%的命中率)还是ICP(96%的命中率,但额外的虚表查找"有代价")更好.