summaryrefslogtreecommitdiffstats
path: root/polly/lib
Commit message (Collapse)AuthorAgeFilesLines
* [ScopBuilder] scalar-indep: Fix mutually referencing PHIs.Michael Kruse2018-02-121-0/+39
| | | | | | | | | | | | | | Two or more PHIs mutually using each other directly or indirectly as incoming value could cause that a PHI WRITE be added before the PHI READ (i.e. it overwrites the current incoming value with the next incoming value before it being read). Fix by ensuring that the PHI WRITE and PHI READ are in the same statement. This should fix the miscompile of SingleSource/Benchmark/Misc/whetstone from the test-suite. llvm-svn: 324934
* [ScopBuilder] Make -polly-stmt-granularity=scalar-indep the default.Michael Kruse2018-02-031-1/+1
| | | | | | | | | | | | | | | | | | | | Splitting basic blocks into multiple statements if there are now additional scalar dependencies gives more freedom to the scheduler, but more statements also means higher compile-time complexity. Switch to finer statement granularity, the additional compile time should be limited by the number of operations quota. The regression tests are written for the -polly-stmt-granularity=bb setting, therefore we add that flag to those tests that break with the new default. Some of the tests only fail because the statements are named differently due to a basic block resulting in multiple statements, but which are removed during simplification of statements without side-effects. Previous commits tried to reduce this effect, but it is not completely avoidable. Differential Revision: https://reviews.llvm.org/D42151 llvm-svn: 324169
* [ScopInfo] Allow epilogues to be the main statement of a BB.Michael Kruse2018-02-031-1/+4
| | | | | | | | | | Do not add a "_last" suffix to the statement name if there is no (other) main statement for a basic block. In other words, it becomes the main statement itself. This further reduces the statement naming difference between -polly-stmt-granularity=bb and -polly-stmt-granularity=scalar-indep. llvm-svn: 324168
* Run clang-format after r324003. NFC.Michael Kruse2018-02-023-8/+12
| | | | llvm-svn: 324112
* Update polly for r323999.Benjamin Kramer2018-02-013-10/+10
| | | | llvm-svn: 324003
* [ScopBuilder] Prefer PHI Write accesses in the statement the incoming value ↵Michael Kruse2018-01-232-66/+30
| | | | | | | | | | | | | | | | | | is defined. Theoretically, a PHI write can be added to any statement that represents the incoming basic block. We previously always chose the last because the incoming value's definition is guaranteed to be defined. With this patch the PHI write is added to the statement that defines the incoming value. It avoids the requirement for a scalar dependency between the defining statement and the statement containing the write. As such the logic for -polly-stmt-granularity=scalar-indep that ensures that there is such scalar dependencies can be removed. Differential Revision: https://reviews.llvm.org/D42147 llvm-svn: 323284
* [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
OpenPOWER on IntegriCloud