summaryrefslogtreecommitdiffstats
path: root/polly/lib/Analysis/Dependences.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Rename the Dependences pass to DependenceInfo [NFC]Johannes Doerfert2015-03-041-637/+0
| | | | | | | | | | We rename the Dependences pass to DependenceInfo as a first step to a caching pass policy. The new DependenceInfo pass will later provide "Dependences" for a SCoP. To keep consistency the test folder is renamed too. llvm-svn: 231308
* [Refactor] Simplify ScopPass interfaceJohannes Doerfert2015-03-011-1/+1
| | | | llvm-svn: 230899
* [Refactor] Add a Scop & as argument to printScopJohannes Doerfert2015-03-011-6/+6
| | | | | | This is the first step in the interface simplification. llvm-svn: 230897
* Dead code elimination: Update dependences after eliminating codeTobias Grosser2014-12-171-2/+6
| | | | | | | | | | | | Without updating dependences we may lose implicit transitive dependences for which all explicit dependences have gone through the statement iterations we have just eliminated. No test case. We should probably implement a -verify-dependences option. This fixes llvm.org/PR21227 llvm-svn: 224459
* Simplify computation of reduction dependencesTobias Grosser2014-12-071-10/+4
| | | | | | | | | This simplifies the construction of the input for the reduction dependence computation and at the same time removes an assumption that expects the schedule to be of 2D + 1 form (the odd dimensions giving textual order, the even dimensions the loop iterations). llvm-svn: 223621
* Assume GetElementPtr offsets to be inboundsTobias Grosser2014-11-251-0/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | In case a GEP instruction references into a fixed size array e.g., an access A[i][j] into an array A[100x100], LLVM-IR does not guarantee that the subscripts always compute values that are within array bounds. We now derive the set of parameter values for which all accesses are within bounds and add the assumption that the scop is only every executed with this set of parameter values. Example: void foo(float A[][20], long n, long m { for (long i = 0; i < n; i++) for (long j = 0; j < m; j++) A[i][j] = ... This loop yields out-of-bound accesses if m is at least 20 and at the same time at least one iteration of the outer loop is executed. Hence, we assume: n <= 0 or m <= 20. Doing so simplifies the dependence analysis problem, allows us to perform more optimizations and generate better code. TODO: The location where the GEP instruction is executed is not necessarily the location where the memory is actually accessed. As a result scanning for GEP[s] is imprecise. Even though this is not a correctness problem, this imprecision may result in missed optimizations or non-optimal run-time checks. In polybench where this mismatch between parametric loop bounds and fixed size arrays is common, we see with this patch significant reductions in compile time (up to 50%) and execution time (up to 70%). We see two significant compile time regressions (fdtd-2d, jacobi-2d-imper), and one execution time regression (trmm). Both regressions arise due to additional optimizations that have been enabled by this patch. They can be addressed in subsequent commits. http://reviews.llvm.org/D6369 llvm-svn: 222754
* Fix typoTobias Grosser2014-11-211-1/+1
| | | | llvm-svn: 222559
* Use nullptr instead of '0' for pointersTobias Grosser2014-11-141-1/+1
| | | | llvm-svn: 221982
* Fix typoTobias Grosser2014-10-221-1/+1
| | | | llvm-svn: 220446
* Use braces in multi-statement DEBUG() code [NFC]Tobias Grosser2014-10-221-6/+20
| | | | | | | | | | | | | | | | | | By adding braces into the DEBUG statement we can make clang-format format code such as: DEBUG(stmt1(); stmt2()) as multi-line code: DEBUG({ stmt1(); stmt2(); }); This makes control-flow in debug statements easier to read. llvm-svn: 220441
* Compute and print the minimal loop carried dependency distanceJohannes Doerfert2014-09-131-9/+29
| | | | | | | | | | | During the IslAst parallelism check also compute the minimal dependency distance and store it in the IstAst for node. Reviewer: sebpop Differential Revision: http://reviews.llvm.org/D4987 llvm-svn: 217729
* Annotate the IslAst with broken reductionsJohannes Doerfert2014-08-011-0/+50
| | | | | | | | | | | | + Split all reduction dependences and map them to the causing memory accesses. + Print the types & base addresses of broken reductions for each "reduction parallel" marked loop (OpenMP style). + 3 test cases to show how reductions are now represented in the isl ast. The mapping "(ast) loops -> broken reductions" is also needed to find the memory accesses we need to privatize in a loop. llvm-svn: 214489
* Replace the dependences parallelism check by the IslAst oneJohannes Doerfert2014-07-281-58/+25
| | | | llvm-svn: 214061
* Annotate reduction parallel loops in the IslAst textual outputJohannes Doerfert2014-07-151-11/+49
| | | | | | | | | | + Introduced dependency type TYPE_TC_RED to represent the transitive closure (& the reverse) of reduction dependences. These are used when we check for reduction parallel loops. + Test cases including loop reversals and modulo schedules which compute reductions in a alternated order. llvm-svn: 213019
* clang-format polly to avoid buildbot noiseTobias Grosser2014-07-091-11/+9
| | | | llvm-svn: 212609
* Allow multiple reductions per statementJohannes Doerfert2014-06-271-1/+0
| | | | | | | | | | | | Iterate over all store memory accesses and check for valid binary reduction candidate loads by following the operands of the stored value. For each candidate pair we check if they have the same base address and there are no other accesses which may overlap with them. This ensures that no intermediate value can escape into other memory locations or is overwritten at some point. + 17 test cases for reduction detection and reduction dependency modeling llvm-svn: 211957
* [Refactor] Make the used dependence types explicitJohannes Doerfert2014-06-261-2/+2
| | | | llvm-svn: 211803
* Use wrapped reduction dependencesJohannes Doerfert2014-06-261-18/+24
| | | | | | | | | | | This change will ease the transision to multiple reductions per statement as we can now distinguish the effects of multiple reductions in the same statement. + Wrapped reduction dependences are used to compute privatization dependences + Modified test cases to account for the change llvm-svn: 211795
* Hybrid dependency analysisJohannes Doerfert2014-06-261-5/+70
| | | | | | | | | | | This dependency analysis will keep track of memory accesses if they might be part of a reduction. If not, the dependences are tracked on a statement level. The main reason to do this is to reduce the compile time while beeing able to distinguish the effects of reduction and non-reduction accesses. + Adjusted two test cases llvm-svn: 211794
* Reduction like is now a memory access propertyJohannes Doerfert2014-06-201-7/+10
| | | | | | | - Remove the statement reduction like property + Add the reduction like property to memory accesses llvm-svn: 211372
* Model statement wise reduction dependencesJohannes Doerfert2014-06-201-3/+121
| | | | | | | | | | | | | + Collect reduction dependences + Introduced TYPE_RED in Dependences.h which can be used to obtain the reduction dependences + Used TYPE_RED to prevent parallelization while we do not have a privatizing code generation + Relax the dependences for non-parallel code generation + Add privatization dependences to ensure correctness + 12 Test cases to check for reduction and privatization dependences llvm-svn: 211369
* [Refactor] C++11 Memory access iterators in SCoP stmtsJohannes Doerfert2014-06-131-5/+3
| | | | | | | | | + Added const iterator version + Changed name to begin/end to allow range loops + Changed call sites to range loops + Changed typename to (const_)iterator llvm-svn: 210927
* [Refactor] Simplify dependency map dumpJohannes Doerfert2014-06-131-13/+9
| | | | llvm-svn: 210926
* Use range-based for loopsTobias Grosser2014-06-041-9/+4
| | | | llvm-svn: 210170
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-3/+4
| | | | | | | | | | definition below all of the header #include lines, Polly edition. If you want to know more details about this, you can see the recent commits to Debug.h in LLVM. This is just the Polly segment of a cleanup I'm doing globally for this macro. llvm-svn: 206852
* [C++11] Use nullptrTobias Grosser2014-04-161-14/+14
| | | | llvm-svn: 206361
* Dependences: Do not fail in case a schedule eliminates all dependencesTobias Grosser2014-04-151-0/+7
| | | | | | | | | | | | | | | | | | | The following example shows a non-parallel loop void f(int a[]) { int i; for (i = 0; i < 10; ++i) A[i] = A[i+5]; } which, in case we import a schedule that limits the iteration domain to 0 <= i < 5, becomes parallel. Previously we crashed in such cases, now we just recognize it as parallel. This fixes http://llvm.org/PR19435 Reported-by: Jeremy Huddleston Sequoia <jeremyhu@apple.com> llvm-svn: 206318
* Dependences: Refine the compute out facilityTobias Grosser2014-04-121-1/+1
| | | | | | | | | | | | We update to a newer version of isl, which includes changes to the compute out facility that make it a lot more predicable. With our new value, we can reliably bail out for all reported bugs, while still being able to compute dependences for all but two test cases in the LLVM test suite. For the remaining two test cases, the dependence problem we construct is unnecessarily complex, so there is hope we can improve on this. However, to avoid any future issues, having a reliable compute out facility in place is important. llvm-svn: 206106
* Return conservative result in case the dependence check timed outTobias Grosser2014-03-211-0/+5
| | | | | | | For complex examples it may happen that we do not compute dependences. In this case we do not want to crash, but just not detect parallel loops. llvm-svn: 204470
* Dependences: Further reduce the allowed compile timeTobias Grosser2014-03-181-1/+1
| | | | | | | | llvm.org/PR19081 reports that the polly dependence analysis causes some h264 compilation to hang. We adjust the compute out, to ensure we do not block on expensive dependence calculations. llvm-svn: 204168
* Print function and region name in scop descriptionTobias Grosser2014-03-181-1/+1
| | | | llvm-svn: 204165
* Allow several polly command line options to be provided multiple timesTobias Grosser2014-03-131-3/+5
| | | | | Contributed-by: Sam Novak <snovak@uwsp.edu> llvm-svn: 203869
* Do not fail in case we do not have valid dependencesTobias Grosser2014-02-231-0/+5
| | | | | | | | In case we do not have valid dependences, we do not run dead code elimination or the schedule optimizer. This fixes an infinite loop in the dead code elimination (PR12110). llvm-svn: 201982
* Dependences: Do not assign 'WAW' twiceTobias Grosser2014-02-211-1/+1
| | | | | | Reported-by: Sebastian Pop <spop@codeaurora.org> Reported-by: Yabin Hu <yabin.hwu@gmail.com> llvm-svn: 201903
* Dependences: Eliminate warning about possibly uninitialized pointersTobias Grosser2014-02-211-1/+3
| | | | llvm-svn: 201898
* Dependences: Bound the time dependence calculation is allowed to takeTobias Grosser2014-01-261-3/+42
| | | | | | | | | | | | | | Count the number of computational steps that have been used to solve the dependence problem and abort in case we reach the "compute-out". This ensures we do not hang forever in cases the dependence problem is too difficult to solve. There is just a single case in the LLVM test-suite that runs into the compute-out. Even in this case, we can probably coalesce some of the parameters (i32 b, i32 b zext i64, ...) to simplify the problem enough to not hit the compute out. However, for now we set the compute out in place to address the general issue. The compute out was choosen such that it stops on a recent laptop after about 8 seconds. llvm-svn: 200156
* Temporarily reformat Polly to silence buildbotsTobias Grosser2014-01-061-4/+1
| | | | | | | We may revert this depending on how the current discussion on llvm-commits ends. llvm-svn: 198581
* PollyDependence: Simplify Read/Write/MayWrite before feeding them into ISL.Tobias Grosser2013-08-081-0/+4
| | | | | Contributed-by: Star Tan <tanmx_star@yeah.net> llvm-svn: 187981
* Dependence: Add DEBUG support.Tobias Grosser2013-07-311-0/+12
| | | | | Contributed-by: Star Tan <tanmx_star@yeah.net> llvm-svn: 187498
* Dependences: Use ostream printer to print analysis outputTobias Grosser2013-07-141-9/+3
| | | | llvm-svn: 186288
* Dependences: Clarify difference between value and memory based dependencesTobias Grosser2013-07-131-5/+15
| | | | | | | We make the option a clear choice between the two analysis types and add descriptions about the difference between the two. llvm-svn: 186251
* Sort includesTobias Grosser2013-05-071-2/+0
| | | | llvm-svn: 181297
* Move polly options into separate option categoryTobias Grosser2013-05-071-6/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | Use the new cl::OptionCategory support to move the Polly options into a separate option category. The aim is to hide most options and show by default only the options a user needs to influence '-O3 -polly'. The available options probably need some care, but here is the current status: Polly Options: Configure the polly loop optimizer -enable-polly-openmp - Generate OpenMP parallel code -polly - Enable the polly optimizer (only at -O3) -polly-no-tiling - Disable tiling in the scheduler -polly-only-func=<function-name> - Only run on a single function -polly-report - Print information about the activities of Polly -polly-vectorizer - Select the vectorization strategy =none - No Vectorization =polly - Polly internal vectorizer =unroll-only - Only grouped unroll the vectorize candidate loops =bb - The Basic Block vectorizer driven by Polly llvm-svn: 181295
* Reformat with clang-formatTobias Grosser2013-05-071-6/+7
| | | | | | | clang-format become way more stable. This time we mainly reformat function signatures. llvm-svn: 181294
* Update formatting to latest version of clang-formatTobias Grosser2013-04-101-3/+3
| | | | llvm-svn: 179160
* clang-format: Many more filesTobias Grosser2013-03-231-6/+4
| | | | | | | | | | | | | After this commit, polly is clang-format clean. This can be tested with 'ninja polly-check-format'. Updates to clang-format may change this, but the differences will hopefully be both small and general improvements to the formatting. We currently have some not very nice formatting for a couple of items, DEBUG() stmts for example. I believe the benefit of being clang-format clean outweights the not perfect layout of this code. llvm-svn: 177796
* Dependences: clang-formatTobias Grosser2013-02-051-46/+38
| | | | | | Everything except INITIALIZE_PASS_* macros llvm-svn: 174367
* Fix obvious formatting problems.Tobias Grosser2012-12-291-4/+3
| | | | | | | | | | | | | | | | | | | | | | We fix the following formatting problems found by clang-format: - 80 cols violations - Obvious problems with missing or too many spaces - multiple new lines in a row clang-format suggests many more changes, most of them falling in the following two categories: 1) clang-format does not at all format a piece of code nicely 2) The style that clang-format suggests does not match the style used in Polly/LLVM I consider differences caused by reason 1) bugs, which should be fixed by improving clang-format. Differences due to 2) need to be investigated closer to understand the cause of the difference and the solution that should be taken. llvm-svn: 171241
* Dependences: Add support to calculate memory based dependencesTobias Grosser2012-11-011-10/+44
| | | | | | | | | Instead of calculating exact value (flow) dependences, it is also possible to calculate memory based dependences. Sometimes memory based dependences are a lot easier to calculate. To evaluate the benefits, we add an option to calculate memory based dependences (use -polly-value-dependences=false). llvm-svn: 167251
* Dependences: Print dependences in -analyze outputTobias Grosser2012-08-271-0/+9
| | | | | | | The dependency printing was accidentally removed in during a previous restructuring. llvm-svn: 162662
OpenPOWER on IntegriCloud