summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar
Commit message (Collapse)AuthorAgeFilesLines
* Revert "[LICM] Make LICM able to hoist phis"Benjamin Kramer2018-11-191-302/+15
| | | | | | This reverts commit r347190. llvm-svn: 347225
* [LICM] Make LICM able to hoist phisJohn Brawn2018-11-191-15/+302
| | | | | | | | | | | | | | | The general approach taken is to make note of loop invariant branches, then when we see something conditional on that branch, such as a phi, we create a copy of the branch and (empty versions of) its successors and hoist using that. This has no impact by itself that I've been able to see, as LICM typically doesn't see such phis as they will have been converted into selects by the time LICM is run, but once we start doing phi-to-select conversion later it will be important. Differential Revision: https://reviews.llvm.org/D52827 llvm-svn: 347190
* [LoopSimplifyCFG] Teach LoopSimplifyCFG to constant-fold branches and switchesMax Kazantsev2018-11-191-0/+313
| | | | | | | | | | | | | | | | This patch introduces infrastructure and the simplest case for constant-folding of branch and switch instructions within loop into unconditional branches. It is useful as a cleanup for such passes as loop unswitching that sometimes produce such branches. Only the simplest case supported in this patch: after the folding, no block should become dead or stop being part of the loop. Support for more sophisticated cases will go separately in follow-up patches. Differential Revision: https://reviews.llvm.org/D54021 Reviewed By: anna llvm-svn: 347183
* [CorrelatedValuePropagation] Preserve debug locations (PR38178)Vedant Kumar2018-11-181-15/+16
| | | | | | | | | Fix all of the missing debug location errors in CVP found by debugify. This includes the missing-location-after-udiv-truncation case described in llvm.org/PR38178. llvm-svn: 347147
* Use llvm::copy. NFCFangrui Song2018-11-172-5/+4
| | | | llvm-svn: 347126
* [SimpleLoopUnswitch] adding cost multiplier to cap exponential unswitch withFedor Sergeev2018-11-161-2/+116
| | | | | | | | | | | | | | | | | | | | | We need to control exponential behavior of loop-unswitch so we do not get run-away compilation. Suggested solution is to introduce a multiplier for an unswitch cost that makes cost prohibitive as soon as there are too many candidates and too many sibling loops (meaning we have already started duplicating loops by unswitching). It does solve the currently known problem with compile-time degradation (PR 39544). Tests are built on top of a recently implemented CHECK-COUNT-<num> FileCheck directives. Reviewed By: chandlerc, mkazantsev Differential Revision: https://reviews.llvm.org/D54223 llvm-svn: 347097
* Recommit r346483: [CallSiteSplitting] Only record conditions up to the ↵Florian Hahn2018-11-141-13/+26
| | | | | | | | | IDom(call site). The underlying problem causing the expensive-check failure was fixed in rL346769. llvm-svn: 346843
* [CSP, Cloning] Update DuplicateInstructionsInSplitBetween to use DomTreeUpdater.Florian Hahn2018-11-132-32/+33
| | | | | | | | | | | | | | | | | | | | | This patch updates DuplicateInstructionsInSplitBetween to update a DTU instead of applying updates to the DT directly. Given that there only are 2 users, also updated them in this patch to avoid churn. I slightly moved the code in CallSiteSplitting around to reduce the places where we have to pass in DTU. If necessary, I could split those changes in a separate patch. This fixes missing DT updates when dealing with musttail calls in CallSiteSplitting, by using DTU->deleteBB. Reviewers: junbuml, kuhar, NutshellySima, indutny, brzycki Reviewed By: NutshellySima llvm-svn: 346769
* Introduce DebugCounter into ConstProp passZhizhou Yang2018-11-131-26/+43
| | | | | | | | | | | | | | | | | | | Summary: This patch introduces DebugCounter into ConstProp pass at per-transformation level. It will provide an option to skip first n or stop after n transformations for the whole ConstProp pass. This will make debug easier for the pass, also providing chance to do transformation level bisecting. Reviewers: davide, fhahn Reviewed By: fhahn Subscribers: llozano, george.burgess.iv, llvm-commits Differential Revision: https://reviews.llvm.org/D50094 llvm-svn: 346720
* [LICM] Hoist guards from non-header blocksMax Kazantsev2018-11-121-11/+3
| | | | | | | | | | | This patch relaxes overconservative checks on whether or not we could write memory before we execute an instruction. This allows us to hoist guards out of loops even if they are not in the header block. Differential Revision: https://reviews.llvm.org/D50891 Reviewed By: fedor.sergeev llvm-svn: 346643
* [IPSCCP,PM] Preserve PDT in the new pass manager.Florian Hahn2018-11-111-4/+3
| | | | | | | | | | Reviewers: kuhar, chandlerc, NutshellySima, brzycki Reviewed By: NutshellySima, brzycki Differential Revision: https://reviews.llvm.org/D54317 llvm-svn: 346618
* [JumpThreading] Fix exponential time algorithm computing known values.Eli Friedman2018-11-091-19/+18
| | | | | | | | | | | | | | | | | | | ComputeValueKnownInPredecessors has a "visited" set to prevent infinite loops, since a value can be visited more than once. However, the implementation didn't prevent the algorithm from taking exponential time. Instead of removing elements from the RecursionSet one at a time, we should keep around the whole set until ComputeValueKnownInPredecessors finishes, then discard it. The testcase is synthetic because I was having trouble effectively reducing the original. But it's basically the same idea. Instead of failing, we could theoretically cache the result instead. But I don't think it would help substantially in practice. Differential Revision: https://reviews.llvm.org/D54239 llvm-svn: 346562
* Revert r346483: [CallSiteSplitting] Only record conditions up to the ↵Florian Hahn2018-11-091-38/+15
| | | | | | | | IDom(call site). This cause a failure with EXPENSIVE_CHECKS llvm-svn: 346492
* [IPSCCP,PM] Preserve DT in the new pass manager.Florian Hahn2018-11-091-27/+38
| | | | | | | | | | | | | | After D45330, Dominators are required for IPSCCP and can be preserved. This patch preserves DominatorTreeAnalysis in the new pass manager. AFAIK the legacy pass manager cannot preserve function analysis required by a module analysis. Reviewers: davide, dberlin, chandlerc, efriedma, kuhar, NutshellySima Reviewed By: chandlerc, kuhar, NutshellySima Differential Revision: https://reviews.llvm.org/D47259 llvm-svn: 346486
* [CallSiteSplitting] Only record conditions up to the IDom(call site).Florian Hahn2018-11-091-15/+38
| | | | | | | | | | | | | | | | | | | | | | | We can stop recording conditions once we reached the immediate dominator for the block containing the call site. Conditions in predecessors of the that node will be the same for all paths to the call site and splitting is not beneficial. This patch makes CallSiteSplitting dependent on the DT anlysis. because the immediate dominators seem to be the easiest way of finding the node to stop at. I had to update some exiting tests, because they were checking for conditions that were true/false on all paths to the call site. Those should now be handled by instcombine/ipsccp. Reviewers: davide, junbuml Reviewed By: junbuml Differential Revision: https://reviews.llvm.org/D44627 llvm-svn: 346483
* [NFC] Add utility function for SafetyInfo updates for moveBeforeMax Kazantsev2018-11-091-3/+11
| | | | llvm-svn: 346472
* [LoopInterchange] Support reductions across inner and outer loop.Florian Hahn2018-11-081-44/+130
| | | | | | | | | | | | | | | | | | | | | This patch adds logic to detect reductions across the inner and outer loop by following the incoming values of PHI nodes in the outer loop. If the incoming values take part in a reduction in the inner loop or come from outside the outer loop, we found a reduction spanning across inner and outer loop. With this change, ~10% more loops are interchanged in the LLVM test-suite + SPEC2006. Fixes https://bugs.llvm.org/show_bug.cgi?id=30472 Reviewers: mcrosier, efriedma, karthikthecool, davide, hfinkel, dmgreen Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D43245 llvm-svn: 346438
* Return "[IndVars] Smart hard uses detection"Max Kazantsev2018-11-081-13/+26
| | | | | | | | | | The patch has been reverted because it ended up prohibiting propagation of a constant to exit value. For such values, we should skip all checks related to hard uses because propagating a constant is always profitable. Differential Revision: https://reviews.llvm.org/D53691 llvm-svn: 346397
* [LSR] Combine unfolded offset into invariant registerGil Rapaport2018-11-081-12/+42
| | | | | | | | | | | | | | | LSR reassociates constants as unfolded offsets when the constants fit as immediate add operands, which currently prevents such constants from being combined later with loop invariant registers. This patch modifies GenerateCombinations() to generate a second formula which includes the unfolded offset in the combined loop-invariant register. This commit fixes a bug in the original patch (committed at r345114, reverted at r345123). Differential Revision: https://reviews.llvm.org/D51861 llvm-svn: 346390
* [SimpleLoopUnswitch] partial unswitch needs to be careful when replacing ↵Fedor Sergeev2018-11-071-1/+14
| | | | | | | | | | | | | | | | | | | | | | | | | invariants with constants When partial unswitch operates on multiple conditions at once, .e.g: if (Cond1 || Cond2 || NonInv) ... it should infer (and replace) values for individual conditions only on one side of unswitch and not another. More precisely only these derivations hold true: (Cond1 || Cond2) == false => Cond1 == Cond2 == false (Cond1 && Cond2) == true => Cond1 == Cond2 == true By the way we organize unswitching it means only replacing on "continue" blocks and never on "unswitched" ones. Since trivial unswitch does not have "unswitched" blocks it does not have this problem. Fixes PR 39568. Reviewers: chandlerc, asbirlea Differential Revision: https://reviews.llvm.org/D54211 llvm-svn: 346350
* [LoopSink] Do not sink instructions into non-cold blocksMandeep Singh Grang2018-11-071-0/+7
| | | | | | | | | | | | | | Summary: This fixes PR39570. Reviewers: danielcdh, rnk, bkramer Reviewed By: rnk Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D54181 llvm-svn: 346337
* [NewGVN] Make sure we do not add a user to itself.Florian Hahn2018-11-071-3/+7
| | | | | | | | | | | | | | | | If we simplify an instruction to itself, we do not need to add a user to itself. For congruence classes with a defining expression, we already use a similar logic. Fixes PR38259. Reviewers: davide, efriedma, mcrosier Reviewed By: davide Differential Revision: https://reviews.llvm.org/D51168 llvm-svn: 346335
* Add support for llvm.is.constant intrinsic (PR4898)James Y Knight2018-11-071-0/+2
| | | | | | | | | | | | | | | This adds the llvm-side support for post-inlining evaluation of the __builtin_constant_p GCC intrinsic. Also fixed SCCPSolver::visitCallSite to not blow up when seeing a call to a function where canConstantFoldTo returns true, and one of the arguments is a struct. Updated from patch initially by Janusz Sobczak. Differential Revision: https://reviews.llvm.org/D4276 llvm-svn: 346322
* fix typos aggressively; NFCSanjay Patel2018-11-071-1/+1
| | | | llvm-svn: 346316
* [LICM] Remove too conservative IsMustExecute variableMax Kazantsev2018-11-061-15/+8
| | | | | | | | | | | | | | | | | | LICM relies on variable `MustExecute` which is conservatively set to `false` in all non-headers. It is used when we decide whether or not we want to hoist an instruction or a guard. For the guards, it might be too conservative to use this variable, we can instead use a more precise logic from LoopSafetyInfo. Currently it is only NFC because `IsMemoryNotModified` is also conservatively set to `false` for all non-headers, and we cannot hoist guards from non-header blocks. However once we give up using `IsMemoryNotModified` and use a smarter check instead, this will allow us to hoist guards from all mustexecute non-header blocks. Differential Revision: https://reviews.llvm.org/D50888 Reveiwed By: fedor.sergeev llvm-svn: 346204
* [LICM] Use ICFLoopSafetyInfo in LICMMax Kazantsev2018-11-061-20/+33
| | | | | | | | | | | | | | | This patch makes LICM use `ICFLoopSafetyInfo` that is a smarter version of LoopSafetyInfo that leverages power of Implicit Control Flow Tracking to keep track of throwing instructions and give less pessimistic answers to queries related to throws. The ICFLoopSafetyInfo itself has been introduced in rL344601. This patch enables it in LICM only. Differential Revision: https://reviews.llvm.org/D50377 Reviewed By: apilipenko llvm-svn: 346201
* Revert "[IndVars] Smart hard uses detection"Max Kazantsev2018-11-061-26/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This reverts commit 2f425e9c7946b9d74e64ebbfa33c1caa36914402. It seems that the check that we still should do the transform if we know the result is constant is missing in this code. So the logic that has been deleted by this change is still sometimes accidentally useful. I revert the change to see what can be done about it. The motivating case is the following: @Y = global [400 x i16] zeroinitializer, align 1 define i16 @foo() { entry: br label %for.body for.body: ; preds = %entry, %for.body %i = phi i16 [ 0, %entry ], [ %inc, %for.body ] %arrayidx = getelementptr inbounds [400 x i16], [400 x i16]* @Y, i16 0, i16 %i store i16 0, i16* %arrayidx, align 1 %inc = add nuw nsw i16 %i, 1 %cmp = icmp ult i16 %inc, 400 br i1 %cmp, label %for.body, label %for.end for.end: ; preds = %for.body %inc.lcssa = phi i16 [ %inc, %for.body ] ret i16 %inc.lcssa } We should be able to figure out that the result is constant, but the patch breaks it. Differential Revision: https://reviews.llvm.org/D51584 llvm-svn: 346198
* [MergeICmps] Do not perform the transformation if GEP is used outside of blockTaewook Oh2018-11-051-1/+1
| | | | | | | | | | | | | | | | | Summary: This patch prevents MergeICmps to performn the transformation if the address operand GEP of the load instruction has a use outside of the load's parent block. Without this patch, compiler crashes with the given test case because the use of `%first.i` is still around when the basic block is erased from https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Scalar/MergeICmps.cpp#L620. I think checking `isUsedOutsideOfBlock` with `GEP` is the original intention of the code, as the checking for `LoadI` is already performed in the same function. This patch is incomplete though, as this makes the pass overly conservative and fails the test `tuple-four-int8.ll`. I believe what needs to be done is checking if GEP has a use outside of block that is not the part of "Comparisons" chain. Submit the patch as of now to prevent compiler crash. Reviewers: courbet, trentxintong Reviewed By: courbet Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D54089 llvm-svn: 346151
* [DebugInfo][InstMerge] Fix -debugify for phi node created by -mldst-motionJordan Rupprecht2018-11-021-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: -mldst-motion creates a new phi node without any debug info. Use the merged debug location from the incoming stores to fix this. Fixes PR38177. The test case here is (somewhat) simplified from: ``` struct S { int foo; void fn(int bar); }; void S::fn(int bar) { if (bar) foo = 1; else foo = 0; } ``` Reviewers: dblaikie, gbedwell, aprantl, vsk Reviewed By: vsk Subscribers: vsk, JDevlieghere, llvm-commits Tags: #debug-info Differential Revision: https://reviews.llvm.org/D54019 llvm-svn: 346027
* [NFC][LICM] Factor out instruction erasing logicMax Kazantsev2018-11-021-11/+15
| | | | | | | | | | This patch factors out a function that makes all required updates whenever an instruction gets erased. Differential Revision: https://reviews.llvm.org/D54011 Reviewed By: apilipenko llvm-svn: 345914
* [LoopInterchange] Fix unused variables in release buildFlorian Hahn2018-11-011-0/+2
| | | | llvm-svn: 345881
* [LoopInterchange] Remove support for inner-only reductions.Florian Hahn2018-11-011-105/+20
| | | | | | | | | | | | | | | | | | | | | | Inner-loop only reductions require additional checks to make sure they form a load-phi-store cycle across inner and outer loop. Otherwise the reduction value is not properly preserved. This patch disables interchanging such loops for now, as it causes miscompiles in some cases and it seems to apply only for a tiny amount of loops. Across the test-suite, SPEC2000 and SPEC2006, 61 instead of 62 loops are interchange with inner loop reduction support disabled. With -loop-interchange-threshold=-1000, 3256 instead of 3267. See the discussion and history of D53027 for an outline of how such legality checks could look like. Reviewers: efriedma, mcrosier, davide Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D53027 llvm-svn: 345877
* [NFC] Reorganize code to prepare it for more transformsMax Kazantsev2018-11-011-4/+15
| | | | llvm-svn: 345820
* [IndVars] Smart hard uses detectionMax Kazantsev2018-11-011-13/+26
| | | | | | | | | | | | | | | | When rewriting loop exit values, IndVars considers this transform not profitable if the loop instruction has a loop user which it believes cannot be optimized away. In current implementation only calls that immediately use the instruction are considered as such. This patch extends the definition of "hard" users to any side-effecting instructions (which usually cannot be optimized away from the loop) and also allows handling of not just immediate users, but use chains. Differentlai Revision: https://reviews.llvm.org/D51584 Reviewed By: etherzhhb llvm-svn: 345814
* [LoopUnroll] allow customization for new-pass-manager version of LoopUnrollFedor Sergeev2018-10-311-12/+9
| | | | | | | | | | | | | | | | | Unlike its legacy counterpart new pass manager's LoopUnrollPass does not provide any means to select which flavors of unroll to run (runtime, peeling, partial), relying on global defaults. In some cases having ability to run a restricted LoopUnroll that does more than LoopFullUnroll is needed. Introduced LoopUnrollOptions to select optional unroll behaviors. Added 'unroll<peeling>' to PassRegistry mainly for the sake of testing. Reviewers: chandlerc, tejohnson Differential Revision: https://reviews.llvm.org/D53440 llvm-svn: 345723
* [IndVars] Strengthen restricton in rewriteLoopExitValuesMax Kazantsev2018-10-311-28/+7
| | | | | | | | | | | | | | | | | | | | For some unclear reason rewriteLoopExitValues considers recalculation after the loop profitable if it has some "soft uses" outside the loop (i.e. any use other than call and return), even if we have proved that it has a user inside the loop which we think will not be optimized away. There is no existing unit test that would explain this. This patch provides an example when rematerialisation of exit value is not profitable but it passes this check due to presence of a "soft use" outside the loop. It makes no sense to recalculate value on exit if we are going to compute it due to some irremovable within the loop. This patch disallows applying this transform in the described situation. Differential Revision: https://reviews.llvm.org/D51581 Reviewed By: etherzhhb llvm-svn: 345708
* ADT/STLExtras: Introduce llvm::empty; NFCMatthias Braun2018-10-311-1/+1
| | | | | | | | This is modeled after C++17 std::empty(). Differential Revision: https://reviews.llvm.org/D53909 llvm-svn: 345679
* [SROA] Use offset sizes from the DataLayout instead of the pointer siezes.Nicola Zaghen2018-10-301-6/+6
| | | | | | | | | | This fixes an assertion when constant folding a GEP when the part of the offset was in i32 (IndexSize, as per DataLayout) and part in the i64 (PointerSize) in the newly created test case. Differential Revision: https://reviews.llvm.org/D52609 llvm-svn: 345585
* Fix -Wdocumentation warning. NFCI.Simon Pilgrim2018-10-271-4/+4
| | | | llvm-svn: 345454
* Pointer types were treated as zero-size by MergeICmpsChristy Lee2018-10-261-1/+2
| | | | | | | | | | | | | | | | Summary: The visitICmp analysis function would record compares of pointer types, as size 0. This causes the resulting memcmp() call to have the wrong total size. Found with "self-build" of clang/LLVM on Windows. Reviewers: christylee, trentxintong, courbet Reviewed By: courbet Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D53536 llvm-svn: 345413
* [SimpleLoopUnswitch] Unswitch by experimental.guard intrinsicsMax Kazantsev2018-10-261-2/+107
| | | | | | | | | | | | | | | | | | This patch adds support of `llvm.experimental.guard` intrinsics to non-trivial simple loop unswitching. These intrinsics represent implicit control flow which has pretty much the same semantics as usual conditional branches. The algorithm of dealing with them is following: - Consider guards as unswitching candidates; - If a guard is considered the best candidate, turn it into a branch; - Apply normal unswitching algorithm on this branch. The patch has no compile time effect on code that does not contain any guards. Differential Revision: https://reviews.llvm.org/D53744 Reviewed By: chandlerc llvm-svn: 345387
* [SimpleLoopUnswitch] Make all checks before actual non-trivial unswitchMax Kazantsev2018-10-261-18/+20
| | | | | | | | | | | We should be able to make all relevant checks before we actually start the non-trivial unswitching, so that we could guarantee that once we have started the transform, it will always succeed. Reviewed By: chandlerc Differential Revision: https://reviews.llvm.org/D53747 llvm-svn: 345375
* Update MemorySSA in LoopRotate.Alina Sbirlea2018-10-241-4/+24
| | | | | | | | | | | | Summary: Teach LoopRotate to preserve MemorySSA. Enable tests for correctness, dependency disabled by default. Subscribers: sanjoy, jlebar, Prazek, george.burgess.iv, llvm-commits Differential Revision: https://reviews.llvm.org/D51718 llvm-svn: 345216
* [FPEnv] Convert more BinaryOperator::isFNeg(...) to m_FNeg(...)Cameron McInally2018-10-241-10/+7
| | | | | | | | This work is to avoid regressions when we seperate FNeg from the FSub IR instruction. Differential Revision: https://reviews.llvm.org/D53205 llvm-svn: 345146
* Revert r345114Gil Rapaport2018-10-241-40/+12
| | | | | | Investigating fails. llvm-svn: 345123
* [LSR] Combine unfolded offset into invariant registerGil Rapaport2018-10-241-12/+40
| | | | | | | | | | | | LSR reassociates constants as unfolded offsets when the constants fit as immediate add operands, which currently prevents such constants from being combined later with loop invariant registers. This patch modifies GenerateCombinations() to generate a second formula which includes the unfolded offset in the combined loop-invariant register. Differential Revision: https://reviews.llvm.org/D51861 llvm-svn: 345114
* [Reassociate] replace fake binop queries with 'match' APISanjay Patel2018-10-231-18/+16
| | | | | | | | | | | | | | | | | We need to update this code before introducing an 'fneg' instruction in IR, so we might as well kill off the integer neg/not queries too. This is no-functional-change-intended for scalar code and most vector code. For vectors, we can see that the 'match' API allows for undef elements in constants, so we optimize those cases better. Ideally, there would be a test for each code diff, but I don't see evidence of that for the existing code, so I didn't try very hard to come up with new vector tests for each code change. Differential Revision: https://reviews.llvm.org/D53533 llvm-svn: 345042
* [SLSR] use 'match' to simplify code; NFCSanjay Patel2018-10-231-4/+5
| | | | | | | | | This pass could probably be modified slightly to allow vector splat transforms for practically no cost, but it only works on scalars for now. So the use of the newer 'match' API should make no functional difference. llvm-svn: 345030
* [Reassociate] add 'using namespace' to reduce bloat; NFCSanjay Patel2018-10-221-3/+4
| | | | llvm-svn: 344959
* Use llvm::{all,any,none}_of instead std::{all,any,none}_of. NFCFangrui Song2018-10-191-4/+3
| | | | llvm-svn: 344774
OpenPOWER on IntegriCloud