[BasicAA] Treat llvm.assume as not accessing memory in getModRefBehavior(Function)

Reviewers: dberlin, chandlerc, hfinkel, reames, sanjoy

Subscribers: mcrosier, llvm-commits

Differential Revision:

[BasicAA] Treat llvm.assume as not accessing memory in getModRefBehavior(Function)

Reviewers: dberlin, chandlerc, hfinkel, reames, sanjoy

Subscribers: mcrosier, llvm-commits

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

llvm-svn: 268068

show more ...

[TLI] Unify LibFunc signature checking. NFCI.

I tried to be as close as possible to the strongest check that
existed before; cleaning these up properly is left for future work.

Differential Revisio

[TLI] Unify LibFunc signature checking. NFCI.

I tried to be as close as possible to the strongest check that
existed before; cleaning these up properly is left for future work.

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

llvm-svn: 267758

show more ...

Don't IPO over functions that can be de-refined

Summary:
Fixes PR26774.

If you're aware of the issue, feel free to skip the "Motivation"
section and jump directly to "This patch".

Motivation:

I d

Don't IPO over functions that can be de-refined

Summary:
Fixes PR26774.

If you're aware of the issue, feel free to skip the "Motivation"
section and jump directly to "This patch".

Motivation:

I define "refinement" as discarding behaviors from a program that the
optimizer has license to discard. So transforming:

```
void f(unsigned x) {
unsigned t = 5 / x;
(void)t;
}
```

to

```
void f(unsigned x) { }
```

is refinement, since the behavior went from "if x == 0 then undefined
else nothing" to "nothing" (the optimizer has license to discard
undefined behavior).

Refinement is a fundamental aspect of many mid-level optimizations done
by LLVM. For instance, transforming `x == (x + 1)` to `false` also
involves refinement since the expression's value went from "if x is
`undef` then { `true` or `false` } else { `false` }" to "`false`" (by
definition, the optimizer has license to fold `undef` to any non-`undef`
value).

Unfortunately, refinement implies that the optimizer cannot assume
that the implementation of a function it can see has all of the
behavior an unoptimized or a differently optimized version of the same
function can have. This is a problem for functions with comdat
linkage, where a function can be replaced by an unoptimized or a
differently optimized version of the same source level function.

For instance, FunctionAttrs cannot assume a comdat function is
actually `readnone` even if it does not have any loads or stores in
it; since there may have been loads and stores in the "original
function" that were refined out in the currently visible variant, and
at the link step the linker may in fact choose an implementation with
a load or a store. As an example, consider a function that does two
atomic loads from the same memory location, and writes to memory only
if the two values are not equal. The optimizer is allowed to refine
this function by first CSE'ing the two loads, and the folding the
comparision to always report that the two values are equal. Such a
refined variant will look like it is `readonly`. However, the
unoptimized version of the function can still write to memory (since
the two loads //can// result in different values), and selecting the
unoptimized version at link time will retroactively invalidate
transforms we may have done under the assumption that the function
does not write to memory.

Note: this is not just a problem with atomics or with linking
differently optimized object files. See PR26774 for more realistic
examples that involved neither.

This patch:

This change introduces a new set of linkage types, predicated as
`GlobalValue::mayBeDerefined` that returns true if the linkage type
allows a function to be replaced by a differently optimized variant at
link time. It then changes a set of IPO passes to bail out if they see
such a function.

Reviewers: chandlerc, hfinkel, dexonsmith, joker.eph, rnk

Subscribers: mcrosier, llvm-commits

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

llvm-svn: 265762

show more ...

[AA] Make BasicAA just require domtree.

This doesn't change how many times we construct domtrees in the normal
pipeline, and it removes fragility and instability where basic-aa may
not be run in tim

[AA] Make BasicAA just require domtree.

This doesn't change how many times we construct domtrees in the normal
pipeline, and it removes fragility and instability where basic-aa may
not be run in time to see domtrees because they happen to be constructed
afterward.

This isn't quite as clean as the change to memdep because there is
a mode where basic-aa specifically runs without domtrees -- in the
hacking version used by function-attrs with the legacy pass manager.

llvm-svn: 263234

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

[BasicAA/MDA] Sink aliasing rules for malloc and calloc into BasicAA

MemoryDependenceAnalysis had a hard-coded exception to the general aliasing rules for malloc and calloc. The reasoning that appli

[BasicAA/MDA] Sink aliasing rules for malloc and calloc into BasicAA

MemoryDependenceAnalysis had a hard-coded exception to the general aliasing rules for malloc and calloc. The reasoning that applied there is equally valid in BasicAA and clarifies the remaining logic in MDA.

In principal, this can expose slightly more optimization opportunities, but since essentially all of our aliasing aware memory optimization passes go through MDA, this will likely be NFC in practice.

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

llvm-svn: 263075

show more ...

[AA] Hoist the logic to reformulate various AA queries in terms of other
parts of the AA interface out of the base class of every single AA
result object.

Because this logic reformulates the query i

[AA] Hoist the logic to reformulate various AA queries in terms of other
parts of the AA interface out of the base class of every single AA
result object.

Because this logic reformulates the query in terms of some other aspect
of the API, it would easily cause O(n^2) query patterns in alias
analysis. These could in turn be magnified further based on the number
of call arguments, and then further based on the number of AA queries
made for a particular call. This ended up causing problems for Rust that
were actually noticable enough to get a bug (PR26564) and probably other
places as well.

When originally re-working the AA infrastructure, the desire was to
regularize the pattern of refinement without losing any generality.
While I think it was successful, that is clearly proving to be too
costly. And the cost is needless: we gain no actual improvement for this
generality of making a direct query to tbaa actually be able to
re-use some other alias analysis's refinement logic for one of the other
APIs, or some such. In short, this is entirely wasted work.

To the extent possible, delegation to other API surfaces should be done
at the aggregation layer so that we can avoid re-walking the
aggregation. In fact, this significantly simplifies the logic as we no
longer need to smuggle the aggregation layer into each alias analysis
(or the TargetLibraryInfo into each alias analysis just so we can form
argument memory locations!).

However, we also have some delegation logic inside of BasicAA and some
of it even makes sense. When the delegation logic is baking in specific
knowledge of aliasing properties of the LLVM IR, as opposed to simply
reformulating the query to utilize a different alias analysis interface
entry point, it makes a lot of sense to restrict that logic to
a different layer such as BasicAA. So one aspect of the delegation that
was in every AA base class is that when we don't have operand bundles,
we re-use function AA results as a fallback for callsite alias results.
This relies on the IR properties of calls and functions w.r.t. aliasing,
and so seems a better fit to BasicAA. I've lifted the logic up to that
point where it seems to be a natural fit. This still does a bit of
redundant work (we query function attributes twice, once via the
callsite and once via the function AA query) but it is *exactly* twice
here, no more.

The end result is that all of the delegation logic is hoisted out of the
base class and into either the aggregation layer when it is a pure
retargeting to a different API surface, or into BasicAA when it relies
on the IR's aliasing properties. This should fix the quadratic query
pattern reported in PR26564, although I don't have a stand-alone test
case to reproduce it.

It also seems general goodness. Now the numerous AAs that don't need
target library info don't carry it around and depend on it. I think
I can even rip out the general access to the aggregation layer and only
expose that in BasicAA as it is the only place where we re-query in that
manner.

However, this is a non-trivial change to the AA infrastructure so I want
to get some additional eyes on this before it lands. Sadly, it can't
wait long because we should really cherry pick this into 3.8 if we're
going to go this route.

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

llvm-svn: 262490

show more ...

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

Remove uses of builtin comma operator.

Cleanup for upcoming Clang warning -Wcomma. No functionality change intended.

llvm-svn: 261270

[BasicAA] NFC - revised comment for function adjustToPointerSize()

llvm-svn: 259300

[BasicAA] Fix for missing must alias (D16343)

llvm-svn: 259299

[BasicAA] Update on r259290 - added missing cast

llvm-svn: 259298

[BasicAA] NFC - utility function for two's complement wrap-around

llvm-svn: 259290

[opaque pointer types] [NFC] GEP: replace get(Pointer)ElementType uses with get{Source,Result}ElementType.

Summary:
GEPOperator: provide getResultElementType alongside getSourceElementType.
This is

[opaque pointer types] [NFC] GEP: replace get(Pointer)ElementType uses with get{Source,Result}ElementType.

Summary:
GEPOperator: provide getResultElementType alongside getSourceElementType.
This is made possible by adding a result element type field to GetElementPtrConstantExpr, which GetElementPtrInst already has.

GEP: replace get(Pointer)ElementType uses with get{Source,Result}ElementType.

Reviewers: mjacob, dblaikie

Subscribers: llvm-commits

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

llvm-svn: 258145

show more ...

fix typos; NFC

llvm-svn: 258026

[BasicAliasAnalysis] Take into account operand bundles in the getModRefInfo function

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

llvm-svn: 257991

[BasicAA] Extract WriteOnly predicate on parameters [NFC]

Since writeonly is the only missing attribute and special case left for the memset/memcpy family of intrinsics, rearrange the code to make t

[BasicAA] Extract WriteOnly predicate on parameters [NFC]

Since writeonly is the only missing attribute and special case left for the memset/memcpy family of intrinsics, rearrange the code to make that much more clear.

llvm-svn: 256949

show more ...

[BasicAA] Remove special casing of memset_pattern16 in favor of generic attribute inference

Most of the properties of memset_pattern16 can be now covered by the generic attributes and inferred by In

[BasicAA] Remove special casing of memset_pattern16 in favor of generic attribute inference

Most of the properties of memset_pattern16 can be now covered by the generic attributes and inferred by InferFunctionAttrs. The only exceptions are:
- We don't yet have a writeonly attribute for the first argument.
- We don't have an attribute for modeling the access size facts encoded in MemoryLocation.cpp.

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

llvm-svn: 256911

show more ...

[BasicAA] Delete dead code related to memset/memcpy/memmove intrinsics [NFCI]

We only need to describe the writeonly property of one of the arguments. All of the rest of the semantics are nicely des

[BasicAA] Delete dead code related to memset/memcpy/memmove intrinsics [NFCI]

We only need to describe the writeonly property of one of the arguments. All of the rest of the semantics are nicely described by existing attributes in Intrinsics.td.

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

llvm-svn: 256910

show more ...

Fix a typo in BasicAliasAnalysis

llvm-svn: 253322

Refactor: Simplify boolean conditional return statements in llvm/lib/Analysis

Patch by Richard Thomson!

Differential revision: http://reviews.llvm.org/D9967

llvm-svn: 252209

[AliasAnalysis] Take into account readnone attribute for the function arguments

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

llvm-svn: 251535

[AliasAnalysis] Take into account readonly attribute for the function arguments

In getArgModRefInfo we consider all arguments as having MRI_ModRef.
However for arguments marked with readonly attribu

[AliasAnalysis] Take into account readonly attribute for the function arguments

In getArgModRefInfo we consider all arguments as having MRI_ModRef.
However for arguments marked with readonly attribute we can return
more precise answer - MRI_Ref.

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

llvm-svn: 251525

show more ...

Initialize BasicAAWrapperPass in it's constructor

Summary: This idiom is used elsewhere in LLVM, but was overlooked here.

Reviewers: chandlerc

Subscribers: llvm-commits

Differential Revision: htt

Initialize BasicAAWrapperPass in it's constructor

Summary: This idiom is used elsewhere in LLVM, but was overlooked here.

Reviewers: chandlerc

Subscribers: llvm-commits

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

llvm-svn: 251348

show more ...