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