summaryrefslogtreecommitdiffstats
path: root/polly/lib/CodeGen
Commit message (Collapse)AuthorAgeFilesLines
* Rename Conjuncts -> Disjunctions. NFC.Michael Kruse2016-05-021-2/+2
| | | | | | | | The check for complexity compares the number of polyhedra in a set, which are combined by disjunctions (union, "OR"), not conjunctions (intersection, "AND"). llvm-svn: 268223
* BlockGenerator: Drop leftover debug statementTobias Grosser2016-04-281-1/+0
| | | | llvm-svn: 267874
* [FIX] Propagate execution domain of invariant loadsJohannes Doerfert2016-04-271-7/+15
| | | | | | | | | | | If the base pointer of an invariant load is is loaded conditionally, that condition needs to hold for the invariant load too. The structure of the program will imply this for domain constraints but not for imprecisions in the modeling. To this end we will propagate the execution context of base pointers during code generation and thus ensure the derived pointer does not access an invalid base pointer. llvm-svn: 267707
* Check only loop control of loops that are part of the regionJohannes Doerfert2016-04-251-3/+0
| | | | | | | 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
* Allow pointer expressions in SCEVs again.Johannes Doerfert2016-04-101-83/+33
| | | | | | | | | 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
* Add __isl_give annotations to return types [NFC]Johannes Doerfert2016-04-091-2/+3
| | | | llvm-svn: 265882
* Collect and verify generated parallel subfunctionsJohannes Doerfert2016-04-082-0/+5
| | | | | | | | We verify the optimized function now for a long time and it helped to track down bugs early. This will now also happen for all parallel subfunctions we generate. llvm-svn: 265823
* [FIX] Look through div & srem instructions in SCEVsJohannes Doerfert2016-04-081-2/+2
| | | | | | | | | The findValues() function did not look through div & srem instructions that were part of the argument SCEV. However, in different other places we already look through it. This mismatch caused us to preload values in the wrong order. llvm-svn: 265775
* [FIX] Adjust the insert point for non-affine region PHIsJohannes Doerfert2016-04-011-4/+7
| | | | | | | | | | If a non-affine region PHI is generated we should not move the insert point prior to the synthezised value in the same block as we might split that block at the insert point later on. Only if the incoming value should be placed in a different block we should change the insertion point. llvm-svn: 265132
* CodegenCleanup: Drop -load-combine passTobias Grosser2016-03-251-1/+0
| | | | | | | | | | | | | | | This pass is not enabled in the default tool chain and currently can run into an infinite loop, due to other parts of LLVM generating incorrect IR (http://llvm.org/PR27065) -- which is not executed and consequently does not seem to disturb other passes. As this pass is not really needed, we can just drop it to get our build clean. This fixes the timeout issues in MultiSource/Benchmarks/MiBench/consumer-jpeg and MultiSource/Benchmarks/mediabench/jpeg/jpeg-6a/cjpeg for -polly-position=before-vectorizer -polly-process-unprofitable.. Unfortunately, we are still left with a miscompile in cjpeg. llvm-svn: 264396
* Add namespace for struct [NFC]Johannes Doerfert2016-03-241-10/+12
| | | | | | This will clean up the doxygen documentation. llvm-svn: 264272
* Codegen:Do not invalidate dominator tree when bailing out during code generationTobias Grosser2016-03-231-6/+28
| | | | | | | | | When codegenerating invariant loads in some rare cases we cannot generate code and bail out. This change ensures that we maintain a valid dominator tree in these situations. This fixes llvm.org/PR26736 Contributed-by: Matthias Reisinger <d412vv1n@gmail.com> llvm-svn: 264142
* [BlockGenerator] Fix PHI merges for MK_Arrays.Michael Kruse2016-03-031-0/+10
| | | | | | | | | | | | | | | | | | Value merging is only necessary for scalars when they are used outside of the scop. While an array's base pointer can be used after the scop, it gets an extra ScopArrayInfo of type MK_Value. We used to generate phi's for both of them, where one was assuming the reault of the other phi would be the original value, because it has already been replaced by the previous phi. This resulted in IR that the current IR verifier allows, but is probably illegal. This reduces the number of LNT test-suite fails with -polly-position=before-vectorizer -polly-process-unprofitable from 16 to 10. Also see llvm.org/PR26718. llvm-svn: 262629
* Allow the client of DependenceInfo to obtain dependences at different ↵Hongbin Zheng2016-03-031-1/+2
| | | | | | granularities. llvm-svn: 262591
* Fix non-synthesizable loop exit values.Michael Kruse2016-03-012-6/+7
| | | | | | | | | | | 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
* Track assumptions and restrictions separatlyJohannes Doerfert2016-03-011-2/+9
| | | | | | | | | | | | | | | In order to speed up compile time and to avoid random timeouts we now separately track assumptions and restrictions. In this context assumptions describe parameter valuations we need and restrictions describe parameter valuations we do not allow. During AST generation we create a runtime check for both, whereas the one for the restrictions is negated before a conjunction is build. Except the In-Bounds assumptions we currently only track restrictions. Differential Revision: http://reviews.llvm.org/D17247 llvm-svn: 262328
* [FIX] Prevent compile time problems due to complex invariant loadsJohannes Doerfert2016-03-011-1/+18
| | | | | | This cures the symptoms we see in h264 of SPEC2006 but not the cause. llvm-svn: 262327
* IslAst: Expose run-time check generation as individual functionTobias Grosser2016-02-261-2/+7
| | | | | | | | This allows to construct run-time checks for a scop without having to generate a full AST. This is currently not taken advantage of in Polly itself, but external users may benefit from this feature. llvm-svn: 262009
* Adapt to LLVM head, againHongbin Zheng2016-02-251-1/+1
| | | | llvm-svn: 261905
* Revert "Adapt to LLVM head. NFC"Hongbin Zheng2016-02-251-1/+1
| | | | | | This reverts commit 4d3753b9646a69c00d234ccd6e91dc3d0ea5d643. llvm-svn: 261892
* Adapt to LLVM head. NFCHongbin Zheng2016-02-251-1/+1
| | | | llvm-svn: 261886
* Use inline local variable declaration. NFC.Michael Kruse2016-02-251-3/+2
| | | | llvm-svn: 261876
* Support calls with known ModRef function behaviourJohannes Doerfert2016-02-251-1/+5
| | | | | | | | | 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
* Fix DomTree preservation for generated subregions.Michael Kruse2016-02-251-5/+49
| | | | | | | | | The generated dedicated subregion exit block was assumed to have the same dominance relation as the original exit block. This is incorrect if the exit block receives other edges than only from the subregion, which results in that e.g. the subregion's entry block does not dominate the exit block. llvm-svn: 261865
* Introduce ScopStmt::getEntryBlock(). NFC.Michael Kruse2016-02-241-2/+1
| | | | | | This replaces an ungly inline ternary operator pattern. llvm-svn: 261792
* Introduce Scop::getStmtFor. NFC.Michael Kruse2016-02-241-1/+1
| | | | | | | | | | | Replace Scop::getStmtForBasicBlock and Scop::getStmtForRegionNode, and add overloads for llvm::Instruction and llvm::RegionNode. getStmtFor and overloads become the common interface to get the Stmt that contains something. Named after LoopInfo::getLoopFor and RegionInfo::getRegionFor. llvm-svn: 261791
* Add assertions checking def dominates use. NFC.Michael Kruse2016-02-241-0/+20
| | | | | | | | This is also be caught by the function verifier, but disconnected from the place that produced it. Catch it already at creation to be able to reason more directly about the cause. llvm-svn: 261790
* Annotation of SIMD loopsRoman Gareev2016-02-232-9/+58
| | | | | | | | | | | | | | | | | | | | | | | | | | | Use 'mark' nodes annotate a SIMD loop during ScheduleTransformation and skip parallelism checks. The buildbot shows the following compile/execution time changes: Compile time: Improvements Δ Previous Current σ …/gesummv -6.06% 0.2640 0.2480 0.0055 …/gemver -4.46% 0.4480 0.4280 0.0044 …/covariance -4.31% 0.8360 0.8000 0.0065 …/adi -3.23% 0.9920 0.9600 0.0065 …/doitgen -2.53% 0.9480 0.9240 0.0090 …/3mm -2.33% 1.0320 1.0080 0.0087 Execution time: Regressions Δ Previous Current σ …/viterbi 1.70% 5.1840 5.2720 0.0074 …/smallpt 1.06% 12.4920 12.6240 0.0040 Reviewed-by: Tobias Grosser <tobias@grosser.es> Differential Revision: http://reviews.llvm.org/D14491 llvm-svn: 261620
* IslAst: Expose IslAst class in header file [NFC]Tobias Grosser2016-02-211-27/+0
| | | | | | | This allows other passes and transformations to use some of the existing AST building infrastructure. This is not yet used in Polly itself. llvm-svn: 261496
* BlockGenerator: Drop unnecessary return valueTobias Grosser2016-02-211-4/+3
| | | | llvm-svn: 261473
* Codegen: Print error in Polly code verification and allow to disable ↵Tobias Grosser2016-02-191-8/+12
| | | | | | | | | | | | verfication. We now always print the reason why the code did not pass the LLVM verifier and we also allow to disable verfication with -polly-codegen-verify=false. Before this change the first assertion had generally no information why or what might have gone wrong and it was also impossible to -view-cfg without recompile. This change makes debugging bugs that result in incorrect IR a lot easier. llvm-svn: 261320
* [Refactor] Move isl_ctx into Scop.Hongbin Zheng2016-02-171-1/+4
| | | | | | | | | | | | | | | | | | | | After we moved isl_ctx into Scop, we need to free the isl_ctx after freeing all isl objects, which requires the ScopInfo pass to be freed at last. But this is not guaranteed by the PassManager, and we need extra code to free the isl_ctx at the right time. We introduced a shared pointer to manage the isl_ctx, and distribute it to all analyses that create isl objects. As such, whenever we free an analyses with the shared_ptr (and also free the isl objects which are created by the analyses), we decrease the (shared) reference counter of the shared_ptr by 1. Whenever the reference counter reach 0 in the releaseMemory function of an analysis, that analysis will be the last one that hold any isl objects, and we can safely free the isl_ctx with that analysis. Differential Revision: http://reviews.llvm.org/D17241 llvm-svn: 261100
* Replace getLoopForInst by getLoopForStmtJohannes Doerfert2016-02-161-10/+12
| | | | | | This patch was extracted from http://reviews.llvm.org/D13611. llvm-svn: 260958
* Set AST Build for all statements [NFC]Johannes Doerfert2016-02-161-2/+5
| | | | llvm-svn: 260956
* CodeGeneration: Add back verification of generated codeTobias Grosser2016-02-141-0/+3
| | | | | | This got accidentally dropped in r260025 llvm-svn: 260857
* Separate invariant equivalence classes by typeJohannes Doerfert2016-02-071-11/+6
| | | | | | | | | | | | | We now distinguish invariant loads to the same memory location if they have different types. This will cause us to pre-load an invariant location once for each type that is used to access it. However, we can thereby avoid invalid casting, especially if an array is accessed though different typed/sized invariant loads. This basically reverts the changes in r260023 but keeps the test cases. llvm-svn: 260045
* Simplify code [NFC]Johannes Doerfert2016-02-071-1/+1
| | | | llvm-svn: 260030
* Make memory accesses with different element types optionalTobias Grosser2016-02-071-3/+0
| | | | | | | | 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
* IslNodeBuilder: Invariant load hoisting of elements with differing sizesTobias Grosser2016-02-061-18/+7
| | | | | | | | | | | | | | | Always use access-instruction pointer type to load the invariant values. Otherwise mismatches between ScopArrayInfo element type and memory access element type will result in invalid casts. These type mismatches are after r259784 a lot more common and also arise with types of different size, which have not been handled before. Interestingly, this change actually simplifies the code, as we now have only one code path that is always taken, rather then a standard code path for the common case and a "fixup" code path that replaces the standard code path in case of mismatching types. llvm-svn: 260009
* Support accesses with differently sized types to the same arrayTobias Grosser2016-02-042-6/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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/+5
| | | | | | 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-5/+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
* Add const keyword to MemoryAccess argument [NFC]Johannes Doerfert2016-02-021-1/+1
| | | | llvm-svn: 259504
* Introduce MemAccInst helper class; NFCMichael Kruse2016-01-273-20/+22
| | | | | | | | | | | | | | | | 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
* Unique phi write accessesMichael Kruse2016-01-261-31/+80
| | | | | | | | | | | | | | | | | | | Ensure that there is at most one phi write access per PHINode and ScopStmt. In particular, this would be possible for non-affine subregions with multiple exiting blocks. We replace multiple MAY_WRITE accesses by one MUST_WRITE access. The written value is constructed using a PHINode of all exiting blocks. The interpretation of the PHI WRITE's "accessed value" changed from the incoming value to the PHI like for PHI READs since there is no unique incoming value. Because region simplification shuffles around PHI nodes -- particularly with exit node PHIs -- the PHINodes at analysis time does not always exist anymore in the code generation pass. We instead remember the incoming block/value pair in the MemoryAccess. Differential Revision: http://reviews.llvm.org/D15681 llvm-svn: 258809
* BlockGenerators: Replace getNewScalarValue with getNewValueTobias Grosser2016-01-261-52/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | Both functions implement the same functionality, with the difference that getNewScalarValue assumes that globals and out-of-scop scalars can be directly reused without loading them from their corresponding stack slot. This is correct for sequential code generation, but causes issues with outlining code e.g. for OpenMP code generation. getNewValue handles such cases correctly. Hence, we can replace getNewScalarValue with getNewValue. This is not only more future proof, but also eliminates a bunch of code. The only functionality that was available in getNewScalarValue that is lost is the on-demand creation of scalar values. However, this is not necessary any more as scalars are always loaded at the beginning of each basic block and will consequently always be available when scalar stores are generated. As this was not the case in older versions of Polly, it seems the on-demand loading is just some older code that has not yet been removed. Finally, generateScalarLoads also generated loads for values that are loop invariant, available in GlobalMap and which are preferred over the ones loaded in generateScalarLoads. Hence, we can just skip the code generation of such scalar values, avoiding the generation of dead code. Differential Revision: http://reviews.llvm.org/D16522 llvm-svn: 258799
* BlockGenerators: Avoid redundant map lookup [NFC]Tobias Grosser2016-01-241-2/+2
| | | | llvm-svn: 258660
* Make sure we preserve alignment information after hoisting invariant loadJohannes Doerfert2016-01-191-4/+11
| | | | | | | | | | | In Polly, after hoisting loop invariant loads outside loop, the alignment information for hoisted loads are missing, this patch restore them. Contributed-by: Lawrence Hu <lawrence@codeaurora.org> Differential Revision: http://reviews.llvm.org/D16160 llvm-svn: 258105
* Fix of r257495.Roman Gareev2016-01-121-1/+0
| | | | | | Remove redundant "FPM->add(createDemoteRegisterToMemoryPass());" llvm-svn: 257514
* We do not need to schedule another loop interchange pass after Polly, as PollyRoman Gareev2016-01-121-1/+1
| | | | | | | | | | | should perform loop interchanges itself. This also fixes a bug we see due to the "loop-interchange" pass producing incorrect IR when compiling linpack-pc.c from the LLVM test-suite with "-polly-position=before-vectorizer". Reviewed-by: Tobias Grosser <tobias@grosser.es> llvm-svn: 257495
OpenPOWER on IntegriCloud