aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp
AgeCommit message (Collapse)AuthorFilesLines
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
2015-06-17Add documentation for new backedge mass propagation in irregular loops.Diego Novillo1-3/+2
Tweak test cases and rename headerIndexFor -> getHeaderIndex. llvm-svn: 239915
2015-06-16Fix PR 23525 - Separate header mass propagation in irregular loops.Diego Novillo1-21/+59
Summary: When propagating mass through irregular loops, the mass flowing through each loop header may not be equal. This was causing wrong frequencies to be computed for irregular loop headers. Fixed by keeping track of masses flowing through each of the headers in an irregular loop. To do this, we now keep track of per-header backedge weights. After the loop mass is distributed through the loop, the backedge weights are used to re-distribute the loop mass to the loop headers. Since each backedge will have a mass proportional to the different branch weights, the loop headers will end up with a more approximate weight distribution (as opposed to the current distribution that assumes that every loop header is the same). Reviewers: dexonsmith Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D10348 llvm-svn: 239843
2015-04-01Remove 4,096 loop scale limitation.Diego Novillo1-21/+33
Summary: This is part 1 of fixes to address the problems described in https://llvm.org/bugs/show_bug.cgi?id=22719. The restriction to limit loop scales to 4,096 does not really prevent overflows anymore, as the underlying algorithm has changed and does not seem to suffer from this problem. Additionally, artificially restricting loop scales to such a low number skews frequency information, making loops of equal hotness appear to have very different hotness properties. The only loops that are artificially restricted to a scale of 4096 are infinite loops (those loops with an exit mass of 0). This prevents infinite loops from skewing the frequencies of other regions in the CFG. At the end of propagation, frequencies are scaled to values that take no more than 64 bits to represent. When the range of frequencies to be represented fits within 61 bits, it pushes up the scaling factor to a minimum of 8 to better distinguish small frequency values. Otherwise, small frequency values are all saturated down at 1. Tested on x86_64. Reviewers: dexonsmith Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8718 llvm-svn: 233826
2014-12-05BFI: Saturate when combining edges to a successorDuncan P. N. Exon Smith1-4/+17
When a loop gets bundled up, its outgoing edges are quite large, and can just barely overflow 64-bits. If one successor has multiple incoming edges -- and that successor is getting all the incoming mass -- combining just its edges can overflow. Handle that by saturating rather than asserting. This fixes PR21622. llvm-svn: 223500
2014-10-13[modules] Stop excluding Support/Debug.h from the Support module. This headerRichard Smith1-1/+0
has been modular since r206822, and excluding it was leading to workarounds such as the one in r219592, which this change removes. llvm-svn: 219593
2014-10-12[Modules] Add some missing includes to make files compile stand-alone.Benjamin Kramer1-1/+1
llvm-svn: 219592
2014-10-06BFI: Improve assertion message, since it's actually firingDuncan P. N. Exon Smith1-1/+2
This assertion is firing because -loop-unroll is failing to preserve -loop-info (see PR20987). Improve it. llvm-svn: 219130
2014-07-12BFI: Add constructor for WeightDuncan P. N. Exon Smith1-5/+1
llvm-svn: 212868
2014-07-12BFI: Clean up BlockMassDuncan P. N. Exon Smith1-10/+0
Implementation is small now -- the interesting logic was moved to `BranchProbability` a while ago. Move it into `bfi_detail` and get rid of the related TODOs. I was originally planning to define it within `BlockFrequencyInfoImpl` (or `BFIIBase`), but it seems cleaner in a namespace. Besides, `isPodLike` needs to be specialized before `BlockMass` can be used in some of the other data structures, and there isn't a clear way to do that. llvm-svn: 212866
2014-07-11BFI: Mark the end of namespacesDuncan P. N. Exon Smith1-1/+2
llvm-svn: 212861
2014-06-24Support: Move class ScaledNumberDuncan P. N. Exon Smith1-190/+0
ScaledNumber has been cleaned up enough to pull out of BFI now. Still work to do there (tests for shifting, bloated printing code, etc.), but it seems clean enough for its new home. llvm-svn: 211562
2014-06-24BFI: Un-floatify more languageDuncan P. N. Exon Smith1-23/+24
llvm-svn: 211561
2014-06-24Support: Extract ScaledNumbers::MinScale and MaxScaleDuncan P. N. Exon Smith1-10/+5
llvm-svn: 211558
2014-06-23BFI: Change language from "exponent" to "scale"Duncan P. N. Exon Smith1-8/+8
llvm-svn: 211557
2014-06-23BFI: Rename UnsignedFloat => ScaledNumberDuncan P. N. Exon Smith1-17/+17
A lot of the docs and API are out of date, but I'll leave that for a separate commit. llvm-svn: 211555
2014-06-20Support: Write ScaledNumber::getQuotient() and getProduct()Duncan P. N. Exon Smith1-91/+0
llvm-svn: 211409
2014-05-06blockfreq: Move include to .cppDuncan P. N. Exon Smith1-0/+1
llvm-svn: 208035
2014-04-29blockfreq: Defer to BranchProbability::scale()Duncan P. N. Exon Smith1-26/+0
`BlockMass` can now defer to `BranchProbability::scale()`. llvm-svn: 207547
2014-04-28blockfreq: Remove more extra typenames from r207438Duncan P. N. Exon Smith1-2/+2
llvm-svn: 207440
2014-04-28Reapply "blockfreq: Approximate irreducible control flow"Duncan P. N. Exon Smith1-20/+210
This reverts commit r207287, reapplying r207286. I'm hoping that declaring an explicit struct and instantiating `addBlockEdges()` directly works around the GCC crash from r207286. This is a lot more boilerplate, though. llvm-svn: 207438
2014-04-25Revert "blockfreq: Approximate irreducible control flow"Duncan P. N. Exon Smith1-210/+20
This reverts commit r207286. It causes an ICE on the cmake-llvm-x86_64-linux buildbot [1]: llvm/lib/Analysis/BlockFrequencyInfo.cpp: In lambda function: llvm/lib/Analysis/BlockFrequencyInfo.cpp:182:1: internal compiler error: in get_expr_operands, at tree-ssa-operands.c:1035 [1]: http://bb.pgr.jp/builders/cmake-llvm-x86_64-linux/builds/12093/steps/build_llvm/logs/stdio llvm-svn: 207287
2014-04-25blockfreq: Approximate irreducible control flowDuncan P. N. Exon Smith1-20/+210
Previously, irreducible backedges were ignored. With this commit, irreducible SCCs are discovered on the fly, and modelled as loops with multiple headers. This approximation specifies the headers of irreducible sub-SCCs as its entry blocks and all nodes that are targets of a backedge within it (excluding backedges within true sub-loops). Block frequency calculations act as if we insert a new block that intercepts all the edges to the headers. All backedges and entries to the irreducible SCC point to this imaginary block. This imaginary block has an edge (with even probability) to each header block. The result is now reasonable enough that I've added a number of testcases for irreducible control flow. I've outlined in `BlockFrequencyInfoImpl.h` ways to improve the approximation. <rdar://problem/14292693> llvm-svn: 207286
2014-04-25blockfreq: Further shift logic to LoopDataDuncan P. N. Exon Smith1-27/+12
Move a lot of the loop-related logic that was sprinkled around the code into `LoopData`. <rdar://problem/14292693> llvm-svn: 207258
2014-04-25blockfreq: Only one mass distribution per nodeDuncan P. N. Exon Smith1-61/+11
Remove the concepts of "forward" and "general" mass distributions, which was wrong. The split might have made sense in an early version of the algorithm, but it's definitely wrong now. <rdar://problem/14292693> llvm-svn: 207195
2014-04-25blockfreq: Document assertionDuncan P. N. Exon Smith1-1/+1
<rdar://problem/14292693> llvm-svn: 207194
2014-04-25blockfreq: Document high-level functionsDuncan P. N. Exon Smith1-1/+1
<rdar://problem/14292693> llvm-svn: 207191
2014-04-25blockfreq: Scale LoopData::Scale on the way downDuncan P. N. Exon Smith1-23/+12
Rather than scaling loop headers and then scaling all the loop members by the header frequency, scale `LoopData::Scale` itself, and scale the loop members by it. It's much more obvious what's going on this way, and doesn't cost any extra multiplies. <rdar://problem/14292693> llvm-svn: 207189
2014-04-25blockfreq: unwrapLoopPackage() => unwrapLoop()Duncan P. N. Exon Smith1-10/+8
<rdar://problem/14292693> llvm-svn: 207188
2014-04-25blockfreq: Pass the Loop directly into unwrapLoopPackage()Duncan P. N. Exon Smith1-6/+4
<rdar://problem/14292693> llvm-svn: 207187
2014-04-25blockfreq: Unwrap from LoopsDuncan P. N. Exon Smith1-4/+2
When unwrapping loops, just visit the loops rather than all nodes. <rdar://problem/14292693> llvm-svn: 207186
2014-04-25blockfreq: Separate unwrapLoops() from finalizeMetrics()Duncan P. N. Exon Smith1-5/+9
<rdar://problem/14292693> llvm-svn: 207185
generated by cgit v1.1 at 2025-10-15 06:00:50 +0000