summaryrefslogtreecommitdiffstats
path: root/polly/lib/Analysis/ScopDetection.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* ScopDectect: Allow memory accesses with different element types by default ↵Tobias Grosser2016-02-161-1/+1
| | | | | | | | | | (try 3) First support for this feature was committed in r259784. Support for loop invariant load hoisting with different types was added by Johannes Doerfert in r260045 and r260886. llvm-svn: 260965
* [Refactor] Eliminate the global variable "InsnToMemAcc".Hongbin Zheng2016-02-151-4/+9
| | | | | | | | | Eliminate the global variable "InsnToMemAcc" to make Scop/ScopInfo become more protable, such that we can safely use them in a CallGraphSCC pass. Differential Revision: http://reviews.llvm.org/D17238 llvm-svn: 260863
* Revert "[ScopDectect] Allow memory accesses with different element types by ↵Tobias Grosser2016-02-141-1/+1
| | | | | | | | | | | default" This reverts commit https://llvm.org/svn/llvm-project/polly/trunk@260853 We unfortunately still have two bugs left which show only up with -polly-process-unprofitable and which I forgot to test before committing. llvm-svn: 260854
* [ScopDectect] Allow memory accesses with different element types by defaultTobias Grosser2016-02-141-1/+1
| | | | | | | | First support for this feature was committed in r259784. Support for loop invariant load hoisting with different types was added by Johannes Doerfert in r260045. This fixed the last known bug. llvm-svn: 260853
* Make memory accesses with different element types optionalTobias Grosser2016-02-071-2/+12
| | | | | | | | We also disable this feature by default, as there are still some issues in combination with invariant load hoisting that slipped through my initial testing. llvm-svn: 260025
* Support accesses with differently sized types to the same arrayTobias Grosser2016-02-041-6/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This allows code such as: void multiple_types(char *Short, char *Float, char *Double) { for (long i = 0; i < 100; i++) { Short[i] = *(short *)&Short[2 * i]; Float[i] = *(float *)&Float[4 * i]; Double[i] = *(double *)&Double[8 * i]; } } To model such code we use as canonical element type of the modeled array the smallest element type of all original array accesses, if type allocation sizes are multiples of each other. Otherwise, we use a newly created iN type, where N is the gcd of the allocation size of the types used in the accesses to this array. Accesses with types larger as the canonical element type are modeled as multiple accesses with the smaller type. For example the second load access is modeled as: { Stmt_bb2[i0] -> MemRef_Float[o0] : 4i0 <= o0 <= 3 + 4i0 } To support code-generating these memory accesses, we introduce a new method getAccessAddressFunction that assigns each statement instance a single memory location, the address we load from/store to. Currently we obtain this address by taking the lexmin of the access function. We may consider keeping track of the memory location more explicitly in the future. We currently do _not_ handle multi-dimensional arrays and also keep the restriction of not supporting accesses where the offset expression is not a multiple of the access element type size. This patch adds tests that ensure we correctly invalidate a scop in case these accesses are found. Both types of accesses can be handled using the very same model, but are left to be added in the future. We also move the initialization of the scop-context into the constructor to ensure it is already available when invalidating the scop. Finally, we add this as a new item to the 2.9 release notes Reviewers: jdoerfert, Meinersbur Differential Revision: http://reviews.llvm.org/D16878 llvm-svn: 259784
* Revert "Support loads with differently sized types from a single array"Tobias Grosser2016-02-031-1/+7
| | | | | | This reverts commit (@259587). It needs some further discussions. llvm-svn: 259629
* Support loads with differently sized types from a single arrayTobias Grosser2016-02-021-7/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | We support now code such as: void multiple_types(char *Short, char *Float, char *Double) { for (long i = 0; i < 100; i++) { Short[i] = *(short *)&Short[2 * i]; Float[i] = *(float *)&Float[4 * i]; Double[i] = *(double *)&Double[8 * i]; } } To support such code we use as element type of the modeled array the smallest element type of all original array accesses. Accesses with larger types are modeled as multiple accesses with the smaller type. For example the second load access is modeled as: { Stmt_bb2[i0] -> MemRef_Float[o0] : 4i0 <= o0 <= 3 + 4i0 } To support jscop-rewritable memory accesses we need each statement instance to only be assigned a single memory location, which will be the address at which we load the value. Currently we obtain this address by taking the lexmin of the access function. We may consider keeping track of the memory location more explicitly in the future. llvm-svn: 259587
* Introduce MemAccInst helper class; NFCMichael Kruse2016-01-271-23/+18
| | | | | | | | | | | | | | | | MemAccInst wraps the common members of LoadInst and StoreInst. Also use of this class in: - ScopInfo::buildMemoryAccess - BlockGenerator::generateLocationAccessed - ScopInfo::addArrayAccess - Scop::buildAliasGroups - Replace every use of polly::getPointerOperand Reviewers: jdoerfert, grosser Differential Revision: http://reviews.llvm.org/D16530 llvm-svn: 258947
* ScopDetection: Do not detect regions with irreducible control as scopsTobias Grosser2016-01-221-0/+73
| | | | | | | | | | | | | | Polly currently does not support irreducible control and it is probably not worth supporting. This patch adds code that checks for irreducible control and refuses regions containing irreducible control. Polly traditionally had rather restrictive checks on the control flow structure which would have refused irregular control, but within the last couple of months most of the control flow restrictions have been removed. As part of this generalization we accidentally allowed irregular control flow. Contributed-by: Karthik Senthil and Ajith Pandel llvm-svn: 258497
* ScopDetection: Simplify std::distance(....) to BB->size()Tobias Grosser2015-12-221-1/+1
| | | | | | Suggested by: Johannes Doerfert <doerfert@cs.uni-saarland.de> llvm-svn: 256260
* Add option to assume single-loop scops with sufficient compute are profitableTobias Grosser2015-12-211-4/+38
| | | | | | | | | | | | | | If a loop has a sufficiently large amount of compute instruction in its loop body, it is unlikely that our rewrite of the loop iterators introduces large performance changes. As Polly can also apply beneficical optimizations (such as parallelization) to such loop nests, we mark them as profitable. This option is currently "disabled" by default, but can be used to run experiments. If enabled by setting it e.g. to 40 instructions, we currently see some compile-time increases on LNT without any significant run-time changes. llvm-svn: 256199
* Adjust formatting to clang-format changes in 256149Tobias Grosser2015-12-211-1/+1
| | | | llvm-svn: 256151
* ScopDetect: Extract profitability check into subfunctionTobias Grosser2015-12-211-13/+22
| | | | | | | | | | | | .. and add some documentation. We also simplify the code by dropping an early check that is also covered by the the later checks. This might have a small compile time impact, but as the scops that are skipped are small we should probably only add this back in the unlikely case that this has a notable compile-time cost. No functional change intended. llvm-svn: 256149
* ScopInfo: Return immediately if scop is unprofitable and marked invalidTobias Grosser2015-12-211-3/+3
| | | | | | | | | | As we already log an error when calling invalid, scops unprofitable scops are in any case marked invalid, but returning immediately safes (a tiny bit of) compile time and is consistent with our use of 'invalid' in the remainder of the file. Found by inspection. llvm-svn: 256140
* ScopInfo: Return in case we found an invalid array sizeTobias Grosser2015-12-211-1/+1
| | | | | | | | | | | Without this return we still log the incorrect array size (and do not detect this scop), but we would unnecessarily continue to verify that access functions are affine. As we do not need to do this, we can return right ahead and consequently safe compile time. This issue was found by inspection. llvm-svn: 256139
* Compile fix: Use "&&" operator instead of "and"Michael Kruse2015-12-201-1/+1
| | | | llvm-svn: 256124
* Fix delinearization of fortran arraysRoman Gareev2015-12-171-2/+2
| | | | | | | | | | | | | | | The patch fixes Bug 25759 produced by inappropriate handling of unsigned maximum SCEV expressions by SCEVRemoveMax. Without a fix, we get an infinite loop and a segmentation fault, if we try to process, for example, '((-1 + (-1 * %b1)) umax {(-1 + (-1 * %yStart)),+,-1}<%.preheader>)'. It also fixes a potential issue related to signed maximum SCEV expressions. Tested-by: Roman Gareev <gareevroman@gmail.com> Fixed-by: Tobias Grosser <tobias@grosser.es> Differential Revision: http://reviews.llvm.org/D15563 llvm-svn: 255922
* ScopInfo: Add support for delinearizing fortran arraysTobias Grosser2015-11-241-0/+93
| | | | | | | | | | | | gfortran (and fortran in general?) does not compute the address of an array element directly from the array sizes (e.g., %s0, %s1), but takes first the maximum of the sizes and 0 (e.g., max(0, %s0)) before multiplying the resulting value with the per-dimension array subscript expressions. To successfully delinearize index expressions as we see them in fortran, we first filter 'smax' expressions out of the SCEV expression, use them to guess array size parameters and only then continue with the existing delinearization. llvm-svn: 253995
* ScopInfo: Split hasAffineMemoryAccesses() into multiple functions [NFC]Tobias Grosser2015-11-241-115/+143
| | | | | | This makes the overall code more readable. llvm-svn: 253951
* Do not enforce lcssaJohannes Doerfert2015-11-211-8/+0
| | | | | | | | At some point we enforced lcssa for the loop surrounding the entry block. This is not only questionable as it does not check any other loop but also not needed any more. llvm-svn: 253789
* Emit SCoP source location as remark during ScopInfoJohannes Doerfert2015-11-121-3/+0
| | | | | | | This removes a similar feature from ScopDetection, though with -polly-report that feature present twice anyway. llvm-svn: 252846
* ScopDetection: Do not allow blocks to reference operands in error blocksTobias Grosser2015-11-111-0/+10
| | | | | | | | | | | | | r252713 introduced a couple of regressions due to later basic blocks refering to instructions defined in error blocks which have not yet been modeled. This commit is currently just encoding limitations of our modeling and code generation backends to ensure correctness. In theory, we should be able to generate and optimize such regions, as everything that is dominated by an error region is assumed to not be executed anyhow. We currently just lack the code to make this happen in practice. llvm-svn: 252725
* ScopInfo: Pass domain constraints through error blocksTobias Grosser2015-11-111-5/+14
| | | | | | | | | | | | | | | | | | | | | | | | | Previously, we just skipped error blocks during scop construction. With this change we make sure we can construct domains for error blocks such that these domains can be forwarded to subsequent basic blocks. This change ensures that basic blocks that post-dominate and are dominated by a basic block that branches to an error condition have the very same iteration domain as the branching basic block. Before, this change we would construct a domain that excludes all error conditions. Such domains could become _very_ complex and were undesirable to build. Another solution would have been to drop these constraints using a dominance/post-dominance check instead of modeling the error blocks. Such a solution could also work in case of unreachable statements or infinite loops in the scop. However, as we currently (to my believe incorrectly) model unreachable basic blocks in the post-dominance tree, such a solution is not yet feasible and requires first a change to LLVM's post-dominance tree construction. This commit addresses the most sever compile time issue reported in: http://llvm.org/PR25458 llvm-svn: 252713
* Remove old and redundant optionsTobias Grosser2015-11-021-5/+0
| | | | | | | | | We remove -polly-detect-unprofitable and -polly-no-early-exit. Both have been superseeded by -polly-process-unprofitable and were only kept as aliases for our buildbots to continue to work. As all buildbots have been moved to the new options, we can now remove the old ones for good. llvm-svn: 251787
* ScopDetect: Bail out for non-simple memory accessesTobias Grosser2015-10-251-0/+9
| | | | | | | | | | | | | Volatile or atomic memory accesses are currently not supported. Neither did we think about any special handling needed nor do we support the unknown instructions the alias set tracker turns them into sometimes. Before this patch, us not supporting unkown instructions in an alias set caused the following assertion failures: Assertion `AG.size() > 1 && "Alias groups should contain at least two accesses"' failed llvm-svn: 251234
* ScopDetection: Update DetectionContextMap accordinglyTobias Grosser2015-10-251-1/+5
| | | | | | | | When verifying if a scop is still valid we rerun all analysis, but did not update DetectionContextMap. This change ensures that information, e.g. about non-affine regions, is correctly updated llvm-svn: 251227
* ScopDetection: Do not crash if we find zero array size candidates for ↵Tobias Grosser2015-10-251-1/+2
| | | | | | delinearization llvm-svn: 251226
* ScopDetection: Always refuse multi-dimensional memory accesses with 'undef' inTobias Grosser2015-10-251-20/+17
| | | | | | | | | | | the size expression. We previously only checked if the size expression is 'undef', but allowed size expressions of the form 'undef * undef' by accident. After this change we now require size expressions to be affine which implies no 'undef' appears anywhere in the expression. llvm-svn: 251225
* [FIX] Only constant integer branch conditions are always affineJohannes Doerfert2015-10-181-2/+2
| | | | | | | | | | | There are several different kinds of constants that could occur in a branch condition, however we can only handle the most interesting one namely constant integers. To this end we have to treat others as non-affine. This fixes bug 25244. llvm-svn: 250669
* Remove independent blocks passJohannes Doerfert2015-10-181-14/+3
| | | | | | | | | | | Polly can now be used as a analysis only tool as long as the code generation is disabled. However, we do not have an alternative to the independent blocks pass in place yet, though in the relevant cases this does not seem to impact the performance much. Nevertheless, a virtual alternative that allows the same transformations without changing the input region will follow shortly. llvm-svn: 250652
* ScopInfo: Allow simple 'AddRec * Parameter' products in delinearizationTobias Grosser2015-10-121-5/+10
| | | | | | | | | | | We also allow such products for cases where 'Parameter' is loaded within the scop, but where we can dynamically verify that the value of 'Parameter' remains unchanged during the execution of the scop. This change relies on Polly's new RequiredILS tracking infrastructure recently contributed by Johannes. llvm-svn: 250019
* Add back -polly-detect-unprofitable as alias of -polly-process-unprofitableTobias Grosser2015-10-111-0/+5
| | | | | | | This flag was still used in our LNT server. We leave it until it has been removed from LNT as well. llvm-svn: 249973
* Allow eager evaluated binary && and || conditionsJohannes Doerfert2015-10-111-0/+11
| | | | | | | | | | | The domain generation can handle lazy && and || by default but eager evaluated expressions were dismissed as non-affine. With this patch we will allow arbitrary combinations of and/or bit-operations in the conditions of branches. Differential Revision: http://reviews.llvm.org/D13624 llvm-svn: 249971
* [NFC] Move helper functions to ScopHelperJohannes Doerfert2015-10-091-1/+0
| | | | | | | | Helper functions in the BlockGenerators.h/cpp introduce dependences from the frontend to the backend of Polly. As they are used in ScopDetection, ScopInfo, etc. we move them to the ScopHelper file. llvm-svn: 249919
* Remove unused flag polly-allow-non-scev-backedge-taken-countJohannes Doerfert2015-10-081-5/+0
| | | | | | | | | | | Drop an unused flag polly-allow-non-scev-backedge-taken-count and also its occurrences from the tests. Contributed-by: Chris Jenneisch <chrisj@codeaurora.org> Differential Revision: http://reviews.llvm.org/D13400 llvm-svn: 249675
* Expose the detection context to ScopDetection usersJohannes Doerfert2015-10-071-40/+33
| | | | | | | | | | | | ScopDetection users are interested in the detection context and access these via different get-methods. However, not all information was exposed though the number of maps to hold it was increasing steadily. With this change only the detection contexts the rejection log and the ValidRegions set are mapped. The former is needed, the second could be integrated in the first and the ValidRegions set is only needed for the deterministic order of the regions. llvm-svn: 249614
* Treat conditionally executed non-pure calls as errorsJohannes Doerfert2015-10-071-1/+4
| | | | | | | | | | | | | | This replaces the support for user defined error functions by a heuristic that tries to determine if a call to a non-pure function should be considered "an error". If so the block is assumed not to be executed at runtime. While treating all non-pure function calls as errors will allow a lot more regions to be analyzed, it will also cause us to dismiss a lot again due to an infeasible runtime context. This patch tries to limit that effect. A non-pure function call is considered an error if it is executed only in conditionally with regards to a cheap but simple heuristic. llvm-svn: 249611
* Allow invariant loads in the SCoP descriptionJohannes Doerfert2015-10-071-28/+57
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch allows invariant loads to be used in the SCoP description, e.g., as loop bounds, conditions or in memory access functions. First we collect "required invariant loads" during SCoP detection that would otherwise make an expression we care about non-affine. To this end a new level of abstraction was introduced before SCEVValidator::isAffineExpr() namely ScopDetection::isAffine() and ScopDetection::onlyValidRequiredInvariantLoads(). Here we can decide if we want a load inside the region to be optimistically assumed invariant or not. If we do, it will be marked as required and in the SCoP generation we bail if it is actually not invariant. If we don't it will be a non-affine expression as before. At the moment we optimistically assume all "hoistable" (namely non-loop-carried) loads to be invariant. This causes us to expand some SCoPs and dismiss them later but it also allows us to detect a lot we would dismiss directly if we would ask e.g., AliasAnalysis::canBasicBlockModify(). We also allow potential aliases between optimistically assumed invariant loads and other pointers as our runtime alias checks are sound in case the loads are actually invariant. Together with the invariant checks this combination allows to handle a lot more than LICM can. The code generation of the invariant loads had to be extended as we can now have dependences between parameters and invariant (hoisted) loads as well as the other way around, e.g., test/Isl/CodeGen/invariant_load_parameters_cyclic_dependence.ll First, it is important to note that we cannot have real cycles but only dependences from a hoisted load to a parameter and from another parameter to that hoisted load (and so on). To handle such cases we materialize llvm::Values for parameters that are referred by a hoisted load on demand and then materialize the remaining parameters. Second, there are new kinds of dependences between hoisted loads caused by the constraints on their execution. If a hoisted load is conditionally executed it might depend on the value of another hoisted load. To deal with such situations we sort them already in the ScopInfo such that they can be generated in the order they are listed in the Scop::InvariantAccesses list (see compareInvariantAccesses). The dependences between hoisted loads caused by indirect accesses are handled the same way as before. llvm-svn: 249607
* Introduce -polly-process-unprofitableTobias Grosser2015-10-061-9/+12
| | | | | | | | | | This single option replaces -polly-detect-unprofitable and -polly-no-early-exit and is supposed to be the only option that disables compile-time heuristics that aim to bail out early on scops that are believed to not benefit from Polly optimizations. Suggested-by: Johannes Doerfert llvm-svn: 249426
* [FIX] Count affine loops correctlyJohannes Doerfert2015-10-041-20/+17
| | | | | | | The "unprofitable" heuristic was broken and counted boxed loops even though we do not represent and optimize them. llvm-svn: 249274
* [FIX] Approximate non-affine loops correctlyJohannes Doerfert2015-10-041-50/+60
| | | | | | | | | | Before isValidCFG() could hide the fact that a loop is non-affine by over-approximation. This is problematic if a subregion of the loop contains an exit/latch block and is over-approximated. Now we do not over-approximate in the isValidCFG function if we check loop control. If such control is non-affine the whole loop is over-approximated, not only a subregion. llvm-svn: 249273
* [FIX] Check loop latches for valid control too.Johannes Doerfert2015-10-041-6/+7
| | | | | | | | | This patch cannot be tested on its own as the isValidCFG currently hides the fact that control is actually non-affine with over-approximation. This will be corrected in the next patch and a test for non-affine latches will be added. llvm-svn: 249272
* [FIX] Erase stall results during the SCoP detectionJohannes Doerfert2015-10-011-17/+27
| | | | | | | | | | | | | | | With this patch we erase cached results for regions that are invalid as early as possible. If we do not (as before), it is possible that two expanded regions will have the same address and the tracked results for both are mixed. Currently this would "only" cause pessimism in later passes but that will change when we allow invariant loads in the SCoP. Additionally, it triggers non-deterministic results as we might dismiss a later region because of results cached for an earlier one. There is no test case as the problem occurs only non-deterministically. llvm-svn: 249000
* [FIX] Remove unknown variableJohannes Doerfert2015-09-301-1/+0
| | | | llvm-svn: 248926
* [FIX] Clear all maps between runsJohannes Doerfert2015-09-301-2/+4
| | | | llvm-svn: 248915
* Allow switch instructions in SCoPsJohannes Doerfert2015-09-281-25/+52
| | | | | | | | | | | | | | | This patch allows switch instructions with affine conditions in the SCoP. Also switch instructions in non-affine subregions are allowed. Both did not require much changes to the code, though there was some refactoring needed to integrate them without code duplication. In the llvm-test suite the number of profitable SCoPs increased from 135 to 139 but more importantly we can handle more benchmarks and user inputs without preprocessing. Differential Revision: http://reviews.llvm.org/D13200 llvm-svn: 248701
* Remove obsolete checkJohannes Doerfert2015-09-281-12/+2
| | | | | | | | This check was needed at some point but seems not useful anymore. Only one adjustment in the domain generation was needed to cope with the cases this check prevented from happening before. llvm-svn: 248695
* Make MIN_LOOP_TRIP_COUNT a static constantJohannes Doerfert2015-09-211-2/+5
| | | | llvm-svn: 248192
* Allow loops with multiple back edgesJohannes Doerfert2015-09-201-4/+0
| | | | | | | | | | In order to allow multiple back edges we: - compute the conditions under which each back edge is taken - build the union over all these conditions, thus the condition that any back edge is taken - apply the same logic to the union we applied to a single back edge llvm-svn: 248120
OpenPOWER on IntegriCloud