summaryrefslogtreecommitdiffstats
path: root/polly/lib/Support/SCEVAffinator.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [polly][SCEV] Expand SCEV matcher cases for new smin/umin opsKeno Fischer2019-05-081-0/+16
| | | | | | | These were added in rL360159, but I neglected to update polly at the same time. llvm-svn: 360238
* Apply include-what-you-use #include removal suggestions. NFC.Michael Kruse2019-03-281-1/+0
| | | | | | | | | | | | This removes unused includes (and forward declarations) as suggested by include-what-you-use. If a transitive include of a removed include is required to compile a file, I added the required header (or forward declaration if suggested by include-what-you-use). This should reduce compilation time and reduce the number of iterative recompilations when a header was changed. llvm-svn: 357209
* Update the file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-191-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
* Update isl-cpp bindingsTobias Grosser2018-08-091-1/+1
| | | | | | | | | We upstreamed the export of isl_val_2exp, to the official cpp bindings. In this process, we concluded that pow2 is a better and more widely used name for this functionality. Hence, both the official isl-cpp bindings and our derived variant use now the term pow2. llvm-svn: 339312
* [SCEVAffinator] BB can be null; don't use it to get the LLVMContext.Eli Friedman2018-05-181-1/+1
| | | | | | Fixes post-commit review comment on r332309. llvm-svn: 332775
* [SCEVAffinator] Fix handling of pwaff complexity limit.Eli Friedman2018-05-141-3/+11
| | | | | | | | | | | nullptr is not a valid affine expression, and none of the callers check for null, so we eventually hit an isl error and crash. Instead, invalidate the scop and return a constant zero. Differential Revision: https://reviews.llvm.org/D46445 llvm-svn: 332309
* Remove another set or release() callsTobias Grosser2018-04-291-6/+6
| | | | llvm-svn: 331129
* Remove the last uses of isl::give and isl::takeTobias Grosser2018-04-291-1/+1
| | | | llvm-svn: 331126
* Revert r327216 'Add isl operator overloads for isl::pw_aff'Tobias Grosser2018-04-111-1/+0
| | | | | | This commit requires further discussions. llvm-svn: 329825
* Revert untested changes in SCEVAffinatorTobias Grosser2018-03-101-1/+1
| | | | llvm-svn: 327221
* Add isl operator overloads for isl::pw_affTobias Grosser2018-03-101-1/+3
| | | | | | | | | | | | Piecewise affine expressions have directly corresponding mathematical operators. Introduce these operators as overloads as this makes writing code with isl::pw_aff expressions more directly readable. We can now write: A = B + C instead of A = B.add(C) llvm-svn: 327216
* Use isl::manage_copy to simplify calls to isl::manage(isl_.._copy())Tobias Grosser2018-02-201-2/+1
| | | | | | | | | | | As part of this cleanup a couple of unnecessary isl::manage(obj.copy()) pattern are eliminated as well. We checked for all potential cleanups by scanning for: "grep -R isl::manage\( lib/ | grep copy" llvm-svn: 325558
* [NFC] Fix formattingPhilip Pfaffe2017-12-061-4/+2
| | | | llvm-svn: 319973
* Port SCEVAffinator to the isl c++ bindingsPhilip Pfaffe2017-12-061-107/+79
| | | | | | | | | | | | | | Summary: Straight forward port of SCEVAffinator Reviewers: grosser, bollu, Meinersbur Reviewed By: Meinersbur Subscribers: pollydev, llvm-commits Differential Revision: https://reviews.llvm.org/D40803 llvm-svn: 319958
* Run polly-update-format. NFC.Michael Kruse2017-11-211-3/+6
| | | | | | | polly-check-format has been failing since at least r318517, due to more than one cause. llvm-svn: 318795
* Port ScopInfo to the isl cpp bindingsPhilip Pfaffe2017-11-191-4/+4
| | | | | | | | | | | | | | | | | | | | | Summary: Most changes are mechanical, but in one place I changed the program semantics by fixing a likely bug: In `Scop::hasFeasibleRuntimeContext()`, I'm now explicitely handling the error-case. Before, when the call to `addNonEmptyDomainConstraints()` returned a null set, this (probably) accidentally worked because isl_bool_error converts to true. I'm checking for nullptr now. Reviewers: grosser, Meinersbur, bollu Reviewed By: Meinersbur Subscribers: nemanjai, kbarton, pollydev, llvm-commits Differential Revision: https://reviews.llvm.org/D39971 llvm-svn: 318632
* [ScopInfo] Move Scop::getPwAffOnly to isl++ [NFC]Tobias Grosser2017-08-061-1/+1
| | | | llvm-svn: 310231
* [ScopInfo] Translate Scop::getIdForParam to isl++ [NFC]Tobias Grosser2017-08-061-1/+1
| | | | llvm-svn: 310220
* [SCEVAffinator] Do not scan redundantly for parametersTobias Grosser2016-11-131-3/+0
| | | | | | | | | | | | | | | | | | | | In r286430 "SCEVValidator: add new parameters resulting from constant extraction" we added functionality to scan for parameters after constant extraction has taken place to ensure newly created parameters are correctly registered. This addition made the already existing registration of parameters redundant. Hence, we remove the corresponding call in this commit. An alternative solution would have been to also perform constant extraction when validating SCEV expressions and to then scan for parameters when validating a SCEV expression. However, as SCEV validation is used during SCoP detection where we want to be especially fast, adding additional functionality on this hot path should be avoided if good alternatives exist. In this case, we can choose to continue to only transform SCEV expression when actually modeling them. As all transformations we perform are expected to not change the validity of the SCEV expressions, this solution seems preferable. Suggested-by: Eli Friedman <efriedma@codeaurora.org> llvm-svn: 286780
* SCEVAffinator: pass parameter-only set to addRestriction if BB=nullptrTobias Grosser2016-11-101-0/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | Assumptions can either be added for a given basic block, in which case the set describing the assumptions is expected to match the dimensions of its domain. In case no basic block is provided a parameter-only set is expected to describe the assumption. The piecewise expressions that are generated by the SCEVAffinator sometimes have a zero-dimensional domain (e.g., [p] -> { [] : p <= -129 or p >= 128 }), which looks similar to a parameter-only domain, but is still a set domain. This change adds an assert that checks that we always pass parameter domains to addAssumptions if BB is empty to make mismatches here fail early. We also change visitTruncExpr to always convert to parameter sets, if BB is null. This change resolves http://llvm.org/PR30941 Another alternative to this change would have been to inspect all code to make sure we directly generate in the SCEV affinator parameter sets in case of empty domains. However, this would likely complicate the code which combines parameter and non-parameter domains when constructing a statement domain. We might still consider doing this at some point, but as this likely requires several non-local changes this should probably be done as a separate refactoring. Reported-by: Eli Friedman <efriedma@codeaurora.org> llvm-svn: 286444
* SCEVValidator: add new parameters resulting from constant extractionTobias Grosser2016-11-101-0/+3
| | | | | | | | | | | | | | | | | When extracting constant expressions out of SCEVs, new parameters may be introduced, which have not been registered before. This change scans SCEV expressions after constant extraction again to make sure newly introduced parameters are registered. We may for example extract the constant '8' from the expression '((8 * ((%a * %b) + %c)) + (-8 * %a))' and obtain the expression '(((-1 + %b) * %a) + %c)'. The new expression has a new parameter '(-1 + %b) * %a)', which was not registered before, but must be registered to not crash. This closes http://llvm.org/PR30953 Reported-by: Eli Friedman <efriedma@codeaurora.org> llvm-svn: 286430
* [SCEVAffinator] Make precise modular math more correct.Eli Friedman2016-10-211-55/+25
| | | | | | | | | | | | | | | | | | | | | | | | | | | Integer math in LLVM IR is modular. Integer math in isl is arbitrary-precision. Modeling LLVM IR math correctly in isl requires either adding assumptions that math doesn't actually overflow, or explicitly wrapping the math. However, expressions with the "nsw" flag are special; we can pretend they're arbitrary-precision because it's undefined behavior if the result wraps. SCEV expressions based on IR instructions with an nsw flag also carry an nsw flag (roughly; actually, the real rule is a bit more complicated, but the details don't matter here). Before this patch, SCEV flags were also overloaded with an additional function: the ZExt code was mutating SCEV expressions as a hack to indicate to checkForWrapping that we don't need to add assumptions to the operand of a ZExt; it'll add explicit wrapping itself. This kind of works... the problem is that if anything else ever touches that SCEV expression, it'll get confused by the incorrect flags. Instead, with this patch, we make the decision about whether to explicitly wrap the math a bit earlier, basing the decision purely on the SCEV expression itself, and not its users. Differential Revision: https://reviews.llvm.org/D25287 llvm-svn: 284848
* SCEVAffinator: Add missing __isl_take annotationsTobias Grosser2016-09-081-1/+2
| | | | llvm-svn: 280943
* Drop '@brief' from doxygen commentsTobias Grosser2016-09-021-8/+8
| | | | | | | | LLVM's coding guideline suggests to not use @brief for one-sentence doxygen comments to improve readability. Switch this once and for all to ensure people do not copy @brief comments from other parts of Polly, when writing new code. llvm-svn: 280468
* [SCEVAffinator] Fix assertion checking for constant divisor.Michael Kruse2016-07-121-1/+1
| | | | | | | | | | | An assertion in visitSDivInstruction() checked whether the divisor is constant by checking whether the argument is a ConstantInt. However, SCEVValidator allows the divisor to be simplified to a constant by ScalarEvolution. We synchronize the implementation of SCEVValidator and SCEVAffinator to both accept simplified SCEV expressions. llvm-svn: 275174
* Recommit: "Look through IntToPtr & PtrToInt instructions"Tobias Grosser2016-06-111-0/+4
| | | | | | | | | | | | | IntToPtr and PtrToInt instructions are basically no-ops that we can handle as such. In order to generate them properly as parameters we had to improve the ScopExpander, though the change is the first in the direction of a more aggressive scalar synthetization. This patch was originally contributed by Johannes Doerfert in r271888, but was in conflict with the revert in r272483. This is a recommit with some minor adjustment to the test cases to take care of differing instruction names. llvm-svn: 272485
* This reverts recent expression type changesTobias Grosser2016-06-111-4/+0
| | | | | | | | | | | | | | | | | | | | | The recent expression type changes still need more discussion, which will happen on phabricator or on the mailing list. The precise list of commits reverted are: - "Refactor division generation code" - "[NFC] Generate runtime checks after the SCoP" - "[FIX] Determine insertion point during SCEV expansion" - "Look through IntToPtr & PtrToInt instructions" - "Use minimal types for generated expressions" - "Temporarily promote values to i64 again" - "[NFC] Avoid unnecessary comparison for min/max expressions" - "[Polly] Fix -Wunused-variable warnings (NFC)" - "[NFC] Simplify min/max expression generation" - "Simplify the type adjustment in the IslExprBuilder" Some of them are just reverted as we would otherwise get conflicts. I will try to re-commit them if possible. llvm-svn: 272483
* [FIX] Model the rounding behaviour of SRem correctlyJohannes Doerfert2016-06-071-8/+8
| | | | llvm-svn: 272001
* Look through IntToPtr & PtrToInt instructionsJohannes Doerfert2016-06-061-0/+4
| | | | | | | | | IntToPtr and PtrToInt instructions are basically no-ops that we can handle as such. In order to generate them properly as parameters we had to improve the ScopExpander, though the change is the first in the direction of a more aggressive scalar synthetization. llvm-svn: 271888
* Replace getSCEV with getSCEVAtScopeJohannes Doerfert2016-06-061-4/+7
| | | | llvm-svn: 271881
* [NFC] Use the ScalarEvolution member of the SCEVAffinatorJohannes Doerfert2016-06-061-7/+4
| | | | llvm-svn: 271880
* [NFC] Coalesce invariant context sets earlyJohannes Doerfert2016-06-061-0/+2
| | | | llvm-svn: 271879
* [FIX] Correctly translate i1 expressionsJohannes Doerfert2016-06-021-1/+2
| | | | llvm-svn: 271534
* Add and use Scop::contains(Loop/BasicBlock/Instruction) [NFC]Johannes Doerfert2016-05-231-1/+1
| | | | llvm-svn: 270424
* Directly access information through the Scop class [NFC]Johannes Doerfert2016-05-231-3/+3
| | | | llvm-svn: 270421
* Support truncate operationsJohannes Doerfert2016-05-121-3/+36
| | | | | | | | | Truncate operations are basically modulo operations, thus we can model them that way. However, for large types we assume the operand to fit in the new type size instead of introducing a modulo with a very large constant. llvm-svn: 269300
* Expose interpretAsUnsigned in the SCEVAffinator [NFC]Johannes Doerfert2016-05-101-6/+11
| | | | | | | | This exposes the functionality to interpret a SCEV, or better the piece-wise function created from the SCEV, as an unsigned value instead of a signed one. llvm-svn: 269044
* Rename Conjuncts -> Disjunctions. NFC.Michael Kruse2016-05-021-2/+2
| | | | | | | | The check for complexity compares the number of polyhedra in a set, which are combined by disjunctions (union, "OR"), not conjunctions (intersection, "AND"). llvm-svn: 268223
* Typo: isToComplex -> isTooComplex. NFC.Michael Kruse2016-05-021-5/+5
| | | | llvm-svn: 268220
* Allow unsigned divisionsJohannes Doerfert2016-04-291-4/+38
| | | | | | | | | | | | | After zero-extend operations and unsigned comparisons we now allow unsigned divisions. The handling is basically the same as for signed division, except the interpretation of the operands. As the divisor has to be constant in both cases we can simply interpret it as an unsigned value without additional complexity in the representation. For the dividend we could choose from the different representation schemes introduced for zero-extend operations but for now we will simply use an assumption. llvm-svn: 268032
* Refactor SCEVAffinator [NFC]Johannes Doerfert2016-04-291-14/+12
| | | | llvm-svn: 268031
* [FIX] Unsigned comparisons change invalid domainJohannes Doerfert2016-04-291-8/+10
| | | | | | | | | It does not suffice to take a global assumptions for unsigned comparisons but we also need to adjust the invalid domain of the statements guarded by such an assumption. To this end we allow to specialize the getPwAff call now in order to indicate unsigned interpretation. llvm-svn: 268025
* [FIX] Adjust assumption space for zext instructionsJohannes Doerfert2016-04-261-1/+2
| | | | llvm-svn: 267552
* Do not add but record signed-unsigned assumptionsJohannes Doerfert2016-04-261-1/+1
| | | | llvm-svn: 267528
* Model zext-extend instructionsJohannes Doerfert2016-04-251-4/+116
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | A zero-extended value can be interpreted as a piecewise defined signed value. If the value was non-negative it stays the same, otherwise it is the sum of the original value and 2^n where n is the bit-width of the original (or operand) type. Examples: zext i8 127 to i32 -> { [127] } zext i8 -1 to i32 -> { [256 + (-1)] } = { [255] } zext i8 %v to i32 -> [v] -> { [v] | v >= 0; [256 + v] | v < 0 } However, LLVM/Scalar Evolution uses zero-extend (potentially lead by a truncate) to represent some forms of modulo computation. The left-hand side of the condition in the code below would result in the SCEV "zext i1 <false, +, true>for.body" which is just another description of the C expression "i & 1 != 0" or, equivalently, "i % 2 != 0". for (i = 0; i < N; i++) if (i & 1 != 0 /* == i % 2 */) /* do something */ If we do not make the modulo explicit but only use the mechanism described above we will get the very restrictive assumption "N < 3", because for all values of N >= 3 the SCEVAddRecExpr operand of the zero-extend would wrap. Alternatively, we can make the modulo in the operand explicit in the resulting piecewise function and thereby avoid the assumption on N. For the example this would result in the following piecewise affine function: { [i0] -> [(1)] : 2*floor((-1 + i0)/2) = -1 + i0; [i0] -> [(0)] : 2*floor((i0)/2) = i0 } To this end we can first determine if the (immediate) operand of the zero-extend can wrap and, in case it might, we will use explicit modulo semantic to compute the result instead of emitting non-wrapping assumptions. Note that operands with large bit-widths are less likely to be negative because it would result in a very large access offset or loop bound after the zero-extend. To this end one can optimistically assume the operand to be positive and avoid the piecewise definition if the bit-width is bigger than some threshold (here MaxZextSmallBitWidth). We choose to go with a hybrid solution of all modeling techniques described above. For small bit-widths (up to MaxZextSmallBitWidth) we will model the wrapping explicitly and use a piecewise defined function. However, if the bit-width is bigger than MaxZextSmallBitWidth we will employ overflow assumptions and assume the "former negative" piece will not exist. llvm-svn: 267408
* Translate SCEVs to isl_pw_aff and their invalid domainJohannes Doerfert2016-04-231-64/+89
| | | | | | | | | | | | | The SCEVAffinator will now produce not only the isl representaiton of a SCEV but also the domain under which it is invalid. This is used to record possible overflows that can happen in the statement domains in the statements invalid domain. The result is that invalid loads have an accurate execution contexts with regards to the validity of their statements domain. While the SCEVAffinator currently is only taking "no-wrapping" assumptions, we can add more withouth worrying about the execution context of loads that are optimistically hoisted. llvm-svn: 267288
* Record wrapping assumptions earlyJohannes Doerfert2016-04-121-39/+22
| | | | | | | | Utilizing the record option for assumptions we can simplify the wrapping assumption generation a lot. Additionally, we can now report locations together with wrapping assumptions, though they might not be accurate yet. llvm-svn: 266069
* Simplify SCEVAffinator code [NFC]Johannes Doerfert2016-04-121-15/+8
| | | | llvm-svn: 266051
* [FIX] Handle multiplications in the SCEVAffinator againJohannes Doerfert2016-04-081-1/+10
| | | | | | | | | | | If ScalarEvolution cannot look through some expression but we do, it might happen that a multiplication will arrive at the SCEVAffinator::visitMulExpr. While we could always try to improve the extractConstantFactor function we might still miss something, thus we reintroduce the code to generate multiplicative piecewise-affine functions as a fall-back. llvm-svn: 265777
* Generalize the domain complexity restrictionsJohannes Doerfert2016-03-261-0/+31
| | | | | | | | | | | | | | | | | | This patch applies the restrictions on the number of domain conjuncts also to the domain parts of piecewise affine expressions we generate. To this end the wording is change slightly. It was needed to support complex additions featuring zext-instructions but it also fixes PR27045. lnt profitable runs reports only little changes that might be noise: Compile Time: Polybench/[...]/2mm +4.34% SingleSource/[...]/stepanov_container -2.43% Execution Time: External/[...]/186_crafty -2.32% External/[...]/188_ammp -1.89% External/[...]/473_astar -1.87% llvm-svn: 264514
OpenPOWER on IntegriCloud