summaryrefslogtreecommitdiffstats
path: root/polly/lib/Transform
Commit message (Collapse)AuthorAgeFilesLines
...
* [DeLICM] Statistics for use in regression tests.Michael Kruse2017-02-271-2/+42
| | | | | | | Print some measurements of the DeLICM transformation at -analyze to be used in regression tests. llvm-svn: 296347
* [DeLICM] Fortify against exceeding isl's max operations counter.Michael Kruse2017-02-231-6/+9
| | | | | | | | | | | | | | | | | | | | | | Control flow would flow-through after the check whether the operations quota exceeded, with the intention that it would later be caught by Knowledge::isUsable(). However, the Knowledge constructor has its own assertions to check consistency which would fail if its fields have only been initialized partially because some sets have been computed correctly before the operations quota takes effect. Fix by erroring-out early instead of falling-throught into the code that might expect that everything has been computed correctly. For robustness, also bail-out if any of the fields contain nullptr values instead of relying on isl always setting exactly this error code if something went wrong. This should fix the perf-x86_64-penryn-O3-polly-before-vectorizer-unprofitable (-polly-process-unprofitable -polly-position=before-vectorizer -polly-enable-delicm) buildbot. llvm-svn: 296022
* [Support] Remove NonowningIslPtr. NFC.Michael Kruse2017-02-232-6/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | NonowningIslPtr<isl_X> was used as types of function parameters when the function does not consume the isl object, i.e. an __isl_keep parameter. The alternatives are: 1. IslPtr<isl_X> This has additional calls to isl_X_copy and isl_X_free to increase/decrease the reference counter even though not needed. The caller already owns a reference to the isl object. 2. const IslPtr<isl_X>& This does not change the reference counter, but requires an additional load to get the pointer to the isl object (instead of just passing the pointer itself). Moreover, the compiler cannot rely on the constness of the pointer and has to reload the pointer every time it writes to memory (unless alias analysis such as TBAA says it is not possible). The isl C++ bindings currently in development do not have an equivalent to NonowningIslPtr and adding one would make the binding more complicated and its advantage in performance is small. In order to simplify the transition to these C++ bindings, remove NonowningIslPtr. Change every former use of it to alternative 2 mentioned aboce (const IslPtr<isl_X>&). llvm-svn: 295998
* [DeLICM] Add missing Doxygen comment. NFC.Michael Kruse2017-02-231-0/+1
| | | | llvm-svn: 295978
* [DeLICM] Capitalize parameter name. NFC.Michael Kruse2017-02-231-2/+2
| | | | llvm-svn: 295977
* Make optimizations based on pattern matching be enabled by defaultRoman Gareev2017-02-231-1/+1
| | | | | | | | | | | | | Currently, pattern based optimizations of Polly can identify matrix multiplication and optimize it according to BLIS matmul optimization pattern (see ScheduleTreeOptimizer for details). This patch makes optimizations based on pattern matching be enabled by default. Reviewed-by: Tobias Grosser <tobias@grosser.es> Differential Revision: https://reviews.llvm.org/D30293 llvm-svn: 295958
* [DeLICM] Regression test for skipping map targets.Michael Kruse2017-02-231-0/+14
| | | | | | | Add optimization-remarks-missed for when mapping targets have been skipped and add regression tests for them. llvm-svn: 295953
* [DeLICM] Add regression tests for DeLICM reject cases.Michael Kruse2017-02-221-3/+44
| | | | | | | | | | | | | | | | | These tests were not included in the main DeLICM commit. These check the cases where zone analysis cannot be successful because of assumption violations. We use the LLVM optimization remark infrastructure as it seems to be the best fit for this kind of messages. I tried to make use if the OptimizationRemarkEmitter. However, it would insert additional function passes into the pass manager to get the hotness information. The pass manager would insert them between the flatten pass and delicm, causing the ScopInfo with the flattened schedule being thrown away. Differential Revision: https://reviews.llvm.org/D30253 llvm-svn: 295846
* [DeLICM] Fix wrong comment. NFC.Michael Kruse2017-02-221-1/+1
| | | | | | | Correct a comment that claimed that a store after load was detected when the code checks a load after a store. llvm-svn: 295835
* [DeLICM] Print message when zone analysis is not available on -analysis.Michael Kruse2017-02-221-0/+5
| | | | | | | This is to distinguish the cases that analysis has failed from the case where not transformation was performed. llvm-svn: 295833
* [DeLICM] Use opt<int>.Michael Kruse2017-02-221-1/+1
| | | | | | | | There is no template specialization for cl::parser<unsigned long> such that parsing an cl::opt<unsigned long> command line argument will fail. Use opt<int> instead which has an associated parser. llvm-svn: 295832
* [DeLICM] Map values hoisted by LICM back to the array.Michael Kruse2017-02-211-5/+1249
| | | | | | | | | | | | | | | | | | | | Implement the -polly-delicm pass. The pass intends to undo the effects of LoopInvariantCodeMotion (LICM) which adds additional scalar dependencies into SCoPs. DeLICM will try to map those scalars back to the array elements they were promoted from, as long as the array element is unused. The is the main patch from the DeLICM/DePRE patch series. It does not yet undo GVN PRE for which additional information about known values is needed and does not handle PHI write accesses that have have no target. As such its usefulness is limited. Patches for these issues including regression tests for error situatons will follow. Reviewers: grosser Differential Revision: https://reviews.llvm.org/D24716 llvm-svn: 295713
* [FIX] Fix the typo in ScheduleOptimizer.cpp.Roman Gareev2017-02-161-1/+2
| | | | llvm-svn: 295292
* [DeLICM] Add Knowledge class. NFC.Michael Kruse2017-02-151-0/+363
| | | | | | | | | | | | | | | The Knowledge class remembers the state of data at any timepoint of a SCoP's execution. Currently, it tracks whether an array element is unused or is occupied by some value, and the writes to it. A future addition will be to also remember which value it contains. Objects are used to determine whether two Knowledge contain conflicting information, i.e. two states cannot be true a the same time. This commit was extracted from the DeLICM algorithm at https://reviews.llvm.org/D24716. llvm-svn: 295197
* Check reduction dependencies in case of the matrix multiplication optimizationRoman Gareev2017-02-111-3/+6
| | | | | | | | | | | | | | To determine parameters of the matrix multiplication, we check RAW dependencies that can be expressed using only reduction dependencies. Consequently, we should check the reduction dependencies, if this is the case. Reviewed-by: Tobias Grosser <tobias@grosser.es>, Sven Verdoolaege <skimo-polly@kotnet.org> Michael Kruse <llvm@meinersbur.de> Differential Revision: https://reviews.llvm.org/D29814 llvm-svn: 294836
* [FIX] Fix the potential issue of containsOnlyMatMulDep.Roman Gareev2017-02-111-0/+2
| | | | llvm-svn: 294835
* [NFC] Fix the style issue of lib/Transform/ScheduleOptimizer.cpp.Roman Gareev2017-02-111-2/+1
| | | | llvm-svn: 294834
* [NFC] Fix style issues of lib/Transform/ScheduleOptimizer.cpp.Roman Gareev2017-02-111-9/+6
| | | | llvm-svn: 294831
* Use the size of the widest type of the matrix multiplication operandsRoman Gareev2017-02-111-8/+48
| | | | | | | | | | | | | The size of the operands type is the one of the parameters required to determine the BLIS micro-kernel. We get the size of the widest type of the matrix multiplication operands in case there are several different types. Reviewed-by: Michael Kruse <llvm@meinersbur.de> Differential Revision: https://reviews.llvm.org/D29269 llvm-svn: 294828
* Isolate a set of partial tile prefixes in case of the matrix multiplicationRoman Gareev2017-02-091-6/+72
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | optimization Isolate a set of partial tile prefixes to allow hoisting and sinking out of the unrolled innermost loops produced by the optimization of the matrix multiplication. In case it cannot be proved that the number of loop iterations can be evenly divided by tile sizes and we tile and unroll the point loop, the isl generates conditional expressions. Subsequently, the conditional expressions can prevent stores and loads of the unrolled loops from being sunk and hoisted. The patch isolates a set of partial tile prefixes, which have exactly Mr x Nr iterations of the two innermost loops, the result of the loop tiling performed by the matrix multiplication optimization, where Mr and Mr are parameters of the micro-kernel. This helps to get rid of the conditional expressions of the unrolled innermost loops. Probably this approach can be replaced with padding in future. In case of, for example, the gemm from Polybench/C 3.2 and parametric loop bounds, it helps to increase the performance from 7.98 GFlops (27.71% of theoretical peak) to 21.47 GFlops (74.57% of theoretical peak). Hence, we get the same performance as in case of scalar loops bounds. It also cause compile time regression. The compile-time is increased from 0.795 seconds to 0.837 seconds in case of scalar loops bounds and from 1.222 seconds to 1.490 seconds in case of parametric loops bounds. Reviewed-by: Michael Kruse <llvm@meinersbur.de> Differential Revision: https://reviews.llvm.org/D29244 llvm-svn: 294564
* [NFC] Make ScheduleTreeOptimizer::optimizeBand return a schedule node optimizedRoman Gareev2017-02-081-1/+1
| | | | | | | | | | | | | | with optimizeMatMulPattern This patch makes ScheduleTreeOptimizer::optimizeBand return a schedule node optimized with optimizeMatMulPattern. Otherwise, it could not use the isolate option, because standardBandOpts could try to tile a band node with anchored subtree and get the error, since the use of the isolate option causes any tree containing the node to be considered anchored. Furthermore, it is not intended to apply standard optimizations, when the matrix multiplication has been detected. llvm-svn: 294444
* A new algorithm for identification of a SCoP statement that implement a matrixRoman Gareev2017-02-021-260/+396
| | | | | | | | | | | | | | | | | | | | multiplication The current identification of a SCoP statement that implement a matrix multiplication does not help to identify different permutations of loops that contain it and check for dependencies, which can prevent it from being optimized. It also requires external determination of the operands of the matrix multiplication. This patch contains the implementation of a new algorithm that helps to avoid these issues. It also modifies the test cases that generate matrix multiplications with linearized accesses, because the new algorithm does not support them. Reviewed-by: Michael Kruse <llvm@meinersbur.de>, Tobias Grosser <tobias@grosser.es> Differential Revision: https://reviews.llvm.org/D28357 llvm-svn: 293890
* Update to recent formatting changesTobias Grosser2017-02-011-3/+2
| | | | llvm-svn: 293756
* Update the documentation on how the packing transformation is implementedRoman Gareev2017-01-291-2/+19
| | | | | | | | | | | | Add a simple example to update the documentation on how the packing transformation is implemented. Reviewed-by: Tobias Grosser <tobias@grosser.es>, Michael Kruse <llvm@meinersbur.de> Differential Revision: https://reviews.llvm.org/D28021 llvm-svn: 293429
* [CodePrepa] Remove unused declaration. NFC.Michael Kruse2017-01-271-2/+0
| | | | llvm-svn: 293304
* Adjust formatting to commit r292110 [NFC]Tobias Grosser2017-01-161-5/+8
| | | | llvm-svn: 292123
* ScheduleOptimizer: Allow to set register width in command lineTobias Grosser2017-01-141-1/+11
| | | | | | | We use this option to set a fixed register width in our test cases to make sure the results are identical accross platforms. llvm-svn: 292002
* Specify the default values of the cache parametersRoman Gareev2016-12-251-19/+35
| | | | | | | | | | | | | | | | | If the parameters of the target cache (i.e., cache level sizes, cache level associativities) are not specified or have wrong values, we use ones for parameters of the macro-kernel and do not perform data-layout optimizations of the matrix multiplication. In this patch we specify the default values of the cache parameters to be able to apply the pattern matching optimizations even in this case. Since there is no typical values of this parameters, we use the parameters of Intel Core i7-3820 SandyBridge that also help to attain the high-performance on IBM POWER System S822 and IBM Power 730 Express server. Reviewed-by: Tobias Grosser <tobias@grosser.es> Differential Revision: https://reviews.llvm.org/D28090 llvm-svn: 290518
* ScheduleOptimizer: Fix spelling of option '-polly-target-throughput-vector-fma'Tobias Grosser2016-12-231-4/+4
| | | | | | througput -> throughput llvm-svn: 290418
* Change the determination of parameters of macro-kernelRoman Gareev2016-12-211-1/+10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Typically processor architectures do not include an L3 cache, which means that Nc, the parameter of the micro-kernel, is, for all practical purposes, redundant ([1]). However, its small values can cause the redundant packing of the same elements of the matrix A, the first operand of the matrix multiplication. At the same time, big values of the parameter Nc can cause segmentation faults in case the available stack is exceeded. This patch adds an option to specify the parameter Nc as a multiple of the parameter of the micro-kernel Nr. In case of Intel Core i7-3820 SandyBridge and the following options, clang -O3 gemm.c -I utilities/ utilities/polybench.c -DPOLYBENCH_TIME -march=native -mllvm -polly -mllvm -polly-pattern-matching-based-opts=true -DPOLYBENCH_USE_SCALAR_LB -mllvm -polly-target-cache-level-associativity=8,8 -mllvm -polly-target-cache-level-sizes=32768,262144 -mllvm -polly-target-latency-vector-fma=8 it helps to improve the performance from 11.303 GFlops/sec (39,247% of theoretical peak) to 17.896 GFlops/sec (62,14% of theoretical peak). Refs.: [1] - http://www.cs.utexas.edu/users/flame/pubs/TOMS-BLIS-Analytical.pdf Reviewed-by: Tobias Grosser <tobias@grosser.es> Differential Revision: https://reviews.llvm.org/D28019 llvm-svn: 290256
* [Polly] Use three-dimensional arrays to store packed operands of the matrixRoman Gareev2016-12-211-25/+19
| | | | | | | | | | | | | | | | | | | | | | | | | | | multiplication Previously we had two-dimensional accesses to store packed operands of the matrix multiplication for the sake of simplicity of the packed arrays. However, addition of the third dimension helps to simplify the corresponding memory access, reduce the execution time of isl operations applied to it, and consequently reduce the compile-time of Polly. For example, in case of Intel Core i7-3820 SandyBridge and the following options, clang -O3 gemm.c -I utilities/ utilities/polybench.c -DPOLYBENCH_TIME -march=native -mllvm -polly -mllvm -polly-pattern-matching-based-opts=true -DPOLYBENCH_USE_SCALAR_LB -mllvm -polly-target-cache-level-associativity=8,8 -mllvm -polly-target-cache-level-sizes=32768,262144 -mllvm -polly-target-latency-vector-fma=7 it helps to reduce the compile-time from about 361.456 seconds to about 0.816 seconds. Reviewed-by: Michael Kruse <llvm@meinersbur.de>, Tobias Grosser <tobias@grosser.es> Differential Revision: https://reviews.llvm.org/D27878 llvm-svn: 290251
* Restrict ranges of extension mapsRoman Gareev2016-12-151-1/+20
| | | | | | | | | | | To prevent copy statements from accessing arrays out of bounds, ranges of their extension maps are restricted, according to the constraints of domains. Reviewed-by: Michael Kruse <llvm@meinersbur.de> Differential Revision: https://reviews.llvm.org/D25655 llvm-svn: 289815
* [NFC] Fix typos in getMacroKernelParams.Roman Gareev2016-12-151-5/+3
| | | | llvm-svn: 289808
* The order of the loops defines the data reused in the BLIS implementation ofRoman Gareev2016-12-151-29/+31
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | gemm ([1]). In particular, elements of the matrix B, the second operand of matrix multiplication, are reused between iterations of the innermost loop. To keep the reused data in cache, only elements of matrix A, the first operand of matrix multiplication, should be evicted during an iteration of the innermost loop. To provide such a cache replacement policy, elements of the matrix A can, in particular, be loaded first and, consequently, be least-recently-used. In our case matrices are stored in row-major order instead of column-major order used in the BLIS implementation ([1]). One of the ways to address it is to accordingly change the order of the loops of the loop nest. However, it makes elements of the matrix A to be reused in the innermost loop and, consequently, requires to load elements of the matrix B first. Since the LLVM vectorizer always generates loads from the matrix A before loads from the matrix B and we can not provide it. Consequently, we only change the BLIS micro kernel and the computation of its parameters instead. In particular, reused elements of the matrix B are successively multiplied by specific elements of the matrix A . Refs.: [1] - http://www.cs.utexas.edu/users/flame/pubs/TOMS-BLIS-Analytical.pdf Reviewed-by: Tobias Grosser <tobias@grosser.es> Differential Revision: https://reviews.llvm.org/D25653 llvm-svn: 289806
* [ScheduleOptimizer] Fix memory leak. NFC.Michael Kruse2016-12-121-1/+3
| | | | llvm-svn: 289434
* Rerun mem2reg after the inlinerJohannes Doerfert2016-12-021-0/+1
| | | | | | | | It did happen that after the inliner finished we end up with promotable allocas in a function. We now run mem2reg to make sure everything is promoted if possible. llvm-svn: 288514
* [DeLICM] Add pass boilerplate code.Michael Kruse2016-11-291-0/+70
| | | | | | | | | | Add an empty DeLICM pass, without any functional parts. Extracting the boilerplate from the the functional part reduces the size of the code to review (https://reviews.llvm.org/D24716) Suggested-by: Tobias Grosser <tobias@grosser.es> llvm-svn: 288160
* Perform copying to created arrays according to the packing transformationRoman Gareev2016-09-142-13/+119
| | | | | | | | | | | | | | | | 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
* Store the size of the outermost dimension in case of newly created arrays ↵Roman Gareev2016-09-121-5/+4
| | | | | | | | | | | | | that require memory allocation. We do not need the size of the outermost dimension in most cases, but if we allocate memory for newly created arrays, that size is needed. Reviewed-by: Michael Kruse <llvm@meinersbur.de> Differential Revision: https://reviews.llvm.org/D23991 llvm-svn: 281234
* FlattenAlgo: Ensure we _really_ obtain a param spaceTobias Grosser2016-09-091-1/+2
| | | | | | | This resolves "isl_space.c:1775: not a parameter space" errors I have seen on two systems. llvm-svn: 281052
* Add -polly-flatten-schedule pass.Michael Kruse2016-09-082-0/+525
| | | | | | | | | | | | | | | | | | | | | | | | | The -polly-flatten-schedule pass reduces the number of scattering dimensions in its isl_union_map form to make them easier to understand. It is not meant to be used in production, only for debugging and regression tests. To illustrate, how it can make sets simpler, here is a lifetime set used computed by the porposed DeLICM pass without flattening: { Stmt_reduction_for[0, 4] -> [0, 2, o2, o3] : o2 < 0; Stmt_reduction_for[0, 4] -> [0, 1, o2, o3] : o2 >= 5; Stmt_reduction_for[0, 4] -> [0, 1, 4, o3] : o3 > 0; Stmt_reduction_for[0, i1] -> [0, 1, i1, 1] : 0 <= i1 <= 3; Stmt_reduction_for[0, 4] -> [0, 2, 0, o3] : o3 <= 0 } And here the same lifetime for a semantically identical one-dimensional schedule: { Stmt_reduction_for[0, i1] -> [2 + 3i1] : 0 <= i1 <= 4 } Differential Revision: https://reviews.llvm.org/D24310 llvm-svn: 280948
* Drop '@brief' from doxygen commentsTobias Grosser2016-09-023-32/+30
| | | | | | | | 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
* Add a flag to dump SCoP optimized with the IslScheduleOptimizer passRoman Gareev2016-08-211-0/+10
| | | | | | | | | | | | | Dump polyhedral descriptions of Scops optimized with the isl scheduling optimizer and the set of post-scheduling transformations applied on the schedule tree to be able to check the work of the IslScheduleOptimizer pass at the polyhedral level. Reviewed-by: Tobias Grosser <tobias@grosser.es> Differential Revision: https://reviews.llvm.org/D23740 llvm-svn: 279395
* Perform replacement of access relations and creation of new arrays according ↵Roman Gareev2016-08-151-0/+215
| | | | | | | | | | | | | | | | | | | | to the packing transformation This is the third 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 replacement of the access relations and create empty arrays, which are steps to implement the packing transformation. In subsequent changes we will implement copying to created arrays. Reviewed-by: Tobias Grosser <tobias@grosser.es> Differential Revision: http://reviews.llvm.org/D22187 llvm-svn: 278666
* Fix a couple of spelling mistakesTobias Grosser2016-08-031-1/+1
| | | | llvm-svn: 277569
* Apply all necessary tilings and interchangings to get a macro-kernelRoman Gareev2016-07-251-0/+95
| | | | | | | | | | | | | | | | | | | This is the second 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 create the BLIS macro-kernel by applying a combination of tiling and interchanging. In subsequent changes we will implement the packing transformation. Reviewed-by: Tobias Grosser <tobias@grosser.es> Differential Revision: http://reviews.llvm.org/D21491 llvm-svn: 276627
* [NFC] Refactor creation of the BLIS mirco-kernel and improve documentationRoman Gareev2016-07-251-5/+28
| | | | | Reviewed-by: Tobias Grosser <tobias@grosser.es> llvm-svn: 276616
* Propagate on-error statusTobias Grosser2016-06-301-1/+2
| | | | | | | | | | | | | | | | This ensures that the error status set with -polly-on-isl-error-abort is maintained even after running DependenceInfo and ScheduleOptimizer. Both passes temporarily set the error status to CONTINUE as the dependence analysis uses a compute-out and the scheduler may not be able to derive a schedule. In both cases we want to not abort, but to handle the error gracefully. Before this commit, we always set the error reporting to ABORT after these passes. After this commit, we use the error reporting mode that was active earlier. This comes without a test case as this would require us to introduce (memory) errors which would trigger the isl errors. llvm-svn: 274272
* Simplify: get isl_ctx only once [NFC]Tobias Grosser2016-06-301-10/+11
| | | | | | ... instead of call S.getIslCtx() many times. llvm-svn: 274271
* clang-tidy: Add llvm namespace commentsTobias Grosser2016-06-234-4/+4
| | | | | | | | | | | | | | | | | | | | | | | 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
OpenPOWER on IntegriCloud