summaryrefslogtreecommitdiff
path: root/lib/Analysis/BlockFrequencyInfoImpl.cpp
Commit message (Collapse)AuthorAge
* Support: Move class ScaledNumberDuncan P. N. Exon Smith2014-06-24
| | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211562 91177308-0d34-0410-b5e6-96231b3b80d8
* BFI: Un-floatify more languageDuncan P. N. Exon Smith2014-06-24
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211561 91177308-0d34-0410-b5e6-96231b3b80d8
* Support: Extract ScaledNumbers::MinScale and MaxScaleDuncan P. N. Exon Smith2014-06-24
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211558 91177308-0d34-0410-b5e6-96231b3b80d8
* BFI: Change language from "exponent" to "scale"Duncan P. N. Exon Smith2014-06-23
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211557 91177308-0d34-0410-b5e6-96231b3b80d8
* BFI: Rename UnsignedFloat => ScaledNumberDuncan P. N. Exon Smith2014-06-23
| | | | | | | A lot of the docs and API are out of date, but I'll leave that for a separate commit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211555 91177308-0d34-0410-b5e6-96231b3b80d8
* Support: Write ScaledNumber::getQuotient() and getProduct()Duncan P. N. Exon Smith2014-06-20
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211409 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Move include to .cppDuncan P. N. Exon Smith2014-05-06
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@208035 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Defer to BranchProbability::scale()Duncan P. N. Exon Smith2014-04-29
| | | | | | `BlockMass` can now defer to `BranchProbability::scale()`. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207547 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Remove more extra typenames from r207438Duncan P. N. Exon Smith2014-04-28
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207440 91177308-0d34-0410-b5e6-96231b3b80d8
* Reapply "blockfreq: Approximate irreducible control flow"Duncan P. N. Exon Smith2014-04-28
| | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207438 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert "blockfreq: Approximate irreducible control flow"Duncan P. N. Exon Smith2014-04-25
| | | | | | | | | | | | 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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207287 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Approximate irreducible control flowDuncan P. N. Exon Smith2014-04-25
| | | | | | | | | | | | | | | | | | | | | | 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> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207286 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Further shift logic to LoopDataDuncan P. N. Exon Smith2014-04-25
| | | | | | | | | Move a lot of the loop-related logic that was sprinkled around the code into `LoopData`. <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207258 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Only one mass distribution per nodeDuncan P. N. Exon Smith2014-04-25
| | | | | | | | | | 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> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207195 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Document assertionDuncan P. N. Exon Smith2014-04-25
| | | | | | <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207194 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Document high-level functionsDuncan P. N. Exon Smith2014-04-25
| | | | | | <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207191 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Scale LoopData::Scale on the way downDuncan P. N. Exon Smith2014-04-25
| | | | | | | | | | | 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> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207189 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: unwrapLoopPackage() => unwrapLoop()Duncan P. N. Exon Smith2014-04-25
| | | | | | <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207188 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Pass the Loop directly into unwrapLoopPackage()Duncan P. N. Exon Smith2014-04-25
| | | | | | <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207187 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Unwrap from LoopsDuncan P. N. Exon Smith2014-04-25
| | | | | | | | When unwrapping loops, just visit the loops rather than all nodes. <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207186 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Separate unwrapLoops() from finalizeMetrics()Duncan P. N. Exon Smith2014-04-25
| | | | | | <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207185 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Expose getPackagedNode()Duncan P. N. Exon Smith2014-04-25
| | | | | | | | | Make `getPackagedNode()` a member function of `BlockFrequencyInfoImplBase` so that it's available for templated code. <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207183 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Store the header with the membersDuncan P. N. Exon Smith2014-04-25
| | | | | | <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207182 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Encapsulate LoopData::HeaderDuncan P. N. Exon Smith2014-04-25
| | | | | | <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207181 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Use LoopData directlyDuncan P. N. Exon Smith2014-04-25
| | | | | | | | Instead of passing around loop headers, pass around `LoopData` directly. <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207179 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Use a std::list for LoopsDuncan P. N. Exon Smith2014-04-25
| | | | | | | | | | | | 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> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207177 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Skip irreducible backedges inside functionsDuncan P. N. Exon Smith2014-04-22
| | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206860 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Rename PackagedLoops => LoopsDuncan P. N. Exon Smith2014-04-22
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206859 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Use a pointer for ContainingLoop tooDuncan P. N. Exon Smith2014-04-22
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206858 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Use pointers to loops instead of an indexDuncan P. N. Exon Smith2014-04-22
| | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206857 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Implement clear() explicitlyDuncan P. N. Exon Smith2014-04-22
| | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206856 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Rename PackagedLoopData => LoopDataDuncan P. N. Exon Smith2014-04-22
| | | | | | No functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206855 91177308-0d34-0410-b5e6-96231b3b80d8
* [Modules] Remove potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-22
| | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206837 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Some cleanup of UnsignedFloatDuncan P. N. Exon Smith2014-04-21
| | | | | | | Change `PositiveFloat` to `UnsignedFloat`, and fix some of the comments to indicate that it's disappearing eventually. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206771 91177308-0d34-0410-b5e6-96231b3b80d8
* Reapply "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith2014-04-21
| | | | | | | | | This reverts commit r206707, reapplying r206704. The preceding commit to CalcSpillWeights should have sorted out the failing buildbots. <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206766 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith2014-04-19
| | | | | | This reverts commit r206704, as expected. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206707 91177308-0d34-0410-b5e6-96231b3b80d8
* Reapply "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith2014-04-19
| | | | | | | | | | | | | | | | | | | | | 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> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206704 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert "blockfreq: Rewrite BlockFrequencyInfoImpl" (#2)Duncan P. N. Exon Smith2014-04-19
| | | | | | | | | | | 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.) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206677 91177308-0d34-0410-b5e6-96231b3b80d8
* Reapply "blockfreq: Rewrite BlockFrequencyInfoImpl" (#2)Duncan P. N. Exon Smith2014-04-18
| | | | | | | | | | | | | | | | | | | 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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206666 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert "blockfreq: Rewrite BlockFrequencyInfoImpl" (#2)Duncan P. N. Exon Smith2014-04-18
| | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206628 91177308-0d34-0410-b5e6-96231b3b80d8
* Fixing MSVC after r206622?Duncan P. N. Exon Smith2014-04-18
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206626 91177308-0d34-0410-b5e6-96231b3b80d8
* Reapply "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith2014-04-18
| | | | | | | | | | | | | | 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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206622 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith2014-04-18
| | | | | | | | | | | 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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206556 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Really fix r206548 (and r206549)Duncan P. N. Exon Smith2014-04-18
| | | | | | Turns out this code is dead. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206554 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Fixing MSVC after r206548?Duncan P. N. Exon Smith2014-04-18
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206549 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Rewrite BlockFrequencyInfoImplDuncan P. N. Exon Smith2014-04-18
Rewrite the shared implementation of BlockFrequencyInfo and MachineBlockFrequencyInfo entirely. The old implementation had a fundamental flaw: precision losses from nested loops (or very wide branches) compounded past loop exits (and convergence points). The @nested_loops testcase at the end of test/Analysis/BlockFrequencyAnalysis/basic.ll is motivating. This function has three nested loops, with branch weights in the loop headers of 1:4000 (exit:continue). The old analysis gives non-sensical results: Printing analysis 'Block Frequency Analysis' for function 'nested_loops': ---- Block Freqs ---- entry = 1.0 for.cond1.preheader = 1.00103 for.cond4.preheader = 5.5222 for.body6 = 18095.19995 for.inc8 = 4.52264 for.inc11 = 0.00109 for.end13 = 0.0 The new analysis gives correct results: Printing analysis 'Block Frequency Analysis' for function 'nested_loops': block-frequency-info: nested_loops - entry: float = 1.0, int = 8 - for.cond1.preheader: float = 4001.0, int = 32007 - for.cond4.preheader: float = 16008001.0, int = 128064007 - for.body6: float = 64048012001.0, int = 512384096007 - for.inc8: float = 16008001.0, int = 128064007 - for.inc11: float = 4001.0, int = 32007 - for.end13: float = 1.0, int = 8 Most importantly, the frequency leaving each loop matches the frequency entering it. The new algorithm leverages BlockMass and PositiveFloat to maintain precision, separates "probability mass distribution" from "loop scaling", and uses dithering to eliminate probability mass loss. I have unit tests for these types out of tree, but it was decided in the review to make the classes private to BlockFrequencyInfoImpl, and try to shrink them (or remove them entirely) in follow-up commits. The new algorithm should generally have a complexity advantage over the old. The previous algorithm was quadratic in the worst case. The new algorithm is still worst-case quadratic in the presence of irreducible control flow, but it's linear without it. The key difference between the old algorithm and the new is that control flow within a loop is evaluated separately from control flow outside, limiting propagation of precision problems and allowing loop scale to be calculated independently of mass distribution. Loops are visited bottom-up, their loop scales are calculated, and they are replaced by pseudo-nodes. Mass is then distributed through the function, which is now a DAG. Finally, loops are revisited top-down to multiply through the loop scales and the masses distributed to pseudo nodes. There are some remaining flaws. - Irreducible control flow isn't modelled correctly. LoopInfo and MachineLoopInfo ignore irreducible edges, so this algorithm will fail to scale accordingly. There's a note in the class documentation about how to get closer. See also the comments in test/Analysis/BlockFrequencyInfo/irreducible.ll. - Loop scale is limited to 4096 per loop (2^12) to avoid exhausting the 64-bit integer precision used downstream. - The "bias" calculation proposed on llvmdev is *not* incorporated here. This will be added in a follow-up commit, once comments from this review have been handled. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206548 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-16 19:26:52 +0000