summaryrefslogtreecommitdiffstats
path: root/polly/lib/Analysis/ScopDetection.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [ScopDetect] Use mayReadOrWriteMemory to shorten conditionTobias Grosser2016-11-211-1/+1
| | | | llvm-svn: 287525
* [ScopDetect] Remove unnecessary namespace qualifierTobias Grosser2016-11-211-5/+5
| | | | llvm-svn: 287524
* Probably overwritten loads should not be considered hoistableJohannes Doerfert2016-11-171-3/+3
| | | | | | | | Do not assume a load to be hoistable/invariant if the pointer is used by another instruction in the SCoP that might write to memory and that is always executed. llvm-svn: 287272
* [ScopDetect] Conservatively handle inaccessible memory alias attributesTobias Grosser2016-11-131-0/+2
| | | | | | | | | | | Commit r286294 introduced support for inaccessiblememonly and inaccessiblemem_or_argmemonly attributes to BasicAA, which we need to support to avoid undefined behavior. This change just refuses all calls which are annotated with these attributes, which is conservatively correct. In the future we may consider to model and support such function calls in Polly. llvm-svn: 286771
* [ScopDetect] Evaluate and verify branches at branch condition, not icmpTobias Grosser2016-11-131-1/+1
| | | | | | | | | | | | | | | | | | | | | | The validity of a branch condition must be verified at the location of the branch (the branch instruction), not the location of the icmp that is used in the branch instruction. When verifying at the wrong location, we may accept an icmp that is defined within a loop which itself dominates, but does not contain the branch instruction. Such loops cannot be modeled as we only introduce domain dimensions for surrounding loops. To address this problem we change the scop detection to evaluate and verify SCEV expressions at the right location. This issue has been around since at least r179148 "scop detection: properly instantiate SCEVs to the place where they are used", where we explicitly set the scope to the wrong location. Before this commit the scope was not explicitly set, which probably also resulted in the scope around the ICmp to be choosen. This resolves http://llvm.org/PR30989 Reported-by: Eli Friedman <efriedma@codeaurora.org> llvm-svn: 286769
* Do not allow switch statements in loop latchesTobias Grosser2016-11-101-8/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | In r248701 "Allow switch instructions in SCoPs" support for switch statements has been introduced, but support for switch statements in loop latches was incomplete. This change completely disables switch statements in loop latches. The original commit changed addLoopBoundsToHeaderDomain to support non-branch terminator instructions, but this change was incorrect: it added a check for BI != null to the if-branch of a condition, but BI was used in the else branch es well. As a result, when a non-branch terminator instruction is encounted a nullptr dereference is triggered. Due to missing test coverage, this bug was overlooked. r249273 "[FIX] Approximate non-affine loops correctly" added code to disallow switch statements for non-affine loops, if they appear in either a loop latch or a loop exit. We adapt this code to now prohibit switch statements in loop latches even if the control condition is affine. We could possibly add support for switch statements in loop latches, but such support should be evaluated and tested separately. This fixes llvm.org/PR30952 Reported-by: Eli Friedman <efriedma@codeaurora.org> llvm-svn: 286426
* [ScopDetect] Use SCEVRewriteVisitor to simplify SCEVRemoveSMax rewriterTobias Grosser2016-10-291-56/+8
| | | | | | | ScalarEvolution got at some pointer a SCEVRewriteVisitor. Use it to simplify our SCEVRemoveSMax visitor. llvm-svn: 285491
* [ScopDetect] Depend transitively on ScalarEvolution.Michael Kruse2016-10-171-1/+1
| | | | | | | ScopDetection might be queried by -dot-scops or -view-scops passes for which it accesses ScalarEvolution. llvm-svn: 284385
* [ScopDetection] Remove redundant checks for endless loopsTobias Grosser2016-09-201-53/+44
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Both `canUseISLTripCount()` and `addOverApproximatedRegion()` contained checks to reject endless loops which are now removed and replaced by a single check in `isValidLoop()`. For reporting such loops the `ReportLoopOverlapWithNonAffineSubRegion` is renamed to `ReportLoopHasNoExit`. The test case `ReportLoopOverlapWithNonAffineSubRegion.ll` is adapted and renamed as well. The schedule generation in `buildSchedule()` is based on the following assumption: Given some block B that is contained in a loop L and a SESE region R, we assume that L is contained in R or the other way around. However, this assumption is broken in the presence of endless loops that are nested inside other loops. Therefore, in order to prevent erroneous behavior in `buildSchedule()`, r265280 introduced a corresponding check in `canUseISLTripCount()` to reject endless loops. Unfortunately, it was possible to bypass this check with -polly-allow-nonaffine-loops which was fixed by adding another check to reject endless loops in `allowOverApproximatedRegion()` in r273905. Hence there existed two separate locations that handled this case. Thank you Johannes Doerfert for helping to provide the above background information. Reviewers: Meinersbur, grosser Subscribers: _jdoerfert, pollydev Differential Revision: https://reviews.llvm.org/D24560 Contributed-by: Matthias Reisinger <d412vv1n@gmail.com> llvm-svn: 281987
* ScopDetection: Make sure we do not accidentally divide by zeroTobias Grosser2016-09-081-0/+3
| | | | | | | This code path is likely never triggered, but by still handling this case locally we avoid warnings in clangs static analyzer. llvm-svn: 280939
* Drop '@brief' from doxygen commentsTobias Grosser2016-09-021-4/+4
| | | | | | | | LLVM's coding guideline suggests to not use @brief for one-sentence doxygen comments to improve readability. Switch this once and for all to ensure people do not copy @brief comments from other parts of Polly, when writing new code. llvm-svn: 280468
* Disable invariant load hoisting temporarilyTobias Grosser2016-08-151-1/+1
| | | | | | | | | | | | With invariant load hoisting enabled the LLVM buildbots currently show some miscompiles, which are possibly caused by invariant load hosting itself. Confirming and fixing this requires a more in-depth analysis. To meanwhile get back green buildbots that allow us to observe other regressions, we disable invariant code hoisting temporarily. The relevant bug is tracked at: http://llvm.org/PR28985 llvm-svn: 278681
* [ScopDetection] Remove unused DetectionContexts during expansion.Michael Kruse2016-08-081-1/+6
| | | | | | | | | | | | | | The function expandRegion() frees Region* objects again when it determines that these are not valid SCoPs. However, the DetectionContext added to the DetectionContextMap still holds a reference. The validity is checked using the ValidRegions lookup table. When a new Region is added to that list, it might share the same address, such that the DetectionContext contains two Region* associations that are in ValidRegions, but that are unrelated and of which one has already been free. Also remove the DetectionContext when not a valid expansion. llvm-svn: 278062
* GPGPU: Mark kernel functions as polly.skipTobias Grosser2016-08-031-1/+1
| | | | | | | | | Otherwise, we would try to re-optimize them with Polly-ACC and possibly even generate kernels that try to offload themselves, which does not work as the GPURuntime is not available on the accelerator and also does not make any sense. llvm-svn: 277589
* Fix a build warning of unhandled enum in switchWeiming Zhao2016-07-111-0/+2
| | | | | | | | | | | | Summary: LLVM adds a new value FMRB_DoesNotReadMemory in the enumeration. Reviewers: andrew.w.kaylor, chrisj, zinob, grosser, jdoerfert Subscribers: Meinersbur, pollydev Differential Revision: http://reviews.llvm.org/D22109 llvm-svn: 275085
* Add comment on why loops/regions can overlap. NFC.Michael Kruse2016-06-271-0/+29
| | | | | | | The case is described in llvm.org/PR28071 which was fixed in the previous commit. llvm-svn: 273906
* Fix assertion due to loop overlap with nonaffine region.Michael Kruse2016-06-271-1/+19
| | | | | | | | | | | | Reject and report regions that contains loops overlapping nonaffine region. This situation typically happens in the presence of inifinite loops. This addresses bug llvm.org/PR28071. Differential Revision: http://reviews.llvm.org/D21312 Contributed-by: Huihui Zhang <huihuiz@codeaurora.org> llvm-svn: 273905
* clang-tidy: apply modern-use-nullptr fixesTobias Grosser2016-06-221-1/+1
| | | | | | | | | | Instead of using 0 or NULL use the C++11 nullptr symbol when referencing null pointers. This cleanup was suggested by Eugene Zelenko <eugene.zelenko@gmail.com> in http://reviews.llvm.org/D21488 and was split out to increase readability. llvm-svn: 273435
* ScopDetection: Make enum function-localTobias Grosser2016-06-111-7/+7
| | | | | | | | | | | | The 'Color' enum is only used for irreducible control flow detection. Johannes already moved this enum in r270054 from ScopDetection.h to ScopDetection.cpp to limit its scope to a single cpp file. We now move it into the only function where this enum is needed to make clear that it is only needed locally in this single function. Thanks to Johannes for pointing out this cleanup opportunity. llvm-svn: 272462
* Make the detection context non-constant [NFC]Johannes Doerfert2016-05-231-1/+1
| | | | llvm-svn: 270410
* Move internal enum out of class declaration [NFC]Johannes Doerfert2016-05-191-6/+13
| | | | llvm-svn: 270054
* Propagate the DetectionContext to the SCoP [NFC]Johannes Doerfert2016-05-191-28/+0
| | | | | | | The SCoP now holds a reference to the ScopDetection::DetectionContext which allows to simplify the type of various methods and remove code. llvm-svn: 270053
* Remove leftover debug output [NFC]Johannes Doerfert2016-05-191-1/+0
| | | | llvm-svn: 270051
* Check late for profitabilityJohannes Doerfert2016-05-121-3/+13
| | | | | | | | | | | | Before this patch we only expanded valid __and__ profitable region. Therefor we did not allow the expansion to create a profitable region from a non-profitable one. With this patch we will remember and expand all valid regions and check for profitability only at the end. This patch increases the number of valid SCoPs in the LLVM-TS and SPEC 2000/2006 by 28% (from 303 to 390), including the hot loop in hmmer. llvm-svn: 269343
* Cleanup rejection log handling [NFC]Johannes Doerfert2016-05-121-52/+30
| | | | | | | | | | | | This patch cleans up the rejection log handling during the ScopDetection. It consists of two interconnected parts: - We keep all detection contexts for a function in order to provide more information to the user, e.g., about the rejection of extended/intermediate regions. - We remove the mutable "RejectLogs" member as the information is available through the detection contexts. llvm-svn: 269323
* Weaken profitability constraints during ScopDetectionJohannes Doerfert2016-05-101-0/+24
| | | | | | | | Regions with one affine loop can be profitable if the loop is distributable. To this end we will allow them to be treated as profitable if they contain at least two non-trivial basic blocks. llvm-svn: 269064
* Allow unsigned comparisonsJohannes Doerfert2016-04-261-12/+0
| | | | | | | | With this patch we will optimistically assume that the result of an unsigned comparison is the same as the result of the same comparison interpreted as signed. llvm-svn: 267559
* Check only loop control of loops that are part of the regionJohannes Doerfert2016-04-251-1/+2
| | | | | | | This also removes a duplicated line of code in the region generator that caused a SPEC benchmark to fail with the new SCoPs. llvm-svn: 267404
* Remove unnecessary argument of the SCEVValidator [NFC]Johannes Doerfert2016-04-251-8/+7
| | | | llvm-svn: 267400
* Allow pointer expressions in SCEVs again.Johannes Doerfert2016-04-101-6/+0
| | | | | | | | | In r247147 we disabled pointer expressions because the IslExprBuilder did not fully support them. This patch reintroduces them by simply treating them as integers. The only special handling for pointers that is left detects the comparison of two address_of operands and uses an unsigned compare. llvm-svn: 265894
* [FIX] Do not allow select as a base pointer in the SCoP regionJohannes Doerfert2016-04-091-0/+3
| | | | llvm-svn: 265884
* Do not allow exception handling code in SCoPsJohannes Doerfert2016-04-091-0/+3
| | | | llvm-svn: 265883
* [FIX] Do not create a SCoP in the presence of infinite loopsJohannes Doerfert2016-04-031-1/+7
| | | | | | | | If a loop has no exiting blocks the region covering we use during schedule genertion might not cover that loop properly. For now we bail out as we would not optimize these loops anyway. llvm-svn: 265280
* Revert "[FIX] Do not create a SCoP in the presence of infinite loops"Tobias Grosser2016-04-031-7/+1
| | | | | | | | | | | | | | This reverts commit r265260, as it caused the following 'make check-polly' failures: Polly :: ScopDetect/index_from_unpredictable_loop.ll Polly :: ScopInfo/multiple_exiting_blocks.ll Polly :: ScopInfo/multiple_exiting_blocks_two_loop.ll Polly :: ScopInfo/schedule-const-post-dominator-walk-2.ll Polly :: ScopInfo/schedule-const-post-dominator-walk.ll Polly :: ScopInfo/switch-5.ll llvm-svn: 265272
* [FIX] Do not create a SCoP in the presence of infinite loopsJohannes Doerfert2016-04-031-1/+7
| | | | | | | | If a loop has no exiting blocks the region covering we use during schedule genertion might not cover that loop properly. For now we bail out as we would not optimize these loops anyway. llvm-svn: 265260
* ScoPDetection: Obtain a known free diagnostic IDTobias Grosser2016-04-011-1/+2
| | | | | | | | | ... instead of hardcoding something that has been free at some point. This fixes a crash triggered by r265084, where the diagnostic IDs have been shifted in a way that resulted our hardcode ID to not be assigned any implementation. Our ID was likely already wrong earlier on, but this time we really crashed nicely. llvm-svn: 265114
* [FIX] Handle accesses to "null" in MemIntrinsicsJohannes Doerfert2016-03-241-8/+12
| | | | | | | | | This fixes PR27035. While we now exclude MemIntrinsics from the polyhedral model if they would access "null" we could exploit this even more, e.g., remove all parameter combinations that would lead to the execution of this statement from the context. llvm-svn: 264284
* Remove weird comment [NFC]Johannes Doerfert2016-03-241-2/+1
| | | | llvm-svn: 264268
* Add option to disallow modref function calls in scops.Tobias Grosser2016-03-231-29/+37
| | | | | | | | | | This might be useful to evaluate the benefit of us handling modref funciton calls. Also, a new bug that was triggered by modref function calls was recently reported http://llvm.org/PR27035. To ensure the same issue does not cause troubles for other people, we temporarily disable this until the bug is resolved. llvm-svn: 264140
* Pass scope and LoopInfo to SCEVValidator. NFC.Michael Kruse2016-03-031-10/+13
| | | | | | | | The scope will be required in the following fix. This commit separates the large changes that do not change behaviour from the small, but functional change. llvm-svn: 262664
* Fix non-synthesizable loop exit values.Michael Kruse2016-03-011-8/+15
| | | | | | | | | | | Polly recognizes affine loops that ScalarEvolution does not, in particular those with loop conditions that depend on hoisted invariant loads. Check for SCEVAddRec dependencies on such loops and do not consider their exit values as synthesizable because SCEVExpander would generate them as expressions that depend on the original induction variables. These are not available in generated code. llvm-svn: 262404
* [ScopDetection] Fix use-after-free.Michael Kruse2016-02-291-3/+2
| | | | | | | | | | | | | | | | removeCachedResults deletes the DetectionContext from DetectionContextMap such that any it cannot be used anymore. Unfortunately invalid<ReportUnprofitable> and RejectLogs.insert still do use it. Because the memory is part of a map and not returned to to the OS immediatly, such that the observable effect was only a memory leak due to reference counters not decreased when the second call to removeCachedResults does not remove the DetectionContext because because it already has been removed. Fix by not removing the DetectionContext prematurely. The second call to removeCachedResults will handle it anyway. llvm-svn: 262235
* Enable llvm's isa/cast/dyn_cast on MemAccInst.Hongbin Zheng2016-02-271-2/+2
| | | | | | Differential Revision: http://reviews.llvm.org/D17250 llvm-svn: 262100
* ScopDetect/Info: Add option to disable invariant load hoistingTobias Grosser2016-02-261-0/+9
| | | | | | This is helpful for test case reduction and other experiments. llvm-svn: 262033
* ScopDetection: Fix mix-up of isLoad and isStore.Michael Kruse2016-02-261-2/+2
| | | | | | | | | This was accidentally introduced in r258947. Thanks to Hongbin Zheng for finding this. Found-by: etherzhhb llvm-svn: 262032
* [MemAccInst] Introduce the '->' operator and remove the simple wrapper ↵Hongbin Zheng2016-02-261-1/+1
| | | | | | functions. NFC llvm-svn: 261994
* Support calls with known ModRef function behaviourJohannes Doerfert2016-02-251-1/+42
| | | | | | | | | Check the ModRefBehaviour of functions in order to decide whether or not a call instruction might be acceptable. Differential Revision: http://reviews.llvm.org/D5227 llvm-svn: 261866
* Simplify code [NFC]Johannes Doerfert2016-02-251-6/+1
| | | | llvm-svn: 261864
* Try to build alias checks even when non-affine accesses are allowedJohannes Doerfert2016-02-251-6/+0
| | | | | | | From now on we bail only if a non-trivial alias group contains a non-affine access, not when we discover aliasing and non-affine accesses are allowed. llvm-svn: 261863
* Support memory intrinsicsJohannes Doerfert2016-02-211-53/+108
| | | | | | | | | | | | | This patch adds support for memcpy, memset and memmove intrinsics. They are represented as one (memset) or two (memcpy, memmove) memory accesses in the polyhedral model. These accesses have an access range that describes the summarized effect of the intrinsic, i.e., memset(&A[i], '$', N); is represented as a write access from A[i] to A[i+N]. Differential Revision: http://reviews.llvm.org/D5226 llvm-svn: 261489
OpenPOWER on IntegriCloud