summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* Fix msc17 build. RegionInfo::RegionInfo::recalculate() doesn't make sense.NAKAMURA Takumi2014-07-201-4/+2
| | | | llvm-svn: 213466
* Fix -Asserts build introduced since r213456.NAKAMURA Takumi2014-07-201-0/+2
| | | | llvm-svn: 213465
* Templatify RegionInfo so it works on MachineBasicBlocksMatt Arsenault2014-07-194-789/+96
| | | | llvm-svn: 213456
* Remove uses of the redundant ".reset(nullptr)" of unique_ptr, in favor of ↵David Blaikie2014-07-191-1/+1
| | | | | | | | | | | ".reset()" It's also possible to just write "= nullptr", but there's some question of whether that's as readable, so I leave it up to authors to pick which they prefer for now. If we want to discuss standardizing on one or the other, we can do that at some point in the future. llvm-svn: 213438
* Add a dereferenceable attributeHal Finkel2014-07-181-1/+1
| | | | | | | | | This attribute indicates that the parameter or return pointer is dereferenceable. Practically speaking, loads from such a pointer within the associated byte range are safe to speculatively execute. Such pointer parameters are common in source languages (C++ references, for example). llvm-svn: 213385
* Rectify r213231. Use proper version of 'ComputeNumSignBits'.Suyog Sarda2014-07-171-1/+1
| | | | | | | | | Earlier when the code was in InstCombine, we were calling the version of ComputeNumSignBits in InstCombine.h that automatically added the DataLayout* before calling into ValueTracking. When the code moved to InstSimplify, we are calling into ValueTracking directly without passing in the DataLayout*. This patch rectifies the same by passing DataLayout in ComputeNumSignBits. llvm-svn: 213295
* Move ashr optimization from InstCombineShift to InstSimplify.Suyog Sarda2014-07-171-0/+5
| | | | | | | | | Refactor code, no functionality change, test case moved from instcombine to instsimplify. Differential Revision: http://reviews.llvm.org/D4102 llvm-svn: 213231
* Improve BasicAA CS-CS queries (redux)Hal Finkel2014-07-173-130/+151
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This reverts, "r213024 - Revert r212572 "improve BasicAA CS-CS queries", it causes PR20303." with a fix for the bug in pr20303. As it turned out, the relevant code was both wrong and over-conservative (because, as with the code it replaced, it would return the overall ModRef mask even if just Ref had been implied by the argument aliasing results). Hopefully, this correctly fixes both problems. Thanks to Nick Lewycky for reducing the test case for pr20303 (which I've cleaned up a little and added in DSE's test directory). The BasicAA test has also been updated to check for this error. Original commit message: BasicAA contains knowledge of certain intrinsics, such as memcpy and memset, and uses that information to form more-accurate answers to CallSite vs. Loc ModRef queries. Unfortunately, it did not use this information when answering CallSite vs. CallSite queries. Generically, when an intrinsic takes one or more pointers and the intrinsic is marked only to read/write from its arguments, the offset/size is unknown. As a result, the generic code that answers CallSite vs. CallSite (and CallSite vs. Loc) queries in AA uses UnknownSize when forming Locs from an intrinsic's arguments. While BasicAA's CallSite vs. Loc override could use more-accurate size information for some intrinsics, it did not do the same for CallSite vs. CallSite queries. This change refactors the intrinsic-specific logic in BasicAA into a generic AA query function: getArgLocation, which is overridden by BasicAA to supply the intrinsic-specific knowledge, and used by AA's generic implementation. This allows the intrinsic-specific knowledge to be used by both CallSite vs. Loc and CallSite vs. CallSite queries, and simplifies the BasicAA implementation. Currently, only one function, Mac's memset_pattern16, is handled by BasicAA (all the rest are intrinsics). As a side-effect of this refactoring, BasicAA's getModRefBehavior override now also returns OnlyAccessesArgumentPointees for this function (which is an improvement). llvm-svn: 213219
* Teach computeKnownBits to look through addrspacecast.Matt Arsenault2014-07-151-0/+2
| | | | | | This fixes inferring alignment through an addrspacecast. llvm-svn: 213030
* Teach GetUnderlyingObject / BasicAA about addrspacecastMatt Arsenault2014-07-152-2/+4
| | | | llvm-svn: 213025
* Revert r212572 "improve BasicAA CS-CS queries", it causes PR20303.Nick Lewycky2014-07-153-142/+126
| | | | llvm-svn: 213024
* Look through addrspacecast in IsConstantOffsetFromGlobalMatt Arsenault2014-07-141-1/+2
| | | | llvm-svn: 213000
* Look through addrspacecast in GetPointerBaseWithConstantOffsetMatt Arsenault2014-07-141-1/+2
| | | | llvm-svn: 212999
* InstSimplify: Correct sdiv x / -1David Majnemer2014-07-141-11/+13
| | | | | | | | | | | Determining the bounds of x/ -1 would start off with us dividing it by INT_MIN. Suffice to say, this would not work very well. Instead, handle it upfront by checking for -1 and mapping it to the range: [INT_MIN + 1, INT_MAX. This means that the result of our division can be any value other than INT_MIN. llvm-svn: 212981
* InstSimplify: The upper bound of X / C was missing a rounding stepDavid Majnemer2014-07-141-1/+9
| | | | | | | | | | | | | | | | | | Summary: When calculating the upper bound of X / -8589934592, we would perform the following calculation: Floor[INT_MAX / 8589934592] However, flooring the result would make us wrongly come to the conclusion that 1073741824 was not in the set of possible values. Instead, use the ceiling of the result. Reviewers: nicholas Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D4502 llvm-svn: 212976
* Templatify DominanceFrontier.Matt Arsenault2014-07-121-109/+26
| | | | | | Theoretically this should now work for MachineBasicBlocks. llvm-svn: 212885
* BFI: Add constructor for WeightDuncan P. N. Exon Smith2014-07-121-5/+1
| | | | llvm-svn: 212868
* BFI: Clean up BlockMassDuncan P. N. Exon Smith2014-07-121-10/+0
| | | | | | | | | | | | | | Implementation is small now -- the interesting logic was moved to `BranchProbability` a while ago. Move it into `bfi_detail` and get rid of the related TODOs. I was originally planning to define it within `BlockFrequencyInfoImpl` (or `BFIIBase`), but it seems cleaner in a namespace. Besides, `isPodLike` needs to be specialized before `BlockMass` can be used in some of the other data structures, and there isn't a clear way to do that. llvm-svn: 212866
* BFI: Mark the end of namespacesDuncan P. N. Exon Smith2014-07-111-1/+2
| | | | llvm-svn: 212861
* Allow isDereferenceablePointer to look through some bitcastsHal Finkel2014-07-101-1/+1
| | | | | | | | | | | | | | | | isDereferenceablePointer should not give up upon encountering any bitcast. If we're casting from a pointer to a larger type to a pointer to a small type, we can continue by examining the bitcast's operand. This missing capability was noted in a comment in the function. In order for this to work, isDereferenceablePointer now takes an optional DataLayout pointer (essentially all callers already had such a pointer available). Most code uses isDereferenceablePointer though isSafeToSpeculativelyExecute (which already took an optional DataLayout pointer), and to enable the LICM test case, LICM needs to actually provide its DL pointer to isSafeToSpeculativelyExecute (which it was not doing previously). llvm-svn: 212686
* Improve BasicAA CS-CS queriesHal Finkel2014-07-083-126/+142
| | | | | | | | | | | | | | | | | | | | | | | | | | | | BasicAA contains knowledge of certain intrinsics, such as memcpy and memset, and uses that information to form more-accurate answers to CallSite vs. Loc ModRef queries. Unfortunately, it did not use this information when answering CallSite vs. CallSite queries. Generically, when an intrinsic takes one or more pointers and the intrinsic is marked only to read/write from its arguments, the offset/size is unknown. As a result, the generic code that answers CallSite vs. CallSite (and CallSite vs. Loc) queries in AA uses UnknownSize when forming Locs from an intrinsic's arguments. While BasicAA's CallSite vs. Loc override could use more-accurate size information for some intrinsics, it did not do the same for CallSite vs. CallSite queries. This change refactors the intrinsic-specific logic in BasicAA into a generic AA query function: getArgLocation, which is overridden by BasicAA to supply the intrinsic-specific knowledge, and used by AA's generic implementation. This allows the intrinsic-specific knowledge to be used by both CallSite vs. Loc and CallSite vs. CallSite queries, and simplifies the BasicAA implementation. Currently, only one function, Mac's memset_pattern16, is handled by BasicAA (all the rest are intrinsics). As a side-effect of this refactoring, BasicAA's getModRefBehavior override now also returns OnlyAccessesArgumentPointees for this function (which is an improvement). llvm-svn: 212572
* fixed typos in commentsSanjay Patel2014-07-061-2/+2
| | | | llvm-svn: 212424
* InstSimplify: Fix a bug when INT_MIN is in a sdivDavid Majnemer2014-07-041-3/+9
| | | | | | | | | | | | | When INT_MIN is the numerator in a sdiv, we would not properly handle overflow when calculating the bounds of possible values; abs(INT_MIN) is not a meaningful number. Instead, check and handle INT_MIN by reasoning that the largest value is INT_MIN/-2 and the smallest value is INT_MIN. This fixes PR20199. llvm-svn: 212307
* [CostModel][x86] Improved cost model for alternate shuffles.Andrea Di Biagio2014-07-031-3/+34
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch: 1) Improves the cost model for x86 alternate shuffles (originally added at revision 211339); 2) Teaches the Cost Model Analysis pass how to analyze alternate shuffles. Alternate shuffles are a special kind of blend; on x86, we can often easily lowered alternate shuffled into single blend instruction (depending on the subtarget features). The existing cost model didn't take into account subtarget features. Also, it had a couple of "dead" entries for vector types that are never legal (example: on x86 types v2i32 and v2f32 are not legal; those are always either promoted or widened to 128-bit vector types). The new x86 cost model takes into account what target features we have before returning the shuffle cost (i.e. the number of instructions after the blend is lowered/expanded). This patch also teaches the Cost Model Analysis how to identify and analyze alternate shuffles (i.e. 'SK_Alternate' shufflevector instructions): - added function 'isAlternateVectorMask'; - added some logic to check if an instruction is a alternate shuffle and, in case, call the target specific TTI to get the corresponding shuffle cost; - added a test to verify the cost model analysis on alternate shuffles. llvm-svn: 212296
* Add new lines to debugging information.Richard Trieu2014-07-031-1/+1
| | | | | | Differential Revision: http://reviews.llvm.org/D4262 llvm-svn: 212250
* Suppress inlining when the block address is takenGerolf Hoflehner2014-07-011-6/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Inlining functions with block addresses can cause many problem and requires a rich infrastructure to support including escape analysis. At this point the safest approach to address these problems is by blocking inlining from happening. Background: There have been reports on Ruby segmentation faults triggered by inlining functions with block addresses like //Ruby code snippet vm_exec_core() { finish_insn_seq_0 = &&INSN_LABEL_finish; INSN_LABEL_finish: ; } This kind of scenario can also happen when LLVM picks a subset of blocks for inlining, which is the case with the actual code in the Ruby environment. LLVM suppresses inlining for such functions when there is an indirect branch. The attached patch does so even when there is no indirect branch. Note that user code like above would not make much sense: using the global for jumping across function boundaries would be illegal. Why was there a segfault: In the snipped above the block with the label is recognized as dead So it is eliminated. Instead of a block address the cloner stores a constant (sic!) into the global resulting in the segfault (when the global is used in a goto). Why had it worked in the past then: By luck. In older versions vm_exec_core was also inlined but the label address used was the block label address in vm_exec_core. So the global jump ended up in the original function rather than in the caller which accidentally happened to work. Test case ./tools/clang/test/CodeGen/indirect-goto.c will fail as a result of this commit. rdar://17245966 llvm-svn: 212077
* Revert "Introduce a string_ostream string builder facilty"Alp Toker2014-06-263-11/+12
| | | | | | Temporarily back out commits r211749, r211752 and r211754. llvm-svn: 211814
* This patch removed duplicate code for matching patterns Dinesh Dwivedi2014-06-261-106/+1
| | | | | | | | | which are now handled in SimplifyUsingDistributiveLaws() (after r211261) Differential Revision: http://reviews.llvm.org/D4253 llvm-svn: 211768
* MSVC build fix following r211749Alp Toker2014-06-261-2/+4
| | | | | | Avoid strndup() llvm-svn: 211752
* Introduce a string_ostream string builder faciltyAlp Toker2014-06-263-11/+8
| | | | | | | | | | | | | | | | | | | | string_ostream is a safe and efficient string builder that combines opaque stack storage with a built-in ostream interface. small_string_ostream<bytes> additionally permits an explicit stack storage size other than the default 128 bytes to be provided. Beyond that, storage is transferred to the heap. This convenient class can be used in most places an std::string+raw_string_ostream pair or SmallString<>+raw_svector_ostream pair would previously have been used, in order to guarantee consistent access without byte truncation. The patch also converts much of LLVM to use the new facility. These changes include several probable bug fixes for truncated output, a programming error that's no longer possible with the new interface. llvm-svn: 211749
* Support: Move class ScaledNumberDuncan P. N. Exon Smith2014-06-241-190/+0
| | | | | | | | ScaledNumber has been cleaned up enough to pull out of BFI now. Still work to do there (tests for shifting, bloated printing code, etc.), but it seems clean enough for its new home. llvm-svn: 211562
* BFI: Un-floatify more languageDuncan P. N. Exon Smith2014-06-241-23/+24
| | | | llvm-svn: 211561
* Support: Extract ScaledNumbers::MinScale and MaxScaleDuncan P. N. Exon Smith2014-06-241-10/+5
| | | | llvm-svn: 211558
* BFI: Change language from "exponent" to "scale"Duncan P. N. Exon Smith2014-06-231-8/+8
| | | | llvm-svn: 211557
* BFI: Rename UnsignedFloat => ScaledNumberDuncan P. N. Exon Smith2014-06-231-17/+17
| | | | | | | A lot of the docs and API are out of date, but I'll leave that for a separate commit. llvm-svn: 211555
* SCEVExpander: Fold constant PHIs harder. The logic below only understands ↵Benjamin Kramer2014-06-211-1/+2
| | | | | | | | proper IVs. PR20093. llvm-svn: 211433
* Add back functionality removed in r210497.Richard Trieu2014-06-214-8/+16
| | | | | | Instead of asserting, output a message stating that a null pointer was found. llvm-svn: 211430
* Support: Write ScaledNumber::getQuotient() and getProduct()Duncan P. N. Exon Smith2014-06-201-91/+0
| | | | llvm-svn: 211409
* [ValueTracking] Extend range metadata to call/invokeJingyue Wu2014-06-191-5/+12
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: With this patch, range metadata can be added to call/invoke including IntrinsicInst. Previously, it could only be added to load. Rename computeKnownBitsLoad to computeKnownBitsFromRangeMetadata because range metadata is not only used by load. Update the language reference to reflect this change. Test Plan: Add several tests in range-2.ll to confirm the verifier is happy with having range metadata on call/invoke. Add two tests in AddOverFlow.ll to confirm annotating range metadata to call/invoke can benefit InstCombine. Reviewers: meheff, nlewycky, reames, hfinkel, eliben Reviewed By: eliben Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D4187 llvm-svn: 211281
* Move optimization of some cases of (A & C1)|(B & C2) from instcombine to ↵Nick Lewycky2014-06-191-0/+32
| | | | | | instsimplify. Patch by Rahul Jain, plus some last minute changes by me -- you can blame me for any bugs. llvm-svn: 211252
* Make instsimplify's analysis of icmp eq/ne use computeKnownBits to determine ↵Nick Lewycky2014-06-191-0/+19
| | | | | | whether the icmp is always true or false. Patch by Suyog Sarda! llvm-svn: 211251
* Removing an "if (!this)" check from two print methods. The condition willRichard Trieu2014-06-094-2/+8
| | | | | | | never be true in a well-defined context. The checking for null pointers has been moved into the caller logic so it does not rely on undefined behavior. llvm-svn: 210497
* Remove old fenv.h workaround for a historic clang driver bugAlp Toker2014-06-091-9/+2
| | | | | | | | | | | Tested and works fine with clang using libstdc++. All indications are that this was fixed some time ago and isn't a problem with any clang version we support. I've added a note in PR6907 which is still open for some reason. llvm-svn: 210485
* Fold FEnv.h into the implementationAlp Toker2014-06-091-7/+41
| | | | | | | | | | | | | | | | | | Support headers shouldn't use config.h definitions, and they should never be undefined like this. ConstantFolding.cpp was the only user of this facility and already includes config.h for other math features, so it makes sense to move the checks there at point of use. (The implicit config.h was also quite dangerous -- removing the FEnv.h include would have silently disabled math constant folding without causing any tests to fail. Need to investigate -Wundef once the cleanup is done.) This eliminates the last config.h include from LLVM headers, paving the way for more consistent configuration checks. llvm-svn: 210483
* ScalarEvolution: Derive element size from the type of the loaded elementTobias Grosser2014-06-081-1/+1
| | | | | | | | | | Before, we where looking at the size of the pointer type that specifies the location from which to load the element. This did not make any sense at all. This change fixes a bug in the delinearization where we failed to delinerize certain load instructions. llvm-svn: 210435
* Add a new attribute called 'jumptable' that creates jump-instruction tables ↵Tom Roeder2014-06-053-0/+42
| | | | | | | | | | | | for functions marked with this attribute. It includes a pass that rewrites all indirect calls to jumptable functions to pass through these tables. This also adds backend support for generating the jump-instruction tables on ARM and X86. Note that since the jumptable attribute creates a second function pointer for a function, any function marked with jumptable must also be marked with unnamed_addr. llvm-svn: 210280
* Add a Constant version of stripPointerCasts.Rafael Espindola2014-06-041-1/+1
| | | | | | Thanks to rnk for the suggestion. llvm-svn: 210205
* implement missing SCEVDivision caseSebastian Pop2014-05-291-0/+9
| | | | | | | | without this case we would end on an infinite recursion: the remainder is zero, so Numerator - Remainder is equal to Numerator and so we would recursively ask for the division of Numerator by Denominator. llvm-svn: 209838
* fail to find dimensions when ElementSize is nullptrSebastian Pop2014-05-291-1/+1
| | | | | | | | when ScalarEvolution::getElementSize returns nullptr it is safe to early return in ScalarEvolution::findArrayDimensions such that we avoid later problems when we try to divide the terms by ElementSize. llvm-svn: 209837
* test check-in: added missing parenthesis in commentSanjay Patel2014-05-281-1/+1
| | | | llvm-svn: 209763
OpenPOWER on IntegriCloud