summaryrefslogtreecommitdiff
path: root/lib/CodeGen/MachineBranchProbabilityInfo.cpp
Commit message (Collapse)AuthorAge
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-02
| | | | | | | | | | | | | | | | | | | | | into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171366 91177308-0d34-0410-b5e6-96231b3b80d8
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-03
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169131 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a quadratic algorithm in MachineBranchProbabilityInfo.Jakob Stoklund Olesen2012-08-20
| | | | | | | | | | | | The getSumForBlock function was quadratic in the number of successors because getSuccWeight would perform a linear search for an already known iterator. This patch was originally committed as r161460, but reverted again because of assertion failures. Now that duplicate Machine CFG edges have been eliminated, this works properly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162233 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert "Fix a quadratic algorithm in MachineBranchProbabilityInfo."Jakob Stoklund Olesen2012-08-08
| | | | | | It caused an assertion failure when compiling consumer-typeset. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161463 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a quadratic algorithm in MachineBranchProbabilityInfo.Jakob Stoklund Olesen2012-08-08
| | | | | | | | The getSumForBlock function was quadratic in the number of successors because getSuccWeight would perform a linear search for an already known iterator. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161460 91177308-0d34-0410-b5e6-96231b3b80d8
* Add some constantness to BranchProbabilityInfo and BlockFrequnencyInfo.Jakub Staszak2011-12-20
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146986 91177308-0d34-0410-b5e6-96231b3b80d8
* Unweaken vtables as per ↵David Blaikie2011-12-20
| | | | | | http://llvm.org/docs/CodingStandards.html#ll_virtual_anch git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146960 91177308-0d34-0410-b5e6-96231b3b80d8
* Reuse the logic in getEdgeProbability within getHotSucc in order toChandler Carruth2011-11-14
| | | | | | | | | | correctly handle blocks whose successor weights sum to more than UINT32_MAX. This is slightly less efficient, but the entire thing is already linear on the number of successors. Calling it within any hot routine is a mistake, and indeed no one is calling it. It also simplifies the code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144527 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix an overflow bug in MachineBranchProbabilityInfo. This pass relied onChandler Carruth2011-11-14
| | | | | | | | | | | | | | | | | | | | | | | | | the sum of the edge weights not overflowing uint32, and crashed when they did. This is generally safe as BranchProbabilityInfo tries to provide this guarantee. However, the CFG can get modified during codegen in a way that grows the *sum* of the edge weights. This doesn't seem unreasonable (imagine just adding more blocks all with the default weight of 16), but it is hard to come up with a case that actually triggers 32-bit overflow. Fortuately, the single-source GCC build is good at this. The solution isn't very pretty, but its no worse than the previous code. We're already summing all of the edge weights on each query, we can sum them, check for an overflow, compute a scale, and sum them again. I've included a *greatly* reduced test case out of the GCC source that triggers it. It's a pretty lame test, as it clearly is just barely triggering the overflow. I'd like to have something that is much more definitive, but I don't understand the fundamental pattern that triggers an explosion in the edge weight sums. The buggy code is duplicated within this file. I'll colapse them into a single implementation in a subsequent commit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144526 91177308-0d34-0410-b5e6-96231b3b80d8
* Use BranchProbability compare operators.Benjamin Kramer2011-10-28
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143190 91177308-0d34-0410-b5e6-96231b3b80d8
* Introduce MachineBranchProbabilityInfo class, which has similar API toJakub Staszak2011-06-16
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