summaryrefslogtreecommitdiffstats
path: root/polly/lib/Support/SCEVValidator.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Update to recent formatting changesTobias Grosser2017-02-011-3/+2
| | | | llvm-svn: 293756
* Adjust formatting to commit r292110 [NFC]Tobias Grosser2017-01-161-2/+3
| | | | llvm-svn: 292123
* Allow to disable unsigned operations (zext, icmp ugt, ...)Johannes Doerfert2016-12-021-2/+20
| | | | | | | Unsigned operations are often useful to support but the heuristics are not yet tuned. This options allows to disable them if necessary. llvm-svn: 288521
* SCEVValidator: reduce indentation to increase readability [NFC]Tobias Grosser2016-11-081-12/+17
| | | | llvm-svn: 286217
* Drop '@brief' from doxygen commentsTobias Grosser2016-09-021-17/+17
| | | | | | | | 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
* [SCEVValidator] Don't reorder multiplies in extractConstantFactor.Eli Friedman2016-08-181-5/+4
| | | | | | | | | | | The existing code would add the operands in the wrong order, and eventually crash because the SCEV expression doesn't exactly match the parameter SCEV expression in SCEVAffinator::visit. (SCEV doesn't sort the operands to getMulExpr in general.) Differential Revision: https://reviews.llvm.org/D23592 llvm-svn: 279087
* [ScopDetect] Do not assert in case of AddRecs with non-constant start expressionTobias Grosser2016-08-151-2/+1
| | | | llvm-svn: 278738
* Fix assertion due to buildMemoryAccess.Michael Kruse2016-07-081-2/+3
| | | | | | | | | | | | | For llvm the memory accesses from nonaffine loops should be visible, however for polly those nonaffine loops should be invisible/boxed. This fixes llvm.org/PR28245 Cointributed-by: Huihui Zhang <huihuiz@codeaurora.org> Differential Revision: http://reviews.llvm.org/D21591 llvm-svn: 274842
* clang-tidy: Add llvm namespace commentsTobias Grosser2016-06-231-2/+2
| | | | | | | | | | | | | | | | | | | | | | | llvm commonly adds a comment to the closing brace of a namespace to indicate which namespace is closed. clang-tidy provides with llvm-namespace-comment a handy tool to check for this habit. We use it to ensure we consitently use namespace comments in Polly. There are slightly different styles in how namespaces are closed in LLVM. As there is no large difference between the different comment styles we go for the style clang-tidy suggests by default. To reproduce this fix run: for i in `ls tools/polly/lib/*/*.cpp`; \ clang-tidy -checks='-*,llvm-namespace-comment' -p build $i -fix \ -header-filter=".*"; \ done This cleanup was suggested by Eugene Zelenko <eugene.zelenko@gmail.com> in http://reviews.llvm.org/D21488 and was split out to increase readability. llvm-svn: 273621
* 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
* 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
* [FIX] Do not recognize division by 0 as affineJohannes Doerfert2016-06-061-2/+2
| | | | llvm-svn: 271885
* Bring some comments up to date [NFC]Johannes Doerfert2016-05-121-8/+2
| | | | llvm-svn: 269301
* Support truncate operationsJohannes Doerfert2016-05-121-17/+1
| | | | | | | | | 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
* Handle llvm.assume inside the SCoPJohannes Doerfert2016-05-101-15/+14
| | | | | | | | | | The assumption attached to an llvm.assume in the SCoP needs to be combined with the domain of the surrounding statement but can nevertheless be used to refine the context. This fixes the problems mentioned in PR27067. llvm-svn: 269060
* Allow unsigned divisionsJohannes Doerfert2016-04-291-23/+34
| | | | | | | | | | | | | 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
* Extract some constant factors from "SCEVAddExprs"Johannes Doerfert2016-04-251-0/+26
| | | | | | | | | Additive expressions can have constant factors too that we can extract and thereby simplify the internal representation. For now we do compute the gcd of all constant factors but only extract the same (possibly negated) factor if there is one. llvm-svn: 267445
* Model zext-extend instructionsJohannes Doerfert2016-04-251-17/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Introduce a parameter set type [NFC]Johannes Doerfert2016-04-251-15/+11
| | | | llvm-svn: 267401
* Remove unnecessary argument of the SCEVValidator [NFC]Johannes Doerfert2016-04-251-15/+7
| | | | llvm-svn: 267400
* SCoPValidator: Use SCEVTraversal to simplify SCEVInRegionDependencesTobias Grosser2016-04-181-101/+33
| | | | llvm-svn: 266622
* Allow pointer expressions in SCEVs again.Johannes Doerfert2016-04-101-10/+2
| | | | | | | | | In r247147 we disabled pointer expressions because the IslExprBuilder did not fully support them. This patch reintroduces them by simply treating them as integers. The only special handling for pointers that is left detects the comparison of two address_of operands and uses an unsigned compare. llvm-svn: 265894
* [FIX] Do not recompute SCEVs but pass them to subfunctionsJohannes Doerfert2016-04-091-6/+3
| | | | | | | | | | | | This reverts commit 2879c53e80e05497f408f21ce470d122e9f90f94. Additionally, it adds SDiv and SRem instructions to the set of values discovered by the findValues function even if we add the operands to be able to recompute the SCEVs. In subfunctions we do not want to recompute SDiv and SRem instructions but pass them instead as they might have been created through the IslExprBuilder and are more complicated than simple SDiv/SRem instructions in the code. llvm-svn: 265873
* [FIX] Look through div & srem instructions in SCEVsJohannes Doerfert2016-04-081-5/+29
| | | | | | | | | The findValues() function did not look through div & srem instructions that were part of the argument SCEV. However, in different other places we already look through it. This mismatch caused us to preload values in the wrong order. llvm-svn: 265775
* [SCEVValidator] Fix loop exit values considered affine.Michael Kruse2016-03-031-1/+8
| | | | | | | | | | | | | | | | | | | | Index calculations can use the last value that come out of a loop. Ideally, ScalarEvolution can compute that exit value directly without depending on the loop induction variable, but not in all cases. This changes isAffine to not consider such loop exit values as affine to avoid that SCEVExpander adds uses of the original loop induction variable. This fix is analogous to r262404 that applies to general uses of loop exit values instead of index expressions and loop bouds as in this patch. This reduces the number of LNT test-suite fails with -polly-position=before-vectorizer -polly-unprofitable from 10 to 8. llvm-svn: 262665
* Pass scope and LoopInfo to SCEVValidator. NFC.Michael Kruse2016-03-031-16/+22
| | | | | | | | The scope will be required in the following fix. This commit separates the large changes that do not change behaviour from the small, but functional change. llvm-svn: 262664
* Fix non-synthesizable loop exit values.Michael Kruse2016-03-011-6/+22
| | | | | | | | | | | Polly recognizes affine loops that ScalarEvolution does not, in particular those with loop conditions that depend on hoisted invariant loads. Check for SCEVAddRec dependencies on such loops and do not consider their exit values as synthesizable because SCEVExpander would generate them as expressions that depend on the original induction variables. These are not available in generated code. llvm-svn: 262404
* [SCEVValidator] Remove redundant visit.Michael Kruse2016-03-011-3/+0
| | | | | | | SCEVAddRecExpr::getStart() is synonymous to SCEVAddRecExpr::getOperand(0) which will be visited in the following loop anyway. llvm-svn: 262375
* Separate more constant factors of parametersJohannes Doerfert2016-02-141-7/+23
| | | | | | | | | | | | | | | | | So far we separated constant factors from multiplications, however, only when they are at the outermost level of a parameter SCEV. Now, we also separate constant factors from the parameter SCEV if the outermost expression is a SCEVAddRecExpr. With the changes to the SCEVAffinator we can now improve the extractConstantFactor(...) function at will without worrying about any other code part. Thus, if needed we can implement a more comprehensive extractConstantFactor(...) function that will traverse the SCEV instead of looking only at the outermost level. Four test cases were affected. One did not change much and the other three were simplified. llvm-svn: 260859
* Use parameter constraints provided via llvm.assumeJohannes Doerfert2015-11-121-0/+38
| | | | | | | | | If an llvm.assume dominates the SCoP entry block and the assumed condition can be expressed as an affine inequality we will now add it to the context. Differential Revision: http://reviews.llvm.org/D14413 llvm-svn: 252851
* Allow invariant loads in the SCoP descriptionJohannes Doerfert2015-10-071-5/+20
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch allows invariant loads to be used in the SCoP description, e.g., as loop bounds, conditions or in memory access functions. First we collect "required invariant loads" during SCoP detection that would otherwise make an expression we care about non-affine. To this end a new level of abstraction was introduced before SCEVValidator::isAffineExpr() namely ScopDetection::isAffine() and ScopDetection::onlyValidRequiredInvariantLoads(). Here we can decide if we want a load inside the region to be optimistically assumed invariant or not. If we do, it will be marked as required and in the SCoP generation we bail if it is actually not invariant. If we don't it will be a non-affine expression as before. At the moment we optimistically assume all "hoistable" (namely non-loop-carried) loads to be invariant. This causes us to expand some SCoPs and dismiss them later but it also allows us to detect a lot we would dismiss directly if we would ask e.g., AliasAnalysis::canBasicBlockModify(). We also allow potential aliases between optimistically assumed invariant loads and other pointers as our runtime alias checks are sound in case the loads are actually invariant. Together with the invariant checks this combination allows to handle a lot more than LICM can. The code generation of the invariant loads had to be extended as we can now have dependences between parameters and invariant (hoisted) loads as well as the other way around, e.g., test/Isl/CodeGen/invariant_load_parameters_cyclic_dependence.ll First, it is important to note that we cannot have real cycles but only dependences from a hoisted load to a parameter and from another parameter to that hoisted load (and so on). To handle such cases we materialize llvm::Values for parameters that are referred by a hoisted load on demand and then materialize the remaining parameters. Second, there are new kinds of dependences between hoisted loads caused by the constraints on their execution. If a hoisted load is conditionally executed it might depend on the value of another hoisted load. To deal with such situations we sort them already in the ScopInfo such that they can be generated in the order they are listed in the Scop::InvariantAccesses list (see compareInvariantAccesses). The dependences between hoisted loads caused by indirect accesses are handled the same way as before. llvm-svn: 249607
* Revert r247278 "Disable support for modulo expressions"Johannes Doerfert2015-09-141-17/+11
| | | | | | | | This reverts commit 00c5b6ca8832439193036aadaaaee92a43236219. We can handle modulo expressions in the domain again. llvm-svn: 247542
* Disable support for modulo expressionsJohannes Doerfert2015-09-101-11/+17
| | | | | | | | | The support for modulo expressions is not comlete and makes the new domain generation harder. As the currently broken domain generation needs to be replaced, we will first swap in the new, fixed domain generation and make it compatible with the modulo expressions later. llvm-svn: 247278
* Disable support for pointer expressionsJohannes Doerfert2015-09-091-2/+10
| | | | | | | | The support for pointer expressions is broken as it can only handle some patterns in the IslExprBuilder. We should to treat pointers in expressions the same as integers at some point and revert this patch. llvm-svn: 247147
* Add support for srem instructionTobias Grosser2015-06-241-0/+16
| | | | | | | | | | | Remainder operations with constant divisor can be modeled as quasi-affine expression. This patch adds support for detecting and modeling them. We also add a test that ensures they are correctly code generated. This patch was extracted from a larger patch contributed by Johannes Doerfert in http://reviews.llvm.org/D5293 llvm-svn: 240518
* Sort include directivesTobias Grosser2015-05-091-2/+1
| | | | | | | | | | Upcoming revisions of isl require us to include header files explicitly, which have previously been already transitively included. Before we add them, we sort the existing includes. Thanks to Chandler for sort_includes.py. A simple, but very convenient script. llvm-svn: 236930
* [FIX] Invalid recognition of multidimensional accessJohannes Doerfert2015-05-031-0/+1
| | | | | | | | In the lnt benchmark MultiSource/Benchmarks/MallocBench/gs/gs with scalar and PHI modeling we detected the multidimensional accesses with sizes variant in the SCoP. This will check the sizes for validity. llvm-svn: 236395
* Use the original no-wrap flags for normalized AddRecsJohannes Doerfert2015-04-261-1/+1
| | | | llvm-svn: 235822
* Do not assume all multi-parameter products are affineTobias Grosser2015-04-051-1/+1
| | | | | | | | | | As soon as one operand of the product is invalid, the entire product is invalid. This happens for example if one of the operands is not loop-invariant. This fixes http://llvm.org/PR23125 Reported-by: Jeremy Huddleston Sequoia <jeremyhu@apple.com llvm-svn: 234119
* Strip constant factors from SCoP parametersJohannes Doerfert2015-03-291-0/+19
| | | | | | | | This will strip the constant factor of a parameter befor we add it to the SCoP. As a result the access functions are simplified, e.g., for the attached test case. llvm-svn: 233501
* Change argument "class" keyword to "const"Johannes Doerfert2015-02-261-2/+2
| | | | llvm-svn: 230666
* Allow signed devision in access functionsJohannes Doerfert2015-02-111-7/+33
| | | | llvm-svn: 228833
* [FIX] Activated a pointer test and removed obsolete commentJohannes Doerfert2015-01-301-7/+0
| | | | llvm-svn: 227524
* Add support for pointer types in expressionsTobias Grosser2015-01-081-2/+2
| | | | llvm-svn: 225464
* Add OpenMP code generation to isl backendTobias Grosser2014-11-151-0/+42
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This backend supports besides the classical code generation the upcoming SCEV based code generation (which the existing CLooG backend does not support robustly). OpenMP code generation in the isl backend benefits from our run-time alias checks such that the set of loops that can possibly be parallelized is a lot larger. The code was tested on LNT. We do not regress on builds without -polly-parallel. When using -polly-parallel most tests work flawlessly, but a few issues still remain and will be addressed in follow up commits. SCEV/non-SCEV codegen: - Compile time failure in ldecod and TimberWolfMC due a problem in our run-time alias check generation triggered by pointers that escape through the OpenMP subfunction (OpenMP specific). - Several execution time failures. Due to the larger set of loops that we now parallelize (compared to the classical code generation), we currently run into some timeouts in tests with a lot loops that have a low trip count and are slowed down by parallelizing them. SCEV only: - One existing failure in lencod due to llvm.org/PR21204 (not OpenMP specific) OpenMP code generation is the last feature that was only available in the CLooG backend. With the isl backend being the only one supporting features such as run-time alias checks and delinearization, we will soon switch to use the isl ast generator by the default and subsequently remove our dependency on CLooG. http://reviews.llvm.org/D5517 llvm-svn: 222088
* Use braces in multi-statement DEBUG() code [NFC]Tobias Grosser2014-10-221-3/+11
| | | | | | | | | | | | | | | | | | By adding braces into the DEBUG statement we can make clang-format format code such as: DEBUG(stmt1(); stmt2()) as multi-line code: DEBUG({ stmt1(); stmt2(); }); This makes control-flow in debug statements easier to read. llvm-svn: 220441
* Revert "Added support for modulo expressions"Tobias Grosser2014-08-161-49/+4
| | | | | | | | | | | | This reverts commit 215684. The intention of the commit is great, but unfortunately it seems to be the cause of 14 LNT test suite failures: http://lab.llvm.org:8011/builders/perf-x86_64-penryn-O3-polly/builds/116 To make our buildbots and performance testers green until this issue is solved, we temporarily revert this commit. llvm-svn: 215816
* Added support for modulo expressionsJohannes Doerfert2014-08-151-4/+49
| | | | | | | | | | | The support is limited to signed modulo access and condition expressions with a constant right hand side, e.g., A[i % 2] or A[i % 9]. Test cases are modified according to this new feature and new test cases are added. Differential Revision: http://reviews.llvm.org/D4843 llvm-svn: 215684
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-3/+3
| | | | | | | | | | definition below all of the header #include lines, Polly edition. If you want to know more details about this, you can see the recent commits to Debug.h in LLVM. This is just the Polly segment of a cleanup I'm doing globally for this macro. llvm-svn: 206852
OpenPOWER on IntegriCloud