summaryrefslogtreecommitdiffstats
path: root/polly/lib/Analysis/DependenceInfo.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [DependenceInfo] Compute WAR dependence info using ISL kills. NFC.Michael Kruse2019-08-291-114/+16
| | | | | | | | | | | | | | | When reading code of Dependences::calculateDependences, I noticed that WAR is computed specifically by buildWAR. Given ISL now supports "kills" in approximate dataflow analysis, this patch takes advantage of it. This patch also cleans up a couple lines redundant codes. Patch by bin.narwal <bin.narwal@gmail.com> Differential Revision: https://reviews.llvm.org/D66741 llvm-svn: 370396
* [DependenceInfo] Remove dead initialization. NFC.Michael Kruse2019-05-201-2/+2
| | | | | | | | | | Fix scan-analyzer issue: Value stored to 'WARMemAccesses' during its initialization is never read Patch by Dominik Adamski <adamski.dominik@gmail.com> Signed-off-by: Dominik Adamski <adamski.dominik@gmail.com> llvm-svn: 361196
* Apply include-what-you-use #include removal suggestions. NFC.Michael Kruse2019-03-281-9/+8
| | | | | | | | | | | | 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
* [DepInfo] Use isl++ in Dependences::isValidSchedule. NFC.Michael Kruse2018-08-101-28/+23
| | | | | | | Also change StatementToIslMapTy to hold isl::map, because it is used as a parameter. llvm-svn: 339484
* [DependenceInfo] Use isl++ to replace foreach_set with for loopTobias Grosser2018-07-171-9/+13
| | | | llvm-svn: 337248
* getDependences to new C++ interfaceTobias Grosser2018-06-061-11/+12
| | | | | | | | | | | | | | Reviewers: Meinersbur, grosser, bollu, cs15btech11044, jdoerfert Reviewed By: grosser Subscribers: pollydev, llvm-commits Tags: #polly Differential Revision: https://reviews.llvm.org/D47786 llvm-svn: 334092
* [polly] Update uses of DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-151-18/+19
| | | | | | | | | | | The DEBUG() macro is very generic so it might clash with other projects. The renaming was done as follows: - git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g' - git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM Differential Revision: https://reviews.llvm.org/D44978 llvm-svn: 332352
* [Polly][IslAst] Fix minimal dependence distance.Huihui Zhang2018-04-041-1/+2
| | | | | | | | | | | | | | | | | | | 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
* [ScopInfo] Move Scop::getPwAffOnly to isl++ [NFC]Tobias Grosser2017-08-061-1/+1
| | | | llvm-svn: 310231
* [ScopInfo] Move Scop::getAssumedContext to isl++ [NFC]Tobias Grosser2017-08-061-2/+2
| | | | llvm-svn: 310228
* [ScopInfo] Translate Scop::getParamSpace to isl++ [NFC]Tobias Grosser2017-08-061-2/+2
| | | | llvm-svn: 310224
* [ScopInfo] Move ScopStmt::getSchedule to isl++Tobias Grosser2017-08-061-3/+4
| | | | llvm-svn: 310215
* Move ScopInfo::getDomain(), getDomainSpace(), getDomainId() to isl++Tobias Grosser2017-08-061-1/+1
| | | | llvm-svn: 310209
* Move MemoryAccess::get*ArrayId to isl++Tobias Grosser2017-07-231-1/+1
| | | | llvm-svn: 308843
* Move MemoryAccess::NewAccessRelation to isl++Tobias Grosser2017-07-231-3/+3
| | | | | | We also move related accessor functions llvm-svn: 308840
* Move MemoryAccess::id to isl++Tobias Grosser2017-07-231-1/+1
| | | | llvm-svn: 308836
* Fix a lot of typos. NFC.Michael Kruse2017-06-081-2/+2
| | | | llvm-svn: 304974
* Post-commit fix of a commentPhilip Pfaffe2017-05-231-1/+1
| | | | llvm-svn: 303628
* [Polly][NewPM] Port DependenceInfo to the new ScopPassManager.Philip Pfaffe2017-05-231-0/+42
| | | | | | | | | | | | | | | | Summary: This patch ports DependenceInfo to the new ScopPassManager. Printing is implemented as a seperate printer pass. Reviewers: grosser, Meinersbur Reviewed By: grosser Subscribers: llvm-commits, pollydev Tags: #polly Differential Revision: https://reviews.llvm.org/D33421 llvm-svn: 303621
* [Polly][NewPM] Port ScopInfo to the new PassManagerPhilip Pfaffe2017-05-151-1/+1
| | | | llvm-svn: 303056
* [Polly] [DependenceInfo] change WAR generation, Read will not block ReadSiddharth Bhat2017-04-241-27/+101
| | | | | | | | | | | | | | | | | | | | | Earlier, the call to buildFlow was: WAR = buildFlow(Write, Read, MustWrite, Schedule). This meant that Read could block another Read, since must-sources can block each other. Fixed the call to buildFlow to correctly compute Read. The resulting code needs to do some ISL juggling to get the output we want. Bug report: https://bugs.llvm.org/show_bug.cgi?id=32623 Reviewers: Meinersbur Tags: #polly Differential Revision: https://reviews.llvm.org/D32011 llvm-svn: 301266
* [Polly] [DependenceInfo] change WAR, WAW generation to correct semanticsSiddharth Bhat2017-04-041-27/+108
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | = Change of WAR, WAW generation: = - `buildFlow(Sink, MustSource, MaySource, Sink)` treates any flow of the form `sink <- may source <- must source` as a *may* dependence. - we used to call: ```lang=cpp, name=old-flow-call.cpp Flow = buildFlow(MustWrite, MustWrite, Read, Schedule); WAW = isl_union_flow_get_must_dependence(Flow); WAR = isl_union_flow_get_may_dependence(Flow); ``` - This caused some WAW dependences to be treated as WAR dependences. - Incorrect semantics. - Now, we call WAR and WAW correctly. == Correct WAW: == ```lang=cpp, name=new-waw-call.cpp Flow = buildFlow(Write, MustWrite, MayWrite, Schedule); WAW = isl_union_flow_get_may_dependence(Flow); isl_union_flow_free(Flow); ``` == Correct WAR: == ```lang=cpp, name=new-war-call.cpp Flow = buildFlow(Write, Read, MustaWrite, Schedule); WAR = isl_union_flow_get_must_dependence(Flow); isl_union_flow_free(Flow); ``` - We want the "shortest" WAR possible (exact dependences). - We mark all the *must-writes* as may-source, reads as must-souce. - Then, we ask for *must* dependence. - This removes all the reads that flow through a *must-write* before reaching a sink. - Note that we only block ealier writes with *must-writes*. This is intuitively correct, as we do not want may-writes to block must-writes. - Leaves us with direct (R -> W). - This affects reduction generation since RED is built using WAW and WAR. = New StrictWAW for Reductions: = - We used to call: ```lang=cpp,name=old-waw-war-call.cpp Flow = buildFlow(MustWrite, MustWrite, Read, Schedule); WAW = isl_union_flow_get_must_dependence(Flow); WAR = isl_union_flow_get_may_dependence(Flow); ``` - This *is* the right model of WAW we need for reductions, just not in general. - Reductions need to track only *strict* WAW, without any interfering reductions. = Explanation: Why the new WAR dependences in tests are correct: = - We no longer set WAR = WAR - WAW - Hence, we will have WAR dependences that were originally removed. - These may look incorrect, but in fact make sense. == Code: == ```lang=llvm, name=new-war-dependence.ll ; void manyreductions(long *A) { ; for (long i = 0; i < 1024; i++) ; for (long j = 0; j < 1024; j++) ; S0: *A += 42; ; ; for (long i = 0; i < 1024; i++) ; for (long j = 0; j < 1024; j++) ; S1: *A += 42; ; ``` === WAR dependence: === { S0[1023, 1023] -> S1[0, 0] } - Between `S0[1023, 1023]` and `S1[0, 0]`, we will have the dependences: ```lang=cpp, name=dependence-incorrect, counterexample S0[1023, 1023]: *-- tmp = *A (load0)--* WAR 2 add = tmp + 42 | *-> *A = add (store0) | WAR 1 S1[0, 0]: | tmp = *A (load1) | add = tmp + 42 | A = add (store1)<-* ``` - One may assume that WAR2 *hides* WAR1 (since store0 happens before store1). However, within a statement, Polly has no idea about the ordering of loads and stores. - Hence, according to Polly, the code may have looked like this: ```lang=cpp, name=dependence-correct S0[1023, 1023]: A = add (store0) tmp = A (load0) ---* add = A + 42 | WAR 1 S1[0, 0]: | tmp = A (load1) | add = A + 42 | A = add (store1) <-* ``` - So, Polly generates (correct) WAR dependences. It does not make sense to remove these dependences, since they are correct with respect to Polly's model. Reviewers: grosser, Meinersbur tags: #polly Differential revision: https://reviews.llvm.org/D31386 llvm-svn: 299429
* revert test commit r299024Huihui Zhang2017-03-291-1/+0
| | | | llvm-svn: 299026
* test commit, add blank lineHuihui Zhang2017-03-291-0/+1
| | | | llvm-svn: 299024
* [DependenceInfo] change name Write to MustWrite to remove ambiguity [NFC]Siddharth Bhat2017-03-211-13/+15
| | | | | | | | | | | | | | | "Write" is an overloaded term. In collectInfo() till buildFlow(), it is used to mean "must writes". However, within the memory based analysis, it is used to mean "both may and must writes". Renaming the Write variable helps clarify this difference. Reviewers: grosser Tags: #polly Differential Revision: https://reviews.llvm.org/D31181 llvm-svn: 298361
* [DependenceInfo] Remove idempotent union: must-writes with may-writes [NFC]Siddharth Bhat2017-03-171-2/+1
| | | | | | | Since may-writes are always a superset of the must-writes, there is no point in taking a union of one with the other. llvm-svn: 298085
* [DependenceInfo] Replace use of deprecated isl_dim_n_out [NFC]Siddharth Bhat2017-03-171-1/+2
| | | | | | Change isl_dim_n_out to isl_map_dim(*, isl_dim_out) llvm-svn: 298075
* [DependenceInfo] Track may-writes and build flow information inSiddharth Bhat2017-03-171-0/+3
| | | | | | | | | | | | Dependences::calculateDependences. This ensures that we handle may-writes correctly when building dependence information. Also add a test case checking correctness of may-write information. Not handling it before was an oversight. Differential Revision: https://reviews.llvm.org/D31075 llvm-svn: 298074
* Set Dependences::RED to be non-null once Dependences::calculateDependences()Siddharth Bhat2017-03-161-0/+1
| | | | | | | occurs, even if there is no actual reduction. This ensures correctness with isl operations. llvm-svn: 297981
* [DependenceInfo] Remove unused variable. NFC.Michael Kruse2017-02-231-1/+0
| | | | llvm-svn: 295987
* [DependenceInfo] Use references instead of double pointers. NFC.Michael Kruse2017-02-231-18/+18
| | | | | | | Non-const references are the more C++-ish way to modify a variable passed by the caller. llvm-svn: 295986
* [DependenceInfo] Rename StmtScheduleDomain -> TaggedStmtDomain. NFC.Michael Kruse2017-02-231-15/+14
| | | | llvm-svn: 295985
* [DependenceInfo] Simplify use of StmtSchedule's domain [NFC]Michael Kruse2017-02-231-21/+21
| | | | | | | | | | | | | | | | | Once a StmtSchedule is created, only its domain is used anywhere within DependenceInfo::calculateDependences. So, we choose to return the wrapped domain of the union_map rather than the entire union_map. However, we still build the union_map first within collectInfo(). It is cleaner to first build the entire union_map and then pull the domain out in one shot, rather than repeatedly extracting the domain in bits and pieces from accdom. Contributed-by: Siddharth Bhat <siddu.druid@gmail.com> Differential Revision: https://reviews.llvm.org/D30208 llvm-svn: 295984
* [DependenceInfo] Simplify creation and subsequent use of AccessSchedule [NFC]Tobias Grosser2017-02-211-31/+22
| | | | | | | | | | | | | | We only ever use the wrapped domain of AccessSchedule, so stop creating an entire union_map and then pulling the domain out. Reviewers: grosser Tags: #polly Contributed-by: Siddharth Bhat <siddu.druid@gmail.com> Differential Revision: https://reviews.llvm.org/D30179 llvm-svn: 295726
* [DependenceInfo] Pull out statement [NFC]Tobias Grosser2017-02-181-3/+2
| | | | | | This simplifies the code slightly. llvm-svn: 295551
* [Dependences] Compute reduction dependences on schedule tree [NFC]Tobias Grosser2017-02-181-39/+27
| | | | | | | | | | | | | | | | | | | This change gets rid of the need for zero padding, makes the reduction computation code more similar to the normal dependence computation, and also better documents what we do at the moment. Making the dependence computation for reductions a little bit easier to understand will hopefully help us to further reduce code duplication. This reduces the time spent only in the reduction dependence pass from 260ms to 150ms for test/DependenceInfo/reduction_sequence.ll. This is a reduction of over 40% in dependence computation time. This change was inspired by discussions with Michael Kruse, Utpal Bora, Siddharth Bhat, and Johannes Doerfert. It can hopefully lay the base for further cleanups of the reduction code. llvm-svn: 295550
* [DependenceInfo] Use ScopArrayInfo to keep track of arrays [NFC]Tobias Grosser2017-02-091-4/+4
| | | | | | | | | | | | | | When computing reduction dependences we first identify all ScopArrays which are part of reductions and then only compute for these ScopArrays the more detailed data dependences that allow us to identify reductions and optimize across them. Instead of using the base pointer as identifier of a ScopArray, it is clearer and more understandable to directly use the ScopArray as identifier. This change implements such a switch. This change removes unnecessary uses of MemoryAddress::getBaseAddr() in preparation for https://reviews.llvm.org/D28518. llvm-svn: 294567
* Fix format after recent clang-format change.Daniel Jasper2017-02-011-3/+2
| | | | llvm-svn: 293753
* Adjust formatting to commit r292110 [NFC]Tobias Grosser2017-01-161-6/+9
| | | | llvm-svn: 292123
* Fix typo.Hongbin Zheng2016-11-231-7/+7
| | | | llvm-svn: 287819
* [DepInfo] Print -debug output outside of max-operations scope.Michael Kruse2016-10-101-5/+5
| | | | | | | | | ISL tries to simplify the polyhedral operations before printing its objects. This increases the operations counter and therefore can contribute to hitting the operations limit. Therefore the result could be different when -debug output is enabled, making debugging harder. llvm-svn: 283745
* [Support/DepInfo] Introduce IslMaxOperationsGuard and make DepInfo use it. NFC.Michael Kruse2016-10-101-51/+45
| | | | | | | | | | | IslMaxOperationsGuard defines a scope where ISL may abort operations because if it takes too many operations. Replace the call to the raw ISL interface by a use of the guard. IslMaxOperationsGuard provides a uniform way to define a maximal computation time for a code region in C++ using RAII. llvm-svn: 283744
* Turn cl::values() (for enum) from a vararg function to using C++ variadic ↵Mehdi Amini2016-10-081-4/+2
| | | | | | | | | | | | | | | 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
* Perform copying to created arrays according to the packing transformationRoman Gareev2016-09-141-1/+8
| | | | | | | | | | | | | | | | This is the fourth patch to apply the BLIS matmul optimization pattern on matmul kernels (http://www.cs.utexas.edu/users/flame/pubs/TOMS-BLIS-Analytical.pdf). BLIS implements gemm as three nested loops around a macro-kernel, plus two packing routines. The macro-kernel is implemented in terms of two additional loops around a micro-kernel. The micro-kernel is a loop around a rank-1 (i.e., outer product) update. In this change we perform copying to created arrays, which is the last step to implement the packing transformation. Reviewed-by: Tobias Grosser <tobias@grosser.es> Differential Revision: https://reviews.llvm.org/D23260 llvm-svn: 281441
* DependenceInfo: Make clear that no double-free problem existsTobias Grosser2016-09-081-1/+3
| | | | | | | | | | | | | When running the clang static analyser to check for memory issues, this code originally showed a double free, as the analyser was unable to understand that isl_union_map_free always returns NULL and consequently later uses of the isl object we just freed will never be reached. Without this knowledge, the analyser has to issue a warning. We refactor the code to make it clear that for empty maps the current loop iteration is aborted. llvm-svn: 280938
* Dependences: Only create flat StmtSchedule in presence of reductionsTobias Grosser2016-09-021-1/+1
| | | | | | | | | Without reductions we do not need a flat union_map schedule describing the computation we want to perform, but can work purely on the schedule tree. This reduces the dependence computation and scheduling time from 33ms to 25ms. Another 30% reduction. llvm-svn: 280558
* Dependences: Exit early, if no reduction dependences are needed.Tobias Grosser2016-09-021-1/+12
| | | | | | | | | | | | In case we do not compute reduction dependences or dependences that are more fine-grained than statement level dependences, we can avoid the corresponding part of the dependence analysis all together. For the 3mm benchmark, this reduces scheduling + dependence analysis time from 62ms to 33ms for a no-asserts build. The majority of the compile time is anyhow spent in the LLVM backends, when doing code generation. Nevertheless, there is no need to waste compile time either. llvm-svn: 280557
* Drop '@brief' from doxygen commentsTobias Grosser2016-09-021-6/+6
| | | | | | | | 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
* [DependenceInfo] Reset operations counter when setting limit.Michael Kruse2016-08-051-1/+3
| | | | | | | | | | | | | | | | | When entering the dependence computation and the max_operations is set, the operations counter may have already exceeded the counter, thus aborting any ISL computation from the start. The counter is reset at the end of the dependence calculation such that a follow-up recomputation might succeed, ie. the success of the first dependence calculation depends on unrelated ISL operations that happened before, giving it a disadvantage to the following calculations. This patch resets the operations counter at the beginning of the dependence recalculation to not depend on previous actions. Otherwise additional preprocessing of the Scop that aims to improve its schedulability (eg. DeLICM) do have the effect that DependenceInfo and hence the scheduling fail more likely, contraproductive to the goal of said preprocessing. llvm-svn: 277810
OpenPOWER on IntegriCloud