aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp
AgeCommit message (Collapse)AuthorFilesLines
2024-02-27[SHT_LLVM_BB_ADDR_MAP] Adds pretty printing of BFI and BPI for PGO Analysis ↵Micah Weston1-15/+0
Map in tools. (#82292) Primary change is to add a flag `--pretty-pgo-analysis-map` to llvm-readobj and llvm-objdump that prints block frequencies and branch probabilities in the same manner as BFI and BPI respectively. This can be helpful if you are manually inspecting the outputs from the tools. In order to print, I moved the `printBlockFreqImpl` function from Analysis to Support and renamed it to `printRelativeBlockFreq`.
2023-10-24BlockFrequencyInfoImpl: Avoid big numbers, increase precision for small spreadsMatthias Braun1-20/+14
BlockFrequencyInfo calculates block frequencies as Scaled64 numbers but as a last step converts them to unsigned 64bit integers (`BlockFrequency`). This improves the factors picked for this conversion so that: * Avoid big numbers close to UINT64_MAX to avoid users overflowing/saturating when adding multiply frequencies together or when multiplying with integers. This leaves the topmost 10 bits unused to allow for some room. * Spread the difference between hottest/coldest block as much as possible to increase precision. * If the hot/cold spread cannot be represented loose precision at the lower end, but keep the frequencies at the upper end for hot blocks differentiable.
2023-10-05BlockFrequencyInfo: Add PrintBlockFreq helper (#67512)Matthias Braun1-12/+12
- Refactor the (Machine)BlockFrequencyInfo::printBlockFreq functions into a `PrintBlockFreq()` function returning a `Printable` object. This simplifies usage as it can be directly piped to a `raw_ostream` like `dbgs() << PrintBlockFreq(MBFI, Freq) << '\n';`. - Previously there was an interesting behavior where `BlockFrequencyInfoImpl` stores frequencies both as a `Scaled64` number and as an `uint64_t`. Most algorithms use the `BlockFrequency` abstraction with the integers, the print function for basic blocks printed the `Scaled64` number potentially showing higher accuracy than was used by the algorithm. This changes things to only print `BlockFrequency` values. - Replace some instances of `dbgs() << Freq.getFrequency()` with the new function.
2023-10-05Use BlockFrequency type in more places (NFC) (#68266)Matthias Braun1-14/+11
The `BlockFrequency` class abstracts `uint64_t` frequency values. Use it more consistently in various APIs and disable implicit conversion to make usage more consistent and explicit. - Use `BlockFrequency Freq` parameter for `setBlockFreq`, `getProfileCountFromFreq` and `setBlockFreqAndScale` functions. - Return `BlockFrequency` in `getEntryFreq()` functions. - While on it change some `const BlockFrequency& Freq` parameters to plain `BlockFreqency Freq`. - Mark `BlockFrequency(uint64_t)` constructor as explicit. - Add missing `BlockFrequency::operator!=`. - Remove `uint64_t BlockFreqency::getMaxFrequency()`. - Add `BlockFrequency BlockFrequency::max()` function.
2023-06-27[llvm] Move AttributeMask to a separate headerElliot Goodrich1-0/+1
Move `AttributeMask` out of `llvm/IR/Attributes.h` to a new file `llvm/IR/AttributeMask.h`. After doing this we can remove the `#include <bitset>` and `#include <set>` directives from `Attributes.h`. Since there are many headers including `Attributes.h`, but not needing the definition of `AttributeMask`, this causes unnecessary bloating of the translation units and slows down compilation. This commit adds in the include directive for `llvm/IR/AttributeMask.h` to the handful of source files that need to see the definition. This reduces the total number of preprocessing tokens across the LLVM source files in lib from (roughly) 1,917,509,187 to 1,902,982,273 - a reduction of ~0.76%. This should result in a small improvement in compilation time. Differential Revision: https://reviews.llvm.org/D153728
2023-02-12BlockFrequencyInfoImpl.cpp - add missing closing namespace comment. NFCSimon Pilgrim1-1/+1
Fixes clang-tidy llvm-namespace-comment warning
2023-01-28Use llvm::count{lr}_{zero,one} (NFC)Kazu Hirata1-1/+1
2022-12-06[ADT] Don't including None.h (NFC)Kazu Hirata1-1/+0
These source files no longer use None, so they do not need to include None.h. This is part of an effort to migrate from llvm::Optional to std::optional: https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716
2022-12-06[YAML] Convert Optional to std::optionalKrzysztof Parzyszek1-2/+3
2022-12-02[Analysis] Use std::nullopt instead of None (NFC)Kazu Hirata1-1/+1
This patch mechanically replaces None with std::nullopt where the compiler would warn if None were deprecated. The intent is to reduce the amount of manual work required in migrating from Optional to std::optional. This is part of an effort to migrate from llvm::Optional to std::optional: https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716
2022-06-03[llvm] Remove unneeded cl::ZeroOrMore for cl::opt options. NFCFangrui Song1-1/+1
Some cl::ZeroOrMore were added to avoid the `may only occur zero or one times!` error. More were added due to cargo cult. Since the error has been removed, cl::ZeroOrMore is unneeded. Also remove cl::init(false) while touching the lines.
2022-03-01Cleanup includes: LLVMAnalysisserge-sans-paille1-2/+1
Number of lines output by preprocessor: before: 1065940348 after: 1065307662 Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup Differential Revision: https://reviews.llvm.org/D120659
2021-11-14[NFC] Use Optional<ProfileCount> to model invalid countsMircea Trofin1-1/+1
ProfileCount could model invalid values, but a user had no indication that the getCount method could return bogus data. Optional<ProfileCount> addresses that, because the user must dereference the optional. In addition, the patch removes concept duplication. Differential Revision: https://reviews.llvm.org/D113839
2021-07-18[CSSPGO][NFC] Allow cl::ZeroOrMore for use-iterative-bfi-inferenceWenlei He1-1/+1
2021-06-11A post-processing for BFI inferencespupyrev1-0/+14
The current implementation for computing relative block frequencies does not handle correctly control-flow graphs containing irreducible loops. This results in suboptimally generated binaries, whose perf can be up to 5% worse than optimal. To resolve the problem, we apply a post-processing step, which iteratively updates block frequencies based on the frequencies of their predesessors. This corresponds to finding the stationary point of the Markov chain by an iterative method aka "PageRank computation". The algorithm takes at most O(|E| * IterativeBFIMaxIterations) steps but typically converges faster. It is turned on by passing option `use-iterative-bfi-inference` and applied only for functions containing profile data and irreducible loops. Tested on SPEC06/17, where it is helping to get correct profile counts for one of the binaries (403.gcc). In prod binaries, we've seen a speedup of up to 2%-5% for binaries containing functions with hot irreducible loops. Reviewed By: hoy, wenlei, davidxl Differential Revision: https://reviews.llvm.org/D103289
2021-05-07Internalize some cl::opt global variables or move them under namespace llvmFangrui Song1-0/+2
2020-02-04[BFI] Add a debug check for unknown block queries.Hiroshi Yamauchi1-1/+16
Summary: Add a debug check for frequency queries for unknown blocks (typically blocks that are created after BFI is computed but their frequencies are not communicated to BFI.) This is useful for detecting and debugging missed BFI updates. This is debug build only and disabled behind a flag. Reviewers: davidxl Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D73920
2019-04-24Add optional arg to profile count getters to filterXinliang David Li1-4/+7
synthetic profile count. Differential Revision: http://reviews.llvm.org/D61025 llvm-svn: 359131
2019-01-19Update the file headers across all of the LLVM projects in the monorepoChandler Carruth1-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
2018-09-27llvm::sort(C.begin(), C.end(), ...) -> llvm::sort(C, ...)Fangrui Song1-6/+6
Summary: The convenience wrapper in STLExtras is available since rL342102. Reviewers: dblaikie, javed.absar, JDevlieghere, andreadb Subscribers: MatzeB, sanjoy, arsenm, dschuff, mehdi_amini, sdardis, nemanjai, jvesely, nhaehnle, sbc100, jgravelle-google, eraman, aheejin, kbarton, JDevlieghere, javed.absar, gbedwell, jrtc27, mgrang, atanasyan, steven_wu, george.burgess.iv, dexonsmith, kristina, jsji, llvm-commits Differential Revision: https://reviews.llvm.org/D52573 llvm-svn: 343163
2018-08-16[BFI] Use rounding while computing profile counts.Easwaran Raman1-1/+3
Summary: Profile count of a block is computed by multiplying its block frequency by entry count and dividing the result by entry block frequency. Do rounded division in the last step and update test cases appropriately. Reviewers: davidxl Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D50822 llvm-svn: 339835
2018-05-14Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen1-38/+42
The DEBUG() macro is very generic so it might clash with other projects. The renaming was done as follows: - git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g' - git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM - Manual change to APInt - Manually chage DOCS as regex doesn't match it. In the transition period the DEBUG() macro is still present and aliased to the LLVM_DEBUG() one. Differential Revision: https://reviews.llvm.org/D43624 llvm-svn: 332240
2018-05-01Remove \brief commands from doxygen comments.Adrian Prantl1-6/+6
We've been running doxygen with the autobrief option for a couple of years now. This makes the \brief markers into our comments redundant. Since they are a visual distraction and we don't want to encourage more \brief markers in new code either, this patch removes them all. Patch produced by for i in $(git grep -l '\\brief'); do perl -pi -e 's/\\brief //g' $i & done Differential Revision: https://reviews.llvm.org/D46290 llvm-svn: 331272
2018-04-30IWYU for llvm-config.h in llvm, additions.Nico Weber1-0/+1
See r331124 for how I made a list of files missing the include. I then ran this Python script: for f in open('filelist.txt'): f = f.strip() fl = open(f).readlines() found = False for i in xrange(len(fl)): p = '#include "llvm/' if not fl[i].startswith(p): continue if fl[i][len(p):] > 'Config': fl.insert(i, '#include "llvm/Config/llvm-config.h"\n') found = True break if not found: print 'not found', f else: open(f, 'w').write(''.join(fl)) and then looked through everything with `svn diff | diffstat -l | xargs -n 1000 gvim -p` and tried to fix include ordering and whatnot. No intended behavior change. llvm-svn: 331184
2018-04-01[Analysis] Change std::sort to llvm::sort in response to r327219Mandeep Singh Grang1-6/+6
Summary: r327219 added wrappers to std::sort which randomly shuffle the container before sorting. This will help in uncovering non-determinism caused due to undefined sorting order of objects having the same key. To make use of that infrastructure we need to invoke llvm::sort instead of std::sort. Note: This patch is one of a series of patches to replace *all* std::sort to llvm::sort. Refer D44363 for a list of all the required patches. Reviewers: sanjoy, dexonsmith, hfinkel, RKSimon Reviewed By: dexonsmith Subscribers: david2050, llvm-commits Differential Revision: https://reviews.llvm.org/D44944 llvm-svn: 328925
2018-01-17Add a ProfileCount class to represent entry counts.Easwaran Raman1-1/+1
Summary: The class wraps a uint64_t and an enum to represent the type of profile count (real and synthetic) with some helper methods. Reviewers: davidxl Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D41883 llvm-svn: 322771
2017-11-02Irreducible loop metadata for more accurate block frequency under PGO.Hiroshi Yamauchi1-0/+21
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
2017-10-15Reverting r315590; it did not include changes for llvm-tblgen, which is ↵Aaron Ballman1-1/+1
causing link errors for several people. Error LNK2019 unresolved external symbol "public: void __cdecl `anonymous namespace'::MatchableInfo::dump(void)const " (?dump@MatchableInfo@?A0xf4f1c304@@QEBAXXZ) referenced in function "public: void __cdecl `anonymous namespace'::AsmMatcherEmitter::run(class llvm::raw_ostream &)" (?run@AsmMatcherEmitter@?A0xf4f1c304@@QEAAXAEAVraw_ostream@llvm@@@Z) llvm-tblgen D:\llvm\2017\utils\TableGen\AsmMatcherEmitter.obj 1 llvm-svn: 315854
2017-10-12[dump] Remove NDEBUG from test to enable dump methods [NFC]Don Hinton1-1/+1
Summary: Add LLVM_FORCE_ENABLE_DUMP cmake option, and use it along with LLVM_ENABLE_ASSERTIONS to set LLVM_ENABLE_DUMP. Remove NDEBUG and only use LLVM_ENABLE_DUMP to enable dump methods. Move definition of LLVM_ENABLE_DUMP from config.h to llvm-config.h so it'll be picked up by public headers. Differential Revision: https://reviews.llvm.org/D38406 llvm-svn: 315590
2017-07-21[Analysis] Fix some Clang-tidy modernize and Include What You Use warnings; ↵Eugene Zelenko1-13/+33
other minor fixes (NFC). llvm-svn: 308787
2017-01-28Cleanup dump() functions.Matthias Braun1-0/+2
We had various variants of defining dump() functions in LLVM. Normalize them (this should just consistently implement the things discussed in http://lists.llvm.org/pipermail/cfe-dev/2014-January/034323.html For reference: - Public headers should just declare the dump() method but not use LLVM_DUMP_METHOD or #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) - The definition of a dump method should look like this: #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) LLVM_DUMP_METHOD void MyClass::dump() { // print stuff to dbgs()... } #endif llvm-svn: 293359
2016-08-22[GraphTraits] Replace all NodeType usage with NodeRefTim Shen1-6/+3
This should finish the GraphTraits migration. Differential Revision: http://reviews.llvm.org/D23730 llvm-svn: 279475
2016-08-02CodeExtractor : Add ability to preserve profile data.Sean Silva1-1/+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
2016-08-01[ADT] NFC: Generalize GraphTraits requirement of "NodeType *" in interfaces ↵Tim Shen1-0/+1
to "NodeRef", and migrate SCCIterator.h to use NodeRef Summary: By generalize the interface, users are able to inject more flexible Node token into the algorithm, for example, a pair of vector<Node>* and index integer. Currently I only migrated SCCIterator to use NodeRef, but more is coming. It's a NFC. Reviewers: dblaikie, chandlerc Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D22937 llvm-svn: 277399
2016-08-01Revert r277313 and r277314.Sean Silva1-7/+1
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
2016-08-01CodeExtractor : Add ability to preserve profile data.Sean Silva1-1/+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
2016-06-22[BFI]: NFC refactoringXinliang David Li1-0/+16
move getBlockProfileCount implementation to the base class so that MBFI can share too. llvm-svn: 273442
2016-05-09fix spelling; NFCSanjay Patel1-2/+2
llvm-svn: 268929
2016-02-02Fix Clang-tidy readability-redundant-control-flow warnings; other minor fixes.Eugene Zelenko1-3/+13
Differential revision: http://reviews.llvm.org/D16793 llvm-svn: 259539
2016-01-29Annotate dump() methods with LLVM_DUMP_METHOD, addressing Richard Smith ↵Yaron Keren1-1/+1
r259192 post commit comment. clang part in r259232, this is the LLVM part of the patch. llvm-svn: 259240
2015-10-15Recommit r250345, it was reverted in r250366 to investigate a bot failure.Manman Ren1-0/+7
Our internal bot is still red after r250366. llvm-svn: 250415
2015-10-15Temporarily revert r250345 to sort out bot failure.Manman Ren1-7/+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
2015-10-14Update the branch weight metadata in JumpThreading pass.Cong Hou1-0/+7
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
2015-10-14Revert r250204 and r250240 due to bot failure. We failed to build PGO-ed clang.Manman Ren1-7/+0
llvm-svn: 250264
2015-10-13Update the branch weight metadata in JumpThreading pass.Cong Hou1-0/+7
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
2015-10-13Revert 250089 due to bot failure. It failed when building clang itself with PGO.Manman Ren1-7/+0
llvm-svn: 250145
2015-10-12Update the branch weight metadata in JumpThreading pass.Cong Hou1-0/+7
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
2015-09-08Fix PR 24723 - Handle 0-mass backedges in irreducible loopsDiego Novillo1-1/+4
This corner case happens when we have an irreducible SCC that is deeply nested. As we work down the tree, the backedge masses start getting smaller and smaller until we reach one that is down to 0. Since we distribute the incoming mass using the backedge masses as weight, the distributor does not allow zero weights. So, we simply ignore them (which will just use the weights of the non-zero nodes). llvm-svn: 247050
2015-06-23Revert r240137 (Fixed/added namespace ending comments using clang-tidy. NFC)Alexander Kornienko1-1/+1
Apparently, the style needs to be agreed upon first. llvm-svn: 240390
2015-06-19Fixed/added namespace ending comments using clang-tidy. NFCAlexander Kornienko1-1/+1
The patch is generated using this command: tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py -fix \ -checks=-*,llvm-namespace-comment -header-filter='llvm/.*|clang/.*' \ llvm/lib/ Thanks to Eugene Kosov for the original patch! llvm-svn: 240137
generated by cgit v1.1 at 2025-10-09 18:09:21 +0000