History log of /llvm-project/llvm/lib/Analysis/BasicAliasAnalysis.cpp (Results 351 – 375 of 785)
Revision (<<< Hide revision tags) (Show revision tags >>>) Date Author Comments
# 557b601b 24-Oct-2015 Benjamin Kramer <benny.kra@googlemail.com>

[BasicAliasAnalysis] Simplify expression, no functional change.

(-1) - x + 1 is the same as -x.

llvm-svn: 251185


# 05a896a8 23-Oct-2015 James Molloy <james.molloy@arm.com>

[BasicAA] Bugfix for r251016

If the loaded type sizes don't match the element type of the sequential type, all bets are off and the addresses may, indeed, overlap.

Surprisingly, this just got caugh

[BasicAA] Bugfix for r251016

If the loaded type sizes don't match the element type of the sequential type, all bets are off and the addresses may, indeed, overlap.

Surprisingly, this just got caught in one test, on one builder, out of the 30+ builders testing this change. Congratulations go to http://lab.llvm.org:8011/builders/clang-aarch64-lnt/builds/5205.

llvm-svn: 251112

show more ...


# 5a4d8cd5 22-Oct-2015 James Molloy <james.molloy@arm.com>

[BasicAA] Non-equal indices in a GEP of a SequentialType don't overlap

If the final indices of two GEPs can be proven to not be equal, and
the GEP is of a SequentialType (not a StructType), then the

[BasicAA] Non-equal indices in a GEP of a SequentialType don't overlap

If the final indices of two GEPs can be proven to not be equal, and
the GEP is of a SequentialType (not a StructType), then the two GEPs
do not alias.

llvm-svn: 251016

show more ...


# 5a82c916 10-Oct-2015 Duncan P. N. Exon Smith <dexonsmith@apple.com>

Analysis: Remove implicit ilist iterator conversions

Remove implicit ilist iterator conversions from LLVMAnalysis.

I came across something really scary in `llvm::isKnownNotFullPoison()`
which relie

Analysis: Remove implicit ilist iterator conversions

Remove implicit ilist iterator conversions from LLVMAnalysis.

I came across something really scary in `llvm::isKnownNotFullPoison()`
which relied on `Instruction::getNextNode()` being completely broken
(not surprising, but scary nevertheless). This function is documented
(and coded to) return `nullptr` when it gets to the sentinel, but with
an `ilist_half_node` as a sentinel, the sentinel check looks into some
other memory and we don't recognize we've hit the end.

Rooting out these scary cases is the reason I'm removing the implicit
conversions before doing anything else with `ilist`; I'm not at all
surprised that clients rely on badness.

I found another scary case -- this time, not relying on badness, just
bad (but I guess getting lucky so far) -- in
`ObjectSizeOffsetEvaluator::compute_()`. Here, we save out the
insertion point, do some things, and then restore it. Previously, we
let the iterator auto-convert to `Instruction*`, and then set it back
using the `Instruction*` version:

Instruction *PrevInsertPoint = Builder.GetInsertPoint();

/* Logic that may change insert point */

if (PrevInsertPoint)
Builder.SetInsertPoint(PrevInsertPoint);

The check for `PrevInsertPoint` doesn't protect correctly against bad
accesses. If the insertion point has been set to the end of a basic
block (i.e., `SetInsertPoint(SomeBB)`), then `GetInsertPoint()` returns
an iterator pointing at the list sentinel. The version of
`SetInsertPoint()` that's getting called will then call
`PrevInsertPoint->getParent()`, which explodes horribly. The only
reason this hasn't blown up is that it's fairly unlikely the builder is
adding to the end of the block; usually, we're adding instructions
somewhere before the terminator.

llvm-svn: 249925

show more ...


# abdcb3c1 24-Sep-2015 Justin Bogner <mail@justinbogner.com>

Fix a think-o in which functions these should surround

llvm-svn: 248465


# aa57ac5d 24-Sep-2015 Justin Bogner <mail@justinbogner.com>

Add some NDEBUG checks I accidentally dropped in r248462

llvm-svn: 248464


# 49655f80 24-Sep-2015 Justin Bogner <mail@justinbogner.com>

BasicAA: Move BasicAAResult::alias out-of-line. NFC

This makes the header more readable and cleans up some unnecessary
header differences between NDEBUG and !NDEBUG.

llvm-svn: 248462


# 7b560d40 09-Sep-2015 Chandler Carruth <chandlerc@gmail.com>

[PM/AA] Rebuild LLVM's alias analysis infrastructure in a way compatible
with the new pass manager, and no longer relying on analysis groups.

This builds essentially a ground-up new AA infrastructur

[PM/AA] Rebuild LLVM's alias analysis infrastructure in a way compatible
with the new pass manager, and no longer relying on analysis groups.

This builds essentially a ground-up new AA infrastructure stack for
LLVM. The core ideas are the same that are used throughout the new pass
manager: type erased polymorphism and direct composition. The design is
as follows:

- FunctionAAResults is a type-erasing alias analysis results aggregation
interface to walk a single query across a range of results from
different alias analyses. Currently this is function-specific as we
always assume that aliasing queries are *within* a function.

- AAResultBase is a CRTP utility providing stub implementations of
various parts of the alias analysis result concept, notably in several
cases in terms of other more general parts of the interface. This can
be used to implement only a narrow part of the interface rather than
the entire interface. This isn't really ideal, this logic should be
hoisted into FunctionAAResults as currently it will cause
a significant amount of redundant work, but it faithfully models the
behavior of the prior infrastructure.

- All the alias analysis passes are ported to be wrapper passes for the
legacy PM and new-style analysis passes for the new PM with a shared
result object. In some cases (most notably CFL), this is an extremely
naive approach that we should revisit when we can specialize for the
new pass manager.

- BasicAA has been restructured to reflect that it is much more
fundamentally a function analysis because it uses dominator trees and
loop info that need to be constructed for each function.

All of the references to getting alias analysis results have been
updated to use the new aggregation interface. All the preservation and
other pass management code has been updated accordingly.

The way the FunctionAAResultsWrapperPass works is to detect the
available alias analyses when run, and add them to the results object.
This means that we should be able to continue to respect when various
passes are added to the pipeline, for example adding CFL or adding TBAA
passes should just cause their results to be available and to get folded
into this. The exception to this rule is BasicAA which really needs to
be a function pass due to using dominator trees and loop info. As
a consequence, the FunctionAAResultsWrapperPass directly depends on
BasicAA and always includes it in the aggregation.

This has significant implications for preserving analyses. Generally,
most passes shouldn't bother preserving FunctionAAResultsWrapperPass
because rebuilding the results just updates the set of known AA passes.
The exception to this rule are LoopPass instances which need to preserve
all the function analyses that the loop pass manager will end up
needing. This means preserving both BasicAAWrapperPass and the
aggregating FunctionAAResultsWrapperPass.

Now, when preserving an alias analysis, you do so by directly preserving
that analysis. This is only necessary for non-immutable-pass-provided
alias analyses though, and there are only three of interest: BasicAA,
GlobalsAA (formerly GlobalsModRef), and SCEVAA. Usually BasicAA is
preserved when needed because it (like DominatorTree and LoopInfo) is
marked as a CFG-only pass. I've expanded GlobalsAA into the preserved
set everywhere we previously were preserving all of AliasAnalysis, and
I've added SCEVAA in the intersection of that with where we preserve
SCEV itself.

One significant challenge to all of this is that the CGSCC passes were
actually using the alias analysis implementations by taking advantage of
a pretty amazing set of loop holes in the old pass manager's analysis
management code which allowed analysis groups to slide through in many
cases. Moving away from analysis groups makes this problem much more
obvious. To fix it, I've leveraged the flexibility the design of the new
PM components provides to just directly construct the relevant alias
analyses for the relevant functions in the IPO passes that need them.
This is a bit hacky, but should go away with the new pass manager, and
is already in many ways cleaner than the prior state.

Another significant challenge is that various facilities of the old
alias analysis infrastructure just don't fit any more. The most
significant of these is the alias analysis 'counter' pass. That pass
relied on the ability to snoop on AA queries at different points in the
analysis group chain. Instead, I'm planning to build printing
functionality directly into the aggregation layer. I've not included
that in this patch merely to keep it smaller.

Note that all of this needs a nearly complete rewrite of the AA
documentation. I'm planning to do that, but I'd like to make sure the
new design settles, and to flesh out a bit more of what it looks like in
the new pass manager first.

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

llvm-svn: 247167

show more ...


# 5989bc6f 31-Aug-2015 Quentin Colombet <qcolombet@apple.com>

[BasicAA] Fix the handling of sext and zext in the analysis of GEPs.
Hopefully this will end the GEPs saga!

This commit reverts r245394, i.e., it reapplies r221876 while incorporating the
fixes from

[BasicAA] Fix the handling of sext and zext in the analysis of GEPs.
Hopefully this will end the GEPs saga!

This commit reverts r245394, i.e., it reapplies r221876 while incorporating the
fixes from D11847.
r221876 was not reapplied alone because it was not safe and D11847 was not
applied alone because it needs r221876 to produce correct results.

This should fix PR24596.

Original commit message for r221876:
Let's try this again...

This reverts r219432, plus a bug fix.

Description of the bug in r219432 (by Nick):

The bug was using AllPositive to break out of the loop; if the loop break
condition i != e is changed to i != e && AllPositive then the
test_modulo_analysis_with_global test I've added will fail as the Modulo will
be calculated incorrectly (as the last loop iteration is skipped, so Modulo
isn't updated with its Scale).

Nick also adds this comment:

ComputeSignBit is safe to use in loops as it takes into account phi nodes, and
the == EK_ZeroEx check is safe in loops as, no matter how the variable changes
between iterations, zero-extensions will always guarantee a zero sign bit. The
isValueEqualInPotentialCycles check is therefore definitely not needed as all
the variable analysis holds no matter how the variables change between loop
iterations.

And this patch also adds another enhancement to GetLinearExpression - basically
to convert ConstantInts to Offsets (see test_const_eval and
test_const_eval_scaled for the situations this improves).

Original commit message:

This reverts r218944, which reverted r218714, plus a bug fix.

Description of the bug in r218714 (by Nick):

The original patch forgot to check if the Scale in VariableGEPIndex flipped the
sign of the variable. The BasicAA pass iterates over the instructions in the
order they appear in the function, and so BasicAliasAnalysis::aliasGEP is
called with the variable it first comes across as parameter GEP1. Adding a
%reorder label puts the definition of %a after %b so aliasGEP is called with %b
as the first parameter and %a as the second. aliasGEP later calculates that %a
== %b + 1 - %idxprom where %idxprom >= 0 (if %a was passed as the first
parameter it would calculate %b == %a - 1 + %idxprom where %idxprom >= 0) -
ignoring that %idxprom is scaled by -1 here lead the patch to incorrectly
conclude that %a > %b.

Revised patch by Nick White, thanks! Thanks to Lang to isolating the bug.
Slightly modified by me to add an early exit from the loop and avoid
unnecessary, but expensive, function calls.

Original commit message:

Two related things:

1. Fixes a bug when calculating the offset in GetLinearExpression. The code
previously used zext to extend the offset, so negative offsets were converted
to large positive ones.

2. Enhance aliasGEP to deduce that, if the difference between two GEP
allocations is positive and all the variables that govern the offset are also
positive (i.e. the offset is strictly after the higher base pointer), then
locations that fit in the gap between the two base pointers are NoAlias.

Patch by Nick White!

Message from D11847:
Un-revert of r241981 and fix for PR23626. The 'Or' case of GetLinearExpression
delegates to 'Add' if possible, and if not it returns an Opaque value.
Unfortunately the Scale and Offsets weren't being set (and so defaulted to 0) -
and a scale of zero effectively removes the variable from the GEP instruction.
This meant that BasicAA would return MustAliases when it should have been
returning PartialAliases (and PR23626 was an example of the GVN pass using an
incorrect MustAlias to merge loads from what should have been different
pointers).

Differential Revision: http://reviews.llvm.org/D11847
Patch by Nick White <n.j.white@gmail.com>!

llvm-svn: 246502

show more ...


Revision tags: llvmorg-3.7.0, llvmorg-3.7.0-rc4, llvmorg-3.7.0-rc3
# b700e357 19-Aug-2015 Quentin Colombet <qcolombet@apple.com>

[BasicAA] Revert r221876 because it can produce incorrect aliasing
information: see PR24468.

llvm-svn: 245394


# b20bda77 17-Aug-2015 Igor Laevsky <igmyrj@gmail.com>

[BasicAliasAnalysis] Do not check ModRef table for intrinsics

All possible ModRef behaviours can be completely represented using existing LLVM IR attributes.

Differential Revision: http://reviews.l

[BasicAliasAnalysis] Do not check ModRef table for intrinsics

All possible ModRef behaviours can be completely represented using existing LLVM IR attributes.

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

llvm-svn: 245224

show more ...


Revision tags: studio-1.4
# c5d81125 06-Aug-2015 Chandler Carruth <chandlerc@gmail.com>

[PM/AA] Clean up and homogenize comments throughout basic-aa.

llvm-svn: 244200


# 903c5f93 06-Aug-2015 Chandler Carruth <chandlerc@gmail.com>

[PM/AA] Run clang-format over all of basic-aa before making more
substantive edits.

llvm-svn: 244198


# 17e0bc37 06-Aug-2015 Chandler Carruth <chandlerc@gmail.com>

[PM/AA] Hoist the interface for BasicAA into a header file.

This is the first mechanical step in preparation for making this and all
the other alias analysis passes available to the new pass manager

[PM/AA] Hoist the interface for BasicAA into a header file.

This is the first mechanical step in preparation for making this and all
the other alias analysis passes available to the new pass manager. I'm
factoring out all the totally boring changes I can so I'm moving code
around here with no other changes. I've even minimized the formatting
churn.

I'll reformat and freshen comments on the interface now that its located
in the right place so that the substantive changes don't triger this.

llvm-svn: 244197

show more ...


# d67daae4 05-Aug-2015 Wei Mi <wmi@google.com>

Add a stat to show how often the limit to decompose GEPs in BasicAA is reached.

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

llvm-svn: 244174


Revision tags: llvmorg-3.7.0-rc2
# 194f59ca 22-Jul-2015 Chandler Carruth <chandlerc@gmail.com>

[PM/AA] Extract the ModRef enums from the AliasAnalysis class in
preparation for de-coupling the AA implementations.

In order to do this, they had to become fake-scoped using the
traditional LLVM pa

[PM/AA] Extract the ModRef enums from the AliasAnalysis class in
preparation for de-coupling the AA implementations.

In order to do this, they had to become fake-scoped using the
traditional LLVM pattern of a leading initialism. These can't be actual
scoped enumerations because they're bitfields and thus inherently we use
them as integers.

I've also renamed the behavior enums that are specific to reasoning
about the mod/ref behavior of functions when called. This makes it more
clear that they have a very narrow domain of applicability.

I think there is a significantly cleaner API for all of this, but
I don't want to try to do really substantive changes for now, I just
want to refactor the things away from analysis groups so I'm preserving
the exact original design and just cleaning up the names, style, and
lifting out of the class.

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

llvm-svn: 242963

show more ...


Revision tags: llvmorg-3.7.0-rc1
# d8ce16b1 15-Jul-2015 Tobias Edler von Koch <tobias@codeaurora.org>

Analyze recursive PHI nodes in BasicAA

Summary:
This patch allows phi nodes like
%x = phi [ %incptr, ... ] [ %var, ... ]
%incptr = getelementptr %x, 1
to be analyzed by BasicAliasAnalysis.

In a

Analyze recursive PHI nodes in BasicAA

Summary:
This patch allows phi nodes like
%x = phi [ %incptr, ... ] [ %var, ... ]
%incptr = getelementptr %x, 1
to be analyzed by BasicAliasAnalysis.

In aliasPHI, we can detect incoming values that are recursive GEPs with a
constant offset. Instead of trying to analyze a recursive GEP (and failing),
we now ignore it and instead set the size of the memory referenced by
the PHINode to UnknownSize. This represents all the possible memory
locations the pointer represented by the PHINode could be advanced to
by the GEP.

For now, this new behavior is turned off by default to allow debugging of
performance degradations seen with SPEC/x86 and Hexagon benchmarks.
The flag -basicaa-recphi turns it on.


Reviewers: hfinkel, sanjoy

Subscribers: tobiasvk_caf, sanjoy, llvm-commits

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

llvm-svn: 242320

show more ...


# 779cf85a 13-Jul-2015 Manuel Klimek <klimek@google.com>

Revert r241981 "Revert "Revert r236894 "[BasicAA] Fix zext & sext handling"""

The repros from PR23626 still fail.

llvm-svn: 242025


# ef28aad9 11-Jul-2015 Hal Finkel <hfinkel@anl.gov>

Revert "Revert r236894 "[BasicAA] Fix zext & sext handling""

r236894 caused PR23626 (Clang miscompiles webkit's base64 decoder), and was
reverted in r237984. This reapplies the patch with an additio

Revert "Revert r236894 "[BasicAA] Fix zext & sext handling""

r236894 caused PR23626 (Clang miscompiles webkit's base64 decoder), and was
reverted in r237984. This reapplies the patch with an additional test case for
PR23626 and the associated fix (both scales and offsets in the
BasicAliasAnalysis::constantOffsetHeuristic should initially be zero).

Patch by Nick White, thanks!

llvm-svn: 241981

show more ...


# 39d662f7 11-Jul-2015 Igor Laevsky <igmyrj@gmail.com>

Add argmemonly attribute.

This change adds new attribute called "argmemonly". Function marked with this attribute can only access memory through it's argument pointers. This attribute directly corre

Add argmemonly attribute.

This change adds new attribute called "argmemonly". Function marked with this attribute can only access memory through it's argument pointers. This attribute directly corresponds to the "OnlyAccessesArgumentPointees" ModRef behaviour in alias analysis.

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

llvm-svn: 241979

show more ...


Revision tags: llvmorg-3.6.2, llvmorg-3.6.2-rc1
# f00654e3 23-Jun-2015 Alexander Kornienko <alexfh@google.com>

Revert r240137 (Fixed/added namespace ending comments using clang-tidy. NFC)

Apparently, the style needs to be agreed upon first.

llvm-svn: 240390


# c3f49eb4 22-Jun-2015 Chandler Carruth <chandlerc@gmail.com>

[PM/AA] Hoist the AliasResult enum out of the AliasAnalysis class.

This will allow classes to implement the AA interface without deriving
from the class or referencing an internal enum of some other

[PM/AA] Hoist the AliasResult enum out of the AliasAnalysis class.

This will allow classes to implement the AA interface without deriving
from the class or referencing an internal enum of some other class as
their return types.

Also, to a pretty fundamental extent, concepts such as 'NoAlias',
'MayAlias', and 'MustAlias' are first class concepts in LLVM and we
aren't saving anything by scoping them heavily.

My mild preference would have been to use a scoped enum, but that
feature is essentially completely broken AFAICT. I'm extremely
disappointed. For example, we cannot through any reasonable[1] means
construct an enum class (or analog) which has scoped names but converts
to a boolean in order to test for the possibility of aliasing.

[1]: Richard Smith came up with a "solution", but it requires class
templates, and lots of boilerplate setting up the enumeration multiple
times. Something like Boost.PP could potentially bundle this up, but
even that would be quite painful and it doesn't seem realistically worth
it. The enum class solution would probably work without the need for
a bool conversion.

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

llvm-svn: 240255

show more ...


# 70bc5f13 19-Jun-2015 Alexander Kornienko <alexfh@google.com>

Fixed/added namespace ending comments using clang-tidy. NFC

The patch is generated using this command:

tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py -fix \
-checks=-*,llvm-namespace-c

Fixed/added namespace ending comments using clang-tidy. NFC

The patch is generated using this command:

tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py -fix \
-checks=-*,llvm-namespace-comment -header-filter='llvm/.*|clang/.*' \
llvm/lib/


Thanks to Eugene Kosov for the original patch!

llvm-svn: 240137

show more ...


# ecbd1682 17-Jun-2015 Chandler Carruth <chandlerc@gmail.com>

[PM/AA] Remove the UnknownSize static member from AliasAnalysis.

This is now living in MemoryLocation, which is what it pertains to. It
is also an enum there rather than a static data member which i

[PM/AA] Remove the UnknownSize static member from AliasAnalysis.

This is now living in MemoryLocation, which is what it pertains to. It
is also an enum there rather than a static data member which is left
never defined.

llvm-svn: 239886

show more ...


# ac80dc75 17-Jun-2015 Chandler Carruth <chandlerc@gmail.com>

[PM/AA] Remove the Location typedef from the AliasAnalysis class now
that it is its own entity in the form of MemoryLocation, and update all
the callers.

This is an entirely mechanical change. Refer

[PM/AA] Remove the Location typedef from the AliasAnalysis class now
that it is its own entity in the form of MemoryLocation, and update all
the callers.

This is an entirely mechanical change. References to "Location" within
AA subclases become "MemoryLocation", and elsewhere
"AliasAnalysis::Location" becomes "MemoryLocation". Hope that helps
out-of-tree folks update.

llvm-svn: 239885

show more ...


1...<<11121314151617181920>>...32