summaryrefslogtreecommitdiffstats
path: root/polly/lib
Commit message (Collapse)AuthorAgeFilesLines
...
* [ScopInfo] Allow invariant loads in branch conditionsTobias Grosser2017-09-252-2/+16
| | | | | | | In case the value used in a branch condition is a load instruction, assume this load to be invariant. llvm-svn: 314146
* [ScopInfo] Allow uniform branch conditionsTobias Grosser2017-09-253-1/+31
| | | | | | | If all but one branch come from an error condition and the incoming value from this branch is a constant, we can model this branch. llvm-svn: 314116
* [ScopDetect/Info] Look through PHIs that follow an error blockTobias Grosser2017-09-244-19/+54
| | | | | | | | | | | 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. This is a recommit of r312663 after fixing test/Isl/CodeGen/phi_after_error_block_outside_of_scop.ll llvm-svn: 314075
* [IslExprBuilder] Do not generate RTC with more than 64 bitTobias Grosser2017-09-232-0/+37
| | | | | | | | | | Such RTCs may introduce integer wrapping intrinsics with more than 64 bit, which are translated to library calls on AOSP that are not part of the runtime and will consequently cause linker errors. Thanks to Eli Friedman for reporting this issue and reducing the test case. llvm-svn: 314065
* [Support] Rename tool_output_file to ToolOutputFile, NFCReid Kleckner2017-09-232-3/+3
| | | | | | | This class isn't similar to anything from the STL, so it shouldn't use the STL naming conventions. llvm-svn: 314050
* [DeLICM] Allow non-injective PHIRead->PHIWrite mapping.Michael Kruse2017-09-211-1/+13
| | | | | | | | | | | | | | | | | | | | Remove an assertion that tests the injectivity of the PHIRead -> PHIWrite relation. That is, allow a single PHI write to be used by multiple PHI reads. This may happen due to some statements containing the PHI write not having the statement instances that would overwrite the previous incoming value due to (assumed/invalid) contexts. This result in that PHI write is mapped to multiple targets which is not supported. Codegen will select one one of the targets using getAddressFunction(). However, the runtime check should protect us from this case ever being executed. We therefore allow injective PHI relations. Additional calculations to detect/santitize this case would probably not be worth the compuational effort. This fixes llvm.org/PR34485 llvm-svn: 313902
* [ScopInfo] Use map for value def/PHI read accesses.Michael Kruse2017-09-211-10/+8
| | | | | | | | | | | | | | | | | | | | | | | Before this patch, ScopInfo::getValueDef(SAI) used getStmtFor(Instruction*) to find the MemoryAccess that writes a MemoryKind::Value. In cases where the value is synthesizable within the statement that defines, the instruction is not added to the statement's instruction list, which means getStmtFor() won't return anything. If the synthesiable instruction is not synthesiable in a different statement (due to being defined in a loop that and ScalarEvolution cannot derive its escape value), we still need a MemoryKind::Value and a write to it that makes it available in the other statements. Introduce a separate map for this purpose. This fixes MultiSource/Benchmarks/MallocBench/cfrac where -polly-simplify could not find the writing MemoryAccess for a use. The write was not marked as required and consequently was removed. Because this could in principle happen as well for PHI scalars, add such a map for PHI reads as well. llvm-svn: 313881
* Check whether IslAstInfo and DependenceInfo were computed for the same Scop.Michael Kruse2017-09-213-2/+32
| | | | | | | | | | | | | | | | | | | | | | | | | | Since -polly-codegen reports itself to preserve DependenceInfo and IslAstInfo, we might get those analysis that were computed by a different ScopInfo for a different Scop structure. This would be unfortunate because DependenceInfo and IslAstInfo hold references to resources allocated by ScopInfo/ScopBuilder/Scop (e.g. isl_id). If -polly-codegen and DependenceInfo/IslAstInfo do not agree on which Scop to use, unpredictable things can happen. When the ScopInfo/Scop object is freed, there is a high probability that the new ScopInfo/Scop object will be created at the same heap position with the same address. Comparing whether the Scop or ScopInfo address is the expected therefore is unreliable. Instead, we compare the address of the isl_ctx object. Both, DependenceInfo and IslAstInfo must hold a reference to the isl_ctx object to ensure it is not freed before the destruction of those analyses which might happen after the destruction of the Scop/ScopInfo they refer to. Hence, the isl_ctx will not be freed and its address not reused as long there is a DependenceInfo or IslAstInfo around. This fixes llvm.org/PR34441 llvm-svn: 313842
* [ScheduleOptimizer] Fix and test schedule tree statistics.Michael Kruse2017-09-201-32/+38
| | | | | | | | | Fix walking over the schedule tree to collect its properties (Number of permutable bands etc.). Also add regression tests for these statistics. llvm-svn: 313750
* [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-182-2/+2
| | | | | | | | | | | | 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
* Unroll and separate the remaining parts of isolationRoman Gareev2017-09-111-13/+13
| | | | | | | | | | | | | | | | | | | | | | | | The remaining parts produced by the full partial tile isolation can contain hot spots that are worth to be optimized. Currently, we rely on the simple loop unrolling pass, LiCM and the SLP vectorizer to optimize such parts. However, the approach can suffer from the lack of the information about aliasing that Polly provides using additional alias metadata or/and the lack of the information required by simple loop unrolling pass. This patch is the first step to optimize the remaining parts. To do it, we unroll and separate them. In case of, for instance, Intel Kaby Lake, it helps to increase the performance of the generated code from 39.87 GFlop/s to 49.23 GFlop/s. The next possible step is to avoid unrolling performed by Polly in case of isolated and remaining parts and rely only on simple loop unrolling pass and the Loop vectorizer. Reviewed-by: Tobias Grosser <tobias@grosser.es> Differential Revision: https://reviews.llvm.org/D37692 llvm-svn: 312929
* [CodegenCleanup] Update cleanup passes according (old) PassManagerBuilder.Michael Kruse2017-09-091-8/+18
| | | | | | | | | | | | | | | | | | | | | | | | | Update CodegenCleanup using the function-level passes added by populatePassManager that run between EP_EarlyAsPossible and EP_VectorizerStart in -O3. The changes in particular are: - Added pass create arguments, e.g. ExpensiveCombines for InstCombine. - Remove reroll pass. The option -reroll-loops is disabled by default. - Add passes run with UnitAtATime, which is the default. - Add instances of LibCallsShrinkWrap, TailCallElimination, SCCP (sparse conditional constant propagation), Float2Int that did not run before. - Add instances of GVN as in the default pipeline. Notes: - GVNHoist, GVNSink, NewGVN are still disabled in the -O3 pipeline. - The optimization level and other optimization parameters are not accessible outside of PassManagerBuilder, hence we cannot add passes depending on these. Differential Revision: https://reviews.llvm.org/D37571 llvm-svn: 312875
* Fix some unused warnings in pollyReid Kleckner2017-09-072-17/+4
| | | | llvm-svn: 312755
* [CodeGen] Bitcast scalar writes to actual value.Michael Kruse2017-09-071-0/+7
| | | | | | | | The type of NewValue might change due to ScalarEvolution looking though bitcasts. The synthesized NewValue therefore becomes the type before the bitcast. llvm-svn: 312718
* [PPCGCodeGen] Document pre-composition with Zero in getExtent. [NFC]Siddharth Bhat2017-09-071-0/+26
| | | | | | | It's weird at first glance that we do this, so I wrote up some documentation on why we need to perform this process. llvm-svn: 312715
* Revert "[ScopDetect/Info] Look through PHIs that follow an error block"Michael Kruse2017-09-064-53/+19
| | | | | | | | | | This reverts commit r312410 - [ScopDetect/Info] Look through PHIs that follow an error block The commit caused generation of invalid IR due to accessing a parameter that does not dominate the SCoP. llvm-svn: 312663
* [ZoneAlgo] Handle non-StoreInst/LoadInst MemoryAccesses including memset.Michael Kruse2017-09-061-17/+34
| | | | | | | | | | | Up to now ZoneAlgo considered array elements access by something else than a LoadInst or StoreInst as not analyzable. This patch removes that restriction by using the unknown ValInst to describe the written content, repectively the element type's null value in case of memset. Differential Revision: https://reviews.llvm.org/D37362 llvm-svn: 312630
* [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
* [CodegenCleanup] Use old GVN pass instead of NewGVNTobias Grosser2017-09-041-1/+3
| | | | | | | It seems NewGVN still has some problems: llvm.org/PR34452, we will switch back after they have been resolved. llvm-svn: 312480
* [ISLTools]: Move singleton to isl++Tobias Grosser2017-09-041-11/+9
| | | | llvm-svn: 312476
* [DeLICM] Move some functions to isl++ [NFC]Tobias Grosser2017-09-041-14/+10
| | | | llvm-svn: 312475
* [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
* [IslAst] Do not assert in case of empty min/max alias locationsTobias Grosser2017-09-031-15/+45
| | | | | | | | | | | | | In certain situations, the context in the isl_ast_build could result for the min/max locations of our alias sets to become empty, which would cause an internal error in isl, which is then unable to derive a value for these expressions. Check these conditions before code generating expressions and instead assume that alias check succeeded. This is valid, as the corresponding memory accesses will not be executed under any valid context. This fixed llvm.org/PR34432. Thanks to Qirun Zhang for reporting. llvm-svn: 312455
* [IslAst] Move buildCondition to isl++Tobias Grosser2017-09-031-26/+28
| | | | llvm-svn: 312452
* [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
* [ForwardOpTree] Fix typos. NFC.Michael Kruse2017-09-031-2/+2
| | | | llvm-svn: 312446
* [ScopDetect/Info] Look through PHIs that follow an error blockTobias Grosser2017-09-024-19/+53
| | | | | | | | 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
* [ISLNodeBuilder] Materialize Fortran array sizes of arrays without memory ↵Siddharth Bhat2017-09-011-31/+22
| | | | | | | | | | | | | | | | | | | | | | accesses. In Polly, we specifically add a paramter to represent the outermost dimension size of fortran arrays. We do this because this information is statically available from the fortran metadata generated by dragonegg. However, we were only materializing these parameters (meaning, creating an llvm::Value to back the isl_id) from *memory accesses*. This is wrong, we should materialize parameters from *scop array info*. It is wrong because if there is a case where we detect 2 fortran arrays, but only one of them is accessed, we may not materialize the other array's dimensions at all. This is incorrect. We fix this by looping over all `polly::ScopArrayInfo` in a scop, rather that just all `polly::MemoryAccess`. Differential Revision: https://reviews.llvm.org/D37379 llvm-svn: 312350
* Fix Memory Access of failing tests.Michael Kruse2017-09-012-2/+8
| | | | | | | | | | | 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
* Run GVN during the cleanupRoman Gareev2017-09-011-0/+1
| | | | | | | | | | | | | Currently, GVN can be necessary to eliminate redundant instructions in case of, for instance, GEMM and float type. This patch makes GVN be run during the cleanup. Reviewed-by: Tobias Grosser <tobias@grosser.es>, Michael Kruse <llvm@meinersbur.de> Differential Revision: https://reviews.llvm.org/D37340 llvm-svn: 312307
* Drop unused statistic counterTobias Grosser2017-09-011-1/+0
| | | | llvm-svn: 312304
* [polly] Fix non-deterministic output due to iteration of unordered ScopArrayInfoMandeep Singh Grang2017-08-311-1/+1
| | | | | | | | | | | | | | | | | | | | | Summary: This fixes the following failures in the reverse iteration builder: http://lab.llvm.org:8011/builders/reverse-iteration/builds/25 Polly :: MaximalStaticExpansion/working_deps_between_inners.ll Polly :: MaximalStaticExpansion/working_expansion_multiple_dependences_per_statement.ll Polly :: MaximalStaticExpansion/working_expansion_multiple_instruction_per_statement.ll Polly :: MaximalStaticExpansion/working_phi_expansion.ll Reviewers: simbuerg, Eugene.Zelenko, grosser, zinob, bollu Reviewed By: grosser Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D37349 llvm-svn: 312273
* Use the information about the target cache provided by the TargetTransformInfo.Roman Gareev2017-08-311-8/+72
| | | | | | | | Reviewed-by: Tobias Grosser <tobias@grosser.es> Differential Revision: https://reviews.llvm.org/D37178 llvm-svn: 312255
* [ForwardOpTree] Allow forwarding in the presence of region statementsTobias Grosser2017-08-312-9/+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
* [PPCGCodeGen] Convert intrinsics to libdevice functions whenever possible.Siddharth Bhat2017-08-311-7/+41
| | | | | | | | | | | | | | | | This is useful when we face certain intrinsics such as `llvm.exp.*` which cannot be lowered by the NVPTX backend while other intrinsics can. So, we would need to keep blacklists of intrinsics that cannot be handled by the NVPTX backend. It is much simpler to try and promote all intrinsics to libdevice versions. This patch makes function/intrinsic very uniform, and will always try to use a libdevice version if it exists. Differential Revision: https://reviews.llvm.org/D37056 llvm-svn: 312239
* [BlockGenerator] Generate entry block of regions from instruction listsTobias Grosser2017-08-311-1/+6
| | | | | | | | | The adds code generation support for the previous commit. This patch has been re-applied, after the memory issue in the previous patch has been fixed. llvm-svn: 312211
* [ScopInfo] Use statement lists for entry blocks of region statementsTobias Grosser2017-08-312-12/+37
| | | | | | | | | | | | | | | By using statement lists in the entry blocks of region statements, instruction level analyses also work on region statements. We currently only model the entry block of a region statements, as this is sufficient for most transformations the known-passes currently execute. Modeling instructions in the presence of control flow (e.g. infinite loops) is left out to not increase code complexity too much. It can be added when good use cases are found. This change set is reapplied, after a memory corruption issue had been fixed. llvm-svn: 312210
* Revert "[ScopInfo] Use statement lists for entry blocks of region statements"Tobias Grosser2017-08-312-28/+12
| | | | | | This reverts commit r312128. It aused some memory issues. llvm-svn: 312209
* Revert "[BlockGenerator] Generate entry block of regions from instruction lists"Tobias Grosser2017-08-311-6/+1
| | | | | | This reverts commit r312129. It caused some memory issues. llvm-svn: 312208
* [BlockGenerator] Generate entry block of regions from instruction listsTobias Grosser2017-08-301-1/+6
| | | | | | The adds code generation support for the previous commit. llvm-svn: 312129
* [ScopInfo] Use statement lists for entry blocks of region statementsTobias Grosser2017-08-302-12/+28
| | | | | | | | | | | | | By using statement lists in the entry blocks of region statements, instruction level analyses also work on region statements. We currently only model the entry block of a region statements, as this is sufficient for most transformations the known-passes currently execute. Modeling instructions in the presence of control flow (e.g. infinite loops) is left out to not increase code complexity too much. It can be added when good use cases are found. llvm-svn: 312128
* [ScopBuilder/ScopInfo] Move reduction detection to ScopBuilder. NFC.Michael Kruse2017-08-302-164/+147
| | | | | | | | Reduction detection is only executed in the SCoP building phase. Hence it fits better into ScopBuilder to separate SCoP-construction from SCoP modeling. llvm-svn: 312118
* [ScopBuilder/ScopInfo] Move ScopStmt::collectSurroundingLoops to ↵Michael Kruse2017-08-302-8/+9
| | | | | | | | | | ScopBuilder. NFC. This method is only called in the SCoP building phase. Therefore it fits better into ScopBuilder to separate SCoP-construction from SCoP modeling. llvm-svn: 312117
* [ScopBuilder/ScopInfo] Move ScopStmt::buildDomain to ScopBuilder. NFC.Michael Kruse2017-08-302-8/+8
| | | | | | | | This method is only called in the SCoP building phase. Therefore it fits better into ScopBuilder to separate SCoP-construction from SCoP modeling. llvm-svn: 312116
* [ScopBuilder/ScopInfo] Move ScopStmt::buildAccessRelations to ScopBuilder. NFC.Michael Kruse2017-08-302-23/+22
| | | | | | | | | | | | This method is only called in the SCoP building phase. Therefore it fits better into ScopBuilder to separate SCoP-construction from SCoP modeling. This mostly mechanical change makes ScopBuilder directly access some of ScopStmt/MemoryAccess private fields. We add ScopBuilder as a friend class and will add proper accessor functions sometime later. llvm-svn: 312115
* [ScopBuilder/ScopInfo] Move and inline Scop::init into ↵Michael Kruse2017-08-302-18/+13
| | | | | | | | | ScopBuilder::buildScop. NFC. The method is only needed in the SCoP building phase, and doesn't need to be part of the general API. llvm-svn: 312114
* [ScopBuilder] Report to dbgs() on SCoP bailout. NFC.Michael Kruse2017-08-302-5/+18
| | | | | | | This allows to use -debug to see that a SCoP was found in ScopDetect, but dismissed by ScopBuilder. llvm-svn: 312113
* [ScopBuilder] Introduce metadata for splitting scop statement.Michael Kruse2017-08-302-7/+28
| | | | | | | | | | | | This patch allows annotating of metadata in ir instruction (with "polly_split_after"), which specifies where to split a particular scop statement. Contributed-by: Nandini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D36402 llvm-svn: 312107
OpenPOWER on IntegriCloud