summaryrefslogtreecommitdiffstats
path: root/polly/lib/CodeGen/IslCodeGeneration.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Add early exits for SCoPs we did not optimizeJohannes Doerfert2015-02-111-2/+8
| | | | | | | | | | | | | 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
* [Refactor] Use only one BlockGenerator for a SCoPJohannes Doerfert2015-02-061-5/+7
| | | | | | | | | | | | | | | | This change has two main purposes: 1) We do not use a static interface to hide an object we create and destroy for every basic block we copy. 2) We allow the BlockGenerator to store information between calls to the copyBB method. This will ease scalar/phi code generation later on. While a lot of method signatures were changed this should not cause any real behaviour change. Differential Revision: http://reviews.llvm.org/D7467 llvm-svn: 228443
* [PM] Update Polly for LLVM r226394 and r226396 which changed some of theChandler Carruth2015-01-181-2/+2
| | | | | | | block splitting interfaces to accept specific analyses rather than a pass. llvm-svn: 226398
* [PM] Update Polly for LLVM r226385 which made LoopInfo actually deriveChandler Carruth2015-01-181-2/+2
| | | | | | | from LoopInfoBase<...>, removing the need for the awkward getBase() dance. llvm-svn: 226387
* [PM] Update Polly following LLVM r226373 which refactors LoopInfo inChandler Carruth2015-01-171-4/+4
| | | | | | preparation for the new pass manager. llvm-svn: 226374
* Check assert before the instruction that uses the assumption checked.Tobias Grosser2015-01-101-2/+3
| | | | | | I did not find a good test case, as the assert should generally hold in Polly. llvm-svn: 225582
* Add support for pointer types in expressionsTobias Grosser2015-01-081-2/+1
| | | | llvm-svn: 225464
* Remove -polly-codegen-scev option and related codeTobias Grosser2014-11-301-9/+0
| | | | | | | | SCEV based code generation has been the default for two weeks after having been tested for a long time. We now drop the support the non-scev-based code generation. llvm-svn: 222978
* Add OpenMP code generation to isl backendTobias Grosser2014-11-151-7/+329
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Extract SCEV generation into subfunctionTobias Grosser2014-11-061-8/+16
| | | | | | | This makes the code more readable and will be reused in subsequent OpenMP patches. llvm-svn: 221418
* Delete some unnecessary codeTobias Grosser2014-10-291-12/+0
| | | | | | | | | Originally we have needed this code to map the isl_id of an array to its base pointer. However, as now the isl_id contains a reference to the array itself we obtain the base pointer from this isl_id and we do not need to add this information to the IDToValue map. llvm-svn: 220876
* Allow the VectorBlockGenerator to use the IslExprBuilder.Johannes Doerfert2014-10-081-1/+2
| | | | | | | This also enables the VectorBlockGenerator to build load store accesses according to the newAccessRelation of a MemoryAccess. llvm-svn: 219321
* Allow multidimensional accesses in the IslExprBuilder.Johannes Doerfert2014-10-051-4/+11
| | | | | | | | | This resolved the issues with delinearized accesses that might alias, thus delinearization doesn't deactivate runtime alias checks anymore. Differential Revision: http://reviews.llvm.org/D5614 llvm-svn: 219078
* Introduce the ScopArrayInfo class.Johannes Doerfert2014-10-051-1/+0
| | | | | | | | | | | | | | | | | | | This class allows to store information about the arrays in the SCoP. For each base pointer in the SCoP one object is created storing the type and dimension sizes of the array. The objects can be obtained via the SCoP, a MemoryAccess or the isl_id associated with the output dimension of a MemoryAccess (the description of what is accessed). So far we use the information in the IslExprBuilder to create the right base type before indexing into the base array. This fixes the bug http://llvm.org/bugs/show_bug.cgi?id=21113 (both test cases are included). On top of that we can now build runtime alias checks for delinearized arrays as the dimension sizes are also part of the ScopArrayInfo objects. Differential Revision: http://reviews.llvm.org/D5613 llvm-svn: 219077
* [Refactor] Rename LoopAnnotator to ScopAnnotatorJohannes Doerfert2014-10-021-3/+3
| | | | | | | | | The LoopAnnotator doesn't annotate only loops any more, thus it is called ScopAnnotator from now on. This also removes unnecessary polly:: namespace tags. llvm-svn: 218878
* Allow to annotate alias scopes in the new SCoP.Johannes Doerfert2014-10-021-0/+4
| | | | | | | | | The command line flag -polly-annotate-alias-scopes controls whether or not Polly annotates alias scopes in the new SCoP (default ON). This can improve later optimizations as the new SCoP is basically an alias free environment for them. llvm-svn: 218877
* Annotate LLVM-IR for all parallel loopsJohannes Doerfert2014-10-011-3/+3
| | | | | | | | | | | | | | This change allows to annotate all parallel loops with loop id metadata. Furthermore, it will annotate memory instructions with llvm.mem.parallel_loop_access metadata for all surrounding parallel loops. This is especially usefull if an external paralleliser is used. This also removes the PollyLoopInfo class and comments the LoopAnnotator. A test case for multiple parallel loops is attached. llvm-svn: 218793
* [RTC] Runtime Alias Checks for the ISL backendJohannes Doerfert2014-09-181-1/+3
| | | | | | | | | | | | | | | | | This change will build all alias groups (minimal/maximal accesses to possible aliasing base pointers) we have to check before we can assume an alias free environment. It will also use these to create Runtime Alias Checks (RTC) in the ISL code generation backend, thus allow us to optimize SCoPs despite possibly aliasing pointers when this backend is used. This feature will be enabled for the isl code generator, e.g., --polly-code-generator=isl, but disabled for: - The cloog code generator (still the default). - The case delinearization is enabled. - The case non-affine accesses are allowed. llvm-svn: 218046
* Allow to generate a loop without the GuardBBJohannes Doerfert2014-09-101-1/+5
| | | | | | | | | | | | This allows us to omit the GuardBB in front of created loops if we can show the loop trip count is at least one. It also simplifies the dominance relation inside the new created region. A GuardBB (even with a constant branch condition) might trigger false dominance errors during function verification. Differential Revision: http://reviews.llvm.org/D5297 llvm-svn: 217525
* [Refactor] Cleanup isl code generationJohannes Doerfert2014-09-101-25/+35
| | | | | | | | | | | | | | | | | | | | Summary: + Refactor the runtime check (RTC) build function + Added helper function to create an PollyIRBuilder + Change the simplify region function to create not only unique entry and exit edges but also enfore that the entry edge is unconditional + Cleaned the IslCodeGeneration runOnScop function: - less post-creation changes of the created IR + Adjusted and added test cases Reviewers: grosser, sebpop, simbuerg, dpeixott Subscribers: llvm-commits, #polly Differential Revision: http://reviews.llvm.org/D5076 llvm-svn: 217508
* Introduce a typedef for the IDToValue typeTobias Grosser2014-08-311-3/+1
| | | | llvm-svn: 216843
* Revert "[Refactor] Cleanup runtime code generation"Tobias Grosser2014-08-161-42/+25
| | | | | | | | | | | | | | | | This reverts commit 215466 (and 215528, a trivial formatting fix). The intention of these commits is a good one, but unfortunately they broke our LNT buildbot: http://lab.llvm.org:8011/builders/perf-x86_64-penryn-O3-polly-codegen-isl Several of the cleanup changes that have been combined in this 'fixup' are trivial and could probably be committed as obvious changes without risking to break the build. The remaining changes are little and it should be easy to figure out what went wrong. llvm-svn: 215817
* [Refactor] Cleanup runtime code generationJohannes Doerfert2014-08-121-25/+42
| | | | | | | + Use regexp in two test case. + Refactor the runtime condition build function llvm-svn: 215466
* Make used analysis passes explicitJohannes Doerfert2014-08-071-10/+15
| | | | | | | | Use the explicit analysis if possible, only for splitBlock we will continue to use the Pass * argument. This change allows us to remove the getAnalysis calls from the code generation. llvm-svn: 215121
* Fix the modifiable access creationJohannes Doerfert2014-08-031-1/+16
| | | | | | | | | | | | + Remove the class IslGenerator which duplicates the functionality of IslExprBuilder. + Use the IslExprBuilder to create code for memory access relations. + Also handle array types during access creation. + Enable scev codegen for one of the transformed memory access tests, thus access creation without canonical induction variables available. + Update one test case to the new output. llvm-svn: 214659
* Change the semantics of is*ParallelJohannes Doerfert2014-08-011-2/+4
| | | | | | | | | The functions isParallel, isInnermostParallel and IsOutermostParallel in IslAstInfo will now return true even in the presence of broken reductions. To compensate for this change the negated result of isReductionParallel can be used. llvm-svn: 214488
* [Refactor] Expose the IslExprBuilderJohannes Doerfert2014-07-291-485/+1
| | | | | | | This allows us to use to IslExprBuilder not only from within IslCodegeneration. llvm-svn: 214215
* [Refactor] Expose the runtime debug builderJohannes Doerfert2014-07-241-83/+0
| | | | llvm-svn: 213908
* [Fix] Typo during refactoringJohannes Doerfert2014-07-231-2/+2
| | | | llvm-svn: 213795
* [Refactor] IslAst and payload structJohannes Doerfert2014-07-231-22/+2
| | | | | | | | | | | + Renamed context into build when it's the isl_ast_build + Use the IslAstInfo functions to extract the schedule of a node + Use the IslAstInfo functions to extract the build/context of a node + Move the payload struct into the IslAstInfo class + Use a constructor and destructor (also new and delete) to allocate/initialize the payload struct llvm-svn: 213792
* Update for RegionInfo changes.Matt Arsenault2014-07-191-3/+4
| | | | | | | Mostly related to missing includes and renaming of the pass to RegionInfoPass. llvm-svn: 213457
* [Refactor] Move code out of the IslAst headerJohannes Doerfert2014-07-171-4/+6
| | | | | | | | | | | | Offer the static functions to extract information out of an IslAst for node as members of IslAstInfo not as top level entities. + Refactor common code + Add isParallel and isReductionParallel + Rename IslAstUser to IslAstUserPayload to make it clear this is just a (or the) payload struct. llvm-svn: 213272
* Derive run-time conditions for delinearizationTobias Grosser2014-07-021-1/+3
| | | | | | | | | | | | | | | | | | | | | | | As our delinearization works optimistically, we need in some cases run-time checks that verify our optimistic assumptions. A simple example is the following code: void foo(long n, long m, long o, double A[n][m][o]) { for (long i = 0; i < 100; i++) for (long j = 0; j < 150; j++) for (long k = 0; k < 200; k++) A[i][j][k] = 1.0; } After clang linearized the access to A and we delinearized it again to A[i][j][k] we need to ensure that we do not access the delinearized array out of bounds (this information is not available in LLVM-IR). Hence, we need to verify the following constraints at run-time: CHECK: Assumed Context: CHECK: [o, m] -> { : m >= 150 and o >= 200 } llvm-svn: 212198
* Use arguments of user statements to perform induction variable substitutionTobias Grosser2014-07-021-49/+70
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | To translate the old induction variables as they exist before Polly to new new induction variables introduced during AST code generation we need to generate code that computes the new values from the old ones. We can do this by just looking at the arguments isl generates in each scheduled statement. Example: // Old for i S(i) // New for c0 for c1 S(c0 + c1) To get the value of i, we need to compute 'c0 + c1'. This expression is readily available in the user statements generated by isl and just needs to be translated to LLVM-IR. This replaces an old confusing construct that constructed during ast generation an isl multi affine expression that described this relation and which was then again ast generated for each statement and argument when translating the isl ast to LLVM-IR. This approach was difficult to understand and the additional ast generation calls where entirely redundant as isl provides the relevant expressions as arguments of the generated user statements. llvm-svn: 212186
* Use range-based for loopsTobias Grosser2014-06-041-3/+2
| | | | llvm-svn: 210170
* Fix formattingTobias Grosser2014-04-221-2/+2
| | | | llvm-svn: 206903
* IslCodeGeneration: Document the IslExprBuilderTobias Grosser2014-04-221-3/+86
| | | | llvm-svn: 206898
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-1/+2
| | | | | | | | | | 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
* Emit llvm.loop metadata for parallel loopsTobias Grosser2014-03-041-5/+16
| | | | | | | For now we only mark innermost loops for the loop vectorizer. We could later also mark not-innermost loops to enable the introduction of openmp parallelism. llvm-svn: 202854
* Introduce PollyIRBuilderTobias Grosser2014-03-041-8/+8
| | | | | | | | PollyIRBuilder is currently just a typedef to IRBuilder<>. Consequently, this change should not affect behavior. In subsequent patches we will extend its functionality to emit loop.parallel metadata. llvm-svn: 202853
* Update to isl 1b3ba3b72c0482fd36bf0b4a1186a259f7bafeedTobias Grosser2014-01-261-0/+2
| | | | | | | | | | | | | | | This includes the following very useful isl commit: commit d962967ab42323ea5ca0398956fbff6a98c782fa Author: Sven Verdoolaege <skimo@kotnet.org> Date: Wed Dec 18 12:05:32 2013 +0100 allow the user to impose a bound on the number of low-level operations This should allow the user to deterministically limit the effort spent on a computation. llvm-svn: 200155
* Adapt to DomTree changes in r199104Tobias Grosser2014-01-131-4/+4
| | | | llvm-svn: 199157
* IslCodegen: Support for run-time conditionsTobias Grosser2013-11-171-0/+12
| | | | llvm-svn: 194948
* IslCodegen: Do not build upper bound in vector forTobias Grosser2013-11-021-6/+0
| | | | | | | | | | | For for-nodes that are translated to a set of vector lanes, we already know the overall number of iterations. Calculating the upper bound is consequently not necessary. This change removes the code for upper bound calculation, which was probably copy/pasted from the code generation for the normal for-loop. This issue was found by Sylvestre's scan-build server. llvm-svn: 193925
* Integrate latest clang-format changesTobias Grosser2013-06-231-1/+1
| | | | llvm-svn: 184655
* Use isl_val instead of isl_int in the core of PollyTobias Grosser2013-06-211-5/+3
| | | | | | | | | | | isl recently introduced isl_val as an abstract interface to represent arbitrary precision numbers. This interface superseeds the old isl_int interface. In contrast to the old interface which implemented arbitrary precision arithmetic using macros that forward to the gmp library, the new library hides the math library implementation in isl. This allows us to switch the math library used by isl without affecting users such as Polly. llvm-svn: 184529
* Update LoopInfo correctlyTobias Grosser2013-05-161-1/+7
| | | | | | | | | | When the Polly code generation was written we did not correctly update the LoopInfo data, but still claimed that the loop information is correct. This does not only lead to missed optimizations, but it can also cause miscompilations in case passes such as LoopSimplify are run after Polly. Reported-by: Sergei Larin <slarin@codeaurora.org> llvm-svn: 181987
* LoopGenerators: Construct loops such that they are already loop rotatedTobias Grosser2013-05-161-10/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | BeforeBB | v GuardBB / \ __ PreHeaderBB \ / \ / | latch HeaderBB | \ / \ / < \ / \ / ExitBB This does not only remove the need for an explicit loop rotate pass, but it also gives us the possibility to skip the construction of the guard condition in case the loop is known to be executed at least once. We do not yet exploit this, but by implementing this analysis in the isl code generator we should be able to remove more guards than the generic loop rotate pass can. Another point is that loop rotation can introduce additional PHI nodes, which may hide that a loop can be executed in parallel. This change avoids this complication and will make it easier to move the openmp code generation into a separate pass. llvm-svn: 181986
* Sort includesTobias Grosser2013-05-071-8/+6
| | | | llvm-svn: 181297
* Reformat with clang-formatTobias Grosser2013-05-071-21/+27
| | | | | | | clang-format become way more stable. This time we mainly reformat function signatures. llvm-svn: 181294
OpenPOWER on IntegriCloud