[SHT_LLVM_BB_ADDR_MAP] Adds pretty printing of BFI and BPI for PGO Analysis Map in tools. (#82292)

Primary change is to add a flag `--pretty-pgo-analysis-map` to
llvm-readobj and llvm-objdump that

[SHT_LLVM_BB_ADDR_MAP] Adds pretty printing of BFI and BPI for PGO Analysis Map in tools. (#82292)

Primary change is to add a flag `--pretty-pgo-analysis-map` to
llvm-readobj and llvm-objdump that prints block frequencies and branch
probabilities in the same manner as BFI and BPI respectively. This can
be helpful if you are manually inspecting the outputs from the tools.

In order to print, I moved the `printBlockFreqImpl` function from
Analysis to Support and renamed it to `printRelativeBlockFreq`.

show more ...

Avoid BlockFrequency overflow problems (#66280)

Multiplying raw block frequency with an integer carries a high risk
of overflow.

- Add `BlockFrequency::mul` return an std::optional with the prod

Avoid BlockFrequency overflow problems (#66280)

Multiplying raw block frequency with an integer carries a high risk
of overflow.

- Add `BlockFrequency::mul` return an std::optional with the product
or `nullopt` to indicate an overflow.
- Fix two instances where overflow was likely.

show more ...

[NFC][BlockFrequency] Move operator definitions into header

While BlockFrequency::operator+= is a very simple operation, it's
definition is present in another TU which means that it doesn't get
inli

[NFC][BlockFrequency] Move operator definitions into header

While BlockFrequency::operator+= is a very simple operation, it's
definition is present in another TU which means that it doesn't get
inlined in non-LTO builds. This means that there is some performance
left on the table in those builds, as this operator is called many
times.

This patch moves that operator (and a few others) into the
BlockFrequency.h header which gives a small speedup (~0.1%):
https://llvm-compile-time-tracker.com/compare.php?from=6ee594be53e7efaa12086ad20f0d0268092a4c73&to=6ac6cd99e211fae5ae5de41ad608604aa22f1882&stat=instructions%3Au

Differential Revision: https://reviews.llvm.org/D152781

show more ...

[llvm] Cleanup header dependencies in ADT and Support

The cleanup was manual, but assisted by "include-what-you-use". It consists in

1. Removing unused forward declaration. No impact expected.
2. R

[llvm] Cleanup header dependencies in ADT and Support

The cleanup was manual, but assisted by "include-what-you-use". It consists in

1. Removing unused forward declaration. No impact expected.
2. Removing unused headers in .cpp files. No impact expected.
3. Removing unused headers in .h files. This removes implicit dependencies and
is generally considered a good thing, but this may break downstream builds.
I've updated llvm, clang, lld, lldb and mlir deps, and included a list of the
modification in the second part of the commit.
4. Replacing header inclusion by forward declaration. This has the same impact
as 3.

Notable changes:

- llvm/Support/TargetParser.h no longer includes llvm/Support/AArch64TargetParser.h nor llvm/Support/ARMTargetParser.h
- llvm/Support/TypeSize.h no longer includes llvm/Support/WithColor.h
- llvm/Support/YAMLTraits.h no longer includes llvm/Support/Regex.h
- llvm/ADT/SmallVector.h no longer includes llvm/Support/MemAlloc.h nor llvm/Support/ErrorHandling.h

You may need to add some of these headers in your compilation units, if needs be.

As an hint to the impact of the cleanup, running

clang++ -E -Iinclude -I../llvm/include ../llvm/lib/Support/*.cpp -std=c++14 -fno-rtti -fno-exceptions | wc -l

before: 8000919 lines
after: 7917500 lines

Reduced dependencies also helps incremental rebuilds and is more ccache
friendly, something not shown by the above metric :-)

Discourse thread on the topic: https://llvm.discourse.group/t/include-what-you-use-include-cleanup/5831

show more ...

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the ne

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the new license. We checked this carefully with the
Foundation's lawyer and we believe this is the correct approach.

Essentially, all code in the project is now made available by the LLVM
project under our new license, so you will see that the license headers
include that license only. Some of our contributors have contributed
code under our old license, and accordingly, we have retained a copy of
our old license notice in the top-level files in each project and
repository.

llvm-svn: 351636

show more ...

Remove redundant includes from lib/Support.

llvm-svn: 320627

Add - and -= operators to BlockFrequency using saturating arithmetic.

llvm-svn: 250077

Turn const/const& into value type for BlockFrequency in functions of this class. Also fix a naming issue. NFC.

llvm-svn: 250074

Fixed a bug that BranchProbability is not defined in BlockFrequency.cpp. NFC.

llvm-svn: 247376

Pass BranchProbability/BlockMass by value instead of const& as they are small. NFC.

llvm-svn: 247357

blockfreq: Defer to BranchProbability::scale() (again)

Change `BlockFrequency` to defer to `BranchProbability::scale()` and
`BranchProbability::scaleByInverse()`.

This removes `BlockFrequency::scal

blockfreq: Defer to BranchProbability::scale() (again)

Change `BlockFrequency` to defer to `BranchProbability::scale()` and
`BranchProbability::scaleByInverse()`.

This removes `BlockFrequency::scale()` from its API (and drops the
ability to see the remainder), but the only user was the unit tests. If
some code in the future needs an API that exposes the remainder, we can
add something to `BranchProbability`, but I find that unlikely.

llvm-svn: 207550

show more ...

[block-freq] Add a right shift to BlockFrequency that saturates at 1.

llvm-svn: 197302

[block-freq] Remove old BlockFrequency entry frequency and printing code.

llvm-svn: 197297

[block-freq] Add BlockFrequency::scale that returns a remainder from the division and make the private scale in BlockFrequency more performant.

This change is the first in a series of changes improv

[block-freq] Add BlockFrequency::scale that returns a remainder from the 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

show more ...

Fix a bad overflow check pointed out by Ben.

llvm-svn: 185226

Eliminate an assortment of undefined behavior.

Hopefully, this fixes the PPC64 buildbots.

llvm-svn: 185218

Stylistic cleanups, no functional change.

- 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.

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 heade

Add a division operator to BlockFrequency.

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

show more ...

Print block frequencies in decimal form.

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, f

Print block frequencies in decimal form.

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

show more ...

Revert "BlockFrequency: Saturate at 1 instead of 0 when multiplying a 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 a branch probability.

Zero is used by BlockFrequencyInfo as a special "don't know" value. It also
causes a sink for frequ

BlockFrequency: Saturate at 1 instead of 0 when multiplying a frequency with 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

show more ...

BlockFrequency: Use a smarter overflow check.

This trades one 64 bit div for one 64 bit mul and some arithmetic.

llvm-svn: 143106

Optimize 96-bit division a little bit.

llvm-svn: 136222

Move static methods to the anonymous namespace.

llvm-svn: 136221

Add BlockFrequency class.

llvm-svn: 135992