summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* [ValueTracking] Tweak a comment slightlyJames Molloy2015-08-121-2/+2
| | | | | | Hal asked for this change in D11146, but I missed it when I committed originally. llvm-svn: 244754
* Add support for floating-point minnum and maxnumJames Molloy2015-08-111-33/+130
| | | | | | | | | | | | | | | | | The select pattern recognition in ValueTracking (as used by InstCombine and SelectionDAGBuilder) only knew about integer patterns. This teaches it about minimum and maximum operations. matchSelectPattern() has been extended to return a struct containing the existing Flavor and a new enum defining the pattern's behavior when given one NaN operand. C minnum() is defined to return the non-NaN operand in this case, but the idiomatic C "a < b ? a : b" would return the NaN operand. ARM and AArch64 at least have different instructions for these different cases. llvm-svn: 244580
* [GMR] Be a bit smarter about which globals don't alias when doing recursive ↵Michael Kuperstein2015-08-111-7/+23
| | | | | | | | | | lookups Should hopefully fix the remainder of PR24288. Differential Revision: http://reviews.llvm.org/D11900 llvm-svn: 244575
* [LAA] Change name from addRuntimeCheck to addRuntimeChecks, NFCAdam Nemet2015-08-111-4/+4
| | | | | | This was requested by Hal in D11205. llvm-svn: 244540
* [IndVarSimplify] Make cost estimation in RewriteLoopExitValues smarterIgor Laevsky2015-08-101-6/+44
| | | | | | Differential Revision: http://reviews.llvm.org/D11687 llvm-svn: 244474
* [TTI] Add a hook for specifying per-target defaults for Interleaved AccessesSilviu Baranga2015-08-101-0/+4
| | | | | | | | | | | | | | | Summary: This adds a hook to TTI which enables us to selectively turn on by default interleaved access vectorization for targets on which we have have performed the required benchmarking. Reviewers: rengolin Subscribers: rengolin, llvm-commits Differential Revision: http://reviews.llvm.org/D11901 llvm-svn: 244449
* [RegionInfo] Add debug-time region viewer functionsMichael Kruse2015-08-102-0/+50
| | | | | | | | | | | | | | | Summary: Analogously to Function::viewCFG(), RegionInfo::view() and RegionInfo::viewOnly() are meant to be called in debugging sessions. They open a viewer to show how RegionInfo currently understands the region hierarchy. The functions viewRegion(Function*) and viewRegionOnly(Function*) invoke a fresh region analysis of the function in contrast to viewRegion(RegionInfo*) and viewRegionOnly(RegionInfo*) which show the current analysis result. Reviewers: grosser Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D11875 llvm-svn: 244444
* [RegionInfo] Use RegionInfo* instead of RegionInfoPass* as graph typeMichael Kruse2015-08-101-56/+62
| | | | | | | | | | | This allows printing region graphs when only the RegionInfo (e.g. Region::getRegionInfo()), but no RegionInfoPass object is available. Specifically, we will use this to print RegionInfo graphs in the debugger. Differential version: http://reviews.llvm.org/D11874 Reviewed-by: grosser llvm-svn: 244442
* [LAA] Remove unused pointer partition argument from needsChecking(), NFCAdam Nemet2015-08-091-10/+4
| | | | | | | This is no longer used in any of the callers. Also remove the logic of handling this argument. llvm-svn: 244421
* [LAA] Remove unused pointer partition argument from generateChecks, NFCAdam Nemet2015-08-091-3/+2
| | | | | | LoopDistribution does its own filtering now. llvm-svn: 244420
* [PHITransAddr] Don't assume that instruction operands are translatableDavid Majnemer2015-08-091-3/+4
| | | | | | | | | | | | | We can only PHI translate instructions. In our attempt to PHI translate a bitcast, we attempt to translate its operand; however, the operand might be an argument or a global instead of an instruction. Benignly bail out when this happens. This fixes PR24397. Differential Revision: http://reviews.llvm.org/D11879 llvm-svn: 244418
* Fix some comment typos.Benjamin Kramer2015-08-083-7/+7
| | | | llvm-svn: 244402
* [LAA] Remove unused pointer partition argument from getNumberOfChecks, NFCAdam Nemet2015-08-071-14/+1
| | | | | | | | | This is unused after filtering checks was moved to the clients. As a result, we can just return the number of the checks in the precomputed set. llvm-svn: 244369
* [LAA] Make the set of runtime checks part of the state of LAA, NFCAdam Nemet2015-08-071-3/+10
| | | | | | | | | | | | | | | | | | | | This is the full set of checks that clients can further filter. IOW, it's client-agnostic. This makes LAA complete in the sense that it now provides the two main results of its analysis precomputed: 1. memory dependences via getDepChecker().getInsterestingDependences() 2. run-time checks via getRuntimePointerCheck().getChecks() However, as a consequence we now compute this information pro-actively. Thus if the client decides to skip the loop based on the dependences we've computed the checks unnecessarily. In order to see whether this was a significant overhead I checked compile time on SPEC2k6 LTO bitcode files. The change was in the noise. The checks are generated in canCheckPtrAtRT, at the same place where we used to call groupChecks to merge checks. llvm-svn: 244368
* [LAA] Remove unused pointer partition argument from print(), NFCAdam Nemet2015-08-071-4/+2
| | | | | | | This is now handled in the client. No need for LAA to provide this variant. llvm-svn: 244349
* [IndVars] Fix PR24356.Sanjoy Das2015-08-061-36/+30
| | | | | | | Unsigned predicates increase or decrease agnostic of the signs of their increments. llvm-svn: 244265
* Convert a bunch of loops to foreach. NFC.Pete Cooper2015-08-061-2/+1
| | | | | | | | After r244074, we now have a successors() method to iterate over all the successors of a TerminatorInst. This commit changes a bunch of eligible loops to use it. llvm-svn: 244260
* Rename inst_range() to instructions() for consistency. NFCNico Rieck2015-08-064-7/+7
| | | | llvm-svn: 244248
* [Reassociation] Fix miscompile for va_arg arguments.Quentin Colombet2015-08-061-0/+4
| | | | | | | | | | | | | | | | iisUnmovableInstruction() had a list of instructions hardcoded which are considered unmovable. The list lacked (at least) an entry for the va_arg and cmpxchg instructions. Fix this by introducing a new Instruction::mayBeMemoryDependent() instead of maintaining another instruction list. Patch by Matthias Braun <matze@braunis.de>. Differential Revision: http://reviews.llvm.org/D11577 rdar://problem/22118647 llvm-svn: 244244
* [PM/AA] Clean up and homogenize comments throughout basic-aa.Chandler Carruth2015-08-061-52/+59
| | | | llvm-svn: 244200
* [PM/AA] Run clang-format over all of basic-aa before making moreChandler Carruth2015-08-061-59/+60
| | | | | | substantive edits. llvm-svn: 244198
* [PM/AA] Hoist the interface for BasicAA into a header file.Chandler Carruth2015-08-061-192/+10
| | | | | | | | | | | | | 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
* [PM/AA] Simplify the AliasAnalysis interface by removing a wrapperChandler Carruth2015-08-065-66/+63
| | | | | | | | | | | | | | | | around a DataLayout interface in favor of directly querying DataLayout. This wrapper specifically helped handle the case where this no DataLayout, but LLVM now requires it simplifynig all of this. I've updated callers to directly query DataLayout. This in turn exposed a bunch of places where we should have DataLayout readily available but don't which I've fixed. This then in turn exposed that we were passing DataLayout around in a bunch of arguments rather than making it readily available so I've also fixed that. No functionality changed. llvm-svn: 244189
* Add a stat to show how often the limit to decompose GEPs in BasicAA is reached.Wei Mi2015-08-051-0/+11
| | | | | | Differential Revision: http://reviews.llvm.org/D9689 llvm-svn: 244174
* [PM] Remove a failed attempt to port the CallGraph analysis to the newChandler Carruth2015-08-051-6/+0
| | | | | | | | | | | | | pass manager. This never worked, and won't ever work. It was actually why I ended up building the LazyCallGraph set of code which is more more effectively wired up to the new pass manager. This accidentally got committed when I was trying to land a cleanup of the code organization in the other parts of this file. =[ My bad, but fortunately Dave was keen eyed enough to spot that this code couldn't possibly work. =] llvm-svn: 244127
* -Wdeprecated cleanup: Make CallGraph movable by default by using unique_ptr ↵David Blaikie2015-08-051-13/+11
| | | | | | | | | | members rather than raw pointers. The only place that tries to return a CallGraph by value (CallGraphAnalysis::run) doesn't seem to be used right now, but it's a reasonable bit of cleanup anyway. llvm-svn: 244122
* [TTI] Make the cost APIs in TargetTransformInfo consistently use 'int'Chandler Carruth2015-08-051-70/+112
| | | | | | | | | | | | | | | | | | | | | | | | | | rather than 'unsigned' for their costs. For something like costs in particular there is a natural "negative" value, that of savings or saved cost. As a consequence, there is a lot of code that subtracts or creates negative values based on cost, all of which is prone to awkwardness or bugs when dealing with an unsigned type. Similarly, we *never* want these values to wrap, as that would cause Very Bad code generation (likely percieved as an infinite loop as we try to emit over 2^32 instructions or some such insanity). All around 'int' seems a much better fit for these basic metrics. I've added asserts to ensure that at least the TTI interface never returns negative numbers here. If we ever have a use case for negative numbers, we can remove this, but this way a bug where someone used '-1' to produce a 'very large' cost will be caught by the assert. This passes all tests, and is also UBSan clean. No functional change intended. Differential Revision: http://reviews.llvm.org/D11741 llvm-svn: 244080
* [GMR] Teach the conservative path of GMR to catch even more easy cases.Chandler Carruth2015-08-051-41/+111
| | | | | | | | | | | | | | In PR24288 it was pointed out that the easy case of a non-escaping global and something that *obviously* required an escape sometimes is hidden behind PHIs (or selects in theory). Because we have this binary test, we can easily just check that all possible input values satisfy the requirement. This is done with a (very small) recursion through PHIs and selects. With this, the specific example from the PR is correctly folded by GVN. Differential Revision: http://reviews.llvm.org/D11707 llvm-svn: 244078
* [AA] Use CallSite cast idiom. No functionality change.Benjamin Kramer2015-08-051-3/+2
| | | | llvm-svn: 244045
* [LAA] Remove unused pointer partition argument from addRuntimeCheck, NFCAdam Nemet2015-08-041-2/+2
| | | | | | | This variant of addRuntimeCheck is only used now from the LoopVectorizer which does not use this parameter. llvm-svn: 243955
* [LAA] Remove unused needsAnyChecking(), NFCAdam Nemet2015-08-031-11/+0
| | | | llvm-svn: 243921
* -Wdeprecated-clean: Fix cases of violating the rule of 5 in ways that are ↵David Blaikie2015-08-032-4/+2
| | | | | | | | | | | | | | | | | | | | | | deprecated in C++11 Various value handles needed to be copy constructible and copy assignable (mostly for their use in DenseMap). But to avoid an API that might allow accidental slicing, make these members protected in the base class and make derived classes final (the special members become implicitly public there - but disallowing further derived classes that might be sliced to the intermediate type). Might be worth having a warning a bit like -Wnon-virtual-dtor that catches public move/copy assign/ctors in classes with virtual functions. (suppressable in the same way - by making them protected in the base, and making the derived classes final) Could be fancier and only diagnose them when they're actually called, potentially. Also allow a few default implementations where custom implementations (especially with non-standard return types) were implemented. llvm-svn: 243909
* De-constify pointers to Type since they can't be modified. NFCCraig Topper2015-08-012-3/+3
| | | | | | This was already done in most places a while ago. This just fixes the ones that crept in over time. llvm-svn: 243842
* -Wdeprecated-clean: Fix cases of violating the rule of 5 in ways that are ↵David Blaikie2015-07-311-4/+3
| | | | | | deprecated in C++11 llvm-svn: 243788
* New EH representation for MSVC compatibilityDavid Majnemer2015-07-313-3/+23
| | | | | | | | | | 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. Differential Revision: http://reviews.llvm.org/D11097 llvm-svn: 243766
* [CaptureTracker] Provide an ordered basic block to PointerMayBeCapturedBeforeBruno Cardoso Lopes2015-07-315-72/+123
| | | | | | | | | | | | | | | | | | This patch is a follow up from r240560 and is a step further into mitigating the compile time performance issues in CaptureTracker. By providing the CaptureTracker with a "cached ordered basic block" instead of computing it every time, MemDepAnalysis can use this cache throughout its calls to AA->callCapturesBefore, avoiding to recompute it for every scanned instruction. In the same testcase used in r240560, compile time is reduced from 2min to 30s. This also fixes PR22348. rdar://problem/19230319 Differential Revision: http://reviews.llvm.org/D11364 llvm-svn: 243750
* Rename hasCompatibleFunctionAttributes->areInlineCompatible basedEric Christopher2015-07-292-4/+4
| | | | | | | on suggestions. Currently the function is only used for inline purposes and this is more descriptive for the use. llvm-svn: 243578
* [SCEV] Apply NSW and NUW flags via poison value analysisJingyue Wu2015-07-282-25/+268
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Make Scalar Evolution able to propagate NSW and NUW flags from instructions to SCEVs in some cases. This is based on reasoning about when poison from instructions with these flags would trigger undefined behavior. This gives a 13% speed-up on some Eigen3-based Google-internal microbenchmarks for NVPTX. There does not seem to be clear agreement about when poison should be considered to propagate through instructions. In this analysis, poison propagates only in cases where that should be uncontroversial. This change makes LSR able to create induction variables for expressions like &ptr[i + offset] for loops like this: for (int i = 0; i < limit; ++i) { sum += ptr[i + offset]; } Here ptr is a 64 bit pointer and offset is a 32 bit integer. For NVPTX, LSR currently creates an induction variable for i + offset instead, which is not as fast. Improving this situation is what brings the 13% speed-up on some Eigen3-based Google-internal microbenchmarks for NVPTX. There are more details in this discussion on llvmdev. June: http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-June/thread.html#87234 July: http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-July/thread.html#87392 Patch by Bjarke Roune Reviewers: eliben, atrick, sanjoy Subscribers: majnemer, hfinkel, jingyue, meheff, llvm-commits Differential Revision: http://reviews.llvm.org/D11212 llvm-svn: 243460
* [LVI] Cleanup whitespaces. NFCBruno Cardoso Lopes2015-07-281-61/+61
| | | | llvm-svn: 243430
* [LAA] Add clarifying comments for the checking pointer grouping algorithm. NFCSilviu Baranga2015-07-281-1/+24
| | | | llvm-svn: 243416
* [GMR] Teach GlobalsModRef to distinguish an important and safe case ofChandler Carruth2015-07-281-0/+46
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | no-alias with non-addr-taken globals: they cannot alias a captured pointer. If the non-global underlying object would have been a capture were it to alias the global, we can firmly conclude no-alias. It isn't reasonable for a transformation to introduce a capture in a way observable by an alias analysis. Consider, even if it were to temporarily capture one globals address into another global and then restore the other global afterward, there would be no way for the load in the alias query to observe that capture event correctly. If it observes it then the temporary capturing would have changed the meaning of the program, making it an invalid transformation. Even instrumentation passes or a pass which is synthesizing stores to global variables to expose race conditions in programs could not trigger this unless it queried the alias analysis infrastructure mid-transform, in which case it seems reasonable to return results from before the transform started. See the comments in the change for a more detailed outlining of the theory here. This should address the primary performance regression found when the non-conservatively-correct path of the alias query was disabled. Differential Revision: http://reviews.llvm.org/D11410 llvm-svn: 243405
* [GMR] Fix a long-standing bug in GlobalsModRef where it failed to clearChandler Carruth2015-07-281-4/+30
| | | | | | | | | | | | | | | | | | | | | | | | out the per-function modref data structures when functions were deleted or when globals were deleted. I don't actually know how the global deletion side of this bug hasn't been hit before, but for the other it just-so-happens that functions aren't likely to be deleted in the particular part of the LTO pipeline where we currently enable GMR, so we got lucky. With this patch, I can self-host with GMR enabled in the normal pass pipeline! I was a bit concerned about the compile-time impact of this chang, which is part of what motivated my prior string of patches to make the per-function datastructure very dense and fast to walk. With those changes in place, I can't measure a significant compile time difference (the difference is around 0.1% which is *way* below the noise) before and after this patch when building a linked bitcode for all of Clang. Differential Revision: http://reviews.llvm.org/D11453 llvm-svn: 243385
* [LAA] Split out a helper to print a collection of memchecksAdam Nemet2015-07-271-34/+27
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is effectively an NFC but we can no longer print the index of the pointer group so instead I print its address. This still lets us cross-check the section that list the checks against the section that list the groups (see how I modified the test). E.g. before we printed this: Run-time memory checks: Check 0: Comparing group 0: %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %store_ind %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc Against group 1: %arrayidxA = getelementptr i16, i16* %a, i64 %ind %arrayidxA1 = getelementptr i16, i16* %a, i64 %add ... Grouped accesses: Group 0: (Low: %c High: (78 + %c)) Member: {%c,+,4}<%for.body> Member: {(2 + %c),+,4}<%for.body> Now we print this (changes are underlined): Run-time memory checks: Check 0: Comparing group (0x7f9c6040c320): ~~~~~~~~~~~~~~ %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %store_ind Against group (0x7f9c6040c358): ~~~~~~~~~~~~~~ %arrayidxA1 = getelementptr i16, i16* %a, i64 %add %arrayidxA = getelementptr i16, i16* %a, i64 %ind ... Grouped accesses: Group 0x7f9c6040c320: ~~~~~~~~~~~~~~ (Low: %c High: (78 + %c)) Member: {(2 + %c),+,4}<%for.body> Member: {%c,+,4}<%for.body> llvm-svn: 243354
* [TargetTransformInfo][NFCI] Add TargetTransformInfo::isZExtFree.Sanjoy Das2015-07-271-0/+4
| | | | | | | | | | | | | | Summary: This function is not used in this change but will be used in a subsequent change. Reviewers: mcrosier, chandlerc Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9180 llvm-svn: 243347
* [IndVars] Make loop varying predicates loop invariant.Sanjoy Das2015-07-271-0/+133
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Was D9784: "Remove loop variant range check when induction variable is strictly increasing" This change re-implements D9784 with the two differences: 1. It does not use SCEVExpander and does not generate new instructions. Instead, it does a quick local search for existing `llvm::Value`s that it needs when modifying the `icmp` instruction. 2. It is more general -- it deals with both increasing and decreasing induction variables. I've added all of the tests included with D9784, and two more. As an example on what this change does (copied from D9784): Given C code: ``` for (int i = M; i < N; i++) // i is known not to overflow if (i < 0) break; a[i] = 0; } ``` This transformation produces: ``` for (int i = M; i < N; i++) if (M < 0) break; a[i] = 0; } ``` Which can be unswitched into: ``` if (!(M < 0)) for (int i = M; i < N; i++) a[i] = 0; } ``` I went back and forth on whether the top level logic should live in `SimplifyIndvar::eliminateIVComparison` or be put into its own routine. Right now I've put it under `eliminateIVComparison` because even though the `icmp` is not *eliminated*, it no longer is an IV comparison. I'm open to putting it in its own helper routine if you think that is better. Reviewers: reames, nicholas, atrick Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D11278 llvm-svn: 243331
* [LAA] Upper-case variable names, NFCAdam Nemet2015-07-271-4/+4
| | | | llvm-svn: 243313
* [LAA] Split out a helper from addRuntimeCheck to generate the check, NFCAdam Nemet2015-07-271-14/+18
| | | | llvm-svn: 243312
* Fix assert when inlining a constantexpr addrspacecastMatt Arsenault2015-07-271-2/+1
| | | | | | | | | | | | The pointer size of the addrspacecasted pointer might not have matched, so this would have hit an assert in accumulateConstantOffset. I think this was here to allow constant folding of a load of an addrspacecasted constant. Accumulating the offset through the addrspacecast doesn't make much sense, so something else is necessary to allow folding the load through this cast. llvm-svn: 243300
* LoopAccessAnalysis.cpp: Tweak r243239 to avoid side effects. It caused ↵NAKAMURA Takumi2015-07-271-3/+4
| | | | | | different emissions between gcc and clang. llvm-svn: 243258
* Roll forward r243250Jingyue Wu2015-07-261-4/+2
| | | | | | | | | r243250 appeared to break clang/test/Analysis/dead-store.c on one of the build slaves, but I couldn't reproduce this failure locally. Probably a false positive as I saw this test was broken by r243246 or r243247 too but passed later without people fixing anything. llvm-svn: 243253
OpenPOWER on IntegriCloud