summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/BlockFrequencyInfo.cpp
Commit message (Collapse)AuthorAgeFilesLines
* CodeExtractor : Add ability to preserve profile data.Sean Silva2016-08-021-0/+7
| | | | | | | | | | | Added ability to estimate the entry count of the extracted function and the branch probabilities of the exit branches. Patch by River Riddle! Differential Revision: https://reviews.llvm.org/D22744 llvm-svn: 277411
* Revert r277313 and r277314.Sean Silva2016-08-011-7/+0
| | | | | | | | | | | | | | | They seem to trigger an LSan failure: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fast/builds/15140/steps/check-llvm%20asan/logs/stdio Revert "Add the tests for r277313" This reverts commit r277314. Revert "CodeExtractor : Add ability to preserve profile data." This reverts commit r277313. llvm-svn: 277317
* CodeExtractor : Add ability to preserve profile data.Sean Silva2016-08-011-0/+7
| | | | | | | | | | | Added ability to estimate the entry count of the extracted function and the branch probabilities of the exit branches. Patch by River Riddle! Differential Revision: https://reviews.llvm.org/D22744 llvm-svn: 277313
* [BFI] Add new LazyBFI analysis passAdam Nemet2016-07-131-0/+6
| | | | | | | | | | | | | | | | | | | | | | | | Summary: This is necessary for D21771. In order to add the hotness attribute to optimization remarks we need BFI to be available in all passes that emit optimization remarks. However we don't want to pay for computing BFI unless the hotness attribute is requested. This is achieved by making BFI lazy at the very high-level through a new analysis pass -- BFI is not calculated unless requested. I am adding a test to check the laziness under D21771 where the first user of the analysis is added. Reviewers: hfinkel, dexonsmith, davidxl Subscribers: davidxl, dexonsmith, llvm-commits Differential Revision: http://reviews.llvm.org/D22141 llvm-svn: 275250
* [BFI/MBFI]: cfg graph view with color scheme Xinliang David Li2016-06-281-2/+21
| | | | | | | | | | This patch enhances dot graph viewer to show hot regions with hot bbs/edges displayed in red. The ratio of the bb freq to the max freq of the function needs to be no less than the value specified by view-hot-freq-percent option. The default value is 10 (i.e. 10%). llvm-svn: 273996
* [BFI]: enhance BFI graph dumpXinliang David Li2016-06-281-13/+20
| | | | | | | | | MBFI supports profile count dumping and function name based filtering. Add these two feature to BFI as well. The filtering option is shared between BFI and MBFI: -view-bfi-func-name=.. llvm-svn: 273992
* [BFI]: graph viewer code refactoring Xinliang David Li2016-06-281-30/+18
| | | | | | | | | | | BFI and MBFI's dot traits class share most of the code and all future enhancement. This patch extracts common implementation into base class BFIDOTGraphTraitsBase. This patch also enables BFI graph to show branch probability on edges as MBFI does before. llvm-svn: 273990
* [BFI]: NFC refactoringXinliang David Li2016-06-221-11/+4
| | | | | | | move getBlockProfileCount implementation to the base class so that MBFI can share too. llvm-svn: 273442
* [PM] port Branch Frequency Analaysis pass to new PMXinliang David Li2016-05-051-0/+27
| | | | llvm-svn: 268687
* Add getBlockProfileCount method to BlockFrequencyInfoEaswaran Raman2016-03-231-0/+14
| | | | | | Differential Revision: http://reviews.llvm.org/D18233 llvm-svn: 264179
* Recommit r250345, it was reverted in r250366 to investigate a bot failure.Manman Ren2015-10-151-0/+6
| | | | | | Our internal bot is still red after r250366. llvm-svn: 250415
* Temporarily revert r250345 to sort out bot failure.Manman Ren2015-10-151-6/+0
| | | | | | | | | | | | | | With r250345 and r250343, we start to observe the following failure when bootstrap clang with lto and pgo: PHI node entries do not match predecessors! %.sroa.029.3.i = phi %"class.llvm::SDNode.13298"* [ null, %30953 ], [ null, %31017 ], [ null, %30998 ], [ null, %_ZN4llvm8dyn_castINS_14ConstantSDNodeENS_7SDValueEEENS_10cast_rettyIT_T0_E8ret_typeERS5_.exit.i.1804 ], [ null, %30975 ], [ null, %30991 ], [ null, %_ZNK4llvm3EVT13getScalarTypeEv.exit.i.1812 ], [ %..sroa.029.0.i, %_ZN4llvm11SmallVectorIiLj8EED1Ev.exit.i.1826 ], !dbg !451895 label %30998 label %_ZNK4llvm3EVTeqES0_.exit19.thread.i LLVM ERROR: Broken function found, compilation aborted! I will re-commit this if the bot does not recover. llvm-svn: 250366
* Update the branch weight metadata in JumpThreading pass.Cong Hou2015-10-141-0/+6
| | | | | | | | | | Currently in JumpThreading pass, the branch weight metadata is not updated after CFG modification. Consider the jump threading on PredBB, BB, and SuccBB. After jump threading, the weight on BB->SuccBB should be adjusted as some of it is contributed by the edge PredBB->BB, which doesn't exist anymore. This patch tries to update the edge weight in metadata on BB->SuccBB by scaling it by 1 - Freq(PredBB->BB) / Freq(BB->SuccBB). This is the third attempt to submit this patch, while the first two led to failures in some FDO tests. After investigation, it is the edge weight normalization that caused those failures. In this patch the edge weight normalization is fixed so that there is no zero weight in the output and the sum of all weights can fit in 32-bit integer. Several unit tests are added. Differential revision: http://reviews.llvm.org/D10979 llvm-svn: 250345
* Revert r250204 and r250240 due to bot failure. We failed to build PGO-ed clang.Manman Ren2015-10-141-6/+0
| | | | llvm-svn: 250264
* Update the branch weight metadata in JumpThreading pass.Cong Hou2015-10-131-0/+6
| | | | | | | | Currently in JumpThreading pass, the branch weight metadata is not updated after CFG modification. Consider the jump threading on PredBB, BB, and SuccBB. After jump threading, the weight on BB->SuccBB should be adjusted as some of it is contributed by the edge PredBB->BB, which doesn't exist anymore. This patch tries to update the edge weight in metadata on BB->SuccBB by scaling it by 1 - Freq(PredBB->BB) / Freq(BB->SuccBB). Differential revision: http://reviews.llvm.org/D10979 llvm-svn: 250204
* Revert 250089 due to bot failure. It failed when building clang itself with PGO.Manman Ren2015-10-131-6/+0
| | | | llvm-svn: 250145
* Update the branch weight metadata in JumpThreading pass.Cong Hou2015-10-121-0/+6
| | | | | | | | In JumpThreading pass, the branch weight metadata is not updated after CFG modification. Consider the jump threading on PredBB, BB, and SuccBB. After jump threading, the weight on BB->SuccBB should be adjusted as some of it is contributed by the edge PredBB->BB, which doesn't exist anymore. This patch tries to update the edge weight in metadata on BB->SuccBB by scaling it by 1 - Freq(PredBB->BB) / Freq(BB->SuccBB). Differential revision: http://reviews.llvm.org/D10979 llvm-svn: 250089
* Analysis: Remove implicit ilist iterator conversionsDuncan P. N. Exon Smith2015-10-101-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Remove implicit ilist iterator conversions from LLVMAnalysis. I came across something really scary in `llvm::isKnownNotFullPoison()` which relied on `Instruction::getNextNode()` being completely broken (not surprising, but scary nevertheless). This function is documented (and coded to) return `nullptr` when it gets to the sentinel, but with an `ilist_half_node` as a sentinel, the sentinel check looks into some other memory and we don't recognize we've hit the end. Rooting out these scary cases is the reason I'm removing the implicit conversions before doing anything else with `ilist`; I'm not at all surprised that clients rely on badness. I found another scary case -- this time, not relying on badness, just bad (but I guess getting lucky so far) -- in `ObjectSizeOffsetEvaluator::compute_()`. Here, we save out the insertion point, do some things, and then restore it. Previously, we let the iterator auto-convert to `Instruction*`, and then set it back using the `Instruction*` version: Instruction *PrevInsertPoint = Builder.GetInsertPoint(); /* Logic that may change insert point */ if (PrevInsertPoint) Builder.SetInsertPoint(PrevInsertPoint); The check for `PrevInsertPoint` doesn't protect correctly against bad accesses. If the insertion point has been set to the end of a basic block (i.e., `SetInsertPoint(SomeBB)`), then `GetInsertPoint()` returns an iterator pointing at the list sentinel. The version of `SetInsertPoint()` that's getting called will then call `PrevInsertPoint->getParent()`, which explodes horribly. The only reason this hasn't blown up is that it's fairly unlikely the builder is adding to the end of the block; usually, we're adding instructions somewhere before the terminator. llvm-svn: 249925
* Add new constructors for LoopInfo/DominatorTree/BFI/BPICong Hou2015-07-161-0/+8
| | | | | | | | | | | | | | | | | Those new constructors make it more natural to construct an object for a function. For example, previously to build a LoopInfo for a function, we need four statements: DominatorTree DT; LoopInfo LI; DT.recalculate(F); LI.analyze(DT); Now we only need one statement: LoopInfo LI(DominatorTree(F)); http://reviews.llvm.org/D11274 llvm-svn: 242486
* Create a wrapper pass for BranchProbabilityInfo.Cong Hou2015-07-151-3/+4
| | | | | | | | This new wrapper pass is useful when we want to do branch probability analysis conditionally (e.g. only in PGO mode) but don't want to add one more pass dependence. http://reviews.llvm.org/D11241 llvm-svn: 242349
* Rename doFunction() in BFI to calculate() and change its parameters from ↵Cong Hou2015-07-151-1/+1
| | | | | | | | pointers to references. http://reviews.llvm.org/D11196 llvm-svn: 242322
* Create a wrapper pass for BlockFrequencyInfo.Wei Mi2015-07-141-32/+48
| | | | | | | | | | | | This is useful when we want to do block frequency analysis conditionally (e.g. only in PGO mode) but don't want to add one more pass dependence. Patch by congh. Approved by dexonsmith. Differential Revision: http://reviews.llvm.org/D11196 llvm-svn: 242248
* Remove superfluous .str() and replace std::string concatenation with Twine.Yaron Keren2015-03-271-1/+1
| | | | llvm-svn: 233392
* [PM] Split the LoopInfo object apart from the legacy pass, creatingChandler Carruth2015-01-171-3/+3
| | | | | | | | | | a LoopInfoWrapperPass to wire the object up to the legacy pass manager. This switches all the clients of LoopInfo over and paves the way to port LoopInfo to the new pass manager. No functionality change is intended with this iteration. llvm-svn: 226373
* Revert "Introduce a string_ostream string builder facilty"Alp Toker2014-06-261-3/+4
| | | | | | Temporarily back out commits r211749, r211752 and r211754. llvm-svn: 211814
* Introduce a string_ostream string builder faciltyAlp Toker2014-06-261-4/+3
| | | | | | | | | | | | | | | | | | | | string_ostream is a safe and efficient string builder that combines opaque stack storage with a built-in ostream interface. small_string_ostream<bytes> additionally permits an explicit stack storage size other than the default 128 bytes to be provided. Beyond that, storage is transferred to the heap. This convenient class can be used in most places an std::string+raw_string_ostream pair or SmallString<>+raw_svector_ostream pair would previously have been used, in order to guarantee consistent access without byte truncation. The patch also converts much of LLVM to use the new facility. These changes include several probable bug fixes for truncated output, a programming error that's no longer possible with the new interface. llvm-svn: 211749
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-1/+2
| | | | | | | | | | definition below all the header #include lines, lib/Analysis/... edition. This one has a bit extra as there were *other* #define's before #include lines in addition to DEBUG_TYPE. I've sunk all of them as a block. llvm-svn: 206843
* Reapply "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith2014-04-211-2/+6
| | | | | | | | | This reverts commit r206707, reapplying r206704. The preceding commit to CalcSpillWeights should have sorted out the failing buildbots. <rdar://problem/14292693> llvm-svn: 206766
* Revert "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith2014-04-191-6/+2
| | | | | | This reverts commit r206704, as expected. llvm-svn: 206707
* Reapply "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith2014-04-191-2/+6
| | | | | | | | | | | | | | | | | | | | | This reverts commit r206677, reapplying my BlockFrequencyInfo rewrite. I've done a careful audit, added some asserts, and fixed a couple of bugs (unfortunately, they were in unlikely code paths). There's a small chance that this will appease the failing bots [1][2]. (If so, great!) If not, I have a follow-up commit ready that will temporarily add -debug-only=block-freq to the two failing tests, allowing me to compare the code path between what the failing bots and what my machines (and the rest of the bots) are doing. Once I've triggered those builds, I'll revert both commits so the bots go green again. [1]: http://bb.pgr.jp/builders/ninja-x64-msvc-RA-centos6/builds/1816 [2]: http://llvm-amd64.freebsd.your.org/b/builders/clang-i386-freebsd/builds/18445 <rdar://problem/14292693> llvm-svn: 206704
* Revert "blockfreq: Rewrite BlockFrequencyInfoImpl" (#2)Duncan P. N. Exon Smith2014-04-191-6/+2
| | | | | | | | | | | This reverts commit r206666, as planned. Still stumped on why the bots are failing. Sanitizer bots haven't turned anything up. If anyone can help me debug either of the failures (referenced in r206666) I'll owe them a beer. (In the meantime, I'll be auditing my patch for undefined behaviour.) llvm-svn: 206677
* Reapply "blockfreq: Rewrite BlockFrequencyInfoImpl" (#2)Duncan P. N. Exon Smith2014-04-181-2/+6
| | | | | | | | | | | | | | | | | | | This reverts commit r206628, reapplying r206622 (and r206626). Two tests are failing only on buildbots [1][2]: i.e., I can't reproduce on Darwin, and Chandler can't reproduce on Linux. Asan and valgrind don't tell us anything, but we're hoping the msan bot will catch it. So, I'm applying this again to get more feedback from the bots. I'll leave it in long enough to trigger builds in at least the sanitizer buildbots (it was failing for reasons unrelated to my commit last time it was in), and hopefully a few others.... and then I expect to revert a third time. [1]: http://bb.pgr.jp/builders/ninja-x64-msvc-RA-centos6/builds/1816 [2]: http://llvm-amd64.freebsd.your.org/b/builders/clang-i386-freebsd/builds/18445 llvm-svn: 206666
* Revert "blockfreq: Rewrite BlockFrequencyInfoImpl" (#2)Duncan P. N. Exon Smith2014-04-181-6/+2
| | | | | | | | | This reverts commit r206622 and the MSVC fixup in r206626. Apparently the remotely failing tests are still failing, despite my attempt to fix the nondeterminism in r206621. llvm-svn: 206628
* Reapply "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith2014-04-181-2/+6
| | | | | | | | | | | | | | This reverts commit r206556, effectively reapplying commit r206548 and its fixups in r206549 and r206550. In an intervening commit I've added target triples to the tests that were failing remotely [1] (but passing locally). I'm hoping the mystery is solved? I'll revert this again if the tests are still failing remotely. [1]: http://bb.pgr.jp/builders/ninja-x64-msvc-RA-centos6/builds/1816 llvm-svn: 206622
* Revert "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith2014-04-181-6/+2
| | | | | | | | | | | This reverts commits r206548, r206549 and r206549. There are some unit tests failing that aren't failing locally [1], so reverting until I have time to investigate. [1]: http://bb.pgr.jp/builders/ninja-x64-msvc-RA-centos6/builds/1816 llvm-svn: 206556
* blockfreq: Rewrite BlockFrequencyInfoImplDuncan P. N. Exon Smith2014-04-181-2/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Rewrite the shared implementation of BlockFrequencyInfo and MachineBlockFrequencyInfo entirely. The old implementation had a fundamental flaw: precision losses from nested loops (or very wide branches) compounded past loop exits (and convergence points). The @nested_loops testcase at the end of test/Analysis/BlockFrequencyAnalysis/basic.ll is motivating. This function has three nested loops, with branch weights in the loop headers of 1:4000 (exit:continue). The old analysis gives non-sensical results: Printing analysis 'Block Frequency Analysis' for function 'nested_loops': ---- Block Freqs ---- entry = 1.0 for.cond1.preheader = 1.00103 for.cond4.preheader = 5.5222 for.body6 = 18095.19995 for.inc8 = 4.52264 for.inc11 = 0.00109 for.end13 = 0.0 The new analysis gives correct results: Printing analysis 'Block Frequency Analysis' for function 'nested_loops': block-frequency-info: nested_loops - entry: float = 1.0, int = 8 - for.cond1.preheader: float = 4001.0, int = 32007 - for.cond4.preheader: float = 16008001.0, int = 128064007 - for.body6: float = 64048012001.0, int = 512384096007 - for.inc8: float = 16008001.0, int = 128064007 - for.inc11: float = 4001.0, int = 32007 - for.end13: float = 1.0, int = 8 Most importantly, the frequency leaving each loop matches the frequency entering it. The new algorithm leverages BlockMass and PositiveFloat to maintain precision, separates "probability mass distribution" from "loop scaling", and uses dithering to eliminate probability mass loss. I have unit tests for these types out of tree, but it was decided in the review to make the classes private to BlockFrequencyInfoImpl, and try to shrink them (or remove them entirely) in follow-up commits. The new algorithm should generally have a complexity advantage over the old. The previous algorithm was quadratic in the worst case. The new algorithm is still worst-case quadratic in the presence of irreducible control flow, but it's linear without it. The key difference between the old algorithm and the new is that control flow within a loop is evaluated separately from control flow outside, limiting propagation of precision problems and allowing loop scale to be calculated independently of mass distribution. Loops are visited bottom-up, their loop scales are calculated, and they are replaced by pseudo-nodes. Mass is then distributed through the function, which is now a DAG. Finally, loops are revisited top-down to multiply through the loop scales and the masses distributed to pseudo nodes. There are some remaining flaws. - Irreducible control flow isn't modelled correctly. LoopInfo and MachineLoopInfo ignore irreducible edges, so this algorithm will fail to scale accordingly. There's a note in the class documentation about how to get closer. See also the comments in test/Analysis/BlockFrequencyInfo/irreducible.ll. - Loop scale is limited to 4096 per loop (2^12) to avoid exhausting the 64-bit integer precision used downstream. - The "bias" calculation proposed on llvmdev is *not* incorporated here. This will be added in a follow-up commit, once comments from this review have been handled. llvm-svn: 206548
* blockfreq: Rename BlockFrequencyImpl to BlockFrequencyInfoImplDuncan P. N. Exon Smith2014-04-111-2/+2
| | | | | | | | | | | | This is a shared implementation class for BlockFrequencyInfo and MachineBlockFrequencyInfo, not for BlockFrequency, a related (but distinct) class. No functionality change. <rdar://problem/14292693> llvm-svn: 206083
* blockfreq: Implement Pass::releaseMemory()Duncan P. N. Exon Smith2014-03-251-9/+10
| | | | | | | | | | Implement Pass::releaseMemory() in BlockFrequencyInfo and MachineBlockFrequencyInfo. Just delete the private implementation when not in use. Switch to a std::unique_ptr to make the logic more clear. <rdar://problem/14292693> llvm-svn: 204741
* [Modules] Move CFG.h to the IR library as it defines graph traits overChandler Carruth2014-03-041-1/+1
| | | | | | IR types. llvm-svn: 202827
* BlockFrequencyInfo: Readded getEntryFreq.Yuchen Wu2013-12-201-0/+4
| | | | llvm-svn: 197839
* [block-freq] Update BlockFrequencyInfo/MachineBlockFrequencyInfo to use the ↵Michael Gottesman2013-12-141-1/+1
| | | | | | new print methods. llvm-svn: 197289
* [block-freq] Add the equivalent methods to MachineBlockFrequencyInfo and ↵Michael Gottesman2013-12-141-0/+11
| | | | | | BlockFrequencyInfo that were added to BlockFrequencyImpl in r197285 and r197284. llvm-svn: 197287
* Added BlockFrequencyInfo::view for displaying the block frequency ↵Michael Gottesman2013-11-141-0/+103
| | | | | | | | | | propagation graph via graphviz. This is useful for debugging issues in the BlockFrequency implementation since one can easily visualize where probability mass and other errors occur in the propagation. llvm-svn: 194654
* Fixed 80+ violations.Michael Gottesman2013-11-141-5/+5
| | | | llvm-svn: 194634
* BlockFrequency: Bump up the entry frequency a bit.Benjamin Kramer2013-06-251-5/+0
| | | | | | | This is a band-aid to fix the most severe regressions we're seeing from basing spill decisions on block frequencies, until we have a better solution. llvm-svn: 184835
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-3/+3
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] llvm-svn: 169131
* Add some constantness to BranchProbabilityInfo and BlockFrequnencyInfo.Jakub Staszak2011-12-201-1/+1
| | | | llvm-svn: 146986
* Add pass printing support to BlockFrequencyInfo pass. The implementationChandler Carruth2011-10-191-0/+4
| | | | | | | | | | | | | layer already had support for printing the results of this analysis, but the wiring was missing. Now that printing the analysis works, actually bring some of this analysis, and the BranchProbabilityInfo analysis that it wraps, under test! I'm planning on fixing some bugs and doing other work here, so having a nice place to add regression tests and a way to observe the results is really useful. llvm-svn: 142491
* Add more constantness in BlockFrequencyInfo.Jakub Staszak2011-08-031-1/+1
| | | | llvm-svn: 136816
* Use BlockFrequency instead of uint32_t in BlockFrequencyInfo.Jakub Staszak2011-07-271-1/+1
| | | | llvm-svn: 136278
OpenPOWER on IntegriCloud