summaryrefslogtreecommitdiffstats
path: root/polly/lib/Transform/Simplify.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Sink all InitializePasses.h includesReid Kleckner2019-11-131-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This file lists every pass in LLVM, and is included by Pass.h, which is very popular. Every time we add, remove, or rename a pass in LLVM, it caused lots of recompilation. I found this fact by looking at this table, which is sorted by the number of times a file was changed over the last 100,000 git commits multiplied by the number of object files that depend on it in the current checkout: recompiles touches affected_files header 342380 95 3604 llvm/include/llvm/ADT/STLExtras.h 314730 234 1345 llvm/include/llvm/InitializePasses.h 307036 118 2602 llvm/include/llvm/ADT/APInt.h 213049 59 3611 llvm/include/llvm/Support/MathExtras.h 170422 47 3626 llvm/include/llvm/Support/Compiler.h 162225 45 3605 llvm/include/llvm/ADT/Optional.h 158319 63 2513 llvm/include/llvm/ADT/Triple.h 140322 39 3598 llvm/include/llvm/ADT/StringRef.h 137647 59 2333 llvm/include/llvm/Support/Error.h 131619 73 1803 llvm/include/llvm/Support/FileSystem.h Before this change, touching InitializePasses.h would cause 1345 files to recompile. After this change, touching it only causes 550 compiles in an incremental rebuild. Reviewers: bkramer, asbirlea, bollu, jdoerfert Differential Revision: https://reviews.llvm.org/D70211
* [Stats] More polly fixes following llvm::Statistic changes in r374490.Volodymyr Sapsai2019-10-111-2/+2
| | | | llvm-svn: 374501
* 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
* [Simplify] Replace isl foreach calls with for loopsTobias Grosser2018-07-171-27/+22
| | | | llvm-svn: 337241
* [polly] Update uses of DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-151-20/+22
| | | | | | | | | | | 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
* [DeLICM] Remove uses of isl::giveTobias Grosser2018-04-281-1/+1
| | | | llvm-svn: 331122
* Run clang-format after r324003. NFC.Michael Kruse2018-02-021-3/+3
| | | | llvm-svn: 324112
* Update polly for r323999.Benjamin Kramer2018-02-011-4/+4
| | | | llvm-svn: 324003
* Port ScopInfo to the isl cpp bindingsPhilip Pfaffe2017-11-191-3/+3
| | | | | | | | | | | | | | | | | | | | | 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
* [Simplify] Actually remove unsed instruction from region header.Michael Kruse2017-09-051-2/+3
| | | | | | | | | | | | | | | | | Since r312249 instructions of a entry block of region statements are not marked as root anymore and hence can theoretically be removed if unused. Theoretically, because the instruction list was not changed. Still, MemoryAccesses for unused instructions were removed. This lead to a failed assertion in the code generator when the MemoryAccess for the still listed instruction was not found. This hould fix the Assertion failed: ArrayAccess && "No array access found for instruction!", file ScopInfo.h, line 1494 compiler crashes. llvm-svn: 312566
* Add more statistics.Michael Kruse2017-08-231-24/+55
| | | | | | | | | | | | | | | | Add statistics about - Which optimizations are applied - Number of loops in Scops at various stages - Number of scalar/singleton writes at various stages representative for scalar false dependencies - Number of parallel loops These will be useful to find regressions due to moving Polly further down of LLVM's pass pipeline. Differential Revision: https://reviews.llvm.org/D37049 llvm-svn: 311553
* [ScheduleOptimizer] Make matmul pattern detection work with delicm outputTobias Grosser2017-08-081-33/+21
| | | | | | | | | | | | In certain cases delicm might decide to not leave the original array write in the loop body, but to remove it and instead leave a transformed phi node as write access. This commit teached the matmul pattern detection to order the memory accesses according to when the access actually happens and use this information to detect the new pattern. This makes pattern based matmul optimization work for 2mm and 3mm in polybench 4 after polly-position=before-vectorizer has been enabled. llvm-svn: 310338
* [ScopInfo] Translate Scop::getParamSpace to isl++ [NFC]Tobias Grosser2017-08-061-8/+6
| | | | llvm-svn: 310224
* Move ScopInfo::getDomain(), getDomainSpace(), getDomainId() to isl++Tobias Grosser2017-08-061-3/+3
| | | | llvm-svn: 310209
* Move setNewAccessRelation to isl++Tobias Grosser2017-08-021-1/+1
| | | | llvm-svn: 309871
* [Simplify] Rewrite redundant write detection algorithm.Michael Kruse2017-08-011-134/+81
| | | | | | | | | | | | | | | | | | | | | | The previous algorithm was to search a writes and the sours of its value operand, and see whether the write just stores the same read value back, which includes a search whether there is another write access between them. This is O(n^2) in the max number of accesses in a statement (+ the complexity of isl comparing the access functions). The new algorithm is more similar to the one used for searching for overwrites and coalescable writes. It scans over all accesses in order of execution while tracking which array elements still have the same value since it was read. This is O(n), not counting the complexity within isl. It should be more reliable than trying to catch all non-conforming cases in the previous approach. It is also less code. We now also support if the write is a partial write of the read's domain, and to some extent non-affine subregions. Differential Revision: https://reviews.llvm.org/D36137 llvm-svn: 309734
* [Simplify] Improve scalability.Michael Kruse2017-08-011-11/+80
| | | | | | | | | | | | | | | | | | | | | | With a lot of reads and writes to the same array in a statement, some isl sets that capture the state between access can become complex such that isl takes more considerable time and memory for operations on them. The problems identified were: - is_subset() takes considerable time with many disjoints in the arguments. We limit the number of disjoints to 4, any additional information is thrown away. - subtract() can lead to many disjoints. We instead assume that any array element is possibly accessed, which removes all disjoints. - subtract_domain() may lead to considerable processing, even if all elements are are to be removed. Instead, we remove determine and remove the affected spaces manually. No behaviour is changed. llvm-svn: 309728
* [Simplify] Remove all kinds of redundant scalar writes.Michael Kruse2017-07-311-1/+2
| | | | | | | | In addition to array and PHI writes, also allow scalar value writes. The only kind of write not allowed are writes by functions (including memcpy/memmove/memset). llvm-svn: 309582
* [Simplify] Implement write accesses coalescing.Michael Kruse2017-07-291-3/+182
| | | | | | | | | | | | | | | | | Write coalescing combines write accesses that - Write the same llvm::Value. - Write to the same array. - Unless they do not write anything in a statement instance (partial writes), write to the same element. - There is no other access between them that accesses the same element. This is particularly useful after DeLICM, which leaves partial writes to disjoint domains. Differential Revision: https://reviews.llvm.org/D36010 llvm-svn: 309489
* [Simplify] Fix typo in statistics output. NFC.Michael Kruse2017-07-281-1/+1
| | | | llvm-svn: 309402
* [Simplify] Remove empty partial accesses first. NFC.Michael Kruse2017-07-281-3/+3
| | | | | | So follow-up cleanup do not need special handling for such accesses. llvm-svn: 309401
* [Simplify] Do not setInstructions() of region stmts. NFC.Michael Kruse2017-07-261-0/+3
| | | | | | | The instruction list is ignored for region statements, there is no reason to set it. llvm-svn: 309196
* Simplify: Adopt for translation of MemoryAccess::getAccessRelationTobias Grosser2017-07-231-1/+1
| | | | | | For some reason this one was missed earlier. llvm-svn: 308845
* Move MemoryAccess::NewAccessRelation to isl++Tobias Grosser2017-07-231-5/+5
| | | | | | We also move related accessor functions llvm-svn: 308840
* [Simplify] Remove partial write accesses with empty domain.Michael Kruse2017-07-221-2/+40
| | | | | | | | | | | If the access relation's domain is empty, the access will never be executed. We can just remove it. We only remove write accesses. Partial read accesses are not yet supported and instructions in the statement might require the llvm::Value holding the read's result to be defined. llvm-svn: 308830
* [ScopInfo] Print instructions in dump().Michael Kruse2017-07-211-1/+1
| | | | | | | | | | | | | | | | | | | Print a statement's instruction on dump() regardless of -polly-print-instructions. dump() is supposed to be used in the debugger only and never in regression tests. While debugging, get all the information we have and we are not bound to break anything. For non-dump purposes of print, forward the setting of -polly-print-instructions as parameters. Some calls to print() had to be changed because the PollyPrintInstructions setting is only available in ScopInfo.cpp. In ScheduleOptimizer.cpp, dump() was used in regression tests. That's not what dump() is for. The print parameter "PrintInstructions" will also be useful for an explicit print SCoP pass in a future patch. llvm-svn: 308746
* [Simplify] Remove unused instructions and accesses.Michael Kruse2017-07-201-0/+77
| | | | | | | | | | | | | | | | | | | | | | | | | | Use a mark-and-sweep algorithm to find and remove unused instructions and MemoryAccesses. This is useful in particular to remove scalar writes that are never used anywhere. A scalar write in a loop induces a write-after-write dependency that stops the loop iterations to be rescheduled. Such writes can be a result of previous transformations such as DeLICM and operand tree forwarding. It adds a new class VirtualInstruction that represents an instruction in a particular statement. At the moment an instruction can only belong to the statement that represents a BasicBlock. In the future, instructions can be in one of multiple statements representing a BasicBlock (Nandini's work), in different statements than its BasicBlock would indicate, and even multiple statements at once (by forwarding operand trees). It also integrates nicely with the VirtualUse class. ScopStmt::contains(Instruction*) currently uses the instruction's parent BasicBlock to check whether it contains the instruction. It will need to check the actual statement list when one of the aforementioned features become possible. Differential Revision: https://reviews.llvm.org/D35656 llvm-svn: 308626
* [Simplify] Ensure all counters are reset before next SCoP is processed. NFC.Michael Kruse2017-07-191-0/+1
| | | | llvm-svn: 308473
* [ScopInfo] Introduce tryGetValueStoredTobias Grosser2017-07-191-7/+1
| | | | | | | | | | | | | | | | | | | | Summary: This makes code more readable and allows to reuse this functionality in the future at other places. Suggested-by Michael Kruse in post-commit review of r307660. Reviewers: Meinersbur, bollu, gareevroman, efriedma, huihuiz, sebpop, simbuerg Reviewed By: Meinersbur Subscribers: pollydev, llvm-commits Tags: #polly Differential Revision: https://reviews.llvm.org/D35585 llvm-svn: 308435
* [Polly] Fix a typo [NFC]Tobias Grosser2017-07-161-2/+2
| | | | | | | | | | | | Reviewers: grosser, Meinersbur, bollu Tags: #polly Contributed-by: Nandini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D35459 llvm-svn: 308134
* [Simplify] Also remove redundant writes which originally came from PHI nodesTobias Grosser2017-07-111-1/+8
| | | | llvm-svn: 307660
* [Simplify] Use execution order of memory accesses.Michael Kruse2017-06-061-1/+2
| | | | | | | | | | | | Iterate through memory accesses in execution order (first all implicit reads, then explicit accesses, then implicit writes). In the test case this caused an implicit load to be handled as if it was loaded after the write. That is, the value being written before it is available. This fixes llvm.org/PR33323 llvm-svn: 304810
* [Simplify] Move to isl C++Tobias Grosser2017-05-211-19/+13
| | | | llvm-svn: 303507
* [isl++] Move isl raw_ostream printers into separate headerTobias Grosser2017-05-211-0/+1
| | | | | | | | Instead of relying on these functions to be part of the isl C++ bindings, we just define this functionality independently. This allows us to use isl C++ bindings that do not contain LLVM specific functionality. llvm-svn: 303503
* [Simplify] Fix r302986 that introduced non-inferrable templates.Siddharth Bhat2017-05-151-13/+19
| | | | | | | | | | | | | | - auto + decltype + template use was not inferrable in `Transform/Simplify.cpp accessesInOrder`. - changed code to explicitly construct required vector instead of using higher order iterator helpers. - Failing compiler spec: Apple LLVM version 7.3.0 (clang-703.0.31) Target: x86_64-apple-darwin15.6.0 llvm-svn: 303039
* [Simplify] Remove some leftover dead codeTobias Grosser2017-05-141-26/+0
| | | | llvm-svn: 303007
* [Simplify] Remove identical write removal. NFC.Michael Kruse2017-05-131-82/+2
| | | | | | | | | | | | | Removal of overwritten writes currently encompasses all the cases of the identical write removal. There is an observable behavioral change in that the last, instead of the first, MemoryAccess is kept. This should not affect the generated code, however. Differential Revision: https://reviews.llvm.org/D33143 llvm-svn: 302987
* [Simplify] Remove writes that are overwritten.Michael Kruse2017-05-131-2/+104
| | | | | | | | | | | | | | | | | | | | Remove memory writes that are overwritten by later writes. This works for StoreInsts: store double 21.0, double* %A store double 42.0, double* %A scalar writes at the end of a statement and mixes of these. Multiple writes can be the result of DeLICM, which might map multiple writes to the same location when it knows that these do no conflict (for instance because they write the same value). Such writes interfere with pattern-matched optimization such as gemm and may not get removed by other LLVM passes after code generation. Differential Revision: https://reviews.llvm.org/D33142 llvm-svn: 302986
* [Simplify] Reset all stats between runs.Michael Kruse2017-05-121-0/+3
| | | | llvm-svn: 302926
* [Simplify] Remove identical scalar writes.Michael Kruse2017-05-111-1/+107
| | | | | | | | | | | | | | | | | | | | | | After DeLICM, it is possible to have two writes of the same value to the same location in the same statement when it determined that those writes do not conflict (write the same value). Teach -polly-simplify to remove one of the writes. It interferes with the pattern matching of matrix-multiplication kernels and also seem to not be optimized away by LLVM. The algorthm is simple, has O(n^2) behaviour (n = max number of MemoryAccesses in a statement) and only matches the most obvious cases, but seem to be enough to pattern-match Boost ublas gemm. Not handled cases include: - StoreInst instructions (a.k.a. explicit writes), since the value might be loaded or overwritten between the two stores. - PHINode, especially LCSSA, when the PHI value matches with on other's. - Partial writes (in preparation) llvm-svn: 302805
* [Simplify] Mark variables as used. NFC.Michael Kruse2017-05-101-0/+1
| | | | | | Mark one more variable as used that is needed in assertions. llvm-svn: 302726
* [Simplify] Mark variables as used. NFC.Michael Kruse2017-05-101-0/+2
| | | | | | Mark variables as used that are needed in assertions. llvm-svn: 302725
* [Simplify] Add -polly-simplify pass.Michael Kruse2017-03-101-0/+285
This new pass removes unnecessary accesses and writes. It currently supports 2 simplifications, but more are planned. It removes write accesses that write a loaded value back to the location it was loaded from. It is a typical artifact from DeLICM. Removing it will get rid of bogus dependencies later in dependency analysis. It also removes statements without side-effects. ScopInfo already removes these, but the removal of unnecessary writes can result in more side-effect free statements. Differential Revision: https://reviews.llvm.org/D30820 llvm-svn: 297473
OpenPOWER on IntegriCloud