summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* Revert r243250Jingyue Wu2015-07-261-2/+4
| | | | | | breaks tests llvm-svn: 243251
* [TTI/CostModel] improve TTI::getGEPCost and use it in ↵Jingyue Wu2015-07-261-4/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | CostModel::getInstructionCost Summary: This patch updates TargetTransformInfoImplCRTPBase::getGEPCost to consider addressing modes. It now returns TCC_Free when the GEP can be completely folded to an addresing mode. I started this patch as I refactored SLSR. Function isGEPFoldable looks common and is indeed used by some WIP of mine. So I extracted that logic to getGEPCost. Furthermore, I noticed getGEPCost wasn't directly tested anywhere. The best testing bed seems CostModel, but its getInstructionCost method invokes getAddressComputationCost for GEPs which provides very coarse estimation. So this patch also makes getInstructionCost call the updated getGEPCost for GEPs. This change inevitably breaks some tests because the cost model changes, but nothing looks seriously wrong -- if we believe the new cost model is the right way to go, these tests should be updated. This patch is not perfect yet -- the comments in some tests need to be updated. I want to know whether this is a right approach before fixing those details. Reviewers: chandlerc, hfinkel Subscribers: aschwaighofer, llvm-commits, aemerson Differential Revision: http://reviews.llvm.org/D9819 llvm-svn: 243250
* [LAA] Begin moving the logic of generating checks out of addRuntimeCheckAdam Nemet2015-07-261-69/+111
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: The goal is to start moving us closer to the model where RuntimePointerChecking will compute and store the checks. Then a client can filter the check according to its requirements and then use the filtered list of checks with addRuntimeCheck. Before the patch, this is all done in addRuntimeCheck. So the patch starts to split up addRuntimeCheck while providing the old API under what's more or less a wrapper now. The new underlying addRuntimeCheck takes a collection of checks now, expands the code for the bounds then generates the code for the checks. I am not completely happy with making expandBounds static because now it needs so many explicit arguments but I don't want to make the type PointerBounds part of LAI. This should get fixed when addRuntimeCheck is moved to LoopVersioning where it really belongs, IMO. Audited the assembly diff of the testsuite (including externals). There is a tiny bit of assembly churn that is due to the different order the code for the bounds is expanded now (MultiSource/Benchmarks/Prolangs-C/bison/conflicts.s and with LoopDist on 456.hmmer/fast_algorithms.s). Reviewers: hfinkel Subscribers: klimek, llvm-commits Differential Revision: http://reviews.llvm.org/D11205 llvm-svn: 243239
* [GMR] Switch the function info we store for every function to be a muchChandler Carruth2015-07-231-23/+91
| | | | | | | | | | | | | | more dense datastructure. We actually only have 3 bits of information and an often-null pointer here. This fits very nicely into a pointer-size value in the DenseMap from Function -> Info. Then we take one more pointer hop to get to a secondary DenseMap from GlobalValue -> ModRefInfo when we actually have precise info for particular globals. This is more code than I would really like to do this packing, but it ended up reasonably cleanly laid out. It should ensure we don't hit scaling limitations with more widespread use of GMR. llvm-svn: 242991
* [ScalarEvolution] Change addRequired to addRequiredTransitive on two passes ↵Craig Topper2015-07-231-2/+2
| | | | | | | | | | | where ScalarEvolution stores long lived raw pointers to objects those passes own. This prevents the pointers from dangling when those passes are freed. http://reviews.llvm.org/D11236 Patch by Steve King. llvm-svn: 242989
* [GMR] Further improve the FunctionInfo API inside of GlobalsModRef, NFC.Chandler Carruth2015-07-231-24/+21
| | | | | | | | | | | | | This takes the operation of merging a callee's information into the current information and embeds it into the FunctionInfo type itself. This is much cleaner as now we don't need to expose iteration of the globals, etc. Also, switched all the uses of a raw integer two maintain the mod/ref info during the SCC walk into just directly manipulating it in the FunctionInfo object. llvm-svn: 242976
* [GMR] Wrap all of the per-function information behind a more stronglyChandler Carruth2015-07-221-63/+92
| | | | | | | | | | | typed interface as a precursor to rewriting how it is stored. This way we know that the access paths are controlled and it should be easy to store these bits in a different way. No functionality changed. llvm-svn: 242974
* [PM/AA] Extract the ModRef enums from the AliasAnalysis class inChandler Carruth2015-07-2213-309/+309
| | | | | | | | | | | | | | | | | | | | | | | 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
* [GMR] Continue my quest to remove linked datastructures from GMR, NFC.Chandler Carruth2015-07-221-3/+2
| | | | | | | | | This replaces the next-to-last std::map with a DenseMap. While DenseMap doesn't yet make tons of sense (there are 32 bytes or so in the value type), my next change will reduce the value type to a single pointer -- we only need a pointer and 3 bits, and that is exactly what we can have. llvm-svn: 242956
* [ConstantFolding] Support folding loads from a GlobalAliasDavid Majnemer2015-07-221-0/+4
| | | | | | | | | | | | | | The MSVC ABI requires that we generate an alias for the vtable which means looking through a GlobalAlias which cannot be overridden improves our ability to devirtualize. Found while investigating PR20801. Patch by Andrew Zhogin! Differential Revision: http://reviews.llvm.org/D11306 llvm-svn: 242955
* [GMR] Make the collection of readers and writers of globals much moreChandler Carruth2015-07-221-20/+22
| | | | | | | | | | | | | | | | | | | | | | | efficient, NFC. Previously, we built up vectors of function pointers to track readers and writers. The primary problem here is that we would add the same function to this vector every time we found an instruction that reads or writes to the pointer. This could be a *lot* of redudant function pointers. Instead of doing that, we can use a SmallPtrSet. This does more than just reduce the size of the list of readers or writers. We walk the entire lists of each and do a map lookup for each one. By having sets, we will only do one map lookup per reader or writer function. But only one user of the pointer analyzer actually needs this information, so we can also skip accumulating it (and doing a lot of heap allocations) for all the other pointer analysis. This is particularly useful because there are very many more pointers in some of the other cases. llvm-svn: 242950
* Fix -Wextra-semi warnings.Hans Wennborg2015-07-221-1/+1
| | | | | | | | Patch by Eugene Zelenko! Differential Revision: http://reviews.llvm.org/D11400 llvm-svn: 242930
* [GMR] Switch from std::set to SmallPtrSet. NFC.Chandler Carruth2015-07-221-3/+3
| | | | | | | | | This almost certainly doesn't matter in some deep sense, but std::set is essentially always going to be slower here. Now the alias query should be essentially constant time instead of having to chase the set tree each time. llvm-svn: 242893
* [GMR] Only look in the associated allocs map for an underlying value ifChandler Carruth2015-07-221-4/+4
| | | | | | | | it wasn't one of the indirect globals (which clearly cannot be an allocation function call). Also only do a single lookup into this map instead of two. NFC. llvm-svn: 242892
* [GMR] Switch to a DenseMap and clean up the iteration loop. NFC.Chandler Carruth2015-07-221-11/+6
| | | | | | | | | | | | | Since we have to iterate this map not that infrequently, we should use a map that is efficient for iteration. It is also almost certainly much faster for lookups as well. There is more to do in terms of reducing the wasted overhead of GMR's runtime though. Not sure how much is worthwhile though. The loop improvements should hopefully address the code review that Duncan gave when he saw this code as I moved it around. llvm-svn: 242891
* [PM/AA] Try to fix libc++ build bots which require the type used inChandler Carruth2015-07-221-40/+39
| | | | | | | std::list to be complete by hoisting the entire definition into the class. Ugly, but hopefully works. llvm-svn: 242888
* [PM/AA] Remove the last of the legacy update API from AliasAnalysis asChandler Carruth2015-07-225-17/+0
| | | | | | | | | | | | | part of simplifying its interface and usage in preparation for porting to work with the new pass manager. Note that this will likely expose that we have dead arguments, members, and maybe even pass requirements for AA. I'll be cleaning those up in seperate patches. This just zaps the actual update API. Differential Revision: http://reviews.llvm.org/D11325 llvm-svn: 242881
* [PM/AA] Put the 'final' keyword in the correct place. And actuallyChandler Carruth2015-07-221-1/+1
| | | | | | succeed at compiling my change before committing it too! llvm-svn: 242879
* [PM/AA] Replace the only use of the AliasAnalysis::deleteValue API (inChandler Carruth2015-07-221-35/+58
| | | | | | | | | | | | | | | | | | | | | | GlobalsModRef) with CallbackVHs that trigger the same behavior. This is technically more expensive, but in benchmarking some LTO runs, it seems unlikely to even be above the noise floor. The only way I was able to measure the performance of GMR at all was to run nothing else but this one analysis on a linked clang bitcode file. The call graph analysis still took 5x more time than GMR, and this change at most made GMR 2% slower (this is well within the noise, so its hard for me to be sure that this is an actual change). However, in a real LTO run over the same bitcode, the GMR run takes so little time that the pass timers don't measure it. With this, I can remove the last update API from the AliasAnalysis interface, but I'll actually remove the interface hook point in a follow-up commit. Differential Revision: http://reviews.llvm.org/D11324 llvm-svn: 242878
* [MDA] change BlockScanLimit into a command line option.Jingyue Wu2015-07-211-1/+5
| | | | | | | | | | | | | | | | | | | | Summary: In the benchmark (https://github.com/vetter/shoc) we are researching, the duplicated load is not eliminated because MemoryDependenceAnalysis hit the BlockScanLimit. This patch change it into a command line option instead of a hardcoded value. Patched by Xuetian Weng. Test Plan: test/Analysis/MemoryDependenceAnalysis/memdep-block-scan-limit.ll Reviewers: jingyue, reames Subscribers: reames, llvm-commits Differential Revision: http://reviews.llvm.org/D11366 llvm-svn: 242842
* [SCEV][NFC] Fix a typo in a comment.Sanjoy Das2015-07-211-6/+6
| | | | llvm-svn: 242834
* Constfold trunc,rint,nearbyint,ceil and floor using APFloatKarthik Bhat2015-07-211-4/+33
| | | | | | | | A patch by Chakshu Grover! This patch allows constfolding of trunc,rint,nearbyint,ceil and floor intrinsics using APFloat class. Differential Revision: http://reviews.llvm.org/D11144 llvm-svn: 242763
* [PM/AA] Remove the addEscapingUse update API that won't be easy toChandler Carruth2015-07-183-17/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | directly model in the new PM. This also was an incredibly brittle and expensive update API that was never fully utilized by all the passes that claimed to preserve AA, nor could it reasonably have been extended to all of them. Any number of places add uses of values. If we ever wanted to reliably instrument this, we would want a callback hook much like we have with ValueHandles, but doing this for every use addition seems *extremely* expensive in terms of compile time. The only user of this update mechanism is GlobalsModRef. The idea of using this to keep it up to date doesn't really work anyways as its analysis requires a symmetric analysis of two different memory locations. It would be very hard to make updates be sufficiently rigorous to *guarantee* symmetric analysis in this way, and it pretty certainly isn't true today. However, folks have been using GMR with this update for a long time and seem to not be hitting the issues. The reported issue that the update hook fixes isn't even a problem any more as other changes to GetUnderlyingObject worked around it, and that issue stemmed from *many* years ago. As a consequence, a prior patch provided a flag to control the unsafe behavior of GMR, and this patch removes the update mechanism that has questionable compile-time tradeoffs and is causing problems with moving to the new pass manager. Note the lack of test updates -- not one test in tree actually requires this update, even for a contrived case. All of this was extensively discussed on the dev list, this patch will just enact what that discussion decides on. I'm sending it for review in part to show what I'm planning, and in part to show the *amazing* amount of work this avoids. Every call to the AA here is something like three to six indirect function calls, which in the non-LTO pipeline never do any work! =[ Differential Revision: http://reviews.llvm.org/D11214 llvm-svn: 242605
* [PM/AA] Disable the core unsafe aspect of GlobalsModRef in the face ofChandler Carruth2015-07-171-6/+33
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | basic changes to the IR such as folding pointers through PHIs, Selects, integer casts, store/load pairs, or outlining. This leaves the feature available behind a flag. This flag's default could be flipped if necessary, but the real-world performance impact of this particular feature of GMR may not be sufficiently significant for many folks to want to run the risk. Currently, the risk here is somewhat mitigated by half-hearted attempts to update GlobalsModRef when the rest of the optimizer changes something. However, I am currently trying to remove that update mechanism as it makes migrating the AA infrastructure to a form that can be readily shared between new and old pass managers very challenging. Without this update mechanism, it is possible that this still unlikely failure mode will start to trip people, and so I wanted to try to proactively avoid that. There is a lengthy discussion on the mailing list about why the core approach here is flawed, and likely would need to look totally different to be both reasonably effective and resilient to basic IR changes occuring. This patch is essentially the first of two which will enact the result of that discussion. The next patch will remove the current update mechanism. Thanks to lots of folks that helped look at this from different angles. Especial thanks to Michael Zolotukhin for doing some very prelimanary benchmarking of LTO without GlobalsModRef to get a rough idea of the impact we could be facing here. So far, it looks very small, but there are some concerns lingering from other benchmarking. The default here may get flipped if performance results end up pointing at this as a more significant issue. Also thanks to Pete and Gerolf for reviewing! Differential Revision: http://reviews.llvm.org/D11213 llvm-svn: 242512
* Add new constructors for LoopInfo/DominatorTree/BFI/BPICong Hou2015-07-162-0/+12
| | | | | | | | | | | | | | | | | Those new constructors make it more natural to construct an object for a function. For example, previously to build a LoopInfo for a function, we need four statements: DominatorTree DT; LoopInfo LI; DT.recalculate(F); LI.analyze(DT); Now we only need one statement: LoopInfo LI(DominatorTree(F)); http://reviews.llvm.org/D11274 llvm-svn: 242486
* Rename LoopInfo::Analyze() to LoopInfo::analyze() and turn its parameter ↵Cong Hou2015-07-161-2/+2
| | | | | | | | | | type to const&. The benefit of turning the parameter of LoopInfo::analyze() to const& is that it now can accept a rvalue. http://reviews.llvm.org/D11250 llvm-svn: 242426
* Fix memcheck interval ends for pointers with negative stridesSilviu Baranga2015-07-161-2/+18
| | | | | | | | | | | | | | | | | | | | | | | | Summary: The checking pointer grouping algorithm assumes that the starts/ends of the pointers are well formed (start <= end). The runtime memory checking algorithm also assumes this by doing: start0 < end1 && start1 < end0 to detect conflicts. This check only works if start0 <= end0 and start1 <= end1. This change correctly orders the interval ends by either checking the stride (if it is constant) or by using min/max SCEV expressions. Reviewers: anemet, rengolin Subscribers: rengolin, llvm-commits Differential Revision: http://reviews.llvm.org/D11149 llvm-svn: 242400
* [LAA] Split out a helper to check the pointer partitions, NFCAdam Nemet2015-07-161-4/+8
| | | | | | | | | This is made a static public member function to allow the transition of this logic from LAA to LoopDistribution. (Technically, it could be an implementation-local static function but then it would not be accessible from LoopDistribution.) llvm-svn: 242376
* Create a wrapper pass for BranchProbabilityInfo.Cong Hou2015-07-153-49/+63
| | | | | | | | This new wrapper pass is useful when we want to do branch probability analysis conditionally (e.g. only in PGO mode) but don't want to add one more pass dependence. http://reviews.llvm.org/D11241 llvm-svn: 242349
* Rename doFunction() in BFI to calculate() and change its parameters from ↵Cong Hou2015-07-151-1/+1
| | | | | | | | pointers to references. http://reviews.llvm.org/D11196 llvm-svn: 242322
* Analyze recursive PHI nodes in BasicAATobias Edler von Koch2015-07-151-0/+26
| | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [PM/AA] Fix *numerous* serious bugs in GlobalsModRef found byChandler Carruth2015-07-151-22/+31
| | | | | | | | | | | | | | | | | | | | | | | | | inspection. While we want to handle calls specially in this code because they should have been modeled by the call graph analysis that precedes it, we should *not* be re-implementing the predicates for whether an instruction reads or writes memory. Those are well defined already. Notably, at least the following issues seem to be clearly missed before: - Ordered atomic loads can "write" to memory by causing writes from other threads to become visible. Similarly for ordered atomic stores. - AtomicRMW instructions quite obviously both read and write to memory. - AtomicCmpXchg instructions also read and write to memory. - Fences read and write to memory. - Invokes of intrinsics or memory allocation functions. I don't have any test cases, and I suspect this has never really come up in the real world. But there is no reason why it wouldn't, and it makes the code simpler to do this the right way. While here, I've tried to make the loops significantly simpler as well and added helpful comments as to what is going on. llvm-svn: 242281
* [PM/AA] Cleanup some loops to be range-based. NFC.Chandler Carruth2015-07-151-20/+19
| | | | llvm-svn: 242275
* Create a wrapper pass for BlockFrequencyInfo.Wei Mi2015-07-142-33/+49
| | | | | | | | | | | | This is useful when we want to do block frequency analysis conditionally (e.g. only in PGO mode) but don't want to add one more pass dependence. Patch by congh. Approved by dexonsmith. Differential Revision: http://reviews.llvm.org/D11196 llvm-svn: 242248
* [LAA] Introduce RuntimePointerChecking::PointerInfo, NFCAdam Nemet2015-07-141-29/+33
| | | | | | | Turn this structure-of-arrays (i.e. the various pointer attributes) into array-of-structures. llvm-svn: 242219
* [LAA] Lift RuntimePointerCheck out of LoopAccessInfo, NFCAdam Nemet2015-07-141-43/+41
| | | | | | | | | I am planning to add more nested classes inside RuntimePointerCheck so all these triple-nesting would be hard to follow. Also rename it to RuntimePointerChecking (i.e. append 'ing'). llvm-svn: 242218
* [PM/AA] Reformat GlobalsModRef so that subsequent patches I make hereChandler Carruth2015-07-141-155/+160
| | | | | | don't continually introduce formatting deltas. NFC llvm-svn: 242129
* Cleanup after r241809 - remove uncessary call to std::sortSilviu Baranga2015-07-131-10/+5
| | | | | | | | | | | | | | Summary: The iteration order within a member of DepCands is deterministic and therefore we don't have to sort the accesses within a member. We also don't have to copy the indices of the pointers into a vector, since we can iterate over the members of the class. Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D11145 llvm-svn: 242033
* Revert r241981 "Revert "Revert r236894 "[BasicAA] Fix zext & sext handling"""Manuel Klimek2015-07-131-199/+60
| | | | | | The repros from PR23626 still fail. llvm-svn: 242025
* [LSR] don't attempt to promote ephemeral values to indvarsJingyue Wu2015-07-131-1/+16
| | | | | | | | | | | | | | | | | Summary: This at least saves compile time. I also encountered a case where ephemeral values affect whether other variables are promoted, causing performance issues. It may be a bug in LSR, but I didn't manage to reduce it yet. Anyhow, I believe it's in general not worth considering ephemeral values in LSR. Reviewers: atrick, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D11115 llvm-svn: 242011
* [InstSimplify] Teach InstSimplify how to simplify extractelementDavid Majnemer2015-07-132-0/+100
| | | | llvm-svn: 242008
* [InstSimplify] Teach InstSimplify how to simplify extractvalueDavid Majnemer2015-07-131-0/+41
| | | | llvm-svn: 242007
* Revert "Revert r236894 "[BasicAA] Fix zext & sext handling""Hal Finkel2015-07-111-60/+199
| | | | | | | | | | | 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
* Move getStrideFromPointer and friends from LoopVectorize to VectorUtilsHal Finkel2015-07-111-0/+146
| | | | | | | | | | | | | | | | The following functions are moved from the LoopVectorizer to VectorUtils: - getGEPInductionOperand - stripGetElementPtr - getUniqueCastUse - getStrideFromPointer These used to be static functions in LoopVectorize, but will also be used by the upcoming loop versioning LICM transformation. Patch by Ashutosh Nema! llvm-svn: 241980
* Add argmemonly attribute.Igor Laevsky2015-07-111-0/+6
| | | | | | | | 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
* [PM/AA] Completely remove the AliasAnalysis::copyValue interface.Chandler Carruth2015-07-115-18/+0
| | | | | | | | | | | | | | | | | | | | | No in-tree alias analysis used this facility, and it was not called in any particularly rigorous way, so it seems unlikely to be correct. Note that one of the only stateful AA implementations in-tree, GlobalsModRef is completely broken currently (and any AA passes like it are equally broken) because Module AA passes are not effectively invalidated when a function pass that fails to update the AA stack runs. Ultimately, it doesn't seem like we know how we want to build stateful AA, and until then trying to support and maintain correctness for an untested API is essentially impossible. To that end, I'm planning to rip out all of the update API. It can return if and when we need it and know how to build it on top of the new pass manager and as part of *tested* stateful AA implementations in the tree. Differential Revision: http://reviews.llvm.org/D10889 llvm-svn: 241975
* [InstSimplify] Fold away ord/uno fcmps when nnan is present.Benjamin Kramer2015-07-101-8/+17
| | | | | | | This is important to fold away the slow case of complex multiplies emitted by clang. llvm-svn: 241911
* Revert the new EH instructionsDavid Majnemer2015-07-101-14/+0
| | | | | | This reverts commits r241888-r241891, I didn't mean to commit them. llvm-svn: 241893
* New EH representation for MSVC compatibilityDavid Majnemer2015-07-101-0/+14
| | | | | | | | | | | | | | | Summary: This introduces new instructions neccessary to implement MSVC-compatible exception handling support. Most of the middle-end and none of the back-end haven't been audited or updated to take them into account. Reviewers: rnk, JosephTremoulet, reames, nlewycky, rjmccall Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D11041 llvm-svn: 241888
* [LAA] Fix grammar in debug outputAdam Nemet2015-07-091-1/+1
| | | | llvm-svn: 241867
OpenPOWER on IntegriCloud