summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* Reintroduce r320049, r320014 and r319894.Igor Laevsky2017-12-131-0/+28
| | | | | | OpenGL issues should be fixed by now. llvm-svn: 320568
* [SLP] Vectorize jumbled memory loads.Mohammad Shahid2017-12-131-0/+71
| | | | | | | | | | | | | | | | | | | | | | Summary: This patch tries to vectorize loads of consecutive memory accesses, accessed in non-consecutive or jumbled way. An earlier attempt was made with patch D26905 which was reverted back due to some basic issue with representing the 'use mask' of jumbled accesses. This patch fixes the mask representation by recording the 'use mask' in the usertree entry. Change-Id: I9fe7f5045f065d84c126fa307ef6ebe0787296df Reviewers: mkuper, loladiro, Ayal, zvi, danielcdh Reviewed By: Ayal Subscribers: mgrang, dcaballe, hans, mzolotukhin Differential Revision: https://reviews.llvm.org/D36130 llvm-svn: 320548
* Revert r320049, r320014 and r319894Igor Laevsky2017-12-121-28/+0
| | | | | | | They were causing failures of the piglit OpenGL tests with AMD GPUs using the Mesa radeonsi driver. llvm-svn: 320466
* [SCEV] Fix wrong Equal predicate created in getAddRecForPhiWithCastsDorit Nuzman2017-12-101-6/+9
| | | | | | | | | | | | | | | | | | | CreateAddRecFromPHIWithCastsImpl() adds an IncrementNUSW overflow predicate which allows the PSCEV rewriter to rewrite this scev expression: (zext i8 {0, + , (trunc i32 step to i8)} to i32) into {0, +, (sext i8 (trunc i32 step to i8) to i32)} But then it adds the wrong Equal predicate: %step == (zext i8 (trunc i32 %step to i8) to i32). instead of: %step == (sext i8 (trunc i32 %step to i8) to i32) This is fixed here. Differential Revision: https://reviews.llvm.org/D40641 llvm-svn: 320298
* Infer lowest bits of an integer Multiply when the low bits of the operands ↵Simon Dardis2017-12-091-9/+66
| | | | | | | | | | | | | | | are known When the lowest bits of the operands to an integer multiply are known, the low bits of the result are deducible. Code to deduce known-zero bottom bits already existed, but this change improves on that by deducing known-ones. Patch by: Pedro Ferreira Reviewers: craig.topper, sanjoy, efriedma Differential Revision: https://reviews.llvm.org/D34029 llvm-svn: 320269
* Hardware-assisted AddressSanitizer (llvm part).Evgeniy Stepanov2017-12-092-3/+6
| | | | | | | | | | | | | | | | | | | | | Summary: This is LLVM instrumentation for the new HWASan tool. It is basically a stripped down copy of ASan at this point, w/o stack or global support. Instrumenation adds a global constructor + runtime callbacks for every load and store. HWASan comes with its own IR attribute. A brief design document can be found in clang/docs/HardwareAssistedAddressSanitizerDesign.rst (submitted earlier). Reviewers: kcc, pcc, alekseyshl Subscribers: srhines, mehdi_amini, mgorny, javed.absar, eraman, llvm-commits, hiraditya Differential Revision: https://reviews.llvm.org/D40932 llvm-svn: 320217
* Revert r320104: infinite loop profiling bug fixXinliang David Li2017-12-081-4/+0
| | | | | | | | | | | Causes unexpected memory issue with New PM this time. The new PM invalidates BPI but not BFI, leaving the reference to BPI from BFI invalid. Abandon this patch. There is a more general solution which also handles runtime infinite loop (but not statically). llvm-svn: 320180
* [NFC] Rename variable from Cond to Pred to make it more soundMax Kazantsev2017-12-081-12/+12
| | | | llvm-svn: 320144
* [SCEV] Fix predicate usage in computeExitLimitFromICmpMax Kazantsev2017-12-081-1/+2
| | | | | | | | | | | | | | | | | | | In this method, we invoke `SimplifyICmpOperands` which takes the `Cond` predicate by reference and may change it along with `LHS` and `RHS` SCEVs. But then we invoke `computeShiftCompareExitLimit` with Values from which the SCEVs have been derived, these Values have not been modified while `Cond` could be. One of possible outcomes of this is that we may falsely prove that an infinite loop ends within some finite number of iterations. In this patch, we save the original `Cond` and pass it along with original operands. This logic may be removed in future once `computeShiftCompareExitLimit` works with SCEVs instead of value operands. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D40953 llvm-svn: 320142
* [ModRefInfo] Make enum ModRefInfo an enum class [NFC].Alina Sbirlea2017-12-078-115/+119
| | | | | | | | | | | | | | | Summary: Make enum ModRefInfo an enum class. Changes to ModRefInfo values should be done using inline wrappers. This should prevent future bit-wise opearations from being added, which can be more error-prone. Reviewers: sanjoy, dberlin, hfinkel, george.burgess.iv Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D40933 llvm-svn: 320107
* [PGO] detect infinite loop and form MST properlyXinliang David Li2017-12-071-0/+4
| | | | | | Differential Revision: http://reviews.llvm.org/D40873 llvm-svn: 320104
* [ModRefInfo] Replace remaining bit-wise operations with wrappers.Alina Sbirlea2017-12-073-5/+5
| | | | llvm-svn: 319993
* [ModRefInfo] Do not use ModRefInfo result in if conditions as this makesAlina Sbirlea2017-12-061-1/+1
| | | | | | | assumptions about the values in the enum. Replace with wrapper returning bool [NFC]. llvm-svn: 319949
* [ModRefInfo] Use createModRefInfo wrapper to create a ModRefInfo from ↵Alina Sbirlea2017-12-061-4/+4
| | | | | | FunctionModRefBehavior. llvm-svn: 319941
* InstructionSimplify: 'extractelement' with an undef index is undefZvi Rackover2017-12-061-0/+5
| | | | | | | | | | | | | | | | | | | Summary: An undef extract index can be arbitrarily chosen to be an out-of-range index value, which would result in the instruction being undef. This change closes a gap identified while working on lowering vector permute intrinsics with variable index vectors to pure LLVM IR. Reviewers: arsenm, spatel, majnemer Reviewed By: arsenm, spatel Subscribers: fhahn, nhaehnle, wdng, llvm-commits Differential Revision: https://reviews.llvm.org/D40231 llvm-svn: 319910
* [InstSimplify] Fold insertelement into undef if index is out of boundsIgor Laevsky2017-12-061-0/+28
| | | | | | Differential Revision: https://reviews.llvm.org/D40650 llvm-svn: 319894
* [SCEV][NFC] Check NoWrap flags before lexicographical comparison of SCEVsMax Kazantsev2017-12-061-0/+8
| | | | | | | | | | | | | | | | Lexicographical comparison of SCEV trees is potentially expensive for big expression trees. We can define ordering between them for AddRecs and N-ary operations by SCEV NoWrap flags to make non-equality check cheaper. This change does not prevent grouping eqivalent SCEVs together and is not supposed to have any meaningful impact on behavior of any transforms. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D40645 llvm-svn: 319889
* [SCEV][NFC] Share value cache between SCEVs in GroupByComplexityMax Kazantsev2017-12-061-22/+26
| | | | | | | | | | | | | Current implementation of `compareSCEVComplexity` is being unreasonable with `SCEVUnknown`s: every time it sees one, it creates a new value cache and tries to prove equality of two values using it. This cache reallocates and gets lost from SCEV to SCEV. This patch changes this behavior: now we create one cache for all values and share it between SCEVs. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D40597 llvm-svn: 319880
* Revert r319482 and r319483 "[memcpyopt] Teach memcpyopt to optimize across ↵Hans Wennborg2017-12-061-8/+0
| | | | | | | | | | | | | | | | | | | | | | | | basic blocks" This caused PR35519. > [memcpyopt] Teach memcpyopt to optimize across basic blocks > > This teaches memcpyopt to make a non-local memdep query when a local query > indicates that the dependency is non-local. This notably allows it to > eliminate many more llvm.memcpy calls in common Rust code, often by 20-30%. > > Fixes PR28958. > > Differential Revision: https://reviews.llvm.org/D38374 > > [memcpyopt] Commit file missed in r319482. > > This change was meant to be included with r319482 but was accidentally > omitted. llvm-svn: 319873
* [ModRefInfo] Initialize ArgMask to MRI_NoModRef.Alina Sbirlea2017-12-051-1/+1
| | | | llvm-svn: 319831
* Modify ModRefInfo values using static inline method abstractions [NFC].Alina Sbirlea2017-12-057-80/+85
| | | | | | | | | | | | | | | | | Summary: The aim is to make ModRefInfo checks and changes more intuitive and less error prone using inline methods that abstract the bit operations. Ideally ModRefInfo would become an enum class, but that change will require a wider set of changes into FunctionModRefBehavior. Reviewers: sanjoy, george.burgess.iv, dberlin, hfinkel Subscribers: nlopes, llvm-commits Differential Revision: https://reviews.llvm.org/D40749 llvm-svn: 319821
* [InstCombine] Don't crash on out of bounds shiftsIgor Laevsky2017-12-051-13/+17
| | | | | | Differential Revision: https://reviews.llvm.org/D40649 llvm-svn: 319761
* [SCEV] Use a "Discovered" set instead of a "Visited" set; NFCSanjoy Das2017-12-041-4/+3
| | | | | | Suggested by Max Kazantsev in https://reviews.llvm.org/D39361 llvm-svn: 319679
* [SCEV] A different fix for PR33494Sanjoy Das2017-12-041-29/+26
| | | | | | | | | | | | | | | | | | | | | | | | | | Summary: I don't think rL309080 is the right fix for PR33494 -- caching ExitLimit only hides the problem[0]. The real issue is that because of how we forget SCEV expressions ScalarEvolution::getBackedgeTakenInfo, in the test case for PR33494 computing the backedge for any loop invalidates the trip count for every other loop. This effectively makes the SCEV cache useless. I've instead made the SCEV expression invalidation in ScalarEvolution::getBackedgeTakenInfo less aggressive to fix this issue. [0]: One way to think about this is that rL309080 essentially augmented the backedge-taken-count cache with another equivalent exit-limit cache. The bug went away because we were explicitly not clearing the exit-limit cache in getBackedgeTakenInfo. But instead of doing all of that, we can just avoid clearing the backedge-taken-count cache. Reviewers: mkazantsev, mzolotukhin Subscribers: mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D39361 llvm-svn: 319678
* Revert "[ValueTracking] Pass only a single lambda to ↵Sam McCall2017-12-041-29/+37
| | | | | | | | | computeKnownBitsFromShiftOperator by using KnownBits struct instead of separate APInts. NFCI" This reverts commit r319624, which seems to cause a miscompile (breaks the multistage PPC buildbots) llvm-svn: 319652
* [ValueTracking] Pass only a single lambda to ↵Craig Topper2017-12-021-37/+29
| | | | | | computeKnownBitsFromShiftOperator by using KnownBits struct instead of separate APInts. NFCI llvm-svn: 319624
* [opt-remarks] If hotness threshold is set, ignore remarks without hotnessAdam Nemet2017-12-011-5/+4
| | | | | | | | | | | | | | These are blocks that haven't not been executed during training. For large projects this could make a significant difference. For the project, I was looking at, I got an order of magnitude decrease in the size of the total YAML files with this and r319235. Differential Revision: https://reviews.llvm.org/D40678 Re-commit after fixing the failing testcase in rL319576, rL319577 and rL319578. llvm-svn: 319581
* IR printing improvement for loop passes - handle -print-module-scopeFedor Sergeev2017-12-011-0/+12
| | | | | | | | | | | | | | | | | Summary: Adding support for -print-module-scope similar to how it is being done for function passes. This option causes loop-pass printer to emit a whole-module IR instead of just a loop itself. Reviewers: sanjoy, silvas, weimingz Reviewed By: sanjoy Subscribers: apilipenko, skatkov, llvm-commits Differential Revision: https://reviews.llvm.org/D40247 llvm-svn: 319566
* Revert "[opt-remarks] If hotness threshold is set, ignore remarks without ↵Adam Nemet2017-12-011-4/+5
| | | | | | | | | | | hotness" This reverts commit r319556. Something is not working with this when used with sample-based profiling. Investigating... llvm-svn: 319562
* [opt-remarks] If hotness threshold is set, ignore remarks without hotnessAdam Nemet2017-12-011-5/+4
| | | | | | | | | | | These are blocks that haven't not been executed during training. For large projects this could make a significant difference. For the project, I was looking at, I got an order of magnitude decrease in the size of the total YAML files with this and r319235. Differential Revision: https://reviews.llvm.org/D40678 llvm-svn: 319556
* [InstSimplify] More fcmp cases when comparing against negative constants.Florian Hahn2017-12-011-0/+22
| | | | | | | | | | | | | | | | | | | | | | | | Summary: For known positive non-zero value X: fcmp uge X, -C => true fcmp ugt X, -C => true fcmp une X, -C => true fcmp oeq X, -C => false fcmp ole X, -C => false fcmp olt X, -C => false Patch by Paul Walker. Reviewers: majnemer, t.p.northover, spatel, RKSimon Reviewed By: spatel Subscribers: fhahn, llvm-commits Differential Revision: https://reviews.llvm.org/D40012 llvm-svn: 319538
* Mark all library options as hidden.Zachary Turner2017-12-015-12/+10
| | | | | | | | | | | | | | | | | These command line options are not intended for public use, and often don't even make sense in the context of a particular tool anyway. About 90% of them are already hidden, but when people add new options they forget to hide them, so if you were to make a brand new tool today, link against one of LLVM's libraries, and run tool -help you would get a bunch of junk that doesn't make sense for the tool you're writing. This patch hides these options. The real solution is to not have libraries defining command line options, but that's a much larger effort and not something I'm prepared to take on. Differential Revision: https://reviews.llvm.org/D40674 llvm-svn: 319505
* [memcpyopt] Teach memcpyopt to optimize across basic blocksDan Gohman2017-11-301-0/+8
| | | | | | | | | | | | This teaches memcpyopt to make a non-local memdep query when a local query indicates that the dependency is non-local. This notably allows it to eliminate many more llvm.memcpy calls in common Rust code, often by 20-30%. Fixes PR28958. Differential Revision: https://reviews.llvm.org/D38374 llvm-svn: 319482
* [InlineCost] Prefer getFunction() to two calls to getParent().Davide Italiano2017-11-301-3/+3
| | | | | | Improves clarity, also slightly cheaper. NFCI. llvm-svn: 319481
* [SCEV][NFC] Break from loop after we found first non-Phi in ↵Max Kazantsev2017-11-291-1/+5
| | | | | | getAddRecExprPHILiterally llvm-svn: 319306
* [SCEV][NFC] Remove condition that can never happen due to check few lines aboveMax Kazantsev2017-11-291-2/+0
| | | | llvm-svn: 319293
* [SCEV][NFC] More efficient caching in CompareValueComplexityMax Kazantsev2017-11-281-4/+4
| | | | | | | | | | | | | | Currently, we use a set of pairs to cache responces like `CompareValueComplexity(X, Y) == 0`. If we had proved that `CompareValueComplexity(S1, S2) == 0` and `CompareValueComplexity(S2, S3) == 0`, this cache does not allow us to prove that `CompareValueComplexity(S1, S3)` is also `0`. This patch replaces this set with `EquivalenceClasses` that merges Values into equivalence sets so that any two values from the same set are equal from point of `CompareValueComplexity`. This, in particular, allows us to prove the fact from example above. Differential Revision: https://reviews.llvm.org/D40429 llvm-svn: 319153
* [SCEV][NFC] More efficient caching in CompareSCEVComplexityMax Kazantsev2017-11-281-8/+9
| | | | | | | | | | | | | Currently, we use a set of pairs to cache responces like `CompareSCEVComplexity(X, Y) == 0`. If we had proved that `CompareSCEVComplexity(S1, S2) == 0` and `CompareSCEVComplexity(S2, S3) == 0`, this cache does not allow us to prove that `CompareSCEVComplexity(S1, S3)` is also `0`. This patch replaces this set with `EquivalenceClasses` any two values from the same set are equal from point of `CompareSCEVComplexity`. This, in particular, allows us to prove the fact from example above. Differential Revision: https://reviews.llvm.org/D40428 llvm-svn: 319149
* [PartiallyInlineLibCalls][x86] add TTI hook to allow sqrt inlining to depend ↵Sanjay Patel2017-11-271-0/+4
| | | | | | | | | | | on arg rather than result This should fix PR31455: https://bugs.llvm.org/show_bug.cgi?id=31455 Differential Revision: https://reviews.llvm.org/D28314 llvm-svn: 319094
* [InstSimplify] use m_APFloat to simplify fcmp folds; NFCISanjay Patel2017-11-271-13/+7
| | | | llvm-svn: 319043
* [SCEV] Adding a check on outgoing branches of a terminator instr for ↵Jatin Bhateja2017-11-261-10/+13
| | | | | | | | | | | | | | | | | | | | | | SCEVBackedgeConditionFolder, NFC. Summary: For a given loop, getLoopLatch returns a non-null value when a loop has only one latch block. In the modified context adding an assertion to check that both the outgoing branches of a terminator instruction (of latch) does not target same header. + few minor code reorganization. Reviewers: jbhateja Reviewed By: jbhateja Subscribers: sanjoy Differential Revision: https://reviews.llvm.org/D40460 llvm-svn: 318997
* [SCEV] NFC : Removing unnecessary check on outgoing branches of a branch instr.Jatin Bhateja2017-11-261-2/+1
| | | | | | | | | | | | | | | | | Summary: For a given loop, getLoopLatch returns a non-null value when a loop has only one latch block. In the modified context a check on both the outgoing branches of a terminator instruction (of latch) to same header is redundant. Reviewers: jbhateja Reviewed By: jbhateja Subscribers: sanjoy Differential Revision: https://reviews.llvm.org/D40460 llvm-svn: 318991
* IR printing improvement for loop passesFedor Sergeev2017-11-221-0/+19
| | | | | | | | | | | | | | | | | | | Summary: Loop-pass printing is somewhat deficient since it does not provide the context around the loop (e.g. preheader). This context information becomes pretty essential when analyzing transformations that move stuff out of the loop. Extending printLoop to cover preheader and exit blocks (if any). Reviewers: sanjoy, silvas, weimingz Reviewed By: sanjoy Subscribers: apilipenko, skatkov, llvm-commits Differential Revision: https://reviews.llvm.org/D40246 llvm-svn: 318878
* [SCEV] Strengthen variance condition in calculateLoopDispositionMax Kazantsev2017-11-221-2/+4
| | | | | | | | | | | | | | | | | | | | | | | | | Given loops `L1` and `L2` with AddRecs `AR1` and `AR2` varying in them respectively. When identifying loop disposition of `AR2` w.r.t. `L1`, we only say that it is varying if `L1` contains `L2`. But there is also a possible situation where `L1` and `L2` are consecutive sibling loops within the parent loop. In this case, `AR2` is also varying w.r.t. `L1`, but we don't correctly identify it. It can lead, for exaple, to attempt of incorrect folding. Consider: AR1 = {a,+,b}<L1> AR2 = {c,+,d}<L2> EXAR2 = sext(AR1) MUL = mul AR1, EXAR2 If we incorrectly assume that `EXAR2` is invariant w.r.t. `L1`, we can end up trying to construct something like: `{a * {c,+,d}<L2>,+,b * {c,+,d}<L2>}<L1>`, which is incorrect because `AR2` is not available on entrance of `L1`. Both situations "`L1` contains `L2`" and "`L1` preceeds sibling loop `L2`" can be handled with one check: "header of `L1` dominates header of `L2`". This patch replaces the old insufficient check with this one. Differential Revision: https://reviews.llvm.org/D39453 llvm-svn: 318819
* Fix r318786Hans Wennborg2017-11-211-2/+2
| | | | llvm-svn: 318787
* removed unused private method decl. NFCNuno Lopes2017-11-211-3/+2
| | | | llvm-svn: 318786
* Add MemorySSA as loop dependency, disabled by default [NFC].Alina Sbirlea2017-11-211-3/+15
| | | | | | | | | | | | | | | | | Summary: First step in adding MemorySSA as dependency for loop pass manager. Adding the dependency under a flag. New pass manager: MSSA pointer in LoopStandardAnalysisResults can be null. Legacy and new pass manager: Use cl::opt EnableMSSALoopDependency. Disabled by default. Reviewers: sanjoy, davide, gberry Subscribers: mehdi_amini, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D40274 llvm-svn: 318772
* [InstSimplify] fold and/or of fcmp ord/uno when operand is known nnanSanjay Patel2017-11-191-9/+51
| | | | | | | | | | | | | | | | | | | The 'ord' and 'uno' predicates have a logic operation for NAN built into their definitions: FCMP_ORD = 7, ///< 0 1 1 1 True if ordered (no nans) FCMP_UNO = 8, ///< 1 0 0 0 True if unordered: isnan(X) | isnan(Y) So we can simplify patterns like this: (fcmp ord (known NNAN), X) && (fcmp ord X, Y) --> fcmp ord X, Y (fcmp uno (known NNAN), X) || (fcmp uno X, Y) --> fcmp uno X, Y It might be better to split this into (X uno 0) | (Y uno 0) as a canonicalization, but that would be another patch. Differential Revision: https://reviews.llvm.org/D40130 llvm-svn: 318627
* [PM/Unswitch] Teach SimpleLoopUnswitch to do non-trivial unswitching,Chandler Carruth2017-11-171-2/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | making it no longer even remotely simple. The pass will now be more of a "full loop unswitching" pass rather than anything substantively simpler than any other approach. I plan to rename it accordingly once the dust settles. The key ideas of the new loop unswitcher are carried over for non-trivial unswitching: 1) Fully unswitch a branch or switch instruction from inside of a loop to outside of it. 2) Update the CFG and IR. This avoids needing to "remember" the unswitched branches as well as avoiding excessively cloning and reliance on complex parts of simplify-cfg to cleanup the cfg. 3) Update the analyses (where we can) rather than just blowing them away or relying on something else updating them. Sadly, #3 is somewhat compromised here as the dominator tree updates were too complex for me to want to reason about. I will need to make another attempt to do this now that we have a nice dynamic update API for dominators. However, we do adhere to #3 w.r.t. LoopInfo. This approach also adds an important principls specific to non-trivial unswitching: not *all* of the loop will be duplicated when unswitching. This fact allows us to compute the cost in terms of how much *duplicate* code is inserted rather than just on raw size. Unswitching conditions which essentialy partition loops will work regardless of the total loop size. Some remaining issues that I will be addressing in subsequent commits: - Handling unstructured control flow. - Unswitching 'switch' cases instead of just branches. - Moving to the dynamic update API for dominators. Some high-level, interesting limitationsV that folks might want to push on as follow-ups but that I don't have any immediate plans around: - We could be much more clever about not cloning things that will be deleted. In fact, we should be able to delete *nothing* and do a minimal number of clones. - There are many more interesting selection criteria for which branch to unswitch that we might want to look at. One that I'm interested in particularly are a set of conditions which all exit the loop and which can be merged into a single unswitched test of them. Differential revision: https://reviews.llvm.org/D34200 llvm-svn: 318549
* [ThinLTO] Remove too aggressive assertion in building function call graph.Volodymyr Sapsai2017-11-171-2/+3
| | | | | | | | | | | | | | | | The assertion was introduced in r317853 but there are cases when a call isn't handled either as direct or indirect. In this case we add a reference graph edge but not a call graph edge. Reviewers: tejohnson Reviewed By: tejohnson Subscribers: mehdi_amini, inglorion, eraman, hiraditya, efriedma, llvm-commits Differential Revision: https://reviews.llvm.org/D40056 llvm-svn: 318540
OpenPOWER on IntegriCloud