summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* [InstSimplify] fold minnum/maxnum with NaN argSanjay Patel2018-07-151-0/+8
| | | | | | | | | | | | | | | This fold is repeated/misplaced in instcombine, but I'm not sure if it's safe to remove that yet because some other folds appear to be asserting that the transform has occurred within instcombine itself. This isn't the best fix for PR37776, but it probably hides the bug with the given code example: https://bugs.llvm.org/show_bug.cgi?id=37776 We have another test to demonstrate the more general bug. llvm-svn: 337127
* Re-apply "[SCEV] Strengthen StrengthenNoWrapFlags (reapply r334428)."Tim Shen2018-07-131-7/+20
| | | | llvm-svn: 337075
* Revert "CallGraphSCCPass: iterate over all functions."Evgeniy Stepanov2018-07-131-71/+39
| | | | | | | | | | | | This reverts commit r336419: use-after-free on CallGraph::FunctionMap elements due to the use of a stale iterator in CGPassManager::runOnModule. The iterator may be invalidated if a pass removes a function, ex.: llvm::LegacyInlinerBase::inlineCalls inlineCallsImpl llvm::CallGraph::removeFunctionFromModule llvm-svn: 337018
* DivergenceAnalysis: added debug outputTim Renouf2018-07-131-5/+16
| | | | | | | | | | | | | | | | | | Summary: This commit does two things: 1. modified the existing DivergenceAnalysis::dump() so it dumps the whole function with added DIVERGENT: annotations; 2. added code to do that dump if the appropriate -debug-only option is on. Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D47700 Change-Id: Id97b605aab1fc6f5a11a20c58a99bbe8c565bf83 llvm-svn: 336998
* [InstCombine] Simplify isKnownNegationFangrui Song2018-07-121-5/+2
| | | | llvm-svn: 336957
* Remove redundant *_or_null checks; NFCGeorge Burgess IV2018-07-121-2/+2
| | | | | | | For the first one, we dereference `NewDef` right before the `if` anyway. For the second, we shouldn't have NULL users(). llvm-svn: 336952
* [InstSimplify] simplify add instruction if two operands are negativeChen Zheng2018-07-122-0/+24
| | | | | | Differential Revision: https://reviews.llvm.org/D49216 llvm-svn: 336881
* [MemorySSA] Add APIs to move memory accesses between blocks, following CFG ↵Alina Sbirlea2018-07-112-1/+61
| | | | | | | | | | | | | | | | changes. Summary: The move APIs added in this patch will be used to update MemorySSA when CFG changes merge or split blocks, by moving memory accesses accordingly in MemorySSA's internal data structures. [Split from D45299 for easier review] Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D48897 llvm-svn: 336860
* [TargetTransformInfo] Add pow2 analysis for scalar constantsSimon Pilgrim2018-07-111-0/+6
| | | | | | Add ConstantInt analysis to getOperandInfo so we get more realistic div/rem expansion costs comparable to the vector costs. llvm-svn: 336827
* llvm: Add support for "-fno-delete-null-pointer-checks"Manoj Gupta2018-07-097-40/+73
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Support for this option is needed for building Linux kernel. This is a very frequently requested feature by kernel developers. More details : https://lkml.org/lkml/2018/4/4/601 GCC option description for -fdelete-null-pointer-checks: This Assume that programs cannot safely dereference null pointers, and that no code or data element resides at address zero. -fno-delete-null-pointer-checks is the inverse of this implying that null pointer dereferencing is not undefined. This feature is implemented in LLVM IR in this CL as the function attribute "null-pointer-is-valid"="true" in IR (Under review at D47894). The CL updates several passes that assumed null pointer dereferencing is undefined to not optimize when the "null-pointer-is-valid"="true" attribute is present. Reviewers: t.p.northover, efriedma, jyknight, chandlerc, rnk, srhines, void, george.burgess.iv Reviewed By: efriedma, george.burgess.iv Subscribers: eraman, haicheng, george.burgess.iv, drinkcat, theraven, reames, sanjoy, xbolva00, llvm-commits Differential Revision: https://reviews.llvm.org/D47895 llvm-svn: 336613
* Make llvm.objectsize more conservative with nullGeorge Burgess IV2018-07-091-1/+8
| | | | | | | | | | In non-zero address spaces, we were reporting that an object at `null` always occupies zero bytes. This is incorrect in many cases, so just return `unknown` in those cases for now. Differential Revision: https://reviews.llvm.org/D48860 llvm-svn: 336611
* [LoopInfo] Port loop exit interfaces from Loop to LoopBaseDiego Caballero2018-07-091-63/+0
| | | | | | | | | | | | | | This patch ports hasDedicatedExits, getUniqueExitBlocks and getUniqueExitBlock in Loop to LoopBase so that they can be used from other LoopBase sub-classes. Reviewers: chandlerc, sanjoy, hfinkel, fhahn Reviewed By: chandlerc Differential Revision: https://reviews.llvm.org/D48817 llvm-svn: 336572
* Revert "[SCEV] Strengthen StrengthenNoWrapFlags (reapply r334428)."Tim Shen2018-07-061-20/+7
| | | | | | This reverts commit r336140. Our tests shows that LSR assert fails with it. llvm-svn: 336473
* Use Type::isIntOrPtrTy where possible, NFCVedant Kumar2018-07-062-20/+11
| | | | | | | | | | | It's a bit neater to write T.isIntOrPtrTy() over `T.isIntegerTy() || T.isPointerTy()`. I used Python's re.sub with this regex to update users: r'([\w.\->()]+)isIntegerTy\(\)\s*\|\|\s*\1isPointerTy\(\)' llvm-svn: 336462
* CallGraphSCCPass: iterate over all functions.Tim Northover2018-07-061-39/+71
| | | | | | | | | | | | | | | Previously we only iterated over functions reachable from the set of external functions in the module. But since some of the passes under this (notably the always-inliner and coroutine lowerer) are required for correctness, they need to run over everything. This just adds an extra layer of iteration over the CallGraph to keep track of which functions we've already visited and get the next batch of SCCs. Should fix PR38029. llvm-svn: 336419
* [SCEV] Strengthen StrengthenNoWrapFlags (reapply r334428).Tim Shen2018-07-021-7/+20
| | | | | | | | | | | | | | | | Summary: Comment on Transforms/LoopVersioning/incorrect-phi.ll: With the change SCEV is able to prove that the loop doesn't wrap-self (due to zext i16 to i64), disabling the entire loop versioning pass. Removed the zext and just use i64. Reviewers: sanjoy Subscribers: jlebar, hiraditya, javed.absar, bixia, llvm-commits Differential Revision: https://reviews.llvm.org/D48409 llvm-svn: 336140
* [ValueTracking] allow undef elements when matching vector absSanjay Patel2018-07-021-32/+27
| | | | llvm-svn: 336111
* Implement strip.invariant.groupPiotr Padlewski2018-07-023-19/+27
| | | | | | | | | | | | | | | | Summary: This patch introduce new intrinsic - strip.invariant.group that was described in the RFC: Devirtualization v2 Reviewers: rsmith, hfinkel, nlopes, sanjoy, amharc, kuhar Subscribers: arsenm, nhaehnle, JDevlieghere, hiraditya, xbolva00, llvm-commits Differential Revision: https://reviews.llvm.org/D47103 Co-authored-by: Krzysztof Pszeniczny <krzysztof.pszeniczny@gmail.com> llvm-svn: 336073
* [MemorySSA] Add APIs to MemoryPhis to delete incoming blocks/values, and an ↵Alina Sbirlea2018-06-292-3/+39
| | | | | | | | | | | | | | | | updater API to remove blocks. Summary: MemoryPhis now have APIs analogous to BB Phis to remove an incoming value/block. The MemorySSAUpdater uses the above APIs when updating MemorySSA given a set of dead blocks about to be deleted. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D48396 llvm-svn: 336015
* Revert "Extend CFGPrinter and CallPrinter with Heat Colors"Sean Fertile2018-06-296-639/+86
| | | | | | This reverts r335996 which broke graph printing in Polly. llvm-svn: 336000
* Extend CFGPrinter and CallPrinter with Heat ColorsSean Fertile2018-06-296-86/+639
| | | | | | | | | | | | | | | Extends the CFGPrinter and CallPrinter with heat colors based on heuristics or profiling information. The colors are enabled by default and can be toggled on/off for CFGPrinter by using the option -cfg-heat-colors for both -dot-cfg[-only] and -view-cfg[-only]. Similarly, the colors can be toggled on/off for CallPrinter by using the option -callgraph-heat-colors for both -dot-callgraph and -view-callgraph. Patch by Rodrigo Caetano Rocha! Differential Revision: https://reviews.llvm.org/D40425 llvm-svn: 335996
* Fix overconfident assert in ScalarEvolution::isImpliedViaMergeRoman Shirokiy2018-06-291-2/+3
| | | | | | | | | We can have AddRec with loops having many predecessors. This changes an assert to an early return. Differential Revision: https://reviews.llvm.org/D48766 llvm-svn: 335965
* SCEVExpander::expandAddRecExprLiterally(): check before casting as InstructionRoman Lebedev2018-06-291-1/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: An alternative to D48597. Fixes [[ https://bugs.llvm.org/show_bug.cgi?id=37936 | PR37936 ]]. The problem is as follows: 1. `indvars` marks `%dec` as `NUW`. 2. `loop-instsimplify` runs `instsimplify`, which constant-folds `%dec` to -1 (D47908) 3. `loop-reduce` tries to do some further modification, but crashes with an type assertion in cast, because `%dec` is no longer an `Instruction`, If the runline is split into two, i.e. you first run `-indvars -loop-instsimplify`, store that into a file, and then run `-loop-reduce`, there is no crash. So it looks like the problem is due to `-loop-instsimplify` not discarding SCEV. But in this case we can just not crash if it's not an `Instruction`. This is just a local fix, unlike D48597, so there may very well be other problems. Reviewers: mkazantsev, uabelho, sanjoy, silviu.baranga, wmi Reviewed By: mkazantsev Subscribers: evstupac, javed.absar, spatel, llvm-commits Differential Revision: https://reviews.llvm.org/D48599 llvm-svn: 335950
* Add a PhiValuesAnalysis pass to calculate the underlying values of phisJohn Brawn2018-06-283-0/+198
| | | | | | | | | | | | This pass is being added in order to make the information available to BasicAA, which can't do caching of this information itself, but possibly this information may be useful for other passes. Incorporates code based on Daniel Berlin's implementation of Tarjan's algorithm. Differential Revision: https://reviews.llvm.org/D47893 llvm-svn: 335857
* [AliasSet] Fix UnknownInstructions printingJakub Kuderski2018-06-271-2/+6
| | | | | | | | | | | | | | | | | Summary: AliasSet::print uses `I->printAsOperand` to print UnknownInstructions. The problem is that not all UnknownInstructions have names (e.g. call instructions). When such instructions are printed, they appear as `<badref>` in AliasSets, which is very confusing, as the values are perfectly valid. This patch fixes that by printing UnknownInstructions without a name using `print` instead of `printAsOperand`. Reviewers: asbirlea, chandlerc, sanjoy, grosser Reviewed By: asbirlea Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D48609 llvm-svn: 335751
* [InstSimplify] fold shifts by sext boolSanjay Patel2018-06-261-1/+5
| | | | | | https://rise4fun.com/Alive/c3Y llvm-svn: 335633
* [InstSimplify] fold srem with sext bool divisorSanjay Patel2018-06-261-0/+6
| | | | llvm-svn: 335616
* [ThinLTO] Add string saver onto index for value namesTeresa Johnson2018-06-261-2/+2
| | | | | | | | | | | | | | | | | | | | | Summary: Adds a string saver to the ModuleSummaryIndex so it can store value names in the case of adding a ValueInfo for a GUID when we don't have the name stored in a Module string table. This is motivated by the upcoming summary parser patch, where we will read value names from the summary entry and want to store them, even when a Module is not available. Currently this allows us to store the name in the legacy bitcode case, and I have added a test to show that. Reviewers: pcc, dexonsmith Subscribers: mehdi_amini, inglorion, eraman, steven_wu, llvm-commits Differential Revision: https://reviews.llvm.org/D47842 llvm-svn: 335570
* [ThinLTO] Compute GUID directly from GV when building per-module indexTeresa Johnson2018-06-261-6/+6
| | | | | | | | | | | | | | | | | | | | | | | Summary: I discovered when writing the summary parsing support that the per-module index builder and writer are computing the GUID from the value name alone (ignoring the linkage type). This was ok since those GUID were not emitted in the bitcode, and there are never multiple conflicting names in a single module. However, I don't see a reason for making the GUID computation different for the per-module case. It also makes things simpler on the parsing side to have the GUID computation consistent. So this patch changes the summary analysis phase and the per-module summary writer to compute the GUID using the facility on the GlobalValue. Reviewers: pcc, dexonsmith Subscribers: llvm-commits, inglorion Differential Revision: https://reviews.llvm.org/D47844 llvm-svn: 335560
* Revert r335513: [SCEVExp] Advance found insertion pointFlorian Hahn2018-06-251-4/+3
| | | | llvm-svn: 335522
* [SCEVExp] Advance found insertion point until we find a non-dbg instruction.Florian Hahn2018-06-251-3/+4
| | | | | | | | | | | | | This avoids creating unnecessary casts if the IP used to be a dbg info intrinsic. Fixes PR37727. Reviewers: vsk, aprantl, sanjoy, efriedma Reviewed By: vsk, efriedma Differential Revision: https://reviews.llvm.org/D47874 llvm-svn: 335513
* [InstSimplify] fold div/rem of zexted boolSanjay Patel2018-06-251-1/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | I was looking at an unrelated fold and noticed that we don't have this simplification (because the other fold would break existing tests). Name: zext udiv %z = zext i1 %x to i32 %r = udiv i32 %y, %z => %r = %y Name: zext urem %z = zext i1 %x to i32 %r = urem i32 %y, %z => %r = 0 Name: zext sdiv %z = zext i1 %x to i32 %r = sdiv i32 %y, %z => %r = %y Name: zext srem %z = zext i1 %x to i32 %r = srem i32 %y, %z => %r = 0 https://rise4fun.com/Alive/LZ9 llvm-svn: 335512
* Add Triple::isMIPS()/isMIPS32()/isMIPS64(). NFCAlexander Richardson2018-06-251-2/+1
| | | | | | | | | | | | | | There are quite a few if statements that enumerate all these cases. It gets even worse in our fork of LLVM where we also have a Triple::cheri (which is mips64 + CHERI instructions) and we had to update all if statements that check for Triple::mips64 to also handle Triple::cheri. This patch helps to reduce our diff to upstream and should also make some checks more readable. Reviewed By: atanasyan Differential Revision: https://reviews.llvm.org/D48548 llvm-svn: 335493
* [DA] Delinearise AddRecs if we can prove they don't wrapDavid Green2018-06-251-2/+21
| | | | | | | | | | | We can prove that some delinearized subscripts do not wrap around to become negative by the fact that they are from inbound geps of load/store locations. This helps improve the delinearisation in cases where we can't prove that they are non-negative from SCEV alone. Differential Revision: https://reviews.llvm.org/D48481 llvm-svn: 335481
* [MSSA] Add domination number verifier; NFCGeorge Burgess IV2018-06-251-0/+39
| | | | | | | | | | | It's easy for domination numbers to get out-of-date, and this is no more costly than any of the other verifiers we already have, so it seems nice to have. A stage3 build with this Works On My Machine, so this hasn't caught any bugs... yet. :) llvm-svn: 335444
* [MSSA] Remove incorrect comment + `auto`ify dyn_cast results; NFCGeorge Burgess IV2018-06-221-6/+5
| | | | llvm-svn: 335399
* [LegacyPM] Fix PR37888 by teaching the legacy loop pass manager how toChandler Carruth2018-06-221-1/+10
| | | | | | | | | | | | | | | | | clear out deleted loops from the current queue beyond just the current loop. This is important because SimpleLoopUnswitch will now enqueue the same loop to be re-processed. When it does this with the legacy PM, we don't have a way of canceling the rest of the pipeline and so we can end up deleting the loop before we reprocess it. =/ This change also makes it easy to support deleting other loops in the queue to process, although I don't have any use cases for that. Differential Revision: https://reviews.llvm.org/D48470 llvm-svn: 335317
* [SCEV] Re-apply r335197 (with Polly fixes).Tim Shen2018-06-211-0/+54
| | | | | | | | | | | | | | | | | Summary: This initiates a discussion on changing Polly accordingly while re-applying r335197 (D48338). I have never worked on Polly. The proposed change to param_div_div_div_2.ll is not educated, but just patterns that match the output. All LLVM files are already reviewed in D48338. Reviewers: jdoerfert, bollu, efriedma Subscribers: jlebar, sanjoy, hiraditya, llvm-commits, bixia Differential Revision: https://reviews.llvm.org/D48453 llvm-svn: 335292
* [DA] Enable -da-delinearize by defaultDavid Green2018-06-211-9/+54
| | | | | | | | | | | | | This enables da-delinearize in Dependence Analysis for delinearizing array accesses into multiple dimensions. This can help to increase the power of Dependence analysis on multi-dimensional arrays and prevent having to fall back to the slower and less accurate MIV tests. It adds static checks on the bounds of the arrays to ensure that one dimension doesn't overflow into another, and brings our code in line with our tests. Differential Revision: https://reviews.llvm.org/D45872 llvm-svn: 335217
* Revert "[SCEV] Improve zext(A /u B) and zext(A % B)"Tim Shen2018-06-211-54/+0
| | | | | | This reverts commit r335197, as some bots are not happy. llvm-svn: 335198
* [SCEV] Improve zext(A /u B) and zext(A % B)Tim Shen2018-06-211-0/+54
| | | | | | | | | | | | | | | Summary: Try to match udiv and urem patterns, and sink zext down to the leaves. I'm not entirely sure why some unrelated tests change, but the added <nsw>s seem right. Reviewers: sanjoy Subscribers: jlebar, hiraditya, bixia, llvm-commits Differential Revision: https://reviews.llvm.org/D48338 llvm-svn: 335197
* [MemorySSA] Verify Phi incoming blocks are block predecessors.Alina Sbirlea2018-06-201-1/+5
| | | | | | | | | | | | Summary: Make the MemorySSA verify also check that all Phi incoming blocks are block predecessors. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D48333 llvm-svn: 335174
* [InstSimplify] Fix missed optimization in simplifyUnsignedRangeCheck()Sanjay Patel2018-06-201-1/+1
| | | | | | | | | | | | | | | | | | | | | For both operands are unsigned, the following optimizations are valid, and missing: 1. X > Y && X != 0 --> X > Y 2. X > Y || X != 0 --> X != 0 3. X <= Y || X != 0 --> true 4. X <= Y || X == 0 --> X <= Y 5. X > Y && X == 0 --> false unsigned foo(unsigned x, unsigned y) { return x > y && x != 0; } should fold to x > y, but I found we haven't done it right now. besides, unsigned foo(unsigned x, unsigned y) { return x < y && y != 0; } Has been folded to x < y, so there may be a bug. Patch by: Li Jia He! Differential Revision: https://reviews.llvm.org/D47922 llvm-svn: 335129
* [IR] move shuffle mask queries from TTI to ShuffleVectorInstSanjay Patel2018-06-191-168/+18
| | | | | | | | | | | | | | | | The optimizer is getting smarter (eg, D47986) about differentiating shuffles based on its mask values, so we should make queries on the mask constant operand generally available to avoid code duplication. We'll probably use this soon in the vectorizers and instcombine (D48023 and https://bugs.llvm.org/show_bug.cgi?id=37806). We might clean up TTI a bit more once all of its current 'SK_*' options are covered. Differential Revision: https://reviews.llvm.org/D48236 llvm-svn: 335067
* Revert "[SCEV] Add nuw/nsw to mul ops in StrengthenNoWrapFlags"Sanjoy Das2018-06-191-19/+6
| | | | | | | | | | | | | | This reverts r334428. It incorrectly marks some multiplications as nuw. Tim Shen is working on a proper fix. Original commit message: [SCEV] Add nuw/nsw to mul ops in StrengthenNoWrapFlags where safe. Summary: Previously we would add them for adds, but not multiplies. llvm-svn: 335016
* Fix namespaces. No functionality change.Benjamin Kramer2018-06-161-1/+1
| | | | llvm-svn: 334890
* Revert "[SCEV] Use LLVM_MARK_AS_BITMASK_ENUM in SCEV." -- breaks MSVC builds.Justin Lebar2018-06-161-34/+38
| | | | | | This reverts D48237. llvm-svn: 334878
* Revert "[SCEV] Simplify some flags expressions." -- dependent revision ↵Justin Lebar2018-06-161-4/+4
| | | | | | | | breaks MSVC builds. This reverts D48238. llvm-svn: 334877
* [SCEV] Simplify some flags expressions.Justin Lebar2018-06-151-4/+4
| | | | | | | | | | | | | | Summary: Sending for presubmit review out of an abundance of caution; it would be bad to mess this up. Reviewers: sanjoy Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D48238 llvm-svn: 334875
* [SCEV] Use LLVM_MARK_AS_BITMASK_ENUM in SCEV.Justin Lebar2018-06-151-38/+34
| | | | | | | | | | | | | | | | | | Summary: Obviates the need for mask/clear/setFlags helpers. There are some expressions here which can be simplified, but to keep this easy to review, I have not simplified them in this patch. No functional change. Reviewers: sanjoy Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D48237 llvm-svn: 334874
OpenPOWER on IntegriCloud