summaryrefslogtreecommitdiffstats
path: root/polly/test
Commit message (Collapse)AuthorAgeFilesLines
...
* BlockGenerators: Replace getNewScalarValue with getNewValueTobias Grosser2016-01-263-3/+56
| | | | | | | | | | | | | | | | | | | | | | | | | | | Both functions implement the same functionality, with the difference that getNewScalarValue assumes that globals and out-of-scop scalars can be directly reused without loading them from their corresponding stack slot. This is correct for sequential code generation, but causes issues with outlining code e.g. for OpenMP code generation. getNewValue handles such cases correctly. Hence, we can replace getNewScalarValue with getNewValue. This is not only more future proof, but also eliminates a bunch of code. The only functionality that was available in getNewScalarValue that is lost is the on-demand creation of scalar values. However, this is not necessary any more as scalars are always loaded at the beginning of each basic block and will consequently always be available when scalar stores are generated. As this was not the case in older versions of Polly, it seems the on-demand loading is just some older code that has not yet been removed. Finally, generateScalarLoads also generated loads for values that are loop invariant, available in GlobalMap and which are preferred over the ones loaded in generateScalarLoads. Hence, we can just skip the code generation of such scalar values, avoiding the generation of dead code. Differential Revision: http://reviews.llvm.org/D16522 llvm-svn: 258799
* test: Name instructions in a test case [NFC]Tobias Grosser2016-01-241-12/+12
| | | | llvm-svn: 258662
* ScopDetection: Do not detect regions with irreducible control as scopsTobias Grosser2016-01-221-0/+120
| | | | | | | | | | | | | | Polly currently does not support irreducible control and it is probably not worth supporting. This patch adds code that checks for irreducible control and refuses regions containing irreducible control. Polly traditionally had rather restrictive checks on the control flow structure which would have refused irregular control, but within the last couple of months most of the control flow restrictions have been removed. As part of this generalization we accidentally allowed irregular control flow. Contributed-by: Karthik Senthil and Ajith Pandel llvm-svn: 258497
* Remove irreducible control flow from test caseTobias Grosser2016-01-221-7/+13
| | | | | | | | | | | | | | | The test case we look at does not necessarily require irreducible control flow, but a normal loop is sufficient to create a non-affine region containing more than one basic block that dominates the exit node. We replace this irreducible control flow with a normal loop for the following reasons: 1) This is easier to understand 2) We will subsequently commit a patch that ensures Polly does not process irreducible control flow. Within non-affine regions, we could possibly handle irreducible control flow. llvm-svn: 258496
* Make sure we preserve alignment information after hoisting invariant loadJohannes Doerfert2016-01-191-0/+31
| | | | | | | | | | | In Polly, after hoisting loop invariant loads outside loop, the alignment information for hoisted loads are missing, this patch restore them. Contributed-by: Lawrence Hu <lawrence@codeaurora.org> Differential Revision: http://reviews.llvm.org/D16160 llvm-svn: 258105
* Update to ISL 0.16.1Michael Kruse2016-01-15122-308/+298
| | | | llvm-svn: 257898
* Prepare unit tests for update to ISL 0.16Michael Kruse2016-01-15105-2496/+2654
| | | | | | | | | | | | | | | | | | | | | ISL 0.16 will change how sets are printed which breaks 117 unit tests that text-compare printed sets. This patch re-formats most of these unit tests using a script and small manual editing on top of that. When actually updating ISL, most work is done by just re-running the script to adapt to the changed output. Some tests that compare IR and tests with single CHECK-lines that can be easily updated manually are not included here. The re-format script will also be committed afterwards. The per-test formatter invocation command lines options will not be added in the near future because it is ad hoc and would overwrite the manual edits. Ideally it also shouldn't be required anymore because ISL's set printing has become more stable in 0.16. Differential Revision: http://reviews.llvm.org/D16095 llvm-svn: 257851
* Call assumeNoOutOfBound only in updateDimensionalityRoman Gareev2016-01-083-2/+106
| | | | | | | | Call assumeNoOutOfBound only in updateDimensionality to process situations when new dimensions are added and new bounds checks are required. Contributed-by: Tobias Grosser, Gareev Roman llvm-svn: 257170
* Add option to assume single-loop scops with sufficient compute are profitableTobias Grosser2015-12-211-0/+83
| | | | | | | | | | | | | | If a loop has a sufficiently large amount of compute instruction in its loop body, it is unlikely that our rewrite of the loop iterators introduces large performance changes. As Polly can also apply beneficical optimizations (such as parallelization) to such loop nests, we mark them as profitable. This option is currently "disabled" by default, but can be used to run experiments. If enabled by setting it e.g. to 40 instructions, we currently see some compile-time increases on LNT without any significant run-time changes. llvm-svn: 256199
* [FIX] Schedule generation for block exiting multiple loops.Johannes Doerfert2015-12-201-0/+64
| | | | | | This fixes bug PR25604. llvm-svn: 256125
* ScopInfo: Bail out in case of complex branch structuresTobias Grosser2015-12-201-0/+195
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Scops that contain many complex branches are likely to result in complex domain conditions that consist of a large (> 100) number of conjucts. Transforming such domains is expensive and unlikely to result in efficient code. To avoid long compile times we detect this case and skip such scops. In the future we may improve this by either using non-affine subregions to hide such complex condition structures or by exploiting in certain cases properties (e.g., dominance) that allow us to construct the domains of a scop in a way that results in a smaller number improving conjuncts. Example of a code that results in complex iteration spaces: loop.header / | \ \ A0 A2 A4 \ \ / \ / \ A1 A3 \ / \ / \ | B0 B2 B4 | \ / \ / | B1 B3 ^ / \ / \ | C0 C2 C4 | \ / \ / / C1 C3 / \ / / loop backedge llvm-svn: 256123
* Fix of a comment.Roman Gareev2015-12-171-1/+1
| | | | llvm-svn: 255923
* Fix delinearization of fortran arraysRoman Gareev2015-12-171-0/+40
| | | | | | | | | | | | | | | The patch fixes Bug 25759 produced by inappropriate handling of unsigned maximum SCEV expressions by SCEVRemoveMax. Without a fix, we get an infinite loop and a segmentation fault, if we try to process, for example, '((-1 + (-1 * %b1)) umax {(-1 + (-1 * %yStart)),+,-1}<%.preheader>)'. It also fixes a potential issue related to signed maximum SCEV expressions. Tested-by: Roman Gareev <gareevroman@gmail.com> Fixed-by: Tobias Grosser <tobias@grosser.es> Differential Revision: http://reviews.llvm.org/D15563 llvm-svn: 255922
* VectorBlockGenerator: Generate scalar loads for vector statementsTobias Grosser2015-12-151-0/+37
| | | | | | | | When generating scalar loads/stores separately the vector code has not been updated. This commit adds code to generate scalar loads for vector code as well as code to assert in case scalar stores are encountered within a vector loop. llvm-svn: 255714
* ScopInfo: Look up first (and only) array accessTobias Grosser2015-12-153-0/+140
| | | | | | | | | | When rewriting the access functions of load/store statements, we are only interested in the actual array memory location. The current code just took the very first memory access, which could be a scalar or an array access. As a result, we failed to update access functions even though this was requested via .jscop. llvm-svn: 255713
* Revert "Always treat scalar writes as MUST_WRITEs"Tobias Grosser2015-12-145-8/+8
| | | | | | | | | | | | | | | | | | | This reverts commit r255471. Johannes raised in the post-commit review of r255471 the concern that PHI writes in non-affine regions with two exiting blocks are not really MUST_WRITE, but we just know that at least one out of the set of all possible PHI writes will be executed. Modeling all PHI nodes as MUST_WRITEs is probably save, but adding the needed documentation for such a special case is probably not worth the effort. Michael will be proposing a new patch that ensures only a single PHI_WRITE is created for non-affine regions, which - besides other benefits - should also allow us to use a single well-defined MUST_WRITE for such PHI writes. (This is not a full revert, but the condition and documentation have been slightly extended) llvm-svn: 255503
* Add unit test for r255473Michael Kruse2015-12-141-0/+51
| | | | | | | Check that memory accesses in non-affine regions that are always executed are MUST_WRITE. llvm-svn: 255500
* Always treat scalar writes as MUST_WRITEsMichael Kruse2015-12-135-8/+8
| | | | | | | | | LLVM's IR guarantees that a value definition occurs before any use, and also the value of a PHI must be one of the incoming values, "written" in one of the incoming blocks. Hence, such writes are never conditional in the context of a non-affine subregion. llvm-svn: 255471
* executeScopConditionally: Introduce special exiting blockTobias Grosser2015-12-0916-21/+21
| | | | | | | | | | | | | | | | | | | | | | | | | | When introducing separate control flow for the original and optimized code we introduce now a special 'ExitingBlock': \ / EnteringBB | SplitBlock---------\ _____|_____ | / EntryBB \ StartBlock | (region) | | \_ExitingBB_/ ExitingBlock | | MergeBlock---------/ | ExitBB / \ This 'ExitingBlock' contains code such as the final_reloads for scalars, which previously were just added to whichever statement/loop_exit/branch-merge block had been generated last. Having an explicit basic block makes it easier to find these constructs when looking at the CFG. llvm-svn: 255107
* test: Fix misspelled test lineTobias Grosser2015-12-091-1/+1
| | | | llvm-svn: 255106
* Update isl to isl-0.15-142-gf101714Tobias Grosser2015-12-041-7/+1
| | | | | | | | | | This update brings in improvements to isl's 'isolate' option that reduce the number of code versions generated. This results in both code-size and compile time reduction for outer loop vectorization. Thanks to Roman Garev and Sven Verdoolaege for working on this improvement. llvm-svn: 254706
* ScopInfo: Add support for delinearizing fortran arraysTobias Grosser2015-11-243-0/+329
| | | | | | | | | | | | gfortran (and fortran in general?) does not compute the address of an array element directly from the array sizes (e.g., %s0, %s1), but takes first the maximum of the sizes and 0 (e.g., max(0, %s0)) before multiplying the resulting value with the per-dimension array subscript expressions. To successfully delinearize index expressions as we see them in fortran, we first filter 'smax' expressions out of the SCEV expression, use them to guess array size parameters and only then continue with the existing delinearization. llvm-svn: 253995
* ScopInfo: Remove domains of error blocks (and blocks they dominate) early onTobias Grosser2015-11-221-2/+1
| | | | | | | | | | | | Trying to build up access functions for any of these blocks is likely to fail, as error blocks may contain invalid/non-representable instructions, and blocks dominated by error blocks may reference such instructions, which wil also cause failures. As all of these blocks are anyhow assumed to not be executed, we can just remove them early on. This fixes http://llvm.org/PR25596 llvm-svn: 253818
* Remove -polly-code-generator=isl from many test casesTobias Grosser2015-11-2137-58/+58
| | | | | | | This is the default since a long time. Setting it again does not add value in any of these test cases. llvm-svn: 253800
* Do not enforce lcssaJohannes Doerfert2015-11-211-2/+2
| | | | | | | | At some point we enforced lcssa for the loop surrounding the entry block. This is not only questionable as it does not check any other loop but also not needed any more. llvm-svn: 253789
* [FIX] Get the correct loop that surrounds a regionJohannes Doerfert2015-11-211-0/+48
| | | | llvm-svn: 253788
* ScopInfo: Ensure unique names for parameter names coming from load instructionsTobias Grosser2015-11-171-1/+1
| | | | | | | | | | | | | | | | In case the original parameter instruction does not have a name, but it comes from a load instruction where the base pointer has a name we used the name of the load instruction to give some more intuition of where the parameter came from. To ensure this works also through GEPs which may have complex offsets, we originally just dropped the offsets and _only_ used the base pointer name. As this can result in multiple parameters to get the same name, we now prefix the parameter ID to ensure parameter names are unique. This will make it easier to understand debug output. This change does not affect correctness, as parameter IDs (even of the same name) can always be distinguished through the SCEV pointer stored inside them. llvm-svn: 253330
* [FIX] Bail if access function is not divisible by element size.Johannes Doerfert2015-11-121-4/+2
| | | | llvm-svn: 252942
* Consistenly use getTypeAllocSize for size estimation.Johannes Doerfert2015-11-122-10/+10
| | | | | | | | | Only when we check for wrapping we want to use the store size, for all other cases we use the alloc size now. Suggested by: Tobias Grosser <tobias@grosser.es> llvm-svn: 252941
* RegionGenerator: Only introduce subregion.ivs for loops fully within a subregionTobias Grosser2015-11-122-4/+0
| | | | | | | | | | | | | | | IVs of loops for which the loop header is in the subregion, but not the entire loop may be incremented outside of the subregion and can consequently not be kept private to the subregion. Instead, they need to and are modeled as virtual loops in the iteration domains. As this is the case, generating new subregion induction variables for such loops is not needed and indeed wrong as they would hide the virtual induction variables modeled in the scop. This fixes a miscompile in MultiSource/Benchmarks/Ptrdist/bc and MultiSource/Benchmarks/nbench/. Thanks Michael and Johannes for their investiagations and helpful observations regarding this bug. llvm-svn: 252860
* Use parameter constraints provided via llvm.assumeJohannes Doerfert2015-11-122-0/+196
| | | | | | | | | 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
* Emit remarks for taken assumptionsJohannes Doerfert2015-11-121-0/+5
| | | | | | Differential Revision: http://reviews.llvm.org/D14412 llvm-svn: 252848
* Emit remark about aliasing pointersJohannes Doerfert2015-11-121-0/+3
| | | | llvm-svn: 252847
* Emit SCoP source location as remark during ScopInfoJohannes Doerfert2015-11-121-0/+309
| | | | | | | This removes a similar feature from ScopDetection, though with -polly-report that feature present twice anyway. llvm-svn: 252846
* [FIX] Do not generate code for parameters referencing dead valuesJohannes Doerfert2015-11-113-0/+391
| | | | | | | Check if a value that is referenced by a parameter is dead and do not generate code for the parameter in such a case. llvm-svn: 252813
* ScopInfo: Bailing out means assigning isl_set_empty to the AssumedContextTobias Grosser2015-11-111-81/+5
| | | | | | I got this the other way around in 252750. Thank you Johannes for noticing. llvm-svn: 252795
* ScopInfo: Do not try to model the memory accesses in an error blockTobias Grosser2015-11-111-0/+33
| | | | | | | | | | Error blocks may contain arbitrary instructions, among them some which we can not modeled correctly. As we do not generate ScopStmts for error blocks anyhow there is no point in trying to generate access functions for them. This fixes llvm.org/PR25494 llvm-svn: 252794
* ScopInfo: Bound compute time spent in boundary context constructionTobias Grosser2015-11-111-0/+300
| | | | | | | | | | | | | | For complex inputs our current approach of construction the boundary context may in rare cases become computationally so expensive that it is better to abort. This change adds a compute out check that bounds the compuations we spend on boundary context construction and bails out if this limit is reached. We can probably make our boundary construction algorithm more efficient, but this requires some more investigation and probably also some additional changes to isl. Until these have been added, we bound the compile time to ensure our buildbots are green. llvm-svn: 252758
* ScopInfo: Limit the number of disjuncts in assumed contextTobias Grosser2015-11-111-0/+229
| | | | | | | | | | | | | | | | | | | | | In certain rare cases (mostly -polly-process-unprofitable on large sequences of conditions - often without any loop), we see some compile-time timeouts due to the construction of an overly complex assumption context. This change limits the number of disjuncts to 150 (adjustable), to prevent us from creating assumptions contexts that are too large for even the compilation to finish. The limit has been choosen as large as possible to make sure we do not unnecessarily drop test coverage. If such cases also appear in -polly-process-unprofitable=false mode we may need to think about this again, as the current limitations may still allow assumptions that are way to complex to be checked profitably at run-time. There is also certainly room for improvement regarding how (and how efficient) we construct an assumed context, but this requires some more thinking. This completes llvm.org/PR25458 llvm-svn: 252750
* ScopDetection: Tighten the check for always executed 'error blocks'Tobias Grosser2015-11-111-0/+62
| | | | | | | | | Basic blocks that are always executed can not be error blocks as their execution can not possibly be an unlikely event. In this commit we tighten the check if an error block to basic blcoks that do not dominate the exit condition, but that dominate all exiting blocks of the scop. llvm-svn: 252726
* ScopDetection: Do not allow blocks to reference operands in error blocksTobias Grosser2015-11-111-0/+54
| | | | | | | | | | | | | r252713 introduced a couple of regressions due to later basic blocks refering to instructions defined in error blocks which have not yet been modeled. This commit is currently just encoding limitations of our modeling and code generation backends to ensure correctness. In theory, we should be able to generate and optimize such regions, as everything that is dominated by an error region is assumed to not be executed anyhow. We currently just lack the code to make this happen in practice. llvm-svn: 252725
* test: Shorten test case to reduce 'make polly-check' timeTobias Grosser2015-11-111-113/+13
| | | | | | | | | Thinking more about the last commit I came to realize that for testing the new functionality it is sufficient to verify that the iteration domains we construct for a simple test case do not contain any of the complexity that caused compile time issues for larger inputs. llvm-svn: 252714
* ScopInfo: Pass domain constraints through error blocksTobias Grosser2015-11-112-7/+234
| | | | | | | | | | | | | | | | | | | | | | | | | Previously, we just skipped error blocks during scop construction. With this change we make sure we can construct domains for error blocks such that these domains can be forwarded to subsequent basic blocks. This change ensures that basic blocks that post-dominate and are dominated by a basic block that branches to an error condition have the very same iteration domain as the branching basic block. Before, this change we would construct a domain that excludes all error conditions. Such domains could become _very_ complex and were undesirable to build. Another solution would have been to drop these constraints using a dominance/post-dominance check instead of modeling the error blocks. Such a solution could also work in case of unreachable statements or infinite loops in the scop. However, as we currently (to my believe incorrectly) model unreachable basic blocks in the post-dominance tree, such a solution is not yet feasible and requires first a change to LLVM's post-dominance tree construction. This commit addresses the most sever compile time issue reported in: http://llvm.org/PR25458 llvm-svn: 252713
* [FIX] Cast pre-loaded values correctly or reload them with adjusted type.Johannes Doerfert2015-11-116-21/+91
| | | | | | | | | | | | | Especially for structs, the SAI object of a base pointer does not describe all the types that the user might expect when he loads from that base pointer. While we will still cast integers and pointers we will now reload the value with the correct type if floating point and non-floating point values are involved. However, there are now TODOs where we use bitcasts instead of a proper conversion or reloading. This fixes bug 25479. llvm-svn: 252706
* [FIX] Create empty invariant equivalence classesJohannes Doerfert2015-11-112-3/+118
| | | | | | | | | | | We now create all invariant equivalence classes for required invariant loads instead of creating them on-demand. This way we can check if a parameter references an invariant load that is actually not executed and was therefor not materialized. If that happens the parameter is not materialized either. This fixes bug 25469. llvm-svn: 252701
* tests: Add test that has a single pointer both as scalar read and array baseTobias Grosser2015-11-101-0/+88
| | | | | | | | | | | | | | In case we also model scalar reads it can happen that a pointer appears in both a scalar read access as well as the base pointer of an array access. As this is a little surprising, we add a specific test case to document this behaviour. To my understanding it should be OK to have a read from an array A[] and read/write accesses to A[...]. isl is treating these arrays as unrelated as their dimensionality differs. This seems to be correct as A[] remains constant throughout the execution of the scop and is not affected by the reads/writes to A[...]. If this causes confusion, it might make sense to make this behaviour more obvious by using different names (e.g., A_scalar[], A[...]). llvm-svn: 252615
* Simplify test caseTobias Grosser2015-11-101-45/+1
| | | | | | | Commit r252422 introduced an unnecessary complicated test case. Reduce it to the part that actually triggered the original issue. llvm-svn: 252611
* ScopInfo: Make printing of ScopArrayInfo more similar to declarations in CTobias Grosser2015-11-108-24/+24
| | | | | | | | | | | | | | | Memory references are now printed as follows: Old New Scalars: i64 MemRef_val[*] i64 MemRef_val; Arrays: i64 MemRef_A[*][%m][%o][8] i64 MemRef_A[*][%m][%o]; We do not print any more information about the element size in the type. Such information has already been available in a comment after the scalar/array declaration. It was redundant and did not match well with what people were used from C. llvm-svn: 252602
* Fix non-affine generated entering node not being recognized as dominatingMichael Kruse2015-11-091-0/+44
| | | | | | | | | | | | | | Scalar reloads in the generated entering block were not recognized as dominating the subregions locks when there were multiple entering nodes. This resulted in values defined in there not being copied. As a fix, we unconditionally add the BBMap of the generated entering node to the generated entry. This fixes part of llvm.org/PR25439. This reverts 252449 and reapplies r252445. Its test was failing indeterministically due to r252375 which was reverted in r252522. llvm-svn: 252540
* Fix dominance when subregion exit is outside scopMichael Kruse2015-11-093-4/+35
| | | | | | | | | | | | | | | The dominance of the generated non-affine subregion block was based on the scop's merge block, therefore resulted in an invalid DominanceTree. It resulted in some values as assumed to be unusable in the actual generated exit block. We detect the case that the exit block has been moved and decide dominance using the BB at the original exit. If we create another exit node, that exit nodes is dominated by the one generated from where the original exit resides. This fixes llvm.org/PR25438 and part of llvm.org/PR25439. llvm-svn: 252526
OpenPOWER on IntegriCloud