[llvm-dev] [RFC] Control Flow Sensitive AutoFDO (FS-AFDO)
Wenlei He via llvm-dev
llvm-dev at lists.llvm.org
Fri Nov 20 14:54:19 PST 2020
Thanks for reply, see comments inline.
From: Xinliang David Li <davidxl at google.com>
Date: Friday, November 20, 2020 at 9:34 AM
To: Rong Xu <xur at google.com>
Cc: Wenlei He <wenlei at fb.com>, llvm-dev <llvm-dev at lists.llvm.org>, Hongtao Yu <hoy at fb.com>
Subject: Re: [llvm-dev] [RFC] Control Flow Sensitive AutoFDO (FS-AFDO)
On Thu, Nov 19, 2020 at 11:29 PM Rong Xu <xur at google.com<mailto:xur at google.com>> wrote:
Hi Wenlei, thanks for comments and questions! Please see my comments inline.
On Wed, Nov 18, 2020 at 4:34 PM Wenlei He <wenlei at fb.com<mailto:wenlei at fb.com>> wrote:
Hi Rong,
This is a very interesting proposal. We've also observed profile quality degradation from CFG destructive pass like loop rotate, and I can see how this proposal would help improve quality of profile that drives later optimization passes in the pipeline. I have a few questions.
* How does this affect today's AutoFDO? Specifically, can users upgrade compiler with FS-AutoFDO support but without refreshing their profile? I think it's important to make new improvement like this as opt-in, so other users of AutoFDO can choose if and when they want to make the switch from AutoFDO to FS-AutoFDO. With the proposed changes to discriminator encoding, sounds like we are going to eliminate duplication factor etc. altogether. In that case, multiple FS-AutoFDO sample profile loading would be required in order to not regress from today's AutoFDO due to lack of duplication factor. Is that correct? If so, this change as is can break backward compatibility with today's AutoFDO profile. It’d be great to handle discriminator in a way that compatible with today’s AutoFDO.
FS-AFDO has a new discriminator encoding scheme. You are right that it's not backward compatible with current AFDO profiles. The conflict is mainly from the duplication factors -- as it will be completely replaced.
The only possible regression I can think of is using current AFDO profile as an FS-AFDO profile. Due to the difference in encoding, some discriminators might be handled incorrectly.
I think we can add a flag to the AFDO header to let the compiler know if this is the new FS-AFDO profile.
We did have some discussions on the deployment at Google -- it will require two stages: the first stage enables the new discriminator scheme but still reads current AFDO profile. In the second stage, we will use the FS-AFDO profile and enable FS-AFDO passes.
[wenlei] The first stage is my concern, it can lead to perf regression like you described because it’s using AFDO profile as FS-AFDO profile. Even if we have a flag in AFDO profile header, if compiler doesn’t know how to decode the old discriminator including duplication factor, we will still see regression. How do you plan to deal with that regression from first stage?
* Profile loading usually happens early in the pipeline in order to avoid mismatch between profiling and optimization. In the case of FS-AutoFDO, some mismatch may be inevitable for the later FS profile loading. In practice, how significant is the mismatch in later profile loading? Have you tried to see by how much using multiple iterations (like CSPGO) can further help profile quality and improve performance? I understand this is not practical for production use, but could give us data points as to what's left on the table due to mismatch of later FS profile loading.
I did measure the coverage (The same mechanism used in SampleLoader). For our non-triel programs, we can use about 74% of the samples (for the FS-AFDO loader before machine block placement).
I also tried the iterative FS-AFDO. Unfortunately iterative AFDO alone shows a non-trival regression which is larger than the gain for FS-AFDO. I did that experiment a while ago. I might need to revisit it later.
Was the experiment (iterative FS-AFDO) with one round of FS profile loading (for MBP) or multiple? Like AFDO, transformation decision differences like ifcvt can affect profile quality.
[wenlei] This is interesting and counter-intuitive. Any insight on what is happening that caused the iterative FS-AFDO to have regression?
* In your performance experiment, where is the extra FSProfileSampleLoader in the pipeline, right before machine block placement or somewhere else? Have you tried adding more than one FSProfileSampleLoader and is there extra perf gain for more than one FSProfileSampleLoader?
The main performance is from the FSProfileSampleLoader before machine block placement. I did add one more loader after block placement (and a new BranchFolder pass to do the tail merge). But that did not give me visible performance.
That said, I think there is still lots of tuning work to do for better performance. I will definitely try more experimental loader passes.
* For the final discriminator assignment, is this because we take MAX of samples on addresses from the same location? So if there's any late code duplication after last discriminator assignment, we need a final discriminator assignment to turn MAX into SUM for earlier FS profile?
Yes. That's the main consideration. create_llvm_profile still use MAX for the same locations. The final discriminator assignment is to assign different discrimnatiro for each duplicated code so their sample can be summed.
There is taildup happening in MBP, so there are branch clonings.
* While changing discriminator encoding, have you considered encode block Id into discriminator so AutoFDO can be CFG aware? This is something Wei brought up earlier in the context of CSSPGO, and we didn't go that route partly because it's hard to do it without breaking compatibility.
Discriminator only has 32 bits. It's hard to inject more information. In the early stage of this work, we did consider using BB labels to encode more the flow information. This would use Sri's work on BasicBlock Sections. But that required significant change than the discriminator based method.
This would be complementary to the context-sensitive SPGO we proposed earlier - would be nice to make PGO/FDO both context-sensitive and flow-sensitive. I think the flow-sensitive part could also integrate with pseudo-probe, essentially we can append FS discriminator later multiple times the same way as you proposed here, except that the "line" part would be "probeId".
Yes. I think this idea could be used in your pseudo-probe work. The good thing about pseudo-probe is that it does not have a real instruction and the compiler can afford multiple round probe insertions.
[wenlei] Yeah, we discussed that internally. Once FS-AFDO is available upstream (both compiler change and profile generation change), we’d like to give it a try on our workloads, and potentially integrate with CSSPGO as well.
Additionally, I think it’d be good to have the profile generation for FS-AFDO available in llvm-profgen. With the recent development in this area (CSSPGO, FS-AFDO), having all the variants of profile generation in one place inside llvm project will be very important so we can all leverage the best profiling and compilation pipeline. Do you plan to make it available in llvm-profgen as well (later after baseline AFDO profile generation is there)? Happy to work together on that.
+Hongtao as well.
Thanks,
Wenlei
From: llvm-dev <llvm-dev-bounces at lists.llvm.org<mailto:llvm-dev-bounces at lists.llvm.org>>
Date: Tuesday, November 17, 2020 at 9:55 AM
To: llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>>
Cc: David Li <davidxl at google.com<mailto:davidxl at google.com>>
Subject: [llvm-dev] [RFC] Control Flow Sensitive AutoFDO (FS-AFDO)
Hi all,
Here I include an RFC for control flow sensitive AutoFDO (FS-AFDO). This is a joint work with David Li. Questions and feedback are welcome.
Thanks,
Rong
=============
[RFC] Control Flow Sensitive AutoFDO (FS-AFDO)
1. Motivation
AFDO profile is derived from PMU samples from running an earlier build binary. PMU samples are indexed by the IP addresses. An offline tool uses the debug line number to map PMU samples to the source line. The accuracy of debug information is critical for AFDO performance. Thanks to the continuous efforts from the community, we have fixed many debug info related issues that affect AFDO.
One of the remaining areas that affects the profile accuracy is the handling of duplicated code. Aggressive compiler optimizations can change functions’ control flow significantly. The transformation can duplicate branches in multiple places and new branches that do not exist in the original source code might also be introduced. All these branches, even though originated from the same source line, may have very different behavior -- which is called (control) flow sensitivity.
Current AFDO handles the duplication in a pretty coarse grain way. When AFDO sees samples with different IP addresses that map to the same source line, it uses a max function to get the maximum number of samples and attach to that line. From this prospective, current AFDO is not control flow sensitive. Consider the following example:
// Original code:
for()
Stmt1; // line 10
// After a versioning optimization
for() {
if (cond1)
stmt1; // line 10, 100 samples, address: C1
else if (cond2)
stmt1; // line 10, 80 samples, address: C2
else
stmt1; // line 10, 20 samples, address: C3
}
In the final binary, stmt1 is cloned 3 times by the versioning optimization. The address C1, gets 100 samples, the address C2 gets 80 samples, and the address C3 gets 20 samples. When converting Perf samples to AFDO profile, a max function is used for these samples as they have the same source line. In the AFDO profile, we will have a sample entry of <10, 100>, which means we have a sample value of 100 for line 10 of this function. We will not have branch information for cond1, cond2, as they do not exist in the sample loading phase. The profile count for stmt1 is also off the actual value (200 = 100 +80 + 20) by 50%.
In this work, we propose a method that maintains more precise AFDO profile counts for the duplicated control flow.
2. FS-AFDO Designs
In this work, we don't aim to keep track of the transformations and make the flow sensitivity available across the compilation pipelines. Rather, we identify a set of target optimizations that can potentially benefit most from a more precise profile. For each of such optimizations, we use a helper pass to recompute the flow sensitive profile just before this pass. When loading this profile, we will recompute the branch probability and hopefully improve the optimization quality for that target pass.
The flow sensitivity in the profile is through a hierarchical discriminator scheme that can better preserve flow information in the Perf profile.
2.1. Current Use of Discriminators
The AFDO profile contains a discriminator field whose goal is to differentiate statements with the same line number in the source code (largely from MACRO expansions).
Discriminators were later expanded to get more accurate profile counts. It is expanded to 3 components which can partially address the issue. The main objective of that work was to get the correct profile count for the unrolled (or vectorized) BBs. The discriminator is divided into 3 components:
* Base discriminator, assigned by AddDiscriminators
* Duplication factor: used in loop unroll and loop vectorization (when cloning the loop body). This factor will be multiplied by sample counts in create_llvm_prof tool to get the count value before duplication.
* Copy Identifier: reserved by not currently used.
Duplication factor was explicitly assigned in loop unroll and loop vectorization. Instruction cloning will copy the discriminator. All the cloned instruction instances, other than inlining, loop unroll and vectorization, have the same discriminator. In the create_llvm_prof tool, when assigning the sample count value for <offset_to_func_head, discriminator>, the max sample value among all the clones will be the assigned value.
2.2 Hierarchical discriminators
In FS-AFDO, discriminator assigning happens multiple times -- conceptually, one assignment for each optimization that can benefit from more precise FS profile data (let’s call it a target optimization pass). The discriminator is divided into multiple sections. Earlier passes have the lower bits and each instance of assigning access the bits in their sections only.
For example, there could be 3 rounds of discriminator assigning: the base discriminator which corresponds to existing discriminator assigning, discriminator for pass N, and discriminator for pass M. Let’s assume each round uses 4 bits. If the instruction Inst1 is from BB0 and it’s copied to BB1, it will have a discriminator 0x1. If BB1:Inst1 is copied to BB2:intr2 before Pass N, this instruction will have a new discriminator of 0x11 associated with pass N. Similarly, each copy of Inst1 before Pass M will have its own discriminators using bit 8 to bit 12.
When converting Perf samples to the AFDO profile, we will have the sample count for each discriminator. The AFDO profile loader reads all the samples and masks out the bit used by later rounds. For example, when loading the profile for the base discriminator, it only checks the first 4 bits. All the samples cloned from the same base discriminator will be aggregated together. Profile loader for pass N will only check the first 8 bits of the discriminator and sum up all the samples with the same discriminator bit 0 to bit 7.
2.3 Profile Mismatch
The above describes the ideal situation for loading the profile -- all the discriminators in the Perf binary match the discriminator in optimized build. In reality, the compilation for the optimized binary, with a new profile, might perform different transformations (from the compilation of the Perf binary). It can alter the program control flow for the downstream passes, which leads to a discriminator mismatch.
If the mismatch happens, the profiling information will not be updated by the SampleLoader to the affected BBs. They will inherit the profile information (like branch probabilities) from the previous round of SampleLoader.
The FS component in the discriminators basically uses a sequential number, just like in the base discriminator. But to handle potential mismatch, we also encode the total number of new discriminators. This prevents the misplacement of profile counts to a wrong code clone. There are limited bits for each FS discriminator component. We choose to use a hash value as the FS discriminator. The hash function takes the following as the input:
* the sequential number of the current clone,
* the total number of the current clone.
A second measure to deal with mismatch is to use the profile coverage. We summarize the samples used by SampleLoad for each function, and compare the total samples in the profile. A warning is printed out if the coverage (ratio of used samples and total sample) is lower than a threshold value. In which case, the user should rebuild the Perf binary and collect the Perf profile again.
2.4 Example of pass pipeline
Here is the one sample pass pipeline for AFDO + ThinLTO compilation.
// Pass Pipeline:
InsertBaseDiscrimator
SampleProfileLoader in FE
...
CM inline
...
SampleProfileLoader in BE
...
AddFSDiscriminator(kind_mbp)
FSProfileLoader(kind_mbp)
MachineBlockPlacement
AddFSDiscriminator(kind_branchfolding)
FSProfileLoader(kind_branchfolding)
BranchFoldingPass
…
AddFSDiscriminator(kind_final)
In the above pass pipeline. MachineBlockPlacement and BranchFoldingPass are the two target optimization passes. MachineBlockPlacement can obviously be benefited from more precise profile information. The tail merge in BranchFoldPass can undo many unneeded tail duplications in MachineBlockPlacment.
Note that we have a FS discriminator assigning pass at the final of compilation pipeline. The reason is to assign a different discriminator for each cloned instruction in the final binary. By doing this, we can get a more precise profile for earlier passes by summing the counter values from different discriminators.
3. A running example
The test program is shown as the following. We pay most attention to the branch in line 5 and line 7 in function foo(). Inner loop at line 3 will be fully unrolled after SampleProfileLoader. Outer loop at line 2 is intact by the optimizer.
__attribute__((noinline)) int bar(int i){
volatile int j;
j = i;
return j;
}
__attribute__((noinline)) void work(int i){
...
}
__attribute__((noinline)) void foo(){ // line 17 of unroll.c
int i, j;
for (j = 0; j < 48; j++)
for (i = 0; i < 4; i++) {
int ii = bar(i + j * 48);
if (ii % 2) // line 22 of unroll.c
work(ii * 2);
if (ii % 4) // line 24 of unroll.c
work(ii * 3);
}
}
Current AFDO will produce the following profile:
foo:30387110:1606 void foo() {
0: 1606 int i, j;
2.1: 83748 for (j = 0; j < 48; j++) {
4: 351836 bar:84932 int ii = bar(i + j * 48);
5: 351836 if (ii % 2)
6: 351836 work:79741 work(ii * 2)
7: 350420 if (ii % 4)
8: 338340 work:75287 work(ii * 3)
10: 1302 }
Function foo() entry sample count is 1606. Line 2.1 is the outer loop body with a sample count of 83748. Line 4 to line 8 is inner loop body count. It’s scaled by an unrolled multiplication discriminator of 4. This resulted in a higher value of sample count: it uses the Max of 4 clones and multiplies by 4.
Here is the FS AFDO profile. Basically it has a separated profile count for each unrolled instructions.
foo:8722583:1597 void foo() {
0: 1597 int i, j;
2.1: 83694 for (j = 0; j < 48; j++)
4: 87205 bar:85542 int ii = bar(i + j * 48);
4.8448: 82042 bar:82155 int ii = bar(i + j * 48);
4.13312: 84795 bar:84802 int ii = bar(i + j * 48);
4.13568: 87820 bar:87718 int ii = bar(i + j * 48);
5: 87205 if (ii % 2)
5.8448: 82042 if (ii % 2)
5.13312: 79604 if (ii %2)
5.13568: 87820 if (ii %2)
6: 0 work(ii * 2);
6.8448: 0 work(ii * 2);
6.13312: 79604 work:79652 work(ii * 2);
6.13568: 87820 work:90500 work(ii * 2);
7: 87493 if (ii %4)
7.8448: 84624 if (ii % 4)
7.13312: 71942 if (ii % 4)
7.13568: 83552 if (ii % 4)
8: 0 work(ii * 3);
8.8448: 84624 work:87655 work(ii * 3);
8.13312: 71942 work:75137 work(ii *3);
8.13568: 83552 work:91223 work(ii *3);
10: 1304 }
Let’s look at line 6 and line 8. Each of which has 4 records. When we use these records in SampleLoader, these 4 records will be combined into one after masking out the bits: line 6 will have one record of
6: 167424 work: 170152
Line 8 will have one record:
8: 240118 work: 254015
Comparing the sample count in line 5 and 7, we can easily see that line 5 has ~50% taken and line 7 has ~75% taken. This is in contrast to the current AFDO profile, where both lines have a 100% taken branch.
When we load the above profile before the MachineBlockPlacement pass, each record will maintain its own instance. We can see that at line 5, two of the branches have ~0% taken probability, while the rest two have ~100% taken probability. For line 7, one branch has 0% taken probability, while the reset three has ~100% taken probability. We will reset the branch probabilities as shown in the following messages:
Set branch fs prob: MBB (1 -> 3): unroll.c:22:11 W=87820 0x00005f85 / 0x80000000 = 0.00% --> 0x80000000 / 0x80000000 = 100.00%
Set branch fs prob: MBB (1 -> 2): unroll.c:22:11 W=87820 0x7fffa07b / 0x80000000 = 100.00% --> 0x00000000 / 0x80000000 = 0.00%
Set branch fs prob: MBB (3 -> 5): unroll.c:24:11 W=87820 0x04a8dc00 / 0x80000000 = 3.64% --> 0x80000000 / 0x80000000 = 100.00%
Set branch fs prob: MBB (3 -> 4): unroll.c:24:11 W=87820 0x7b572400 / 0x80000000 = 96.36% --> 0x00000000 / 0x80000000 = 0.00%
Set branch fs prob: MBB (9 -> 11): unroll.c:22:11 W=87820 0x00005f85 / 0x80000000 = 0.00% --> 0x80000000 / 0x80000000 = 100.00%
Set branch fs prob: MBB (9 -> 10): unroll.c:22:11 W=87820 0x7fffa07b / 0x80000000 = 100.00% --> 0x00000000 / 0x80000000 = 0.00%
Set branch fs prob: MBB (15 -> 17): unroll.c:24:11 W=87820 0x04a8dc00 / 0x80000000 = 3.64% --> 0x17248215 / 0x80000000 = 18.08%
Set branch fs prob: MBB (15 -> 16): unroll.c:24:11 W=87820 0x7b572400 / 0x80000000 = 96.36% --> 0x68db7deb / 0x80000000 = 81.92%
4. Implementation in LLVM
4.1 AFDO profile data format
The AFDO profile format remains largely the same. Samples could be splitted into multiple parts with different discriminator copy components. SampleLoader will aggregate the samples dynamically when reading the AFDO profile based on the discriminator masks. Current discriminator encoding will be removed and related code in the compiler will be removed.
The hierarchical discriminator in FS-AFDO captures most of the cases of multiplication discriminator in currenting encoding scheme. As a matter of fact, the resulting count values are usually more precise as each individual discriminator may have different count values. There is one exception: when the unrolling body has a single BB. FS-AFDO will have the correct sample count after unrolling as all the instructions residing in the same BB. In our prototype implementation, we did not find this issue to have a visible performance impact.
4.2 Compiler changes
4.2.1 Add two new CodeGen passes:
AddFSDiscriminatorsPass: adds flow sensitive discriminators.
FSProfileLoaderPass: read FS profile and set branch probabilities.
FSProfileLoadPass will reuse most of the IR level SampleProfileLoader algorithm and heuristics, but we need to reimplement at Machine level. We will not need to update branch metadata. We will change the branch probabilities directly.
4.2.2 Enhance SampleProfileReader to handle FS discriminators.
Add a new field of MaskedBitFrom to SampleProfileReader. This is the lower mask bit being used for this pass instance. For each profile loader, we dynamically compute samples based on bit masks -- this is done in readImpl() method where the masked discriminators are used to aggregate the samples.
4.3 AutoFDO tool changes
The position type used in PositionCountMap and Callsite type is of type uint32. It is divided into high 16 bits as file offset and lower 16 bits as discriminator. This is probably OK for the current discriminators as they are numbered sequentially. But this would create too many clashes in FS discriminators. We need to extend to uint64 for the position: a full 32-bit for line number and full 32-bit for discriminators.
5. Experimental performance
A prototype was implemented and a performance test was done on critical applications in Google.
Test binary:
(1) build the first round binary with an existing AFDO profile with AddFSDiscriminator enabled.
(2) collect the PERF samples and convert them to the FS AFDO profile.
(3) build an optimized binary using the FSAFDO profile from step (2).
Base binary:
(1) build the first round binary with an existing AFDO profile
(2) collect the PERF samples and convert them to the AFDO profile.
(3) build an optimized binary using profile from step (2).
Run time performance:
The test binary shows 0.9% to 1.3% performance improvement over the base binary.
Profile size:
Profile size is modestly increased. Using the Google benchmark as the example, the profile size for the text form increased by 4% to 7% while the binary form profile size increased by 5% to 8%.
Compiler time:
Prototype implementation shows about 10% increase of build time (measued by the elapsed time which includes two extra FSAddDiscrimniator passes and one extra FSProfileSampleLoader pass). Profile readings are not shared b/w FSProfileSampleLoader and current ProfileSampleLoader. We expect a smaller compiler time increase with better data structures that share a profile loader.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20201120/e151f9b3/attachment-0001.html>
More information about the llvm-dev
mailing list