[AssumeBundles] adapt Assumption cache to assume bundles

Summary: change assumption cache to store an assume along with an index to the operand bundle containing the knowledge.

Reviewers: jdoerfert

[AssumeBundles] adapt Assumption cache to assume bundles

Summary: change assumption cache to store an assume along with an index to the operand bundle containing the knowledge.

Reviewers: jdoerfert, hfinkel

Reviewed By: jdoerfert

Subscribers: hiraditya, mgrang, llvm-commits

Tags: #llvm

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

show more ...

Sink all InitializePasses.h includes

This file lists every pass in LLVM, and is included by Pass.h, which is
very popular. Every time we add, remove, or rename a pass in LLVM, it
caused lots of reco

Sink all InitializePasses.h includes

This file lists every pass in LLVM, and is included by Pass.h, which is
very popular. Every time we add, remove, or rename a pass in LLVM, it
caused lots of recompilation.

I found this fact by looking at this table, which is sorted by the
number of times a file was changed over the last 100,000 git commits
multiplied by the number of object files that depend on it in the
current checkout:
recompiles touches affected_files header
342380 95 3604 llvm/include/llvm/ADT/STLExtras.h
314730 234 1345 llvm/include/llvm/InitializePasses.h
307036 118 2602 llvm/include/llvm/ADT/APInt.h
213049 59 3611 llvm/include/llvm/Support/MathExtras.h
170422 47 3626 llvm/include/llvm/Support/Compiler.h
162225 45 3605 llvm/include/llvm/ADT/Optional.h
158319 63 2513 llvm/include/llvm/ADT/Triple.h
140322 39 3598 llvm/include/llvm/ADT/StringRef.h
137647 59 2333 llvm/include/llvm/Support/Error.h
131619 73 1803 llvm/include/llvm/Support/FileSystem.h

Before this change, touching InitializePasses.h would cause 1345 files
to recompile. After this change, touching it only causes 550 compiles in
an incremental rebuild.

Reviewers: bkramer, asbirlea, bollu, jdoerfert

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

show more ...

Fix: Actually erase remove the elements from AssumeHandles

Reviewers: sdmitriev, tejohnson

Reviewed by: tejohnson

Subscribers: llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llv

Fix: Actually erase remove the elements from AssumeHandles

Reviewers: sdmitriev, tejohnson

Reviewed by: tejohnson

Subscribers: llvm-commits

Tags: #llvm

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

llvm-svn: 373494

show more ...

AssumptionCache: remove old affected values after RAUW.

If they're left in the cache then they can't be removed efficiently when the
cache is notified to unlink a @llvm.assume call, and that can lea

AssumptionCache: remove old affected values after RAUW.

If they're left in the cache then they can't be removed efficiently when the
cache is notified to unlink a @llvm.assume call, and that can lead to values
from different functions entirely remaining there.

llvm-svn: 369091

show more ...

[llvm] Migrate llvm::make_unique to std::make_unique

Now that we've moved to C++14, we no longer need the llvm::make_unique
implementation from STLExtras.h. This patch is a mechanical replacement
of

[llvm] Migrate llvm::make_unique to std::make_unique

Now that we've moved to C++14, we no longer need the llvm::make_unique
implementation from STLExtras.h. This patch is a mechanical replacement
of (hopefully) all the llvm::make_unique instances across the monorepo.

llvm-svn: 369013

show more ...

[CodeExtractor] Update function's assumption cache after extracting blocks from it

Summary: Assumption cache's self-updating mechanism does not correctly handle the case when blocks are extracted fr

[CodeExtractor] Update function's assumption cache after extracting blocks from it

Summary: Assumption cache's self-updating mechanism does not correctly handle the case when blocks are extracted from the function by the CodeExtractor. As a result function's assumption cache may have stale references to the llvm.assume calls that were moved to the outlined function. This patch fixes this problem by removing extracted llvm.assume calls from the function’s assumption cache.

Reviewers: hfinkel, vsk, fhahn, davidxl, sanjoy

Reviewed By: hfinkel, vsk

Subscribers: llvm-commits

Tags: #llvm

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

llvm-svn: 353500

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

[Analysis, Transforms] Fix some Clang-tidy modernize and Include What You Use warnings; other minor fixes (NFC).

llvm-svn: 312383

[IR][AssumptionCache] Add m_Shift and m_BitwiseLogic matchers to replace a couple m_CombineOr

Summary:
m_CombineOr isn't very efficient. The code using it is also quite verbose.

This patch adds m_S

[IR][AssumptionCache] Add m_Shift and m_BitwiseLogic matchers to replace a couple m_CombineOr

Summary:
m_CombineOr isn't very efficient. The code using it is also quite verbose.

This patch adds m_Shift and m_BitwiseLogic matchers to make the using code more concise and improve the match efficiency.

Reviewers: spatel, davide

Reviewed By: davide

Subscribers: davide, llvm-commits

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

llvm-svn: 306206

show more ...

Rename WeakVH to WeakTrackingVH; NFC

This relands r301424.

llvm-svn: 301812

Reverts commit r301424, r301425 and r301426

Commits were:

"Use WeakVH instead of WeakTrackingVH in AliasSetTracker's UnkownInsts"
"Add a new WeakVH value handle; NFC"
"Rename WeakVH to WeakTracking

Reverts commit r301424, r301425 and r301426

Commits were:

"Use WeakVH instead of WeakTrackingVH in AliasSetTracker's UnkownInsts"
"Add a new WeakVH value handle; NFC"
"Rename WeakVH to WeakTrackingVH; NFC"

The changes assumed pointers are 8 byte aligned on all architectures.

llvm-svn: 301429

show more ...

Rename WeakVH to WeakTrackingVH; NFC

Summary:
I plan to use WeakVH to mean "nulls itself out on deletion, but does
not track RAUW" in a subsequent commit.

Reviewers: dblaikie, davide

Reviewed By:

Rename WeakVH to WeakTrackingVH; NFC

Summary:
I plan to use WeakVH to mean "nulls itself out on deletion, but does
not track RAUW" in a subsequent commit.

Reviewers: dblaikie, davide

Reviewed By: davide

Subscribers: arsenm, mehdi_amini, mcrosier, mzolotukhin, jfb, llvm-commits, nhaehnle

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

llvm-svn: 301424

show more ...

AssumptionCache: Disable the verifier by default, move it behind a hidden cl::opt and verify from releaseMemory().

This is a short term solution to the problem that many passes currently fail
to upd

AssumptionCache: Disable the verifier by default, move it behind a hidden cl::opt and verify from releaseMemory().

This is a short term solution to the problem that many passes currently fail
to update the assumption cache. In the long term the verifier should not
be controllable with a flag. We should either fix all passes to correctly
update the assumption cache and enable the verifier unconditionally or
somehow arrange for the assumption list to be updated automatically by passes.

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

llvm-svn: 295236

show more ...

[ValueTracking] recognize a 'not' of an assumed condition as false

Also, add the corresponding match to the AssumptionCache's 'Affected Values' list.

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

[ValueTracking] recognize a 'not' of an assumed condition as false

Also, add the corresponding match to the AssumptionCache's 'Affected Values' list.

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

llvm-svn: 292239

show more ...

Fix use-after-free bug in AffectedValueCallbackVH::allUsesReplacedWith

When transferring affected values in the cache from an old value, identified by
the value of the current callback, to the speci

Fix use-after-free bug in AffectedValueCallbackVH::allUsesReplacedWith

When transferring affected values in the cache from an old value, identified by
the value of the current callback, to the specified new value we might need to
insert a new entry into the DenseMap which constitutes the cache. Doing so
might delete the current callback object. Move the copying logic into a new
function, a member of the assumption cache itself, so that we don't run into UB
should the callback handle itself be removed mid-copy.

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

llvm-svn: 292133

show more ...

Make processing @llvm.assume more efficient - Add affected values to the assumption cache

Here's my second try at making @llvm.assume processing more efficient. My
previous attempt, which leveraged

Make processing @llvm.assume more efficient - Add affected values to the assumption cache

Here's my second try at making @llvm.assume processing more efficient. My
previous attempt, which leveraged operand bundles, r289755, didn't end up
working: it did make assume processing more efficient but eliminating the
assumption cache made ephemeral value computation too expensive. This is a
more-targeted change. We'll keep the assumption cache, but extend it to keep a
map of affected values (i.e. values about which an assumption might provide
some information) to the corresponding assumption intrinsics. This allows
ValueTracking and LVI to find assumptions relevant to the value being queried
without scanning all assumptions in the function. The fact that ValueTracking
started doing O(number of assumptions in the function) work, for every
known-bits query, has become prohibitively expensive in some cases.

As discussed during the review, this is a pragmatic fix that, longer term, will
likely be replaced by a more-principled solution (perhaps based on an extended
SSA form).

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

llvm-svn: 291671

show more ...

Add files I seem to have dropped in my revert (r290086).

Sorry!

llvm-svn: 290087

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

Consistently use FunctionAnalysisManager

Besides a general consistently benefit, the extra layer of indirection
allows the mechanical part of https://reviews.llvm.org/D23256 that
requires touching e

Consistently use FunctionAnalysisManager

Besides a general consistently benefit, the extra layer of indirection
allows the mechanical part of https://reviews.llvm.org/D23256 that
requires touching every transformation and analysis to be factored out
cleanly.

Thanks to David for the suggestion.

llvm-svn: 278077

show more ...

[PM] Make the AnalysisManager parameter to run methods a reference.

This was originally a pointer to support pass managers which didn't use
AnalysisManagers. However, that doesn't realistically come

[PM] Make the AnalysisManager parameter to run methods a reference.

This was originally a pointer to support pass managers which didn't use
AnalysisManagers. However, that doesn't realistically come up much and
the complexity of supporting it doesn't really make sense.

In fact, *many* parts of the pass manager were just assuming the pointer
was never null already. This at least makes it much more explicit and
clear.

llvm-svn: 263219

show more ...

[PM] Implement the final conclusion as to how the analysis IDs should
work in the face of the limitations of DLLs and templated static
variables.

This requires passes that use the AnalysisBase mixin

[PM] Implement the final conclusion as to how the analysis IDs should
work in the face of the limitations of DLLs and templated static
variables.

This requires passes that use the AnalysisBase mixin provide a static
variable themselves. So as to keep their APIs clean, I've made these
private and befriended the CRTP base class (which is the common
practice).

I've added documentation to AnalysisBase for why this is necessary and
at what point we can go back to the much simpler system.

This is clearly a better pattern than the extern template as it caught
*numerous* places where the template magic hadn't been applied and
things were "just working" but would eventually have broken
mysteriously.

llvm-svn: 263216

show more ...

[PM] Appease mingw32's auto-import DLL build with minimal tweaks, with fix for clang.

char AnalysisBase::ID should be declared as extern and defined in one module.

llvm-svn: 262188

Revert r262185, "[PM] Appease mingw32's auto-import DLL build with minimal tweaks."

I'll rework soon.

llvm-svn: 262186

[PM] Appease mingw32's auto-import DLL build with minimal tweaks.

char AnalysisBase::ID should be declared as extern and defined in one module.

llvm-svn: 262185

[PM] Introduce CRTP mixin base classes to help define passes and
analyses in the new pass manager.

These just handle really basic stuff: turning a type name into a string
statically that is nice to

[PM] Introduce CRTP mixin base classes to help define passes and
analyses in the new pass manager.

These just handle really basic stuff: turning a type name into a string
statically that is nice to print in logs, and getting a static unique ID
for each analysis.

Sadly, the format of passes in anonymous namespaces makes using their
names in tests really annoying so I've customized the names of the no-op
passes to keep tests sane to read.

This is the first of a few simplifying refactorings for the new pass
manager that should reduce boilerplate and confusion.

llvm-svn: 262004

show more ...