summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp
Commit message (Collapse)AuthorAgeFilesLines
* 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
* blockfreq: Separate unwrapLoops() from finalizeMetrics()Duncan P. N. Exon Smith2014-04-251-5/+9
| | | | | | <rdar://problem/14292693> llvm-svn: 207185
* blockfreq: Expose getPackagedNode()Duncan P. N. Exon Smith2014-04-251-24/+1
| | | | | | | | | Make `getPackagedNode()` a member function of `BlockFrequencyInfoImplBase` so that it's available for templated code. <rdar://problem/14292693> llvm-svn: 207183
* blockfreq: Store the header with the membersDuncan P. N. Exon Smith2014-04-251-2/+2
| | | | | | <rdar://problem/14292693> llvm-svn: 207182
* blockfreq: Encapsulate LoopData::HeaderDuncan P. N. Exon Smith2014-04-251-14/+12
| | | | | | <rdar://problem/14292693> llvm-svn: 207181
* blockfreq: Use LoopData directlyDuncan P. N. Exon Smith2014-04-251-30/+28
| | | | | | | | Instead of passing around loop headers, pass around `LoopData` directly. <rdar://problem/14292693> llvm-svn: 207179
* blockfreq: Use a std::list for LoopsDuncan P. N. Exon Smith2014-04-251-1/+1
| | | | | | | | | | | | As pointed out by David Blaikie in code review, a `std::list<T>` is simpler than a `std::vector<std::unique_ptr<T>>`. Another option is a `std::deque<T>` (which allocates in chunks), but I'd like to leave open the option of inserting in the middle of the sequence for handling irreducible control flow on the fly. <rdar://problem/14292693> llvm-svn: 207177
* blockfreq: Skip irreducible backedges inside functionsDuncan P. N. Exon Smith2014-04-221-1/+1
| | | | | | | | | | | | The branch that skips irreducible backedges was only active when propagating mass at the top-level. In particular, when propagating mass through a loop recognized by `LoopInfo` with irreducible control flow inside, irreducible backedges would not be skipped. Not sure where that idea came from, but the result was that mass was lost until after loop exit. Added a testcase that covers this case. llvm-svn: 206860
* blockfreq: Rename PackagedLoops => LoopsDuncan P. N. Exon Smith2014-04-221-1/+1
| | | | llvm-svn: 206859
* blockfreq: Use a pointer for ContainingLoop tooDuncan P. N. Exon Smith2014-04-221-9/+9
| | | | llvm-svn: 206858
* blockfreq: Use pointers to loops instead of an indexDuncan P. N. Exon Smith2014-04-221-4/+5
| | | | | | | | | | | | | Store pointers directly to loops inside the nodes. This could have been done without changing the type stored in `std::vector<>`. However, rather than computing the number of loops before constructing them (which `LoopInfo` doesn't provide directly), I've switched to a `vector<unique_ptr<LoopData>>`. This adds some heap overhead, but the number of loops is typically small. llvm-svn: 206857
* blockfreq: Implement clear() explicitlyDuncan P. N. Exon Smith2014-04-221-1/+5
| | | | | | | | | This was implicitly with copy assignment before, which fails to actually clear `std::vector<>`'s heap storage. Move assignment would work, but since MSVC can't imply those anyway, explicitly `clear()`-ing members makes more sense. llvm-svn: 206856
* blockfreq: Rename PackagedLoopData => LoopDataDuncan P. N. Exon Smith2014-04-221-7/+7
| | | | | | No functionality change. llvm-svn: 206855
* [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
* blockfreq: Some cleanup of UnsignedFloatDuncan P. N. Exon Smith2014-04-211-22/+19
| | | | | | | Change `PositiveFloat` to `UnsignedFloat`, and fix some of the comments to indicate that it's disappearing eventually. llvm-svn: 206771
* Reapply "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith2014-04-211-0/+932
| | | | | | | | | 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-932/+0
| | | | | | This reverts commit r206704, as expected. llvm-svn: 206707
* Reapply "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith2014-04-191-0/+932
| | | | | | | | | | | | | | | | | | | | | 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-933/+0
| | | | | | | | | | | 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-0/+933
| | | | | | | | | | | | | | | | | | | 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-933/+0
| | | | | | | | | 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
* Fixing MSVC after r206622?Duncan P. N. Exon Smith2014-04-181-0/+2
| | | | llvm-svn: 206626
* Reapply "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith2014-04-181-0/+931
| | | | | | | | | | | | | | 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-931/+0
| | | | | | | | | | | 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
OpenPOWER on IntegriCloud