summaryrefslogtreecommitdiffstats
path: root/polly/lib/Transform
Commit message (Collapse)AuthorAgeFilesLines
...
* Do not use isl_set_project_out to get all loop prefixesRoman Gareev2017-08-081-3/+4
| | | | | | | | | | | | Currently, only convex isolation sets can be efficiently processed by isl. Consequently, as a temporary solution, we use a different algorithm for partial tile isolation that helps to build convex isolation sets in some cases. Reviewed-by: Tobias Grosser <tobias@grosser.es> Differential Revision: https://reviews.llvm.org/D36278 llvm-svn: 310374
* [DeLICM] Properly handle PHI writes becoming empty partial writes.Michael Kruse2017-08-081-3/+8
| | | | | | | | | | | | | It is possible that partial writes are empty (write is never executed). In this case, when in PHINode's incoming edge is never taken such that the incoming write becomes an empty partial write, if enabled. The issue is that when converting the union_map to an map, it's space cannot be derived from the union_map itself. Rather, we need to determine its space independently. This fixes test-suite's MultiSource/Benchmarks/ASC_Sequoia/CrystalMk. llvm-svn: 310348
* [ScheduleOptimizer] Make matmul pattern detection work with delicm outputTobias Grosser2017-08-082-35/+28
| | | | | | | | | | | | 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
* [DeLICM] Enable partial writesTobias Grosser2017-08-071-1/+1
| | | | | | | This allows us to remove more scalar dependences. While this feature is still rather experimental, we want to give it sufficient test coverage. llvm-svn: 310314
* [ZoneAlgo] Allow two writes that write identical values into same array slotTobias Grosser2017-08-071-5/+30
| | | | | | | | | Two write statements which write into the very same array slot generally are conflicting. However, in case the value that is written is identical, this does not cause any problem. Hence, allow such write pairs in this specific situation. llvm-svn: 310311
* [Polly] Fully-Indexed static expansionAndreas Simbuerger2017-08-071-0/+394
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This commit implements the initial version of fully-indexed static expansion. ``` for(int i = 0; i<Ni; i++) for(int j = 0; j<Ni; j++) S: B[j] = j; T: A[i] = B[i] ``` After the pass, we want this : ``` for(int i = 0; i<Ni; i++) for(int j = 0; j<Ni; j++) S: B[i][j] = j; T: A[i] = B[i][i] ``` For now we bail (fail) in the following cases: - Scalar access - Multiple writes per SAI - MayWrite Access - Expansion that leads to an access to the original array Furthermore: We still miss checks for escaping references to the array base pointers. A future commit will add the missing escape-checks to stay correct in those cases. The expansion is still locked behind a CLI-Option and should not yet be used. Patch contributed by: Nicholas Bonfante <bonfante.nicolas@gmail.com> Reviewers: simbuerg, Meinersbur, bollu Reviewed By: Meinersbur Subscribers: mgorny, llvm-commits, pollydev Differential Revision: https://reviews.llvm.org/D34982 llvm-svn: 310304
* [ForwardOpTree] Use known array content analysis to forward load instructions.Michael Kruse2017-08-073-56/+585
| | | | | | | | | | | | | | | | | 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
* [ScopInfo] Move Scop::getPwAffOnly to isl++ [NFC]Tobias Grosser2017-08-064-5/+5
| | | | llvm-svn: 310231
* [ScopInfo] Move Scop::getDomains to isl++ [NFC]Tobias Grosser2017-08-064-4/+4
| | | | llvm-svn: 310230
* [ScopInfo] Translate Scop::getParamSpace to isl++ [NFC]Tobias Grosser2017-08-061-8/+6
| | | | llvm-svn: 310224
* [ScopInfo] Move get*Writes/getReads/getAccesses to isl++Tobias Grosser2017-08-061-2/+2
| | | | llvm-svn: 310219
* [ScopInfo] Move ScopStmt::ScopStmt to isl++ [NFC]Tobias Grosser2017-08-061-4/+2
| | | | llvm-svn: 310210
* Move ScopInfo::getDomain(), getDomainSpace(), getDomainId() to isl++Tobias Grosser2017-08-063-11/+9
| | | | llvm-svn: 310209
* [unittests] Add unittest for getPartialTilePrefixesTobias Grosser2017-08-051-17/+1
| | | | | | | | In https://reviews.llvm.org/D36278 it was pointed out that the behavior of getPartialTilePrefixes is not very well understood. To allow for a better understanding, we first provide some basic unittests. llvm-svn: 310175
* [DeLICM] Refactor ZoneAlgorithm into ZoneAlgo.cpp. NFC.Michael Kruse2017-08-042-754/+624
| | | | | | | | Extract ZoneAlgorithm from DeLICM.cpp into its own file. It will gain a second use by the load forwarding part of -polly-optree. llvm-svn: 310146
* [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
* Move setNewAccessRelation to isl++Tobias Grosser2017-08-023-7/+7
| | | | llvm-svn: 309871
* [Polly][PM][WIP] Polly pass registrationPhilip Pfaffe2017-08-021-0/+23
| | | | | | | | | | | | | | | | | | | | | Summary: This patch is a first attempt at registering Polly passes with the LLVM tools. Tool plugins are still unsupported, but this registration is usable from the tools if Polly is linked into them (albeit requiring minimal patches to those tools). Registration requires a small amount of machinery (the owning analysis proxies), necessary for injecting ScopAnalysisManager objects into the calling tools. This patch is marked WIP because the registration is incomplete. Parsing manual pipelines is fully supported, but default pass injection into the O3 pipeline is lacking, mostly because there is opportunity for some redesign here, I believe. The first point of order would be insertion points. I think it makes sense to run before the vectorizers. Running Polly Early, however, is weird. Mostly because it actually is the default (which to me is unexpected), and because Polly runs it's own O1 pipeline. Why not instead insert it at an appropriate place somewhere after simplification happend? Running after the loop optimizers seems intuitive, but it also seems wasteful, since multiple consecutive loops might well be a single scop, and we don't need to run for all of them. My second request for comments would be regarding all those smallish helper passes we have, like PollyViewer, PollyPrinter, PollyImportJScop. Right now these are controlled by command line options, deciding whether they should be part of the Polly pipeline. What is your opinion on treating them like real passes, and have the user write an appropriate pipeline if they want to use any of them? Reviewers: grosser, Meinersbur, bollu Reviewed By: grosser Subscribers: llvm-commits, pollydev Tags: #polly Differential Revision: https://reviews.llvm.org/D35458 llvm-svn: 309826
* [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
* [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
* Silence -Wunused-variable warning in NDEBUG buildsReid Kleckner2017-08-011-3/+2
| | | | llvm-svn: 309730
* [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
* [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
* [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
* [ScheduleOptimizer] Translate to C++ bindingsRoman Gareev2017-07-261-385/+289
| | | | | | | | | | Translate the ScheduleOptimizer to use the new isl C++ bindings. Reviewed-by: Michael Kruse <llvm@meinersbur.de> Differential Revision: https://reviews.llvm.org/D35845 llvm-svn: 309119
* Move MemoryAccess::isStride* to isl++Tobias Grosser2017-07-241-3/+3
| | | | llvm-svn: 308927
* [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
* 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-233-12/+12
| | | | | | 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
* [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
* Move ScopArrayInfo to isl++Tobias Grosser2017-07-211-2/+4
| | | | | | This moves the full ScopArrayInfo class to isl++ llvm-svn: 308801
* [ScopInfo] Print instructions in dump().Michael Kruse2017-07-213-3/+3
| | | | | | | | | | | | | | | | | | | 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
* [ScopInfo] Integrate ScalarDefUseChain into polly::Scop. NFC.Michael Kruse2017-07-191-113/+16
| | | | | | | | | | | | | | | | | | | Before this patch, ScalarDefUseChain was a tool used by DeLICM to find all reads and writes of scalar accesses. It iterated once over all accesses and stores the accesses into maps. By integrating it into the Scop class, we can keep the maps up-to-date without the need for recomputing them. It will be needed for more than DeLICM in the future, such as SCoP simplification, code movement between virtual statements, and array expansion (GSoC project). Compared to ScalarUseDefChain, we save two maps by finding the ScopStmt a Def/PHIRead must reside in, and use its already existing lookup function to find the MemoryAccess. Differential Revision: https://reviews.llvm.org/D35631 llvm-svn: 308495
* Make the pattern matching work with modified memory accessesRoman Gareev2017-07-191-10/+10
| | | | | | | | | | | | | Some optimizations (e.g., DeLICM) can modify memory accesses (e.g., change their MemoryKind). Consequently, the pattern matching should take it into the account. Reviewed-by: Tobias Grosser <tobias@grosser.es>, Michael Kruse <llvm@meinersbur.de> Differential Revision: https://reviews.llvm.org/D33138 llvm-svn: 308494
* [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
OpenPOWER on IntegriCloud