summaryrefslogtreecommitdiffstats
path: root/polly/test/Isl/CodeGen
Commit message (Collapse)AuthorAgeFilesLines
...
* Enable code generation of scalar dependences from function argumentsTobias Grosser2015-08-131-0/+33
| | | | | | | | | This change extends the BlockGenerator to not only allow Instructions as base elements of scalar dependences, but any llvm::Value. This allows us to code-generate scalar dependences which reference function arguments, as they arise when moddeling read-only scalar dependences. llvm-svn: 244874
* Always model PHI nodes in scop (if not in same nonaffine subregion)Tobias Grosser2015-08-121-2/+6
| | | | | | | | | | | | | | | | | | | | | | | Before we only modeled PHI nodes if at least one incoming basic block was itself part of the region, now we always model them except if all of their operands are part of a single non-affine subregion which we model as a black-box. This change only affects PHI nodes in the entry block, that have exactly one incoming edge. Before this change, we did not model them and as a result code generation would not know how to code generate them. With this change, code generation can code generate them like any other PHI node. This issue was exposed by r244606. Before this change simplifyRegion would have moved these PHI nodes out of the SCoP, so we would never have tried to code generate them. We could implement this behavior again, but changing the IR after the scop has been modeled and transformed always adds a risk of us invalidating earlier analysis results. It seems more save and overall also more consistent to just model and handle this one-entry-edge PHI nodes like any other PHI node in the scop. Solution proposed by: Michael Kruse <llvm@meinersbur.de> llvm-svn: 244721
* Add another test case with trival PHI in entry BBMichael Kruse2015-08-121-0/+38
| | | | | | | This one was extracted from the test-suite's pifft and caused a miscompilation because a scalar was not written to its alloca address. llvm-svn: 244720
* Add test case for entry node with trivial PHIMichael Kruse2015-08-111-0/+37
| | | | | | | This is a break-down from the test-suite's oggenc where Polly currently crashes. llvm-svn: 244692
* Revise the simplification of regionsMichael Kruse2015-08-114-52/+52
| | | | | | | | | | | | | | | | | | | | The previous code had several problems: For newly created BasicBlocks it did not (always) call RegionInfo::setRegionFor in order to update its analysis. At the moment RegionInfo does not verify its BBMap, but will in the future. This is fixed by determining the region new BBs belong to and set it accordingly. The new executeScopConditionally() requires accurate getRegionFor information. Which block is created by SplitEdge depends on the incoming and outgoing edges of the blocks it connects, which makes handling its output more difficult than it needs to be. Especially for finding which block has been created an to assign a region to it for the setRegionFor problem above. This patch uses an implementation for splitEdge that always creates a block between the predecessor and successor. simplifyRegion has also been simplified by using SplitBlockPredecessors instead of SplitEdge. Isolating the entries and exits have been refectored into individual functions. Previously simplifyRegion did more than just ensuring that there is only one entering and one exiting edge. It ensured that the entering block had no other outgoing edge which was necessary for executeScopConditionally(). Now the latter uses the alternative splitEdge implementation which can handle this situation so simplifyRegion really only needs to simplify the region. Also, executeScopConditionally assumed that there can be no PHI nodes in blocks with one incoming edge. This is wrong and LCSSA deliberately produces such edges. However, previous passes ensured that there can be no such PHIs in exit nodes, but which will no longer hold in the future. The new code that the property that it preserves the identity of region block (the property that the memory address of the BasicBlock containing the instructions remains the same; new blocks only contain PHI nodes and a terminator), especially the entry block. As a result, there is no need to update the reference to the BasicBlock of ScopStmt that contain its instructions because they have been moved to other basic blocks. Reviewers: grosser Part of Differential Revision: http://reviews.llvm.org/D11867 llvm-svn: 244606
* Correct non-existing past participle of split in filename Michael Kruse2015-08-101-0/+0
| | | | llvm-svn: 244478
* Update testcases after LLVM r243885Duncan P. N. Exon Smith2015-08-032-2/+2
| | | | llvm-svn: 243887
* Use the branch instruction to define the location of a PHI-node writeTobias Grosser2015-08-021-0/+58
| | | | | | | | | | | | | | | | | | | We use the branch instruction as the location at which a PHI-node write takes place, instead of the PHI-node itself. This allows us to identify the basic-block in a region statement which is on the incoming edge of the PHI-node and for which the write access was originally introduced. As a result we can, during code generation, avoid generating PHI-node write accesses for basic blocks that do not preceed the PHI node without having to look at the IR again. This change fixes a bug which was introduced in r243420, when we started to explicitly model PHI-node reads and writes, but dropped some additional checks that where still necessary during code generation to not emit PHI-node writes for basic-blocks that are not on incoming edges of the original PHI node. Compared to the code before r243420 the new code does not need to inspect the IR any more and we also do not generate multiple redundant writes. llvm-svn: 243852
* Only use instructions as insert locations for SCEVExpanderTobias Grosser2015-08-011-0/+54
| | | | | | | | | | | | | | | | | | | | | | | SCEVExpander, which we are using during code generation, only allows instructions as insert locations, but breaks in case BasicBlock->end() iterators are passed to it due to it trying to obtain the basic block in which code should be generated by calling Instruction->getParent(), which is not defined for ->end() iterators. This change adds an assert to Polly that ensures we only pass valid instructions to SCEVExpander and it fixes one case, where we used IRBuilder->SetInsertBlock() to set an ->end() insert location which was later passed to SCEVExpander. In general, Polly is always trying to build up the CFG first, before we actually insert instructions into the CFG sceleton. As a result, each basic block should already have at least one branch instruction before we start adding code. Hence, always requiring the IRBuilder insert location to be set to a real instruction should always be possible. Thanks Utpal Bora <cs14mtech11017@iith.ac.in> for his help with test case reduction. llvm-svn: 243830
* Fix polly tests after LLVM IR change in r243774Duncan P. N. Exon Smith2015-07-312-4/+4
| | | | llvm-svn: 243801
* Removed redundant alias checks generated during run time.Johannes Doerfert2015-07-232-13/+13
| | | | | | | | | As specified in PR23888, run-time alias check generation is expensive in terms of compile-time. This reduces the compile time by computing minimal/maximal access only once for each base pointer Contributed-by: Pratik Bhatu <cs12b1010@iith.ac.in> llvm-svn: 243024
* Use schedule trees to represent execution order of statementsTobias Grosser2015-07-146-27/+20
| | | | | | | | | | | | | | | | | | Instead of flat schedules, we now use so-called schedule trees to represent the execution order of the statements in a SCoP. Schedule trees make it a lot easier to analyze, understand and modify properties of a schedule, as specific nodes in the tree can be choosen and possibly replaced. This patch does not yet fully move our DependenceInfo pass to schedule trees, as some additional performance analysis is needed here. (In general schedule trees should be faster in compile-time, as the more structured representation is generally easier to analyze and work with). We also can not yet perform the reduction analysis on schedule trees. For more information regarding schedule trees, please see Section 6 of https://lirias.kuleuven.be/handle/123456789/497238 llvm-svn: 242130
* Remove code for scalar and PHI to array translationTobias Grosser2015-06-269-28/+11
| | | | | | | | | | | | | | | | This removes old code that has been disabled since several weeks and was hidden behind the flags -disable-polly-intra-scop-scalar-to-array=false and -polly-model-phi-nodes=false. Earlier, Polly used to translate scalars and PHI nodes to single element arrays, as this avoided the need for their special handling in Polly. With Johannes' patches adding native support for such scalar references to Polly, this code is not needed any more. After this commit both -polly-prepare and -polly-independent are now mostly no-ops. Only a couple of simple transformations still remain, but they are scheduled for removal too. Thanks again to Johannes Doerfert for his nice work in making all this code obsolete. llvm-svn: 240766
* Add support for srem instructionTobias Grosser2015-06-241-0/+38
| | | | | | | | | | | 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
* Mark sdivs as 'exact' instead of lowering them ourselvesTobias Grosser2015-06-041-3/+3
| | | | | | | | | LLVM's instcombine already translates power-of-two sdivs that are known to be exact to fast ashr instructions. Hence, there is no need to add this logic ourselves. Pointed-out-by: Johannes Doerfert llvm-svn: 239025
* Ensure memory access mappings are defined for full domainTobias Grosser2015-06-043-15/+19
| | | | | | | | | | | | | | We now verify that memory access functions imported via JSON are indeed defined for the full iteration domain. Before this change we accidentally imported memory mappings such as i -> i / 127, which only defined a mapped for values of i that are evenly divisible by 127, but which did not define any mapping for the remaining values, with the result that isl just generated an access expression that had undefined behavior for all the unmapped values. In the incorrect test cases, we now either use floor(i/127) or we use p/127 and provide the information that p is indeed a multiple of 127. llvm-svn: 239024
* Lower signed-divisions without rounding to ashr instructionsTobias Grosser2015-06-031-5/+3
| | | | llvm-svn: 238929
* Translate power-of-two floor-division into ashrTobias Grosser2015-06-033-15/+77
| | | | | | | | | | | | | | | | | | Power-of-two floor divisions can be translated into an arithmetic shift operation. This allows us to replace a complex lowering that requires division operations: %pexp.fdiv_q.0 = sub i64 %21, 128 %pexp.fdiv_q.1 = add i64 %pexp.fdiv_q.0, 1 %pexp.fdiv_q.2 = icmp slt i64 %21, 0 %pexp.fdiv_q.3 = select i1 %pexp.fdiv_q.2, i64 %pexp.fdiv_q.1, i64 %21 %pexp.fdiv_q.4 = sdiv i64 %pexp.fdiv_q.3, 128 with a simple ashr: %polly.fdiv_q.shr = ashr i64 %21, 7 llvm-svn: 238905
* Exploit non-negative numeratorsTobias Grosser2015-05-292-0/+115
| | | | | | | | | isl marks known non-negative numerators in modulo (and soon also division) operations. We now exploit this by generating unsigned operations. This is beneficial as unsigned operations with power-of-two denominators will be translated by isl to fast bitshift or bitwise and operations. llvm-svn: 238577
* Make use of scalar/phi code generation explicit in the testsTobias Grosser2015-05-232-3/+21
| | | | | | | | | | This ensures we pass all tests independently of how we set the options -disable-polly-intra-scop-scalar-to-array and -polly-model-phi-nodes. (At least if we enable both or disable both. Enabling them individually makes little sense, as they will hopefully disappear soon anyhow). llvm-svn: 238087
* Add scalar and phi code generationJohannes Doerfert2015-05-227-0/+528
| | | | | | | | | | | | | | | | | | | | | | | | | | | | To reduce compile time and to allow more and better quality SCoPs in the long run we introduced scalar dependences and PHI-modeling. This patch will now allow us to generate code if one or both of those options are set. While the principle of demoting scalars as well as PHIs to memory in order to communicate their value stays the same, this allows to delay the demotion till the very end (the actual code generation). Consequently: - We __almost__ do not modify the code if we do not generate code for an optimized SCoP in the end. Thus, the early exit as well as the unprofitable option will now actually preven us from introducing regressions in case we will probably not get better code. - Polly can be used as a "pure" analyzer tool as long as the code generator is set to none. - The original SCoP is almost not touched when the optimized version is placed next to it. Runtime regressions if the runtime checks chooses the original are not to be expected and later optimizations do not need to revert the demotion for that part. - We will generate direct accesses to the demoted values, thus there are no "trivial GEPs" that select the first element of a scalar we demoted and treated as an array. Differential Revision: http://reviews.llvm.org/D7513 llvm-svn: 238070
* Use base-pointer address space when creating new access functionsTobias Grosser2015-05-201-0/+44
| | | | llvm-svn: 237785
* Changed renaming of local symbols by inserting a dot before the numeric suffix.Sunil Srivastava2015-05-122-2/+2
| | | | | | | | | Modified two test cases to adjust to the above change in renaming. These two files were causing the buildbot failure in Polly, #30204 for example. Details in http://reviews.llvm.org/D9483 This checkin goes with r237150 and r237151 llvm-svn: 237203
* Rename IslCodeGeneration to CodeGenerationTobias Grosser2015-05-1295-116/+116
| | | | | | | | | Besides class, function and file names, we also change the command line option from -polly-codegen-isl to just -polly-codegen. The isl postfix is a leftover from the times when we still had the CLooG based -polly-codegen. Today it is just redundant and we drop it. llvm-svn: 237099
* Update polly for LLVM rename of debug info metadata with DI* prefixDuncan P. N. Exon Smith2015-04-292-38/+38
| | | | | | | Ran the same rename-md-di-prefix.sh script attached to PR23080 as in LLVM r236120 and CFE r236121. llvm-svn: 236127
* Remove flag '-polly-annotate-alias-scopes'Tobias Grosser2015-04-271-16/+0
| | | | | | | | This option is enabled since a long time and there does not seem to be a situation in which we would not want to print alias scopes. Remove this option to reduce the set of command-line option combinations that may expose bugs. llvm-svn: 235861
* Remove target triples from test casesTobias Grosser2015-04-2190-90/+0
| | | | | | | | I just learned that target triples prevent test cases to be run on other architectures. Polly test cases are until now sufficiently target independent to not require any target triples. Hence, we drop them. llvm-svn: 235384
* [opaque pointer types] Explicit non-pointer type for call expressionsDavid Blaikie2015-04-163-3/+3
| | | | | | (migration for recent LLVM change to textual IR for calls) llvm-svn: 235146
* Sign-extend in case of non-matching bitwidthTobias Grosser2015-04-052-0/+48
| | | | | | | | | | This change ensures that we sign-extend integer types in case non-matching operands are encountered when generating a multi-dimensional access offset. This fixes http://llvm.org/PR23124 Reported-by: Jeremy Huddleston Sequoia <jeremyhu@apple.com> llvm-svn: 234122
* Do not use the POLLY vector code generator if only strip-mining is requestedTobias Grosser2015-04-051-0/+3
| | | | | | | This fixes http://llvm.org/PR23127 Reported-by: Jeremy Huddleston Sequoia <jeremyhu@apple.com> llvm-svn: 234113
* [tests] Use -polly-vectorizer=polly directlyTobias Grosser2015-04-0511-11/+11
| | | | | | instead of defining a lit variable %vector-opt. llvm-svn: 234112
* Code generate parameters and run-time checks after branching new code regionTobias Grosser2015-03-284-6/+38
| | | | | | | | | | | | | | | | | | | When creating parameters the SCEVexpander may introduce new induction variables, that possibly create scalar dependences in the original scop, before we code generate the scop. The resulting scalar dependences may then inhibit correct code generation of the scop. To prevent this, we first version the code without a run-time check and only then introduce new parameters and the run-time condition. The if-condition that guards the original scop from being modified by the SCEVexpander. This change causes some test case changes as the run-time conditions are now introduced in the split basic block rather than in the entry basic block. This fixes http://llvm.org/PR22069 Test case reduced by: Karthik Senthil llvm-svn: 233477
* Drop redundant run line in checkTobias Grosser2015-03-281-1/+0
| | | | llvm-svn: 233476
* Drop -polly-vectorizer-unroll-only optionTobias Grosser2015-03-231-1/+0
| | | | | | | | This options was earlier used for experiments with the vectorizer, but to my knowledge is not really used anymore. If anybody needs this, we can always reintroduce this feature. llvm-svn: 232934
* Test case updates for explicit type parameter to the gep operatorDavid Blaikie2015-03-1324-67/+67
| | | | llvm-svn: 232186
* Drop option to prepare code for the BB vectorizerTobias Grosser2015-03-121-1/+1
| | | | | | | | The BB vectorizer is deprecated and there is no point in generating code for it any more. This option was introduced when there was not yet any loop vectorizer in sight. Now being matured, Polly should target the loop vectorizer. llvm-svn: 232099
* Add sign-extension during codegen of index expressionsTobias Grosser2015-03-081-0/+25
| | | | | | | | When code generating array index expressions the types of the different components of the index expressions may not always match. We extend the type of the index expression (if possible) and assert otherwise. llvm-svn: 231592
* Update Polly tests for the great metadata schema changeDavid Blaikie2015-03-032-32/+32
| | | | llvm-svn: 231089
* Update Polly tests to handle explicitly typed load changes in LLVM.David Blaikie2015-02-2769-149/+149
| | | | llvm-svn: 230796
* Update one test I missed when updating for the opaque pointer gep changes to ↵David Blaikie2015-02-271-7/+7
| | | | | | LLVM. llvm-svn: 230792
* Update Polly tests to handle explicitly typed gep changes in LLVMDavid Blaikie2015-02-2789-269/+269
| | | | llvm-svn: 230784
* [FIX] Teach RegionGenerator to respect and update dominanceJohannes Doerfert2015-02-272-4/+78
| | | | | | | | | | | | | | | | When we generate code for a whole region we have to respect dominance and update it too. The first is achieved with multiple "BBMap"s. Each copied block in the region gets its own map. It is initialized only with values mapped in the immediate dominator block, if this block is in the region and was therefor already copied. This way no values defined in a block that doesn't dominate the current one will be used. To update dominance information we check if the immediate dominator of the original block we want to copy is in the region. If so we set the immediate dominator of the current block to the copy of the immediate dominator of the original block. llvm-svn: 230774
* Use isl_ast_expr_call to create run-time checksTobias Grosser2015-02-263-8/+6
| | | | | | | isl recently introduced a new interface to create run-time checks from constraint sets. Use this interface to simplify our run-time check generation. llvm-svn: 230640
* Allow non-affine control flow -- Code GenerationJohannes Doerfert2015-02-241-0/+78
| | | | | | | | | | This is the code generation for region statements that are created when non-affine control flow was present in the input. A new generator, similar to the block or vector generator, for regions is used to traverse and copy the region statement and to adjust the control flow inside the new region in the end. llvm-svn: 230340
* ScopDetection: Only detect scops that have at least one read and one writeTobias Grosser2015-02-19115-156/+156
| | | | | | | | | | Scops that only read seem generally uninteresting and scops that only write are most likely initializations where there is also little to optimize. To not waste compile time we bail early. Differential Revision: http://reviews.llvm.org/D7735 llvm-svn: 229820
* [FIX] Fix test case that was affected by the early exit patchJohannes Doerfert2015-02-111-3/+2
| | | | llvm-svn: 228865
* Drop an assert and XFAIL two test casesTobias Grosser2015-02-111-0/+1
| | | | | | | This gets the buildbot green to avoid further emails. Johannes will fix this later in the evening. llvm-svn: 228862
* Add early exits for SCoPs we did not optimizeJohannes Doerfert2015-02-1138-54/+54
| | | | | | | | | | | | | This allows us to skip ast and code generation if we did not optimize a SCoP and will not generate parallel or alias annotations. The initial heuristic to exit is simple but allows improvements later on. All failing test cases have been modified to disable early exit, thus to keep their coverage. Differential Revision: http://reviews.llvm.org/D7254 llvm-svn: 228851
* Add test case for r227805Tobias Grosser2015-02-031-0/+29
| | | | llvm-svn: 227970
* [FIX] Updated test case (fixed names -> regular expressions)Johannes Doerfert2015-02-021-12/+12
| | | | llvm-svn: 227807
OpenPOWER on IntegriCloud