原文

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

用de>PGOde>编译时,de>LDCde>的D代码(de>测试用例de>上)速度提高了de>7%de>.

d="PGO_7">按配置优化de>(PGO)de>

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

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

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

使用de>PGOde>的de>简单de>构建过程如下.

de class="prism language-cpp">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
de>

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

d="_25">直接和间接调用

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

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

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

d="ICP_35">提升间接调用de>(ICP)de>

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

de class="prism language-cpp">// 加载未知的函数地址到`fptr`中
d">void function() fptr = get_function_ptr();
// ...,并调用
fptr();
//为:

d">void function() fptr = get_function_ptr();
//检查地址是否是`空 likely_function()`的地址.
d">if (fptr == &likely_function)
    likely_function();
    //是的!则`/直接/`调用`likely_function()`
d">else
    fptr(); // 不,则间接调用.
de>

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

de class="prism language-cpp">d">auto is_likely(alias Likely, Fptr, Args...)(Fptr fptr, Args args) {
    d">return (fptr==&Likely)?Likely(args):fptr(args);
}
// ...
d">void function() fptr = get_function_ptr();
fptr.is_likely!likely_function();
de>

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

d="_66">分析间接调用

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

de class="prism language-cpp">d">void somefunction() {
    fptr(); // typeof(fptr) = void function()
}
de>

转换为(有些简化):

de class="prism language-cpp">d">void somefunction() {
    increment_counter(&__profc_somefunction, 0);
    __llvm_profile_instrument_target(fptr, &__profd_somefunction, 0);
    fptr();
}
de>

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

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

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

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

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

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

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

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

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

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

d="VCP_115">提升虚调用de>(VCP)de>

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

de class="prism language-cpp">d">class A {
    d">int foo(d">int a) {
        d">return a * 2;
    }
};
// ...
d">void somefunction(A a) {
    // ...
    d">auto b = a.foo(2);
    // ...
}
de>

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

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

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

de class="prism language-cpp">d">void somefunction(A a) {
    // ...
    d">auto b =
        (cast(d">void*)a.__vptr == cast(d">void*)d">typeid(B).vtbl.ptr)
      b = a.B.foo(2)//直接调用
    : b = a.foo(2);//虚表查找的原间接调用
    // ...
}
de>

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

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

d="llvm_163">哄骗de>llvmde>

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

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

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

de class="prism language-cpp">_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 ]
de>

为什么没有符号名

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

但是de>__profd_Xde>仅在,de>X函数de>内有de>llvmde>分析内置函数时,de>llvmde>才生成它.

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

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

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

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

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

de class="prism language-cpp">  %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 !185

pgo.虚表.真:
  %9 = bitcast %ddmd.dsymbol.Dsymbol* %4 to %ddmd.aggregate.AggregateDeclaration*
  br label %pgo.虚表.end

pgo.虚表.假:
  %"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.虚表.end

pgo.虚表.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}
de>

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

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

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

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

d="ICPVCP_258">de>ICPde>与de>VCPde>通信

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

de class="prism language-cpp">d">class B : A {
    d">override d">int foo(d">int a) {
        d">return a + 1;
    }
}
d">class C : A {
    d">void bar() {}
}
d">void somefunction(A a) {
    // ...
    d">auto b = a.foo(2);
    // ...
}
de>

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

当大多数时候传递de>Cde>时,你会想要de>VCPde>(假设它比de>ICPde>更快).主要是de>A和Cde>的混合时,你会想要de>ICPde>.

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

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