summaryrefslogtreecommitdiffstats
path: root/polly/test/Isl/CodeGen
Commit message (Collapse)AuthorAgeFilesLines
...
* Extend the jscop interface to allow the user to declare new arrays and to ↵Roman Gareev2016-07-303-0/+165
| | | | | | | | | | | | | | | | reference these arrays from access expressions Extend the jscop interface to allow the user to export arrays. It is required that already existing arrays of the list of arrays correspond to arrays of the SCoP. Each array that is appended to the list will be newly created. Furthermore, we allow the user to modify access expressions to reference any array in case it has the same element type. Reviewed-by: Tobias Grosser <tobias@grosser.es> Differential Revision: https://reviews.llvm.org/D22828 llvm-svn: 277263
* tests: make test cases more robust using regexpTobias Grosser2016-07-212-5/+5
| | | | llvm-svn: 276262
* tests: fix order of memory accesses to ensure import succeedsTobias Grosser2016-07-213-20/+28
| | | | | | | | | | | It seems the order in which we generated memory accesses changed such that the import of these updated memory accesses failed for the 'loop3' statement in this test case. Unfortunately, the existing CHECK lines were not strict enough to catch this. Hence, besides fixing the order of the memory access lines we also ensure that the memory access changes are both clearly visibly and well checked. llvm-svn: 276247
* test: Drop unnecessary -polly-code-generator=isl flagTobias Grosser2016-07-061-2/+2
| | | | | | | isl is already the default code generator since we switched from CLooG several years ago. llvm-svn: 274609
* Ensure parameter names are isl-compatibleTobias Grosser2016-07-011-1/+1
| | | | | | | Without this change it is not possible for isl to parse the resulting objects from their string representation. llvm-svn: 274350
* Update isl to isl-0.17.1-57-g1879898Tobias Grosser2016-06-123-17/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | With this update the isl AST generation extracts disjunctive constraints early on. As a result, code that previously resulted in two branches with (close-to) identical code within them: if (P <= -1) { for (int c0 = 0; c0 < N; c0 += 1) Stmt_store(c0); } else if (P >= 1) for (int c0 = 0; c0 < N; c0 += 1) Stmt_store(c0); results now in only a single branch body: if (P <= -1 || P >= 1) for (int c0 = 0; c0 < N; c0 += 1) Stmt_store(c0); This resolves http://llvm.org/PR27559 Besides the above change, this isl update brings better simplification of sets/maps containing existentially quantified dimensions and fixes a bug in isl's coalescing. llvm-svn: 272500
* Expand test cases affected by next commitTobias Grosser2016-06-123-22/+24
| | | | | | | | | As these test cases will be changed in a subsequent commit, we expand and tighten them to make the subsequent changes to them more obvious. As part of this we add more context to some test cases and add CHECK-NEXT lines to ensure no intermediate lines are missed by accident. llvm-svn: 272499
* Recommit: "[FIX] Determine insertion point during SCEV expansion"Tobias Grosser2016-06-111-0/+43
| | | | | | | This patch was originally contributed by Johannes Doerfert in r271892, but was in conflict with the revert in r272483. llvm-svn: 272486
* Recommit: "Look through IntToPtr & PtrToInt instructions"Tobias Grosser2016-06-112-3/+36
| | | | | | | | | | | | | 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-1147-369/+272
| | | | | | | | | | | | | | | | | | | | | 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
* Refactor division generation codeJohannes Doerfert2016-06-062-11/+20
| | | | | | | | | This patch refactors the code generation for divisions. This allows to always generate a shift for a power-of-two division and to utilize information about constant divisors in order to truncate the result type. llvm-svn: 271898
* [NFC] Generate runtime checks after the SCoPJohannes Doerfert2016-06-064-28/+28
| | | | | | | | | We now generate runtime checks __after__ the SCoP code generation and not before, though they are still inserted at the same position int the code. This allows to modify the runtime check during SCoP code generation. llvm-svn: 271894
* [FIX] Determine insertion point during SCEV expansionJohannes Doerfert2016-06-061-0/+43
| | | | llvm-svn: 271892
* Look through IntToPtr & PtrToInt instructionsJohannes Doerfert2016-06-062-3/+36
| | | | | | | | | 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
* Use minimal types for generated expressionsJohannes Doerfert2016-06-0643-249/+261
| | | | | | | | | | | | We now use the minimal necessary bit width for the generated code. If operations might overflow (add/sub/mul) we will try to adjust the types in order to ensure a non-wrapping computation. If the type adjustment is not possible, thus the necessary type is bigger than the type value of --polly-max-expr-bit-width, we will use assumptions to verify the computation will not wrap. However, for run-time checks we cannot build assumptions but instead utilize overflow tracking intrinsics. llvm-svn: 271878
* Fix modulo compared to zero.Michael Kruse2016-06-031-0/+48
| | | | | | | | | | | | | | | | In case of modulo compared to zero, we need to do signed modulo operation as unsigned can give different results based on whether the dividend is negative or not. This addresses llvm.org/PR27707 Contributed-by: Chris Jenneisch <chrisj@codeaurora.org> Reviewers: _jdoerfert, grosser, Meinersbur Differential Revision: http://reviews.llvm.org/D20145 llvm-svn: 271707
* Temporarily promote values to i64 againJohannes Doerfert2016-06-022-45/+51
| | | | | | | Operands of binary operations that might overflow will be temporarily promoted to i64 again, though that is not a sound solution for the problem. llvm-svn: 271538
* Simplify the type adjustment in the IslExprBuilderJohannes Doerfert2016-06-022-51/+45
| | | | | | | | | We now have a simple function to adjust/unify the types of two (or three) operands before an operation that requieres the same type for all operands. Due to this change we will not promote parameters that are added to i64 anymore if that is not needed. llvm-svn: 271513
* [FIX] Require base pointers of loads that might alias to be hoistedJohannes Doerfert2016-05-231-0/+48
| | | | | | | | | | | Since the base pointer of a possibly aliasing pointer might not alias with any other pointer it (the base pointer) might not be tagged as "required invariant". However, we need it do be in order to compare the accessed addresses of the derived (possibly aliasing) pointer. This patch also tries to clean up the load hoisting a little bit. llvm-svn: 270412
* [FIX] Let ScalarEvolution forget hoisted valuesJohannes Doerfert2016-05-231-0/+59
| | | | | | | We have to rethink the handling of escaping values in order to make this kind of "fixes" go away. llvm-svn: 270409
* [FIX] Synthezise Sdiv/Srem/Udiv instructions correctly.Johannes Doerfert2016-05-232-9/+67
| | | | | | | This patch simplifies the Sdiv/Srem/Udiv expansion and thereby prevents errors, e.g., regarding the insertion point. llvm-svn: 270408
* Support truncate operationsJohannes Doerfert2016-05-121-2/+0
| | | | | | | | | 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
* Check overflows in RTCs and bail accordinglyJohannes Doerfert2016-05-127-38/+179
| | | | | | | | | | | | | | | We utilize assumptions on the input to model IR in polyhedral world. To verify these assumptions we version the code and guard it with a runtime-check (RTC). However, since the RTCs are themselves generated from the polyhedral representation we generate them under the same assumptions that they should verify. In other words, the guarantees that we try to provide with the RTCs do not hold for the RTCs themselves. To this end it is necessary to employ a different check for the RTCs that will verify the assumptions did hold for them too. Differential Revision: http://reviews.llvm.org/D20165 llvm-svn: 269299
* Refactor simplifySCoP [NFC]Johannes Doerfert2016-05-101-0/+31
| | | | | | | Remove obsolete code and decrease the indention in the Scop::simplifySCoP() function. llvm-svn: 269049
* Codegen: Enable the detection of min/max expressionsTobias Grosser2016-05-071-6/+4
| | | | | | | | | Min/max expressions are easier to read and can in some cases also result in more concise IR that is generated as the min/max --- when lowered to a cmp+select pattern -- commonly has a simpler condition then the ternary condition isl would normally generate. llvm-svn: 268855
* test: Use CHECK-NEXT to not miss instructions in test outputTobias Grosser2016-05-071-25/+23
| | | | llvm-svn: 268854
* Allow unsigned divisionsJohannes Doerfert2016-04-291-14/+7
| | | | | | | | | | | | | 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
* [FIX] Prevent division/modulo by zero in parameters -- test caseJohannes Doerfert2016-04-291-0/+56
| | | | | | This commits a test case for r268023. llvm-svn: 268026
* test: Make test case independent of earlier instructionsTobias Grosser2016-04-281-5/+5
| | | | | | | Instead of matching for %6, we use a regexp to match for the result strings. This test case caused unrelated noise in http://reviews.llvm.org/D15722. llvm-svn: 267875
* [FIX] Propagate execution domain of invariant loadsJohannes Doerfert2016-04-271-0/+73
| | | | | | | | | | | If the base pointer of an invariant load is is loaded conditionally, that condition needs to hold for the invariant load too. The structure of the program will imply this for domain constraints but not for imprecisions in the modeling. To this end we will propagate the execution context of base pointers during code generation and thus ensure the derived pointer does not access an invalid base pointer. llvm-svn: 267707
* Model zext-extend instructionsJohannes Doerfert2016-04-253-9/+19
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Check only loop control of loops that are part of the regionJohannes Doerfert2016-04-251-0/+33
| | | | | | | This also removes a duplicated line of code in the region generator that caused a SPEC benchmark to fail with the new SCoPs. llvm-svn: 267404
* Update two more test cases for r266445+r266446 IITobias Grosser2016-04-152-4/+3
| | | | llvm-svn: 266475
* Update two more test cases for r266445+r266446Tobias Grosser2016-04-151-3/+2
| | | | llvm-svn: 266474
* [Polly] Remove unwanted --check-prefix=CHECK from unit tests. NFC.Mandeep Singh Grang2016-04-151-1/+1
| | | | | | | | | | | | | | | | | Summary: Removed unwanted --check-prefix=CHECK from the following unit tests: DeadCodeElimination/dead_iteration_elimination.ll Isl/CodeGen/simple_vec_cast.ll Patch by: Mandeep Singh Grang (mgrang) Reviewers: jdoerfert, zinob, spop, grosser Projects: #polly Differential Revision: http://reviews.llvm.org/D19143 llvm-svn: 266411
* Allow pointer expressions in SCEVs again.Johannes Doerfert2016-04-109-54/+54
| | | | | | | | | 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 allow select as a base pointer in the SCoP regionJohannes Doerfert2016-04-091-0/+65
| | | | llvm-svn: 265884
* [FIX] Do not recompute SCEVs but pass them to subfunctionsJohannes Doerfert2016-04-091-3/+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] Teach the ScopExpander about parallel subfunctionsJohannes Doerfert2016-04-081-0/+44
| | | | llvm-svn: 265824
* [FIX] Allow to lookup domains for non-affine subregion blocksJohannes Doerfert2016-04-081-0/+73
| | | | llvm-svn: 265779
* [FIX] Look through div & srem instructions in SCEVsJohannes Doerfert2016-04-081-0/+51
| | | | | | | | | 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
* [FIX] Ensure SAI objects for exit PHIsJohannes Doerfert2016-04-051-1/+1
| | | | | | | | | | | | | If all exiting blocks of a SCoP are error blocks and therefor not represented we will not generate accesses and consequently no SAI objects for exit PHIs. However, they are needed in the code generation to generate the merge PHIs between the original and optimized region. With this patch we enusre that the SAI objects for exit PHIs exist even if all exiting blocks turn out to be eror blocks. This fixes the crash reported in PR27207. llvm-svn: 265393
* Exploit graph properties during domain generationJohannes Doerfert2016-04-041-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | As a CFG is often structured we can simplify the steps performed during domain generation. When we push domain information we can utilize the information from a block A to build the domain of a block B, if A dominates B and there is no loop backede on a path from A to B. When we pull domain information we can use information from a block A to build the domain of a block B if B post-dominates A. This patch implements both ideas and thereby simplifies domains that were not simplified by isl. For the FINAL basic block in test/ScopInfo/complex-successor-structure-3.ll we used to build a universe set with 81 basic sets. Now it actually is represented as universe set. While the initial idea to utilize the graph structure depended on the dominator and post-dominator tree we can use the available region information as a coarse grained replacement. To this end we push the region entry domain to the region exit and pull it from the region entry for the region exit if applicable. With this patch we now successfully compile External/SPEC/CINT2006/400_perlbench/400_perlbench and SingleSource/Benchmarks/Adobe-C++/loop_unroll. Differential Revision: http://reviews.llvm.org/D18450 llvm-svn: 265285
* [FIX] Adjust the insert point for non-affine region PHIsJohannes Doerfert2016-04-011-0/+50
| | | | | | | | | | If a non-affine region PHI is generated we should not move the insert point prior to the synthezised value in the same block as we might split that block at the insert point later on. Only if the incoming value should be placed in a different block we should change the insertion point. llvm-svn: 265132
* Revert 264782 and 264789Tobias Grosser2016-03-301-1/+1
| | | | | | | | | | | | | | | | | | | These caused LNT failures due to new assertions when running with -polly-position=before-vectorizer -polly-process-unprofitable for: FAIL: clamscan.compile_time FAIL: cjpeg.compile_time FAIL: consumer-jpeg.compile_time FAIL: shapes.compile_time FAIL: clamscan.execution_time FAIL: cjpeg.execution_time FAIL: consumer-jpeg.execution_time FAIL: shapes.execution_time The failures have been introduced by r264782, but r264789 had to be reverted as it depended on the earlier patch. llvm-svn: 264885
* Exploit graph properties during domain generationJohannes Doerfert2016-03-291-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | As a CFG is often structured we can simplify the steps performed during domain generation. When we push domain information we can utilize the information from a block A to build the domain of a block B, if A dominates B. When we pull domain information we can use information from a block A to build the domain of a block B if B post-dominates A. This patch implements both ideas and thereby simplifies domains that were not simplified by isl. For the FINAL basic block in test/ScopInfo/complex-successor-structure-3.ll . we used to build a universe set with 81 basic sets. Now it actually is represented as universe set. While the initial idea to utilize the graph structure depended on the dominator and post-dominator tree we can use the available region information as a coarse grained replacement. To this end we push the region entry domain to the region exit and pull it from the region entry for the region exit. Differential Revision: http://reviews.llvm.org/D18450 llvm-svn: 264789
* Revert "[ScopInfo] Fix domains after loops."Michael Kruse2016-03-291-1/+1
| | | | | | This reverts commit r264118. The approach is still under discussion. llvm-svn: 264705
* [FIX] Verify the alias group before returning itJohannes Doerfert2016-03-241-0/+72
| | | | | | | | | | | | Similar to r262612 we need to check not only the pointer SCEV and the type of an alias group but also the actual access instruction. The reason is again the same: The pointer SCEV is not flow sensitive but the access function is. In r262612 we avoided consolidating alias groups even though the pointer SCEV and the type were the same but the access function was not. Here it is simpler as we can simply check all members of an alias group against the given access instruction. llvm-svn: 264274
* Drop explicit -polly-delinearize parameterTobias Grosser2016-03-236-6/+6
| | | | | | | Delinearization is now enabled by default and does not need to explicitly need to be enabled in our tests. llvm-svn: 264154
* Codegen:Do not invalidate dominator tree when bailing out during code generationTobias Grosser2016-03-231-1/+1
| | | | | | | | | When codegenerating invariant loads in some rare cases we cannot generate code and bail out. This change ensures that we maintain a valid dominator tree in these situations. This fixes llvm.org/PR26736 Contributed-by: Matthias Reisinger <d412vv1n@gmail.com> llvm-svn: 264142
OpenPOWER on IntegriCloud