summaryrefslogtreecommitdiffstats
path: root/polly/lib/CodeGen/IslAst.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [ScheduleOptimizer] Hoist extension nodes after schedule optimization.Michael Kruse2019-05-311-6/+0
| | | | | | | | | | | | | | | | | | | | | | Extension nodes make schedule trees are less flexible: Many operations, such as rescheduling, do not work on such schedule trees with extension. As such, some functionality such as determining parallel loops in isl's AST are disabled. Currently, only the pattern-matching generalized matrix-matrix multiplication optimization adds extension nodes (to add copy-in statements). This patch removes all extension nodes as the last step of the schedule optimization by hoisting the extension node's added domain up to the root domain node. All following passes can assume that schedule trees work without restrictions, including the parallelism test. Mark the outermost loop of the optimized matrix-matrix multiplication as parallel such that -polly-parallel is able to parallelize that loop. Differential Revision: https://reviews.llvm.org/D58202 llvm-svn: 362257
* Apply include-what-you-use #include removal suggestions. NFC.Michael Kruse2019-03-281-7/+0
| | | | | | | | | | | | This removes unused includes (and forward declarations) as suggested by include-what-you-use. If a transitive include of a removed include is required to compile a file, I added the required header (or forward declaration if suggested by include-what-you-use). This should reduce compilation time and reduce the number of iterative recompilations when a header was changed. llvm-svn: 357209
* Update the file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-191-4/+3
| | | | | | | | | | | | | | | | | to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351636
* [IslAst] Fix InParallelFor nesting.Michael Kruse2018-09-271-20/+18
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | IslAst could mark two nested outer loops as "OutermostParallel". It caused that the code generator tried to OpenMP-parallelize both loops, which it is not prepared loop. It was because the recursive AST build algorithm managed a flag "InParallelFor" to ensure that no nested loop is also marked as "OutermostParallel". Unfortunatetly the same flag was used by nodes marked as SIMD, and reset to false after the SIMD node. Since loops can be marked as SIMD inside "OutermostParallel" loops, the recursive algorithm again tried to mark loops as "OutermostParellel" although still nested inside another "OutermostParallel" loop. The fix exposed another bug: The function "astScheduleDimIsParallel" was only called when a loop was potentially "OutermostParallel" or "InnermostParallel", but as a side-effect also determines the minimum dependence distance. Hence, changing when we need to know whether a loop is "OutermostParallel" also changed which loop was annotated with "#pragma minimal dependence distance". Moreover, some complex condition linked with "InParallelFor" determined whether a loop should be an "InnermostParallel" loop. It missed some situations where it would not use mark as such although being inside an SIMD mark node, and therefore not be annotated using "#pragma simd". The changes in particular: 1. Split the "InParallelFor" flag into an "InParallelFor" and an "InSIMD" flag. 2. Unconditionally call "astScheduleDimIsParallel" for its side-effects and store the result in "InParallel" for later use. 3. Simplify the condition when a loop is "InnermostParallel". Fixes llvm.org/PR33153 and llvm.org/PR38073. llvm-svn: 343212
* getDependences to new C++ interfaceTobias Grosser2018-06-061-4/+8
| | | | | | | | | | | | | | Reviewers: Meinersbur, grosser, bollu, cs15btech11044, jdoerfert Reviewed By: grosser Subscribers: pollydev, llvm-commits Tags: #polly Differential Revision: https://reviews.llvm.org/D47786 llvm-svn: 334092
* [polly] Update uses of DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-151-3/+4
| | | | | | | | | | | The DEBUG() macro is very generic so it might clash with other projects. The renaming was done as follows: - git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g' - git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM Differential Revision: https://reviews.llvm.org/D44978 llvm-svn: 332352
* [Polly][IslAst] Fix minimal dependence distance.Huihui Zhang2018-04-041-2/+7
| | | | | | | | | | | | | | | | | | | Summary: When checking the parallelism of a scheduling dimension, we first check if excluding reduction dependences the loop is parallel or not. If the loop is not parallel, then we need to return the minimal dependence distance of all data dependences, including the previously subtracted reduction dependences. Reviewers: grosser, Meinersbur, efriedma, eli.friedman, jdoerfert, bollu Reviewed By: Meinersbur Subscribers: llvm-commits, pollydev Tags: #polly Differential Revision: https://reviews.llvm.org/D45236 llvm-svn: 329214
* Adjust to clang-format changesTobias Grosser2018-03-201-1/+0
| | | | llvm-svn: 328005
* Use isl::manage_copy to simplify calls to isl::manage(isl_.._copy())Tobias Grosser2018-02-201-7/+4
| | | | | | | | | | | As part of this cleanup a couple of unnecessary isl::manage(obj.copy()) pattern are eliminated as well. We checked for all potential cleanups by scanning for: "grep -R isl::manage\( lib/ | grep copy" llvm-svn: 325558
* Run polly-update-format. NFC.Michael Kruse2017-11-211-1/+1
| | | | | | | polly-check-format has been failing since at least r318517, due to more than one cause. llvm-svn: 318795
* Port ScopInfo to the isl cpp bindingsPhilip Pfaffe2017-11-191-12/+11
| | | | | | | | | | | | | | | | | | | | | Summary: Most changes are mechanical, but in one place I changed the program semantics by fixing a likely bug: In `Scop::hasFeasibleRuntimeContext()`, I'm now explicitely handling the error-case. Before, when the call to `addNonEmptyDomainConstraints()` returned a null set, this (probably) accidentally worked because isl_bool_error converts to true. I'm checking for nullptr now. Reviewers: grosser, Meinersbur, bollu Reviewed By: Meinersbur Subscribers: nemanjai, kbarton, pollydev, llvm-commits Differential Revision: https://reviews.llvm.org/D39971 llvm-svn: 318632
* Check whether IslAstInfo and DependenceInfo were computed for the same Scop.Michael Kruse2017-09-211-1/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | Since -polly-codegen reports itself to preserve DependenceInfo and IslAstInfo, we might get those analysis that were computed by a different ScopInfo for a different Scop structure. This would be unfortunate because DependenceInfo and IslAstInfo hold references to resources allocated by ScopInfo/ScopBuilder/Scop (e.g. isl_id). If -polly-codegen and DependenceInfo/IslAstInfo do not agree on which Scop to use, unpredictable things can happen. When the ScopInfo/Scop object is freed, there is a high probability that the new ScopInfo/Scop object will be created at the same heap position with the same address. Comparing whether the Scop or ScopInfo address is the expected therefore is unreliable. Instead, we compare the address of the isl_ctx object. Both, DependenceInfo and IslAstInfo must hold a reference to the isl_ctx object to ensure it is not freed before the destruction of those analyses which might happen after the destruction of the Scop/ScopInfo they refer to. Hence, the isl_ctx will not be freed and its address not reused as long there is a DependenceInfo or IslAstInfo around. This fixes llvm.org/PR34441 llvm-svn: 313842
* [IslAst] Do not assert in case of empty min/max alias locationsTobias Grosser2017-09-031-15/+45
| | | | | | | | | | | | | In certain situations, the context in the isl_ast_build could result for the min/max locations of our alias sets to become empty, which would cause an internal error in isl, which is then unable to derive a value for these expressions. Check these conditions before code generating expressions and instead assume that alias check succeeded. This is valid, as the corresponding memory accesses will not be executed under any valid context. This fixed llvm.org/PR34432. Thanks to Qirun Zhang for reporting. llvm-svn: 312455
* [IslAst] Move buildCondition to isl++Tobias Grosser2017-09-031-26/+28
| | | | llvm-svn: 312452
* [IslAst] Do not compare arrays in alias check which are known to be identicalTobias Grosser2017-08-281-0/+14
| | | | | | This possibly helps to avoid run-time check failures in the COSMO kernels. llvm-svn: 311920
* [PM] Properly require and preserve OptimizationRemarkEmitter. NFCI.Michael Kruse2017-08-281-0/+2
| | | | | | | | | | | | | | | | | | | | | | Properly require and preserve the OptimizationRemarkEmitter for use in ScopPass. Previously one had to get the ORE from ScopDetection because CodeGeneration did not mark it as preserved. It would need to be recomputed which results in the legacy PM to throw away all previous SCoP analysis. This also changes the implementation of ScopPass::getAnalysisUsage to not unconditionally preserve all passes, but only those needed to be preserved by any SCoP pass (at least when using the legacy PM). This allows invalidating DependenceInfo (and IslAstInfo) in case the pass would cause them to change (e.g. OpTree, DeLICM, MaximalArrayExpansion) JSONImporter should also invalidate the DependenceInfo. In this patch it marks DependenceInfo as preserved anyway because some regression tests depend on it. Differential Revision: https://reviews.llvm.org/D37010 llvm-svn: 311888
* [Polly] Fix some Clang-tidy modernize and Include What You Use warnings; ↵Eugene Zelenko2017-08-241-31/+41
| | | | | | other minor fixes (NFC). llvm-svn: 311704
* Add more statistics.Michael Kruse2017-08-231-0/+56
| | | | | | | | | | | | | | | | Add statistics about - Which optimizations are applied - Number of loops in Scops at various stages - Number of scalar/singleton writes at various stages representative for scalar false dependencies - Number of parallel loops These will be useful to find regressions due to moving Polly further down of LLVM's pass pipeline. Differential Revision: https://reviews.llvm.org/D37049 llvm-svn: 311553
* [ScopInfo] Move Scop::getPwAffOnly to isl++ [NFC]Tobias Grosser2017-08-061-3/+3
| | | | llvm-svn: 310231
* [ScopInfo] Move Scop::getInvalidContext to isl++ [NFC]Tobias Grosser2017-08-061-1/+2
| | | | llvm-svn: 310229
* [ScopInfo] Move Scop::getAssumedContext to isl++ [NFC]Tobias Grosser2017-08-061-1/+2
| | | | llvm-svn: 310228
* [ScopInfo] Translate Scop::getParamSpace to isl++ [NFC]Tobias Grosser2017-08-061-1/+2
| | | | llvm-svn: 310224
* [ScopInfo] Translate Scop::getContext to isl++ [NFC]Tobias Grosser2017-08-061-1/+1
| | | | llvm-svn: 310221
* Move applyScheduleToAccessRelation to isl++Tobias Grosser2017-07-231-1/+1
| | | | llvm-svn: 308842
* [IslAst] Print memory accesses in AST dumpTobias Grosser2017-07-101-0/+60
| | | | | | | | | | | | | | | | | | | | When providing the option "-polly-ast-print-accesses" Polly also prints the memory accesses that are generated: #pragma known-parallel for (int c0 = 0; c0 <= 1023; c0 += 4) #pragma simd for (int c1 = c0; c1 <= c0 + 3; c1 += 1) Stmt_for_body( /* read */ &MemRef_B[0] /* write */ MemRef_A[c1] ); This makes writing and debugging memory layout transformations easier. Based on a patch contributed by Thomas Lang (ETH Zurich) llvm-svn: 307579
* Introduce a hybrid target to generate code for either the GPU or CPUSingapuram Sanjay Srivallabh2017-06-301-0/+5
| | | | | | | | | | | | | | | | | | | | | Summary: Introduce a "hybrid" `-polly-target` option to optimise code for either the GPU or CPU. When this target is selected, PPCGCodeGeneration will attempt first to optimise a Scop. If the Scop isn't modified, it is then sent to the passes that form the CPU pipeline, i.e. IslScheduleOptimizerPass, IslAstInfoWrapperPass and CodeGeneration. In case the Scop is modified, it is marked to be skipped by the subsequent CPU optimisation passes. Reviewers: grosser, Meinersbur, bollu Reviewed By: grosser Subscribers: kbarton, nemanjai, pollydev Tags: #polly Differential Revision: https://reviews.llvm.org/D34054 llvm-svn: 306863
* Fix a lot of typos. NFC.Michael Kruse2017-06-081-2/+2
| | | | llvm-svn: 304974
* [Polly][NewPM] Port IslAst to the new ScopPassManagerPhilip Pfaffe2017-05-231-52/+70
| | | | | | | | | | | | | | | | Summary: This patch ports IslAst to the new PM. The change is mostly straightforward. The only major modification required is making IslAst move-only, to correctly manage the isl resources it owns. Reviewers: grosser, Meinersbur Reviewed By: grosser Subscribers: nemanjai, pollydev, llvm-commits Tags: #polly Differential Revision: https://reviews.llvm.org/D33422 llvm-svn: 303622
* [NFC] [IslAST] fix typo: "int the" -> "in the"Siddharth Bhat2017-05-021-1/+1
| | | | llvm-svn: 301925
* Disable the parallel code generation in case of extension nodesRoman Gareev2017-02-271-0/+8
| | | | | | | | | | | We can not perform the dependence analysis and, consequently, the parallel code generation in case the schedule tree contains extension nodes. Reviewed-by: Tobias Grosser <tobias@grosser.es> Differential Revision: https://reviews.llvm.org/D30394 llvm-svn: 296325
* [IslAst] Print the ScopArray name to mark reductionsTobias Grosser2017-02-091-1/+1
| | | | | | | | | | | | | Before this change we used the name of the base pointer to mark reductions. This is imprecise as the canonical reference is the ScopArray itself and not the basepointer of a reduction. Using the base pointer of reductions is problematic in cases where a single ScopArray is referenced through two different base pointers. This change removes unnecessary uses of MemoryAddress::getBaseAddr() in preparation for https://reviews.llvm.org/D28518. llvm-svn: 294568
* IslAst: always use the context during ast generationTobias Grosser2016-11-101-1/+1
| | | | | | | | | | | | | | | | | | | Providing the context to the ast generator allows for additional simplifcations and -- more importantly -- allows to generate loops with only partially bounded domains, assuming the domains are bounded for all parameter configurations that are valid as defined by the context. This change fixes the crash reported in http://llvm.org/PR30956 The original reason why we did not include the context when generating an AST was that CLooG and later isl used to sometimes transfer some of the constraints that bound the size of parameters from the context into the generated AST. This resulted in operations with very large constants, which sometimes introduced problematic integer overflows. The latest versions of the isl AST generator are careful to not introduce such constants. Reported-by: Eli Friedman <efriedma@codeaurora.org> llvm-svn: 286442
* Perform copying to created arrays according to the packing transformationRoman Gareev2016-09-141-3/+2
| | | | | | | | | | | | | | | | This is the fourth patch to apply the BLIS matmul optimization pattern on matmul kernels (http://www.cs.utexas.edu/users/flame/pubs/TOMS-BLIS-Analytical.pdf). BLIS implements gemm as three nested loops around a macro-kernel, plus two packing routines. The macro-kernel is implemented in terms of two additional loops around a micro-kernel. The micro-kernel is a loop around a rank-1 (i.e., outer product) update. In this change we perform copying to created arrays, which is the last step to implement the packing transformation. Reviewed-by: Tobias Grosser <tobias@grosser.es> Differential Revision: https://reviews.llvm.org/D23260 llvm-svn: 281441
* Drop '@brief' from doxygen commentsTobias Grosser2016-09-021-11/+11
| | | | | | | | LLVM's coding guideline suggests to not use @brief for one-sentence doxygen comments to improve readability. Switch this once and for all to ensure people do not copy @brief comments from other parts of Polly, when writing new code. llvm-svn: 280468
* isl: isl-0.17.1-164-gcbba1b6Tobias Grosser2016-07-061-1/+1
| | | | | | | | | | | This is a regular maintenance update to ensure the latest version of isl is tested. Interesting Changes: - AST nodes and expressions are now printed as YAML llvm-svn: 274614
* clang-tidy: Add llvm namespace commentsTobias Grosser2016-06-231-1/+1
| | | | | | | | | | | | | | | | | | | | | | | llvm commonly adds a comment to the closing brace of a namespace to indicate which namespace is closed. clang-tidy provides with llvm-namespace-comment a handy tool to check for this habit. We use it to ensure we consitently use namespace comments in Polly. There are slightly different styles in how namespaces are closed in LLVM. As there is no large difference between the different comment styles we go for the style clang-tidy suggests by default. To reproduce this fix run: for i in `ls tools/polly/lib/*/*.cpp`; \ clang-tidy -checks='-*,llvm-namespace-comment' -p build $i -fix \ -header-filter=".*"; \ done This cleanup was suggested by Eugene Zelenko <eugene.zelenko@gmail.com> in http://reviews.llvm.org/D21488 and was split out to increase readability. llvm-svn: 273621
* This reverts recent expression type changesTobias Grosser2016-06-111-4/+14
| | | | | | | | | | | | | | | | | | | | | 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
* [NFC] Generate runtime checks after the SCoPJohannes Doerfert2016-06-061-14/+4
| | | | | | | | | 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
* Decouple SCoP building logic from passJohannes Doerfert2016-05-311-2/+2
| | | | | | | | | | | | | | | | Created a new pass ScopInfoRegionPass. As name suggests, it is a region pass and it is there to preserve compatibility with our existing Polly passes. ScopInfoRegionPass will return a SCoP object for a valid region while the creation of the SCoP stays in the ScopInfo class. Contributed-by: Utpal Bora <cs14mtech11017@iith.ac.in> Reviewed-by: Tobias Grosser <tobias@grosser.es>, Johannes Doerfert <doerfert@cs.uni-saarland.de> Differential Revision: http://reviews.llvm.org/D20770 llvm-svn: 271259
* Directly access information through the Scop class [NFC]Johannes Doerfert2016-05-231-3/+2
| | | | llvm-svn: 270421
* Codegen: Enable the detection of min/max expressionsTobias Grosser2016-05-071-0/+1
| | | | | | | | | 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
* Add __isl_give annotations to return types [NFC]Johannes Doerfert2016-04-091-2/+3
| | | | llvm-svn: 265882
* Add namespace for struct [NFC]Johannes Doerfert2016-03-241-10/+12
| | | | | | This will clean up the doxygen documentation. llvm-svn: 264272
* Allow the client of DependenceInfo to obtain dependences at different ↵Hongbin Zheng2016-03-031-1/+2
| | | | | | granularities. llvm-svn: 262591
* Track assumptions and restrictions separatlyJohannes Doerfert2016-03-011-2/+9
| | | | | | | | | | | | | | | In order to speed up compile time and to avoid random timeouts we now separately track assumptions and restrictions. In this context assumptions describe parameter valuations we need and restrictions describe parameter valuations we do not allow. During AST generation we create a runtime check for both, whereas the one for the restrictions is negated before a conjunction is build. Except the In-Bounds assumptions we currently only track restrictions. Differential Revision: http://reviews.llvm.org/D17247 llvm-svn: 262328
* IslAst: Expose run-time check generation as individual functionTobias Grosser2016-02-261-2/+7
| | | | | | | | This allows to construct run-time checks for a scop without having to generate a full AST. This is currently not taken advantage of in Polly itself, but external users may benefit from this feature. llvm-svn: 262009
* Annotation of SIMD loopsRoman Gareev2016-02-231-4/+37
| | | | | | | | | | | | | | | | | | | | | | | | | | | Use 'mark' nodes annotate a SIMD loop during ScheduleTransformation and skip parallelism checks. The buildbot shows the following compile/execution time changes: Compile time: Improvements Δ Previous Current σ …/gesummv -6.06% 0.2640 0.2480 0.0055 …/gemver -4.46% 0.4480 0.4280 0.0044 …/covariance -4.31% 0.8360 0.8000 0.0065 …/adi -3.23% 0.9920 0.9600 0.0065 …/doitgen -2.53% 0.9480 0.9240 0.0090 …/3mm -2.33% 1.0320 1.0080 0.0087 Execution time: Regressions Δ Previous Current σ …/viterbi 1.70% 5.1840 5.2720 0.0074 …/smallpt 1.06% 12.4920 12.6240 0.0040 Reviewed-by: Tobias Grosser <tobias@grosser.es> Differential Revision: http://reviews.llvm.org/D14491 llvm-svn: 261620
* IslAst: Expose IslAst class in header file [NFC]Tobias Grosser2016-02-211-27/+0
| | | | | | | This allows other passes and transformations to use some of the existing AST building infrastructure. This is not yet used in Polly itself. llvm-svn: 261496
* [Refactor] Move isl_ctx into Scop.Hongbin Zheng2016-02-171-1/+4
| | | | | | | | | | | | | | | | | | | | After we moved isl_ctx into Scop, we need to free the isl_ctx after freeing all isl objects, which requires the ScopInfo pass to be freed at last. But this is not guaranteed by the PassManager, and we need extra code to free the isl_ctx at the right time. We introduced a shared pointer to manage the isl_ctx, and distribute it to all analyses that create isl objects. As such, whenever we free an analyses with the shared_ptr (and also free the isl objects which are created by the analyses), we decrease the (shared) reference counter of the shared_ptr by 1. Whenever the reference counter reach 0 in the releaseMemory function of an analysis, that analysis will be the last one that hold any isl objects, and we can safely free the isl_ctx with that analysis. Differential Revision: http://reviews.llvm.org/D17241 llvm-svn: 261100
* Adjust formatting to clang-format changes in 256149Tobias Grosser2015-12-211-1/+1
| | | | llvm-svn: 256151
OpenPOWER on IntegriCloud