summaryrefslogtreecommitdiffstats
path: root/polly/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* [ScopDetect] Do not add loads out of the SCoP to required invariant loads.Michael Kruse2017-10-011-1/+1
| | | | | | | | | | | | | | | | Loads before the SCoP are always invariant within the SCoP and therefore are no "required invariant loads". An assertion failes in ScopBuilder when it finds such an invariant load. Fix by not adding such loads to the required invariant load list. This likely will cause the region to be not considered a valid SCoP. We may want to unconditionally accept instructions defined before the region as valid invariant conditions instead of rejecting them. This fixes a compilation crash of SPEC CPU2006 453.povray's render.cpp. llvm-svn: 314636
* [ScopBuilder] Fix typo. NFC.Michael Kruse2017-09-291-2/+2
| | | | | | | | Contributed-by: Nandini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D38322 llvm-svn: 314519
* Fix the build after r314375Philip Pfaffe2017-09-281-1/+1
| | | | | | r314375 privatized Loop's constructor and replaced it with an Allocator. llvm-svn: 314412
* [ScopInfo] Allow PHI nodes that reference an error blockTobias Grosser2017-09-261-2/+11
| | | | | | As long as these PHI nodes are only referenced by terminator instructions. llvm-svn: 314212
* [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-252-1/+17
| | | | | | | 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-243-19/+27
| | | | | | | | | | | 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
* [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
* Revert "[ScopDetect/Info] Look through PHIs that follow an error block"Michael Kruse2017-09-063-27/+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
* [ScopDetect/Info] Look through PHIs that follow an error blockTobias Grosser2017-09-023-19/+27
| | | | | | | | 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/+7
| | | | | | | | | | | 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
* [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
* [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
* [PM] Properly require and preserve OptimizationRemarkEmitter. NFCI.Michael Kruse2017-08-283-17/+41
| | | | | | | | | | | | | | | | | | | | | | Properly require and preserve the OptimizationRemarkEmitter for use in ScopPass. Previously one had to get the ORE from ScopDetection because CodeGeneration did not mark it as preserved. It would need to be recomputed which results in the legacy PM to throw away all previous SCoP analysis. This also changes the implementation of ScopPass::getAnalysisUsage to not unconditionally preserve all passes, but only those needed to be preserved by any SCoP pass (at least when using the legacy PM). This allows invalidating DependenceInfo (and IslAstInfo) in case the pass would cause them to change (e.g. OpTree, DeLICM, MaximalArrayExpansion) JSONImporter should also invalidate the DependenceInfo. In this patch it marks DependenceInfo as preserved anyway because some regression tests depend on it. Differential Revision: https://reviews.llvm.org/D37010 llvm-svn: 311888
* [Detect] Consider nested loop profitable if entry block is not in loopTobias Grosser2017-08-271-2/+7
| | | | | | | | | | | | | In cases where the entry block of a scop was not contained in a loop that was part of the scop region and at the same time there was a loop surrounding the scop, we missed to count the loops in the scop and consequently did not consider the scop profitable. We correct this by only moving to the loop parent, in case the current loop is loop contained in the scop. This increases the number of loops in COSMO which we assume to be profitable from 3974 to 4981. llvm-svn: 311863
* [Polly] Fix some Clang-tidy modernize and Include What You Use warnings; ↵Eugene Zelenko2017-08-253-53/+115
| | | | | | other minor fixes (NFC). llvm-svn: 311802
* Revert "[polly] Fix ScopDetectionDiagnostic test failure caused by r310940"Tobias Grosser2017-08-242-13/+64
| | | | | | | | This reverts commit 950849ece9bb8fdd2b41e3ec348b9653b4e37df6. This commit broke various buildbots. llvm-svn: 311692
* Add more statistics.Michael Kruse2017-08-232-4/+104
| | | | | | | | | | | | | | | | 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
* [ScopDetect] Include zero-iteration loops in loop count.Michael Kruse2017-08-231-18/+5
| | | | | | | | | | | | | | | | | | | | Loop with zero iteration are, syntactically, loops. They have been excluded from the loop counter even for the non-profitable counters. This seems to be unintentially as the sentinel value of '0' minimal iterations does exclude such loops. Fix by never considering the iteration count when the sentinel value of 0 is found. This makes the recently added NumTotalLoops couter redundant with NumLoopsOverall, which now is equivalent. Hence, NumTotalLoops is removed as well. Note: The test case 'ScopDetect/statistics.ll' effectively does not check profitability, because -polly-process-unprofitable is passed to all test cases. llvm-svn: 311551
* [ScopInfo] Remove stray semicolon. NFC.Michael Kruse2017-08-231-1/+1
| | | | llvm-svn: 311547
* [polly] Fix ScopDetectionDiagnostic test failure caused by r310940Jakub Kuderski2017-08-222-64/+13
| | | | | | | | | | | | | | | | | | | | | | | Summary: ScopDetection used to check if a loop withing a region was infinite and emitted a diagnostic in such cases. After r310940 there's no point checking against that situation, as infinite loops don't appear in regions anymore. The test failure was observed on these two polly buildbots: http://lab.llvm.org:8011/builders/polly-arm-linux/builds/8368 http://lab.llvm.org:8011/builders/polly-amd64-linux/builds/10310 This patch XFAILs `ReportLoopHasNoExit.ll` and turns infinite loop detection into an assert. Reviewers: grosser, sanjoy, bollu Reviewed By: grosser Subscribers: efriedma, aemerson, kristof.beyls, dberlin, llvm-commits Tags: #polly Differential Revision: https://reviews.llvm.org/D36776 llvm-svn: 311503
* [Polly] Fix some Clang-tidy modernize and Include What You Use warnings; ↵Eugene Zelenko2017-08-222-113/+172
| | | | | | other minor fixes (NFC). llvm-svn: 311489
* [ScopDetection] Add stat for total number of loops.Michael Kruse2017-08-221-0/+14
| | | | | | | The total number of loops is useful as a baseline comparing how many loops have been optimized in different configurations. llvm-svn: 311469
* [ScopInfo] Add option to treat all function parameters as dereferencible.Siddharth Bhat2017-08-211-0/+22
| | | | | | | | | | | | | | | | | | | Dragonegg generates most function parameters as pointers to the actual parameters. However, it does not mark these parameters with the dereferencable attribute. Polly is conservative when it comes to invariant load hoisting, thus we add runtime checks to invariant load hoisted pointers when we do not know that pointers are dereferencable. This is correct behaviour, but is a performance penalty. Add a flag that allows all pointer parameters to be dereferencable. That way, polly can speculatively load-hoist paramters to functions without runtime checks. Differential Revision: https://reviews.llvm.org/D36461 llvm-svn: 311329
* [GPGPU] Only collect the access that belong to an array [NFC]Tobias Grosser2017-08-171-0/+5
| | | | | | | | This avoid the construction of very large sets and in many cases also keeps the number of parameters low. As a result, we see a compile time reduction from 5 minutes to only slightly above 1 minute for one of our larger test cases. llvm-svn: 311127
* [ScopInliner] Add a simple Scop-based inliner to polly.Siddharth Bhat2017-08-171-7/+8
| | | | | | | | | | | | | 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
* [Polly] Move ScopStmt::checkForReductions to islpp. NFC.Tobias Grosser2017-08-151-18/+11
| | | | | | | | Reviewers: grosser, bollu Differential Revision: https://reviews.llvm.org/D36714 llvm-svn: 310908
* Move ScopStmt::getSchedule to islpp. NFC.Tobias Grosser2017-08-141-23/+13
| | | | | | | | Reviewers: grosser, Meinersbur, bollu Differential Revision: https://reviews.llvm.org/D36660 llvm-svn: 310815
* [Polly] Move Scop::restrictDomains to islpp. NFC.Tobias Grosser2017-08-141-17/+9
| | | | | | | | Reviewers: grosser, Meinersbur, bollu Differential Revision: https://reviews.llvm.org/D36659 llvm-svn: 310814
* [ScopInfo] Translate ParameterIds to isl++Tobias Grosser2017-08-131-5/+4
| | | | llvm-svn: 310795
* [Polly][PM] Improve invalidation in the Scop-PipelinePhilip Pfaffe2017-08-102-6/+26
| | | | | | | | | | | | | | | | | | | | | Summary: During code generation for a Scop we modify the IR of a function. While this shouldn't affect a Scop in the formal sense, the implementation caches various information about the IR such as SCEV expressions for bounds or parameters. This cached information needs to be updated or invalidated. To this end, SPMUpdater allows passes to report when they've invalidated a Scop to the PassManager, which will then flush and recompute all Scops. This in turn invalidates all iterators, so references to Scops shouldn't be held. Reviewers: grosser, Meinersbur, bollu Reviewed By: grosser Subscribers: llvm-commits, pollydev Differential Revision: https://reviews.llvm.org/D36524 llvm-svn: 310551
* Remove dependency of Scop::getStmtFor(Inst) on getStmtFor(BB). NFC.Michael Kruse2017-08-091-17/+27
| | | | | | | | | | | | | 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
* [ScopInfo] [NFC] Typo fix.Siddharth Bhat2017-08-081-1/+1
| | | | | | "to conservative" -> "too conservative". llvm-svn: 310353
* [ForwardOpTree] Use known array content analysis to forward load instructions.Michael Kruse2017-08-071-1/+5
| | | | | | | | | | | | | | | | | 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] Make Scop::canAlwaysBeHoisted a member functionTobias Grosser2017-08-071-4/+3
| | | | llvm-svn: 310236
* [ScopInfo] Move Scop::addInvariantLoads to isl++ [NFC]Tobias Grosser2017-08-061-31/+23
| | | | llvm-svn: 310235
* [ScopInfo] Move Scop::getPwAffOnly to isl++ [NFC]Tobias Grosser2017-08-062-17/+17
| | | | llvm-svn: 310231
* [ScopInfo] Move Scop::getDomains to isl++ [NFC]Tobias Grosser2017-08-061-8/+8
| | | | llvm-svn: 310230
* [ScopInfo] Move Scop::getInvalidContext to isl++ [NFC]Tobias Grosser2017-08-061-3/+3
| | | | llvm-svn: 310229
* [ScopInfo] Move Scop::getAssumedContext to isl++ [NFC]Tobias Grosser2017-08-062-5/+5
| | | | llvm-svn: 310228
* [ScopInfo] Move Scop::addNonEmptyDomainConstraints to isl++ [NFC]Tobias Grosser2017-08-061-4/+4
| | | | llvm-svn: 310225
* [ScopInfo] Translate Scop::getParamSpace to isl++ [NFC]Tobias Grosser2017-08-063-15/+16
| | | | llvm-svn: 310224
OpenPOWER on IntegriCloud