summaryrefslogtreecommitdiffstats
path: root/polly/test
Commit message (Collapse)AuthorAgeFilesLines
...
* Extract some constant factors from "SCEVAddExprs"Johannes Doerfert2016-04-251-0/+52
| | | | | | | | | 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
* Do not check all GEPs for assumptionsJohannes Doerfert2016-04-251-0/+68
| | | | | | | | | | Before, we checked all GEPs in a statement in order to derive out-of-bound assumptions. However, this can not only introduce new parameters but it is also not clear what we can learn from GEPs that are not immediately used in a memory accesses inside the SCoP. As this case is very rare, no actual change in the behaviour is expected. llvm-svn: 267442
* Only add user assumptions on known parameters [NFC]Johannes Doerfert2016-04-252-0/+106
| | | | | | | | | | | | Before, assumptions derived from llvm.assume could reference new parameters that were not known to the SCoP before. These were neither beneficial to the representation nor to the user that reads the emitted remark. Now we project them out and keep only user assumptions on known parameters. Nevertheless, the new parameters are still part of the SCoPs parameter space as the SCEVAffinator currently adds them on demand. llvm-svn: 267441
* Model zext-extend instructionsJohannes Doerfert2016-04-2513-33/+304
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Add an invalid domain to memory accessesJohannes Doerfert2016-04-231-0/+53
| | | | | | | | | Memory accesses can have non-precisely modeled access functions that would cause us to build incorrect execution context for hoisted loads. This is the same issue that occurred during the domain construction for statements and it is dealt with the same way. llvm-svn: 267289
* Translate SCEVs to isl_pw_aff and their invalid domainJohannes Doerfert2016-04-231-0/+48
| | | | | | | | | | | | | 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
* Simplify the execution context for dereferencable loadsJohannes Doerfert2016-04-235-5/+115
| | | | | | | If we know it is safe to execute a load we do not need an execution context, however only if we are sure it was modeled correctly. llvm-svn: 267284
* Bail for complex execution contexts of invariant loadsJohannes Doerfert2016-04-222-8/+49
| | | | llvm-svn: 267146
* 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
* Update debug metadata after LLVM commits r266445+r266446Tobias Grosser2016-04-1511-34/+24
| | | | llvm-svn: 266473
* [Polly] Remove unwanted --check-prefix=CHECK from unit tests. NFC.Mandeep Singh Grang2016-04-152-2/+2
| | | | | | | | | | | | | | | | | 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
* Add contexts to test cases. NFC.Michael Kruse2016-04-142-2/+12
| | | | | | | | As discussed in the Polly weekly phone call and reviews.llvm.org/D18878, the assumed contexts changed (widen) due to D18878/r265942. Also check these contexts in the tests affected by that change. llvm-svn: 266323
* Add InvalidContext to update_test.py.Michael Kruse2016-04-141-0/+4
| | | | | | | This allows the test update script to add 'Invalid Context:' to test cases. Enable with --check-include=InvalidContext. llvm-svn: 266322
* [FIX] Check the invalid context agains the context to rule out SCoPsJohannes Doerfert2016-04-121-0/+70
| | | | llvm-svn: 266096
* Do not by default minimize remarksJohannes Doerfert2016-04-122-0/+3
| | | | | | | | | | | | | We used checks to minimize the number of remarks we present to a user but these checks can become expensive, especially since all wrapping assumptions are emitted separately. Because there is not benefit for a "headless" run we put these checks under a command line flag. Thus, if the flag is not given we will emit "non-effective" remarks, e.g., duplicates and revert to the old behaviour if it is given. As this also changes the internal representation of some sets we set the flag by default for our unit tests. llvm-svn: 266087
* Record wrapping assumptions earlyJohannes Doerfert2016-04-128-8/+8
| | | | | | | | 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
* Record assumptions first and add them laterJohannes Doerfert2016-04-129-13/+12
| | | | | | | | | | | | | | | | | | There are three reasons why we want to record assumptions first before we add them to the assumed/invalid context: 1) If the SCoP is not profitable or otherwise invalid without the assumed/invalid context we do not have to compute it. 2) Information about the context are gathered rather late in the SCoP construction (basically after we know all parameters), thus the user might see overly complicated assumptions to be taken while they would have been simplified later on. 3) Currently we cannot take assumptions at any point but have to wait, e.g., for the domain generation to finish. This makes wrapping assumptions much more complicated as they need to be and it will have a similar effect on "signed-unsigned" assumptions later. llvm-svn: 266068
* Introduce an invalid context for each statementJohannes Doerfert2016-04-121-1/+1
| | | | | | | | | | Collect the error domain contexts (formerly in the ErrorDomainCtxMap) for each statement in the new InvalidContext member variable. While this commit is basically a [NFC] it is a first step to make hoisting sound by allowing a more fine grained record of invalid contexts, e.g., here on statement level. llvm-svn: 266053
* Allow overflow of indices with constant dim-sizes.Michael Kruse2016-04-112-19/+40
| | | | | | | | | | | | | | | | | | | Allow overflow of indices into the next higher dimension if it has constant size. E.g. float A[32][2]; ((float*)A)[5]; is effectively the same as A[2][1]; This can happen since r265379 as a side effect if ScopDetection recognizes an access as affine, but ScopInfo rejects the GetElementPtr. Differential Revision: http://reviews.llvm.org/D18878 llvm-svn: 265942
* Allow pointer expressions in SCEVs again.Johannes Doerfert2016-04-1012-67/+137
| | | | | | | | | 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-092-3/+62
| | | | | | | | | | | | 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] Do not crash on opaque (unsized) types.Johannes Doerfert2016-04-081-0/+25
| | | | llvm-svn: 265834
* [FIX] Teach the ScopExpander about parallel subfunctionsJohannes Doerfert2016-04-081-0/+44
| | | | llvm-svn: 265824
* Add testcase from PR27218. NFC.Michael Kruse2016-04-081-0/+49
| | | | | | | The the bug has already been fixed r265795, but this second testcase still useful. llvm-svn: 265809
* [ScopInfo] Fix check for element size mismatch.Michael Kruse2016-04-081-0/+56
| | | | | | | | | | | | The way to get the elements size with getPrimitiveSizeInBits() is not the same as used in other parts of Polly which should use DataLayout::getTypeAllocSize(). Its use only queries the size of the pointer and getPrimitiveSizeInBits returns 0 for types that require a DataLayout object such as pointers. Together with r265379, this should fix PR27195. llvm-svn: 265795
* [FIX] Allow to lookup domains for non-affine subregion blocksJohannes Doerfert2016-04-081-0/+73
| | | | llvm-svn: 265779
* [FIX] Adjust execution context of hoisted loads wrt. error domainsJohannes Doerfert2016-04-081-0/+72
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | If we build the domains for error blocks and later remove them we lose the information that they are not executed. Thus, in the SCoP it looks like the control will always reach the statement S: for (i = 0 ... N) if (*valid == 0) doSth(&ptr); S: A[i] = *ptr; Consequently, we would have assumed "ptr" to be always accessed and preloaded it unconditionally. However, only if "*valid != 0" we would execute the optimized version of the SCoP. Nevertheless, we would have hoisted and accessed "ptr"regardless of "*valid". This changes the semantic of the program as the value of "*valid" can cause a change of "ptr" and control if it is executed or not. To fix this problem we adjust the execution context of hoisted loads wrt. error domains. To this end we introduce an ErrorDomainCtxMap that maps each basic block to the error context under which it might be executed. Thus, to the context under which it is executed but an error block would have been executed to. To fill this map one traversal of the blocks in the SCoP suffices. During this traversal we do also "remove" error statements and those that are only reachable via error statements. This was previously done by the removeErrorBlockDomains function which is therefor not needed anymore. This fixes bug PR26683 and thereby several SPEC miscompiles. Differential Revision: http://reviews.llvm.org/D18822 llvm-svn: 265778
* [FIX] Handle multiplications in the SCEVAffinator againJohannes Doerfert2016-04-081-0/+92
| | | | | | | | | | | 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
* Add test cases for the removal of error blocksJohannes Doerfert2016-04-082-0/+152
| | | | llvm-svn: 265776
* [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
* Add test case forgotten in r265379.Tobias Grosser2016-04-051-0/+52
| | | | | | Thanks Johannes for reminding me. llvm-svn: 265423
* [FIX] Ensure SAI objects for exit PHIsJohannes Doerfert2016-04-053-2/+99
| | | | | | | | | | | | | 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
* Do not allow to complex branch conditionsJohannes Doerfert2016-04-043-10/+155
| | | | | | | | | | | | | Even before we build the domain the branch condition can become very complex, especially if we have to build the complement of a lot of equality constraints. With this patch we bail if the branch condition has a lot of basic sets and parameters. After this patch we now successfully compile External/SPEC/CINT2000/186_crafty/186_crafty with "-polly-process-unprofitable -polly-position=before-vectorizer". llvm-svn: 265286
* Exploit graph properties during domain generationJohannes Doerfert2016-04-0412-57/+952
| | | | | | | | | | | | | | | | | | | | | | | | | | | 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] Do not create a SCoP in the presence of infinite loopsJohannes Doerfert2016-04-033-10/+73
| | | | | | | | If a loop has no exiting blocks the region covering we use during schedule genertion might not cover that loop properly. For now we bail out as we would not optimize these loops anyway. llvm-svn: 265280
* Revert "[FIX] Do not create a SCoP in the presence of infinite loops"Tobias Grosser2016-04-033-73/+10
| | | | | | | | | | | | | | This reverts commit r265260, as it caused the following 'make check-polly' failures: Polly :: ScopDetect/index_from_unpredictable_loop.ll Polly :: ScopInfo/multiple_exiting_blocks.ll Polly :: ScopInfo/multiple_exiting_blocks_two_loop.ll Polly :: ScopInfo/schedule-const-post-dominator-walk-2.ll Polly :: ScopInfo/schedule-const-post-dominator-walk.ll Polly :: ScopInfo/switch-5.ll llvm-svn: 265272
* [FIX] Do not create two SAI objects for exit PHIsJohannes Doerfert2016-04-031-0/+39
| | | | | | | | | If an exit PHI is written and also read in the SCoP we should not create two SAI objects but only one. As the read is only modeled to ensure OpenMP code generation knows about it we can simply use the EXIT_PHI MemoryKind for both accesses. llvm-svn: 265261
* [FIX] Do not create a SCoP in the presence of infinite loopsJohannes Doerfert2016-04-033-10/+73
| | | | | | | | If a loop has no exiting blocks the region covering we use during schedule genertion might not cover that loop properly. For now we bail out as we would not optimize these loops anyway. llvm-svn: 265260
* [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-3013-955/+60
| | | | | | | | | | | | | | | | | | | 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-2913-60/+955
| | | | | | | | | | | | | | | | | | | | | | | | 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-2910-112/+43
| | | | | | This reverts commit r264118. The approach is still under discussion. llvm-svn: 264705
* Add fine-grain dependences analysis to release notes.Hongbin Zheng2016-03-284-7/+7
| | | | | | Differential Revision: http://reviews.llvm.org/D17905 llvm-svn: 264575
* Generalize the domain complexity restrictionsJohannes Doerfert2016-03-263-2/+144
| | | | | | | | | | | | | | | | | | 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
* Update to isl-0.16.1-145-g243bf7cTobias Grosser2016-03-252-2/+2
| | | | | | | Just an import to keep track with the latest version of isl. We are not looking for specific features. llvm-svn: 264452
* [FIX] Handle accesses to "null" in MemIntrinsicsJohannes Doerfert2016-03-241-0/+37
| | | | | | | | | This fixes PR27035. While we now exclude MemIntrinsics from the polyhedral model if they would access "null" we could exploit this even more, e.g., remove all parameter combinations that would lead to the execution of this statement from the context. llvm-svn: 264284
* [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
OpenPOWER on IntegriCloud