summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [SCEV] Don't expand Wrap predicate using inttoptr in ni addrspacesKeno Fischer2018-07-261-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
* [SCEV] Add an expandAddToGEP overload for a single operand. NFC.Keno Fischer2018-07-261-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
* SCEVExpander::expandAddRecExprLiterally(): check before casting as InstructionRoman Lebedev2018-06-291-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
* Revert r335513: [SCEVExp] Advance found insertion pointFlorian Hahn2018-06-251-4/+3
| | | | llvm-svn: 335522
* [SCEVExp] Advance found insertion point until we find a non-dbg instruction.Florian Hahn2018-06-251-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
* Remove \brief commands from doxygen comments.Adrian Prantl2018-05-011-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
* [Analysis] Change std::sort to llvm::sort in response to r327219Mandeep Singh Grang2018-04-011-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
* Fix more spelling mistakes in comments of LLVM Analysis passesVedant Kumar2018-03-021-3/+3
| | | | | | | | Patch by Reshabh Sharma! Differential Revision: https://reviews.llvm.org/D43939 llvm-svn: 326601
* Use phi ranges to simplify code. No functionality change intended.Benjamin Kramer2017-12-301-19/+10
| | | | llvm-svn: 321585
* [SCEV] Be careful with nuw/nsw/exact in InsertBinopSerguei Katkov2017-12-271-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
* [SCEV] Fix the movement of insertion point in expander. PR35406.Serguei Katkov2017-12-151-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
* [ScalarEvolution] Fix base condition in isNormalAddRecPHI.Bjorn Pettersson2017-12-141-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
* [SCEV][NFC] Break from loop after we found first non-Phi in ↵Max Kazantsev2017-11-291-1/+5
| | | | | | getAddRecExprPHILiterally llvm-svn: 319306
* [SCEV][NFC] Introduce isSafeToExpandAt function to SCEVExpanderMax Kazantsev2017-11-161-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
* Undo accidental commitPhilip Reames2017-10-311-8/+0
| | | | | | These files shouldn't have been submitted in 316967 llvm-svn: 316968
* [CGP] Fix crash on i96 bit multiplyPhilip Reames2017-10-301-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
* Revert rL316568 because of sudden performance drop on ARMMax Kazantsev2017-10-271-2/+8
| | | | llvm-svn: 316739
* [SCEV] Enhance SCEVFindUnsafe for divisionMax Kazantsev2017-10-251-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
* [SCEV] Teach SCEVExpander to expand BinPowMax Kazantsev2017-06-191-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
* [SCEVExpander] Try harder to avoid introducing inttoptrKeno Fischer2017-05-271-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
* Rename WeakVH to WeakTrackingVH; NFCSanjoy Das2017-05-011-3/+4
| | | | | | This relands r301424. llvm-svn: 301812
* Kill off the old SimplifyInstruction API by converting remaining users.Daniel Berlin2017-04-281-1/+1
| | | | llvm-svn: 301673
* Reverts commit r301424, r301425 and r301426Sanjoy Das2017-04-261-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
* Rename WeakVH to WeakTrackingVH; NFCSanjoy Das2017-04-261-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
* Tighten the API for ScalarEvolutionNormalizationSanjoy Das2017-04-141-2/+1
| | | | llvm-svn: 300331
* Remove NormalizeAutodetect; NFCSanjoy Das2017-04-141-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
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-191-1/+1
| | | | | | | This creates non-linear behavior in the inliner (see more details in r289755's commit thread). llvm-svn: 290086
* Remove the AssumptionCacheHal Finkel2016-12-151-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
* Revert "[SCEVExpand] do not hoist divisions by zero (PR30935)"Reid Kleckner2016-12-121-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
* [SCEVExpand] do not hoist divisions by zero (PR30935)Sebastian Pop2016-12-121-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
* [SCEVExpander] Explicitly expand AddRec starts into loop preheaderSanjoy Das2016-12-111-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
* Fix comment typos. NFC.Simon Pilgrim2016-11-201-1/+1
| | | | | | Identified by Pedro Giffuni in PR27636. llvm-svn: 287490
* Revert r286437 r286438, they caused PR30976Nico Weber2016-11-101-44/+32
| | | | llvm-svn: 286483
* [SCEVExpander] Hoist unsigned divisons when safeSanjoy Das2016-11-101-1/+3
| | | | | | That is, when the divisor is a constant non-zero. llvm-svn: 286438
* [SCEVExpander] Don't hoist divisionsSanjoy Das2016-11-101-32/+42
| | | | | | Fixes PR30942. llvm-svn: 286437
* Create a getelementptr instead of sub expr for ValueOffsetPair if theWei Mi2016-09-141-3/+22
| | | | | | | | | | | | value is a pointer. This patch is to fix PR30213. When expanding an expr based on ValueOffsetPair, if the value is of pointer type, we can only create a getelementptr instead of sub expr. Differential Revision: https://reviews.llvm.org/D24088 llvm-svn: 281439
* Use range algorithms instead of unpacking begin/endDavid Majnemer2016-08-111-3/+2
| | | | | | No functionality change is intended. llvm-svn: 278417
* [SCEV] Update interface to handle SCEVExpander insert point motion.Geoff Berry2016-08-111-2/+1
| | | | | | | | | | | | | | | | | | | | Summary: This is an extension of the fix in r271424. That fix dealt with builder insert points being moved by SCEV expansion, but only for the lifetime of the expand call. This change modifies the interface so that LSR can safely call expand multiple times at the same insert point and do the right thing if one of the expansions decides to move the original insert point. This is a fix for PR28719. Reviewers: sanjoy Subscribers: llvm-commits, mcrosier, mzolotukhin Differential Revision: https://reviews.llvm.org/D23342 llvm-svn: 278413
* Fix the runtime error caused by "Use ValueOffsetPair to enhance value reuse ↵Wei Mi2016-08-091-9/+20
| | | | | | | | | | | | | | during SCEV expansion". The patch is to fix the bug in PR28705. It was caused by setting wrong return value for SCEVExpander::findExistingExpansion. The return values of findExistingExpansion have different meanings when the function is used in different ways so it is easy to make mistake. The fix creates two new interfaces to replace SCEVExpander::findExistingExpansion, and specifies where each interface is expected to be used. Differential Revision: https://reviews.llvm.org/D22942 llvm-svn: 278161
* Recommit "Use ValueOffsetPair to enhance value reuse during SCEV expansion".Wei Mi2016-08-091-13/+17
| | | | | | | | | | | | | | | | | | | | | | | | | The fix for PR28705 will be committed consecutively. In D12090, the ExprValueMap was added to reuse existing value during SCEV expansion. However, const folding and sext/zext distribution can make the reuse still difficult. A simplified case is: suppose we know S1 expands to V1 in ExprValueMap, and S1 = S2 + C_a S3 = S2 + C_b where C_a and C_b are different SCEVConstants. Then we'd like to expand S3 as V1 - C_a + C_b instead of expanding S2 literally. It is helpful when S2 is a complex SCEV expr and S2 has no entry in ExprValueMap, which is usually caused by the fact that S3 is generated from S1 after const folding. In order to do that, we represent ExprValueMap as a mapping from SCEV to ValueOffsetPair. We will save both S1->{V1, 0} and S2->{V1, C_a} into the ExprValueMap when we create SCEV for V1. When S3 is expanded, it will first expand S2 to V1 - C_a because of S2->{V1, C_a} in the map, then expand S3 to V1 - C_a + C_b. Differential Revision: https://reviews.llvm.org/D21313 llvm-svn: 278160
* Revert r276136 "Use ValueOffsetPair to enhance value reuse during SCEV ↵Hans Wennborg2016-07-261-18/+13
| | | | | | | | | | expansion." It causes Clang tests to fail after Windows self-host (PR28705). (Also reverts follow-up r276139.) llvm-svn: 276822
* Use ValueOffsetPair to enhance value reuse during SCEV expansion.Wei Mi2016-07-201-13/+18
| | | | | | | | | | | | | | | | | | | | | | | In D12090, the ExprValueMap was added to reuse existing value during SCEV expansion. However, const folding and sext/zext distribution can make the reuse still difficult. A simplified case is: suppose we know S1 expands to V1 in ExprValueMap, and S1 = S2 + C_a S3 = S2 + C_b where C_a and C_b are different SCEVConstants. Then we'd like to expand S3 as V1 - C_a + C_b instead of expanding S2 literally. It is helpful when S2 is a complex SCEV expr and S2 has no entry in ExprValueMap, which is usually caused by the fact that S3 is generated from S1 after const folding. In order to do that, we represent ExprValueMap as a mapping from SCEV to ValueOffsetPair. We will save both S1->{V1, 0} and S2->{V1, C_a} into the ExprValueMap when we create SCEV for V1. When S3 is expanded, it will first expand S2 to V1 - C_a because of S2->{V1, C_a} in the map, then expand S3 to V1 - C_a + C_b. Differential Revision: https://reviews.llvm.org/D21313 llvm-svn: 276136
* Fix ScalarEvolutionExpander step scaling bugKeno Fischer2016-07-131-0/+7
| | | | | | | | | | | | | | | | The expandAddRecExprLiterally function incorrectly transforms `[Start + Step * X]` into `Step * [Start + X]` instead of the correct transform of `[Step * X] + Start`. This caused https://github.com/JuliaLang/julia/issues/14704#issuecomment-174126219 due to what appeared to be sufficiently complicated loop interactions. Patch by Jameson Nash (jameson@juliacomputing.com). Reviewers: sanjoy Differential Revision: http://reviews.llvm.org/D16505 llvm-svn: 275239
* Avoid output indeterminism between GCC and Clang builds.Patrik Hagglund2016-06-201-2/+6
| | | | | | | | | Remove dependency of the evalution order of function arguments, which is unspecified. Patch by David Stenberg. llvm-svn: 273145
* [SCEV] Keep SCEVExpander insert points consistent.Geoff Berry2016-06-011-35/+52
| | | | | | | | | | | | | | | | | | | | | Summary: Make sure that the SCEVExpander Builder insert point and any saved/restored insert points are kept consistent (i.e. their Instruction and BasicBlock match) when moving instructions in SCEVExpander. This fixes an issue triggered by http://reviews.llvm.org/D18001 [LSR] Create fewer redundant instructions. Test case will be added in reapply commit of above change: http://reviews.llvm.org/D18480 Reapply [LSR] Create fewer redundant instructions. Reviewers: sanjoy Subscribers: mzolotukhin, sanjoy, qcolombet, mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D20703 llvm-svn: 271424
* [SCEVExpander] Fix a failed cast<> assertionSanjoy Das2016-05-111-43/+47
| | | | | | | | | SCEVExpander::replaceCongruentIVs assumes the backedge value of an SCEV-analysable PHI to always be an instruction, when this is not necessarily true. For now address this by bailing out of the optimization if the backedge value of the PHI is a non-Instruction. llvm-svn: 269213
* [SCEVExpander] Don't break SSA in replaceCongruentIVsSanjoy Das2016-05-111-2/+1
| | | | | | | | | | | | `SCEVExpander::replaceCongruentIVs` bypasses `hoistIVInc` if both the original and the isomorphic increments are PHI nodes. Doing this can break SSA if the isomorphic increment is not dominated by the original increment. Get rid of the bypass, and let `hoistIVInc` do the right thing. Fixes PR27232 (compile time crash/hang). llvm-svn: 269212
* [SCEVExpander] Clang format expressions; NFCSanjoy Das2016-05-101-17/+16
| | | | | | The boolean expressions are somewhat hard to read otherwise. llvm-svn: 268998
* [SCEV] Improve the run-time checking of the NoWrap predicateSilviu Baranga2016-04-251-19/+63
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This implements a new method of run-time checking the NoWrap SCEV predicates, which should be easier to optimize and nicer for targets that don't correctly handle multiplication/addition of large integer types (like i128). If the AddRec is {a,+,b} and the backedge taken count is c, the idea is to check that |b| * c doesn't have unsigned overflow, and depending on the sign of b, that: a + |b| * c >= a (b >= 0) or a - |b| * c <= a (b <= 0) where the comparisons above are signed or unsigned, depending on the flag that we're checking. The advantage of doing this is that we avoid extending to a larger type and we avoid the multiplication of large types (multiplying i128 can be expensive). Reviewers: sanjoy Subscribers: llvm-commits, mzolotukhin Differential Revision: http://reviews.llvm.org/D19266 llvm-svn: 267389
* Remove emacs mode markers from .cpp files. NFCNick Lewycky2016-04-241-1/+1
| | | | | | .cpp files are unambiguously C++, you only need the mode markers on .h files. llvm-svn: 267353
OpenPOWER on IntegriCloud