summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/MachineBlockFrequencyInfo.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Irreducible loop metadata for more accurate block frequency under PGO.Hiroshi Yamauchi2017-11-021-0/+6
| | | | | | | | | | | | | | | | | | | | | | | Summary: Currently the block frequency analysis is an approximation for irreducible loops. The new irreducible loop metadata is used to annotate the irreducible loop headers with their header weights based on the PGO profile (currently this is approximated to be evenly weighted) and to help improve the accuracy of the block frequency analysis for irreducible loops. This patch is a basic support for this. Reviewers: davidxl Reviewed By: davidxl Subscribers: mehdi_amini, llvm-commits, eraman Differential Revision: https://reviews.llvm.org/D39028 llvm-svn: 317278
* Add options to dump block frequency/branch probability info in text.Hiroshi Yamauchi2017-08-261-0/+13
| | | | | | | | | | | | | | | | | | | | | Summary: Add options -print-bfi/-print-bpi that dump block frequency and branch probability info like -view-block-freq-propagation-dags and -view-machine-block-freq-propagation-dags do but in text. This is useful when the graph is very large and complex (the dot command crashes, lines/edges too close to tell apart, hard to navigate without textual search) or simply when text is preferred. Reviewers: davidxl Reviewed By: davidxl Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D37165 llvm-svn: 311822
* [CodeGen] Fix some Clang-tidy modernize-use-using and Include What You Use ↵Eugene Zelenko2017-08-241-18/+20
| | | | | | warnings; other minor fixes (NFC). llvm-svn: 311703
* CodeGen: Rename DEBUG_TYPE to match passnamesMatthias Braun2017-05-251-3/+3
| | | | | | | | Rename the DEBUG_TYPE to match the names of corresponding passes where it makes sense. Also establish the pattern of simply referencing DEBUG_TYPE instead of repeating the passname where possible. llvm-svn: 303921
* include function name in dot filenameXinliang David Li2017-02-151-5/+4
| | | | | | Differential Revision: http://reviews.llvm.org/D29975 llvm-svn: 295220
* Add new pass LazyMachineBlockFrequencyInfoAdam Nemet2017-02-141-4/+10
| | | | | | | | | | | | | | | | | And use it in MachineOptimizationRemarkEmitter. A test will follow on top of Justin's changes to enable MachineORE in AsmPrinter. The approach is similar to the IR-level pass. It's a bit simpler because BPI is immutable at the Machine level so we don't need to make that lazy. Because of this, a new function mapping is introduced (BPIPassTrait::getBPI). This function extracts BPI from the pass. In case of the lazy pass, this is when the calculation of the BFI occurs. For Machine-level, this is the identity function. Differential Revision: https://reviews.llvm.org/D29836 llvm-svn: 295072
* [PGO] internal option cleanupsXinliang David Li2017-02-021-0/+4
| | | | | | | | | | 1. Added comments for options 2. Added missing option cl::desc field 3. Uniified function filter option for graph viewing. Now PGO count/raw-counts share the same filter option: -view-bfi-func-name=. llvm-svn: 293938
* [PGO] make graph view internal options available for all buildsXinliang David Li2017-02-021-9/+0
| | | | | | Differential Revision: https://reviews.llvm.org/D29259 llvm-svn: 293921
* Add support to dump dot graph block layout after MBPXinliang David Li2017-01-291-5/+48
| | | | | | Differential Revision: https://reviews.llvm.org/D29141 llvm-svn: 293408
* Turn cl::values() (for enum) from a vararg function to using C++ variadic ↵Mehdi Amini2016-10-081-3/+1
| | | | | | | | | | | | | | | template The core of the change is supposed to be NFC, however it also fixes what I believe was an undefined behavior when calling: va_start(ValueArgs, Desc); with Desc being a StringRef. Differential Revision: https://reviews.llvm.org/D25342 llvm-svn: 283671
* s/static inline/static/ for headers I have changed in r279475. NFC.Tim Shen2016-08-311-1/+1
| | | | llvm-svn: 280257
* [GraphTraits] Replace all NodeType usage with NodeRefTim Shen2016-08-221-7/+3
| | | | | | | | This should finish the GraphTraits migration. Differential Revision: http://reviews.llvm.org/D23730 llvm-svn: 279475
* [GraphTraits] Make nodes_iterator dereference to NodeType*/NodeRefTim Shen2016-08-191-3/+3
| | | | | | | | | Currently nodes_iterator may dereference to a NodeType* or a NodeType&. Make them all dereference to NodeType*, which is NodeRef later. Differential Revision: https://reviews.llvm.org/D23704 Differential Revision: https://reviews.llvm.org/D23705 llvm-svn: 279326
* [GraphWriter] Change GraphWriter to use NodeRef in GraphTraitsTim Shen2016-08-171-0/+1
| | | | | | | | | | | | | | | Summary: This is part of the "NodeType* -> NodeRef" migration. Notice that since GraphWriter prints object address as identity, I added a static_assert on NodeRef to be a pointer type. Reviewers: dblaikie Subscribers: llvm-commits, MatzeB Differential Revision: https://reviews.llvm.org/D23580 llvm-svn: 278966
* CodeExtractor : Add ability to preserve profile data.Sean Silva2016-08-021-0/+6
| | | | | | | | | | | 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-6/+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/+6
| | | | | | | | | | | 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
* Fixed MSVC unresolved symbol error due to an incorrectly declared externSimon Pilgrim2016-06-281-1/+1
| | | | llvm-svn: 274007
* [BFI/MBFI]: cfg graph view with color scheme Xinliang David Li2016-06-281-1/+9
| | | | | | | | | | 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-4/+3
| | | | | | | | | 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-47/+11
| | | | | | | | | | | 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]: code cleanup Xinliang David Li2016-06-281-4/+9
| | | | | | | | Expose getBPI interface from BFI impl and use it in graph viewer. This eliminates the dependency on old PM interface. llvm-svn: 273967
* [MBFI]: Add a new suboption for graph viewerXinliang David Li2016-06-221-3/+19
| | | | | | | | | -view-machine-block-freq-propagation-dags currently support integer and fraction as the suboptions. This patch adds the 'count' suboption to display actual profile count if available. llvm-svn: 273460
* [MBFI]: show branch probability in DOT graphXinliang David Li2016-06-221-0/+18
| | | | | | Differential Revision: http://reviews.llvm.org/D21596 llvm-svn: 273430
* Add an option to enable MBFI dot viewer for a given functionXinliang David Li2016-06-221-1/+6
| | | | llvm-svn: 273366
* Clang format change /NFCXinliang David Li2016-06-211-35/+27
| | | | llvm-svn: 273335
* CodeGen: Avoid ilist iterator implicit conversions in a few more places, NFCDuncan P. N. Exon Smith2015-10-091-1/+1
| | | | llvm-svn: 249880
* 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
* 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] Remove potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-1/+2
| | | | | | | | | | | | define below all header includes in the lib/CodeGen/... tree. While the current modules implementation doesn't check for this kind of ODR violation yet, it is likely to grow support for it in the future. It also removes one layer of macro pollution across all the included headers. Other sub-trees will follow. llvm-svn: 206837
* Reapply "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith2014-04-211-3/+9
| | | | | | | | | 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-9/+3
| | | | | | This reverts commit r206704, as expected. llvm-svn: 206707
* Reapply "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith2014-04-191-3/+9
| | | | | | | | | | | | | | | | | | | | | 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-9/+3
| | | | | | | | | | | 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-3/+9
| | | | | | | | | | | | | | | | | | | 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-9/+3
| | | | | | | | | 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-3/+9
| | | | | | | | | | | | | | 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-9/+3
| | | | | | | | | | | 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-3/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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-10/+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
* blockfreq: Use const in MachineBlockFrequencyInfoDuncan P. N. Exon Smith2014-03-251-1/+1
| | | | | | <rdar://problem/14292693> llvm-svn: 204740
* [block-freq] Rename getEntryFrequency() -> getEntryFreq() to match ↵Michael Gottesman2013-12-141-2/+2
| | | | | | getBlockFreq() in all *BlockFrequencyInfo*. llvm-svn: 197304
* [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/+16
| | | | | | BlockFrequencyInfo that were added to BlockFrequencyImpl in r197285 and r197284. llvm-svn: 197287
* Fixed various whitespace/spelling/80+ issues.Michael Gottesman2013-12-031-9/+16
| | | | llvm-svn: 196310
* Added MachineBlockFrequencyInfo::view for displaying the block frequency ↵Michael Gottesman2013-12-031-0/+107
| | | | | | | | | | | | 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. This is the MI version of r194654. llvm-svn: 196183
* 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
OpenPOWER on IntegriCloud