summaryrefslogtreecommitdiffstats
path: root/polly/lib
Commit message (Collapse)AuthorAgeFilesLines
...
* Remove keep/take/give from isl C++ bindingsTobias Grosser2018-04-291-816/+0
| | | | | | | | These functions have been legacy leftovers which we used before the official C++ bindings existed. As all uses of these legacy functions have been removed, this polly-specific extension can also be dropped. llvm-svn: 331130
* Remove another set or release() callsTobias Grosser2018-04-293-10/+10
| | | | llvm-svn: 331129
* Remove the last uses of isl::give and isl::takeTobias Grosser2018-04-298-212/+183
| | | | llvm-svn: 331126
* [DeLICM] Remove uses of isl::giveTobias Grosser2018-04-284-90/+58
| | | | llvm-svn: 331122
* [ZoneAlgo] Remove uses of isl::give - IITobias Grosser2018-04-281-13/+8
| | | | llvm-svn: 331121
* [ZoneAlgo] Remove uses of isl::giveTobias Grosser2018-04-281-41/+33
| | | | | | This moves more of Polly to islpp. llvm-svn: 331120
* [MaximalStaticExpansion] Replace copied function with version from ISLToolsTobias Grosser2018-04-281-43/+1
| | | | llvm-svn: 331118
* Update to latest version of the isl c++ bindingsTobias Grosser2018-04-281-1871/+4047
| | | | | | | The delta to the previous version is rather small, but a change in brace placement makes this a rather noisy commit. llvm-svn: 331113
* [CodeGen] Print executed statement instances at runtime.Michael Kruse2018-04-252-0/+128
| | | | | | | | | | | | | Add the options -polly-codegen-trace-stmts and -polly-codegen-trace-scalars. When enabled, adds a call to the beginning of every generated statement that prints the executed statement instance. With -polly-codegen-trace-scalars, it also prints the value of all scalars that are used in the statement, and PHIs defined in the beginning of the statement. Differential Revision: https://reviews.llvm.org/D45743 llvm-svn: 330864
* [ScopDetect] Reject loop with multiple exit blocks.Michael Kruse2018-04-252-0/+38
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The current statement domain derivation algorithm does not (always) consider that different exit blocks of a loop can have different conditions to be reached. From the code for (int i = n; ; i-=2) { if (i <= 0) goto even; if (i <= 1) goto odd; A[i] = i; } even: A[0] = 42; return; odd: A[1] = 21; return; Polly currently derives the following domains: Stmt_even_critedge Domain := [n] -> { Stmt_even_critedge[] }; Stmt_odd Domain := [n] -> { Stmt_odd[] : (1 + n) mod 2 = 0 and n > 0 }; while the domain for the odd case is correct, Stmt_even is assumed to be executed unconditionally, which is obviously wrong. While projecting out the loop dimension in `adjustDomainDimensions`, it does not consider that there are other exit condition that have matched before. I don't know a how to fix this without changing a lot of code. Therefore This patch rejects loops with multiple exist blocks to fix the miscompile of test-suite's uuencode. The odd condition is transformed by LLVM to %cmp1 = icmp eq i64 %indvars.iv, 1 such that the project_out in adjustDomainDimensions() indeed only matches for odd n (using this condition only, we'd have an infinite loop otherwise). The even condition manifests as %cmp = icmp slt i64 %indvars.iv, 3 Because buildDomainsWithBranchConstraints() does not consider other exit conditions, it has to assume that the induction variable will eventually be lower than 3 and taking this exit. IMHO we need to reuse the algorithm that determines the number of iterations (addLoopBoundsToHeaderDomain) to determine which exit condition applies first. It has to happen in buildDomainsWithBranchConstraints() because the result will need to propagate to successor BBs. Currently addLoopBoundsToHeaderDomain() just look for union of all backedge conditions (which means leaving not the loop here). The patch in llvm.org/PR35465 changes it to look for exit conditions instead. This is required because there might be other exit conditions that do not alternatively go back to the loop header. Differential Revision: https://reviews.llvm.org/D45649 llvm-svn: 330858
* Update isl to isl-0.19-114-g385262afTobias Grosser2018-04-2513-41/+248
| | | | llvm-svn: 330800
* Fixup Polly for an LLVM header file change.David Blaikie2018-04-242-0/+2
| | | | llvm-svn: 330679
* Update isl to isl-0.19-107-gc4fe33d8Tobias Grosser2018-04-2188-979/+4985
| | | | | | This is a regular maintenance update. llvm-svn: 330496
* [isl++] abort() on assertion violation.Michael Kruse2018-04-201-0/+1
| | | | | | | | | | | | | | | | Before this patch, ISL_ASSERT only printed an error message to stderr. This can be easily missed if the program continues or just fails later. To fail-early and help error diagnostics (e.g. using bugpoint), call abort() when an assertion does not hold. I seem to just have forgotten to add this abort() when I originally proposed the ISL_ASSERT macro. Suggested-By: Eli Friedman <efriedma@codeaurora.org> Differential Revision: https://reviews.llvm.org/D45171 llvm-svn: 330467
* Allow arbitrary function calls for debugging purposes.Michael Kruse2018-04-204-1/+63
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Add the switch -polly-debug-func to define the name of a debug function. This function is ignored for any validity check. Its purpose is to allow to observe a value after transformation by a SCoP, and to follow which statements are executed in which order. For instance, consider the following code: static void dbg_printf(int sum, int i) { fprintf(stderr, "The value of sum is %d, i=%d\n", sum, i); fflush(stderr); } void func(int n) { int sum = 0; for (int i = 0; i < 16; i+=1) { sum += i; dbg_printf(sum, i); } } Executing this after Polly's codegen with -polly-debug-func=dbg_printf reveals the new execution order and the assumed values at that point of execution. Differential Revision: https://reviews.llvm.org/D45728 llvm-svn: 330466
* [RuntimeDebugBuilder] Do not break for 64 bit integersTobias Grosser2018-04-191-3/+6
| | | | | | | | | In r330292 this assert was turned incorrectly into an unreachable, but the correct behavior (thanks Michael) is to assert for anything that is not 64 bit, but falltrough for 64 bit. I document this in the source code. llvm-svn: 330309
* [RuntimeDebugBuilder] Turn assert into an unreachableTobias Grosser2018-04-181-2/+1
| | | | llvm-svn: 330289
* [ScopDetect / ScopInfo] Get statistics for scops without any loop correctlyTobias Grosser2018-04-182-3/+13
| | | | | | Make sure we also counts scops not containing any loops. llvm-svn: 330285
* [NewPM] Update pass registration for the LLVM plugin interfacePhilip Pfaffe2018-04-171-0/+8
| | | | | | | | | | | | | | | | Summary: As of rL329273, LLVM has a mechanism to load new-pm plugins in opt. Use this API in Polly. Reviewers: grosser, Meinersbur, bollu Reviewed By: grosser, Meinersbur Subscribers: lksbhm, bollu, pollydev, llvm-commits Differential Revision: https://reviews.llvm.org/D45484 llvm-svn: 330181
* Revert r327216 'Add isl operator overloads for isl::pw_aff'Tobias Grosser2018-04-111-1/+0
| | | | | | This commit requires further discussions. llvm-svn: 329825
* [CodeGen] Allow undefined loads in statement instances outside context.Michael Kruse2018-04-102-1/+4
| | | | | | | | | | | | | | | | | | | | A check in assert-builds was meant to verify that a load provides a value in all statement instances (i.e. its domain). The domain is commonly gist'ed within the parameter context to contain fewer constraints. However, statement instances outside the context are no valid executions, hence the value provided can be undefined. Refine the check for valid loads to only needed to be defined within the SCoP context. In addition, the JSONImporter had to be changed to allow importing access relations that are broader than the current access relation, but still defined over all statement instances. This should fix the compiler crash in test-suite's oggenc of the -polly-process-unprofitable buildbot. llvm-svn: 329655
* [CodeGen] Convert BlockGenerator::generateScalarLoads to isl++. NFC.Michael Kruse2018-04-101-5/+3
| | | | llvm-svn: 329654
* [ScopInfo] Avoid iterator invalidation.Michael Kruse2018-04-101-1/+3
| | | | | | | | | | | Commit r329640 introduced the removal of all MemoryAccesses of a Scop. It accidentally continued iterating over a vector whose iterators have been invalidated by a MemoryAccess removal. Make a copy of the MemoryAccesses to remove to iterate over while removing them. llvm-svn: 329653
* [ScopInfo] Completely remove MemoryAccesses when their parent statement is ↵Michael Kruse2018-04-091-10/+18
| | | | | | | | | | | | | | | removed. Removing a statement left its MemoryAccesses in some lists and maps of the SCoP. Which lists depends on at which phase of the SCoP construction the statement is deleted. Follow-up passes could still see the already deleted MemoryAccesses by iterating through these lists/maps, resulting in an access violation. When removing a ScopStmt, also remove all its MemoryAccesses by using the same mechnism that removes a MemoryAccess. llvm-svn: 329640
* [ScopInfo] Actually remove from list.Michael Kruse2018-04-091-2/+4
| | | | | | | | | | std::remove, despite its name, does not remove elements from a list, but only moves them to the end of a list. Call erase() to shorten the vector to the remaining elements. Test case included in next commit. llvm-svn: 329639
* Remove immediate dominator heuristic for error block detection.Michael Kruse2018-04-091-19/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch removes the heuristic in - Polly :: lib/Support/ScopHelper.cpp The heuristic forces blocks that directly follow a loop header to not to be considered error blocks. It was introduced in r249611 with the following commit message: > This replaces the support for user defined error functions by a > heuristic that tries to determine if a call to a non-pure function > should be considered "an error". If so the block is assumed not to be > executed at runtime. While treating all non-pure function calls as > errors will allow a lot more regions to be analyzed, it will also > cause us to dismiss a lot again due to an infeasible runtime context. > This patch tries to limit that effect. A non-pure function call is > considered an error if it is executed only in conditionally with > regards to a cheap but simple heuristic. In the code below `CCK_Abort2()` would be considered as an error block, but not `CCK_Abort1()` due to this heuristic. ``` for (int i = 0; i < n; i+=1) { if (ErrorCondition1) CCK_Abort1(); // No __attribute__((noreturn)) if (ErrorCondition2) CCK_Abort2(); // No __attribute__((noreturn)) } ``` This does not seem useful. Checking error conditions in the beginning of some work is quite common. It causes a switch default-case to be not considered an error block in SPEC's cactuBSSN. The comment justifying the heuristic mentions a "load", which does not seem to be applicable here. It has been proposed to remove the heuristic. In addition, the patch fixes the following test cases: - Polly :: ScopDetect/mod_ref_read_pointer.ll - Polly :: ScopInfo/max-loop-depth.ll - Polly :: ScopInfo/mod_ref_access_pointee_arguments.ll - Polly :: ScopInfo/mod_ref_read_pointee_arguments.ll - Polly :: ScopInfo/mod_ref_read_pointer.ll - Polly :: ScopInfo/mod_ref_read_pointers.ll The test cases failed after removing the heuristic. Differential Revision: https://reviews.llvm.org/D45274 Contributed-by: Lorenzo Chelini <l.chelini@icloud.com> llvm-svn: 329548
* Silence msvc warning on isl. NFC.Michael Kruse2018-04-051-0/+1
| | | | | | | | | | | | | | | | | The warning is: isl_union_map.c(2041): warning C4221: nonstandard extension used: 'filter_user': cannot be initialized using address of automatic variable 'data' for the following code (and others) struct isl_un_op_drop_user_data data = { &isl_set_is_wrapping }; struct isl_un_op_control control = { .filter = &un_op_filter_drop_user, .filter_user = &data, .fn_map = &isl_set_wrapped_domain_map, }; llvm-svn: 329328
* [Polly][IslAst] Fix minimal dependence distance.Huihui Zhang2018-04-042-3/+9
| | | | | | | | | | | | | | | | | | | Summary: When checking the parallelism of a scheduling dimension, we first check if excluding reduction dependences the loop is parallel or not. If the loop is not parallel, then we need to return the minimal dependence distance of all data dependences, including the previously subtracted reduction dependences. Reviewers: grosser, Meinersbur, efriedma, eli.friedman, jdoerfert, bollu Reviewed By: Meinersbur Subscribers: llvm-commits, pollydev Tags: #polly Differential Revision: https://reviews.llvm.org/D45236 llvm-svn: 329214
* Fix polly build after r328717Reid Kleckner2018-03-282-0/+2
| | | | llvm-svn: 328728
* [polly] [ScopInfo] Don't pre-compute the name of the Scop's region.Eli Friedman2018-03-271-2/+2
| | | | | | | | | | | This gets very expensive for basic blocks which don't have a name: it calls printAsOperand, which numbers the entire module. We don't normally need the name anyway, though; it's only used for debug dumps, so don't compute it by default. Differential Revision: https://reviews.llvm.org/D44946 llvm-svn: 328666
* Update for LLVM header movementDavid Blaikie2018-03-212-2/+2
| | | | llvm-svn: 328169
* Adjust to clang-format changesTobias Grosser2018-03-2012-16/+0
| | | | llvm-svn: 328005
* [polly] Change std::sort to llvm::sort in response to r327219Mandeep Singh Grang2018-03-131-1/+1
| | | | | | | | | | | | | | | | | | | | | Summary: r327219 added wrappers to std::sort which randomly shuffle the container before sorting. This will help in uncovering non-determinism caused due to undefined sorting order of objects having the same key. To make use of that infrastructure we need to invoke llvm::sort instead of std::sort. Reviewers: grosser, efriedma, jdoerfert, bollu, sebpop Reviewed By: sebpop Subscribers: sebpop, mehdi_amini, llvm-commits, pollydev Tags: #polly Differential Revision: https://reviews.llvm.org/D44361 llvm-svn: 327361
* Revert untested changes in SCEVAffinatorTobias Grosser2018-03-101-1/+1
| | | | llvm-svn: 327221
* Add isl operator overloads for isl::pw_affTobias Grosser2018-03-101-1/+3
| | | | | | | | | | | | Piecewise affine expressions have directly corresponding mathematical operators. Introduce these operators as overloads as this makes writing code with isl::pw_aff expressions more directly readable. We can now write: A = B + C instead of A = B.add(C) llvm-svn: 327216
* [ScopInfo] Do not use the set dimension ids to carry loop informationTobias Grosser2018-03-032-44/+18
| | | | | | | | | | | | | | isl does not guarantee that set dimension ids will be preserved, so using them to carry information is not a good idea. Furthermore, the loop information can be derived without problem from the statement itself. As this even requires less code than propagating loop information on set dimension ids, starting from this commit we just derive the loop information in collectSurroundingLoops directly from the IR. Interestingly this also results in a couple of isl sets to take a simpler representation. llvm-svn: 326664
* Revert "[Acc] Fix for PR33208"Philip Pfaffe2018-03-031-5/+9
| | | | | | This reverts commit r326643. Fix didn't really fix anything. llvm-svn: 326656
* [Acc] Fix for PR33208Philip Pfaffe2018-03-031-9/+5
| | | | | | | | | | | | | During codegen, Polly attempts to clear all loops from ScalarEvolution and LoopInfo, and it does so one block at a time. This causes undefined behaviour, since this way a loop header might be removed from a loop before the entire loop is erased, causing ScalarEvolution to run into an error. Instead, just delete the entire loop atomically. This fixes currently failing testcases. llvm-svn: 326643
* isl: "isl_schedule_get_map: handle trees with divergent filter node parameters"Tobias Grosser2018-02-263-4/+37
| | | | | | | | | | | Also un-revert (isl_pw_*_alloc: add missing check for compatible spaces, Wed Sep 6 12:18:04 2017 +0200). This patch is a proposed fix to avoid asserts due to stricter space checking within isl, which resulted in failures when converting a schedule tree to a schedule map. llvm-svn: 326073
* Use isl::manage_copy to simplify calls to isl::manage(isl_.._copy())Tobias Grosser2018-02-209-49/+37
| | | | | | | | | | | As part of this cleanup a couple of unnecessary isl::manage(obj.copy()) pattern are eliminated as well. We checked for all potential cleanups by scanning for: "grep -R isl::manage\( lib/ | grep copy" llvm-svn: 325558
* Update isl to isl-0.18-1047-g4a20ef8Tobias Grosser2018-02-20118-5369/+4039
| | | | | | | | | | | | | | | | | | This update: - Removes several deprecated functions (e.g., isl_band). - Improves the pretty-printing of sets by detecting modulos and "false" equalities. - Minor improvements to coalescing and increased robustness of the isl scheduler. This update does not yet include isl commit isl-0.18-90-gd00cb45 (isl_pw_*_alloc: add missing check for compatible spaces, Wed Sep 6 12:18:04 2017 +0200), as this additional check is too tight and unfortunately causes two test case failures in Polly. A patch has been submitted to isl and will be included in the next isl update for Polly. llvm-svn: 325557
* Fix broken isl-noexceptions.h path in update-isl scriptTobias Grosser2018-02-201-2/+2
| | | | llvm-svn: 325556
* Update isl C++ bindings to latest version of islTobias Grosser2018-02-201-276/+954
| | | | llvm-svn: 325555
* Do not call band_list().dump()Tobias Grosser2018-02-201-1/+0
| | | | | | This is in preparation for the removal of band_list from isl. llvm-svn: 325554
* [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
OpenPOWER on IntegriCloud