summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/MachineBlockFrequencyInfo.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Sink all InitializePasses.h includesReid Kleckner2019-11-131-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This file lists every pass in LLVM, and is included by Pass.h, which is very popular. Every time we add, remove, or rename a pass in LLVM, it caused lots of recompilation. I found this fact by looking at this table, which is sorted by the number of times a file was changed over the last 100,000 git commits multiplied by the number of object files that depend on it in the current checkout: recompiles touches affected_files header 342380 95 3604 llvm/include/llvm/ADT/STLExtras.h 314730 234 1345 llvm/include/llvm/InitializePasses.h 307036 118 2602 llvm/include/llvm/ADT/APInt.h 213049 59 3611 llvm/include/llvm/Support/MathExtras.h 170422 47 3626 llvm/include/llvm/Support/Compiler.h 162225 45 3605 llvm/include/llvm/ADT/Optional.h 158319 63 2513 llvm/include/llvm/ADT/Triple.h 140322 39 3598 llvm/include/llvm/ADT/StringRef.h 137647 59 2333 llvm/include/llvm/Support/Error.h 131619 73 1803 llvm/include/llvm/Support/FileSystem.h Before this change, touching InitializePasses.h would cause 1345 files to recompile. After this change, touching it only causes 550 compiles in an incremental rebuild. Reviewers: bkramer, asbirlea, bollu, jdoerfert Differential Revision: https://reviews.llvm.org/D70211
* [PGO][PGSO] SizeOpts changes.Hiroshi Yamauchi2019-10-281-0/+7
| | | | | | | | | | | | | | | Summary: (Split of off D67120) SizeOpts/MachineSizeOpts changes for profile guided size optimization. (A second try after previously committed as r375254 and reverted as r375375.) Subscribers: mgorny, hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D69409
* Reverted r375254 as it has broken some build bots for a long time.Vladimir Vereschaka2019-10-201-7/+0
| | | | llvm-svn: 375375
* [PGO][PGSO] SizeOpts changes.Hiroshi Yamauchi2019-10-181-0/+7
| | | | | | | | | | | | | | | | | Summary: (Split of off D67120) SizeOpts/MachineSizeOpts changes for profile guided size optimization. Reviewers: davidxl Subscribers: mgorny, hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D69070 llvm-svn: 375254
* Update the file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-191-4/+3
| | | | | | | | | | | | | | | | | to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351636
* MachineFunction: Return reference from getFunction(); NFCMatthias Braun2017-12-151-4/+4
| | | | | | The Function can never be nullptr so we can return a reference. llvm-svn: 320884
* 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
OpenPOWER on IntegriCloud