summaryrefslogtreecommitdiffstats
path: root/polly/lib/CodeGen/IslNodeBuilder.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Update for alloca construction changesMatt Arsenault2017-04-111-2/+4
| | | | llvm-svn: 299905
* [Polly][NewPM] Pull references to the legacy PM interface from utilities and ↵Philip Pfaffe2017-04-041-2/+2
| | | | | | | | | | | | | | | | | | | | | helpers Summary: A couple of the utilities used to analyze or build IR make explicit use of the legacy PM on their interface, to access analysis results. This patch removes the legacy PM from the interface, and just passes the required results directly. This shouldn't introduce any function changes, although the API technically allowed to obtain two different analysis results before, one passed by reference and one through the PM. I don't believe that was ever intended, however. Reviewers: grosser, Meinersbur Reviewed By: grosser Subscribers: nemanjai, pollydev, llvm-commits Tags: #polly Differential Revision: https://reviews.llvm.org/D31653 llvm-svn: 299423
* Introduce another level of metadata to distinguish non-aliasing accessesRoman Gareev2017-03-221-0/+4
| | | | | | | | | | | | | | Introduce another level of alias metadata to distinguish the individual non-aliasing accesses that have inter iteration alias-free base pointers marked with "Inter iteration alias-free" mark nodes. It can be used to, for example, distinguish different stores (loads) produced by unrolling of the innermost loops and, subsequently, sink (hoist) them by LICM. Reviewed-by: Tobias Grosser <tobias@grosser.es> Differential Revision: https://reviews.llvm.org/D30606 llvm-svn: 298510
* Map the new load to the base pointer of the invariant load hoisted loadRoman Gareev2017-03-221-0/+3
| | | | | | | | | | | Map the new load to the base pointer of the invariant load hoisted load to be able to find the alias information for it. Reviewed-by: Tobias Grosser <tobias@grosser.es> Differential Revision: https://reviews.llvm.org/D30605 llvm-svn: 298507
* [CodeGen] Remove need for all parameters to be in scop context for load ↵Tobias Grosser2017-03-181-6/+14
| | | | | | | | | | | hoisting. When not adding constraints on parameters using -polly-ignore-parameter-bounds, the context may not necessarily list all parameter dimensions. To support code generation in this situation, we now always iterate over the actual parameter list, rather than relying on the context to list all parameter dimensions. llvm-svn: 298197
* Remove all references to PostDominators. NFC.Michael Kruse2017-02-231-1/+0
| | | | | | | | | Marking a pass as preserved is necessary if any Polly pass uses it, even if it is not preserved within the generated code. Not marking it would cause the the Polly pass chain to be interrupted. It is not used by any Polly pass anymore, hence we can remove all references to it. llvm-svn: 295983
* Update to recent formatting changesTobias Grosser2017-02-011-6/+4
| | | | llvm-svn: 293756
* [Polly] [BlockGenerator] Unify ScalarMap and PhiOpsMapTobias Grosser2017-01-281-6/+2
| | | | | | | | | | | | | | | | | | | | | | | | | Instead of keeping two separate maps from Value to Allocas, one for MemoryType::Value and the other for MemoryType::PHI, we introduce a single map from ScopArrayInfo to the corresponding Alloca. This change is intended, both as a general simplification and cleanup, but also to reduce our use of MemoryAccess::getBaseAddr(). Moving away from using getBaseAddr() makes sure we have only a single place where the array (and its base pointer) for which we generate code for is specified, which means we can more easily introduce new access functions that use a different ScopArrayInfo as base. We already today experiment with modifiable access functions, so this change does not address a specific bug, but it just reduces the scope one needs to reason about. Another motivation for this patch is https://reviews.llvm.org/D28518, where memory accesses with different base pointers could possibly be mapped to a single ScopArrayInfo object. Such a mapping is currently not possible, as we currently generate alloca instructions according to the base addresses of the memory accesses, not according to the ScopArrayInfo object they belong to. By making allocas ScopArrayInfo specific, a mapping to a single ScopArrayInfo object will automatically mean that the same stack slot is used for these arrays. For D28518 this is not a problem, as only MemoryType::Array objects are mapping, but resolving this inconsistency will hopefully avoid confusion. llvm-svn: 293374
* Relax assert when setting access functions with invariant base pointersTobias Grosser2017-01-171-2/+0
| | | | | | | | | | | | | | | | | | | | | | | | | Summary: Instead of forbidding such access functions completely, we verify that their base pointer has been hoisted and only assert in case the base pointer was not hoisted. I was trying for a little while to get a test case that ensures the assert is correctly fired in case of invariant load hoisting being disabled, but I could not find a good way to do so, as llvm-lit immediately aborts if a command yields a non-zero return value. As we do not generally test our asserts, not having a test case here seems OK. This resolves http://llvm.org/PR31494 Suggested-by: Michael Kruse <llvm@meinersbur.de> Reviewers: efriedma, jdoerfert, Meinersbur, gareevroman, sebpop, zinob, huihuiz, pollydev Reviewed By: Meinersbur Differential Revision: https://reviews.llvm.org/D28798 llvm-svn: 292213
* Adjust formatting to commit r292110 [NFC]Tobias Grosser2017-01-161-2/+3
| | | | llvm-svn: 292123
* Align newly created arrays to the first level cache line boundaryRoman Gareev2016-12-211-2/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Aligning data to cache lines boundaries helps to avoid overheads related to an access to it ([1]). This patch aligns newly created arrays and adds an option to specify the first level cache line size. By default we use 64 bytes, which is a typical cache-line size ([2]). 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 12.63 GFlops/sec (43,8542% of theoretical peak). Refs.: [1] - http://www.alexonlinux.com/aligned-vs-unaligned-memory-access [2] - http://igoro.com/archive/gallery-of-processor-cache-effects/ Differential Revision: https://reviews.llvm.org/D28020 Reviewed-by: Tobias Grosser <tobias@grosser.es> llvm-svn: 290253
* Add newline at end of debug printTobias Grosser2016-12-011-5/+5
| | | | | | | | In '[DBG] Allow to emit the RTC value at runtime' the diagnostics were printed without a newline at the end of each diagnostic. We add such a newline to improve readability. llvm-svn: 288323
* canSynthesize: Remove unused argument LI. NFC.Michael Kruse2016-11-291-2/+1
| | | | | | | The helper function polly::canSynthesize() does not directly use the LoopInfo analysis, hence remove it from its argument list. llvm-svn: 288144
* Update for clang-format change in r288119Tobias Grosser2016-11-291-4/+5
| | | | llvm-svn: 288134
* [CodeGen] Add flag to code-generate most memory access expressionsTobias Grosser2016-11-221-2/+25
| | | | | | | | | | | | | | Introduce the new flag -polly-codegen-generate-expressions which forces Polly to code generate AST expressions instead of using our SCEV based access expression generation even for cases where the original memory access relation was not changed and the SCEV based access expression could be code generated without any issue. This is an experimental option for better testing the isl ast expression generation. The default behavior of Polly remains unchanged. We also exclude a couple of cases for which the AST expression is not yet working. llvm-svn: 287694
* [NFC] Adjust naming scheme of statistic variablesJohannes Doerfert2016-11-181-2/+2
| | | | | Suggested-by: Tobias Grosser <tobias@grosser.es> llvm-svn: 287347
* [DBG] Collect statistics about actually versioned SCoPsJohannes Doerfert2016-11-171-0/+8
| | | | llvm-svn: 287267
* [DBG] Allow to emit the RTC value at runtimeJohannes Doerfert2016-11-171-0/+16
| | | | | | | | The new command line flag "polly-codegen-emit-rtc-print" can be used to place a "printf" in the generated code that will print the RTC value and the overflow state. llvm-svn: 287265
* IslNodeBuilder: Ensure newly generated memory accesses are well-definedTobias Grosser2016-11-051-0/+18
| | | | | | | Add some additional asserts that ensure newly code-generated memory accesses are defined on all domain and schedule domain instances. llvm-svn: 286050
* [Polly CodeGen] Break critical edge from RTC to original loop.Eli Friedman2016-11-021-1/+2
| | | | | | | | | | | | | | | This makes polly generate a CFG which is closer to what we want in LLVM IR, with a loop preheader for the original loop. This is just a cleanup, but it exposes some fragile assumptions. I'm not completely happy with the changes related to expandCodeFor; RTCBB->getTerminator() is basically a random insertion point which happens to work due to the way we generate runtime checks. I'm not sure what the right answer looks like, though. Differential Revision: https://reviews.llvm.org/D26053 llvm-svn: 285864
* Handle multi-dimensional invariant load.Eli Friedman2016-10-171-0/+19
| | | | | | | If the address of a load depends on another load, make sure to emit the loads in the right order. llvm-svn: 284426
* [CodeGen] Add assertion for indirect array index expression generation. NFC.Michael Kruse2016-09-301-0/+3
| | | | | | | | | | | Currently Polly cannot generate code for index expressions if the base pointer is computed within the scop. The base pointer must be generated as well, but there is no code that triggers that. Add an assertion to detect when this would occur and miscompile. The IR verifier should catch it as well. llvm-svn: 282893
* Perform copying to created arrays according to the packing transformationRoman Gareev2016-09-141-5/+27
| | | | | | | | | | | | | | | | 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-1/+5
| | | | | | | | | | | | | 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
* IslNodeBuilder: Add missing __isl_take annotationTobias Grosser2016-09-091-2/+2
| | | | llvm-svn: 281034
* IslNodeBuilder: Add missing __isl_take annotationsTobias Grosser2016-09-081-2/+3
| | | | llvm-svn: 280936
* Drop '@brief' from doxygen commentsTobias Grosser2016-09-021-6/+6
| | | | | | | | 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
* Fix compilation in 'asserts' modeTobias Grosser2016-08-081-1/+1
| | | | llvm-svn: 278025
* [IslNodeBuilder] Move run-time check generation to NodeBuilder [NFC]Tobias Grosser2016-08-081-0/+17
| | | | | | | This improves the structure of the code and allows us to reuse the runtime code generation in the PPCGCodeGeneration. llvm-svn: 278017
* [IslNodeBuilder] Directly use the insert location of our BuilderTobias Grosser2016-08-081-1/+14
| | | | | | | | | ... instead of adding instructions at the end of the basic block the builder is currently at. This makes it easier to reason about where IR is generated, as with the IRBuilder there is just a single location that specificies where IR is generated. llvm-svn: 278013
* GPGPU: Handle scalar array referencesTobias Grosser2016-08-041-12/+4
| | | | | | | Pass the content of scalar array references to the alloca on the kernel side and do not pass them additional as normal LLVM scalar value. llvm-svn: 277699
* Fix a couple of spelling mistakesTobias Grosser2016-08-031-3/+3
| | | | llvm-svn: 277569
* Extend the jscop interface to allow the user to declare new arrays and to ↵Roman Gareev2016-07-301-0/+26
| | | | | | | | | | | | | | | | reference these arrays from access expressions Extend the jscop interface to allow the user to export arrays. It is required that already existing arrays of the list of arrays correspond to arrays of the SCoP. Each array that is appended to the list will be newly created. Furthermore, we allow the user to modify access expressions to reference any array in case it has the same element type. Reviewed-by: Tobias Grosser <tobias@grosser.es> Differential Revision: https://reviews.llvm.org/D22828 llvm-svn: 277263
* IslNodeBuilder: expose addReferencesFromStmt [NFC]Tobias Grosser2016-07-211-11/+1
| | | | | | | This will be used by Polly GPGPU to determine the values that need to be passed to GPU kernels. llvm-svn: 276269
* Fix gcc compile failureTobias Grosser2016-07-111-1/+1
| | | | | | | | | Commit r275056 introduced a gcc compile failure due to us using two types named 'Type', the first being the newly introduced member variable 'Type' the second being llvm::Type. We resolve this issue by renaming the newly introduced member variable to AccessType. llvm-svn: 275057
* InvariantEquivClassTy: Use struct instead of 4-tuple to increase readabilityTobias Grosser2016-07-111-5/+5
| | | | | | | | | | | | | | Summary: With a struct we can use named accessors instead of generic std::get<3>() calls. This increases readability of the source code. Reviewers: jdoerfert Subscribers: pollydev, llvm-commits Differential Revision: http://reviews.llvm.org/D21955 llvm-svn: 275056
* This reverts recent expression type changesTobias Grosser2016-06-111-6/+31
| | | | | | | | | | | | | | | | | | | | | 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
* Use minimal types for generated expressionsJohannes Doerfert2016-06-061-1/+5
| | | | | | | | | | | | We now use the minimal necessary bit width for the generated code. If operations might overflow (add/sub/mul) we will try to adjust the types in order to ensure a non-wrapping computation. If the type adjustment is not possible, thus the necessary type is bigger than the type value of --polly-max-expr-bit-width, we will use assumptions to verify the computation will not wrap. However, for run-time checks we cannot build assumptions but instead utilize overflow tracking intrinsics. llvm-svn: 271878
* [Polly] Fix -Wunused-variable warnings (NFC)Matthew Simpson2016-06-021-2/+0
| | | | llvm-svn: 271518
* Simplify the type adjustment in the IslExprBuilderJohannes Doerfert2016-06-021-30/+3
| | | | | | | | | We now have a simple function to adjust/unify the types of two (or three) operands before an operation that requieres the same type for all operands. Due to this change we will not promote parameters that are added to i64 anymore if that is not needed. llvm-svn: 271513
* Use the SCoP directly for canSynthesize [NFC]Johannes Doerfert2016-05-231-3/+3
| | | | llvm-svn: 270429
* Duplicate part of the Region interface in the Scop class [NFC]Johannes Doerfert2016-05-231-3/+2
| | | | | | | This allows to use the SCoP directly for various queries, thus to hide the underlying region more often. llvm-svn: 270426
* Add and use Scop::contains(Loop/BasicBlock/Instruction) [NFC]Johannes Doerfert2016-05-231-6/+5
| | | | llvm-svn: 270424
* [FIX] Let ScalarEvolution forget hoisted valuesJohannes Doerfert2016-05-231-0/+5
| | | | | | | We have to rethink the handling of escaping values in order to make this kind of "fixes" go away. llvm-svn: 270409
* Check overflows in RTCs and bail accordinglyJohannes Doerfert2016-05-121-0/+6
| | | | | | | | | | | | | | | We utilize assumptions on the input to model IR in polyhedral world. To verify these assumptions we version the code and guard it with a runtime-check (RTC). However, since the RTCs are themselves generated from the polyhedral representation we generate them under the same assumptions that they should verify. In other words, the guarantees that we try to provide with the RTCs do not hold for the RTCs themselves. To this end it is necessary to employ a different check for the RTCs that will verify the assumptions did hold for them too. Differential Revision: http://reviews.llvm.org/D20165 llvm-svn: 269299
* Simplify access relation for invariant loads early [NFC]Johannes Doerfert2016-05-101-1/+2
| | | | llvm-svn: 269046
* Prevent complex access ranges with low number of pieces.Johannes Doerfert2016-05-101-3/+15
| | | | | | | | | | | Previously we checked the number of pieces to decide whether or not a invariant load was to complex to be generated. However, there are cases when e.g., divisions cause the complexity to spike regardless of the number of pieces. To this end we now check the number of totally involved dimensions which will increase with the number of pieces but also the number of divisions. llvm-svn: 269045
* Rename Conjuncts -> Disjunctions. NFC.Michael Kruse2016-05-021-2/+2
| | | | | | | | The check for complexity compares the number of polyhedra in a set, which are combined by disjunctions (union, "OR"), not conjunctions (intersection, "AND"). llvm-svn: 268223
* [FIX] Propagate execution domain of invariant loadsJohannes Doerfert2016-04-271-7/+15
| | | | | | | | | | | If the base pointer of an invariant load is is loaded conditionally, that condition needs to hold for the invariant load too. The structure of the program will imply this for domain constraints but not for imprecisions in the modeling. To this end we will propagate the execution context of base pointers during code generation and thus ensure the derived pointer does not access an invalid base pointer. llvm-svn: 267707
* Collect and verify generated parallel subfunctionsJohannes Doerfert2016-04-081-0/+3
| | | | | | | | We verify the optimized function now for a long time and it helped to track down bugs early. This will now also happen for all parallel subfunctions we generate. llvm-svn: 265823
OpenPOWER on IntegriCloud