aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
AgeCommit message (Collapse)AuthorFilesLines
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
2016-11-10Revert r286437 r286438, they caused PR30976Nico Weber1-44/+32
llvm-svn: 286483
2016-11-10[SCEVExpander] Hoist unsigned divisons when safeSanjoy Das1-1/+3
That is, when the divisor is a constant non-zero. llvm-svn: 286438
2016-11-10[SCEVExpander] Don't hoist divisionsSanjoy Das1-32/+42
Fixes PR30942. llvm-svn: 286437
2016-09-14Create a getelementptr instead of sub expr for ValueOffsetPair if theWei Mi1-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
2016-08-11Use range algorithms instead of unpacking begin/endDavid Majnemer1-3/+2
No functionality change is intended. llvm-svn: 278417
2016-08-11[SCEV] Update interface to handle SCEVExpander insert point motion.Geoff Berry1-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
2016-08-09Fix the runtime error caused by "Use ValueOffsetPair to enhance value reuse ↵Wei Mi1-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
2016-08-09Recommit "Use ValueOffsetPair to enhance value reuse during SCEV expansion".Wei Mi1-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
2016-07-26Revert r276136 "Use ValueOffsetPair to enhance value reuse during SCEV ↵Hans Wennborg1-18/+13
expansion." It causes Clang tests to fail after Windows self-host (PR28705). (Also reverts follow-up r276139.) llvm-svn: 276822
2016-07-20Use ValueOffsetPair to enhance value reuse during SCEV expansion.Wei Mi1-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
2016-07-13Fix ScalarEvolutionExpander step scaling bugKeno Fischer1-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
2016-06-20Avoid output indeterminism between GCC and Clang builds.Patrik Hagglund1-2/+6
Remove dependency of the evalution order of function arguments, which is unspecified. Patch by David Stenberg. llvm-svn: 273145
2016-06-01[SCEV] Keep SCEVExpander insert points consistent.Geoff Berry1-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
2016-05-11[SCEVExpander] Fix a failed cast<> assertionSanjoy Das1-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
2016-05-11[SCEVExpander] Don't break SSA in replaceCongruentIVsSanjoy Das1-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
2016-05-10[SCEVExpander] Clang format expressions; NFCSanjoy Das1-17/+16
The boolean expressions are somewhat hard to read otherwise. llvm-svn: 268998
2016-04-25[SCEV] Improve the run-time checking of the NoWrap predicateSilviu Baranga1-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
2016-04-24Remove emacs mode markers from .cpp files. NFCNick Lewycky1-1/+1
.cpp files are unambiguously C++, you only need the mode markers on .h files. llvm-svn: 267353
2016-04-08Re-commit [SCEV] Introduce a guarded backedge taken count and use it in LAA ↵Silviu Baranga1-1/+3
and LV This re-commits r265535 which was reverted in r265541 because it broke the windows bots. The problem was that we had a PointerIntPair which took a pointer to a struct allocated with new. The problem was that new doesn't provide sufficient alignment guarantees. This pattern was already present before r265535 and it just happened to work. To fix this, we now separate the PointerToIntPair from the ExitNotTakenInfo struct into a pointer and a bool. Original commit message: Summary: When the backedge taken codition is computed from an icmp, SCEV can deduce the backedge taken count only if one of the sides of the icmp is an AddRecExpr. However, due to sign/zero extensions, we sometimes end up with something that is not an AddRecExpr. However, we can use SCEV predicates to produce a 'guarded' expression. This change adds a method to SCEV to get this expression, and the SCEV predicate associated with it. In HowManyGreaterThans and HowManyLessThans we will now add a SCEV predicate associated with the guarded backedge taken count when the analyzed SCEV expression is not an AddRecExpr. Note that we only do this as an alternative to returning a 'CouldNotCompute'. We use new feature in Loop Access Analysis and LoopVectorize to analyze and transform more loops. Reviewers: anemet, mzolotukhin, hfinkel, sanjoy Subscribers: flyingforyou, mcrosier, atrick, mssimpso, sanjoy, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D17201 llvm-svn: 265786
2016-04-06Revert r265535 until we know how we can fix the bots Silviu Baranga1-3/+1
llvm-svn: 265541
2016-04-06[SCEV] Introduce a guarded backedge taken count and use it in LAA and LVSilviu Baranga1-1/+3
Summary: When the backedge taken codition is computed from an icmp, SCEV can deduce the backedge taken count only if one of the sides of the icmp is an AddRecExpr. However, due to sign/zero extensions, we sometimes end up with something that is not an AddRecExpr. However, we can use SCEV predicates to produce a 'guarded' expression. This change adds a method to SCEV to get this expression, and the SCEV predicate associated with it. In HowManyGreaterThans and HowManyLessThans we will now add a SCEV predicate associated with the guarded backedge taken count when the analyzed SCEV expression is not an AddRecExpr. Note that we only do this as an alternative to returning a 'CouldNotCompute'. We use new feature in Loop Access Analysis and LoopVectorize to analyze and transform more loops. Reviewers: anemet, mzolotukhin, hfinkel, sanjoy Subscribers: flyingforyou, mcrosier, atrick, mssimpso, sanjoy, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D17201 llvm-svn: 265535
2016-03-21[IndVars] Fix PR26974: make sure replaceCongruentIVs doesn't break LCSSASilviu Baranga1-0/+1
Summary: replaceCongruentIVs can break LCSSA when trying to replace IV increments since it tries to replace all uses of a phi node with another phi node while both of the phi nodes are not necessarily in the processed loop. This will cause an assert in IndVars. To fix this, we add a check to make sure that the replacement maintains LCSSA. Reviewers: sanjoy Subscribers: mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D18266 llvm-svn: 263941
2016-02-21ADT: Remove == and != comparisons between ilist iterators and pointersDuncan P. N. Exon Smith1-3/+3
I missed == and != when I removed implicit conversions between iterators and pointers in r252380 since they were defined outside ilist_iterator. Since they depend on getNodePtrUnchecked(), they indirectly rely on UB. This commit removes all uses of these operators. (I'll delete the operators themselves in a separate commit so that it can be easily reverted if necessary.) There should be NFC here. llvm-svn: 261498
generated by cgit v1.1 at 2025-10-04 15:31:24 +0000