summaryrefslogtreecommitdiffstats
path: root/polly/lib/CodeGen/IslExprBuilder.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Apply include-what-you-use #include removal suggestions. NFC.Michael Kruse2019-03-281-2/+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
* [IslExprBuilder] Do not generate RTC with more than 64 bitTobias Grosser2017-09-231-0/+26
| | | | | | | | | | Such RTCs may introduce integer wrapping intrinsics with more than 64 bit, which are translated to library calls on AOSP that are not part of the runtime and will consequently cause linker errors. Thanks to Eli Friedman for reporting this issue and reducing the test case. llvm-svn: 314065
* Move ScopArrayInfo::getFromAccessFunction and getFromId to isl++Tobias Grosser2017-07-241-1/+1
| | | | llvm-svn: 308892
* Fix a lot of typos. NFC.Michael Kruse2017-06-081-3/+3
| | | | llvm-svn: 304974
* [IslExprBuilder] Print accessed memory locations with RuntimeDebugBuilderTobias Grosser2017-03-181-0/+11
| | | | | | | | | | | | | | | | | | | After this change, enabling -polly-codegen-add-debug-printing in combination with -polly-codegen-generate-expressions allows us to instrument the compiled binaries to not only print the values stored and loaded to a given memory access, but also to print the accessed location with array name and per-dimension offset: MemRef_A[3][2] Store to 6299784: 5.000000 MemRef_A[3][3] Load from 6299788: 0.000000 MemRef_A[3][3] Store to 6299788: 6.000000 This can be very helpful for debugging. llvm-svn: 298194
* [Polly CodeGen] Break critical edge from RTC to original loop.Eli Friedman2016-11-021-3/+5
| | | | | | | | | | | | | | | 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
* Turn cl::values() (for enum) from a vararg function to using C++ variadic ↵Mehdi Amini2016-10-081-2/+1
| | | | | | | | | | | | | | | template The core of the change is supposed to be NFC, however it also fixes what I believe was an undefined behavior when calling: va_start(ValueArgs, Desc); with Desc being a StringRef. Differential Revision: https://reviews.llvm.org/D25342 llvm-svn: 283671
* Drop '@brief' from doxygen commentsTobias Grosser2016-09-021-1/+1
| | | | | | | | 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
* GPGPU: Support scalars that are mapped to shared memoryTobias Grosser2016-08-041-1/+6
| | | | llvm-svn: 277726
* IslExprBuilder: allow to specify an external isl_id to ScopArrayInfo mappingTobias Grosser2016-07-211-1/+12
| | | | | | | | | This is useful for external users using IslExprBuilder, in case they cannot embed ScopArrayInfo data into their isl_ids, because the isl_ids either already carry other information or the isl_ids have been created and their user pointers cannot be updated any more. llvm-svn: 276268
* Recommit: "Simplify min/max expression generation"Tobias Grosser2016-06-121-21/+16
| | | | | | | | | | | | | | As part of this simplification we pull complex logic out of the loop body and skip the previously redundantly executed first loop iteration. This is a partial recommit of r271514 and r271535 which where in conflict with the revert in r272483 and consequently also had to be reverted temporarily. The original patch was contributed by Johannes Doerfert. This patch is mostly a NFC, but dropping the first loop iteration can sometimes result in slightly simpler code. llvm-svn: 272502
* This reverts recent expression type changesTobias Grosser2016-06-111-143/+163
| | | | | | | | | | | | | | | | | | | | | 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
* Refactor division generation codeJohannes Doerfert2016-06-061-26/+46
| | | | | | | | | This patch refactors the code generation for divisions. This allows to always generate a shift for a power-of-two division and to utilize information about constant divisors in order to truncate the result type. llvm-svn: 271898
* Use minimal types for generated expressionsJohannes Doerfert2016-06-061-38/+59
| | | | | | | | | | | | 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
* Fix modulo compared to zero.Michael Kruse2016-06-031-1/+1
| | | | | | | | | | | | | | | | In case of modulo compared to zero, we need to do signed modulo operation as unsigned can give different results based on whether the dividend is negative or not. This addresses llvm.org/PR27707 Contributed-by: Chris Jenneisch <chrisj@codeaurora.org> Reviewers: _jdoerfert, grosser, Meinersbur Differential Revision: http://reviews.llvm.org/D20145 llvm-svn: 271707
* Temporarily promote values to i64 againJohannes Doerfert2016-06-021-1/+4
| | | | | | | Operands of binary operations that might overflow will be temporarily promoted to i64 again, though that is not a sound solution for the problem. llvm-svn: 271538
* [NFC] Avoid unnecessary comparison for min/max expressionsJohannes Doerfert2016-06-021-1/+1
| | | | llvm-svn: 271535
* [NFC] Simplify min/max expression generationJohannes Doerfert2016-06-021-22/+8
| | | | llvm-svn: 271514
* Simplify the type adjustment in the IslExprBuilderJohannes Doerfert2016-06-021-82/+32
| | | | | | | | | 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
* [FIX] Ensure wrapping checks for unary expressionsJohannes Doerfert2016-06-021-1/+1
| | | | llvm-svn: 271512
* Check overflows in RTCs and bail accordinglyJohannes Doerfert2016-05-121-9/+125
| | | | | | | | | | | | | | | 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
* Allow pointer expressions in SCEVs again.Johannes Doerfert2016-04-101-83/+33
| | | | | | | | | In r247147 we disabled pointer expressions because the IslExprBuilder did not fully support them. This patch reintroduces them by simply treating them as integers. The only special handling for pointers that is left detects the comparison of two address_of operands and uses an unsigned compare. llvm-svn: 265894
* ScopInfo: Make getDimensionSize better reflect which dimensions carry sizesTobias Grosser2015-11-101-1/+1
| | | | | | | | | | | | | | | In polly the first dimensions of an array as well as all scalars do not carry any size information. This commit makes this explicit in the interface of getDimensionSize. Before this commit getDimensionSize(0) returned the size of the first dimension that carried a size. After this commit getDimensionSize(i) will either return the size of dimension 'i' or assert in case 'i' does not carry a size or does not exist at all. This very same behaviour was already present in getDimensionSizePw(). This commit also adds assertions that ensure getDimensionSizePw() is called appropriately. llvm-svn: 252607
* [FIX] Bail out if there is a dependence cycle between invariant loadsJohannes Doerfert2015-11-071-0/+2
| | | | | | | | | | | | | While the program cannot cause a dependence cycle between invariant loads, additional constraints (e.g., to ensure finite loops) can introduce them. It is hard to detect them in the SCoP description, thus we will only check for them at code generation time. If such a recursion is detected we will bail out the code generation and place a "false" runtime check to guarantee the original code is used. This fixes bug 25443. llvm-svn: 252412
* polly/ADT: Remove implicit ilist iterator conversions, NFCDuncan P. N. Exon Smith2015-11-061-2/+2
| | | | | | | | | | | | | Remove all the implicit ilist iterator conversions from polly, in preparation for making them illegal in ADT. There was one oddity I came across: at line 95 of lib/CodeGen/LoopGenerators.cpp, there was a post-increment `Builder.GetInsertPoint()++`. Since it was a no-op, I removed it, but I admit I wonder if it might be a bug (both before and after this change)? Perhaps it should be a pre-increment? llvm-svn: 252357
* [FIX] Use appropriately sized types for big constantsJohannes Doerfert2015-11-031-1/+7
| | | | llvm-svn: 251869
* Consolidate the different ValueMapTypes we are usingTobias Grosser2015-10-041-1/+2
| | | | | | | | | | There have been various places where llvm::DenseMap<const llvm::Value *, llvm::Value *> types have been defined, but all types have been expected to be identical. We make this more clear by consolidating the different types and use BlockGenerator::ValueMapT wherever there is a need for types to match BlockGenerator::ValueMapT. llvm-svn: 249264
* OpenMP codegen: support generation of multi-dimensional access functionsTobias Grosser2015-09-051-0/+6
| | | | | | | | | | When computing the index expressions for new, multi-dimensional memory accesses these new index expressions may reference original llvm::Values that are not transfered into the OpenMP subfunction. Using GlobalMap we now replace references to such values with the rewritten values that have e.g. been passed to the OpenMP subfunction. llvm-svn: 246923
* Introduce the ScopExpander as a SCEVExpander replacementJohannes Doerfert2015-08-181-3/+4
| | | | | | | | | | | | | | | The SCEVExpander cannot deal with all SCEVs Polly allows in all kinds of expressions. To this end we introduce a ScopExpander that handles the additional expressions separatly and falls back to the SCEVExpander for everything else. Reviewers: grosser, Meinersbur Subscribers: #polly Differential Revision: http://reviews.llvm.org/D12066 llvm-svn: 245288
* Mark sdivs as 'exact' instead of lowering them ourselvesTobias Grosser2015-06-041-8/+1
| | | | | | | | | 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
* Lower signed-divisions without rounding to ashr instructionsTobias Grosser2015-06-031-0/+7
| | | | llvm-svn: 238929
* Only convert power-of-two floor-division with non-negative denominatorTobias Grosser2015-06-031-4/+6
| | | | | | | | | | | | | | | floord(a,b) === a ashr log_2 (b) holds for positive and negative a's, but shifting only makes sense for positive values of b. The previous patch did not consider this as isl currently always produces postive b's. To avoid future surprises, we check that b is positive and only then apply the optimization. We also now correctly check the return value of the dyn-cast. No additional test case, as isl currently does not produce negative denominators. Reported-by: David Majnemer <david.majnemer@gmail.com> llvm-svn: 238927
* Translate power-of-two floor-division into ashrTobias Grosser2015-06-031-0/+5
| | | | | | | | | | | | | | | | | | 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-291-7/+13
| | | | | | | | | 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
* Use base-pointer address space when creating new access functionsTobias Grosser2015-05-201-3/+6
| | | | llvm-svn: 237785
* Add printing and testing to ScopArrayInfoTobias Grosser2015-05-201-2/+2
| | | | | | | | | | | | Being here, we extend the interface to return the element type and not a pointer to the element type. We also provide a function to get the size (in bytes) of the elements stored in this array. We currently still store the element size as an innermost dimension in ScopArrayInfo, which is somehow inconsistent and should be addressed in future patches. llvm-svn: 237779
* Sort include directivesTobias Grosser2015-05-091-2/+0
| | | | | | | | | | Upcoming revisions of isl require us to include header files explicitly, which have previously been already transitively included. Before we add them, we sort the existing includes. Thanks to Chandler for sort_includes.py. A simple, but very convenient script. llvm-svn: 236930
* Sign-extend in case of non-matching bitwidthTobias Grosser2015-04-051-5/+9
| | | | | | | | | | 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
* Assert in isl expression builder if id can not be found [NFC]Tobias Grosser2015-03-101-0/+2
| | | | llvm-svn: 231865
* Add sign-extension during codegen of index expressionsTobias Grosser2015-03-081-2/+8
| | | | | | | | 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
* Add support for conditional 'and' and 'or' expressionsTobias Grosser2015-03-041-2/+63
| | | | | | | No test cases unfortunately as we do not yet generate isl_ast_op_and_then or isl_ast_op_or_else. Those will be added in a later commit. llvm-svn: 231268
* [FIX] Partially fix the pointer negation crashJohannes Doerfert2015-02-021-2/+39
| | | | llvm-svn: 227805
* [FIX] Handle pointer-pointer comparisonsJohannes Doerfert2015-01-291-2/+26
| | | | | | This should fix a problem introduced by r225464. llvm-svn: 227404
* Use types of matching size when generating multi-dimensional address expressionsTobias Grosser2015-01-131-3/+12
| | | | | | | | | | This change ensures that the values that represent the array size of a multi-dimensional access are correctly sign-extended when used to compute a memory address used in the run-time alias check. To make the test case more readable, we name the instructions that we generate. llvm-svn: 225818
* Add support for pointer types in expressionsTobias Grosser2015-01-081-3/+6
| | | | llvm-svn: 225464
* Use explicit StringRef TypeTobias Grosser2015-01-071-1/+1
| | | | | | | | | | We previously used a Twine here, but as pointed out by David Blaikie and Mehdi Amini storing a temporary StringRef in a Twine is not a good idea, as the StringRef will be freed before the Twine is used leaving a Twine that points to uninitialized memory. We now make it explicit that we use a StringRef here. llvm-svn: 225342
* Do not use a const Twine hereTobias Grosser2015-01-071-1/+1
| | | | | | | This has caused segfaults when using Polly in the context of Julia, that are not reproducible on my machine in 'make check-polly'. llvm-svn: 225326
* Update to the latest version of islTobias Grosser2014-12-071-0/+3
| | | | | | | | | | Isl now specifically marks modulo operations that are compared against zero. They can be implemented with the C/LLVM remainder operation. We also update a couple of test cases where the output of isl has slightly changed. llvm-svn: 223607
* [Fix] Non i1 typed select condition for weird pw aff functions.Johannes Doerfert2014-10-071-0/+2
| | | | | | | | | | | | | | | | | | | In case the pieceweise affine function used to create an isl_ast_expr had empty cases (e.g., with contradicting constraints on the parameters), it was possible that the condition of the isl_ast_expr select was not a comparison but a constant (thus of type i64). This patch does two thing: 1) Handle the case the condition of a select is not a i1 type like C. 2) Try to simplify the pieceweise affine functions for the min/max access when we generate runtime alias checks. That step can often remove empty or redundant cases as well as redundant constrains. This fixes bug: http://llvm.org/PR21167 Differential Revision: http://reviews.llvm.org/D5627 llvm-svn: 219208
OpenPOWER on IntegriCloud