summaryrefslogtreecommitdiffstats
path: root/polly/lib
Commit message (Collapse)AuthorAgeFilesLines
...
* [VirtualInst] Derive correct use kind of PHI operands. NFC.Michael Kruse2018-01-231-6/+26
| | | | | | | | | | VirtualUse::create is only called for MemoryKind::Value, but its consistency nonetheless checked in verifyUses(). PHI uses are always inter-stmt dependencies, which was not considered by the constructor method. The virtual and non-virtual execution paths were the same, such that verifyUses did not encounter any inconsistencies. llvm-svn: 323283
* [ScopBuilder] Revise statement naming when there are multiple statements per BB.Michael Kruse2018-01-181-17/+47
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | The goal is to have -polly-stmt-granularity=bb and -polly-stmt-granularity=scalar-indep to have the same names if there is just one statement per basic block. This fixes a fluke when Polybench's jacobi-2d is optimized differently depending on the -polly-stmt-granularity option, although both options create the same SCoP, just with different statement names. The new naming scheme is: With -polly-use-llvm-names=0: Stmt<BBIdx as decimal><Idx within BB as letter> With -polly-use-llvm-names=1: Stmt_BBName_<Idx within BB as letter> The <Idx within BB> suffix is omitted for the main statement of a BB. The main statement is either the one containing the first store or call (those cannot be removed by the simplifyer), or if there is no such instruction, the first. If after simplification there is just a single statement left, it should be the main statement and have the same names as with -polly-stmt-granularity=bb. Differential Revision: https://reviews.llvm.org/D42136 llvm-svn: 322852
* [ScopInfo] Pass name to ScopStmt ctor. NFC.Michael Kruse2018-01-182-25/+45
| | | | | | | | This will give control of the statement's name to the caller. Required to give -polly-stmt-granularity=scalar-indep more control over the name of the generated statement in a follow-up commit. llvm-svn: 322851
* [polly] [ScopInfo] Don't use isl_val_get_num_si.Eli Friedman2018-01-171-3/+7
| | | | | | | | | | | | | | | | | isl_val_get_num_si crashes on overflow, so don't use it on arbitrary integers. Testcase only crashes on platforms where long is 32 bits because of the signature of isl_val_get_num_si; not sure if it's possible to write a testcase which crashes if long is 64 bits. There are a few other places in polly which use isl_val_get_num_si; they probably need to be fixed as well. I don't think polly uses any of the other "long" isl APIs in an unsafe manner. Differential Revision: https://reviews.llvm.org/D42129 llvm-svn: 322766
* [IslTools] dumpPw: Dump same structure pieces together.Michael Kruse2018-01-161-21/+44
| | | | | | | | | | | | | | | | | | | | | | Print same or similar structure elements together. Previously, the value could take more importance that the space structure if visited first in the space nest tree. Before: { Left[0] -> Right[i]: i >= 0; Left[1] -> AnotherRight[i]; Left[2] -> Right[-1] } After: { Left[0] -> Right[i]: i >= 0; Left[2] -> Right[-1]; Left[1] -> AnotherRight[i] } llvm-svn: 322581
* [CMake] Use only keyword-version of target_link_library. NFC.Michael Kruse2018-01-122-8/+8
| | | | | | | | | | | | | | | | | | | | | | | | | CMake insists that for each target, one uses only the non-keyword version of target_link_library target_link_library(mytarget lib) or the one with PUBLIC/PRIVATE/INTERFACE keyword: target_link_library(mytarget PUBLIC lib) Otherwise, CMake fails with the error message: The keyword signature for target_link_libraries has already been used with the target "mytarget". All uses of target_link_libraries with a target must be either all-keyword or all-plain. Change all occurances of target_link_library to the newer keyworded version to avoid such errors. Some already have been changed in r319840, but might not be sufficient for all build configurations to build the doxygen manual. Reported-by: Tanya Lattner <tanyalattner@llvm.org> llvm-svn: 322376
* [CodeGen] Fix noalias annotations for memcpy/memmove.Michael Kruse2017-12-221-0/+6
| | | | | | | | | | | | | | | | Memory transfer instructions take two pointers. It is not defined to which of those a noalias annotation applies. To ensure correctness, do not add noalias annotations to memcpy/memmove instructions anymore. The caused a miscompile with test-suite's MultiSource/Applications/obsequi. Since r321138, the MemCpyOpt pass would remove memcpy/memmove calls if known to copy uninitialized memory. In that case, it was initialized by another memcpy, but the annotation for the target pointer said it would not alias. The annotation was actually meant for the source pointer, which was was an alloca and could not alias with the target pointer. llvm-svn: 321371
* [ScopBuilder] Split statements on encountering store instructions.Michael Kruse2017-12-111-4/+10
| | | | | | | | | | Introduce -polly-stmt-granularity=store option. Contributed-by: Nandini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D37337 llvm-svn: 320360
* [ScopBuilder] Fix typo. NFC.Michael Kruse2017-12-101-4/+4
| | | | | | | | Contributed-by: Nandini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D41047 llvm-svn: 320336
* [NFC] Fix formattingPhilip Pfaffe2017-12-061-4/+2
| | | | llvm-svn: 319973
* Port SCEVAffinator to the isl c++ bindingsPhilip Pfaffe2017-12-062-113/+84
| | | | | | | | | | | | | | Summary: Straight forward port of SCEVAffinator Reviewers: grosser, bollu, Meinersbur Reviewed By: Meinersbur Subscribers: pollydev, llvm-commits Differential Revision: https://reviews.llvm.org/D40803 llvm-svn: 319958
* Update to latest clang-format. [NFC]Siddharth Bhat2017-12-051-3/+3
| | | | | | Differential Revision: https://reviews.llvm.org/D40791 llvm-svn: 319718
* Handle Top-Level-Regions in polly::isHoistableLoadPhilip Pfaffe2017-11-301-3/+9
| | | | | | | | | | | | | | | | | | | | Summary: This can be seen as a follow-up on my previous differential [D33411](https://reviews.llvm.org/D33411). We received a bug report where this error was triggered. I have tried my best to recreate the issue in a minimal lit testcase which is also part of this differential. I only handle return instructions as predecessors to a virtual TLR-exit right now. From inspecting the codebase, it seems `unreachable` instructions may also be of interest here. If requested, I can extend my patches to consider them as well. I would also apply this on `ScopHelper.cpp::isErrorBlock` (see D33411), of course. Reviewers: philip.pfaffe, bollu Reviewed By: bollu Subscribers: Meinersbur, pollydev, llvm-commits Tags: #polly Differential Revision: https://reviews.llvm.org/D40492 llvm-svn: 319431
* Update format after clang-format change. NFC.Michael Kruse2017-11-301-3/+3
| | | | | | In r319314 clang-format changed its reflowing logic. llvm-svn: 319426
* [MaximalStaticExpansion] Simplify this code a bit. NFCI.Davide Italiano2017-11-251-6/+2
| | | | llvm-svn: 318988
* [CodeGen] Detect empty domain because of parameters context.Michael Kruse2017-11-211-0/+2
| | | | | | | | | | | | | | | | | | | Isl does not allow generating isl_ast_expr from an isl_pw_aff that has an empty domain (i.e. has no pieces). We already detected the case if the isl_pw_aff comes with an empty domain. isl_ast_build also considers the domain empty if it is disjoint with the parameter context (e.g. parameters values that we exclude by runtime versioning). Intersect the access relation domain with the parameter context to also detect such practically empty access domains. The effective pointer used in the generated code is unimportand because it will never be executed. This fixes llvm.org/PR35362 llvm-svn: 318806
* Run polly-update-format. NFC.Michael Kruse2017-11-216-10/+10
| | | | | | | 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-1910-252/+182
| | | | | | | | | | | | | | | | | | | | | 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
* [NFC] Make r318597 compatible with clang-formatZhaoshi Zheng2017-11-171-1/+1
| | | | llvm-svn: 318561
* [nfc] Iwyu: forward-declare/include raw_ostream in zone algoPhilip Pfaffe2017-11-171-0/+1
| | | | llvm-svn: 318517
* [SI] Fix a potential use-after-freePhilip Pfaffe2017-11-161-14/+17
| | | | | | | | | | | | | | | | | | | Summary: There is a potential use-after-free bug in Scop::buildSchedule(Region *, LoopStackTy &, LoopInfo &). Before, we took a reference to LoopStack.back() which is a use after free, since back is popped off further below. This didn't crash before by pure chance, since LoopStack is actually a vector, and the memory isn't freed upon pop. I turned this into an iterator-based algorithm. Reviewers: grosser, bollu, Meinersbur Reviewed By: Meinersbur Subscribers: llvm-commits, pollydev Differential Revision: https://reviews.llvm.org/D39979 llvm-svn: 318415
* [polly] Remove redundant return [NFC]Mandeep Singh Grang2017-11-101-1/+0
| | | | | | | | | | | | | | Reviewers: grosser, bollu Reviewed By: grosser Subscribers: nemanjai, kbarton, llvm-commits Tags: #polly Differential Revision: https://reviews.llvm.org/D39916 llvm-svn: 317922
* [ForwardOpTree] Limit isl operations of known content reload.Michael Kruse2017-11-061-1/+8
| | | | | | | | | | Put the analysis part of reloadKnownContent under an isl max-operations quota scope, as has already been done for forwardKnownLoad. This should fix the aosp timeout of "GrTestUtils.cpp". llvm-svn: 317495
* [Analysis] update to use new fast-math API - isFast()Sanjay Patel2017-11-061-2/+2
| | | | llvm-svn: 317491
* [ZoneAlgo/ForwardOpTree] Normalize PHIs to their known incoming values.Michael Kruse2017-10-313-54/+307
| | | | | | | | | | | | | | | | | | | | | | | Represent PHIs by their incoming values instead of an opaque value of themselves. This allows ForwardOpTree to "look through" the PHIs and forward the incoming values since forwardings PHIs is currently not supported. This is particularly useful to cope with PHIs inserted by GVN LoadPRE. The incoming values all resolve to a load from a single array element which then can be forwarded. It should in theory also reduce spurious conflicts in value mapping (DeLICM), but I have not yet found a profitable case yet, so it is not included here. To avoid transitive closure and potentially necessary overapproximations of those, PHIs that may reference themselves are excluded from normalization and keep their opaque self-representation. Differential Revision: https://reviews.llvm.org/D39333 llvm-svn: 317008
* [DeLICM] Fix wrong assumed access execution order.Michael Kruse2017-10-311-1/+1
| | | | | | | | | | | | | | ForwardOpTree may already transform a scalar access to an array accesses. The access remains implicit (isOriginalScalarKind(), meaning that the access is always executed at the begin/end of a statement), but targets an array (isLatestArrayKind(), which is unrelated to whether the execution is implicit/explicit). Fix by properly using isOriginalXXX() to determine execution order. This fixes the buildbots on MultiSource/Benchmarks/DOE-ProxyApps-C/miniGMG. llvm-svn: 316995
* [OpenMP] Fix reference collection of latest base ptrs.Michael Kruse2017-10-311-1/+1
| | | | | | | | When collecting base pointers that need to be made available in parallel subfunctions, use the base pointer associated with the latest ScopArrayInfo, instead of the original one. llvm-svn: 316983
* [Acc] Do not statically dispatch into IslNodeBuilder's createForPhilip Pfaffe2017-10-292-8/+13
| | | | | | | | | | | | | | | | | | | | Summary: When GPUNodeBuilder creates loops inside the kernel, it dispatches to IslNodeBuilder. This however is surprisingly dangerous, since it accesses the AST Node's user through the wrong type. This patch fixes this problem by overriding createFor correctly. This fixes PR35010. Reviewers: grosser, bollu, Meinersbur Reviewed By: Meinersbur Subscribers: Meinersbur, nemanjai, pollydev, llvm-commits, kbarton Differential Revision: https://reviews.llvm.org/D39364 llvm-svn: 316872
* [ForwardOpTree] Use space indention. NFC.Michael Kruse2017-10-271-1/+1
| | | | llvm-svn: 316769
* [ForwardOpTree] Reload know values.Michael Kruse2017-10-271-32/+124
| | | | | | | | | | | | | | For scalar accesses, change the access target to an array element that is known to contain the same value. This may become an alternative to forwardKnownLoad which creates new loads (and therefore closer to forwarding speculatives). Reloading does not require the known value originating from a load, but can be a store as well. Differential Revision: https://reviews.llvm.org/D39325 llvm-svn: 316766
* [Simplify] Mark (and sweep) based on latest access relation.Michael Kruse2017-10-261-2/+2
| | | | | | | | | Previously we marked scalars based on the original access function. However, when a scalar read access is redirected, the original definition (or incoming values of a PHI) is not used anymore, and can be deleted (unless referenced by use that has not been redirected). llvm-svn: 316660
* [ZoneAlgo] Translate addArrayWriteAccess to isl++. NFC.Michael Kruse2017-10-241-11/+7
| | | | llvm-svn: 316459
* [ISLTools] Translate computeReachingWrite to isl++. NFC.Michael Kruse2017-10-241-24/+17
| | | | llvm-svn: 316445
* [DeLICM] Do not try to map to multiple array elements.Michael Kruse2017-10-241-14/+26
| | | | | | | | | | | | | | | | | Add check and skip when the store used to determine the target accesses multiple array elements. Only a single array location should for mapping the scalar. Having multiple creates problems when deciding which element to load from. While MemoryAccess::getAddressFunction() should select just one of them, other problems arise in code that assumes that there is just one target element per statement instance. This fixes llvm.org/PR34989 This also reverts r313902 which fixed llvm.org/PR34485 also caused by a non-functional target array element. This patch avoids the situation to occur in the first place. llvm-svn: 316432
* Rename OptimizationDiagnosticInfo.h to OptimizationRemarkEmitter.hAdam Nemet2017-10-096-6/+6
| | | | | | Polly version of r315249 on LLVM trunk. llvm-svn: 315253
* [ScopBuilder] Introduce -polly-stmt-granularity=scalar-indep option.Michael Kruse2017-10-051-2/+180
| | | | | | | | | | | | | | | | | | | | | | | | | The option splits BasicBlocks into minimal statements such that no additional scalar dependencies are introduced. The algorithm is based on a union-find structure, and unites sets if putting them into separate statements would introduce a scalar dependencies. As a consequence, instructions may be split into separate statements such their relative order is different than the statements they are in. This is accounted for instructions whose relative order matters (e.g. memory accesses). The algorithm is generic in that heuristic changes can be made relatively easily. We might relax the order requirement for read-reads or accesses to different base pointers. Forwardable instructions can be made to not cause a join. This implementation gives us a speed-up of 82% in SPEC 2006 456.hmmer benchmark by allowing loop-distribution in a hot loop such that one of the loops can be vectorized. Differential Revision: https://reviews.llvm.org/D38403 llvm-svn: 314983
* [ScopBuilder] Introduce -polly-stmt-granularity option. NFC.Michael Kruse2017-10-041-16/+33
| | | | | | | | | | The option is introduced with only one possible value -polly-stmt-granularity=bb which represents the current behaviour, which is outlined into the new function buildSequentialBlockStmts(). More options will be added in future commits. llvm-svn: 314900
* [GPGPU] Make sure escaping invariant load hoisted scalars are preservedTobias Grosser2017-10-041-1/+3
| | | | | | | | | | | | | | | We make sure that the final reload of an invariant scalar memory access uses the same stack slot into which the invariant memory access was stored originally. Earlier, this was broken as we introduce a new stack slot aside of the preload stack slot, which remained uninitialized and caused our escaping loads to contain garbage. This happened due to us clearing the pre-populated values in EscapeMap after kernel code generation. We address this issue by preserving the original host values and restoring them after kernel code generation. EscapeMap is not expected to be used during kernel code generation, hence we clear it during kernel generation to make sure that any unintended uses are noticed. llvm-svn: 314894
* [ScopBuilder] Iterate over statement instructions. NFC.Michael Kruse2017-10-021-39/+28
| | | | | | | | | Iterate over statement instructions instead over basic block instructions when creating MemoryAccesses. It allows making the creation of MemoryAccesses independent of how the basic blocks are split into multiple ScopStmts. llvm-svn: 314665
* [ScopBuilder] Build invariant loads separately.Michael Kruse2017-10-021-3/+47
| | | | | | | | | | | | | | | | | | Create the MemoryAccesses of invariant loads separately and before all other MemoryAccesses. Invariant loads are classified as synthesizable and therefore are not contained in any statement. When iterating over all instructions of all statements, the invariant loads are consequently not processed and iterating over them separately becomes necessary. This patch can change the order in which MemoryAccesses are created, but otherwise has no functional change. Some temporary code is introduced to ensure correctness, but will be removed in the next commit. llvm-svn: 314664
* [ScopBuilder] Build escaping dependencies separately.Michael Kruse2017-10-021-2/+9
| | | | | | | | | | | | | Instructions that compute escaping values might be synthesizable and therefore not contained in any ScopStmt. When buildAccessFunctions is changed to only iterate over the instruction list of statement, "free" instructions still need to be written. We do this after the main MemoryAccesses have been created. This can change the order in which MemoryAccesses are created, but has otherwise no functional change. llvm-svn: 314663
* [ScopBuilder] Specialize exit block handling. NFC.Michael Kruse2017-10-021-15/+15
| | | | | | | | | | | Decouple handling of exit block PHIs and other MemoryAccesses. Exit PHIs only need the PHI handling part of buildAccessFunctions but requires code for skipping them in while creating other MemoryAcesses. This change will make it easier to modify how statement MemoryAccesses are created without considering the exit block special case. llvm-svn: 314662
* [ForwardOpTree] Fix out-of-quota in assertion.Michael Kruse2017-10-021-1/+1
| | | | llvm-svn: 314661
* [ScopDetect] Do not add loads out of the SCoP to required invariant loads.Michael Kruse2017-10-011-1/+1
| | | | | | | | | | | | | | | | Loads before the SCoP are always invariant within the SCoP and therefore are no "required invariant loads". An assertion failes in ScopBuilder when it finds such an invariant load. Fix by not adding such loads to the required invariant load list. This likely will cause the region to be not considered a valid SCoP. We may want to unconditionally accept instructions defined before the region as valid invariant conditions instead of rejecting them. This fixes a compilation crash of SPEC CPU2006 453.povray's render.cpp. llvm-svn: 314636
* [GPGPU] Set Polly's RTC to false in case invariant load hoisting failsTobias Grosser2017-10-011-0/+6
| | | | | | | | | | | This matches the behavior we already have in lib/Codegen/CodeGeneration.cpp and makes sure that we fall back to the original code. It seems when invariant load hoisting was introduced to the GPGPU backend we missed to reset the RTC flag, such that kernels where invariant load hoisting failed executed the 'optimized' SCoP, which however is set to a simple 'unreachable'. Unsurprisingly, this results in hard to debug issues that are a lot of fun to debug. llvm-svn: 314624
* [Polly] Add dumpPw() and dumpExpanded() functions. NFC.Michael Kruse2017-09-292-43/+339
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | These functions print a multi-line and sorted representation of unions of polyhedra. Each polyhedron (basic_{ast/map}) has its own line. First sort key is the polyhedron's hierachical space structure. Secondary sort key is the lower bound of the polyhedron, which should ensure that the polyhedral are printed in approximately ascending order. Example output of dumpPw(): [p_0, p_1, p_2] -> { Stmt0[0] -> [0, 0]; Stmt0[i0] -> [i0, 0] : 0 < i0 <= 5 - p_2; Stmt1[0] -> [0, 2] : p_1 = 1 and p_0 = -1; Stmt2[0] -> [0, 1] : p_1 >= 3 + p_0; Stmt3[0] -> [0, 3]; } In contrast dumpExpanded() prints each point in the sets, unless there is an unbounded dimension that cannot be expandend. This is useful for reduced test cases where the loop counts are set to some constant to understand a bug. Example output of dumpExpanded( { [MemRef_A[i0] -> [i1]] : (exists (e0 = floor((1 + i1)/3): i0 = 1 and 3e0 <= i1 and 3e0 >= -1 + i1 and i1 >= 15 and i1 <= 25)) or (exists (e0 = floor((i1)/3): i0 = 0 and 3e0 < i1 and 3e0 >= -2 + i1 and i1 > 0 and i1 <= 11)) }): { [MemRef_A[0] ->[1]]; [MemRef_A[0] ->[2]]; [MemRef_A[0] ->[4]]; [MemRef_A[0] ->[5]]; [MemRef_A[0] ->[7]]; [MemRef_A[0] ->[8]]; [MemRef_A[0] ->[10]]; [MemRef_A[0] ->[11]]; [MemRef_A[1] ->[15]]; [MemRef_A[1] ->[16]]; [MemRef_A[1] ->[18]]; [MemRef_A[1] ->[19]]; [MemRef_A[1] ->[21]]; [MemRef_A[1] ->[22]]; [MemRef_A[1] ->[24]]; [MemRef_A[1] ->[25]] } Differential Revision: https://reviews.llvm.org/D38349 llvm-svn: 314525
* [ScopBuilder] Fix typo. NFC.Michael Kruse2017-09-291-2/+2
| | | | | | | | Contributed-by: Nandini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D38322 llvm-svn: 314519
* Fix the build after r314375Philip Pfaffe2017-09-282-2/+2
| | | | | | r314375 privatized Loop's constructor and replaced it with an Allocator. llvm-svn: 314412
* [Support] Force instantiation of isl dump() methods. NFC.Michael Kruse2017-09-281-0/+57
| | | | | | | | | | | | | | | | In order for debuggers to be able to call an inline method, it must have been instantiated somewhere. The dump() methods are usually not used, so add an instantiation in debug builds. This allows to call .dump() on any isl++ object from the gcc/gdb and Visual Studio debugger in debug builds with assertions enabled. In optimized builds, even with assertions enabled, the dump() methods are also inlined in GICHelper.cpp, so no externally visible symbols will be available either. Differential Revision: https://reviews.llvm.org/D38198 llvm-svn: 314395
* [ScopInfo] Allow PHI nodes that reference an error blockTobias Grosser2017-09-261-2/+11
| | | | | | As long as these PHI nodes are only referenced by terminator instructions. llvm-svn: 314212
OpenPOWER on IntegriCloud