summaryrefslogtreecommitdiffstats
path: root/polly/lib/CodeGen/CodeGeneration.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [Polly CodeGen] Break critical edge from RTC to original loop.Eli Friedman2016-11-021-2/+3
| | | | | | | | | | | | | | | This makes polly generate a CFG which is closer to what we want in LLVM IR, with a loop preheader for the original loop. This is just a cleanup, but it exposes some fragile assumptions. I'm not completely happy with the changes related to expandCodeFor; RTCBB->getTerminator() is basically a random insertion point which happens to work due to the way we generate runtime checks. I'm not sure what the right answer looks like, though. Differential Revision: https://reviews.llvm.org/D26053 llvm-svn: 285864
* 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
* [IslNodeBuilder] Move run-time check generation to NodeBuilder [NFC]Tobias Grosser2016-08-081-22/+1
| | | | | | | This improves the structure of the code and allows us to reuse the runtime code generation in the PPCGCodeGeneration. llvm-svn: 278017
* [CodeGeneration] Do not set insert position redundantlyTobias Grosser2016-08-081-1/+0
| | | | | | | | There is no need to reset the position of the builder, as we can just continue to insert code at the current position of the IRBuilder, which happens to be precisely the location we reset the builder to. llvm-svn: 278014
* Extend the jscop interface to allow the user to declare new arrays and to ↵Roman Gareev2016-07-301-0/+1
| | | | | | | | | | | | | | | | reference these arrays from access expressions Extend the jscop interface to allow the user to export arrays. It is required that already existing arrays of the list of arrays correspond to arrays of the SCoP. Each array that is appended to the list will be newly created. Furthermore, we allow the user to modify access expressions to reference any array in case it has the same element type. Reviewed-by: Tobias Grosser <tobias@grosser.es> Differential Revision: https://reviews.llvm.org/D22828 llvm-svn: 277263
* IslNodeBuilder: Make finalize() virtualTobias Grosser2016-07-251-2/+1
| | | | | | | | This allows the finalization routine of the IslNodeBuilder to be overwritten by derived classes. Being here, we also drop the unnecessary 'Scop' postfix and the unnecessary 'Scop' parameter. llvm-svn: 276622
* clang-tidy: Add llvm namespace commentsTobias Grosser2016-06-231-1/+1
| | | | | | | | | | | | | | | | | | | | | | | llvm commonly adds a comment to the closing brace of a namespace to indicate which namespace is closed. clang-tidy provides with llvm-namespace-comment a handy tool to check for this habit. We use it to ensure we consitently use namespace comments in Polly. There are slightly different styles in how namespaces are closed in LLVM. As there is no large difference between the different comment styles we go for the style clang-tidy suggests by default. To reproduce this fix run: for i in `ls tools/polly/lib/*/*.cpp`; \ clang-tidy -checks='-*,llvm-namespace-comment' -p build $i -fix \ -header-filter=".*"; \ done 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: 273621
* This reverts recent expression type changesTobias Grosser2016-06-111-6/+4
| | | | | | | | | | | | | | | | | | | | | The recent expression type changes still need more discussion, which will happen on phabricator or on the mailing list. The precise list of commits reverted are: - "Refactor division generation code" - "[NFC] Generate runtime checks after the SCoP" - "[FIX] Determine insertion point during SCEV expansion" - "Look through IntToPtr & PtrToInt instructions" - "Use minimal types for generated expressions" - "Temporarily promote values to i64 again" - "[NFC] Avoid unnecessary comparison for min/max expressions" - "[Polly] Fix -Wunused-variable warnings (NFC)" - "[NFC] Simplify min/max expression generation" - "Simplify the type adjustment in the IslExprBuilder" Some of them are just reverted as we would otherwise get conflicts. I will try to re-commit them if possible. llvm-svn: 272483
* [NFC] Generate runtime checks after the SCoPJohannes Doerfert2016-06-061-4/+6
| | | | | | | | | We now generate runtime checks __after__ the SCoP code generation and not before, though they are still inserted at the same position int the code. This allows to modify the runtime check during SCoP code generation. llvm-svn: 271894
* [NFC] Simplify codeJohannes Doerfert2016-06-061-2/+2
| | | | llvm-svn: 271889
* Decouple SCoP building logic from passJohannes Doerfert2016-05-311-2/+2
| | | | | | | | | | | | | | | | Created a new pass ScopInfoRegionPass. As name suggests, it is a region pass and it is there to preserve compatibility with our existing Polly passes. ScopInfoRegionPass will return a SCoP object for a valid region while the creation of the SCoP stays in the ScopInfo class. Contributed-by: Utpal Bora <cs14mtech11017@iith.ac.in> Reviewed-by: Tobias Grosser <tobias@grosser.es>, Johannes Doerfert <doerfert@cs.uni-saarland.de> Differential Revision: http://reviews.llvm.org/D20770 llvm-svn: 271259
* Duplicate part of the Region interface in the Scop class [NFC]Johannes Doerfert2016-05-231-2/+2
| | | | | | | This allows to use the SCoP directly for various queries, thus to hide the underlying region more often. llvm-svn: 270426
* Directly access information through the Scop class [NFC]Johannes Doerfert2016-05-231-1/+1
| | | | llvm-svn: 270421
* Check overflows in RTCs and bail accordinglyJohannes Doerfert2016-05-121-1/+8
| | | | | | | | | | | | | | | We utilize assumptions on the input to model IR in polyhedral world. To verify these assumptions we version the code and guard it with a runtime-check (RTC). However, since the RTCs are themselves generated from the polyhedral representation we generate them under the same assumptions that they should verify. In other words, the guarantees that we try to provide with the RTCs do not hold for the RTCs themselves. To this end it is necessary to employ a different check for the RTCs that will verify the assumptions did hold for them too. Differential Revision: http://reviews.llvm.org/D20165 llvm-svn: 269299
* 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
OpenPOWER on IntegriCloud