summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar
Commit message (Collapse)AuthorAgeFilesLines
* [PRE] Preserve !invariant.load metadataPhilip Reames2015-11-171-0/+2
| | | | | | Spoted via inspection. Test case included. llvm-svn: 253275
* Add intermediate subtract instructions to reassociation worklist.Owen Anderson2015-11-161-9/+39
| | | | | | | | | | We sometimes create intermediate subtract instructions during reassociation. Adding these to the worklist to revisit exposes many additional reassociation opportunities. Patch by Aditya Nandakumar. llvm-svn: 253240
* [LoopStrengthReduce] Don't increment iterator past the end of the BBDavid Majnemer2015-11-161-1/+1
| | | | | | | | | | | We tried to move the insertion point beyond instructions like landingpad and cleanuppad. However, we *also* tried to move past catchpad. This is problematic because catchpad is also a terminator. This fixes PR25541. llvm-svn: 253238
* [Sink] Don't move landingpadsKeno Fischer2015-11-161-1/+1
| | | | | | | | | | | | | | | Summary: Moving landingpads into successor basic blocks makes the verifier sad. Teach Sink that much like PHI nodes and terminator instructions, landingpads (and cleanuppads, etc.) may not be moved between basic blocks. Reviewers: majnemer Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D14475 llvm-svn: 253182
* [LIR] Add support for creating memcpys from loops with a negative stride.Chad Rosier2015-11-131-12/+21
| | | | | | | | | | | | | | | This allows us to transform the below loop into a memcpy. void test(unsigned *__restrict__ a, unsigned *__restrict__ b) { for (int i = 2047; i >= 0; --i) { a[i] = b[i]; } } This is the memcpy version of r251518, which added support for memset with negative strided loops. llvm-svn: 253091
* Add a comment that should have made my last commit.Chad Rosier2015-11-131-0/+1
| | | | llvm-svn: 253063
* [LIR] Factor out the code to compute base ptr for negative strided loops.Chad Rosier2015-11-131-10/+15
| | | | | | This will allow for the code to be reused in the memcpy optimization. llvm-svn: 253061
* Revert "Fix bug 25440: GVN assertion after coercing loads"Tobias Grosser2015-11-121-41/+13
| | | | | | This reverts 252919 which broke LNT: MultiSource/Applications/SPASS llvm-svn: 252936
* [LIR] Minor refactoring. NFCI.Chad Rosier2015-11-121-21/+44
| | | | | | | This change prevents uninteresting stores from being inserted into the list of candidate stores for memset/memcpy conversion. llvm-svn: 252926
* Fix bug 25440: GVN assertion after coercing loadsWeiming Zhao2015-11-121-13/+41
| | | | | | | | | | | | | | | | Summary: when coercing loads, it inserts some instructions, which have no GV assigned. https://llvm.org/bugs/show_bug.cgi?id=25440 Reviewers: hfinkel, dberlin Subscribers: dberlin, llvm-commits Differential Revision: http://reviews.llvm.org/D14479 llvm-svn: 252919
* [LIR] General refactor to improve compile-time and simplify code.Chad Rosier2015-11-111-16/+26
| | | | | | | | | | | First create a list of candidates, then transform. This simplifies the code in that you have don't have to worry that you may be using an invalidated iterator. Previously, each time we created a memset/memcpy we would reevaluate the entire loop potentially resulting in lots of redundant work for large basic blocks. llvm-svn: 252817
* Revert "Strip metadata when speculatively hoisting instructions"Renato Golin2015-11-101-4/+0
| | | | | | | This reverts commit r252604, as it broke all ARM and AArch64 buildbots, as well as some x86, et al. llvm-svn: 252623
* Strip metadata when speculatively hoisting instructionsIgor Laevsky2015-11-101-0/+4
| | | | | | | | | | | | | | | | This is fix for PR24059. When we are hoisting instruction above some condition it may turn out that metadata on this instruction was control dependant on the condition. This metadata becomes invalid and we need to drop it. This patch should cover most obvious places of speculative execution (which I have found by greping isSafeToSpeculativelyExecute). I think there are more cases but at least this change covers the severe ones. Differential Revision: http://reviews.llvm.org/D14398 llvm-svn: 252604
* Simplify. NFC.Chad Rosier2015-11-091-4/+1
| | | | llvm-svn: 252491
* Allow LLE/LD and the loop versioning infrastructure to use SCEV predicatesSilviu Baranga2015-11-092-6/+37
| | | | | | | | | | | | | | | | | | | Summary: LAA currently generates a set of SCEV predicates that must be checked by users. In the case of Loop Distribute/Loop Load Elimination, no such predicates could have been emitted, since we don't allow stride versioning. However, in the future there could be SCEV predicates that will need to be checked. This change adds support for SCEV predicate versioning in the Loop Distribute, Loop Load Eliminate and the loop versioning infrastructure. Reviewers: anemet Subscribers: mssimpso, sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D14240 llvm-svn: 252467
* [LoopStrengthReduce] Don't bother fixing up PHIs from EH Pad predsDavid Majnemer2015-11-081-0/+3
| | | | | | | | We cannot really insert fixup code into a PHI's predecessor. This fixes PR25445. llvm-svn: 252416
* ADT: Remove last implicit ilist iterator conversions, NFCDuncan P. N. Exon Smith2015-11-071-1/+1
| | | | | | | | | | Some implicit ilist iterator conversions have crept back into Analysis, Transforms, Hexagon, and llvm-stress. This removes them. I'll commit a patch immediately after this to disallow them (in a separate patch so that it's easy to revert if necessary). llvm-svn: 252371
* Add 'notail' marker for call instructions.Akira Hatanaka2015-11-061-2/+4
| | | | | | | | | | | | This marker prevents optimization passes from adding 'tail' or 'musttail' markers to a call. Is is used to prevent tail call optimization from being performed on the call. rdar://problem/22667622 Differential Revision: http://reviews.llvm.org/D12923 llvm-svn: 252368
* [ValueTracking] Add parameters to isImpliedCondition; NFCSanjoy Das2015-11-061-1/+3
| | | | | | | | | | | | | | | | Summary: This change makes the `isImpliedCondition` interface similar to the rest of the functions in ValueTracking (in that it takes a DataLayout, AssumptionCache etc.). This is an NFC, intended to make a later diff less noisy. Depends on D14369 Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D14391 llvm-svn: 252333
* [LIR] Simplify code by making DataLayout globally accessible. NFC.Chad Rosier2015-11-061-11/+10
| | | | llvm-svn: 252317
* Fix some Clang-tidy modernize warnings, other minor fixes.Eugene Zelenko2015-11-041-2/+2
| | | | | | | | Fixed warnings are: modernize-use-override, modernize-use-nullptr and modernize-redundant-void-arg. Differential revision: http://reviews.llvm.org/D14312 llvm-svn: 252087
* [CVP] Fold return values if possiblePhilip Reames2015-11-041-0/+51
| | | | | | | | | | | | In my previous change to CVP (251606), I made CVP much more aggressive about trying to constant fold comparisons. This patch is a reversal in direction. Rather than being agressive about every compare, we restore the non-block local restriction for most, and then try hard for compares feeding returns. The motivation for this is two fold: * The more I thought about it, the less comfortable I got with the possible compile time impact of the other approach. There have been no reported issues, but after talking to a couple of folks, I've come to the conclusion the time probably isn't justified. * It turns out we need to know the context to leverage the full power of LVI. In particular, asking about something at the end of it's block (the use of a compare in a return) will frequently get more precise results than something in the middle of a block. This is an implementation detail, but it's also hard to get around since mid-block queries have to reason about possible throwing instructions and don't get to use most of LVI's block focused infrastructure. This will become particular important when combined with http://reviews.llvm.org/D14263. Differential Revision: http://reviews.llvm.org/D14271 llvm-svn: 252032
* Fix unused variable warning from r252017Adam Nemet2015-11-041-3/+2
| | | | llvm-svn: 252019
* LLE 6/6: Add LoopLoadElimination passAdam Nemet2015-11-033-0/+556
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: The goal of this pass is to perform store-to-load forwarding across the backedge of a loop. E.g.: for (i) A[i + 1] = A[i] + B[i] => T = A[0] for (i) T = T + B[i] A[i + 1] = T The pass relies on loop dependence analysis via LoopAccessAnalisys to find opportunities of loop-carried dependences with a distance of one between a store and a load. Since it's using LoopAccessAnalysis, it was easy to also add support for versioning away may-aliasing intervening stores that would otherwise prevent this transformation. This optimization is also performed by Load-PRE in GVN without the option of multi-versioning. As was discussed with Daniel Berlin in http://reviews.llvm.org/D9548, this is inferior to a more loop-aware solution applied here. Hopefully, we will be able to remove some complexity from GVN/MemorySSA as a consequence. In the long run, we may want to extend this pass (or create a new one if there is little overlap) to also eliminate loop-indepedent redundant loads and store that *require* versioning due to may-aliasing intervening stores/loads. I have some motivating cases for store elimination. My plan right now is to wait for MemorySSA to come online first rather than using memdep for this. The main motiviation for this pass is the 456.hmmer loop in SPECint2006 where after distributing the original loop and vectorizing the top part, we are left with the critical path exposed in the bottom loop. Being able to promote the memory dependence into a register depedence (even though the HW does perform store-to-load fowarding as well) results in a major gain (~20%). This gain also transfers over to x86: it's around 8-10%. Right now the pass is off by default and can be enabled with -enable-loop-load-elim. On the LNT testsuite, there are two performance changes (negative number -> improvement): 1. -28% in Polybench/linear-algebra/solvers/dynprog: the length of the critical paths is reduced 2. +2% in Polybench/stencils/adi: Unfortunately, I couldn't reproduce this outside of LNT The pass is scheduled after the loop vectorizer (which is after loop distribution). The rational is to try to reuse LAA state, rather than recomputing it. The order between LV and LLE is not critical because normally LV does not touch scalar st->ld forwarding cases where vectorizing would inhibit the CPU's st->ld forwarding to kick in. LoopLoadElimination requires LAA to provide the full set of dependences (including forward dependences). LAA is known to omit loop-independent dependences in certain situations. The big comment before removeDependencesFromMultipleStores explains why this should not occur for the cases that we're interested in. Reviewers: dberlin, hfinkel Subscribers: junbuml, dberlin, mssimpso, rengolin, sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D13259 llvm-svn: 252017
* [LAA] LLE 3/6: Rename InterestingDependence to Dependences, NFCAdam Nemet2015-11-031-6/+5
| | | | | | | | | | | | | | Summary: We now collect all types of dependences including lexically forward deps not just "interesting" ones. Reviewers: hfinkel Subscribers: rengolin, llvm-commits Differential Revision: http://reviews.llvm.org/D13256 llvm-svn: 251985
* Revert "[IndVarSimplify] Rewrite loop exit values with their initial values ↵Tobias Grosser2015-11-031-73/+0
| | | | | | | | | | | | | | | | | | | from loop preheader" Commit 251839 triggers miscompiles on some bots: http://lab.llvm.org:8011/builders/perf-x86_64-penryn-O3-polly-fast/builds/13723 (The commit is listed in 13722, but due to an existing failure introduced in 13721 and reverted in 13723 the failure is only visible in 13723) To verify r251839 is indeed the only change that triggered the buildbot failures and to ensure the buildbots remain green while investigating I temporarily revert this commit. At the current state it is unclear if this commit introduced some miscompile or if it only exposed code to Polly that is subsequently miscompiled by Polly. llvm-svn: 251901
* [IndVarSimplify] Rewrite loop exit values with their initial values from ↵Chen Li2015-11-021-0/+73
| | | | | | | | | | | | | | | | | loop preheader Summary: This patch adds support to check if a loop has loop invariant conditions which lead to loop exits. If so, we know that if the exit path is taken, it is at the first loop iteration. If there is an induction variable used in that exit path whose value has not been updated, it will keep its initial value passing from loop preheader. We can therefore rewrite the exit value with its initial value. This will help remove phis created by LCSSA and enable other optimizations like loop unswitch. Reviewers: sanjoy Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13974 llvm-svn: 251839
* [PM] Port ADCE to the new pass managerJustin Bogner2015-10-302-27/+34
| | | | llvm-svn: 251725
* [LVI/CVP] Teach LVI about range metadataPhilip Reames2015-10-291-26/+6
| | | | | | | | | | | | | | Somewhat shockingly for an analysis pass which is computing constant ranges, LVI did not understand the ranges provided by range metadata. As part of this change, I included a change to CVP primarily because doing so made it much easier to write small self contained test cases. CVP was previously only handling the non-local operand case, but given that LVI can sometimes figure out information about instructions standalone, I don't see any reason to restrict this. There could possibly be a compile time impact from this, but I suspect it should be minimal. If anyone has an example which substaintially regresses, please let me know. I could restrict the block local handling to ICmps feeding Terminator instructions if needed. Note that this patch continues a somewhat bad practice in LVI. In many cases, we know facts about values, and separate context sensitive facts about values. LVI makes no effort to distinguish and will frequently cache the same value fact repeatedly for different contexts. I would like to change this, but that's a large enough change that I want it to go in separately with clear documentation of what's changing. Other examples of this include the non-null handling, and arguments. As a meta comment: the entire motivation of this change was being able to write smaller (aka reasonable sized) test cases for a future patch teaching LVI about select instructions. Differential Revision: http://reviews.llvm.org/D13543 llvm-svn: 251606
* [JumpThreading] Use dominating conditions to prove implicationsSanjoy Das2015-10-281-2/+40
| | | | | | | | | | | | | | | Summary: If P branches to Q conditional on C and Q branches to R conditional on C' and C => C' then the branch conditional on C' can be folded to an unconditional branch. Reviewers: reames Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13972 llvm-svn: 251557
* Typo.Chad Rosier2015-10-281-1/+1
| | | | llvm-svn: 251521
* Reapply: [LIR] Add support for creating memsets from loops with a negative ↵Chad Rosier2015-10-281-24/+32
| | | | | | | | stride. The simple fix is to prevent forming memcpy from loops with a negative stride. llvm-svn: 251518
* Revert "[LIR] Add support for creating memsets from loops with a negative ↵Chad Rosier2015-10-281-28/+24
| | | | | | | | stride." This reverts commit r251512. This is causing LNT/chomp to fail. llvm-svn: 251513
* [LIR] Add support for creating memsets from loops with a negative stride.Chad Rosier2015-10-281-24/+28
| | | | | | http://reviews.llvm.org/D14125 llvm-svn: 251512
* Revert r251492 "[IndVarSimplify] Rewrite loop exit values with their Chen Li2015-10-281-71/+0
| | | | | | initial values from loop preheader", because it broke some bots. llvm-svn: 251498
* [IndVarSimplify] Rewrite loop exit values with their initial values from ↵Chen Li2015-10-281-0/+71
| | | | | | | | | | | | | | | | | loop preheader Summary: This patch adds support to check if a loop has loop invariant conditions which lead to loop exits. If so, we know that if the exit path is taken, it is at the first loop iteration. If there is an induction variable used in that exit path whose value has not been updated, it will keep its initial value passing from loop preheader. We can therefore rewrite the exit value with its initial value. This will help remove phis created by LCSSA and enable other optimizations like loop unswitch. Reviewers: sanjoy Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13974 llvm-svn: 251492
* [RS4GC] Strip noalias attribute after statepoint rewriteIgor Laevsky2015-10-261-1/+4
| | | | | | | | | We should remove noalias along with dereference and dereference_or_null attributes because statepoint could potentially touch the entire heap including noalias objects. Differential Revision: http://reviews.llvm.org/D14032 llvm-svn: 251333
* Convert assert(false) into llvm_unreachable where it makes sense.Benjamin Kramer2015-10-251-1/+1
| | | | llvm-svn: 251266
* ScalarReplAggregates.cpp: Try to appease clash of anonymous::SROA in modules ↵NAKAMURA Takumi2015-10-241-0/+1
| | | | | | build. llvm-svn: 251181
* [RS4GC] Rename stripDereferenceabilityInfo into stripNonValidAttributes.Igor Laevsky2015-10-231-18/+18
| | | | llvm-svn: 251157
* GVN: don't try to replace instruction with itself.Tim Northover2015-10-231-5/+9
| | | | | | | | | | | After some look-ahead PRE was added for GEPs, an instruction could end up in the table of candidates before it was actually inspected. When this happened the pass might decide it was the best candidate to replace itself. This didn't go well. Should fix PR25291 llvm-svn: 251145
* LoopPass: Simplify the API for adding a new loop. NFCJustin Bogner2015-10-221-5/+4
| | | | | | | The insertLoop() API is only used to add new loops, and has confusing ownership semantics. Simplify it by replacing it with addLoop(). llvm-svn: 251064
* [Sink] Don't check BB.empty()David Majnemer2015-10-221-1/+1
| | | | | | | | As an invariant, BasicBlocks cannot be empty when passed to a transform. This is not the case for MachineBasicBlocks and the Sink pass was ported from the MachineSink pass which would explain the check's existence. llvm-svn: 251057
* [RS4GC] Remove a redundant linear search, NFCISanjoy Das2015-10-201-2/+1
| | | | | | | Since LiveVariables is uniqued (we just created it from a `DenseSet`), `FindIndex(LiveVariables, LiveVariables[i])` is always `i`. llvm-svn: 250786
* [RS4GC] Clean up `find_index`; NFCSanjoy Das2015-10-201-11/+11
| | | | | | | - Bring it up to the LLVM Coding Style - Sink it inside `CreateGCRelocates`, which is its only user llvm-svn: 250785
* [RS4GC] Re-purpose `normalizeForInvokeSafepoint`; NFC.Sanjoy Das2015-10-201-9/+9
| | | | | | | | | | | | `normalizeForInvokeSafepoint` in RewriteStatepointsForGC.cpp, as it is written today, deals with `gc.relocate` and `gc.result` uses of a statepoint equally well. This change documents this fact and adds a test case. There is no functional change here -- only documentation of existing functionality. llvm-svn: 250784
* [RS4GC] Minor cleanup to `normalizeForInvokeSafepoint`; NFCSanjoy Das2015-10-201-3/+3
| | | | llvm-svn: 250783
* Preserve CFG in MergedLoadStoreMotion. This fixes PR24426.Jakub Staszak2015-10-181-0/+1
| | | | llvm-svn: 250660
* [RS4GC] Dont' propagate call attrs related to patchable statepointsSanjoy Das2015-10-161-0/+7
| | | | | | | | The `"statepoint-id"` and `"statepoint-num-patch-bytes"` attributes are used solely to determine properties of the `gc.statepoint` being created. Once the `gc.statepoint` is in place, these should be removed. llvm-svn: 250491
* [RS4GC] Bring legalizeCallAttributes up to LLVM coding style; NFCSanjoy Das2015-10-161-13/+11
| | | | llvm-svn: 250490
OpenPOWER on IntegriCloud