summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar
Commit message (Collapse)AuthorAgeFilesLines
...
* [LICM] Reapply r347190 "Make LICM able to hoist phis" with fixJohn Brawn2018-11-281-15/+312
| | | | | | | | | | | | | | | This commit caused failures because it failed to correctly handle cases where we hoist a phi, then hoist a use of that phi, then have to rehoist that use. We need to make sure that we rehoist the use to _after_ the hoisted phi, which we do by always rehoisting to the immediate dominator instead of just rehoisting everything to the original preheader. An option is also added to control whether control flow is hoisted, which is off in this commit but will be turned on in a subsequent commit. Differential Revision: https://reviews.llvm.org/D52827 llvm-svn: 347776
* [LoopSimplifyCFG] Turn on term folding after underlying bug fixedMax Kazantsev2018-11-271-1/+1
| | | | llvm-svn: 347641
* [LoopSimplifyCFG] Fix corner case with duplicating successorsMax Kazantsev2018-11-271-1/+11
| | | | | | | | | | | | It fixes a bug that doesn't update Phi inputs of the only live successor that is in the list of block's successors more than once. Thanks @uabelho for finding this. Differential Revision: https://reviews.llvm.org/D54849 Reviewed By: anna llvm-svn: 347640
* [IPSCCP] Use input operand instead of OriginalOp for ssa_copy.Florian Hahn2018-11-251-5/+5
| | | | | | | | | | | OriginalOp of a Predicate refers to the original IR value, before renaming. While solving in IPSCCP, we have to use the operand of the ssa_copy instead, to avoid missing updates for nested conditions on the same IR value. Fixes PR39772. llvm-svn: 347524
* Disable LoopSimplifyCFG terminator folding by defaultMax Kazantsev2018-11-231-0/+6
| | | | llvm-svn: 347486
* [LoopSimplifyCFG] Don't delete LCSSA PhisMax Kazantsev2018-11-231-1/+4
| | | | | | | | | | | | When removing edges, we also update Phi inputs and may end up removing a Phi if it has only one input. We should not do it for edges that leave the current loop because these Phis are LCSSA Phis and need to be preserved. Thanks @dmgreen for finding this! Differential Revision: https://reviews.llvm.org/D54841 llvm-svn: 347484
* [NFC] Assert that all blocks staying in loop are liveMax Kazantsev2018-11-221-0/+2
| | | | llvm-svn: 347458
* [NFC] Ensure deterministic order of dead exit blocksMax Kazantsev2018-11-221-6/+11
| | | | llvm-svn: 347457
* [NFC] Simplify code by using standard exit blocks collectionMax Kazantsev2018-11-221-10/+8
| | | | llvm-svn: 347454
* [PM] correcting return value for new-pass-manager version of ScalarizerFedor Sergeev2018-11-211-2/+2
| | | | | | Obvious mistake missed during D54695 review. llvm-svn: 347432
* [PM] Port Scalarizer to the new pass manager.Mikael Holmen2018-11-212-55/+72
| | | | | | | | | | | | | | Patch by: markus (Markus Lavin) Reviewers: chandlerc, fedor.sergeev Reviewed By: fedor.sergeev Subscribers: llvm-commits, Ka-Ka, bjope Differential Revision: https://reviews.llvm.org/D54695 llvm-svn: 347392
* [LoopSink] Add preheader to alias setGuozhi Wei2018-11-201-0/+1
| | | | | | | | | | This patch fixes PR39695. The original LoopSink only considers memory alias in loop body. But PR39695 shows that instructions following sink candidate in preheader should also be checked. This is a conservative patch, it simply adds whole preheader block to alias set. It may lose some optimization opportunity, but I think that is very rare because: 1 in the most common case st/ld to the same address, the load should already be optimized away. 2 usually preheader is not very large. Differential Revision: https://reviews.llvm.org/D54659 llvm-svn: 347325
* Recommit "[LoopSimplifyCFG] Teach LoopSimplifyCFG to constant-fold branches ↵Max Kazantsev2018-11-201-0/+315
| | | | | | | | | | | and switches" The initial version of patch lacked Phi nodes updates in destinations of removed edges. This version contains this update and tests on this situation. Differential Revision: https://reviews.llvm.org/D54021 llvm-svn: 347289
* Revert "[LoopSimplifyCFG] Teach LoopSimplifyCFG to constant-fold branches ↵Benjamin Kramer2018-11-191-313/+0
| | | | | | | | and switches" This reverts commits r347183 & r347184. Crashes while building libxml. llvm-svn: 347260
* 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
OpenPOWER on IntegriCloud