aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp
AgeCommit message (Collapse)AuthorFilesLines
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
2014-04-25blockfreq: Expose getPackagedNode()Duncan P. N. Exon Smith1-24/+1
Make `getPackagedNode()` a member function of `BlockFrequencyInfoImplBase` so that it's available for templated code. <rdar://problem/14292693> llvm-svn: 207183
2014-04-25blockfreq: Store the header with the membersDuncan P. N. Exon Smith1-2/+2
<rdar://problem/14292693> llvm-svn: 207182
2014-04-25blockfreq: Encapsulate LoopData::HeaderDuncan P. N. Exon Smith1-14/+12
<rdar://problem/14292693> llvm-svn: 207181
2014-04-25blockfreq: Use LoopData directlyDuncan P. N. Exon Smith1-30/+28
Instead of passing around loop headers, pass around `LoopData` directly. <rdar://problem/14292693> llvm-svn: 207179
2014-04-25blockfreq: Use a std::list for LoopsDuncan P. N. Exon Smith1-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
2014-04-22blockfreq: Skip irreducible backedges inside functionsDuncan P. N. Exon Smith1-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
2014-04-22blockfreq: Rename PackagedLoops => LoopsDuncan P. N. Exon Smith1-1/+1
llvm-svn: 206859
2014-04-22blockfreq: Use a pointer for ContainingLoop tooDuncan P. N. Exon Smith1-9/+9
llvm-svn: 206858
2014-04-22blockfreq: Use pointers to loops instead of an indexDuncan P. N. Exon Smith1-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
2014-04-22blockfreq: Implement clear() explicitlyDuncan P. N. Exon Smith1-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
2014-04-22blockfreq: Rename PackagedLoopData => LoopDataDuncan P. N. Exon Smith1-7/+7
No functionality change. llvm-svn: 206855
2014-04-22[Modules] Remove potential ODR violations by sinking the DEBUG_TYPEChandler Carruth1-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
2014-04-21blockfreq: Some cleanup of UnsignedFloatDuncan P. N. Exon Smith1-22/+19
Change `PositiveFloat` to `UnsignedFloat`, and fix some of the comments to indicate that it's disappearing eventually. llvm-svn: 206771
2014-04-21Reapply "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith1-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
2014-04-19Revert "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith1-932/+0
This reverts commit r206704, as expected. llvm-svn: 206707
2014-04-19Reapply "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith1-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
2014-04-19Revert "blockfreq: Rewrite BlockFrequencyInfoImpl" (#2)Duncan P. N. Exon Smith1-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
2014-04-18Reapply "blockfreq: Rewrite BlockFrequencyInfoImpl" (#2)Duncan P. N. Exon Smith1-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
2014-04-18Revert "blockfreq: Rewrite BlockFrequencyInfoImpl" (#2)Duncan P. N. Exon Smith1-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
2014-04-18Fixing MSVC after r206622?Duncan P. N. Exon Smith1-0/+2
llvm-svn: 206626
2014-04-18Reapply "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith1-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
2014-04-18Revert "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith1-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
generated by cgit v1.1 at 2025-10-17 03:12:01 +0000