summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar
Commit message (Collapse)AuthorAgeFilesLines
* Analysis: Simplify the ScalarEvolution::getGEPExpr() interface. NFCI.Peter Collingbourne2016-11-132-6/+3
| | | | | | | | All existing callers were manually extracting information out of an existing GEP instruction and passing it to getGEPExpr(). Simplify the interface by changing it to take a GEPOperator instead. llvm-svn: 286751
* Preserve assumption cache in loop-rotate.Eli Friedman2016-11-091-0/+4
| | | | | | | | | | | No testcase included because I can't figure out how to reduce it. (It's easy to write a testcase where rotation clones an assume, but that doesn't actually seem to trigger the crash in opt on its own; maybe an issue with the laziness?) Differential Revision: https://reviews.llvm.org/D26434 llvm-svn: 286410
* Minor unroll pass refacoring.Evgeny Stupachenko2016-11-091-35/+29
| | | | | | | | | | | | | | | | Summary: Unrolled Loop Size calculations moved to a function. Constant representing number of optimized instructions when "back edge" becomes "fall through" replaced with variable. Some comments added. Reviewers: mzolotukhin Differential Revision: http://reviews.llvm.org/D21719 From: Evgeny Stupachenko <evstupac@gmail.com> llvm-svn: 286389
* Remove TimeValue usage from Scalar/SROA.cpp. NFC.Pavel Labath2016-11-091-2/+3
| | | | llvm-svn: 286361
* [ARM] Loop Strength Reduction crashes when targeting ARM or Thumb.Alexandros Lamprineas2016-11-091-3/+3
| | | | | | | | | | | Scalar Evolution asserts when not all the operands of an Add Recurrence Expression are loop invariants. Loop Strength Reduction should only create affine Add Recurrences, so that both the start and the step of the expression are loop invariants. Differential Revision: https://reviews.llvm.org/D26185 llvm-svn: 286347
* Enable Loop Sink pass for functions that has profile.Dehao Chen2016-11-091-0/+5
| | | | | | | | | | | | Summary: For functions with profile data, we are confident that loop sink will be optimal in sinking code. Reviewers: davidxl, hfinkel Subscribers: mehdi_amini, mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D26155 llvm-svn: 286325
* [LoopDistribute] Preserve GlobalsAA also in the new Pass Manager.Davide Italiano2016-11-081-0/+1
| | | | | | Differential Revision: https://reviews.llvm.org/D26408 llvm-svn: 286280
* [JumpThreading] Unfold selects that depend on the same conditionPablo Barrio2016-11-081-38/+77
| | | | | | | | | | | | | | | | | | Summary: These are good candidates for jump threading. This enables later opts (such as InstCombine) to combine instructions from the selects with instructions out of the selects. SimplifyCFG will fold the select again if unfolding wasn't worth it. Patch by James Molloy and Pablo Barrio. Reviewers: rengolin, haicheng, sebpop Subscribers: jojo, jmolloy, llvm-commits Differential Revision: https://reviews.llvm.org/D26391 llvm-svn: 286236
* [TRE] Remove dead codeSanjoy Das2016-11-071-1/+0
| | | | | | Address review by Eli Friedman on rL286147. llvm-svn: 286165
* Avoid tail recursion elimination across calls with operand bundlesSanjoy Das2016-11-071-1/+2
| | | | | | | | | | | | | | | | | | | | Summary: In some specific scenarios with well understood operand bundle types (like `"deopt"`) it may be possible to go ahead and convert recursion to iteration, but TailRecursionElimination does not have that logic today so avoid doing the right thing for now. I need some input on whether `"funclet"` operand bundles should also block tail recursion elimination. If not, I'll allow TRE across calls with `"funclet"` operand bundles and add a test case. Reviewers: rnk, majnemer, nlewycky, ahatanak Subscribers: mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D26270 llvm-svn: 286147
* [MemCpyOpt] Don't emit IR in an unspecified orderBenjamin Kramer2016-11-071-4/+4
| | | | | | | | | Argument evaluation order is one of the edge cases where Clang differs from GCC, yielding different IR depending on which compiler LLVM was built with. Make the order deterministic and tune the test to actually verify the order instead of trying to hide it. llvm-svn: 286126
* [LoopStrengthReduce] Don't use a DenseSet<int64_t> when we might add any ↵Justin Lebar2016-11-051-1/+6
| | | | | | | | | | | | | | | | | | | | | | | | | valid int64_t to the set. Summary: SmallSetVector uses DenseSet, but that means we need to reserve some values for the empty and tombstone keys. It seems to me we should have a general way to let us store full-range ints inside of DenseSets, and furthermore that we probably shouldn't silently let you add ints into DenseSets without explicitly promising that they're in range. But that's a battle for another day; for now, just fix this code, since we currently do something Very Bad when compiling ffmpeg. Fixes PR30914. Reviewers: jeremyhu Subscribers: llvm-commits, mzolotukhin Differential Revision: https://reviews.llvm.org/D26323 llvm-svn: 286038
* Fix a bug found by inspection by PVS-Studio.Chandler Carruth2016-11-031-1/+1
| | | | | | | | | | | This condition is trivially always true prior to the change. The comment at the call site makes it clear that we expect *all* of these to be '=', 'S', or 'I' so fix the code. We have a bug I will update to track the fact that Clang doesn't warn on this: http://llvm.org/PR13101 llvm-svn: 285930
* [Reassociate] Skip analysis of dead code to avoid infinite loop.Bjorn Pettersson2016-11-021-4/+13
| | | | | | | | | | | | | | | | | | | | | | | | Summary: It was detected that the reassociate pass could enter an inifite loop when analysing dead code. Simply skipping to analyse basic blocks that are dead avoids such problems (and as a side effect we avoid spending time on optimising dead code). The solution is using the same Reverse Post Order ordering of the basic blocks when doing the optimisations, as when building the precalculated rank map. A nice side-effect of this solution is that we now know that we only try to do optimisations for blocks with ranked instructions. Fixes https://llvm.org/bugs/show_bug.cgi?id=30818 Reviewers: llvm-commits, davide, eli.friedman, mehdi_amini Subscribers: dberlin Differential Revision: https://reviews.llvm.org/D26154 llvm-svn: 285793
* [MemorySSA] Tighten up types to make our API prettier. NFC.George Burgess IV2016-11-011-4/+3
| | | | | | | | Patch by bryant. Differential Revision: https://reviews.llvm.org/D26126 llvm-svn: 285750
* SpeculativeExecution: Allow speculating more inst typesMatt Arsenault2016-10-281-0/+18
| | | | | | | Partial step towards removing the whitelist and only using TTI's cost. llvm-svn: 285438
* [Reassociate] Removing instructions mutates the IR.Davide Italiano2016-10-281-1/+3
| | | | | | | | | Fixes PR 30784. Discussed with Justin, who pointed out that in the new PassManager infrastructure we can have more fine-grained control on which analyses we want to preserve, but this is the best we can do with the current infrastructure. llvm-svn: 285380
* [LoopUnroll] Check partial unrolling is enabled before initialization. NFC.Haicheng Wu2016-10-271-2/+2
| | | | | | Differential Revision: https://reviews.llvm.org/D23891 llvm-svn: 285330
* Add Loop Sink pass to reverse the LICM based of basic block frequency.Dehao Chen2016-10-274-14/+337
| | | | | | | | | | | | Summary: LICM may hoist instructions to preheader speculatively. Before code generation, we need to sink down the hoisted instructions inside to loop if it's beneficial. This pass is a reverse of LICM: looking at instructions in preheader and sinks the instruction to basic blocks inside the loop body if basic block frequency is smaller than the preheader frequency. Reviewers: hfinkel, davidxl, chandlerc Subscribers: anna, modocache, mgorny, beanz, reames, dberlin, chandlerc, mcrosier, junbuml, sanjoy, mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D22778 llvm-svn: 285308
* [IndVarSimplify][DebugLoc] When widening the exit loop condition, correctly ↵Andrea Di Biagio2016-10-261-0/+5
| | | | | | | | | | | | | | | reuse the debug location of the original comparison. When the loop exit condition is canonicalized as a != compaison, reuse the debug location of the original (non canonical) comparison. Before this patch, the debug location of the new icmp was obtained from the loop latch terminator. This patch fixes the issue by correctly setting the IRBuilder's "current debug location" to the location of the original compare. Differential Revision: https://reviews.llvm.org/D25953 llvm-svn: 285185
* Fix 80-char violations. NFC.Michael Kuperstein2016-10-251-5/+10
| | | | llvm-svn: 285092
* [IndVarSimplify][Dwarf] When widening the IV increment, correctly set the ↵Andrea Di Biagio2016-10-251-0/+5
| | | | | | | | | | | | | | | debug loc. When indvars widened an induction variable, the debug location for the loop increment computation was incorrectly set equal to the debug loc of the loop latch terminator. This patch fixes the issue by propagating the correct location from the original loop increment instruction to the new widened increment. Differential Revision: https://reviews.llvm.org/D25872 llvm-svn: 285083
* [EarlyCSE] Make MemorySSA memory dependency check more aggressive.Geoff Berry2016-10-251-16/+6
| | | | | | | | | | Now that MemorySSA keeps track of whether MemoryUses are optimized, use getClobberingMemoryAccess() to check MemoryUse memory dependencies since it should no longer be so expensive. This is a follow-up change to https://reviews.llvm.org/D25881 llvm-svn: 285080
* [EarlyCSE] Optimize MemoryPhis and reduce memory clobber queries w/ MemorySSAGeoff Berry2016-10-241-10/+44
| | | | | | | | | | | | | | | | | | | | | Summary: When using MemorySSA, re-optimize MemoryPhis when removing a store since this may create MemoryPhis with all identical arguments. Also, when using MemorySSA to check if two MemoryUses are reading from the same version of the heap, use the defining access instead of calling getClobberingAccess, since the latter can currently result in many more AA calls. Once the MemorySSA use optimization tracking changes are done, we can remove this limitation, which should result in more loads being CSE'd. Reviewers: dberlin Subscribers: mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D25881 llvm-svn: 284984
* Revert 284971.Nico Weber2016-10-241-73/+38
| | | | | | | | | It seems to break selfhost on some bots, see e.g. http://lab.llvm.org:8011/builders/clang-x86-windows-msvc2015/builds/21 http://lab.llvm.org:8011/builders/clang-ppc64be-linux-multistage/builds/20 http://lab.llvm.org:8011/builders/clang-ppc64be-linux-lnt/builds/22 llvm-svn: 284979
* [JumpThreading] Unfold selects that depend on the same conditionPablo Barrio2016-10-241-38/+73
| | | | | | | | | | | | | | | | | | Summary: These are good candidates for jump threading. This enables later opts (such as InstCombine) to combine instructions from the selects with instructions out of the selects. SimplifyCFG will fold the select again if unfolding wasn't worth it. Patch by James Molloy and Pablo Barrio. Reviewers: reames, bkramer, mcrosier, gberry, haicheng, jmolloy, sebpop Subscribers: jojo, rengolin, llvm-commits Differential Revision: https://reviews.llvm.org/D25477 llvm-svn: 284971
* Analysis: Move llvm::getConstantRangeFromMetadata to IR library.Peter Collingbourne2016-10-211-0/+1
| | | | | | | | We're about to start using it there. Differential Revision: https://reviews.llvm.org/D25877 llvm-svn: 284865
* [LoopUnroll] Keep the loop test only on the first iteration of max-or-zero loopsJohn Brawn2016-10-211-10/+18
| | | | | | | | | | | | | | | | When we have a loop with a known upper bound on the number of iterations, and furthermore know that either the number of iterations will be either exactly that upper bound or zero, then we can fully unroll up to that upper bound keeping only the first loop test to check for the zero iteration case. Most of the work here is in plumbing this 'max-or-zero' information from the part of scalar evolution where it's detected through to loop unrolling. I've also gone for the safe default of 'false' everywhere but howManyLessThans which could probably be improved. Differential Revision: https://reviews.llvm.org/D25682 llvm-svn: 284818
* Revert "[GVN/PRE] Hoist global values outside of loops."Davide Italiano2016-10-211-58/+26
| | | | | | | | | There's no agreement about this patch. I personally find the PRE machinery of the current GVN hard enough to reason about that I'm not sure I'll try to land this again, instead of working on the rewrite). llvm-svn: 284796
* [GVN] Use defaulted members. No functional change.Benjamin Kramer2016-10-201-10/+3
| | | | llvm-svn: 284726
* [IndVarSimplify] Teach calculatePostIncRange to take guards into accountArtur Pilipenko2016-10-191-2/+26
| | | | | | | | Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D25739 llvm-svn: 284632
* [IndVarSimplify] Use control-dependent range information to prove non-negativityArtur Pilipenko2016-10-191-2/+148
| | | | | | | | | | | | | | | | | | | | | | | | | | | | This change is motivated by the case when IndVarSimplify doesn't widen a comparison of IV increment because it can't prove IV increment being non-negative. We end up with a redundant trunc of the widened increment on this example. for.body: %i = phi i32 [ %start, %for.body.lr.ph ], [ %i.inc, %for.inc ] %within_limits = icmp ult i32 %i, 64 br i1 %within_limits, label %continue, label %for.end continue: %i.i64 = zext i32 %i to i64 %arrayidx = getelementptr inbounds i32, i32* %base, i64 %i.i64 %val = load i32, i32* %arrayidx, align 4 br label %for.inc for.inc: %i.inc = add nsw nuw i32 %i, 1 %cmp = icmp slt i32 %i.inc, %limit br i1 %cmp, label %for.body, label %for.end There is a range check inside of the loop which guarantees the IV to be non-negative. NSW on the increment guarantees that the increment is also non-negative. Teach IndVarSimplify to use the range check to prove non-negativity of loop increments. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D25738 llvm-svn: 284629
* [GVN] Consistently use division instead of shift. NFCI.Davide Italiano2016-10-181-2/+2
| | | | | | | This is in line with other places of GVN (e.g. load coercion logic). llvm-svn: 284535
* [GVN] Remove dead code. NFC.Davide Italiano2016-10-181-20/+1
| | | | llvm-svn: 284534
* [GVN/PRE] Hoist global values outside of loops.Davide Italiano2016-10-151-26/+58
| | | | | | | | | | | In theory this could be generalized to move anything where we prove the operands are available, but that would require rewriting PRE. As NewGVN will hopefully come soon, and we're trying to rewrite PRE in terms of NewGVN+MemorySSA, it's probably not worth spending too much time on it. Fix provided by Daniel Berlin! llvm-svn: 284311
* [NFC] Loop Versioning for LICM code clean upEvgeny Astigeevich2016-10-141-31/+42
| | | | | | | | | | | | - Removed unused class members. - Made class internal data private. - Made class scoped data function scoped where it's possible. - Replace naked new/delete with unique_ptr. - Made resources guaranteed to be freed. Differential Revision: https://reviews.llvm.org/D25464 llvm-svn: 284290
* commit back "GVN-hoist: fix store past load dependence analysis (PR30216, ↵Sebastian Pop2016-10-131-41/+48
| | | | | | | | | | PR30499)" This is with an extra change to avoid calling MemoryLocation::get() on a call instruction. Differential Revision: https://reviews.llvm.org/D25542 llvm-svn: 284098
* Revert "GVN-hoist: fix store past load dependence analysis (PR30216, PR30499)"Reid Kleckner2016-10-131-48/+41
| | | | | | | | | | | This CL didn't actually address the test case in PR30499, and clang still crashes. Also revert dependent change "Memory-SSA cleanup of clobbers interface, NFC" Reverts r283965 and r283967. llvm-svn: 284093
* Reapply "[LoopUnroll] Use the upper bound of the loop trip count to fullly ↵Haicheng Wu2016-10-121-27/+73
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | unroll a loop" Reappy r284044 after revert in r284051. Krzysztof fixed the error in r284049. The original summary: This patch tries to fully unroll loops having break statement like this for (int i = 0; i < 8; i++) { if (a[i] == value) { found = true; break; } } GCC can fully unroll such loops, but currently LLVM cannot because LLVM only supports loops having exact constant trip counts. The upper bound of the trip count can be obtained from calling ScalarEvolution::getMaxBackedgeTakenCount(). Part of the patch is the refactoring work in SCEV to prevent duplicating code. The feature of using the upper bound is enabled under the same circumstance when runtime unrolling is enabled since both are used to unroll loops without knowing the exact constant trip count. llvm-svn: 284053
* Revert "[LoopUnroll] Use the upper bound of the loop trip count to fullly ↵Haicheng Wu2016-10-121-73/+27
| | | | | | | | unroll a loop" This reverts commit r284044. llvm-svn: 284051
* [LoopUnroll] Use the upper bound of the loop trip count to fullly unroll a loopHaicheng Wu2016-10-121-27/+73
| | | | | | | | | | | | | | | | | | | | | | | | | | This patch tries to fully unroll loops having break statement like this for (int i = 0; i < 8; i++) { if (a[i] == value) { found = true; break; } } GCC can fully unroll such loops, but currently LLVM cannot because LLVM only supports loops having exact constant trip counts. The upper bound of the trip count can be obtained from calling ScalarEvolution::getMaxBackedgeTakenCount(). Part of the patch is the refactoring work in SCEV to prevent duplicating code. The feature of using the upper bound is enabled under the same circumstance when runtime unrolling is enabled since both are used to unroll loops without knowing the exact constant trip count. Differential Revision: https://reviews.llvm.org/D24790 llvm-svn: 284044
* [CVP] Convert an AShr to a LShr if 1st operand is known to be nonnegative.Chad Rosier2016-10-121-0/+23
| | | | | | | | | | | | | | An arithmetic shift can be safely changed to a logical shift if the first operand is known positive. This allows ComputeKnownBits (and similar analysis) to determine the sign bit of the shifted value in some cases. In turn, this allows InstCombine to canonicalize a signed comparison (a > 0) into an equality check (a != 0). PR30577 Differential Revision: https://reviews.llvm.org/D25119 llvm-svn: 284013
* Memory-SSA cleanup of clobbers interface, NFCSebastian Pop2016-10-121-15/+16
| | | | | | | | | This implements the cleanup that Danny asked to commit separately from the previous fix to GVN-hoist in https://reviews.llvm.org/D25476#inline-219818 Tested with ninja check on x86_64-linux. llvm-svn: 283967
* GVN-hoist: fix store past load dependence analysis (PR30216, PR30499)Sebastian Pop2016-10-121-28/+34
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is a refreshed version of a patch that was reverted: it fixes the problems reported in both PR30216 and PR30499, and contains all the test-cases from both bugs. To hoist stores past loads, we used to search for potential conflicting loads on the hoisting path by following a MemorySSA def-def link from the store to be hoisted to the previous defining memory access, and from there we followed the def-use chains to all the uses that occur on the hoisting path. The problem is that the def-def link may point to a store that does not alias with the store to be hoisted, and so the loads that are walked may not alias with the store to be hoisted, and even as in the testcase of PR30216, the loads that may alias with the store to be hoisted are not visited. The current patch visits all loads on the path from the store to be hoisted to the hoisting position and uses the alias analysis to ask whether the store may alias the load. I was not able to use the MemorySSA functionality to ask for whether load and store are clobbered: I'm not sure which function to call, so I used a call to AA->isNoAlias(). Store past store is still working as before using a MemorySSA query: I added an extra test to pr30216.ll to make sure store past store does not regress. Tested on x86_64-linux with check and a test-suite run. Differential Revision: https://reviews.llvm.org/D25476 llvm-svn: 283965
* [LCSSA] Implement linear algorithm for the isRecursivelyLCSSAFormIgor Laevsky2016-10-111-3/+6
| | | | | | | | For each block check that it doesn't have any uses outside of it's innermost loop. Differential Revision: https://reviews.llvm.org/D25364 llvm-svn: 283877
* Turn cl::values() (for enum) from a vararg function to using C++ variadic ↵Mehdi Amini2016-10-081-2/+1
| | | | | | | | | | | | | | | template The core of the change is supposed to be NFC, however it also fixes what I believe was an undefined behavior when calling: va_start(ValueArgs, Desc); with Desc being a StringRef. Differential Revision: https://reviews.llvm.org/D25342 llvm-svn: 283671
* [LoopIdiomRecognize] Merge two if conditions into one. NFCI.Davide Italiano2016-10-071-3/+1
| | | | llvm-svn: 283579
* [RS4GC] Fix comment to show TODO. NFCAnna Thomas2016-10-061-1/+1
| | | | llvm-svn: 283449
* [LoopDistribute] Fix a typo in the pass name.Michael Zolotukhin2016-10-051-1/+1
| | | | llvm-svn: 283282
* [RS4GC] Handle ShuffleVector instruction in findBasePointerAnna Thomas2016-10-041-10/+32
| | | | | | | | | | | | | | | Summary: This patch modifies the findBasePointer to handle the shufflevector instruction. Tests run: RS4GC tests, local downstream tests. Reviewers: reames, sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D25197 llvm-svn: 283219
OpenPOWER on IntegriCloud