aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
AgeCommit message (Collapse)AuthorFilesLines
2019-07-08[SCEV] Fix for PR42397. SCEVExpander wrongly adds nsw to shl instruction.Denis Bakhvalov1-2/+6
Change-Id: I76c9f628c092ae3e6e78ebdaf55cec726e25d692 llvm-svn: 365363
2019-07-03[SCEV][LSR] Prevent using undefined value in binopsEugene Leviant1-3/+1
On some occasions ReuseOrCreateCast may convert previously expanded value to undefined. That value may be passed by SCEVExpander as an argument to InsertBinop making IV chain undefined. Differential revision: https://reviews.llvm.org/D63928 llvm-svn: 365009
2019-06-17[SCEV] Use NoWrapFlags when expanding a simple mulSam Parker1-2/+2
Second functional change following on from rL362687. Pass the NoWrapFlags from the MulExpr to InsertBinop when we're generating a shl or mul. Differential Revision: https://reviews.llvm.org/D61934 llvm-svn: 363540
2019-06-14[SCEV] Pass NoWrapFlags when expanding an AddExprSam Parker1-1/+1
InsertBinop now accepts NoWrapFlags, so pass them through when expanding a simple add expression. This is the first re-commit of the functional changes from rL362687, which was previously reverted. Differential Revision: https://reviews.llvm.org/D61934 llvm-svn: 363364
2019-06-12Fix a Wunused-lambda-capture warning.Nico Weber1-1/+1
The capture was added in the first commit of https://reviews.llvm.org/D61934 when it was used. In the reland, the use was removed but the capture wasn't removed. llvm-svn: 363155
2019-06-12[NFC][SCEV] Add NoWrapFlag argument to InsertBinOpSam Parker1-19/+31
'Use wrap flags in InsertBinop' (rL362687) was reverted due to miscompiles. This patch introduces the previous change to pass no-wrap flags but now only FlagAnyWrap is passed. Differential Revision: https://reviews.llvm.org/D61934 llvm-svn: 363147
2019-06-06Revert "[SCEV] Use wrap flags in InsertBinop"Benjamin Kramer1-31/+18
This reverts commit r362687. Miscompiles llvm-profdata during selfhost. llvm-svn: 362699
2019-06-06[SCEV] Use wrap flags in InsertBinopSam Parker1-18/+31
If the given SCEVExpr has no (un)signed flags attached to it, transfer these to the resulting instruction or use them to find an existing instruction. Differential Revision: https://reviews.llvm.org/D61934 llvm-svn: 362687
2019-05-08[SCEV] Suppress hoisting insertion point of binops when unsafeWarren Ristow1-18/+27
InsertBinop tries to move insertion-points out of loops for expressions that are loop-invariant. This patch adds a new parameter, IsSafeToHost, to guard that hoisting. This allows callers to suppress that hoisting for unsafe situations, such as divisions that may have a zero denominator. This fixes PR38697. Differential Revision: https://reviews.llvm.org/D55232 llvm-svn: 360280
2019-05-07[SCEV] Add explicit representations of umin/sminKeno Fischer1-4/+56
Summary: Currently we express umin as `~umax(~x, ~y)`. However, this becomes a problem for operands in non-integral pointer spaces, because `~x` is not something we can compute for `x` non-integral. However, since comparisons are generally still allowed, we are actually able to express `umin(x, y)` directly as long as we don't try to express is as a umax. Support this by adding an explicit umin/smin representation to SCEV. We do this by factoring the existing getUMax/getSMax functions into a new function that does all four. The previous two functions were largely identical. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D50167 llvm-svn: 360159
2019-04-23Use llvm::stable_sortFangrui Song1-2/+2
While touching the code, simplify if feasible. llvm-svn: 358996
2019-04-18Fix a bug in SCEV's isSafeToExpand around speculation safetyPhilip Reames1-1/+19
isSafeToExpand was making a common, but dangerously wrong, mistake in assuming that if any instruction within a basic block executes, that all instructions within that block must execute. This can be trivially shown to be false by considering the following small example: bb: add x, y <-- InsertionPoint call @throws() udiv x, y <-- SCEV* S br ... It's clearly not legal to expand S above the throwing call, but the previous logic would do so since S dominates (but not properlyDominates) the block containing the InsertionPoint. Since iterating instructions w/in a block is expensive, this change special cases two cases: 1) S is an operand of InsertionPoint, and 2) InsertionPoint is the terminator of it's block. These two together are enough to keep all current optimizations triggering while fixing the latent correctness issue. As best I can tell, this is a silent bug in current ToT. Given that, there's no tests with this change. It was noticed in an upcoming optimization change (D60093), and was reviewed as part of that. That change will include the test which caused me to notice the issue. I'm submitting this seperately so that anyone bisecting a problem gets a clear explanation. llvm-svn: 358680
2019-03-18[SCEV] Guard movement of insertion point for loop-invariantsWarren Ristow1-41/+47
This reinstates r347934, along with a tweak to address a problem with PHI node ordering that that commit created (or exposed). (That commit was reverted at r348426, due to the PHI node issue.) Original commit message: r320789 suppressed moving the insertion point of SCEV expressions with dev/rem operations to the loop header in non-loop-invariant situations. This, and similar, hoisting is also unsafe in the loop-invariant case, since there may be a guard against a zero denominator. This is an adjustment to the fix of r320789 to suppress the movement even in the loop-invariant case. This fixes PR30806. Differential Revision: https://reviews.llvm.org/D57428 llvm-svn: 356392
2019-03-05[SCEV] Ensure that isHighCostExpansion takes into account what is being dividedDavid Green1-2/+5
A SCEV is not low-cost just because you can divide it by a power of 2. We need to also check what we are dividing to make sure it too is not a high-code expansion. This helps to not expand the exit value of certain loops, helping not to bloat the code. The change in no-iv-rewrite.ll is reverting back to what it was testing before rL194116, and looks a lot like the other tests in replace-loop-exit-folds.ll. Differential Revision: https://reviews.llvm.org/D58435 llvm-svn: 355393
2019-01-19Update the file headers across all of the LLVM projects in the monorepoChandler Carruth1-4/+3
to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351636
2018-12-05Revert r347934 "[SCEV] Guard movement of insertion point for loop-invariants"David L. Jones1-42/+41
This change caused SEGVs in instcombine. (The r347934 change seems to me to be a precipitating cause, not a root cause. Details are on the llvm-commits thread for r347934.) llvm-svn: 348426
2018-11-30[SCEV] Guard movement of insertion point for loop-invariantsWarren Ristow1-41/+42
r320789 suppressed moving the insertion point of SCEV expressions with dev/rem operations to the loop header in non-loop-invariant situations. This, and similar, hoisting is also unsafe in the loop-invariant case, since there may be a guard against a zero denominator. This is an adjustment to the fix of r320789 to suppress the movement even in the loop-invariant case. This fixes PR30806. Differential Revision: https://reviews.llvm.org/D54713 llvm-svn: 347934
2018-09-27llvm::sort(C.begin(), C.end(), ...) -> llvm::sort(C, ...)Fangrui Song1-1/+1
Summary: The convenience wrapper in STLExtras is available since rL342102. Reviewers: dblaikie, javed.absar, JDevlieghere, andreadb Subscribers: MatzeB, sanjoy, arsenm, dschuff, mehdi_amini, sdardis, nemanjai, jvesely, nhaehnle, sbc100, jgravelle-google, eraman, aheejin, kbarton, JDevlieghere, javed.absar, gbedwell, jrtc27, mgrang, atanasyan, steven_wu, george.burgess.iv, dexonsmith, kristina, jsji, llvm-commits Differential Revision: https://reviews.llvm.org/D52573 llvm-svn: 343163
2018-07-26[SCEV] Don't expand Wrap predicate using inttoptr in ni addrspacesKeno Fischer1-5/+17
Summary: In non-integral address spaces, we're not allowed to introduce inttoptr/ptrtoint intrinsics. Instead, we need to expand any pointer arithmetic as geps on the base pointer. Luckily this is a common task for SCEV, so all we have to do here is hook up the corresponding helper function and add test case. Fixes PR38290 Reviewers: sanjoy Differential Revision: https://reviews.llvm.org/D49832 llvm-svn: 338073
2018-07-26[SCEV] Add an expandAddToGEP overload for a single operand. NFC.Keno Fischer1-10/+12
Only wanting to pass a single SCEV operand to use as the offset of the GEP is a common operation. Right now this requires creating a temporary stack array at every call site. Add an overload that encapsulates that pattern and simplify the call sites. Suggested-By: sanjoy (in https://reviews.llvm.org/D49832) llvm-svn: 338072
2018-06-29SCEVExpander::expandAddRecExprLiterally(): check before casting as InstructionRoman Lebedev1-1/+4
Summary: An alternative to D48597. Fixes [[ https://bugs.llvm.org/show_bug.cgi?id=37936 | PR37936 ]]. The problem is as follows: 1. `indvars` marks `%dec` as `NUW`. 2. `loop-instsimplify` runs `instsimplify`, which constant-folds `%dec` to -1 (D47908) 3. `loop-reduce` tries to do some further modification, but crashes with an type assertion in cast, because `%dec` is no longer an `Instruction`, If the runline is split into two, i.e. you first run `-indvars -loop-instsimplify`, store that into a file, and then run `-loop-reduce`, there is no crash. So it looks like the problem is due to `-loop-instsimplify` not discarding SCEV. But in this case we can just not crash if it's not an `Instruction`. This is just a local fix, unlike D48597, so there may very well be other problems. Reviewers: mkazantsev, uabelho, sanjoy, silviu.baranga, wmi Reviewed By: mkazantsev Subscribers: evstupac, javed.absar, spatel, llvm-commits Differential Revision: https://reviews.llvm.org/D48599 llvm-svn: 335950
2018-06-25Revert r335513: [SCEVExp] Advance found insertion pointFlorian Hahn1-4/+3
llvm-svn: 335522
2018-06-25[SCEVExp] Advance found insertion point until we find a non-dbg instruction.Florian Hahn1-3/+4
This avoids creating unnecessary casts if the IP used to be a dbg info intrinsic. Fixes PR37727. Reviewers: vsk, aprantl, sanjoy, efriedma Reviewed By: vsk, efriedma Differential Revision: https://reviews.llvm.org/D47874 llvm-svn: 335513
2018-05-01Remove \brief commands from doxygen comments.Adrian Prantl1-2/+2
We've been running doxygen with the autobrief option for a couple of years now. This makes the \brief markers into our comments redundant. Since they are a visual distraction and we don't want to encourage more \brief markers in new code either, this patch removes them all. Patch produced by for i in $(git grep -l '\\brief'); do perl -pi -e 's/\\brief //g' $i & done Differential Revision: https://reviews.llvm.org/D46290 llvm-svn: 331272
2018-04-01[Analysis] Change std::sort to llvm::sort in response to r327219Mandeep Singh Grang1-1/+1
Summary: r327219 added wrappers to std::sort which randomly shuffle the container before sorting. This will help in uncovering non-determinism caused due to undefined sorting order of objects having the same key. To make use of that infrastructure we need to invoke llvm::sort instead of std::sort. Note: This patch is one of a series of patches to replace *all* std::sort to llvm::sort. Refer D44363 for a list of all the required patches. Reviewers: sanjoy, dexonsmith, hfinkel, RKSimon Reviewed By: dexonsmith Subscribers: david2050, llvm-commits Differential Revision: https://reviews.llvm.org/D44944 llvm-svn: 328925
2018-03-02Fix more spelling mistakes in comments of LLVM Analysis passesVedant Kumar1-3/+3
Patch by Reshabh Sharma! Differential Revision: https://reviews.llvm.org/D43939 llvm-svn: 326601
2017-12-30Use phi ranges to simplify code. No functionality change intended.Benjamin Kramer1-19/+10
llvm-svn: 321585
2017-12-27[SCEV] Be careful with nuw/nsw/exact in InsertBinopSerguei Katkov1-1/+14
InsertBinop tries to find an appropriate instruction instead of creating a new instruction. When it checks whether instruction is the same as we need to create it ignores nuw/nsw/exact flags. It leads to invalid behavior when poison instruction can be used when it was not expected. Specifically, for example Expander expands the SCEV built for instruction %a = add i32 %v, 1 It is possible that InsertBinop can find an instruction % b = add nuw nsw i32 %v, 1 and will use it instead of version w/o nuw nsw. It is incorrect. The patch conservatively ignores all instructions with any of poison flags installed. Reviewers: sanjoy, mkazantsev, sebpop, jbhateja Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D41576 llvm-svn: 321475
2017-12-15[SCEV] Fix the movement of insertion point in expander. PR35406.Serguei Katkov1-1/+19
We cannot move the insertion point to header if SCEV contains div/rem operations due to they may go over check for zero denominator. Reviewers: sanjoy, mkazantsev, sebpop Reviewed By: sebpop Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D41229 llvm-svn: 320789
2017-12-14[ScalarEvolution] Fix base condition in isNormalAddRecPHI.Bjorn Pettersson1-1/+1
Summary: The function is meant to recurse until it comes upon the phi it's looking for. However, with the current condition, it will recurse until it finds anything _but_ the phi. The function will even fail for simple cases like: %i = phi i32 [ %inc, %loop ], ... ... %inc = add i32 %i, 1 because the base condition will not happen when the phi is recursed to, and the recursion will end with a 'false' result since the previous instruction is a phi. Reviewers: sanjoy, atrick Reviewed By: sanjoy Subscribers: Ka-Ka, bjope, llvm-commits Committing on behalf of: Bevin Hansson (bevinh) Differential Revision: https://reviews.llvm.org/D40946 llvm-svn: 320700
2017-11-29[SCEV][NFC] Break from loop after we found first non-Phi in ↵Max Kazantsev1-1/+5
getAddRecExprPHILiterally llvm-svn: 319306
2017-11-16[SCEV][NFC] Introduce isSafeToExpandAt function to SCEVExpanderMax Kazantsev1-0/+5
This function checks that: 1) It is safe to expand a SCEV; 2) It is OK to materialize it at the specified location. For example, attempt to expand a loop's AddRec to the same loop's preheader should fail. Differential Revision: https://reviews.llvm.org/D39236 llvm-svn: 318377
2017-10-31Undo accidental commitPhilip Reames1-8/+0
These files shouldn't have been submitted in 316967 llvm-svn: 316968
2017-10-30[CGP] Fix crash on i96 bit multiplyPhilip Reames1-0/+8
Issue found by llvm-isel-fuzzer on OSS fuzz, https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=3725 If anyone actually cares about > 64 bit arithmetic, there's a lot more to do in this area. There's a bunch of obviously wrong code in the same function. I don't have the time to fix all of them and am just using this to understand what the workflow for fixing fuzzer cases might look like. llvm-svn: 316967
2017-10-27Revert rL316568 because of sudden performance drop on ARMMax Kazantsev1-2/+8
llvm-svn: 316739
2017-10-25[SCEV] Enhance SCEVFindUnsafe for divisionMax Kazantsev1-8/+2
This patch allows SCEVFindUnsafe algorithm to tread division by any non-positive value as safe. Previously, it could only recognize non-zero constants. Differential Revision: https://reviews.llvm.org/D39228 llvm-svn: 316568
2017-06-19[SCEV] Teach SCEVExpander to expand BinPowMax Kazantsev1-5/+43
Current implementation of SCEVExpander demonstrates a very naive behavior when it deals with power calculation. For example, a SCEV for x^8 looks like (x * x * x * x * x * x * x * x) If we try to expand it, it generates a very straightforward sequence of muls, like: x2 = mul x, x x3 = mul x2, x x4 = mul x3, x ... x8 = mul x7, x This is a non-efficient way of doing that. A better way is to generate a sequence of binary power calculation. In this case the expanded calculation will look like: x2 = mul x, x x4 = mul x2, x2 x8 = mul x4, x4 In some cases the code size reduction for such SCEVs is dramatic. If we had a loop: x = a; for (int i = 0; i < 3; i++) x = x * x; And this loop have been fully unrolled, we have something like: x = a; x2 = x * x; x4 = x2 * x2; x8 = x4 * x4; The SCEV for x8 is the same as in example above, and if we for some reason want to expand it, we will generate naively 7 multiplications instead of 3. The BinPow expansion algorithm here allows to keep code size reasonable. This patch teaches SCEV Expander to generate a sequence of BinPow multiplications if we have repeating arguments in SCEVMulExpressions. Differential Revision: https://reviews.llvm.org/D34025 llvm-svn: 305663
2017-05-27[SCEVExpander] Try harder to avoid introducing inttoptrKeno Fischer1-4/+16
Summary: This fixes introduction of an incorrect inttoptr/ptrtoint pair in the included test case which makes use of non-integral pointers. I suspect there are more cases like this left, but this takes care of the one I was seeing at the moment. Reviewers: sanjoy Subscribers: mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D33129 llvm-svn: 304058
2017-05-01Rename WeakVH to WeakTrackingVH; NFCSanjoy Das1-3/+4
This relands r301424. llvm-svn: 301812
2017-04-28Kill off the old SimplifyInstruction API by converting remaining users.Daniel Berlin1-1/+1
llvm-svn: 301673
2017-04-26Reverts commit r301424, r301425 and r301426Sanjoy Das1-4/+3
Commits were: "Use WeakVH instead of WeakTrackingVH in AliasSetTracker's UnkownInsts" "Add a new WeakVH value handle; NFC" "Rename WeakVH to WeakTrackingVH; NFC" The changes assumed pointers are 8 byte aligned on all architectures. llvm-svn: 301429
2017-04-26Rename WeakVH to WeakTrackingVH; NFCSanjoy Das1-3/+4
Summary: I plan to use WeakVH to mean "nulls itself out on deletion, but does not track RAUW" in a subsequent commit. Reviewers: dblaikie, davide Reviewed By: davide Subscribers: arsenm, mehdi_amini, mcrosier, mzolotukhin, jfb, llvm-commits, nhaehnle Differential Revision: https://reviews.llvm.org/D32266 llvm-svn: 301424
2017-04-14Tighten the API for ScalarEvolutionNormalizationSanjoy Das1-2/+1
llvm-svn: 300331
2017-04-14Remove NormalizeAutodetect; NFCSanjoy Das1-2/+2
It is cleaner to have a callback based system where the logic of whether an add recurrence is normalized or not lives on IVUsers. This is one step in a multi-step cleanup. llvm-svn: 300330
2016-12-19Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper1-1/+1
This creates non-linear behavior in the inliner (see more details in r289755's commit thread). llvm-svn: 290086
2016-12-15Remove the AssumptionCacheHal Finkel1-1/+1
After r289755, the AssumptionCache is no longer needed. Variables affected by assumptions are now found by using the new operand-bundle-based scheme. This new scheme is more computationally efficient, and also we need much less code... llvm-svn: 289756
2016-12-12Revert "[SCEVExpand] do not hoist divisions by zero (PR30935)"Reid Kleckner1-58/+30
Reverts r289412. It caused an OOB PHI operand access in instcombine when ASan is enabled. Reduction in progress. Also reverts "[SCEVExpander] Add a test case related to r289412" llvm-svn: 289453
2016-12-12[SCEVExpand] do not hoist divisions by zero (PR30935)Sebastian Pop1-30/+58
SCEVExpand computes the insertion point for the components of a SCEV to be code generated. When it comes to generating code for a division, SCEVexpand would not be able to check (at compilation time) all the conditions necessary to avoid a division by zero. The patch disables hoisting of expressions containing divisions by anything other than non-zero constants in order to avoid hoisting these expressions past conditions that should hold before doing the division. The patch passes check-all on x86_64-linux. Differential Revision: https://reviews.llvm.org/D27216 llvm-svn: 289412
2016-12-11[SCEVExpander] Explicitly expand AddRec starts into loop preheaderSanjoy Das1-5/+8
This is NFC today, but won't be once D27216 (or an equivalent patch) is in. This change fixes a design problem in SCEVExpander -- it relied on a hoisting optimization to generate correct code for add recurrences. This meant changing the hoisting optimization to not kick in under certain circumstances (to avoid speculating faulting instructions, say) would break correctness. The fix is to make the correctness requirements explicit, and have it not rely on the hoisting optimization for correctness. llvm-svn: 289397
2016-11-20Fix comment typos. NFC.Simon Pilgrim1-1/+1
Identified by Pedro Giffuni in PR27636. llvm-svn: 287490
generated by cgit v1.1 at 2025-10-10 17:09:45 +0000