summaryrefslogtreecommitdiffstats
path: root/polly/lib/Analysis/TempScopInfo.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Merge TempScopInfo.{cpp|h} into ScopInfo.{cpp|h}Michael Kruse2015-09-101-431/+0
| | | | | | | | | | | | | | | | | | This prepares for a series of patches that merges TempScopInfo into ScopInfo to reduce Polly's code complexity. Only ScopInfo.{cpp|h} will be left thereafter. Moving the code of TempScopInfo in one commit makes the mains diffs simpler to understand. In detail, merging the following classes is planned: TempScopInfo into ScopInfo TempScop into Scop IRAccess into MemoryAccess Only moving code, no functional changes intended. Differential Version: http://reviews.llvm.org/D12693 llvm-svn: 247274
* [PM] Update Polly for the new AA infrastructure landed in r247167.Chandler Carruth2015-09-091-3/+3
| | | | llvm-svn: 247198
* Allow PHI nodes in the region exit blockJohannes Doerfert2015-09-081-8/+35
| | | | | | | | | | | | While we do not need to model PHI nodes in the region exit (as it is not part of the SCoP), we need to prepare for the case that the exit block is split in code generation to create a single exiting block. If this will happen, hence if the region did not have a single exiting block before, we will model the operands of the PHI nodes as escaping scalars in the SCoP. Differential Revision: http://reviews.llvm.org/D12051 llvm-svn: 247078
* Always use the branch instructions to model the PHI-node writesTobias Grosser2015-08-311-4/+3
| | | | | | | | | | Before this commit we did this only for Arguments or Constants, but indeed an instruction may define a value a lot higher up in the dominance tree, but the actual write generally needs to happen right before branching to the PHI node. Otherwise, the writes of different branches into PHI nodes may get intermixed if they lay higher up in the dominance tree. llvm-svn: 246441
* Also build scalar dependences for store instructionsTobias Grosser2015-08-311-5/+6
| | | | | | | | | While ignoring read-only scalar dependences it was not necessary to consider store instructins, but as store instructions can be the target of a scalar read-only dependency we need to consider them for the construction of scalar read-only dependences. llvm-svn: 246429
* Enable modeling of scalar read-only dependencesTobias Grosser2015-08-311-1/+1
| | | | | | | | | | Even though these are not strictly necessary for sequential code generation, we still model both for sequential and parallel code generation to reduce the set of configurations that needs to be tested. If this turns out, against what we currently see, to be significant overhead, we can decide to limit this feature again to parallel code-generation use cases only. llvm-svn: 246420
* Do not model scalar references to constant valuesTobias Grosser2015-08-311-0/+3
| | | | llvm-svn: 246418
* Traverse the SCoP to compute non-loop-carried domain conditionsJohannes Doerfert2015-08-301-137/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | In order to compute domain conditions for conditionals we will now traverse the region in the ScopInfo once and build the domains for each block in the region. The SCoP statements can then use these constraints when they build their domain. The reason behind this change is twofold: 1) This removes a big chunk of preprocessing logic from the TempScopInfo, namely the Conditionals we used to build there. Additionally to moving this logic it is also simplified. Instead of walking the dominance tree up for each basic block in the region (as we did before), we now traverse the region only once in order to collect the domain conditions. 2) This is the first step towards the isl based domain creation. The second step will traverse the region similar to this step, however it will propagate back edge conditions. Once both are in place this conditional handling will allow multiple exit loops additional logic. Reviewers: grosser Differential Revision: http://reviews.llvm.org/D12428 llvm-svn: 246398
* Ignore debug intrinsics and do not model their potential scalar metadata readsTobias Grosser2015-08-301-0/+3
| | | | | | | | | | Our code generation currently does not support scalar references to metadata values. Hence, it would crash if we try to model scalar dependences to metadata values. Fortunately, for one of the common uses, debug information, we can for now just ignore the relevant intrinsics and consequently the issue of how to model scalar dependences to metadata. llvm-svn: 246388
* Add a field to the memory access class for a related value.Johannes Doerfert2015-08-171-9/+14
| | | | | | | | | | | | | | | | | | | | | The new field in the MemoryAccess allows us to track a value related to that access: - For real memory accesses the value is the loaded result or the stored value. - For straigt line scalar accesses it is the access instruction itself. - For PHI operand accesses it is the operand value. We use this value to simplify code which deduced information about the value later in the Polly pipeline and was known to be error prone. Reviewers: grosser, Meinsersbur Subscribers: #polly Differential Revision: http://reviews.llvm.org/D12062 llvm-svn: 245213
* Fix Polly after SCEV port to new pass managerTobias Grosser2015-08-171-3/+3
| | | | | | This fixes compilation after LLVM commit r245193. llvm-svn: 245211
* Make TempScopInfo a RegionPassMichael Kruse2015-08-141-20/+17
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This modifies the order in which Polly passes are executed. Assuming a function has two scops (A and B), the order before was: FunctionPassManager ScopDetection IndependentBlocks TempScopInfo for A and B RegionPassManager ScopInfo for A DependenceInfo for A IslScheduleOptimizer for A IslAstInfo for A CodeGeneration for A ScopInfo for B DependenceInfo for B IslScheduleOptimizer for B IslAstInfo for B CodeGeneration for B After this patch: FunctionPassManager ScopDetection IndependentBlocks RegionPassManager TempScopInfo for A ScopInfo for A DependenceInfo for A IslScheduleOptimizer for A IslAstInfo for A CodeGeneration for A TempScopInfo for B ScopInfo for B DependenceInfo for B IslScheduleOptimizer for B IslAstInfo for B CodeGeneration for B TempScopInfo for B might store information and references to the IR that CodeGeneration for A might modify. Changing the order ensures that the IR is not modified from the analysis of a region until code generation. Reviewers: grosser Differential Revision: http://reviews.llvm.org/D12014 llvm-svn: 245091
* Always model PHI nodes in scop (if not in same nonaffine subregion)Tobias Grosser2015-08-121-7/+7
| | | | | | | | | | | | | | | | | | | | | | | Before we only modeled PHI nodes if at least one incoming basic block was itself part of the region, now we always model them except if all of their operands are part of a single non-affine subregion which we model as a black-box. This change only affects PHI nodes in the entry block, that have exactly one incoming edge. Before this change, we did not model them and as a result code generation would not know how to code generate them. With this change, code generation can code generate them like any other PHI node. This issue was exposed by r244606. Before this change simplifyRegion would have moved these PHI nodes out of the SCoP, so we would never have tried to code generate them. We could implement this behavior again, but changing the IR after the scop has been modeled and transformed always adds a risk of us invalidating earlier analysis results. It seems more save and overall also more consistent to just model and handle this one-entry-edge PHI nodes like any other PHI node in the scop. Solution proposed by: Michael Kruse <llvm@meinersbur.de> llvm-svn: 244721
* Optionally model read-only scalarsTobias Grosser2015-08-041-0/+21
| | | | | | | | | Even though read-only accesses to scalars outside of a scop do not need to be modeled to derive valid transformations or to generate valid sequential code, but information about them is useful when we considering memory footprint analysis and/or kernel offloading. llvm-svn: 243981
* Use the branch instruction to define the location of a PHI-node writeTobias Grosser2015-08-021-3/+3
| | | | | | | | | | | | | | | | | | | We use the branch instruction as the location at which a PHI-node write takes place, instead of the PHI-node itself. This allows us to identify the basic-block in a region statement which is on the incoming edge of the PHI-node and for which the write access was originally introduced. As a result we can, during code generation, avoid generating PHI-node write accesses for basic blocks that do not preceed the PHI node without having to look at the IR again. This change fixes a bug which was introduced in r243420, when we started to explicitly model PHI-node reads and writes, but dropped some additional checks that where still necessary during code generation to not emit PHI-node writes for basic-blocks that are not on incoming edges of the original PHI node. Compared to the code before r243420 the new code does not need to inspect the IR any more and we also do not generate multiple redundant writes. llvm-svn: 243852
* Keep track of ScopArrayInfo objects that model PHI node storageTobias Grosser2015-07-281-2/+4
| | | | | | | | | | | | | | | | | | | | | Summary: When translating PHI nodes into memory dependences during code generation we require two kinds of memory. 'Normal memory' as for all scalar dependences and 'PHI node memory' to store the incoming values of the PHI node. With this patch we now mark and track these two kinds of memories, which we previously incorrectly marked as a single memory object. Being aware of PHI node storage makes code generation easier, as we do not need to guess what kind of storage a scalar reference requires. This simplifies the code nicely. Reviewers: jdoerfert Subscribers: pollydev, llvm-commits Differential Revision: http://reviews.llvm.org/D11554 llvm-svn: 243420
* Store ArrayShape in shared_ptr and MemAccs as actual objectsTobias Grosser2015-06-041-3/+4
| | | | | | This fixes two more memory leaks. llvm-svn: 239050
* Store comparison objects as objects, not pointersTobias Grosser2015-06-041-10/+5
| | | | | | | This fixes a memory leak. If we store the actual objects we can not forget to free them. llvm-svn: 239033
* Sort include directivesTobias Grosser2015-05-091-2/+2
| | | | | | | | | | Upcoming revisions of isl require us to include header files explicitly, which have previously been already transitively included. Before we add them, we sort the existing includes. Thanks to Chandler for sort_includes.py. A simple, but very convenient script. llvm-svn: 236930
* Allow loops in non-affine subregions -- SCoP ModelingJohannes Doerfert2015-04-121-3/+20
| | | | | | | | | | | This will allow the ScopInfo to build the polyhedral representation for non-affine regions that contain loops. Such loops are basically not visible in the SCoP representation. Accesses that are variant in such loops are therefor represented as non-affine accesses. Differential Revision: http://reviews.llvm.org/D8153 llvm-svn: 234713
* Fix compilation after 'Make DataLayout Non-Optional in the Module' commitTobias Grosser2015-03-051-3/+2
| | | | llvm-svn: 231362
* Do not model scalar accesses in non-affine subregionsJohannes Doerfert2015-03-021-10/+42
| | | | | | | | | | If a scalar was defined and used only in a non-affine subregion we do not need to model the accesses. However, if the scalar was defined inside the region and escapes the region we have to model the access. The same is true if the scalar was defined outside and used inside the region. llvm-svn: 230960
* Allow non-affine control flow -- SCoP ModelingJohannes Doerfert2015-02-241-4/+24
| | | | | | | | | | | | This allows us to model non-affine regions in the SCoP representation. SCoP statements can now describe either basic blocks or non-affine regions. In the latter case all accesses in the region are accumulated for the statement and write accesses, except in the entry, have to be marked as may-write. Differential Revision: http://reviews.llvm.org/D7846 llvm-svn: 230329
* Drop an assert and XFAIL two test casesTobias Grosser2015-02-111-6/+0
| | | | | | | This gets the buildbot green to avoid further emails. Johannes will fix this later in the evening. llvm-svn: 228862
* Model scalar writes with uses outside the SCoPJohannes Doerfert2015-02-111-8/+13
| | | | | | | | | | These write are important as they will force the scheduling and code generation of an otherwise trivial statement and also impose an order of execution needed to guarantee the correct final value for a scalar in a loop. Added test case modeled after ClamAV/clamscan. llvm-svn: 228847
* [FIX] Special case for branch users of scalar valuesJohannes Doerfert2015-02-111-0/+6
| | | | llvm-svn: 228832
* Model PHI nodes without demoting themJohannes Doerfert2015-02-061-2/+49
| | | | | | | | | | This allows us to model PHI nodes in the polyhedral description without demoting them. The modeling however will result in the same accesses as the demotion would have introduced. Differential Revision: http://reviews.llvm.org/D7415 llvm-svn: 228433
* [NFC] Remove some unnecessary local objectsJohannes Doerfert2015-02-021-9/+6
| | | | llvm-svn: 227844
* [FIX] Debug build + instrinsic handlingJohannes Doerfert2015-01-261-0/+2
| | | | | | | The ignored intrinsics needed to be ignored in three other places as well. Tests and lnt pass now. llvm-svn: 227092
* [PM] Update Polly following LLVM r226373 which refactors LoopInfo inChandler Carruth2015-01-171-3/+3
| | | | | | preparation for the new pass manager. llvm-svn: 226374
* Do not incorrectly set the inverted flag.Hongbin Zheng2014-11-281-1/+16
| | | | | | | | | | | | | | | | | | In TempScopInfo::buildCondition we extract the conditions to guard the BB *in addition of* loop bounds. This means we should only consider the conditions in the paths (in CFG) that do not contain cycles (loops). At the same time, we set the invert flag if the FalseBB of the current branch dominates our target BB to indicate that we reach the target BB with an inverted condition from the current branch. In this case, the path from the FalseBB contains a cycle if the FalseBB is the target of a backedge. The conditions implied by such a path should not be consider. We can identify such a case by checking if the TrueBB also dominates our target BB, which means we can also reach our target BB from the TrueBB, without going through the backedge. llvm-svn: 222907
* Remove the LoopBounds from the TempScop class.Johannes Doerfert2014-11-011-21/+1
| | | | | | | | | We will use ScalarEvolution in the ScopInfo.cpp to get the loop trip count, not cache it in the TempScop object. Differential Revision: http://reviews.llvm.org/D6070 llvm-svn: 221035
* Remove the MaxLoopDepth attribute from the TempScop classJohannes Doerfert2014-11-011-11/+1
| | | | | | | | | | Now MaxLoopDepth only lives in Scops not in TempScops anymore. This is the first part of a series of changes to make TempScops obsolete. Differential Revision: http://reviews.llvm.org/D6069 llvm-svn: 221026
* [Polly] Move MAY/MUST write property to IRAccessJohannes Doerfert2014-09-121-4/+9
| | | | | | Differential Revision: http://reviews.llvm.org/D5223 llvm-svn: 217665
* Update for RegionInfo changes.Matt Arsenault2014-07-191-1/+2
| | | | | | | Mostly related to missing includes and renaming of the pass to RegionInfoPass. llvm-svn: 213457
* record delinearization result and reuse it in polyhedral translationSebastian Pop2014-06-031-27/+10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Without this patch, the testcase would fail on the delinearization of the second array: ; void foo(long n, long m, long o, double A[n][m][o]) { ; for (long i = 0; i < n; i++) ; for (long j = 0; j < m; j++) ; for (long k = 0; k < o; k++) { ; A[i+3][j-4][k+7] = 1.0; ; A[i][0][k] = 2.0; ; } ; } ; CHECK: [n, m, o] -> { Stmt_for_body6[i0, i1, i2] -> MemRef_A[3 + i0, -4 + i1, 7 + i2] }; ; CHECK: [n, m, o] -> { Stmt_for_body6[i0, i1, i2] -> MemRef_A[i0, 0, i2] }; Here is the output of FileCheck on the testcase without this patch: ; CHECK: [n, m, o] -> { Stmt_for_body6[i0, i1, i2] -> MemRef_A[i0, 0, i2] }; ^ <stdin>:26:2: note: possible intended match here [n, m, o] -> { Stmt_for_body6[i0, i1, i2] -> MemRef_A[o0] }; ^ It is possible to find a good delinearization for A[i][0][k] only in the context of the delinearization of both array accesses. There are two ways to delinearize together all array subscripts touching the same base address: either duplicate the code from scop detection to first gather all array references and then run the delinearization; or as implemented in this patch, use the same delinearization info that we computed during scop detection. llvm-svn: 210117
* delinearize does not return a remainderSebastian Pop2014-05-271-3/+1
| | | | llvm-svn: 209696
* pass element size to delinearizationSebastian Pop2014-05-271-1/+3
| | | | | | | | | Instead of relying on the delinearization to infer the size of an element, compute the element size from the base address type. This is a much more precise way of computing the element size than before, as we would have mixed together the size of an element with the strides of the innermost dimension. llvm-svn: 209695
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-2/+2
| | | | | | | | | | definition below all of the header #include lines, Polly edition. If you want to know more details about this, you can see the recent commits to Debug.h in LLVM. This is just the Polly segment of a cleanup I'm doing globally for this macro. llvm-svn: 206852
* only delinearize when the access function is not affineSebastian Pop2014-04-101-14/+16
| | | | llvm-svn: 205971
* ScopInfo: Scalar accesses are zero dimensionalTobias Grosser2014-04-101-7/+3
| | | | llvm-svn: 205958
* clang format last patchSebastian Pop2014-04-081-7/+7
| | | | llvm-svn: 205804
* delinearize memory access functionsSebastian Pop2014-04-081-6/+43
| | | | llvm-svn: 205799
* clang-format: Remove empty linesTobias Grosser2014-03-211-1/+0
| | | | llvm-svn: 204468
* [C++11] Update to reflect the Value::use_iterator andChandler Carruth2014-03-091-8/+7
| | | | | | | | | | Value::user_iterator changes in LLVM r203364. Converts several of these loops to nice range based loops in the process. Built and tested cleanly for me, yay for being able to fully build and test Polly changes! llvm-svn: 203381
* [C++11] Use foreach iterator for blocks and operandsTobias Grosser2014-03-031-12/+6
| | | | llvm-svn: 202707
* Update for llvm api change.Rafael Espindola2014-02-251-3/+3
| | | | llvm-svn: 202183
* Fix typoTobias Grosser2014-02-201-1/+1
| | | | llvm-svn: 201814
* Check scops a second time before working on themTobias Grosser2014-02-181-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | In rare cases the modification of one scop can effect the validity of other scops, as code generation of an earlier scop may make the scalar evolution functions derived for later scops less precise. The example that triggered this patch was a scop that contained an 'or' expression as follows: %add13710 = or i32 %j.19, 1 --> {(1 + (4 * %l)),+,2}<nsw><%for.body81> Scev could only analyze the 'or' as it knew %j.19 is a multiple of 2. This information was not available after the first scop was code generated (or independent-blocks was run on it) and SCEV could not derive a precise SCEV expression any more. This means we could not any more code generate this SCoP. My current understanding is that there is always the risk that an earlier code generation change invalidates later scops. As the example we have seen here is difficult to avoid, we use this occasion to guard us against all such invalidations. This patch "solves" this issue by verifying right before we start working on a detected scop, if this scop is in fact still valid. This adds a certain overhead. However the verification we run is anyways very fast and secondly it is only run on detected scops. So the overhead should not be very large. As a later optimization we could detect scops only on demand, such that we need to run scop-detections always only a single time. This should fix the single last failure in the LLVM test-suite for the new scev-based code generation. llvm-svn: 201593
* Fix formattingTobias Grosser2014-02-121-2/+1
| | | | llvm-svn: 201204
OpenPOWER on IntegriCloud