summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* [Dominators] Remove verifyDomTree and add some verifying for Post Dom TreesDavid Green2018-02-281-0/+13
| | | | | | | | | | | | Removes verifyDomTree, using assert(verify()) everywhere instead, and changes verify a little to always run IsSameAsFreshTree first in order to print good output when we find errors. Also adds verifyAnalysis for PostDomTrees, which will allow checking of PostDomTrees it the same way we check DomTrees and MachineDomTrees. Differential Revision: https://reviews.llvm.org/D41298 llvm-svn: 326315
* [ValueTracking] Teach cannotBeOrderedLessThanZeroImpl to look through ↵Craig Topper2018-02-271-0/+6
| | | | | | | | | | ExtractElement. This is similar to what's done in computeKnownBits and computeSignBits. Don't do anything fancy just collect information valid for any element. Differential Revision: https://reviews.llvm.org/D43789 llvm-svn: 326237
* [MemorySSA] Call the correct dtorsGeorge Burgess IV2018-02-271-3/+2
| | | | | | | | | | | | It appears that there were many cases where we were directly (through templates) calling the dtor of MemoryAccess, which is conceptually an abstract class. This hasn't been a problem, since the data members of all of the subclasses of MemoryAccess have been POD. I'm planning on changing that. :) llvm-svn: 326175
* [SCEV] Cleanup SCEVInitRewriter. NFC.Serguei Katkov2018-02-271-2/+2
| | | | | | | | | | Set default value for IgnoreOtherLoops of SCEVInitRewriter::rewrite to true to be consistent with SCEVPostIncRewriter which does not have this parameter but behaves as it would be true. This is follow up for rL326067. llvm-svn: 326174
* Fix PR36032, PR35432Evgeny Stupachenko2018-02-271-0/+6
| | | | | | | | | | | | | | | Summary: The change fix an assert fail at ScalarEvolutionExpander.cpp: assert(ExitCount != SE.getCouldNotCompute() && "Invalid loop count"); Reviewers: sbaranga Differential Revision: http://reviews.llvm.org/D42604 From: Evgeny Stupachenko <evstupac@gmail.com> <evgeny.v.stupachenko@intel.com> llvm-svn: 326154
* [ValueTracking] Teach cannotBeOrderedLessThanZeroImpl to handle vector ↵Craig Topper2018-02-261-0/+18
| | | | | | | | | | | | | | | | constants. Summary: This allows vector fabs to be removed in more cases. Reviewers: spatel, arsenm, RKSimon Reviewed By: spatel Subscribers: wdng, llvm-commits Differential Revision: https://reviews.llvm.org/D43739 llvm-svn: 326138
* [SCEV] Factor out getUsedLoopsSerguei Katkov2018-02-261-4/+12
| | | | | | | | | | | | | | | The patch introduces the new function in ScalarEvolution to get all loops used in specified SCEV. This is a preparation for re-writing isKnownPredicate utility as described in https://reviews.llvm.org/D42417. Reviewers: sanjoy, mkazantsev, reames Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D43504 llvm-svn: 326072
* [SCEV] Introduce SCEVPostIncRewriterSerguei Katkov2018-02-261-0/+41
| | | | | | | | | | | | | | | | The patch introduces the SCEVPostIncRewriter rewriter which is similar to SCEVInitRewriter but rewrites AddRec with post increment value of this AddRec. This is a preparation for re-writing isKnownPredicate utility as described in https://reviews.llvm.org/D42417. Reviewers: sanjoy, mkazantsev, reames Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D43499 llvm-svn: 326071
* [SCEV] Extends the SCEVInitRewriterSerguei Katkov2018-02-261-8/+20
| | | | | | | | | | | | | | | | | The patch introduces an additional parameter IgnoreOtherLoops to SCEVInitRewriter. if it is equal to true then rewriter will not invalidate result in case SCEV depends on other loops then specified during creation. The patch does not change the default behavior. This is a preparation for re-writing isKnownPredicate utility as described in https://reviews.llvm.org/D42417. Reviewers: sanjoy, mkazantsev, reames Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D43498 llvm-svn: 326067
* [MemorySSA] Remove a redundant dyn_cast.George Burgess IV2018-02-241-3/+2
| | | | | | StartingAccess is a MemoryUseOrDef. No need to check again. llvm-svn: 326000
* [MemorySSA] Fix a cache invalidation bug with removed accessesGeorge Burgess IV2018-02-231-1/+1
| | | | | | | I suspect there's a deeper issue here, but we probably shouldn't be using INVALID_MEMORYSSA_ID as liveOnEntry's ID anyway. llvm-svn: 325971
* [InstSimplify] sqrt(X) * sqrt(X) --> XSanjay Patel2018-02-231-0/+6
| | | | | | This was misplaced in InstCombine. We can loosen the FMF as a follow-up step. llvm-svn: 325965
* [BPI] Detect branches in loops that make themselves not takenJohn Brawn2018-02-231-14/+135
| | | | | | | | | | | | | | | | | | | | | | If we have a loop like this: int n = 0; while (...) { if (++n >= MAX) { n = 0; } } then the body of the 'if' statement will only be executed once every MAX iterations. Detect this by looking for branches in loops where taking the branch makes the branch condition evaluate to 'not taken' in the next iteration of the loop, and reduce the probability of such branches. This slightly improves EEMBC benchmarks on cortex-m4/cortex-m33 due to making better choices in if-conversion, but has no effect on any other cpu/benchmark that I could detect. Differential Revision: https://reviews.llvm.org/D35804 llvm-svn: 325925
* [ThinLTO] Represent relative BF using a scaled representation .Easwaran Raman2018-02-221-11/+3
| | | | | | | | | | | | | | | Summary: The current integer representation of relative block frequency prevents representing relative block frequencies below 1. This change uses a 8 of the 29 bits to represent the decimal part by using a fixed scale of -8. Reviewers: tejohnson, davidxl Subscribers: mehdi_amini, inglorion, llvm-commits Differential Revision: https://reviews.llvm.org/D43520 llvm-svn: 325823
* [SCEV][NFC] Factor out common logic into a separate methodMax Kazantsev2018-02-221-13/+14
| | | | | | | | | | | | SCEV has multiple occurences of code when we need to prove some predicate on every iteration of a loop and do it with invocations of couple `isLoopEntryGuardedByCond`, `isLoopBackedgeGuardedByCond`. This patch factors out these two calls into a separate method. It is a preparation step to extend this logic: it is not the only way how we can prove such conditions. Differential Revision: https://reviews.llvm.org/D43373 llvm-svn: 325745
* [SCEV] Temporarily disable loop versioning for the purposeSilviu Baranga2018-02-211-0/+7
| | | | | | | | | | of turning SCEVUnknowns of PHIs into AddRecExprs. This feature is now hidden behind the -scev-version-unknown flag. Fixes PR36032 and PR35432. llvm-svn: 325687
* [MemoryBuiltins] Check nobuiltin status when identifying calls to free.Benjamin Kramer2018-02-201-10/+8
| | | | | | | | This is usually not a problem because this code's main purpose is eliminating unused new/delete pairs. We got deletes of nullptr or nobuiltin deletes of builtin new wrong though. llvm-svn: 325630
* [PatternMatch, InstSimplify] enhance m_AllOnes() to ignore undef elements in ↵Sanjay Patel2018-02-181-11/+7
| | | | | | | | | | | | | | | | | | | vectors Loosening the matcher definition reveals a subtle bug in InstSimplify (we should not assume that because an operand constant matches that it's safe to return it as a result). So I'm making that change here too (that diff could be independent, but I'm not sure how to reveal it before the matcher change). This also seems like a good reason to *not* include matchers that capture the value. We don't want to encourage the potential misstep of propagating undef values when it's not allowed/intended. I didn't include the capture variant option here or in the related rL325437 (m_One), but it already exists for other constant matchers. llvm-svn: 325466
* [InstSimplify] move select undef cond fold with other constant cond folds; NFCISanjay Patel2018-02-171-20/+21
| | | | llvm-svn: 325434
* [JumpThreading] PR36133 enable/disable DominatorTree for LVI analysisBrian M. Rzycki2018-02-161-1/+29
| | | | | | | | | | | | | | | | | | | | | | Summary: The LazyValueInfo pass caches a copy of the DominatorTree when available. Whenever there are pending DominatorTree updates within JumpThreading's DeferredDominance object we cannot use the cached DT for LVI analysis. This commit adds the new methods enableDT() and disableDT() to LVI. JumpThreading also sets the appropriate usage model before calling LVI analysis methods. Fixes https://bugs.llvm.org/show_bug.cgi?id=36133 Reviewers: sebpop, dberlin, kuhar Reviewed by: sebpop, kuhar Subscribers: uabelho, llvm-commits, aprantl, hiraditya, a.elovikov Differential Revision: https://reviews.llvm.org/D42717 llvm-svn: 325356
* [NFC] Rename isKnownViaSimpleReasoning to isKnownViaNonRecursiveReasoningMax Kazantsev2018-02-151-15/+15
| | | | llvm-svn: 325216
* [SCEV] Favor isKnownViaSimpleReasoning over constant ranges checkMax Kazantsev2018-02-151-6/+6
| | | | | | | | | | | | | | | | | | | | | There is a more powerful but still simple function `isKnownViaSimpleReasoning ` that does constant range check and few more additional checks. We use it some places (e.g. when proving implications) and in some other places we only check constant ranges. Currently, indvar simplifier fails to remove the check in following loop: int inc = ...; for (int i = inc, j = inc - 1; i < 200; ++i, ++j) if (i > j) { ... } This patch replaces all usages of `isKnownPredicateViaConstantRanges` with `isKnownViaSimpleReasoning` to have smarter proofs. In particular, it fixes the case above. Reviewed-By: sanjoy Differential Revision: https://reviews.llvm.org/D43175 llvm-svn: 325214
* Adding a width of the GEP index to the Data Layout.Elena Demikhovsky2018-02-147-39/+52
| | | | | | | | | | | | | | | | | | Making a width of GEP Index, which is used for address calculation, to be one of the pointer properties in the Data Layout. p[address space]:size:memory_size:alignment:pref_alignment:index_size_in_bits. The index size parameter is optional, if not specified, it is equal to the pointer size. Till now, the InstCombiner normalized GEPs and extended the Index operand to the pointer width. It works fine if you can convert pointer to integer for address calculation and all registered targets do this. But some ISAs have very restricted instruction set for the pointer calculation. During discussions were desided to retrieve information for GEP index from the Data Layout. http://lists.llvm.org/pipermail/llvm-dev/2018-January/120416.html I added an interface to the Data Layout and I changed the InstCombiner and some other passes to take the Index width into account. This change does not affect any in-tree target. I added tests to cover data layouts with explicitly specified index size. Differential Revision: https://reviews.llvm.org/D42123 llvm-svn: 325102
* [InstSimplify] allow exp/log simplifications with only 'reassoc' FMFSanjay Patel2018-02-121-4/+4
| | | | | | | | | | These intrinsic folds were added with D41381, but only allowed with isFast(). That's more than necessary because FMF has 'reassoc' to apply to these kinds of folds after D39304, and that's all we need in these cases. Differential Revision: https://reviews.llvm.org/D43160 llvm-svn: 324967
* [SCEV] Make getPostIncExpr guaranteed to return AddRecMax Kazantsev2018-02-121-0/+25
| | | | | | | | | | | | | The current implementation of `getPostIncExpr` invokes `getAddExpr` for two recurrencies and expects that it always returns it a recurrency. But this is not guaranteed to happen if we have reached max recursion depth or refused to make SCEV simplification for other reasons. This patch changes its implementation so that now it always returns SCEVAddRec without relying on `getAddExpr`. Differential Revision: https://reviews.llvm.org/D42953 llvm-svn: 324866
* [ValueTracking] don't crash when assumptions conflict (PR36270)Sanjay Patel2018-02-081-0/+8
| | | | | | | | | | | | | | The last assume in the test says that %B12 is 0. The first assume says that %and1 is less than %B12. Therefore, %and1 is unsigned less than 0...does not compute. That means this line: Known.Zero.setHighBits(RHSKnown.countMinLeadingZeros() + 1); ...tries to set more bits than exist. Differential Revision: https://reviews.llvm.org/D43052 llvm-svn: 324610
* Re-enable "[SCEV] Make isLoopEntryGuardedByCond a bit smarter"Max Kazantsev2018-02-071-5/+57
| | | | | | | | | The failures happened because of assert which was overconfident about SCEV's proving capabilities and is generally not valid. Differential Revision: https://reviews.llvm.org/D42835 llvm-svn: 324473
* Revert [SCEV] Make isLoopEntryGuardedByCond a bit smarterSerguei Katkov2018-02-071-57/+5
| | | | | | | | Revert rL324453 commit which causes buildbot failures. Differential Revision: https://reviews.llvm.org/D42835 llvm-svn: 324462
* [SCEV] Make isLoopEntryGuardedByCond a bit smarterMax Kazantsev2018-02-071-5/+57
| | | | | | | | | | | Sometimes `isLoopEntryGuardedByCond` cannot prove predicate `a > b` directly. But it is a common situation when `a >= b` is known from ranges and `a != b` is known from a dominating condition. Thia patch teaches SCEV to sum these facts together and prove strict comparison via non-strict one. Differential Revision: https://reviews.llvm.org/D42835 llvm-svn: 324453
* Follow-up for r324429: "[LCSSAVerification] Run verification only when ↵Michael Zolotukhin2018-02-071-1/+5
| | | | | | | | | | | | | asserts are enabled." Before r324429 we essentially didn't have a verification of LCSSA, so no wonder that it has been broken: currently loop-sink breaks it (the attached test illustrates the failure). It was detected during a stage2 RA build, so to unbreak it I'm disabling the check for now. llvm-svn: 324445
* [LCSSAVerification] Run verification only when asserts are enabled.Michael Zolotukhin2018-02-071-1/+3
| | | | llvm-svn: 324429
* [InstCombine][ValueTracking] Match non-uniform constant power-of-two vectorsSimon Pilgrim2018-02-061-8/+5
| | | | | | | | Generalize existing constant matching to work with non-uniform constant vectors as well. Differential Revision: https://reviews.llvm.org/D42818 llvm-svn: 324369
* [LoopStrengthReduce, x86] don't add cost for a cmp that will be macro-fused ↵Sanjay Patel2018-02-051-0/+4
| | | | | | | | | | | | | | | (PR35681) In the motivating case from PR35681 and represented by the macro-fuse-cmp test: https://bugs.llvm.org/show_bug.cgi?id=35681 ...there's a 37 -> 31 byte size win for the loop because we eliminate the big base address offsets. SPEC2017 on Ryzen shows no significant perf difference. Differential Revision: https://reviews.llvm.org/D42607 llvm-svn: 324289
* Re-apply [SCEV] Fix isLoopEntryGuardedByCond usageSerguei Katkov2018-02-051-3/+12
| | | | | | | | | | | | | | | | | ScalarEvolution::isKnownPredicate invokes isLoopEntryGuardedByCond without check that SCEV is available at entry point of the loop. It is incorrect and fixed by patch. To bugs additionally fixed: assert is moved after the check whether loop is not a nullptr. Usage of isLoopEntryGuardedByCond in ScalarEvolution::isImpliedCondOperandsViaNoOverflow is guarded by isAvailableAtLoopEntry. Reviewers: sanjoy, mkazantsev, anna, dorit, reames Reviewed By: mkazantsev Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D42417 llvm-svn: 324204
* [Analysis] Support aggregate access types in TBAAIvan A. Kosarev2018-02-021-96/+217
| | | | | | | | | This patch implements analysis for new-format TBAA access tags with aggregate types as their final access types. Differential Revision: https://reviews.llvm.org/D41501 llvm-svn: 324092
* Remove CallGraphTraits and use equivalent methods in GraphTraitsEaswaran Raman2018-02-011-2/+2
| | | | | | | | | | | | | | | | Summary: D42698 adds child_edge_{begin|end} and children_edges to GraphTraits which are used here. The reason for this change is to make it easy to use count propagation on ModulesummaryIndex. As it stands, CallGraphTraits is in Analysis while ModuleSummaryIndex is in IR. Reviewers: davidxl, dberlin Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D42703 llvm-svn: 323994
* [Analysis] Disable calls to *_finite and other glibc-only functions on Android.Chih-Hung Hsieh2018-01-311-12/+6
| | | | | | | | | | Since r322087, glibc's finite lib calls are generated when possible. However, they are not supported on Android. This change also disables other functions not available on Android. Differential Revision: http://reviews.llvm.org/D42668 llvm-svn: 323898
* [Lint] Upgrade uses of MemoryIntrinic::getAlignment() to new API. (NFCI)Daniel Neilson2018-01-311-5/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This change is part of step five in the series of changes to remove alignment argument from memcpy/memmove/memset in favour of alignment attributes. In particular, this changes the Lint analysis to cease using the old getAlignment() API of MemoryIntrinsic in favour of getting source & dest specific alignments through the new API. Steps: Step 1) Remove alignment parameter and create alignment parameter attributes for memcpy/memmove/memset. ( rL322965, rC322964, rL322963 ) Step 2) Expand the IRBuilder API to allow creation of memcpy/memmove with differing source and dest alignments. ( rL323597 ) Step 3) Update Clang to use the new IRBuilder API. ( rC323617 ) Step 4) Update Polly to use the new IRBuilder API. ( rL323618 ) Step 5) Update LLVM passes that create memcpy/memmove calls to use the new IRBuilder API, and those that use use MemIntrinsicInst::[get|set]Alignment() to use [get|set]DestAlignment() and [get|set]SourceAlignment() instead. Step 6) Remove the single-alignment IRBuilder API for memcpy/memmove, and the MemIntrinsicInst::[get|set]Alignment() methods. Reference http://lists.llvm.org/pipermail/llvm-dev/2015-August/089384.html http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20151109/312083.html llvm-svn: 323886
* Re-commit : [PowerPC] Add handling for ColdCC calling convention and a pass ↵Zaara Syeda2018-01-301-0/+4
| | | | | | | | | | | | | | | | | | | | | to mark candidates with coldcc attribute. This recommits r322721 reverted due to sanitizer memory leak build bot failures. Original commit message: This patch adds support for the coldcc calling convention for Power. This changes the set of non-volatile registers. It includes a pass to stress test the implementation by marking all static directly called functions with the coldcc attribute through the option -enable-coldcc-stress-test. It also includes an option, -ppc-enable-coldcc, to add the coldcc attribute to functions which are cold at all call sites based on BlockFrequencyInfo when the containing function does not call any non cold functions. Differential Revision: https://reviews.llvm.org/D38413 llvm-svn: 323778
* [InstSimplify] (X * Y) / Y --> X for relaxed floating-point opsSanjay Patel2018-01-301-0/+6
| | | | | | | | | This is the FP counterpart that was mentioned in PR35709: https://bugs.llvm.org/show_bug.cgi?id=35709 Differential Revision: https://reviews.llvm.org/D42385 llvm-svn: 323716
* [InlineCost] Mark functions accessing varargs as not viable.Florian Hahn2018-01-281-6/+12
| | | | | | | | | | | | | This prevents functions accessing varargs from being inlined if they have the alwaysinline attribute. Reviewers: efriedma, rnk, davide Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D42556 llvm-svn: 323619
* [SyntheticCounts] Rewrite the code using only graph traits.Easwaran Raman2018-01-251-74/+65
| | | | | | | | | | | | | | | | | | | Summary: The intent of this is to allow the code to be used with ThinLTO. In Thinlink phase, a traditional Callgraph can not be computed even though all the necessary information (nodes and edges of a call graph) is available. This is due to the fact that CallGraph class is closely tied to the IR. This patch first extends GraphTraits to add a CallGraphTraits graph. This is then used to implement a version of counts propagation on a generic callgraph. Reviewers: davidxl Subscribers: mehdi_amini, tejohnson, llvm-commits Differential Revision: https://reviews.llvm.org/D42311 llvm-svn: 323475
* Re-land "[ThinLTO] Add call edges' relative block frequency to per-module ↵Easwaran Raman2018-01-251-3/+18
| | | | | | | | | | | | | | summary." It was reverted after buildbot regressions. Original commit message: This allows relative block frequency of call edges to be passed to the thinlink stage where it will be used to compute synthetic entry counts of functions. llvm-svn: 323460
* Revert "[ThinLTO] Add call edges' relative block frequency to per-module ↵Easwaran Raman2018-01-241-18/+3
| | | | | | | | summary." Causes buildbot regressions. llvm-svn: 323358
* [ThinLTO] Add call edges' relative block frequency to per-module summary.Easwaran Raman2018-01-241-3/+18
| | | | | | | | | | | | | | | Summary: This allows relative block frequency of call edges to be passed to the thinlink stage where it will be used to compute synthetic entry counts of functions. Reviewers: tejohnson, pcc Subscribers: mehdi_amini, llvm-commits, inglorion Differential Revision: https://reviews.llvm.org/D42212 llvm-svn: 323349
* InstSimplify: If divisor element is undef simplify to undefZvi Rackover2018-01-241-2/+3
| | | | | | | | | | | | | | | | Summary: If any vector divisor element is undef, we can arbitrarily choose it be zero which would make the div/rem an undef value by definition. Reviewers: spatel, reames Reviewed By: spatel Subscribers: magabari, llvm-commits Differential Revision: https://reviews.llvm.org/D42485 llvm-svn: 323343
* [ValueTracking] add recursion depth param to matchSelectPattern Sanjay Patel2018-01-241-11/+18
| | | | | | | | | | | | | | | | | | | | | | | We're getting bug reports: https://bugs.llvm.org/show_bug.cgi?id=35807 https://bugs.llvm.org/show_bug.cgi?id=35840 https://bugs.llvm.org/show_bug.cgi?id=36045 ...where we blow up the stack in value tracking because other passes are sending in selects that have an operand that is itself the select. We don't currently have a reliable way to avoid analyzing dead code that may take non-standard forms, so bail out when things go too far. This mimics the recursion depth limitations in other parts of value tracking. Unfortunately, this pushes the underlying problems for other passes (jump-threading, simplifycfg, correlated-propagation) into hiding. If someone wants to uncover those again, the first draft of this patch on Phab would do that (it would assert rather than bail out). Differential Revision: https://reviews.llvm.org/D42442 llvm-svn: 323331
* Fix typos of occurred and occurrenceMalcolm Parsons2018-01-241-1/+1
| | | | llvm-svn: 323318
* [Analysis] Disable exp/exp2/pow finite lib calls on Android with -ffast-math.MinSeong Kim2018-01-231-0/+9
| | | | | | | | | | | | | | | | | | | Summary: Since r322087, glibc's finite lib calls are generated when possible. However, glibc is not supported on Android. Therefore this change enables llvm to finely distinguish between linux and Android for unsupported library calls. The change also include some regression tests. Reviewers: srhines, pirama Reviewed By: srhines Subscribers: kongyi, chh, javed.absar, llvm-commits Differential Revision: https://reviews.llvm.org/D42288 llvm-svn: 323187
* [InstSimplify] (X << Y) % X -> 0Anton Bikineev2018-01-231-0/+7
| | | | llvm-svn: 323182
OpenPOWER on IntegriCloud