summaryrefslogtreecommitdiffstats
path: root/polly/lib/Support
Commit message (Collapse)AuthorAgeFilesLines
...
* [ScopHelper] Do not crash on unreachable blocksTobias Grosser2017-09-031-1/+9
| | | | | | This resolves llvm.org/PR34433. Thanks to Zhendong Su for reporting. llvm-svn: 312451
* [ScopDetect/Info] Look through PHIs that follow an error blockTobias Grosser2017-09-021-0/+26
| | | | | | | | In case a PHI node follows an error block we can assume that the incoming value can only come from the node that is not an error block. As a result, conditions that seemed non-affine before are now in fact affine. llvm-svn: 312410
* Fix Memory Access of failing tests.Michael Kruse2017-09-011-1/+1
| | | | | | | | | | | Mark scalar dependences for different statements belonging to same BB as 'Inter'. Contributed-by: Nandini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D37147 llvm-svn: 312324
* [ForwardOpTree] Allow forwarding in the presence of region statementsTobias Grosser2017-08-311-5/+9
| | | | | | | | | | | | | | | | | | 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
* Do not consider mem intrinsics as error.Michael Kruse2017-08-291-0/+4
| | | | | | | | | | The intrinsics memset, memcopy and memmove do have their memory accesses modeled by ScopBuilder. Do not consider them error-case behavior. Test case will come with a future patch that requires memory intrinsics outside of error blocks. llvm-svn: 312021
* Skip ignored intrinsics.Michael Kruse2017-08-291-1/+1
| | | | | | | | | | | | Commit r252725 introduced a "return false" if an ignored intrinsics was found. The consequence of this was that the mere existence of an ignored intrinsic (such as llvm.dbg.value) before a call that would have qualified the block to be an error block, to not be an error block. The obvious goal was to just skip ignored intrinsics, not changing the meaning of what an error block is. llvm-svn: 312020
* [ZoneAlgo] More fine-grained bail-out.Michael Kruse2017-08-281-0/+5
| | | | | | | | | | | | | | | | | | | | | 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
* Add more statistics.Michael Kruse2017-08-231-2/+2
| | | | | | | | | | | | | | | | 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
* [DeLICM] Fix unused zone for writes without in-between read.Michael Kruse2017-08-211-11/+15
| | | | | | | | | | | | | | The implementation of computeArrayUnused did not consider writes without reads before, except for the first write in the SCoP. This caused it to 'forget' writes directly following another write. This patch re-adds the entire reaching defintion of a write that has not been covered before by a read. This fixes Polybench 4.2 2mm where only one of the matrix-multiplication was detected. llvm-svn: 311403
* [ScopInliner] Add a simple Scop-based inliner to polly.Siddharth Bhat2017-08-171-0/+1
| | | | | | | | | | | | | We add a ScopInliner pass which inlines functions based on a simple heuristic: Let `g` call `f`. If we can model all of `f` as a Scop, we inline `f` into `g`. This requires `-polly-detect-full-function` to be enabled. So, the pass asserts that `-polly-detect-full-function` is enabled. Differential Revision: https://reviews.llvm.org/D36832 llvm-svn: 311126
* Add rewrite by-reference parameter passTobias Grosser2017-08-171-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This pass detangles induction variables from functions, which take variables by reference. Most fortran functions compiled with gfortran pass variables by reference. Unfortunately a common pattern, printf calls of induction variables, prevent in this situation the promotion of the induction variable to a register, which again inhibits any kind of loop analysis. To work around this issue we developed a specialized pass which introduces separate alloca slots for known-read-only references, which indicate the mem2reg pass that the induction variables can be promoted to registers and consquently enable SCEV to work. We currently hardcode the information that a function _gfortran_transfer_integer_write does not read its second parameter, as dragonegg does not add the right annotations and we cannot change old dragonegg releases. Hopefully flang will produce the right annotations. Reviewers: Meinersbur, bollu, singam-sanjay Reviewed By: bollu Subscribers: mgorny, pollydev, llvm-commits Tags: #polly Differential Revision: https://reviews.llvm.org/D36800 llvm-svn: 311066
* [JSON][PM] Port json import/export over to new pmPhilip Pfaffe2017-08-102-1/+5
| | | | | | | | | | | | | | | | Summary: I pulled out all functionality into static functions, and use those both in the legacy passes and in the new ones. Reviewers: grosser, Meinersbur, bollu Reviewed By: Meinersbur Subscribers: llvm-commits, pollydev Differential Revision: https://reviews.llvm.org/D36578 llvm-svn: 310597
* [ManagedMemoryRewrite] Introduce a new pass to rewrite modules to use ↵Siddharth Bhat2017-08-091-2/+8
| | | | | | | | | | | | | | | | managed memory. This pass is useful to automatically convert a codebase that uses malloc/free to use their managed memory counterparts. Currently, rewrite malloc and free to the `polly_{malloc,free}Managed` variants. A future patch will teach ManagedMemoryRewrite to rewrite global arrays as pointers to globally allocated managed memory. Differential Revision: https://reviews.llvm.org/D36513 llvm-svn: 310471
* [ISLTools/ZoneAlgo] Make distributeDomain and filterKnownValInst ↵Michael Kruse2017-08-091-4/+3
| | | | | | | | | | | | | | | isl_error_quota proof. distributeDomain() and filterKnownValInst() are used in a scop of ForwardOpTree that limits the number of isl operations. Therefore some isl functions may return null after any operation. Remove assertion that assume non-null results and handle isl_*_foreach returning isl::stat::error. I hope this fixes the crash of the asop buildbot at ihevc_recon.c. llvm-svn: 310461
* [RegisterPasses] Run polly-simplify also right after scop modelingTobias Grosser2017-08-081-0/+2
| | | | | | | | This allows us to get rid of stores that are overwritten within the very same basic block, without ever being read beforehand. This simplification is necessary for delicm to run on pb4's correlation. llvm-svn: 310369
* Change Polly's position to "before-vectorizer"Tobias Grosser2017-08-071-1/+1
| | | | | | | | | | | | | | | | | | | | | Polly has traditionally always been executed at the beginning of the pass pipeline as LLVM's inliner and DeLICM passes introduced plenty of scalar dependences which prevented any kind of useful high-level loop optimizations later in the pass pipeline. With DeLICM now being available, Polly can also run optimizations when folded into the pass pipeline. This has the benefit that Polly should now be more effective on C++ code and as an additional bonus, no additional early canonicalization phase must be run. As a result, Polly touches the code only if it applies a transformation. Code that does not benefit from Polly is not touched and consequently will have the very same execution time as without Polly enabled. Random performance changes, as could sometimes be observed with polly-position=early are consequently not possible any more. If performance is changed, this is due to Polly is choosing to perform a transformation. If this choice is wrong, it can be fixed directly in Polly. http://polly.llvm.org/docs/Architecture.html#polly-in-the-llvm-pass-pipeline llvm-svn: 310319
* Enable delicm to automatically remove scalar loop carried dependencesTobias Grosser2017-08-071-1/+1
| | | | | | | While this code is still rather we enable it by default to get better test coverage. llvm-svn: 310313
* [Polly] Fully-Indexed static expansionAndreas Simbuerger2017-08-071-0/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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-071-0/+15
| | | | | | | | | | | | | | | | | 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-061-1/+1
| | | | llvm-svn: 310231
* [ScopInfo] Translate Scop::getIdForParam to isl++ [NFC]Tobias Grosser2017-08-061-1/+1
| | | | llvm-svn: 310220
* [VirtualInstruction] Handle MetadataAsValue as constant.Michael Kruse2017-08-031-1/+1
| | | | | | | | | | | | | | The complication of bspatch.cc of the AOSP buildbot currently fails presumably because the occurance of a MetadataAsValue in an operand. This kind of value can occur as operands of intrinsics, the typical example being the debug intrinsics. Polly currently ignores the debug intrinsics and it is not yet clear which other intrinic might occur. For such cases, and to unbreak the AOSP buildbot, treat a MetadataAsValue as a constant because it can be referenced without modification in generated code. llvm-svn: 309992
* [VirtualInstruction] Avoid use of getStmtFor(BB). NFC.Michael Kruse2017-08-031-1/+6
| | | | | | | | | | | With this patch, we get rid of the last use of getStmtFor(BB). Here this is done by getting the last statement of the incoming block in case the user is a phi node; otherwise just fetching the statement comprising the instruction for which the virtual use is being created. Differential Revision: https://reviews.llvm.org/D36268 llvm-svn: 309947
* Enable simplify and forward-op-tree by defaultTobias Grosser2017-08-021-2/+2
| | | | | | | | | These passes have been tested over the last month and should generally help to remove scalar data dependences in Polly. We enable them to give them even wider test coverage. Large performance regressions and any kind of correctness regressions are not expected. llvm-svn: 309878
* Replace asserts with llvm_unreachable to clarify intentTobias Grosser2017-08-021-2/+2
| | | | llvm-svn: 309856
* [Polly][PM][WIP] Polly pass registrationPhilip Pfaffe2017-08-023-2/+240
| | | | | | | | | | | | | | | | | | | | | 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
* [Simplify] Do not remove dependencies of phis within region stmts.Michael Kruse2017-07-281-1/+2
| | | | | | | These were wrongly assumed to be phi nodes that require MemoryKind::PHI accesses. llvm-svn: 309454
* [VirtualInstruction] Do not iterate over a region statement's instruction ↵Michael Kruse2017-07-281-0/+1
| | | | | | | | | list. NFC. It should be empty anyways. In this case it would even be redundant because we just all all instructions in region statements. llvm-svn: 309453
* [ScopBuilder/Simplify] Refactor isEscaping. NFC.Michael Kruse2017-07-271-20/+2
| | | | | | | | | | | | ScopBuilder and Simplify (through VirtualInstruction.cpp) previously used this functionality in their own implementation. Refactor them both into a common one into the Scop class. BlockGenerator also makes use of a similiar functionality, but also records outside users and takes place after region simplification. Merging it as well would be more complicated. llvm-svn: 309273
* [Simplify] Count PHINodes in simplifiable exit nodes as escaping use.Michael Kruse2017-07-271-0/+7
| | | | | | | | | After region exit simplification, the incoming block of a phi node in the SCoP region's exit block lands outside of the region. Since we treat SCoPs as if this already happened, we need to account for that when looking for outside uses of scalars (i.e. escaping scalars). llvm-svn: 309271
* [Simplify] Fix invalid removal write for escaping values.Michael Kruse2017-07-261-2/+2
| | | | | | | | | A PHI node's incoming block is the user of its operand, not the PHI's parent. Assuming the PHINode's parent being the user lead to the removal of a MemoryAccesses because its use was assumed to be inside of the SCoP. llvm-svn: 309164
* [SCEVValidator] Loop exit values of loops before the SCoP are synthesizable.Michael Kruse2017-07-261-4/+0
| | | | | | | | | | | | | | | | | | | | | | | In the following loop: int i; for (i = 0; i < func(); i+=1) ; SCoP: for (int j = 0; j<n; j+=1) S(i, j) The value i is synthesizable in the SCoP that includes only the j-loop. This is because i is fixed within the SCoP, it is irrelevant whether it originates from another loop. This fixes a strange case where a PHI was synthesiable in a SCoP, but not its incoming value, triggering an assertion. This should fix MultiSource/Applications/sgefa/sgefa of the perf-x86_64-penryn-O3-polly-before-vectorizer-unprofitable buildbot. llvm-svn: 309109
* [ScopInfo] Rename ScopStmt::contains(BB) to represents(BB). NFC.Michael Kruse2017-07-251-1/+1
| | | | | | | | | | | In future, there will be no more a 1:1 correspondence between statements and basic blocks, the name `contains` does not correctly capture their relationship. A BB may infact comprise of multiple statements; hence we describe a statement 'representing' a basic block. Differential Revision: https://reviews.llvm.org/D35838 llvm-svn: 308982
* [ForwardOpTree] Introduce the -polly-optree pass.Michael Kruse2017-07-221-0/+9
| | | | | | | | | | | | | | | | | | 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
* [Polly][GPGPU] Added SPIR Code Generation and Corresponding Runtime Support ↵Philipp Schaad2017-07-211-1/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | for Intel Summary: Added SPIR Code Generation to the PPCG Code Generator. This can be invoked using the polly-gpu-arch flag value 'spir32' or 'spir64' for 32 and 64 bit code respectively. In addition to that, runtime support has been added to execute said SPIR code on Intel GPU's, where the system is equipped with Intel's open source driver Beignet (development version). This requires the cmake flag 'USE_INTEL_OCL' to be turned on, and the polly-gpu-runtime flag value to be 'libopencl'. The transformation of LLVM IR to SPIR is currently quite a hack, consisting in part of regex string transformations. Has been tested (working) with Polybench 3.2 on an Intel i7-5500U (integrated graphics chip). Reviewers: bollu, grosser, Meinersbur, singam-sanjay Reviewed By: grosser, singam-sanjay Subscribers: pollydev, nemanjai, mgorny, Anastasia, kbarton Tags: #polly Differential Revision: https://reviews.llvm.org/D35185 llvm-svn: 308751
* Annotate dump() functions with LLVM_DUMP_METHOD. NFC.Michael Kruse2017-07-211-2/+2
| | | | llvm-svn: 308749
* [NFC] [RegisterPasses] Fix typo: To early -> too early.Siddharth Bhat2017-07-211-1/+1
| | | | llvm-svn: 308743
* [Simplify] Remove unused instructions and accesses.Michael Kruse2017-07-201-0/+273
| | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Make byref llvm::Use parameters const. NFC.Michael Kruse2017-07-192-2/+3
| | | | llvm-svn: 308522
* [Invariant Loads] Do not consider invariant loads to have dependences.Siddharth Bhat2017-07-132-5/+23
| | | | | | | | | | | | | | | | | We need to relax constraints on invariant loads so that they do not create fake RAW dependences. So, we do not consider invariant loads as scalar dependences in a region. During these changes, it turned out that we do not consider `llvm::Value` replacements correctly within `PPCGCodeGeneration` and `ISLNodeBuilder`. The replacements dictated by `ValueMap` were not being followed in all places. This was fixed in this commit. There is no clean way to decouple this change because this bug only seems to arise when the relaxed version of invariant load hoisting was enabled. Differential Revision: https://reviews.llvm.org/D35120 llvm-svn: 307907
* Introduce a hybrid target to generate code for either the GPU or CPUSingapuram Sanjay Srivallabh2017-06-301-13/+16
| | | | | | | | | | | | | | | | | | | | | Summary: Introduce a "hybrid" `-polly-target` option to optimise code for either the GPU or CPU. When this target is selected, PPCGCodeGeneration will attempt first to optimise a Scop. If the Scop isn't modified, it is then sent to the passes that form the CPU pipeline, i.e. IslScheduleOptimizerPass, IslAstInfoWrapperPass and CodeGeneration. In case the Scop is modified, it is marked to be skipped by the subsequent CPU optimisation passes. Reviewers: grosser, Meinersbur, bollu Reviewed By: grosser Subscribers: kbarton, nemanjai, pollydev Tags: #polly Differential Revision: https://reviews.llvm.org/D34054 llvm-svn: 306863
* [ScopInfo] Do not use ScopStmt in Domain derivation of ScopInfo. NFCMichael Kruse2017-06-291-0/+14
| | | | | | | | | | | | | | ScopStmts were being used in the computation of the Domain of the SCoPs in ScopInfo. Once statements are split, there will not be a 1-to-1 correspondence between Stmts and Basic blocks. Thus this patch avoids the use of getStmtFor() by creating a map of BB to InvalidDomain and using it to compute the domain of the statements. Contributed-by: Nanidini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D33942 llvm-svn: 306667
* Initializing NVPTX backend within PollySingapuram Sanjay Srivallabh2017-06-291-0/+5
| | | | | | | | | | | | | | | | | Summary: The NVPTX backend is now initialised within Polly. A language front-end need not be modified to initialise the backend, just for Polly. Reviewers: Meinersbur, grosser Reviewed By: Meinersbur Subscribers: vchuravy, mgorny Tags: #polly Differential Revision: https://reviews.llvm.org/D31859 llvm-svn: 306649
* [PPCGCodeGeneration] Enable GPU code generation with invariant loads.Siddharth Bhat2017-06-251-5/+0
| | | | | | | | | | The condition that disallowed code generation in PPCGCodeGeneration with invariant loads is not required. I haven't been able to construct a counterexample where this generates invalid code. Differential Revision: https://reviews.llvm.org/D34604 llvm-svn: 306245
* Don't check side effects for functions outside of SCoPEli Friedman2017-06-141-4/+5
| | | | | | | | | | | | In r304074 we introduce a patch to accept results from side effect free functions into SCEV modeling. This causes rejection of cases where the call is happening outside the SCoP. This patch checks if the call is outside the Region and treats the results as a parameter (SCEVType::PARAM) to the SCoP instead of returning SCEVType::INVALID. Patch by Sameer Abu Asal. llvm-svn: 305423
* [NFC] Fix typo in `ImportJScop` declaration.Siddharth Bhat2017-06-121-1/+1
| | | | | | | | Contributed by: Singapuram Sanjay Differential Revision: https://reviews.llvm.org/D34079 llvm-svn: 305183
* Fix a lot of typos. NFC.Michael Kruse2017-06-082-3/+3
| | | | llvm-svn: 304974
* Revert "[NFC] Fix formatting & typecast issue. Build succeeds."Siddharth Bhat2017-05-291-1/+1
| | | | | | | | Should not have 'fixed' the formatting issue, I did not have the most recent version of `clang-format`. This reverts commit 761b1268359e14e59142f253d77864a29d55c56c. llvm-svn: 304148
* [NFC] Fix formatting & typecast issue. Build succeeds.Siddharth Bhat2017-05-291-1/+1
| | | | | | | | | - Fix formatting in `RegisterPasses.cpp`. - `assert` tried to compare `isl::boolean` against `long`. Explicitly construct `bool` from `isl::boolean`. This allows the implicit cast of `bool` to `long. llvm-svn: 304146
* Adapt to recent clang-format changesTobias Grosser2017-05-291-1/+1
| | | | llvm-svn: 304136
OpenPOWER on IntegriCloud