summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/IPO/SampleProfile.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Change CoverageTracker from a global variable to member variable to avoid ↵Dehao Chen2016-12-131-52/+52
| | | | | | breaking thread-safety. (NFC) llvm-svn: 289603
* Use CallSite to simplify codeDavid Blaikie2016-11-291-5/+3
| | | | llvm-svn: 288192
* Before sample pgo annotation, do not inline a function that has no debug ↵Dehao Chen2016-11-221-0/+2
| | | | | | | | info. (NFC) If there is no debug info in the callee, inlining it will not help annotator. This avoids infinite loop as reported in PR/31119. llvm-svn: 287710
* Use StringRef in Pass/PassManager APIs (NFC)Mehdi Amini2016-10-011-1/+1
| | | | llvm-svn: 283004
* Change the basic block weight calculation algorithm to use max instead of ↵Dehao Chen2016-09-211-14/+6
| | | | | | | | | | | | | | voting. Summary: Now that we have more precise debug info, we should change back to use maximum to get basic block weight. Reviewers: dnovillo Subscribers: andreadb, llvm-commits Differential Revision: https://reviews.llvm.org/D24788 llvm-svn: 282084
* Handle early inline for hot callsites that reside in the same basic block.Dehao Chen2016-09-191-2/+7
| | | | | | | | | | | | Summary: Callsites in the same basic block should share the same hotness. This patch checks for the hottest callsite in the same basic block, and use the hotness for all callsites in that basic block for early inline decisions. It also fixes the test to add "-S" so theat the "CHECK-NOT" is actually checking the content. Reviewers: dnovillo Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D24734 llvm-svn: 281927
* Only set branch weight during sample pgo annotation when max_weight of the ↵Dehao Chen2016-09-191-11/+15
| | | | | | | | | | | | | | branch is non-zero. Otherwise use default static profile to set branch probability. Summary: It does not make sense to set equal weights for all unkown branches as we have static branch prediction available. Reviewers: dnovillo Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D24732 llvm-svn: 281912
* Use call target count to derive the call instruction weightDehao Chen2016-09-191-3/+5
| | | | | | | | | | | | Summary: The call target count profile is directly derived from LBR branch->target data. This is more reliable than instruction frequency profiles that could be moved across basic block boundaries. This patches uses call target count profile to annotate call instructions. Reviewers: davidxl, dnovillo Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D24410 llvm-svn: 281911
* Handle Invoke during sample profiler annotation: make it inlinable.Dehao Chen2016-09-181-23/+32
| | | | | | | | | | | | Summary: Previously we reline on inst-combine to remove inlinable invoke instructions. This causes trouble because a few extra optimizations are schedule early that could introduce too much CFG change (e.g. simplifycfg removes too much control flow). This patch handles invoke instruction in-place during sample profile annotation, so that we do not rely on instcombine to remove those invoke instructions. Reviewers: davidxl, dnovillo Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D24409 llvm-svn: 281870
* Fine tuning of sample profile propagation algorithm.Dehao Chen2016-08-121-31/+100
| | | | | | | | | | | | Summary: The refined propagation algorithm is more accurate and robust. Reviewers: davidxl, dnovillo Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D23224 llvm-svn: 278522
* Consistently use ModuleAnalysisManagerSean Silva2016-08-091-1/+1
| | | | | | | | | | | Besides a general consistently benefit, the extra layer of indirection allows the mechanical part of https://reviews.llvm.org/D23256 that requires touching every transformation and analysis to be factored out cleanly. Thanks to David for the suggestion. llvm-svn: 278078
* Avoid using a raw AssumptionCacheTracker in various inliner functions.Sean Silva2016-07-231-1/+3
| | | | | | | | | | This unblocks the new PM part of River's patch in https://reviews.llvm.org/D22706 Conveniently, this same change was needed for D21921 and so these changes are just spun out from there. llvm-svn: 276515
* Implement callsite-hotness based inline cost for Sample-based PGODehao Chen2016-07-111-0/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: For sample-based PGO, using BFI to calculate callsite count is sometime not accurate. This is because with sampling based approach, if a callsite resides in a hot loop deeply nested in a bunch of cold branches, the callsite's BFI frequency would be inaccurately calculated due to lack of samples in the cold branch. E.g. if (A1 && A2 && A3 && ..... && A10) { for (i=0; i < 100000000; i++) { callsite(); } } Assume that A1 to A100 are all 100% taken, and callsite has 1000 samples and thus is considerred hot. Because the loop's trip count is huge, it's normal that all branches outside the loop has no sample at all. As a result, we can only use static branch probability to derive the the frequency of the loop header. Assuming that static heuristic thinks each branch is 50% taken, then the count calculated from BFI will be 1/(2^10) of the actual value. In order to get more accurate callsite count, we directly annotate the weight on the call instruction, and directly use it when checking callsite hotness. Note that this mechanism can also be shared by instrumentation based callsite hotness analysis. The side benefit is that it breaks the dependency from Inliner to BFI as call count is embedded in the IR. Reviewers: davidxl, eraman, dnovillo Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D22118 llvm-svn: 275073
* Tune the weight propagation algorithm for sample profile.Dehao Chen2016-07-111-12/+26
| | | | | | | | | | | | Summary: Handle the case when there is only one incoming/outgoing edge for a visited basic block: use the block weight to adjust edge weight even when the edge has been visited before. This can help reduce inaccuracies introduced by incorrect basic block profile, as shown in the updated unittest. Reviewers: davidxl, dnovillo Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D22180 llvm-svn: 275072
* Remove inline hints computation from SampleProfile.cppDehao Chen2016-07-081-70/+0
| | | | | | | | | | | | Summary: As we will move to use uniformed hotness check in inliner, we do not need inline hints in SampleProfile pass any more. Reviewers: dnovillo, davidxl Subscribers: eraman, llvm-commits Differential Revision: http://reviews.llvm.org/D19287 llvm-svn: 274918
* Hookup ProfileSummary with SampleProfilerLoaderDehao Chen2016-06-241-0/+1
| | | | | | | | | | | | Summary: Set ProfileSummary in SampleProfilerLoader. Reviewers: davidxl, eraman Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D21702 llvm-svn: 273745
* Pass AssumptionCacheTracker from SampleProfileLoader to InlinerDehao Chen2016-06-201-4/+17
| | | | | | | | | | | | Summary: Inliner needs ACT when calling InlineFunction. Instead of nullptr, we need to pass it in from SampleProfileLoader Reviewers: davidxl Subscribers: eraman, vsk, danielcdh, llvm-commits Differential Revision: http://reviews.llvm.org/D21205 llvm-svn: 273199
* [PM] Port the Sample FDO to new PM (part-2)Xinliang David Li2016-05-271-5/+17
| | | | llvm-svn: 271072
* [PM] Port the Sample FDO to new PM (part-1)Xinliang David Li2016-05-271-19/+37
| | | | llvm-svn: 271062
* Remove sample profile dependency to instcombine, which is not a analysis pass.Dehao Chen2016-05-271-8/+0
| | | | | | | | | | | | Summary: This patch removes dependency from sample profile pass to instcombine pass. Reviewers: davidxl, dnovillo Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D20501 llvm-svn: 271009
* Avoid some copies by using const references.Benjamin Kramer2016-05-271-1/+1
| | | | | | | clang-tidy's performance-unnecessary-copy-initialization with some manual fixes. No functional changes intended. llvm-svn: 270988
* Do not read callee name when matching IR to profile as it is not used.Dehao Chen2016-04-291-8/+3
| | | | | | | | | | | | Summary: Callee name is not used to identify a callsite now, so do not read it during annotation. Reviewers: davidxl, dnovillo Subscribers: dnovillo, danielcdh, llvm-commits Differential Revision: http://reviews.llvm.org/D19704 llvm-svn: 268069
* Tune basic block annotation algorithm.Dehao Chen2016-04-261-9/+12
| | | | | | | | | | | | | | | Summary: Instead of using maximum IR weight as the basic block weight, this patch uses the voting algorithm to find the most likely weight for the basic block. This can effectively avoid the cases when some IRs are annotated incorrectly due to code motion of the profiled binary. This patch also updates propagate.ll unittest to include discriminator in the input file so that it is testing something meaningful. Reviewers: davidxl, dnovillo Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D19301 llvm-svn: 267519
* Refine instruction weight annotation algorithm for sample profiler.Dehao Chen2016-04-201-0/+13
| | | | | | | | | | | | | | | Summary: This patch refined the instruction weight anootation algorithm: 1. Do not use dbg_value intrinsics for annotation. 2. Annotate cold calls if the call is inlined in profile, but not inlined before preparation. This indicates that the annotation preparation step found no sample for the inlined callsite, thus the call should be very cold. Reviewers: dnovillo, davidxl Subscribers: mgrang, llvm-commits Differential Revision: http://reviews.llvm.org/D19286 llvm-svn: 266936
* Remove llvm::getDISubprogram in favor of Function::getSubprogramPete Cooper2016-03-111-3/+3
| | | | | | | | | | | | | | | | | llvm::getDISubprogram walks the instructions in a function, looking for one in the scope of the current function, so that it can find the !dbg entry for the subprogram itself. Now that !dbg is attached to functions, this should not be necessary. This patch changes all uses to just query the subprogram directly on the function. Ideally this should be NFC, but in reality its possible that a function: has no !dbg (in which case there's likely a bug somewhere in an opt pass), or that none of the instructions had a scope referencing the function, so we used to not find the !dbg on the function but now we will Reviewed by Duncan Exon Smith. Differential Revision: http://reviews.llvm.org/D18074 llvm-svn: 263184
* Use LineLocation instead of CallsiteLocation to index callsite profile.Dehao Chen2016-03-031-14/+6
| | | | | | | | | | | | Summary: With discriminator, LineLocation can uniquely identify a callsite without the need to specifying callee name. Remove Callee function name from the key, and put it in the value (FunctionSamples). Reviewers: davidxl, dnovillo Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D17827 llvm-svn: 262634
* Perform InstructioinCombiningPass before SampleProfile pass.Dehao Chen2016-03-011-1/+4
| | | | | | | | | | | | Summary: SampleProfile pass needs to be performed after InstructionCombiningPass, which helps eliminate un-inlinable function calls. Reviewers: davidxl, dnovillo Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D17742 llvm-svn: 262419
* Set function entry count as 0 if sample profile is not found for the function.Dehao Chen2016-02-221-0/+1
| | | | | | | | | | | | Summary: This change makes the sample profile's behavior consistent with instr profile. Reviewers: davidxl, eraman, dnovillo Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D17522 llvm-svn: 261587
* Use ArrayRef to hide SmallVector details, kill a useless vector copy along ↵Benjamin Kramer2016-02-131-3/+2
| | | | | | the way. llvm-svn: 260824
* Avoid overly large SmallPtrSet/SmallSetMatthias Braun2016-01-301-2/+2
| | | | | | | These sets perform linear searching in small mode so it is never a good idea to use SmallSize/N bigger than 32. llvm-svn: 259283
* SamplePGO - Reduce memory utilization by 10x.Diego Novillo2015-12-111-1/+1
| | | | | | | | | | | | | | | DenseMap is the wrong data structure to use for sample records and call sites. The keys are too large, causing massive core memory growth when reading profiles. Before this patch, a 21Mb input profile was causing the compiler to grow to 3Gb in memory. By switching to std::map, the compiler now grows to 300Mb in memory. There still are some opportunities for memory footprint reduction. I'll be looking at those next. llvm-svn: 255389
* SamplePGO - Do not use std::to_string in diagnostics.Diego Novillo2015-11-291-12/+17
| | | | | | | | This fixes buildbots in systems that std::to_string is not present. It also tidies the output of the diagnostic to render doubles a bit better (thanks Ben Kramer for help with string streams and format). llvm-svn: 254261
* SamplePGO - Add initial support for inliner annotations.Diego Novillo2015-11-271-1/+79
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | This adds two thresholds to the sample profiler to affect inlining decisions: the concept of global hotness and coldness. Functions that have accumulated more than a certain fraction of samples at runtime, are annotated with the InlineHint attribute. Conversely, functions that accumulate less than a certain fraction of samples, are annotated with the Cold attribute. This is very similar to the hints emitted by Clang when using instrumentation profiles. Notice that this is a very blunt instrument. A function may have globally collected a significant fraction of samples, but that does not necessarily mean that every callsite for that function is hot. Ideally, we would annotate each callsite with the samples collected at that callsite. This way, the inliner can incorporate all these weights into its cost model. Once the inliner offers this functionality, we can change the hints emitted here to a more precise per-callsite annotation. For now, this is providing some measure of speedups with our internal benchmarks. I've observed speedups of up to 23% (though the geo mean is about 3%). I expect these numbers to improve as the inliner gets better annotations. llvm-svn: 254212
* SamplePGO - Fix default threshold for hot callsites.Diego Novillo2015-11-271-3/+4
| | | | | | | | | | | | | | | | | | | | | | | Based on testing of internal benchmarks, I'm lowering this threshold to a value of 0.1%. This means that SamplePGO will respect 99.9% of the original inline decisions when following a profile. The performance difference is noticeable in some tests. With the previous threshold, the speedups over baseline -O2 was about 0.63%. With the new default, the speedups are around 3% on average. The point of this threshold is not to do more aggressive inlining. When an inlined callsite crosses this threshold, SamplePGO will redo the inline decision so that it can better apply the input profile. By respecting most original inline decisions, we can apply more of the input profile because the shape of the code follows the profile more closely. In the next series, I'll be looking at adding some inline hints for the cold callsites and for toplevel functions that are hot/cold as well. llvm-svn: 254211
* SamplePGO - Add test for hot/cold inlined functions.Diego Novillo2015-11-241-17/+47
| | | | | | | | | | | | | | | | | | | | | | | When the original binary is executed and sampled, the resulting profile contains information on the original inline stack. We currently follow the original inline plan if we notice that the inlined callsite has more than 0 samples to it. A better way is to determine whether the callsite is actually worth inlining. If the callsite accumulates a small fraction of the samples spent in the parent function, then we don't want to bother inlining it (as it means that the callsite is actually cold). This patch introduces a threshold expressed in percentage of samples in relation to the parent function. If the callsite uses less than N% of the total samples used by its parent, the original inline decision is not re-applied. I've set the threshold to the very arbitrary value of 5%. I'm yet to do any actual experiments to see what's a good value. I wanted to separate the basic mechanism from the tuning. llvm-svn: 254034
* SamplePGO - Add coverage tracking for samples.Diego Novillo2015-11-231-26/+85
| | | | | | | | | | | | The existing coverage tracker counts the number of records that were used from the input profile. An alternative view of coverage is to check how many available samples were applied. This way, if the profile contains several records with few samples, it doesn't really matter much that they were not applied. The more interesting records to apply are the ones that contribute many samples. llvm-svn: 253912
* SamplePGO - Clear coverage tracking when clearing per-function data.Diego Novillo2015-11-231-0/+2
| | | | llvm-svn: 253877
* SamplePGO - Use newly introduced local variable. NFC.Diego Novillo2015-11-231-2/+2
| | | | llvm-svn: 253868
* SamplePGO - Do not count never-executed inlined functions when computing ↵Diego Novillo2015-11-201-5/+24
| | | | | | | | | | | | | | | coverage. If a function was originally inlined but not actually hot at runtime, its samples will not be counted inside the parent function. This throws off the coverage calculation because it expects to find more used records than it should. Fixed by ignoring functions that will not be inlined into the parent. Currently, this is inlined functions with 0 samples. In subsequent patches, I'll change this to mean "cold" functions. llvm-svn: 253716
* SamplePGO - Add line offset and discriminator information to sample reports.Diego Novillo2015-11-201-3/+5
| | | | | | | | | While debugging some sampling coverage problems, I found this useful: When applying samples from a profile, it helps to also know what line offset and discriminator the sample belongs to. This makes it easy to correlate against the input profile. llvm-svn: 253670
* StringRef-ify DiagnosticInfoSampleProfile::FilenameDavid Blaikie2015-11-021-3/+2
| | | | llvm-svn: 251823
* SamplePGO - Count sample records in embedded profiles when computing coverage.Diego Novillo2015-10-311-30/+54
| | | | | | | The initial coverage checking code for sample records failed to count records inside inlined profiles. This change fixes the oversight. llvm-svn: 251752
* Fix use-after-free. Thanks ASAN for giving me a detailed report :-).Daniel Jasper2015-10-291-2/+2
| | | | llvm-svn: 251623
* SamplePGO - Add flag to check sampling coverage.Diego Novillo2015-10-281-3/+83
| | | | | | | | | | | | | | | | This adds the flag -mllvm -sample-profile-check-coverage=N to the SampleProfile pass. N is the percent of input sample records that the user expects to apply. If the pass does not use N% (or more) of the sample records in the input, it emits a warning. This is useful to detect some forms of stale profiles. If the code has drifted enough from the original profile, there will be records that do not match the IR anymore. This will not detect cases where a sample profile record for line L is referring to some other instructions that also used to be at line L. llvm-svn: 251568
* SamplePGO - Clear per-function data after applying a profile.Diego Novillo2015-10-281-4/+21
| | | | | | | | | | The pass was keeping around a lot of per-function data (visited blocks, edges, dominance, etc) that is just taking up memory for no reason. In fact, from function to function it could potentially confuse the propagator since some maps are indexed by line offsets which can be common between functions. llvm-svn: 251531
* Tidy a comment. NFC.Diego Novillo2015-10-271-1/+1
| | | | llvm-svn: 251434
* Fix SamplePGO segfault when debug info is missing.Diego Novillo2015-10-271-2/+4
| | | | | | | | | | When emitting a remark for a conditional branch annotation, the remark uses the line location information of the conditional branch in the message. In some cases, that information is unavailable and the optimization would segfaul. I'm still not sure whether this is a bug or WAI, but the optimizer should not die because of this. llvm-svn: 251420
* Remove unused local variable. NFC.Diego Novillo2015-10-261-2/+0
| | | | llvm-svn: 251344
* SamplePGO - Add optimization reports.Diego Novillo2015-10-261-6/+30
| | | | | | | | | | | | | | | | | | | | | | | This adds a couple of optimization remarks to the SamplePGO transformation. When it decides to inline a hot function (to mimic the inline stack and repeat useful inline decisions in the original build). It will also report branch destinations. For instance, given the code fragment: 6 if (i < 1000) 7 sum -= i; 8 else 9 sum += -i * rand(); If the 'else' branch is taken most of the time, building this code with -Rpass=sample-profile will produce: a.cc:9:14: remark: most popular destination for conditional branches at small.cc:6:9 [-Rpass=sample-profile] sum += -i * rand(); ^ llvm-svn: 251330
* Tolerate negative offset when matching sample profile.Dehao Chen2015-10-211-9/+20
| | | | | | | | In some cases (as illustrated in the unittest), lineno can be less than the heade_lineno because the function body are included from some other files. In this case, offset will be negative. This patch makes clang still able to match the profile to IR in this situation. http://reviews.llvm.org/D13914 llvm-svn: 250873
OpenPOWER on IntegriCloud