summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Cleanup dump() functions.Matthias Braun2017-01-281-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
* [GraphTraits] Replace all NodeType usage with NodeRefTim Shen2016-08-221-6/+3
| | | | | | | | This should finish the GraphTraits migration. Differential Revision: http://reviews.llvm.org/D23730 llvm-svn: 279475
* CodeExtractor : Add ability to preserve profile data.Sean Silva2016-08-021-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
* [ADT] NFC: Generalize GraphTraits requirement of "NodeType *" in interfaces ↵Tim Shen2016-08-011-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
* Revert r277313 and r277314.Sean Silva2016-08-011-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
* CodeExtractor : Add ability to preserve profile data.Sean Silva2016-08-011-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
* [BFI]: NFC refactoringXinliang David Li2016-06-221-0/+16
| | | | | | | move getBlockProfileCount implementation to the base class so that MBFI can share too. llvm-svn: 273442
* fix spelling; NFCSanjay Patel2016-05-091-2/+2
| | | | llvm-svn: 268929
* Fix Clang-tidy readability-redundant-control-flow warnings; other minor fixes.Eugene Zelenko2016-02-021-3/+13
| | | | | | Differential revision: http://reviews.llvm.org/D16793 llvm-svn: 259539
* Annotate dump() methods with LLVM_DUMP_METHOD, addressing Richard Smith ↵Yaron Keren2016-01-291-1/+1
| | | | | | | | r259192 post commit comment. clang part in r259232, this is the LLVM part of the patch. llvm-svn: 259240
* Recommit r250345, it was reverted in r250366 to investigate a bot failure.Manman Ren2015-10-151-0/+7
| | | | | | Our internal bot is still red after r250366. llvm-svn: 250415
* Temporarily revert r250345 to sort out bot failure.Manman Ren2015-10-151-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
* Update the branch weight metadata in JumpThreading pass.Cong Hou2015-10-141-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
* Revert r250204 and r250240 due to bot failure. We failed to build PGO-ed clang.Manman Ren2015-10-141-7/+0
| | | | llvm-svn: 250264
* Update the branch weight metadata in JumpThreading pass.Cong Hou2015-10-131-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
* Revert 250089 due to bot failure. It failed when building clang itself with PGO.Manman Ren2015-10-131-7/+0
| | | | llvm-svn: 250145
* Update the branch weight metadata in JumpThreading pass.Cong Hou2015-10-121-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
* Fix PR 24723 - Handle 0-mass backedges in irreducible loopsDiego Novillo2015-09-081-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
* Revert r240137 (Fixed/added namespace ending comments using clang-tidy. NFC)Alexander Kornienko2015-06-231-1/+1
| | | | | | Apparently, the style needs to be agreed upon first. llvm-svn: 240390
* Fixed/added namespace ending comments using clang-tidy. NFCAlexander Kornienko2015-06-191-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
* Add documentation for new backedge mass propagation in irregular loops.Diego Novillo2015-06-171-3/+2
| | | | | | Tweak test cases and rename headerIndexFor -> getHeaderIndex. llvm-svn: 239915
* Fix PR 23525 - Separate header mass propagation in irregular loops.Diego Novillo2015-06-161-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
* Remove 4,096 loop scale limitation.Diego Novillo2015-04-011-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
* BFI: Saturate when combining edges to a successorDuncan P. N. Exon Smith2014-12-051-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
* [modules] Stop excluding Support/Debug.h from the Support module. This headerRichard Smith2014-10-131-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
* [Modules] Add some missing includes to make files compile stand-alone.Benjamin Kramer2014-10-121-1/+1
| | | | llvm-svn: 219592
* BFI: Improve assertion message, since it's actually firingDuncan P. N. Exon Smith2014-10-061-1/+2
| | | | | | | This assertion is firing because -loop-unroll is failing to preserve -loop-info (see PR20987). Improve it. llvm-svn: 219130
* BFI: Add constructor for WeightDuncan P. N. Exon Smith2014-07-121-5/+1
| | | | llvm-svn: 212868
* BFI: Clean up BlockMassDuncan P. N. Exon Smith2014-07-121-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
* BFI: Mark the end of namespacesDuncan P. N. Exon Smith2014-07-111-1/+2
| | | | llvm-svn: 212861
* Support: Move class ScaledNumberDuncan P. N. Exon Smith2014-06-241-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
* BFI: Un-floatify more languageDuncan P. N. Exon Smith2014-06-241-23/+24
| | | | llvm-svn: 211561
* Support: Extract ScaledNumbers::MinScale and MaxScaleDuncan P. N. Exon Smith2014-06-241-10/+5
| | | | llvm-svn: 211558
* BFI: Change language from "exponent" to "scale"Duncan P. N. Exon Smith2014-06-231-8/+8
| | | | llvm-svn: 211557
* BFI: Rename UnsignedFloat => ScaledNumberDuncan P. N. Exon Smith2014-06-231-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
* Support: Write ScaledNumber::getQuotient() and getProduct()Duncan P. N. Exon Smith2014-06-201-91/+0
| | | | llvm-svn: 211409
* blockfreq: Move include to .cppDuncan P. N. Exon Smith2014-05-061-0/+1
| | | | llvm-svn: 208035
* blockfreq: Defer to BranchProbability::scale()Duncan P. N. Exon Smith2014-04-291-26/+0
| | | | | | `BlockMass` can now defer to `BranchProbability::scale()`. llvm-svn: 207547
* blockfreq: Remove more extra typenames from r207438Duncan P. N. Exon Smith2014-04-281-2/+2
| | | | llvm-svn: 207440
* Reapply "blockfreq: Approximate irreducible control flow"Duncan P. N. Exon Smith2014-04-281-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
* Revert "blockfreq: Approximate irreducible control flow"Duncan P. N. Exon Smith2014-04-251-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
* blockfreq: Approximate irreducible control flowDuncan P. N. Exon Smith2014-04-251-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
* blockfreq: Further shift logic to LoopDataDuncan P. N. Exon Smith2014-04-251-27/+12
| | | | | | | | | Move a lot of the loop-related logic that was sprinkled around the code into `LoopData`. <rdar://problem/14292693> llvm-svn: 207258
* blockfreq: Only one mass distribution per nodeDuncan P. N. Exon Smith2014-04-251-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
* blockfreq: Document assertionDuncan P. N. Exon Smith2014-04-251-1/+1
| | | | | | <rdar://problem/14292693> llvm-svn: 207194
* blockfreq: Document high-level functionsDuncan P. N. Exon Smith2014-04-251-1/+1
| | | | | | <rdar://problem/14292693> llvm-svn: 207191
* blockfreq: Scale LoopData::Scale on the way downDuncan P. N. Exon Smith2014-04-251-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
* blockfreq: unwrapLoopPackage() => unwrapLoop()Duncan P. N. Exon Smith2014-04-251-10/+8
| | | | | | <rdar://problem/14292693> llvm-svn: 207188
* blockfreq: Pass the Loop directly into unwrapLoopPackage()Duncan P. N. Exon Smith2014-04-251-6/+4
| | | | | | <rdar://problem/14292693> llvm-svn: 207187
* blockfreq: Unwrap from LoopsDuncan P. N. Exon Smith2014-04-251-4/+2
| | | | | | | | When unwrapping loops, just visit the loops rather than all nodes. <rdar://problem/14292693> llvm-svn: 207186
OpenPOWER on IntegriCloud