summaryrefslogtreecommitdiffstats
path: root/polly/lib/Support
Commit message (Collapse)AuthorAgeFilesLines
* Generalize the pass registration mechanism used by Polly to any third-party toolserge_sans_paille2020-01-021-5/+20
| | | | | | | | | | | | | | | | | | | | | | | | There's quite a lot of references to Polly in the LLVM CMake codebase. However the registration pattern used by Polly could be useful to other external projects: thanks to that mechanism it would be possible to develop LLVM extension without touching the LLVM code base. This patch has two effects: 1. Remove all code specific to Polly in the llvm/clang codebase, replaicing it with a generic mechanism 2. Provide a generic mechanism to register compiler extensions. A compiler extension is similar to a pass plugin, with the notable difference that the compiler extension can be configured to be built dynamically (like plugins) or statically (like regular passes). As a result, people willing to add extra passes to clang/opt can do it using a separate code repo, but still have their pass be linked in clang/opt as built-in passes. Differential Revision: https://reviews.llvm.org/D61446
* Add missing includes needed to prune LLVMContext.h include, NFCReid Kleckner2019-11-141-0/+1
| | | | | These are a pre-requisite to removing #include "llvm/Support/Options.h" from LLVMContext.h: https://reviews.llvm.org/D70280
* Rename F_{None,Text,Append} to OF_{None,Text,Append}. NFCFangrui Song2019-08-051-1/+1
| | | | | | F_{None,Text,Append} are kept for compatibility since r334221. llvm-svn: 367800
* [NFC][ScopBuilder] Move buildSchedule and its callees to ScopBuilder or ↵Dominik Adamski2019-07-171-0/+74
| | | | | | | | | | | | | | | | | | ScopHelper Scope of changes: 1. Moved buildSchedule functions to ScopBuilder. 2. Moved combineInSequence function to ScopBuilder. 3. Moved mapToDimension function to ScopBuilder. 4. Moved LoopStackTy to ScopBuilder. 5. Moved getLoopSurroundingScop to ScopHelper. 6. Moved getNumBlocksInLoop to ScopHelper. 7. Moved getNumBlocksInRegionNode to ScopHelper. 8. Moved getRegionNodeLoop to ScopHelper. Differential Revision: https://reviews.llvm.org/D64223 llvm-svn: 366377
* [ZoneAlgo] Fix PHI inconsistency in invalid contexts.Michael Kruse2019-05-101-0/+6
| | | | | | | | | | PHI nodes (reads) could point to multiple instances of predecessor blocks (PHI writes) when in an invalid context. Fix by removing PHI instances that are in an invalid or ouside assumed context. This fixes llvm.org/PR41656. llvm-svn: 360454
* [polly][SCEV] Expand SCEV matcher cases for new smin/umin opsKeno Fischer2019-05-083-0/+58
| | | | | | | These were added in rL360159, but I neglected to update polly at the same time. llvm-svn: 360238
* Apply include-what-you-use #include removal suggestions. NFC.Michael Kruse2019-03-289-31/+8
| | | | | | | | | | | | This removes unused includes (and forward declarations) as suggested by include-what-you-use. If a transitive include of a removed include is required to compile a file, I added the required header (or forward declaration if suggested by include-what-you-use). This should reduce compilation time and reduce the number of iterative recompilations when a header was changed. llvm-svn: 357209
* Moving ManagedMemoryRewritePass when hybrid option is selectedMichael Kruse2019-03-251-4/+7
| | | | | | | | | | | | | | | Compiling with -polly-target=hybrid was causing Polly to occur two times in the pipeline. The reason was how the ManagedMemoryRewritePass was registered in the pass manager. ManagedMemoryRewritePass being a ModulePass was forcing all previous passes to get recomputed. This commit avoids Polly to appear two times in the pipeline registering the ManagedMemoryRewritePass later in the pass manager. Patch by Lorenzo Chelini <l.chelini@icloud.com> Differential Revision: https://reviews.llvm.org/D59263 llvm-svn: 356965
* Update the file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-198-32/+24
| | | | | | | | | | | | | | | | | to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351636
* [polly] Change to range-based invocation of llvm::sortMandeep Singh Grang2019-01-181-1/+1
| | | | llvm-svn: 351502
* [TI removal] Make `getTerminator()` return a generic `Instruction`.Chandler Carruth2018-10-151-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | This removes the primary remaining API producing `TerminatorInst` which will reduce the rate at which code is introduced trying to use it and generally make it much easier to remove the remaining APIs across the codebase. Also clean up some of the stragglers that the previous mechanical update of variables missed. Users of LLVM and out-of-tree code generally will need to update any explicit variable types to handle this. Replacing `TerminatorInst` with `Instruction` (or `auto`) almost always works. Most of these edits were made in prior commits using the perl one-liner: ``` perl -i -ple 's/TerminatorInst(\b.* = .*getTerminator\(\))/Instruction\1/g' ``` This also my break some rare use cases where people overload for both `Instruction` and `TerminatorInst`, but these should be easily fixed by removing the `TerminatorInst` overload. llvm-svn: 344504
* [IR] Replace `isa<TerminatorInst>` with `isTerminator()`.Chandler Carruth2018-08-261-1/+1
| | | | | | | | | | | | This is a bit awkward in a handful of places where we didn't even have an instruction and now we have to see if we can build one. But on the whole, this seems like a win and at worst a reasonable cost for removing `TerminatorInst`. All of this is part of the removal of `TerminatorInst` from the `Instruction` type hierarchy. llvm-svn: 340701
* Update isl-cpp bindingsTobias Grosser2018-08-091-1/+1
| | | | | | | | | We upstreamed the export of isl_val_2exp, to the official cpp bindings. In this process, we concluded that pow2 is a better and more widely used name for this functionality. Hence, both the official isl-cpp bindings and our derived variant use now the term pow2. llvm-svn: 339312
* Rebase C++ bindings on top of latest isl bindingsTobias Grosser2018-08-011-34/+39
| | | | | | | | | | | | | | | | | | | | | | The main difference in this change is that isl_stat is now always checked by default. As we elminiated most used of isl_stat, thanks to Philip Pfaffe's implementation of foreach, only a small set of changes is needed. This change does not include the following recent changes to isl's C++ bindings: - stricter error handling for isl_bool - dropping of the isl::namespace qualifiers The former requires a larger patch in Polly and consequently should go through a patch-review. The latter will be applied in the next commit to keep this commit free from noise. We also still apply a couple of other changes on top of the official isl bindings. This delta is expected to shrink over time. llvm-svn: 338504
* Translate a couple of foreach callbacks into range-based iterator loopsTobias Grosser2018-06-291-38/+25
| | | | | | | Thanks to Philip Pfaffe for providing iterator support in the previous commit. llvm-svn: 335970
* [ScopHelper] Provide support for recognising collective invariant loadsPhilip Pfaffe2018-06-291-1/+32
| | | | | | | | | | | | | | Summary: This patch aims to provide support for detecting load patterns which are collectively invariant but right now `isHoistableLoad()` is checking each load instruction individually which cannot detect the load pattern as a whole. Patch by: Sahil Girish Yerawar Reviewers: bollu, philip.pfaffe, Meinersbur Reviewed By: philip.pfaffe, Meinersbur Differential Revision: https://reviews.llvm.org/D48026 llvm-svn: 335949
* [ScopHelper] Cache ScopExpander results.Eli Friedman2018-06-271-0/+12
| | | | | | | | | | | | | | | | | | | The number of SCEV expressions is usually linear in the number of IR instructions being modeled. However, a naive SCEV visitor is not. For an expression like x*x, "x" will be visited twice. If x is itself an expression like x*x, that will be visited twice, etc, and the overall runtime is O(2^N) in the number of SCEV expressions. To prevent this from happening, add a cache, so we only visit each SCEV expression once. Not sure this is the best solution. Maybe we can instead check whether the SCEV is scop-invariant (in which case we never need to map the value). But we don't have a utility for that at the moment. Differential Revision: https://reviews.llvm.org/D47087 llvm-svn: 335783
* Drop unnecessary whitespace [NFCI]Tobias Grosser2018-06-111-2/+2
| | | | llvm-svn: 334413
* [polly] Drop nonexistant LLVM_PLUGIN_EXPORT macro from llvmGetPassPluginInfo()Roman Lebedev2018-05-191-1/+1
| | | | | | | | | | | | Fixes build: /build/polly/lib/Support/RegisterPasses.cpp:709:80: error: expected ';' after top level declarator extern "C" ::llvm::PassPluginLibraryInfo LLVM_ATTRIBUTE_WEAK LLVM_PLUGIN_EXPORT ^ ; Was missed in rL332796 / D47082 llvm-svn: 332814
* [SCEVAffinator] BB can be null; don't use it to get the LLVMContext.Eli Friedman2018-05-181-1/+1
| | | | | | Fixes post-commit review comment on r332309. llvm-svn: 332775
* [DeLICM] Avoid assertion on out-of-quota.Michael Kruse2018-05-161-0/+4
| | | | | | | | | | An assertion was not prepared to be passed a nullptr because the out-of-quota limit was exceeded. Bail-out before the assertion since the assertion does not apply on out-of-quote. This fixes llvm.org/PR37477. llvm-svn: 332488
* [polly] Update uses of DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-152-20/+23
| | | | | | | | | | | The DEBUG() macro is very generic so it might clash with other projects. The renaming was done as follows: - git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g' - git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM Differential Revision: https://reviews.llvm.org/D44978 llvm-svn: 332352
* [SCEVAffinator] Fix handling of pwaff complexity limit.Eli Friedman2018-05-141-3/+11
| | | | | | | | | | | nullptr is not a valid affine expression, and none of the callers check for null, so we eventually hit an isl error and crash. Instead, invalidate the scop and return a constant zero. Differential Revision: https://reviews.llvm.org/D46445 llvm-svn: 332309
* Remove another set or release() callsTobias Grosser2018-04-291-6/+6
| | | | llvm-svn: 331129
* Remove the last uses of isl::give and isl::takeTobias Grosser2018-04-292-176/+151
| | | | llvm-svn: 331126
* Allow arbitrary function calls for debugging purposes.Michael Kruse2018-04-201-0/+52
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Add the switch -polly-debug-func to define the name of a debug function. This function is ignored for any validity check. Its purpose is to allow to observe a value after transformation by a SCoP, and to follow which statements are executed in which order. For instance, consider the following code: static void dbg_printf(int sum, int i) { fprintf(stderr, "The value of sum is %d, i=%d\n", sum, i); fflush(stderr); } void func(int n) { int sum = 0; for (int i = 0; i < 16; i+=1) { sum += i; dbg_printf(sum, i); } } Executing this after Polly's codegen with -polly-debug-func=dbg_printf reveals the new execution order and the assumed values at that point of execution. Differential Revision: https://reviews.llvm.org/D45728 llvm-svn: 330466
* [NewPM] Update pass registration for the LLVM plugin interfacePhilip Pfaffe2018-04-171-0/+8
| | | | | | | | | | | | | | | | Summary: As of rL329273, LLVM has a mechanism to load new-pm plugins in opt. Use this API in Polly. Reviewers: grosser, Meinersbur, bollu Reviewed By: grosser, Meinersbur Subscribers: lksbhm, bollu, pollydev, llvm-commits Differential Revision: https://reviews.llvm.org/D45484 llvm-svn: 330181
* Revert r327216 'Add isl operator overloads for isl::pw_aff'Tobias Grosser2018-04-111-1/+0
| | | | | | This commit requires further discussions. llvm-svn: 329825
* Remove immediate dominator heuristic for error block detection.Michael Kruse2018-04-091-19/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch removes the heuristic in - Polly :: lib/Support/ScopHelper.cpp The heuristic forces blocks that directly follow a loop header to not to be considered error blocks. It was introduced in r249611 with the following commit message: > This replaces the support for user defined error functions by a > heuristic that tries to determine if a call to a non-pure function > should be considered "an error". If so the block is assumed not to be > executed at runtime. While treating all non-pure function calls as > errors will allow a lot more regions to be analyzed, it will also > cause us to dismiss a lot again due to an infeasible runtime context. > This patch tries to limit that effect. A non-pure function call is > considered an error if it is executed only in conditionally with > regards to a cheap but simple heuristic. In the code below `CCK_Abort2()` would be considered as an error block, but not `CCK_Abort1()` due to this heuristic. ``` for (int i = 0; i < n; i+=1) { if (ErrorCondition1) CCK_Abort1(); // No __attribute__((noreturn)) if (ErrorCondition2) CCK_Abort2(); // No __attribute__((noreturn)) } ``` This does not seem useful. Checking error conditions in the beginning of some work is quite common. It causes a switch default-case to be not considered an error block in SPEC's cactuBSSN. The comment justifying the heuristic mentions a "load", which does not seem to be applicable here. It has been proposed to remove the heuristic. In addition, the patch fixes the following test cases: - Polly :: ScopDetect/mod_ref_read_pointer.ll - Polly :: ScopInfo/max-loop-depth.ll - Polly :: ScopInfo/mod_ref_access_pointee_arguments.ll - Polly :: ScopInfo/mod_ref_read_pointee_arguments.ll - Polly :: ScopInfo/mod_ref_read_pointer.ll - Polly :: ScopInfo/mod_ref_read_pointers.ll The test cases failed after removing the heuristic. Differential Revision: https://reviews.llvm.org/D45274 Contributed-by: Lorenzo Chelini <l.chelini@icloud.com> llvm-svn: 329548
* [polly] Change std::sort to llvm::sort in response to r327219Mandeep Singh Grang2018-03-131-1/+1
| | | | | | | | | | | | | | | | | | | | | Summary: r327219 added wrappers to std::sort which randomly shuffle the container before sorting. This will help in uncovering non-determinism caused due to undefined sorting order of objects having the same key. To make use of that infrastructure we need to invoke llvm::sort instead of std::sort. Reviewers: grosser, efriedma, jdoerfert, bollu, sebpop Reviewed By: sebpop Subscribers: sebpop, mehdi_amini, llvm-commits, pollydev Tags: #polly Differential Revision: https://reviews.llvm.org/D44361 llvm-svn: 327361
* Revert untested changes in SCEVAffinatorTobias Grosser2018-03-101-1/+1
| | | | llvm-svn: 327221
* Add isl operator overloads for isl::pw_affTobias Grosser2018-03-101-1/+3
| | | | | | | | | | | | Piecewise affine expressions have directly corresponding mathematical operators. Introduce these operators as overloads as this makes writing code with isl::pw_aff expressions more directly readable. We can now write: A = B + C instead of A = B.add(C) llvm-svn: 327216
* Use isl::manage_copy to simplify calls to isl::manage(isl_.._copy())Tobias Grosser2018-02-202-10/+9
| | | | | | | | | | | As part of this cleanup a couple of unnecessary isl::manage(obj.copy()) pattern are eliminated as well. We checked for all potential cleanups by scanning for: "grep -R isl::manage\( lib/ | grep copy" llvm-svn: 325558
* Do not call band_list().dump()Tobias Grosser2018-02-201-1/+0
| | | | | | This is in preparation for the removal of band_list from isl. llvm-svn: 325554
* [VirtualInst] Derive correct use kind of PHI operands. NFC.Michael Kruse2018-01-231-6/+26
| | | | | | | | | | VirtualUse::create is only called for MemoryKind::Value, but its consistency nonetheless checked in verifyUses(). PHI uses are always inter-stmt dependencies, which was not considered by the constructor method. The virtual and non-virtual execution paths were the same, such that verifyUses did not encounter any inconsistencies. llvm-svn: 323283
* [IslTools] dumpPw: Dump same structure pieces together.Michael Kruse2018-01-161-21/+44
| | | | | | | | | | | | | | | | | | | | | | Print same or similar structure elements together. Previously, the value could take more importance that the space structure if visited first in the space nest tree. Before: { Left[0] -> Right[i]: i >= 0; Left[1] -> AnotherRight[i]; Left[2] -> Right[-1] } After: { Left[0] -> Right[i]: i >= 0; Left[2] -> Right[-1]; Left[1] -> AnotherRight[i] } llvm-svn: 322581
* [NFC] Fix formattingPhilip Pfaffe2017-12-061-4/+2
| | | | llvm-svn: 319973
* Port SCEVAffinator to the isl c++ bindingsPhilip Pfaffe2017-12-061-107/+79
| | | | | | | | | | | | | | Summary: Straight forward port of SCEVAffinator Reviewers: grosser, bollu, Meinersbur Reviewed By: Meinersbur Subscribers: pollydev, llvm-commits Differential Revision: https://reviews.llvm.org/D40803 llvm-svn: 319958
* Handle Top-Level-Regions in polly::isHoistableLoadPhilip Pfaffe2017-11-301-3/+9
| | | | | | | | | | | | | | | | | | | | Summary: This can be seen as a follow-up on my previous differential [D33411](https://reviews.llvm.org/D33411). We received a bug report where this error was triggered. I have tried my best to recreate the issue in a minimal lit testcase which is also part of this differential. I only handle return instructions as predecessors to a virtual TLR-exit right now. From inspecting the codebase, it seems `unreachable` instructions may also be of interest here. If requested, I can extend my patches to consider them as well. I would also apply this on `ScopHelper.cpp::isErrorBlock` (see D33411), of course. Reviewers: philip.pfaffe, bollu Reviewed By: bollu Subscribers: Meinersbur, pollydev, llvm-commits Tags: #polly Differential Revision: https://reviews.llvm.org/D40492 llvm-svn: 319431
* Run polly-update-format. NFC.Michael Kruse2017-11-211-3/+6
| | | | | | | polly-check-format has been failing since at least r318517, due to more than one cause. llvm-svn: 318795
* Port ScopInfo to the isl cpp bindingsPhilip Pfaffe2017-11-191-4/+4
| | | | | | | | | | | | | | | | | | | | | Summary: Most changes are mechanical, but in one place I changed the program semantics by fixing a likely bug: In `Scop::hasFeasibleRuntimeContext()`, I'm now explicitely handling the error-case. Before, when the call to `addNonEmptyDomainConstraints()` returned a null set, this (probably) accidentally worked because isl_bool_error converts to true. I'm checking for nullptr now. Reviewers: grosser, Meinersbur, bollu Reviewed By: Meinersbur Subscribers: nemanjai, kbarton, pollydev, llvm-commits Differential Revision: https://reviews.llvm.org/D39971 llvm-svn: 318632
* [Simplify] Mark (and sweep) based on latest access relation.Michael Kruse2017-10-261-2/+2
| | | | | | | | | Previously we marked scalars based on the original access function. However, when a scalar read access is redirected, the original definition (or incoming values of a PHI) is not used anymore, and can be deleted (unless referenced by use that has not been redirected). llvm-svn: 316660
* [ISLTools] Translate computeReachingWrite to isl++. NFC.Michael Kruse2017-10-241-24/+17
| | | | llvm-svn: 316445
* [Polly] Add dumpPw() and dumpExpanded() functions. NFC.Michael Kruse2017-09-291-0/+338
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | These functions print a multi-line and sorted representation of unions of polyhedra. Each polyhedron (basic_{ast/map}) has its own line. First sort key is the polyhedron's hierachical space structure. Secondary sort key is the lower bound of the polyhedron, which should ensure that the polyhedral are printed in approximately ascending order. Example output of dumpPw(): [p_0, p_1, p_2] -> { Stmt0[0] -> [0, 0]; Stmt0[i0] -> [i0, 0] : 0 < i0 <= 5 - p_2; Stmt1[0] -> [0, 2] : p_1 = 1 and p_0 = -1; Stmt2[0] -> [0, 1] : p_1 >= 3 + p_0; Stmt3[0] -> [0, 3]; } In contrast dumpExpanded() prints each point in the sets, unless there is an unbounded dimension that cannot be expandend. This is useful for reduced test cases where the loop counts are set to some constant to understand a bug. Example output of dumpExpanded( { [MemRef_A[i0] -> [i1]] : (exists (e0 = floor((1 + i1)/3): i0 = 1 and 3e0 <= i1 and 3e0 >= -1 + i1 and i1 >= 15 and i1 <= 25)) or (exists (e0 = floor((i1)/3): i0 = 0 and 3e0 < i1 and 3e0 >= -2 + i1 and i1 > 0 and i1 <= 11)) }): { [MemRef_A[0] ->[1]]; [MemRef_A[0] ->[2]]; [MemRef_A[0] ->[4]]; [MemRef_A[0] ->[5]]; [MemRef_A[0] ->[7]]; [MemRef_A[0] ->[8]]; [MemRef_A[0] ->[10]]; [MemRef_A[0] ->[11]]; [MemRef_A[1] ->[15]]; [MemRef_A[1] ->[16]]; [MemRef_A[1] ->[18]]; [MemRef_A[1] ->[19]]; [MemRef_A[1] ->[21]]; [MemRef_A[1] ->[22]]; [MemRef_A[1] ->[24]]; [MemRef_A[1] ->[25]] } Differential Revision: https://reviews.llvm.org/D38349 llvm-svn: 314525
* [Support] Force instantiation of isl dump() methods. NFC.Michael Kruse2017-09-281-0/+57
| | | | | | | | | | | | | | | | In order for debuggers to be able to call an inline method, it must have been instantiated somewhere. The dump() methods are usually not used, so add an instantiation in debug builds. This allows to call .dump() on any isl++ object from the gcc/gdb and Visual Studio debugger in debug builds with assertions enabled. In optimized builds, even with assertions enabled, the dump() methods are also inlined in GICHelper.cpp, so no externally visible symbols will be available either. Differential Revision: https://reviews.llvm.org/D38198 llvm-svn: 314395
* [ScopInfo] Allow uniform branch conditionsTobias Grosser2017-09-251-0/+14
| | | | | | | If all but one branch come from an error condition and the incoming value from this branch is a constant, we can model this branch. llvm-svn: 314116
* [ScopDetect/Info] Look through PHIs that follow an error blockTobias Grosser2017-09-241-0/+27
| | | | | | | | | | | In case a PHI node follows an error block we can assume that the incoming value can only come from the node that is not an error block. As a result, conditions that seemed non-affine before are now in fact affine. This is a recommit of r312663 after fixing test/Isl/CodeGen/phi_after_error_block_outside_of_scop.ll llvm-svn: 314075
* [Support] Rename tool_output_file to ToolOutputFile, NFCReid Kleckner2017-09-231-2/+2
| | | | | | | This class isn't similar to anything from the STL, so it shouldn't use the STL naming conventions. llvm-svn: 314050
* Revert "[ScopDetect/Info] Look through PHIs that follow an error block"Michael Kruse2017-09-061-26/+0
| | | | | | | | | | This reverts commit r312410 - [ScopDetect/Info] Look through PHIs that follow an error block The commit caused generation of invalid IR due to accessing a parameter that does not dominate the SCoP. llvm-svn: 312663
* [ISLTools]: Move singleton to isl++Tobias Grosser2017-09-041-11/+9
| | | | llvm-svn: 312476
OpenPOWER on IntegriCloud