summaryrefslogtreecommitdiffstats
path: root/polly/lib/Transform/ForwardOpTree.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
* [Polly] Migrate llvm::make_unique to std::make_uniqueJonas Devlieghere2019-08-141-1/+1
| | | | | | | | | | Now that we've moved to C++14, we no longer need the llvm::make_unique implementation from STLExtras.h. This patch is a mechanical replacement of (hopefully) all the llvm::make_unique instances across the monorepo. Differential revision: https://reviews.llvm.org/D66259 llvm-svn: 368935
* Apply include-what-you-use #include removal suggestions. NFC.Michael Kruse2019-03-281-1/+0
| | | | | | | | | | | | 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
* [ForwardOpTree] Replace isl foreach calls with for loopsTobias Grosser2018-07-171-5/+5
| | | | llvm-svn: 337242
* [ZoneAlgo] Use getDefToTarget in makeValInst. NFC.Michael Kruse2018-06-261-105/+0
| | | | | | | | | | | | Move the optimized getDefToTarget() from ForwardOpTree to ZoneAlgo such that it can be used by makeValInst. This reduces the compile time of GrTestUtils of the aosp buildbot from 2m46s to 21s, which should fix the timeout issue. Differential Revision: https://reviews.llvm.org/D48579 llvm-svn: 335606
* [OpTree] Introduce shortcut for computing the def->target mapping. NFCI.Michael Kruse2018-06-061-0/+45
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | In case the schedule has not changed and the operand tree root uses a value defined in an ancestor loop, the def-to-target mapping is trivial. For instance, the SCoP for (int i < 0; i < N; i+=1) { DefStmt: D = ...; for (int j < 0; j < N; j+=1) { TargetStmt: use(D); } } has DefStmt-to-TargetStmt mapping of { DefStmt[i] -> TargetStmt[i,j] } This should apply on the majority of def-to-target mappings. This patch detects this case and directly constructs the expected mapping. It assumes that the mapping never crosses the loop header DefStmt is in, which ForwardOpTree does not support at the moment anyway. Differential Revision: https://reviews.llvm.org/D47752 llvm-svn: 334134
* [ZoneAlgo] Make ZoneAlgorithm::isNormalized out-of-quota safe.Michael Kruse2018-05-311-1/+2
| | | | | | | | | | | | | | | The aosp-O3-polly-before-vectorizer-unprofitable buildbot currently fails in ZoneAlgorithm::isNormalized, presumably because an out-of-quota happens in that function. Modify ZoneAlgorithm::isNormalized to return an isl::boolean such it can report an error. In the failing case, it was called in an assertion in ForwardOpTree. Allow to pass the assertion in an out-of-quota event, a condition that is later checked before forwarding an operand tree. llvm-svn: 333709
* [ForwardOpTree] Use less computationally expensive method to compute ↵Michael Kruse2018-05-291-59/+68
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | def-to-target map. NFCI. When forwarding a LoadInst to another statement, a map that translates their domain is needed. Before this patch, is was computed by appending the def-to-use map to the def-to-target of the operand tree's target. This patch lets the new method getDefToTarget do this. This is computationally less expensive due to: * Caching of the result such that it can be used for multiple operands tree to the same target. * The map is only computed when there is a LoadInst that needs it. * It is only computed for the statement requiring the translator map, instead of having an intermediate result for every edge in the operand tree. The downside is that this scheme cannot handle forwarding from a previous loop iteration (which would require the entire path from statement to target). Since ForwardOpTree currently does not support forwarding across loop iterations (SCEV expressions would need to be transformed), this was not needed anyway. Differential Revision: https://reviews.llvm.org/D47385 llvm-svn: 333426
* [polly] Update uses of DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-151-21/+24
| | | | | | | | | | | 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
* Adjust to clang-format changesTobias Grosser2018-03-201-1/+0
| | | | llvm-svn: 328005
* Port ScopInfo to the isl cpp bindingsPhilip Pfaffe2017-11-191-1/+1
| | | | | | | | | | | | | | | | | | | | | 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
* [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
* [ZoneAlgo/ForwardOpTree] Normalize PHIs to their known incoming values.Michael Kruse2017-10-311-2/+11
| | | | | | | | | | | | | | | | | | | | | | | 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
* [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
* [ForwardOpTree] Fix out-of-quota in assertion.Michael Kruse2017-10-021-1/+1
| | | | llvm-svn: 314661
* [ForwardOpTree] Allow out-of-quota in examination part of forwardTree.Michael Kruse2017-09-191-13/+29
| | | | | | | | | | | | | | | | | | | | | | | | Computing the reaching definition in forwardTree() can take a long time if the coefficients are large. When the forwarding is carried-out (doIt==true), forwardTree() must execute entirely or not at all to get a consistent output, which means we cannot just allow out-of-quota errors to happen in the middle of the processing. We introduce the class IslQuotaScope which allows to opt-in code that is conformant and has been tested with out-of-quota events. In case of ForwardOpTree, out-of-quota is allowed during the operand tree examination, but not during the transformation. The same forwardTree() recursion is used for examination and execution, meaning that the reaching definition has already been computed in the examination tree walk and cached for reuse in the transformation tree walk. This should fix the time-out of grtestutils.ll of the asop buildbot. If the compilation still takes too long, we can reduce the max-operations allows for -polly-optree. Differential Revision: https://reviews.llvm.org/D37984 llvm-svn: 313690
* [ForwardOpTree] Test the max operations quota.Michael Kruse2017-09-181-1/+1
| | | | | | | | | | | | cl::opt<unsigned long> is not specialized and hence the option -polly-optree-max-ops impossible to use. Replace by supported option cl::opt<unsigned>. Also check for an error state when computing the written value, which happens when the quota runs out. llvm-svn: 313546
* [ForwardOptTree] Remove redundant simplify(). NFC.Michael Kruse2017-09-181-1/+0
| | | | | | The result of computeKnown has already been simplified. llvm-svn: 313526
* [ForwardOp] Remove read accesses for all instructions that have been movedTobias Grosser2017-09-031-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Before this patch, OpTree did not consider forwarding an operand tree consisting of only single LoadInst as useful. The motivation was that, like an access to a read-only variable, it would just replace one MemoryAccess by another. However, in contrast to read-only accesses, this would replace a scalar access by an array access, which is something worth doing. In addition, leaving scalar MemoryAccess is problematic in that VirtualUse prioritizes inter-Stmt use over intra-Stmt. It was possible that the same LLVM value has a MemoryAccess for accessing the remote Stmt's LoadInst as well as having the same LoadInst in its own instruction list (due to being forwarded from another operand tree). With this patch we ensure that if a LoadInst is forwarded is any operand tree, also the operand tree containing just the LoadInst is forwarded as well, which effectively removes the scalar MemoryAccess such that only the array access remains, not both. Thanks Michael for the detailed explanation. Reviewers: Meinersbur, bellu, singam-sanjay, gareevroman Subscribers: hfinkel, pollydev, llvm-commits Tags: #polly Differential Revision: https://reviews.llvm.org/D37424 llvm-svn: 312456
* [ForwardOpTree] Fix typos. NFC.Michael Kruse2017-09-031-2/+2
| | | | llvm-svn: 312446
* [ForwardOpTree] Allow forwarding in the presence of region statementsTobias Grosser2017-08-311-4/+0
| | | | | | | | | | | | | | | | | | Summary: After region statements now also have instruction lists, this is a straightforward extension. Reviewers: Meinersbur, bollu, singam-sanjay, gareevroman Reviewed By: Meinersbur Subscribers: hfinkel, pollydev, llvm-commits Tags: #polly Differential Revision: https://reviews.llvm.org/D37298 llvm-svn: 312249
* [ZoneAlgo] More fine-grained bail-out.Michael Kruse2017-08-281-5/+1
| | | | | | | | | | | | | | | | | | | | | ZoneAlgo used to bail out for the complete SCoP if it encountered something violating its assumption. This meant the neither OpTree can forward any load nor DeLICM do anything in such cases, even if their transformations are unrelated to the violations. This patch adds a list of compatible elements (currently with the granularity of entire arrays) that can be used for analysis. OpTree and DeLICM can then check whether their transformations only concern compatible elements, and skip non-compatible ones. This will be useful for e.g. Polybench's benchmarks covariance, correlation, bicg, doitgen, durbin, gramschmidt, adi that have assumption violation, but which are not necessarily relevant for all transformations. Differential Revision: https://reviews.llvm.org/D37219 llvm-svn: 311929
* [Polly] Fix some Clang-tidy modernize and Include What You Use warnings; ↵Eugene Zelenko2017-08-241-22/+36
| | | | | | other minor fixes (NFC). llvm-svn: 311704
* Add more statistics.Michael Kruse2017-08-231-0/+19
| | | | | | | | | | | | | | | | 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
* Fix two warnings in polly, -Wmismatched-tags and -WreorderReid Kleckner2017-08-101-1/+1
| | | | llvm-svn: 310667
* Remove dependency of Scop::getStmtFor(Inst) on getStmtFor(BB). NFC.Michael Kruse2017-08-091-2/+5
| | | | | | | | | | | | | We are working towards removing uses of Scop::getStmtFor(BB). In this patch, we remove dependency of Scop::getStmtFor(Inst) on getStmtFor(BB). To do so, we introduce a map of instructions to their corresponding scop statements and use it to get the instructions' statement. Contributed-by: Nandini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D35663 llvm-svn: 310494
* [ForwardOpTree] Set DEBUG_TYPE to "polly-optree".Michael Kruse2017-08-091-1/+1
| | | | | | | | | The previous value of "polly-delicm" was forgotten to to be changed when ForwardOpTree was split from DeLICM. Thanks to Tobias for noticing! llvm-svn: 310465
* [ForwardOpTree] Use known array content analysis to forward load instructions.Michael Kruse2017-08-071-37/+459
| | | | | | | | | | | | | | | | | This is an addition to the -polly-optree pass that reuses the array content analysis from DeLICM to find array elements that contain the same value as the value loaded when the target statement instance is executed. The analysis is now enabled by default. The known content analysis could also be used to rematerialize any llvm::Value that was written to some array element, but currently only loads are forwarded. Differential Revision: https://reviews.llvm.org/D36380 llvm-svn: 310279
* [ForwardOpTree] Refactor out forwardSpeculatable(). NFC.Michael Kruse2017-08-041-61/+88
| | | | | | | | | | The method forwardSpeculatable forwards speculatively executable instructions and is currently the only way to forward an instruction. In the future we intend to add more methods. llvm-svn: 310056
* [ForwardOpTree] Execute canForwardTree also in release builds.Michael Kruse2017-08-011-7/+9
| | | | | | | | | | | | Commit r309730 moved the call to canForwardTree into an assert(), even though this function has side-effects if its DoIt parameter is true. To avoid a warning in release builds, do an (void)Execution of its result instead. To avoid such confusion in the future, rename canForwardTree() to forwardTree(). llvm-svn: 309753
* Silence -Wunused-variable warning in NDEBUG buildsReid Kleckner2017-08-011-3/+2
| | | | llvm-svn: 309730
* [ForwardOpTree] Support synthesizable values.Michael Kruse2017-07-311-10/+30
| | | | | | | | | | | | | | | | | | | | | | | | | This allows -polly-optree to move instructions that depend on synthesizable values. The difficulty for synthesizable values is that their value depends on the location. When it is moved over a loop header, and the SCEV expression depends on the loop induction variable (SCEVAddRecExpr), it would use the current induction variable instead of the last one. At the moment we cannot forward PHI nodes such that crossing the header of loops referenced by SCEVAddRecExpr is not possible (assuming the loop header has at least two incoming blocks: for entering the loop and the backedge, such any instruction to be forwarded must have a phi between use and definition). A remaining issue is when the forwarded value is used after the loop, but is only synthesizable inside the loop. This happens e.g. if ScalarEvolution is unable to determine the number of loop iterations or the initial loop value. We do not forward in this situation. Differential Revision: https://reviews.llvm.org/D36102 llvm-svn: 309609
* [ForwardOpTree] Properly indent enumeration in comment. NFC.Michael Kruse2017-07-241-4/+4
| | | | llvm-svn: 308887
* [ForwardOpTree] Rename FD_CanForward to FD_CanForwardLeaf. NFC.Michael Kruse2017-07-241-4/+4
| | | | | | To make the meaning and distinction to FD_CanForwardTree clearer. llvm-svn: 308886
* [ForwardOpTree] Add comments to ForwardingDecision items. NFC.Michael Kruse2017-07-241-0/+30
| | | | | | | In particular, explain the difference between FD_CanForward and FD_CanForwardTree. llvm-svn: 308885
* [ForwardOpTree] Support read-only value uses.Michael Kruse2017-07-241-5/+21
| | | | | | | | | | | | Read-only values (values defined before the SCoP) require special handing with -polly-analyze-read-only-scalars=true (which is the default). If active, each use of a value requires a read access. When a copied value uses a read-only value, we must also ensure that such a MemoryAccess is available or is created. Differential Revision: https://reviews.llvm.org/D35764 llvm-svn: 308876
* [ForwardOpTree] Fix mixup in comment. NFC.Michael Kruse2017-07-241-2/+2
| | | | | | | | The cases DoIt==false and DoIt==true were mixed up. Thanks to Siddharth for noticing. llvm-svn: 308874
* [ScopInfo] Fix typo in method name. NFC.Michael Kruse2017-07-241-1/+1
| | | | | | | | prependInstrunction -> prependInstruction Thanks Nandini for noticing. llvm-svn: 308873
* [ForwardOpTree] Support hoisted invariant loads.Michael Kruse2017-07-221-5/+1
| | | | | | | | Hoisted loads can be trivially supported because there are no MemoryAccess to be modified, the loaded value is just available at code generation. llvm-svn: 308826
* [ForwardOpTree] Introduce the -polly-optree pass.Michael Kruse2017-07-221-0/+356
This pass 'forwards' operand trees into statements that use them in order to avoid scalar dependencies. This minimal implementation handles only the case of speculatable instructions. We will successively add support for: - Hoisted loads - Read-only values - Synthesizable values - Loads - PHIs - Forwarding only parts of the tree Differential Revision: https://reviews.llvm.org/D35754 llvm-svn: 308825
OpenPOWER on IntegriCloud