summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Support/BlockFrequency.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [block-freq] Add a right shift to BlockFrequency that saturates at 1.Michael Gottesman2013-12-141-0/+12
| | | | llvm-svn: 197302
* [block-freq] Remove old BlockFrequency entry frequency and printing code.Michael Gottesman2013-12-141-21/+0
| | | | llvm-svn: 197297
* [block-freq] Add BlockFrequency::scale that returns a remainder from the ↵Michael Gottesman2013-11-171-38/+60
| | | | | | | | | | | | | | | | | | | | | | | | | | division and make the private scale in BlockFrequency more performant. This change is the first in a series of changes improving LLVM's Block Frequency propogation implementation to not lose probability mass in branchy code when propogating block frequency information from a basic block to its successors. This patch is a simple infrastructure improvement that does not actually modify the block frequency algorithm. The specific changes are: 1. Changes the division algorithm used when scaling block frequencies by branch probabilities to a short division algorithm. This gives us the remainder for free as well as provides a nice speed boost. When I benched the old routine and the new routine on a Sandy Bridge iMac with disabled turbo mode performing 8192 iterations on an array of length 32768, I saw ~600% increase in speed in mean/median performance. 2. Exposes a scale method that returns a remainder. This is important so we can ensure that when we scale a block frequency by some branch probability BP = N/D, the remainder from the division by D can be retrieved and propagated to other children to ensure no probability mass is lost (more to come on this). llvm-svn: 194950
* Fix a bad overflow check pointed out by Ben.Jakob Stoklund Olesen2013-06-281-4/+2
| | | | llvm-svn: 185226
* Eliminate an assortment of undefined behavior.Jakob Stoklund Olesen2013-06-281-1/+5
| | | | | | Hopefully, this fixes the PPC64 buildbots. llvm-svn: 185218
* Stylistic cleanups, no functional change.Jakob Stoklund Olesen2013-06-281-10/+7
| | | | | | | | - Use static functions instead of anonymous namespace. - Appease the Doxygen lobby. - Use 0-based induction variable. llvm-svn: 185185
* Add a division operator to BlockFrequency.Jakob Stoklund Olesen2013-06-281-23/+35
| | | | | | | | | | | Allow a BlockFrequency to be divided by a non-zero BranchProbability with saturating arithmetic. This will be used to compute the frequency of a loop header given the probability of leaving the loop. Our long division algorithm already saturates on overflow, so that was a freebie. llvm-svn: 185184
* Print block frequencies in decimal form.Jakob Stoklund Olesen2013-06-251-1/+10
| | | | | | | | | This is easier to read than the internal fixed-point representation. If anybody knows the correct algorithm for converting fixed-point numbers to base 10, feel free to fix it. llvm-svn: 184881
* Revert "BlockFrequency: Saturate at 1 instead of 0 when multiplying a ↵Benjamin Kramer2013-06-211-10/+2
| | | | | | | | frequency with a branch probability." This reverts commit r184584. Breaks PPC selfhost. llvm-svn: 184590
* BlockFrequency: Saturate at 1 instead of 0 when multiplying a frequency with ↵Benjamin Kramer2013-06-211-2/+10
| | | | | | | | | | | | | | | a branch probability. Zero is used by BlockFrequencyInfo as a special "don't know" value. It also causes a sink for frequencies as you can't ever get off a zero frequency with more multiplies. This recovers a 10% regression on MultiSource/Benchmarks/7zip. A zero frequency was propagated into an inner loop causing excessive spilling. PR16402. llvm-svn: 184584
* BlockFrequency: Use a smarter overflow check.Benjamin Kramer2011-10-271-4/+8
| | | | | | This trades one 64 bit div for one 64 bit mul and some arithmetic. llvm-svn: 143106
* Optimize 96-bit division a little bit.Jakub Staszak2011-07-271-2/+3
| | | | llvm-svn: 136222
* Move static methods to the anonymous namespace.Jakub Staszak2011-07-271-2/+7
| | | | llvm-svn: 136221
* Add BlockFrequency class.Jakub Staszak2011-07-251-0/+120
llvm-svn: 135992
OpenPOWER on IntegriCloud