[ThinLTO] Use DenseSet instead of SmallPtrSet for holding GUIDs

Should fix some more bot failures from r291108.
This should have been a DenseSet, since GUID is not a pointer type.
It caused some bot

[ThinLTO] Use DenseSet instead of SmallPtrSet for holding GUIDs

Should fix some more bot failures from r291108.
This should have been a DenseSet, since GUID is not a pointer type.
It caused some bots to fail, but for some reason I wasnt't getting a
build failure.

llvm-svn: 291115

show more ...

[ThinLTO] Subsume all importing checks into a single flag

Summary:
This adds a new summary flag NotEligibleToImport that subsumes
several existing flags (NoRename, HasInlineAsmMaybeReferencingIntern

[ThinLTO] Subsume all importing checks into a single flag

Summary:
This adds a new summary flag NotEligibleToImport that subsumes
several existing flags (NoRename, HasInlineAsmMaybeReferencingInternal
and IsNotViableToInline). It also subsumes the checking of references
on the summary that was being done during the thin link by
eligibleForImport() for each candidate. It is much more efficient to
do that checking once during the per-module summary build and record
it in the summary.

Reviewers: mehdi_amini

Subscribers: llvm-commits

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

llvm-svn: 291108

show more ...

[ThinLTO] Fix "||" vs "|" mixup.

The effect of the bug was that we would incorrectly create summaries
for global and weak values defined in module asm (since we were
essentially testing for bit 1 wh

[ThinLTO] Fix "||" vs "|" mixup.

The effect of the bug was that we would incorrectly create summaries
for global and weak values defined in module asm (since we were
essentially testing for bit 1 which is SF_Undefined, and the
RecordStreamer ignores local undefined references). This would have
resulted in conservatively disabling importing of anything referencing
globals and weaks defined in module asm. Added these cases to the test
which now fails without this bug fix.

Fixes PR31459.

llvm-svn: 290610

show more ...

IR: Function summary representation for type tests.

Each function summary has an attached list of type identifier GUIDs. The
idea is that during the regular LTO phase we would match these GUIDs to t

IR: Function summary representation for type tests.

Each function summary has an attached list of type identifier GUIDs. The
idea is that during the regular LTO phase we would match these GUIDs to type
identifiers defined by the regular LTO module and store the resolutions in
a top-level "type identifier summary" (which will be implemented separately).

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

llvm-svn: 290280

show more ...

IR: Eliminate non-determinism in the module summary analysis.

Also make the summary ref and call graph vectors immutable. This means
a smaller API surface and fewer places to audit for non-determini

IR: Eliminate non-determinism in the module summary analysis.

Also make the summary ref and call graph vectors immutable. This means
a smaller API surface and fewer places to audit for non-determinism.

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

llvm-svn: 290200

show more ...

ModuleSummaryAnalysis: Remove some duplicate code. NFCI.

llvm-svn: 290003

Object: Extract a ModuleSymbolTable class from IRObjectFile.

This class represents a symbol table built from in-memory IR. It provides
access to GlobalValues and should only be used if such access i

Object: Extract a ModuleSymbolTable class from IRObjectFile.

This class represents a symbol table built from in-memory IR. It provides
access to GlobalValues and should only be used if such access is required
(e.g. in the LTO implementation). We will eventually change IRObjectFile
to read from a bitcode symbol table rather than using ModuleSymbolTable,
so it would not be able to expose the module.

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

llvm-svn: 288319

show more ...

[PM] Change the static object whose address is used to uniquely identify
analyses to have a common type which is enforced rather than using
a char object and a `void *` type when used as an identifie

[PM] Change the static object whose address is used to uniquely identify
analyses to have a common type which is enforced rather than using
a char object and a `void *` type when used as an identifier.

This has a number of advantages. First, it at least helps some of the
confusion raised in Justin Lebar's code review of why `void *` was being
used everywhere by having a stronger type that connects to documentation
about this.

However, perhaps more importantly, it addresses a serious issue where
the alignment of these pointer-like identifiers was unknown. This made
it hard to use them in pointer-like data structures. We were already
dodging this in dangerous ways to create the "all analyses" entry. In
a subsequent patch I attempted to use these with TinyPtrVector and
things fell apart in a very bad way.

And it isn't just a compile time or type system issue. Worse than that,
the actual alignment of these pointer-like opaque identifiers wasn't
guaranteed to be a useful alignment as they were just characters.

This change introduces a type to use as the "key" object whose address
forms the opaque identifier. This both forces the objects to have proper
alignment, and provides type checking that we get it right everywhere.
It also makes the types somewhat less mysterious than `void *`.

We could go one step further and introduce a truly opaque pointer-like
type to return from the `ID()` static function rather than returning
`AnalysisKey *`, but that didn't seem to be a clear win so this is just
the initial change to get to a reliably typed and aligned object serving
is a key for all the analyses.

Thanks to Richard Smith and Justin Lebar for helping pick plausible
names and avoid making this refactoring many times. =] And thanks to
Sean for the super fast review!

While here, I've tried to move away from the "PassID" nomenclature
entirely as it wasn't really helping and is overloaded with old pass
manager constructs. Now we have IDs for analyses, and key objects whose
address can be used as IDs. Where possible and clear I've shortened this
to just "ID". In a few places I kept "AnalysisID" to make it clear what
was being identified.

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

llvm-svn: 287783

show more ...

Restore "[ThinLTO] Prevent exporting of locals used/defined in module level asm"

This restores the rest of r286297 (part was restored in r286475).
Specifically, it restores the part requiring adding

Restore "[ThinLTO] Prevent exporting of locals used/defined in module level asm"

This restores the rest of r286297 (part was restored in r286475).
Specifically, it restores the part requiring adding a dependency from
the Analysis to Object library (downstream use changed to correctly
model split BitReader vs BitWriter libraries).

Original description of this part of patch follows:

Module level asm may also contain defs of values. We need to prevent
export of any refs to local values defined in module level asm (e.g. a
ref in normal IR), since that also requires renaming/promotion of the
local. To do that, the summary index builder looks at all values in the
module level asm string that are not marked Weak or Global, which is
exactly the set of locals that are defined. A summary is created for
each of these local defs and flagged as NoRename.

This required adding handling to the BitcodeWriter to look at GV
declarations to see if they have a summary (rather than skipping them
all).

Finally, added an assert to IRObjectFile::CollectAsmUndefinedRefs to
ensure that an MCAsmParser is available, otherwise the module asm parse
would silently fail. Initialized the asm parser in the opt tool for use
in testing this fix.

Fixes PR30610.

llvm-svn: 286844

show more ...

[ThinLTO] Make inline assembly handling more efficient in summary

Summary:
The change in r285513 to prevent exporting of locals used in
inline asm added all locals in the llvm.used set to the refere

[ThinLTO] Make inline assembly handling more efficient in summary

Summary:
The change in r285513 to prevent exporting of locals used in
inline asm added all locals in the llvm.used set to the reference
set of functions containing inline asm. Since these locals were marked
NoRename, this automatically prevented importing of the function.

Unfortunately, this caused an explosion in the summary reference lists
in some cases. In my particular example, it happened for a large protocol
buffer generated C++ file, where many of the generated functions
contained an inline asm call. It was exacerbated when doing a ThinLTO
PGO instrumentation build, where the PGO instrumentation included
thousands of private __profd_* values that were added to llvm.used.

We really only need to include a single llvm.used local (NoRename) value
in the reference list of a function containing inline asm to block it
being imported. However, it seems cleaner to add a flag to the summary
that explicitly describes this situation, which is what this patch does.

Reviewers: mehdi_amini

Subscribers: llvm-commits

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

llvm-svn: 286840

show more ...

Restore part of "[ThinLTO] Prevent exporting of locals used/defined in module level asm"

This restores the part of r286297 that didn't require adding a
dependency from the Analysis to Object library

Restore part of "[ThinLTO] Prevent exporting of locals used/defined in module level asm"

This restores the part of r286297 that didn't require adding a
dependency from the Analysis to Object library. There are two parts
to the original fix, and this will address the handling for the case
where locals are used in module level asm.

The part that requires functionality in libObject handles local defs
in module level asm, and was reverted because our downstream build
of clang builds lib/Bitcode into a single library, and this new
dependency introduced a cycle there. I am trying to get that fixed
(see D26502), so for now that change isn't being restored

llvm-svn: 286475

show more ...

Revert "[ThinLTO] Prevent exporting of locals used/defined in module level asm"

This reverts commit r286297.
Introduces a dependency from libAnalysis to libObject, which I missed
during the review.

Revert "[ThinLTO] Prevent exporting of locals used/defined in module level asm"

This reverts commit r286297.
Introduces a dependency from libAnalysis to libObject, which I missed
during the review.

llvm-svn: 286329

show more ...

[ThinLTO] Prevent exporting of locals used/defined in module level asm

Summary:
This patch uses the same approach added for inline asm in r285513 to
similarly prevent promotion/renaming of locals us

[ThinLTO] Prevent exporting of locals used/defined in module level asm

Summary:
This patch uses the same approach added for inline asm in r285513 to
similarly prevent promotion/renaming of locals used or defined in module
level asm.

All static global values defined in normal IR and used in module level asm
should be included on either the llvm.used or llvm.compiler.used global.
The former were already being flagged as NoRename in the summary, and
I've simply added llvm.compiler.used values to this handling.

Module level asm may also contain defs of values. We need to prevent
export of any refs to local values defined in module level asm (e.g. a
ref in normal IR), since that also requires renaming/promotion of the
local. To do that, the summary index builder looks at all values in the
module level asm string that are not marked Weak or Global, which is
exactly the set of locals that are defined. A summary is created for
each of these local defs and flagged as NoRename.

This required adding handling to the BitcodeWriter to look at GV
declarations to see if they have a summary (rather than skipping them
all).

Finally, added an assert to IRObjectFile::CollectAsmUndefinedRefs to
ensure that an MCAsmParser is available, otherwise the module asm parse
would silently fail. Initialized the asm parser in the opt tool for use
in testing this fix.

Fixes PR30610.

Reviewers: mehdi_amini

Subscribers: johanengelen, krasin, llvm-commits

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

llvm-svn: 286297

show more ...

[ThinLTO] Use per-summary flag to prevent exporting locals used in inline asm

Summary:
Instead of using the workaround of suppressing the entire index for
modules that call inline asm that may refer

[ThinLTO] Use per-summary flag to prevent exporting locals used in inline asm

Summary:
Instead of using the workaround of suppressing the entire index for
modules that call inline asm that may reference locals, use the
NoRename flag on the summary for any locals in the llvm.used set, and
add a reference edge from any functions containing inline asm.

This avoids issues from having no summaries despite the module defining
global values, which was preventing more aggressive index-based
optimization. It will be followed by a subsequent patch to make a
similar fix for local references in module level asm (to fix PR30610).

Reviewers: mehdi_amini

Subscribers: llvm-commits

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

llvm-svn: 285513

show more ...

[ThinLTO] Create AliasSummary when building index

Summary:
Previously we were creating the alias summary on the fly while writing
the summary to bitcode. This moves the creation of these summaries t

[ThinLTO] Create AliasSummary when building index

Summary:
Previously we were creating the alias summary on the fly while writing
the summary to bitcode. This moves the creation of these summaries to
the module summary index builder where we build the rest of the summary
index.

This is going to be necessary for setting the NoRename flag for values
possibly used in inline asm or module level asm.

Reviewers: mehdi_amini

Subscribers: llvm-commits

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

llvm-svn: 285379

show more ...

[ThinLTO] Record calls to aliases

Summary:
When there is a call to an alias in the same module, we were not
adding a call edge. So we could incorrectly think that the alias
was dead if it was inline

[ThinLTO] Record calls to aliases

Summary:
When there is a call to an alias in the same module, we were not
adding a call edge. So we could incorrectly think that the alias
was dead if it was inlined in that function, despite having a
reference imported elsewhere. This resulted in unsats at link time.

Add a call edge when the call is to an alias.

Reviewers: davide, mehdi_amini

Subscribers: llvm-commits

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

llvm-svn: 283664

show more ...

Refactor the ProfileSummaryInfo to use doInitialization and doFinalization to handle Module update.

Summary: This refactors the change in r282616

Reviewers: davidxl, eraman, mehdi_amini

Subscriber

Refactor the ProfileSummaryInfo to use doInitialization and doFinalization to handle Module update.

Summary: This refactors the change in r282616

Reviewers: davidxl, eraman, mehdi_amini

Subscribers: mehdi_amini, davide, llvm-commits

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

llvm-svn: 282630

show more ...

[thinlto] Basic thinlto fdo heuristic

Summary:
This patch improves thinlto importer
by importing 3x larger functions that are called from hot block.

I compared performance with the trunk on spec, a

[thinlto] Basic thinlto fdo heuristic

Summary:
This patch improves thinlto importer
by importing 3x larger functions that are called from hot block.

I compared performance with the trunk on spec, and there
were about 2% on povray and 3.33% on milc. These results seems
to be consistant and match the results Teresa got with her simple
heuristic. Some benchmarks got slower but I think they are just
noisy (mcf, xalancbmki, omnetpp)- running the benchmarks again with
more iterations to confirm. Geomean of all benchmarks including the noisy ones
were about +0.02%.

I see much better improvement on google branch with Easwaran patch
for pgo callsite inlining (the inliner actually inline those big functions)
Over all I see +0.5% improvement, and I get +8.65% on povray.
So I guess we will see much bigger change when Easwaran patch will land
(it depends on new pass manager), but it is still worth putting this to trunk
before it.

Implementation details changes:
- Removed CallsiteCount.
- ProfileCount got replaced by Hotness
- hot-import-multiplier is set to 3.0 for now,
didn't have time to tune it up, but I see that we get most of the interesting
functions with 3, so there is no much performance difference with higher, and
binary size doesn't grow as much as with 10.0.

Reviewers: eraman, mehdi_amini, tejohnson

Subscribers: mehdi_amini, llvm-commits

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

llvm-svn: 282437

show more ...

NFC: add early exit in ModuleSummaryAnalysis

Summary:
Changed this code because it was not very readable.
The one question that I got after changing it is, should we
count calls to intrinsics? We do

NFC: add early exit in ModuleSummaryAnalysis

Summary:
Changed this code because it was not very readable.
The one question that I got after changing it is, should we
count calls to intrinsics? We don't add them to caller summary,
so maybe we shouldn't also count them?

Reviewers: tejohnson, eraman, mehdi_amini

Subscribers: llvm-commits

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

llvm-svn: 280036

show more ...

[PM] Rework the new PM support for building the ModuleSummaryIndex to
directly produce the index as the value type result.

This requires making the index movable which is straightforward. It
greatly

[PM] Rework the new PM support for building the ModuleSummaryIndex to
directly produce the index as the value type result.

This requires making the index movable which is straightforward. It
greatly simplifies things by allowing us to completely avoid the builder
API and the layers of abstraction inherent there. Instead both pass
managers can directly construct these when run by value. They still
won't be constructed truly eagerly thanks to the optional in the legacy
PM. The code that directly builds the index can also just share a direct
function.

A notable change here is that the result type of the analysis for the
new PM is no longer a reference type. This was really problematic when
making changes to how we handle result types to make our interface
requirements *much* more strict and precise. But I think this is an
overall improvement.

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

llvm-svn: 279216

show more ...

[PM] Port ModuleSummaryIndex analysis to new pass manager

Summary:
Port the ModuleSummaryAnalysisWrapperPass to the new pass manager.
Use it in the ported BitcodeWriterPass (similar to how we use th

[PM] Port ModuleSummaryIndex analysis to new pass manager

Summary:
Port the ModuleSummaryAnalysisWrapperPass to the new pass manager.
Use it in the ported BitcodeWriterPass (similar to how we use the
legacy ModuleSummaryAnalysisWrapperPass in the legacy WriteBitcodePass).

Also, pass the -module-summary opt flag through to the new pass
manager pipeline and through to the bitcode writer pass, and add
a test that uses it.

Reviewers: mehdi_amini

Subscribers: llvm-commits, mehdi_amini

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

llvm-svn: 278508

show more ...

Use range algorithms instead of unpacking begin/end

No functionality change is intended.

llvm-svn: 278417

[ThinLTO] Perform profile-guided indirect call promotion

Summary:
To enable profile-guided indirect call promotion in ThinLTO mode, we
simply add call graph edges for each profitable target from the

[ThinLTO] Perform profile-guided indirect call promotion

Summary:
To enable profile-guided indirect call promotion in ThinLTO mode, we
simply add call graph edges for each profitable target from the profile
to the summaries, then the summary-guided importing will consider the
callee for importing as usual.

Also we need to enable the indirect call promotion pass creation in the
PassManagerBuilder when PerformThinLTO=true (we are in the ThinLTO
backend), so that the newly imported functions are considered for
promotion in the backends.

The IC promotion profiles refer to callees by GUID, which required
adding GUIDs to the per-module VST in bitcode (and assigning them
valueIds similar to how they are assigned valueIds in the combined
index).

Reviewers: mehdi_amini, xur

Subscribers: mehdi_amini, davidxl, llvm-commits

Differential Revision: http://reviews.llvm.org/D21932

llvm-svn: 275707

show more ...

Apply clang-tidy's modernize-loop-convert to lib/Analysis.

Only minor manual fixes. No functionality change intended.

llvm-svn: 273816

ThinLTO: fix assertion and refactor check for hidden use from inline ASM in a helper function

This test was crashing, and currently it breaks bootstrapping clang with debuginfo

Differential Revisio

ThinLTO: fix assertion and refactor check for hidden use from inline ASM in a helper function

This test was crashing, and currently it breaks bootstrapping clang with debuginfo

Differential Revision: http://reviews.llvm.org/D20008

From: Mehdi Amini <mehdi.amini@apple.com>
llvm-svn: 268715

show more ...