summaryrefslogtreecommitdiffstats
path: root/polly/lib/CodeGen/CodeGeneration.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Collect and verify generated parallel subfunctionsJohannes Doerfert2016-04-081-0/+2
| | | | | | | | 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
* 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
* 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
* 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
* CodeGeneration: Add back verification of generated codeTobias Grosser2016-02-141-0/+3
| | | | | | This got accidentally dropped in r260025 llvm-svn: 260857
* 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
* Adjust formatting to clang-format changes in 256149Tobias Grosser2015-12-211-1/+1
| | | | llvm-svn: 256151
* IR cleanup after CodeGenerationMichael Kruse2015-11-261-0/+6
| | | | | | | | | | | | | | | | | | | | | | | | Re-run canonicalization passes after Polly's code generation. The set of passes currently added here are nearly all the passes between --polly-position=early and --polly-position=before-vectorizer, i.e. all passes that would usually run after Polly. In order to run these only if Polly actually modified the code, we add a function attribute "polly-optimzed" to a function that contains generated code. The cleanup pass is skipped if the function does not have this attribute. There is no support by the (legacy) PassManager to run passes only under some conditions. One could have wrapped all transformation passes to run only when CodeGeneration changed the code, but the analyses would run anyway. This patch creates an independent pass manager. The disadvantages are that all analyses have to re-run even if preserved and it does not honor compiler switches like the PassManagerBuilder does. Differential Revision: http://reviews.llvm.org/D14333 llvm-svn: 254150
* [FIX] Use unreachable to indicate dead code and repair dominanceJohannes Doerfert2015-11-081-1/+6
| | | | | | | | | | | | When we bail out early we make the partially build new code path practically dead, though it was not unreachable. To remove dominance problems we now make it not only dead but also prevent the control flow to join with the original code path, thus allow to use original values after the SCoP without any PHI nodes. This fixes bug 25447. llvm-svn: 252420
* Verify IR after we bail outJohannes Doerfert2015-11-081-9/+11
| | | | | | | | | The bail out in r252412 left the code generation without verifying the (so far) generated IR. This will change now and ensure we always run the verifier. Suggested-by: Tobias Grosser <tobias@grosser.es> llvm-svn: 252419
* [FIX] Bail out if there is a dependence cycle between invariant loadsJohannes Doerfert2015-11-071-1/+8
| | | | | | | | | | | | | While the program cannot cause a dependence cycle between invariant loads, additional constraints (e.g., to ensure finite loops) can introduce them. It is hard to detect them in the SCoP description, thus we will only check for them at code generation time. If such a recursion is detected we will bail out the code generation and place a "false" runtime check to guarantee the original code is used. This fixes bug 25443. llvm-svn: 252412
* polly/ADT: Remove implicit ilist iterator conversions, NFCDuncan P. N. Exon Smith2015-11-061-1/+1
| | | | | | | | | | | | | Remove all the implicit ilist iterator conversions from polly, in preparation for making them illegal in ADT. There was one oddity I came across: at line 95 of lib/CodeGen/LoopGenerators.cpp, there was a post-increment `Builder.GetInsertPoint()++`. Since it was a no-op, I removed it, but I admit I wonder if it might be a bug (both before and after this change)? Perhaps it should be a pre-increment? llvm-svn: 252357
* Remove independent blocks passJohannes Doerfert2015-10-181-1/+0
| | | | | | | | | | | 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
* Allow invariant loads in the SCoP descriptionJohannes Doerfert2015-10-071-1/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Make ScopAnnotator a function-local variable to ensure it is freed at each runTobias Grosser2015-10-041-3/+1
| | | | | | | | | | | | When the ScopAnnotator was a class member variable some of the maps it contains have not been properly cleared. As a result we had dangling pointers to llvm::Value(s) which got detected by the AssertingVH we recently added. No test case as this issue is hard to reproduce reliably as subsequent optimizations need to delete some of the llvm::Values we still keep in our lists. llvm-svn: 249269
* Identify and hoist definitively invariant loadsJohannes Doerfert2015-09-291-1/+2
| | | | | | | | | | | | | | | | | | | As a first step in the direction of assumed invariant loads (loads that are not written in some context) we now detect and hoist definitively invariant loads. These invariant loads will be preloaded in the code generation and used in the optimized version of the SCoP. If the load is only conditionally executed the preloaded version will also only be executed under the same condition, hence we will never access memory that wouldn't have been accessed otherwise. This is also the most distinguishing feature to licm. As hoisting can make statements empty we will simplify the SCoP and remove empty statements that would otherwise cause artifacts in the code generation. Differential Revision: http://reviews.llvm.org/D13194 llvm-svn: 248861
* [NFC] Consistenly use commented and annotated ScopPass functionsJohannes Doerfert2015-09-271-2/+2
| | | | | | | | | | | The changes affect methods that are part of the Pass interface and include: - Comments that describe the methods purpose. - A consistent use of the keywords override and virtual. Additionally, the printScop method is now optional and removed from SCoP passes that do not implement it. llvm-svn: 248685
* Sort includes using Chandler's sort_includes.py scriptTobias Grosser2015-09-251-3/+3
| | | | llvm-svn: 248568
* Merge TempScopInfo into ScopInfoMichael Kruse2015-09-101-1/+0
| | | | | | | | | | | | | The TempScopInfo (-polly-analyze-ir) pass is removed and its work taken over by ScopInfo (-polly-scops). Several tests depend on -polly-analyze-ir and use -polly-scops instead which for the moment prints the output of both passes. This again is not expected by some other tests, especially those with negative searches, which have been adapted. Differential Version: http://reviews.llvm.org/D12694 llvm-svn: 247288
* Merge TempScopInfo.{cpp|h} into ScopInfo.{cpp|h}Michael Kruse2015-09-101-1/+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-0/+8
| | | | llvm-svn: 247198
* Fix Polly after SCEV port to new pass managerTobias Grosser2015-08-171-4/+4
| | | | | | This fixes compilation after LLVM commit r245193. llvm-svn: 245211
* Make TempScopInfo a RegionPassMichael Kruse2015-08-141-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Assign regions to all BBs from CodeGenerationMichael Kruse2015-08-111-0/+13
| | | | | | | | | | In order to have a valid region analysis, we assign all newly created blocks to the parent of the scop's region. This is correct for any pre-existing regions (including the scop's region and its parent), but does not discover any region inside the generated code. For Polly this is not necessary because we do not want to re-run Polly on its own generated code anyway. Reviewers: grosser Part of Differential Revision: http://reviews.llvm.org/D11867 llvm-svn: 244608
* Revise the simplification of regionsMichael Kruse2015-08-111-4/+8
| | | | | | | | | | | | | | | | | | | | The previous code had several problems: For newly created BasicBlocks it did not (always) call RegionInfo::setRegionFor in order to update its analysis. At the moment RegionInfo does not verify its BBMap, but will in the future. This is fixed by determining the region new BBs belong to and set it accordingly. The new executeScopConditionally() requires accurate getRegionFor information. Which block is created by SplitEdge depends on the incoming and outgoing edges of the blocks it connects, which makes handling its output more difficult than it needs to be. Especially for finding which block has been created an to assign a region to it for the setRegionFor problem above. This patch uses an implementation for splitEdge that always creates a block between the predecessor and successor. simplifyRegion has also been simplified by using SplitBlockPredecessors instead of SplitEdge. Isolating the entries and exits have been refectored into individual functions. Previously simplifyRegion did more than just ensuring that there is only one entering and one exiting edge. It ensured that the entering block had no other outgoing edge which was necessary for executeScopConditionally(). Now the latter uses the alternative splitEdge implementation which can handle this situation so simplifyRegion really only needs to simplify the region. Also, executeScopConditionally assumed that there can be no PHI nodes in blocks with one incoming edge. This is wrong and LCSSA deliberately produces such edges. However, previous passes ensured that there can be no such PHIs in exit nodes, but which will no longer hold in the future. The new code that the property that it preserves the identity of region block (the property that the memory address of the BasicBlock containing the instructions remains the same; new blocks only contain PHI nodes and a terminator), especially the entry block. As a result, there is no need to update the reference to the BasicBlock of ScopStmt that contain its instructions because they have been moved to other basic blocks. Reviewers: grosser Part of Differential Revision: http://reviews.llvm.org/D11867 llvm-svn: 244606
* Add scalar and phi code generationJohannes Doerfert2015-05-221-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | To reduce compile time and to allow more and better quality SCoPs in the long run we introduced scalar dependences and PHI-modeling. This patch will now allow us to generate code if one or both of those options are set. While the principle of demoting scalars as well as PHIs to memory in order to communicate their value stays the same, this allows to delay the demotion till the very end (the actual code generation). Consequently: - We __almost__ do not modify the code if we do not generate code for an optimized SCoP in the end. Thus, the early exit as well as the unprofitable option will now actually preven us from introducing regressions in case we will probably not get better code. - Polly can be used as a "pure" analyzer tool as long as the code generator is set to none. - The original SCoP is almost not touched when the optimized version is placed next to it. Runtime regressions if the runtime checks chooses the original are not to be expected and later optimizations do not need to revert the demotion for that part. - We will generate direct accesses to the demoted values, thus there are no "trivial GEPs" that select the first element of a scalar we demoted and treated as an array. Differential Revision: http://reviews.llvm.org/D7513 llvm-svn: 238070
* Rename IslCodeGeneration to CodeGenerationTobias Grosser2015-05-121-0/+181
| | | | | | | | | Besides class, function and file names, we also change the command line option from -polly-codegen-isl to just -polly-codegen. The isl postfix is a leftover from the times when we still had the CLooG based -polly-codegen. Today it is just redundant and we drop it. llvm-svn: 237099
* Drop Cloog supportJohannes Doerfert2014-12-021-1107/+0
| | | | | | | | | This commit drops the Cloog support for Polly. The scripts and documentation are changed to only use isl as prerequisity. In the code all Cloog specific parts have been removed and all relevant tests have been ported to the isl backend when it was created. llvm-svn: 223141
* Remove -polly-codegen-scev option and related codeTobias Grosser2014-11-301-10/+0
| | | | | | | | SCEV based code generation has been the default for two weeks after having been tested for a long time. We now drop the support the non-scev-based code generation. llvm-svn: 222978
* Use nullptr instead of '0' for pointersTobias Grosser2014-11-141-1/+1
| | | | llvm-svn: 221982
* Use braces in multi-statement DEBUG() code [NFC]Tobias Grosser2014-10-221-1/+1
| | | | | | | | | | | | | | | | | | By adding braces into the DEBUG statement we can make clang-format format code such as: DEBUG(stmt1(); stmt2()) as multi-line code: DEBUG({ stmt1(); stmt2(); }); This makes control-flow in debug statements easier to read. llvm-svn: 220441
* [Refactor] Generalize parallel code generationJohannes Doerfert2014-10-031-6/+11
| | | | | | | | | | | | | + Generalized function names and comments + Removed OpenMP (omp) from the names and comments + Use common names (non OpenMP specific) for runtime library call creation methodes + Commented the parallel code generator and all its member functions + Refactored some values and methodes Differential Revision: http://reviews.llvm.org/D4990 llvm-svn: 219003
* [Refactor] Cleanup isl code generationJohannes Doerfert2014-09-101-1/+2
| | | | | | | | | | | | | | | | | | | | Summary: + Refactor the runtime check (RTC) build function + Added helper function to create an PollyIRBuilder + Change the simplify region function to create not only unique entry and exit edges but also enfore that the entry edge is unconditional + Cleaned the IslCodeGeneration runOnScop function: - less post-creation changes of the created IR + Adjusted and added test cases Reviewers: grosser, sebpop, simbuerg, dpeixott Subscribers: llvm-commits, #polly Differential Revision: http://reviews.llvm.org/D5076 llvm-svn: 217508
* Use "const auto &" in range based for loopsTobias Grosser2014-09-101-5/+5
| | | | | | | This previous code added in r216842 most likely created unnecessary copies. Reported-by: Duncan P. N. Exon Smith <dexonsmith@apple.com> llvm-svn: 217507
* Fix formattingTobias Grosser2014-08-311-1/+1
| | | | llvm-svn: 216844
* Use range based for loopsTobias Grosser2014-08-311-32/+19
| | | | llvm-svn: 216842
* Revert "[Refactor] Cleanup runtime code generation"Tobias Grosser2014-08-161-2/+1
| | | | | | | | | | | | | | | | This reverts commit 215466 (and 215528, a trivial formatting fix). The intention of these commits is a good one, but unfortunately they broke our LNT buildbot: http://lab.llvm.org:8011/builders/perf-x86_64-penryn-O3-polly-codegen-isl Several of the cleanup changes that have been combined in this 'fixup' are trivial and could probably be committed as obvious changes without risking to break the build. The remaining changes are little and it should be easy to figure out what went wrong. llvm-svn: 215817
* [Refactor] Cleanup runtime code generationJohannes Doerfert2014-08-121-1/+2
| | | | | | | + Use regexp in two test case. + Refactor the runtime condition build function llvm-svn: 215466
* [Fix] Broken build after r215121Johannes Doerfert2014-08-081-6/+14
| | | | llvm-svn: 215183
* [Refactor] Use non-const MemoryAccess base addressesJohannes Doerfert2014-07-291-1/+1
| | | | llvm-svn: 214168
* Replace the dependences parallelism check by the IslAst oneJohannes Doerfert2014-07-281-2/+24
| | | | llvm-svn: 214061
* Update for RegionInfo changes.Matt Arsenault2014-07-191-3/+3
| | | | | | | Mostly related to missing includes and renaming of the pass to RegionInfoPass. llvm-svn: 213457
* clang-format polly to avoid buildbot noiseTobias Grosser2014-07-091-9/+9
| | | | llvm-svn: 212609
* [C++11] Use more range based forsTobias Grosser2014-06-281-8/+2
| | | | llvm-svn: 211981
* Update for ScopStmt iterator name change in LLVM r210927Tobias Grosser2014-06-191-7/+4
| | | | | Contributed-by: Yabin Hu <yabin.hwu@gmail.com> llvm-svn: 211280
* Remove unnecessary explicit typing in std::make_pairTobias Grosser2014-05-071-1/+1
| | | | | Contributed-by: Yabin Hu <yabin.hwu@gmail.com> llvm-svn: 208181
* Add the missing 'LoopToScev' parameterTobias Grosser2014-05-071-1/+1
| | | | | Contributed-by: Yabin Hu <yabin.hwu@gmail.com> llvm-svn: 208180
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-1/+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
OpenPOWER on IntegriCloud