aboutsummaryrefslogtreecommitdiffstats
path: root/lib/Analysis/BranchProbabilityInfo.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Make the unreachable probability much much heavier. The previousChandler Carruth2011-12-221-2/+3
| | | | | | | | | | probability wouldn't be considered "hot" in some weird loop structures or other compounding probability patterns. This makes it much harder to confuse, but isn't really a principled fix. I'd actually like it if we could model a zero probability, as it would make this much easier to reason about. Suggestions for how to do this better are welcome. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147142 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove all remaining uses of Value::getNameStr().Benjamin Kramer2011-11-151-3/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144648 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix the API usage in loop probability heuristics. It was incorrectlyChandler Carruth2011-10-251-15/+8
| | | | | | | | | | | | | | | classifying many edges as exiting which were in fact not. These mainly formed edges into sub-loops. It was also not correctly classifying all returning edges out of loops as leaving the loop. With this match most of the loop heuristics are more rational. Several serious regressions on loop-intesive benchmarks like perlbench's loop tests when built with -enable-block-placement are fixed by these updated heuristics. Unfortunately they in turn uncover some other regressions. There are still several improvemenst that should be made to loop heuristics including trip-count, and early back-edge management. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142917 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove return heuristics from the static branch probabilities, andChandler Carruth2011-10-241-73/+76
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | introduce no-return or unreachable heuristics. The return heuristics from the Ball and Larus paper don't work well in practice as they pessimize early return paths. The only good hitrate return heuristics are those for: - NULL return - Constant return - negative integer return Only the last of these three can possibly require significant code for the returning block, and even the last is fairly rare and usually also a constant. As a consequence, even for the cold return paths, there is little code on that return path, and so little code density to be gained by sinking it. The places where sinking these blocks is valuable (inner loops) will already be weighted appropriately as the edge is a loop-exit branch. All of this aside, early returns are nearly as common as all three of these return categories, and should actually be predicted as taken! Rather than muddy the waters of the static predictions, just remain silent on returns and let the CFG itself dictate any layout or other issues. However, the return heuristic was flagging one very important case: unreachable. Unfortunately it still gave a 1/4 chance of the branch-to-unreachable occuring. It also didn't do a rigorous job of finding those blocks which post-dominate an unreachable block. This patch builds a more powerful analysis that should flag all branches to blocks known to then reach unreachable. It also has better worst-case runtime complexity by not looping through successors for each block. The previous code would perform an N^2 walk in the event of a single entry block branching to N successors with a switch where each successor falls through to the next and they finally fall through to a return. Test case added for noreturn heuristics. Also doxygen comments improved along the way. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142793 91177308-0d34-0410-b5e6-96231b3b80d8
* Simplify the design of BranchProbabilityInfo by collapsing it intoChandler Carruth2011-10-241-135/+90
| | | | | | | | | | | | | a single class. Previously it was split between two classes, one internal and one external. The concern seemed to center around exposing the weights used, but those can remain confined to the implementation file. Having a single class to maintain the state and analyses in use will also simplify several of the enhancements I want to make to our static heuristics. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142783 91177308-0d34-0410-b5e6-96231b3b80d8
* Tidy up a loop to be more idiomatic for LLVM's codebase, and remove someChandler Carruth2011-10-231-18/+9
| | | | | | | extraneous whitespace. Trying to clean-up this pass as much as I can before I start making functional changes. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142780 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach the BranchProbabilityInfo pass to print its results, and use thatChandler Carruth2011-10-231-2/+20
| | | | | | | | | | to bring it under direct test instead of merely indirectly testing it in the BlockFrequencyInfo pass. The next step is to start adding tests for the various heuristics employed, and to start fixing those heuristics once they're under test. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142778 91177308-0d34-0410-b5e6-96231b3b80d8
* Add compare operators to BranchProbability and use it to determine if an ↵Benjamin Kramer2011-10-231-8/+4
| | | | | | edge is hot. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142751 91177308-0d34-0410-b5e6-96231b3b80d8
* Extend the floating point heuristic to consider NaN checks unlikely.Benjamin Kramer2011-10-211-4/+17
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142687 91177308-0d34-0410-b5e6-96231b3b80d8
* BranchProbabilityInfo: floating point equality is unlikely.Benjamin Kramer2011-10-211-2/+34
| | | | | | This is from the same paper from Ball and Larus as the rest of the currently implemented heuristics. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142677 91177308-0d34-0410-b5e6-96231b3b80d8
* Generalize the reading of probability metadata to work for both branchesChandler Carruth2011-10-191-16/+24
| | | | | | | | | and switches, with arbitrary numbers of successors. Still optimized for the common case of 2 successors for a conditional branch. Add a test case for switch metadata showing up in the BlockFrequencyInfo pass. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142493 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach the BranchProbabilityInfo analysis pass to read any metadataChandler Carruth2011-10-191-0/+38
| | | | | | | | | | | encoding of probabilities. In the absense of metadata, it continues to fall back on static heuristics. This allows __builtin_expect, after lowering through llvm.expect a branch instruction's metadata, to actually enter the branch probability model. This is one component of resolving PR2577. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142492 91177308-0d34-0410-b5e6-96231b3b80d8
* Delete a dead member. Dunno if this was ever used, but the current codeChandler Carruth2011-10-161-6/+3
| | | | | | | directly manipulates the weights inside of the BranchProbabilityInfo that is passed in. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142163 91177308-0d34-0410-b5e6-96231b3b80d8
* Use canonical forms for the branch probability zero heutistic.Benjamin Kramer2011-09-041-25/+30
| | | | | | | | - Drop support for X >u 0, it's equivalent to X != 0 and should be canonicalized into the latter. - Add X < 1 -> unlikely, which is what instcombine canonicalizes X <= 0 into. - Add X > -1 -> likely, which is what instcombine canonicalizes X >= 0 into. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139110 91177308-0d34-0410-b5e6-96231b3b80d8
* Change SmallVector to SmallPtrSet in BranchProbabilityInfo. Handle cases whereJakub Staszak2011-08-011-15/+15
| | | | | | | one than one successor goes to the same block. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136638 91177308-0d34-0410-b5e6-96231b3b80d8
* Do not handle cases with >= and <= predicates.Jakub Staszak2011-07-311-7/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136588 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove untrue comment.Jakub Staszak2011-07-311-3/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136587 91177308-0d34-0410-b5e6-96231b3b80d8
* Do not handle case where LHS is equal to zero, because InstCombiner always movesJakub Staszak2011-07-311-24/+8
| | | | | | | it to RHS anyway. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136586 91177308-0d34-0410-b5e6-96231b3b80d8
* Add Zero Heurestics to BranchProbabilityInfo. If we compare value to zero weJakub Staszak2011-07-311-1/+91
| | | | | | | | | | | | | | decide whether condition is likely to be true this way: x == 0 -> false x < 0 -> false x <= 0 -> false x != 0 -> true x > 0 -> true x >= 0 -> true git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136583 91177308-0d34-0410-b5e6-96231b3b80d8
* Add more constantness in BranchProbabilityInfo.Jakub Staszak2011-07-291-10/+11
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136502 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove incEdgeWeight and decEdgeWeight. Set edge weight directly to avoidJakub Staszak2011-07-291-30/+35
| | | | | | | rounding errors. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136456 91177308-0d34-0410-b5e6-96231b3b80d8
* Change LBH_TAKEN_WEIGHT to 124 (from 128). Right now, sum ofJakub Staszak2011-07-281-4/+4
| | | | | | | | | LBH_TAKEN_WEIGHT + LBH_NONTAKEN_WEIGHT = 128 which in _most_ cases reduce number of rounding errors. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136428 91177308-0d34-0410-b5e6-96231b3b80d8
* Heuristics are in descending priority now. If we use one of them, skip the rest.Jakub Staszak2011-07-281-13/+23
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136402 91177308-0d34-0410-b5e6-96231b3b80d8
* Add InEdges (edges from header to the loop) in Loop Branch Heuristics, soJakub Staszak2011-07-281-0/+17
| | | | | | | | there is no frequency difference whether condition is in the header or in the latch. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136398 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove "LoopInfo.h" include from BranchProbabilityInfo.h.Jakub Staszak2011-07-161-0/+5
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135353 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix pointer heuristic. Check whether predicator is ICMP_NE instead of if it isJakub Staszak2011-07-151-2/+2
| | | | | | | not isEquality(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135296 91177308-0d34-0410-b5e6-96231b3b80d8
* Calculate backedge probability correctly.Jakub Staszak2011-06-231-24/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133776 91177308-0d34-0410-b5e6-96231b3b80d8
* Introduce BlockFrequency analysis for BasicBlocks.Jakub Staszak2011-06-231-0/+24
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133766 91177308-0d34-0410-b5e6-96231b3b80d8
* Introduce MachineBranchProbabilityInfo class, which has similar API toJakub Staszak2011-06-161-1/+1
| | | | | | | | | BranchProbabilityInfo (expect setEdgeWeight which is not available here). Branch Weights are kept in MachineBasicBlocks. To turn off this analysis set -use-mbpi=false. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133184 91177308-0d34-0410-b5e6-96231b3b80d8
* Move class into an anonymous namespace.Benjamin Kramer2011-06-131-1/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132925 91177308-0d34-0410-b5e6-96231b3b80d8
* Branch profiling: floating-point avoidance.Andrew Trick2011-06-111-54/+63
| | | | | | | | | | Patch by: Jakub Staszak! Introduces BranchProbability. Changes unsigned to uint32_t all over and uint64_t only when overflow is expected. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132867 91177308-0d34-0410-b5e6-96231b3b80d8
* Fold assert-only-used variable into the assert.Nick Lewycky2011-06-041-2/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132620 91177308-0d34-0410-b5e6-96231b3b80d8
* Missing include of climits in the new BranchProbability pass.Andrew Trick2011-06-041-0/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132616 91177308-0d34-0410-b5e6-96231b3b80d8
* New BranchProbabilityInfo analysis. Patch by Jakub Staszak!Andrew Trick2011-06-041-0/+348
BranchProbabilityInfo provides an interface for IR passes to query the likelihood that control follows a CFG edge. This patch provides an initial implementation of static branch predication that will populate BranchProbabilityInfo for branches with no external profile information using very simple heuristics. It currently isn't hooked up to any external profile data, so static prediction does all the work. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132613 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.1 at 2024-12-27 18:18:38 +0000