[AliasAnalysis] Teach BasicAA about memcpy.

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

llvm-svn: 290526

Revert @llvm.assume with operator bundles (r289755-r289757)

This creates non-linear behavior in the inliner (see more details in
r289755's commit thread).

llvm-svn: 290086

Fix argument attribute queries with bundle operands

When iterating over data operands in AA, don't make argument-attribute-specific
queries on bundle operands. Trying to fix self hosting...

llvm-sv

Fix argument attribute queries with bundle operands

When iterating over data operands in AA, don't make argument-attribute-specific
queries on bundle operands. Trying to fix self hosting...

llvm-svn: 289765

show more ...

Remove the AssumptionCache

After r289755, the AssumptionCache is no longer needed. Variables affected by
assumptions are now found by using the new operand-bundle-based scheme. This
new scheme is mo

Remove the AssumptionCache

After r289755, the AssumptionCache is no longer needed. Variables affected by
assumptions are now found by using the new operand-bundle-based scheme. This
new scheme is more computationally efficient, and also we need much less
code...

llvm-svn: 289756

show more ...

IR: Change the gep_type_iterator API to avoid always exposing the "current" type.

Instead, expose whether the current type is an array or a struct, if an array
what the upper bound is, and if a stru

IR: Change the gep_type_iterator API to avoid always exposing the "current" type.

Instead, expose whether the current type is an array or a struct, if an array
what the upper bound is, and if a struct the struct type itself. This is
in preparation for a later change which will make PointerType derive from
Type rather than SequentialType.

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

llvm-svn: 288458

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

Fix comment typos. NFC.

Identified by Pedro Giffuni in PR27636.

llvm-svn: 287490

[BasicAA] Teach BasicAA to handle the inaccessiblememonly and inaccessiblemem_or_argmemonly attributes

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

llvm-svn: 286294

[BasicAA] Fix - missed alias in GEP expressions

In BasicAA GEP operand values get adjusted ("wrap-around") based on the
pointersize. Otherwise, in non-64b modes, AA could report false negatives.
Ho

[BasicAA] Fix - missed alias in GEP expressions

In BasicAA GEP operand values get adjusted ("wrap-around") based on the
pointersize. Otherwise, in non-64b modes, AA could report false negatives.
However, a wrap-around is valid only for a fully evaluated expression.
It had been introduced to fix an alias problem in
http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160118/326163.html.
This commit restricts the wrap-around to constant gep operands only where the
value is known at compile-time.

llvm-svn: 284908

show more ...

Replace a few more "fall through" comments with LLVM_FALLTHROUGH

Follow up to r278902. I had missed "fall through", with a space.

llvm-svn: 278970

[BasicAA] Avoid calling GetUnderlyingObject, when the result of a previous call can be reused.

Recursive calls to aliasCheck from alias[GEP|Select|PHI] may result in a second call to GetUnderlyingOb

[BasicAA] Avoid calling GetUnderlyingObject, when the result of a previous call can be reused.

Recursive calls to aliasCheck from alias[GEP|Select|PHI] may result in a second call to GetUnderlyingObject for a Value, whose underlying object is already computed. This patch ensures that in this situations, the underlying object is not computed again, and the result of the previous call is resued.

https://reviews.llvm.org/D22305

llvm-svn: 278519

show more ...

[AliasAnalysis] Treat invariant.start as read-memory

Summary:
We teach alias analysis that invariant.start is readonly.
This helps with GVN and memcopy optimizations that currently treat.
invariant.

[AliasAnalysis] Treat invariant.start as read-memory

Summary:
We teach alias analysis that invariant.start is readonly.
This helps with GVN and memcopy optimizations that currently treat.
invariant.start as a clobber.
We need to treat this as readonly, so that DSE does not incorrectly
remove stores prior to the invariant.start

Reviewers: sanjoy, reames, majnemer, dberlin

Subscribers: llvm-commits

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

llvm-svn: 278138

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

BasicAA should look through functions with returned arguments

Motivated by the work on the llvm.noalias intrinsic, teach BasicAA to look
through returned-argument functions when answering queries. T

BasicAA should look through functions with returned arguments

Motivated by the work on the llvm.noalias intrinsic, teach BasicAA to look
through returned-argument functions when answering queries. This is essential
so that we don't loose all other AA information when supplementing with
llvm.noalias.

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

llvm-svn: 275035

show more ...

Add writeonly IR attribute

Summary:
This complements the earlier addition of IntrWriteMem and IntrWriteArgMem
LLVM intrinsic properties, see D18291.

Also start using the attribute for memset, memcp

Add writeonly IR attribute

Summary:
This complements the earlier addition of IntrWriteMem and IntrWriteArgMem
LLVM intrinsic properties, see D18291.

Also start using the attribute for memset, memcpy, and memmove intrinsics,
and remove their special-casing in BasicAliasAnalysis.

Reviewers: reames, joker.eph

Subscribers: joker.eph, llvm-commits

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

llvm-svn: 274485

show more ...

Revert "Claim NoAlias if two GEPs index different fields of the same struct"

This reverts commit 2d5d6493f43eb68493a3852b8c226ac9fafdc7eb.

llvm-svn: 271422

Claim NoAlias if two GEPs index different fields of the same struct

Patch by Taewook Oh

Summary: Patch for Bug 27478. Make BasicAliasAnalysis claims NoAlias if two GEPs index different fields of th

Claim NoAlias if two GEPs index different fields of the same struct

Patch by Taewook Oh

Summary: Patch for Bug 27478. Make BasicAliasAnalysis claims NoAlias if two GEPs index different fields of the same structure.

Reviewers: hfinkel, dberlin

Subscribers: dberlin, mcrosier, llvm-commits

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

llvm-svn: 271415

show more ...

[BasicAA] Extend inbound GEP negative offset logic to GlobalVariables

r270777 improved the precision of alloca vs. inbounbds GEP alias queries: if
we have (a) an inbounds GEP and (b) a pointer based

[BasicAA] Extend inbound GEP negative offset logic to GlobalVariables

r270777 improved the precision of alloca vs. inbounbds GEP alias queries: if
we have (a) an inbounds GEP and (b) a pointer based on an alloca, and the
beginning of the object the GEP points to would have a negative offset with
respect to the alloca, then the GEP can not alias pointer (b).

This makes the same logic fire when (b) is based on a GlobalVariable instead
of an alloca.

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

llvm-svn: 270893

show more ...

MemorySSA: Revert r269678 and r268068; replace with special casing in MemorySSA.

It turns out that too many passes are relying on alias analysis results
for control dependencies. Until we fix that b

MemorySSA: Revert r269678 and r268068; replace with special casing in MemorySSA.

It turns out that too many passes are relying on alias analysis results
for control dependencies. Until we fix that by introducing a more accurate
modelling of control dependencies, special case assume in MemorySSA instead.

Also introduce tests to ensure we don't regress the FunctionAttrs or LICM
passes.

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

llvm-svn: 270823

show more ...

[BasicAA] Improve precision of alloca vs. inbounds GEP alias queries

If a we have (a) a GEP and (b) a pointer based on an alloca, and the
beginning of the object the GEP points would have a negative

[BasicAA] Improve precision of alloca vs. inbounds GEP alias queries

If a we have (a) a GEP and (b) a pointer based on an alloca, and the
beginning of the object the GEP points would have a negative offset with
repsect to the alloca, then the GEP can not alias pointer (b).

For example, consider code like:

struct { int f0, int f1, ...} foo;
...
foo alloca;
foo *random = bar(alloca);
int *f0 = &alloca.f0
int *f1 = &random->f1;

Which is lowered, approximately, to:
%alloca = alloca %struct.foo
%random = call %struct.foo* @random(%struct.foo* %alloca)
%f0 = getelementptr inbounds %struct, %struct.foo* %alloca, i32 0, i32 0
%f1 = getelementptr inbounds %struct, %struct.foo* %random, i32 0, i32 1

Assume %f1 and %f0 alias. Then %f1 would point into the object allocated
by %alloca. Since the %f1 GEP is inbounds, that means %random must also
point into the same object. But since %f0 points to the beginning of %alloca,
the highest %f1 can be is (%alloca + 3). This means %random can not be higher
than (%alloca - 1), and so is not inbounds, a contradiction.

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

llvm-svn: 270777

show more ...

Revert r270268 due to unused variable warnings.

llvm-svn: 270272

[BasicAA] Turn DecomposeGEPExpression runtime checks into asserts.

When it has a DataLayout, DecomposeGEPExpression() should return the same object
as GetUnderlyingObject(). Per the FIXME, it curren

[BasicAA] Turn DecomposeGEPExpression runtime checks into asserts.

When it has a DataLayout, DecomposeGEPExpression() should return the same object
as GetUnderlyingObject(). Per the FIXME, it currently always has a DL, so the
runtime check is redundant and can become an assert.

llvm-svn: 270268

show more ...

[BasicAA] Update comments based on feedback from hfinkel. NFCI.

Original change Hal's comments were based on:
http://reviews.llvm.org/D19730

llvm-svn: 269678

[BasicAA] Compare GEP indices based on value (Fix PR27418)

Equivalent GEP indices with different types are treated as different
indices altogether, leading to an incorrect AA result. Fix the issue
b

[BasicAA] Compare GEP indices based on value (Fix PR27418)

Equivalent GEP indices with different types are treated as different
indices altogether, leading to an incorrect AA result. Fix the issue
by comparing indices based on their values.

Thanks to Mikael Holmén for reporting the issue!

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

llvm-svn: 269197

show more ...

[BasicAA] Guard intrinsics don't write to memory

Summary:
The idea is very close to what we do for assume intrinsics: we mark the
guard intrinsics as writing to arbitrary memory to maintain control

[BasicAA] Guard intrinsics don't write to memory

Summary:
The idea is very close to what we do for assume intrinsics: we mark the
guard intrinsics as writing to arbitrary memory to maintain control
dependence, but under the covers we teach AA that they do not mod any
particular memory location.

Reviewers: chandlerc, hfinkel, gbiv, reames

Subscribers: george.burgess.iv, mcrosier, llvm-commits

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

llvm-svn: 269007

show more ...