aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/BranchProbabilityInfo.cpp
AgeCommit message (Collapse)AuthorFilesLines
2020-11-06[BranchProbabilityInfo] Get rid of MaxSuccIdx. NFCYevgeny Rouban1-25/+22
This refactoring allows to eliminate the MaxSuccIdx map proposed in the commit a7b662d0. The idea is to remove probabilities for a block BB for all its successors one by one from first, second, ... till N-th until they are defined in Probs. This works because probabilities for the block are set at once for all its successors from number 0 to N-1 and the rest are removed if there were stale probs. The protected method setEdgeProbability(), which set probabilities for individual successor, is removed. This makes it clear that the probabilities are set in bulk by the public method with the same name. Reviewed By: kazu, MaskRay Differential Revision: https://reviews.llvm.org/D90837
2020-10-31Revert "Use uint64_t for branch weights instead of uint32_t"Arthur Eubanks1-31/+23
This reverts commit 10f2a0d662d8d72eaac48d3e9b31ca8dc90df5a4. More uint64_t overflows.
2020-10-30Use uint64_t for branch weights instead of uint32_tArthur Eubanks1-23/+31
CallInst::updateProfWeight() creates branch_weights with i64 instead of i32. To be more consistent everywhere and remove lots of casts from uint64_t to uint32_t, use i64 for branch_weights. Reviewed By: davidxl Differential Revision: https://reviews.llvm.org/D88609
2020-10-27[BranchProbabilityInfo] Make MaxSuccIdx[Src] efficient and add a comment ↵Fangrui Song1-4/+4
about the subtle eraseBlock. NFC Follow-up to D90272.
2020-10-27[BranchProbabilityInfo] Fix eraseBlockKazu Hirata1-2/+13
This patch ensures that BranchProbabilityInfo::eraseBlock(BB) deletes all entries in Probs associated with with BB. Without this patch, stale entries for BB may remain in Probs after eraseBlock(BB), leading to a situation where a newly created basic block has an edge probability associated with it even before the pass responsible for creating the basic block adds any edge probability to it. Consider the current implementation of eraseBlock(BB): for (const_succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { auto MapI = Probs.find(std::make_pair(BB, I.getSuccessorIndex())); if (MapI != Probs.end()) Probs.erase(MapI); } Notice that it uses succ_begin(BB) and succ_end(BB), which are based on BB->getTerminator(). This means that if the terminator changes between calls to setEdgeProbability and eraseBlock, then we may not examine all pairs associated with BB. This is exactly what happens in MaybeMergeBasicBlockIntoOnlyPred, which merges basic blocks A into B if A is the sole predecessor of B, and B is the sole successor of A. It replaces the terminator of A with UnreachableInst before (indirectly) calling eraseBlock(A). The patch fixes the problem by keeping track of all edge probablities entered with setEdgeProbability in a map from BasicBlock* to a successor index. Differential Revision: https://reviews.llvm.org/D90272
2020-10-27Revert "Use uint64_t for branch weights instead of uint32_t"Nico Weber1-3/+6
This reverts commit e5766f25c62c185632e3a75bf45b313eadab774b. Makes clang assert when building Chromium, see https://crbug.com/1142813 for a repro.
2020-10-26Use uint64_t for branch weights instead of uint32_tArthur Eubanks1-6/+3
CallInst::updateProfWeight() creates branch_weights with i64 instead of i32. To be more consistent everywhere and remove lots of casts from uint64_t to uint32_t, use i64 for branch_weights. Reviewed By: davidxl Differential Revision: https://reviews.llvm.org/D88609
2020-08-17Revert "[BPI] Improve static heuristics for integer comparisons"Dávid Bolvanský1-17/+10
This reverts commit 50c743fa713002fe4e0c76d23043e6c1f9e9fe6f. Patch will be split to smaller ones.
2020-08-13[BPI] Improve static heuristics for integer comparisonsDávid Bolvanský1-10/+17
Similarly as for pointers, even for integers a == b is usually false. GCC also uses this heuristic. Reviewed By: ebrevnov Differential Revision: https://reviews.llvm.org/D85781
2020-08-13Revert "[BPI] Improve static heuristics for integer comparisons"Dávid Bolvanský1-17/+10
This reverts commit 44587e2f7e732604cd6340061d40ac21e7e188e5. Sanitizer tests need to be updated.
2020-08-13[BPI] Improve static heuristics for integer comparisonsDávid Bolvanský1-10/+17
Similarly as for pointers, even for integers a == b is usually false. GCC also uses this heuristic. Reviewed By: ebrevnov Differential Revision: https://reviews.llvm.org/D85781
2020-08-13Revert "[BPI] Improve static heuristics for integer comparisons"Dávid Bolvanský1-17/+10
This reverts commit 385c9d673f217e176b18e7bf6fe055154ac589c6.
2020-08-13[BPI] Improve static heuristics for integer comparisonsDávid Bolvanský1-10/+17
Similarly as for pointers, even for integers a == b is usually false. GCC also uses this heuristic. Reviewed By: ebrevnov Differential Revision: https://reviews.llvm.org/D85781
2020-08-11[BPI] Teach BPI about bcmp functionDávid Bolvanský1-1/+2
bcmp is similar to memcmp
2020-08-05[BPI][NFC] Unify handling of normal and SCC based loopsEvgeniy Brevnov1-27/+78
This is one more NFC part extracted from D79485. Normal and SCC based loops have very different representation and have to be handled separatly each time we deal with loops. D79485 is going to introduce much more extensive use of loops what will be problematic with out this change. Reviewed By: davidxl Differential Revision: https://reviews.llvm.org/D84838
2020-08-01Use llvm::is_contained where appropriate (NFC)Kazu Hirata1-2/+1
Use llvm::is_contained where appropriate (NFC) Reviewed By: kazu Differential Revision: https://reviews.llvm.org/D85083
2020-07-28[BPI] Fix memory leak reported by sanitizer botsEvgeniy Brevnov1-1/+1
There is a silly mistake where release() is used instead of reset() for free resources of unique pointer. Reviewed By: ebrevnov Differential Revision: https://reviews.llvm.org/D84747
2020-07-28[BPI][NFC] Consolidate code to deal with SCCs under a dedicated data structure.Evgeniy Brevnov1-58/+106
In order to facilitate review of D79485 here is a small NFC change which restructures code around handling of SCCs in BPI. Reviewed By: davidxl Differential Revision: https://reviews.llvm.org/D84514
2020-07-10[BPI] Compile time improvement when erasing blocks (NFC)Teresa Johnson1-4/+4
Summary: eraseBlock is trying to erase all probability info for the given BB. This info is stored in a DenseMap organized like so: using Edge = std::pair<const BasicBlock *, unsigned>; DenseMap<Edge, BranchProbability> Probs; where the unsigned in the Edge key is the successor id. It was walking through every single map entry, checking if the BB in the key's pair matched the given BB. Much more efficient is to do what another method (getEdgeProbability) was already doing, which is to walk the successors of the BB, and simply do a map lookup on the key formed from each <BB, successor id> pair. Doing this dropped the overall compile time for a file containing a very large function by around 32%. Reviewers: davidxl, xur Subscribers: llvm-commits, hiraditya Tags: #llvm Differential Revision: https://reviews.llvm.org/D83596
2020-06-04Extend InvokeInst !prof branch_weights metadata to unwind branchesYevgeny Rouban1-1/+2
Allow InvokeInst to have the second optional prof branch weight for its unwind branch. InvokeInst is a terminator with two successors. It might have its unwind branch taken many times. If so the BranchProbabilityInfo unwind branch heuristic can be inaccurate. This patch allows a higher accuracy calculated with both branch weights set. Changes: - A new section about InvokeInst is added to the BranchWeightMetadata page. It states the old information that missed in the doc and adds new about the second branch weight. - Verifier is changed to allow either 1 or 2 branch weights for InvokeInst. - A new test is written for BranchProbabilityInfo to demonstrate the main improvement of the simple fix in calcMetadataWeights(). - Several new testcases are created for Inliner. Those check that both weights are accounted for invoke instruction weight calculation. - PGOUseFunc::setBranchWeights() is fixed to be applicable to InvokeInst. Reviewers: davidxl, reames, xur, yamauchi Tags: #llvm Differential Revision: https://reviews.llvm.org/D80618
2020-06-02[BrachProbablityInfo] Proportional distribution of reachable probabilitiesYevgeny Rouban1-28/+62
When fixing probability of unreachable edges in BranchProbabilityInfo::calcMetadataWeights() proportionally distribute remainder probability over the reachable edges. The old implementation distributes the remainder probability evenly. See examples in the fixed tests. Reviewers: yamauchi, ebrevnov Tags: #llvm Differential Revision: https://reviews.llvm.org/D80611
2020-06-02[BrachProbablityInfo] Rename loop variables. NFCYevgeny Rouban1-17/+17
2020-05-21[BrachProbablityInfo] Set edge probabilities at once and fix ↵Yevgeny Rouban1-38/+84
calcMetadataWeights() Hide the method that allows setting probability for particular edge and introduce a public method that sets probabilities for all outgoing edges at once. Setting individual edge probability is error prone. More over it is difficult to check that the total probability is 1.0 because there is no easy way to know when the user finished setting all the probabilities. Related bug is fixed in BranchProbabilityInfo::calcMetadataWeights(). Changing unreachable branch probabilities to raw(1) and distributing the rest (oldProbability - raw(1)) over the reachable branches could introduce total probability inaccuracy bigger than 1/numOfBranches. Reviewers: yamauchi, ebrevnov Tags: #llvm Differential Revision: https://reviews.llvm.org/D79396
2020-05-13Revert "[BrachProbablityInfo] Set edge probabilities at once. NFC."Reid Kleckner1-66/+33
This reverts commit eef95f2746c3347b8dad19091ffb82a88d73acd3. The new assertion about branch propability sums does not hold.
2020-05-13[BrachProbablityInfo] Set edge probabilities at once. NFC.Yevgeny Rouban1-33/+66
Hide the method that allows setting probability for particular edge and introduce a public method that sets probabilities for all outgoing edges at once. Setting individual edge probability is error prone. More over it is difficult to check that the total probability is 1.0 because there is no easy way to know when the user finished setting all the probabilities. Reviewers: yamauchi, ebrevnov Tags: #llvm Differential Revision: https://reviews.llvm.org/D79396
2020-04-30[BPI] Incorrect probability reported in case of mulptiple edges.Evgeniy Brevnov1-1/+3
Summary: By design 'BranchProbabilityInfo:: getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const' should return sum of probabilities over all edges from Src to Dst. Current implementation is buggy and returns 1/num_of_successors if probabilities are not explicitly set. Note current implementation of BPI printing has an issue as well and annotates each edge with sum of probabilities over all ages from one basic block to another. That's why 30% probability reported (instead of 10%) in the lit test. This is not urgent issue since only printing is affected. Note also current implementation assumes that either all or none edges have probabilities set. This is not the only place which uses such assumption. At least we should assert that in verifier. In addition we can think on a more robust API of BPI which would prevent situations. Reviewers: skatkov, yrouban, taewookoh Reviewed By: skatkov Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D79071
2020-04-30[BPI][NFC] Reuse post dominantor tree from analysis manager when availableEvgeniy Brevnov1-7/+19
Summary: Currenlty BPI unconditionally creates post dominator tree each time. While this is not incorrect we can save compile time by reusing existing post dominator tree (when it's valid) provided by analysis manager. Reviewers: skatkov, taewookoh, yrouban Reviewed By: skatkov Subscribers: hiraditya, steven_wu, dexonsmith, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D78987
2020-04-07[BPI] Clear handles when releasing memory (NFC)Nikita Popov1-0/+1
This reduces max-rss of sqlite compilation by 2.5%.
2020-03-25[CFG/BasicBlock] Rename succ_const to const_succ. [NFC]Alina Sbirlea1-7/+7
Summary: Rename `succ_const_iterator` to `const_succ_iterator` and `succ_const_range` to `const_succ_range` for consistency with the predecessor iterators, and the corresponding iterators in MachineBasicBlock. Reviewers: nicholas, dblaikie, nlewycky Subscribers: hiraditya, bmahjour, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D75952
2020-01-17[BrachProbablityInfo] Add invalidate method.Alina Sbirlea1-0/+9
Summary: Add invalidate method for BrachProbablityInfo. Reviewers: Eugene.Zelenko, chandlerc Subscribers: hiraditya, sanjoy.google, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D72815
2019-12-02Reland "b19ec1eb3d0c [BPI] Improve unreachable/ColdCall heurstics to handle ↵Taewook Oh1-57/+75
loops." Summary: b19ec1eb3d0c has been reverted because of the test failures with PowerPC targets. This patch addresses the issues from the previous commit. Test Plan: ninja check-all. Confirmed that CodeGen/PowerPC/pr36292.ll and CodeGen/PowerPC/sms-cpy-1.ll pass Subscribers: llvm-commits
2019-11-27Revert b19ec1eb3d0ctaewookoh1-75/+57
Summary: This reverts commit b19ec1eb3d0c as it fails powerpc tests Subscribers: llvm-commits
2019-11-27[BPI] Improve unreachable/ColdCall heurstics to handle loops.Taewook Oh1-57/+75
Summary: While updatePostDominatedByUnreachable attemps to find basic blocks that are post-domianted by unreachable blocks, it currently cannot handle loops precisely, because it doesn't use the actual post dominator tree analysis but relies on heuristics of visiting basic blocks in post-order. More precisely, when the entire loop is post-dominated by the unreachable block, current algorithm fails to detect the entire loop as post-dominated by the unreachable because when the algorithm reaches to the loop latch it fails to tell all its successors (including the loop header) will "eventually" be post-domianted by the unreachable block, because the algorithm hasn't visited the loop header yet. This makes BPI for the loop latch to assume that loop backedges are taken with 100% of probability. And because of this, block frequency info sometimes marks virtually dead loops (which are post dominated by unreachable blocks) super hot, because 100% backedge-taken probability makes the loop iteration count the max value. updatePostDominatedByColdCall has the exact same problem as well. To address this problem, this patch makes PostDominatedByUnreachable/PostDominatedByColdCall to be computed with the actual post-dominator tree. Reviewers: skatkov, chandlerc, manmanren Reviewed By: skatkov Subscribers: manmanren, vsk, apilipenko, Carrot, qcolombet, hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D70104
2019-11-14Add missing includes needed to prune LLVMContext.h include, NFCReid Kleckner1-0/+1
These are a pre-requisite to removing #include "llvm/Support/Options.h" from LLVMContext.h: https://reviews.llvm.org/D70280
2019-11-13Sink all InitializePasses.h includesReid Kleckner1-0/+7
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
2019-09-10[BPI] Adjust the probability for floating point unordered comparisonGuozhi Wei1-2/+14
Since NaN is very rare in normal programs, so the probability for floating point unordered comparison should be extremely small. Current probability is 3/8, it is too large, this patch changes it to a tiny number. Differential Revision: https://reviews.llvm.org/D65303 llvm-svn: 371541
2019-09-07Change TargetLibraryInfo analysis passes to always require FunctionTeresa Johnson1-1/+2
Summary: This is the first change to enable the TLI to be built per-function so that -fno-builtin* handling can be migrated to use function attributes. See discussion on D61634 for background. This is an enabler for fixing handling of these options for LTO, for example. This change should not affect behavior, as the provided function is not yet used to build a specifically per-function TLI, but rather enables that migration. Most of the changes were very mechanical, e.g. passing a Function to the legacy analysis pass's getTLI interface, or in Module level cases, adding a callback. This is similar to the way the per-function TTI analysis works. There was one place where we were looking for builtins but not in the context of a specific function. See FindCXAAtExit in lib/Transforms/IPO/GlobalOpt.cpp. I'm somewhat concerned my workaround could provide the wrong behavior in some corner cases. Suggestions welcome. Reviewers: chandlerc, hfinkel Subscribers: arsenm, dschuff, jvesely, nhaehnle, mehdi_amini, javed.absar, sbc100, jgravelle-google, eraman, aheejin, steven_wu, george.burgess.iv, dexonsmith, jfb, asbirlea, gchatelet, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D66428 llvm-svn: 371284
2019-02-15[BPI] Look through bitcasts in calcZeroHeuristicSam Parker1-1/+7
Constant hoisting may have hidden a constant behind a bitcast so that it isn't folded into its users. However, this prevents BPI from calculating some of its heuristics that are based upon constant values. So, I've added a simple helper function to look through these casts. Differential Revision: https://reviews.llvm.org/D58166 llvm-svn: 354119
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-10-15[TI removal] Make variables declared as `TerminatorInst` and initializedChandler Carruth1-5/+5
by `getTerminator()` calls instead be declared as `Instruction`. This is the biggest remaining chunk of the usage of `getTerminator()` that insists on the narrow type and so is an easy batch of updates. Several files saw more extensive updates where this would cascade to requiring API updates within the file to use `Instruction` instead of `TerminatorInst`. All of these were trivial in nature (pervasively using `Instruction` instead just worked). llvm-svn: 344502
2018-06-15[BPI] Remove unnecessary std::listBenjamin Kramer1-5/+4
vector is sufficient here. No functionality change intended. llvm-svn: 334865
2018-06-08[BPI] Apply invoke heuristic before loop branch heuristicArtur Pilipenko1-11/+8
Currently the loop branch heuristic is applied before the invoke heuristic which makes us overestimate the probability of the unwind destination of invokes inside loops. This in turn makes us grossly underestimate the frequencies of loops with invokes. Reviewed By: skatkov, vsk Differential Revision: https://reviews.llvm.org/D47371 llvm-svn: 334285
2018-05-17Require DominatorTree when requiring/preserving LoopInfo in the old pass managerMikael Holmen1-0/+5
Summary: Require DominatorTree when requiring/preserving LoopInfo in the old pass manager BreakCriticalEdges tries to keep LoopInfo and DominatorTree updated if they exist. However, since commit r321653 and r321805, to update LoopInfo we must have a DominatorTree, or we will hit an assert. To fix this we now make a couple of passes that only required/preserved LoopInfo also require DominatorTree. This solves PR37334. Reviewers: eli.friedman, efriedma Reviewed By: efriedma Subscribers: efriedma, llvm-commits Differential Revision: https://reviews.llvm.org/D46829 llvm-svn: 332583
2018-05-14Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen1-8/+10
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-10[STLExtras] Add distance() for ranges, pred_size(), and succ_size()Vedant Kumar1-2/+1
This commit adds a wrapper for std::distance() which works with ranges. As it would be a common case to write `distance(predecessors(BB))`, this also introduces `pred_size()` and `succ_size()` helpers to make that easier to write. Differential Revision: https://reviews.llvm.org/D46668 llvm-svn: 332057
2018-05-01Remove \brief commands from doxygen comments.Adrian Prantl1-9/+9
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-03-02Fix more spelling mistakes in comments of LLVM Analysis passesVedant Kumar1-1/+1
Patch by Reshabh Sharma! Differential Revision: https://reviews.llvm.org/D43939 llvm-svn: 326601
2018-02-23[BPI] Detect branches in loops that make themselves not takenJohn Brawn1-14/+135
If we have a loop like this: int n = 0; while (...) { if (++n >= MAX) { n = 0; } } then the body of the 'if' statement will only be executed once every MAX iterations. Detect this by looking for branches in loops where taking the branch makes the branch condition evaluate to 'not taken' in the next iteration of the loop, and reduce the probability of such branches. This slightly improves EEMBC benchmarks on cortex-m4/cortex-m33 due to making better choices in if-conversion, but has no effect on any other cpu/benchmark that I could detect. Differential Revision: https://reviews.llvm.org/D35804 llvm-svn: 325925
2017-11-01[BranchProbabilityInfo] Handle irreducible loops.Geoff Berry1-10/+80
Summary: Compute the strongly connected components of the CFG and fall back to use these for blocks that are in loops that are not detected by LoopInfo when computing loop back-edge and exit branch probabilities. Reviewers: dexonsmith, davidxl Subscribers: mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D39385 llvm-svn: 317094
2017-08-26Add options to dump block frequency/branch probability info in text.Hiroshi Yamauchi1-0/+15
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
generated by cgit v1.1 at 2025-10-10 06:32:28 +0000