summaryrefslogtreecommitdiffstats
path: root/polly/lib
Commit message (Collapse)AuthorAgeFilesLines
...
* Move MemoryAccess::createBasicAccessMap to isl++Tobias Grosser2017-07-231-8/+8
| | | | llvm-svn: 308837
* Move MemoryAccess::id to isl++Tobias Grosser2017-07-235-64/+69
| | | | llvm-svn: 308836
* [Simplify] Remove partial write accesses with empty domain.Michael Kruse2017-07-221-2/+40
| | | | | | | | | | | If the access relation's domain is empty, the access will never be executed. We can just remove it. We only remove write accesses. Partial read accesses are not yet supported and instructions in the statement might require the llvm::Value holding the read's result to be defined. llvm-svn: 308830
* [ScopInfo] Adapt indentation of instruction list printing.Michael Kruse2017-07-221-1/+1
| | | | | | | | | | | | | | | | | | | | Change the indention of the last brace to align with the opening line. Before: Instructions { %val = fadd double %arg, 2.100000e+01 store double %val, double* %A } After: Instructions { %val = fadd double %arg, 2.100000e+01 store double %val, double* %A } llvm-svn: 308828
* [ForwardOpTree] Support hoisted invariant loads.Michael Kruse2017-07-221-5/+1
| | | | | | | | Hoisted loads can be trivially supported because there are no MemoryAccess to be modified, the loaded value is just available at code generation. llvm-svn: 308826
* [ForwardOpTree] Introduce the -polly-optree pass.Michael Kruse2017-07-223-0/+366
| | | | | | | | | | | | | | | | | | This pass 'forwards' operand trees into statements that use them in order to avoid scalar dependencies. This minimal implementation handles only the case of speculatable instructions. We will successively add support for: - Hoisted loads - Read-only values - Synthesizable values - Loads - PHIs - Forwarding only parts of the tree Differential Revision: https://reviews.llvm.org/D35754 llvm-svn: 308825
* Move ScopArrayInfo to isl++Tobias Grosser2017-07-215-50/+45
| | | | | | This moves the full ScopArrayInfo class to isl++ llvm-svn: 308801
* [Polly][GPGPU] Added SPIR Code Generation and Corresponding Runtime Support ↵Philipp Schaad2017-07-212-12/+163
| | | | | | | | | | | | | | | | | | | | | | | | | | | for Intel Summary: Added SPIR Code Generation to the PPCG Code Generator. This can be invoked using the polly-gpu-arch flag value 'spir32' or 'spir64' for 32 and 64 bit code respectively. In addition to that, runtime support has been added to execute said SPIR code on Intel GPU's, where the system is equipped with Intel's open source driver Beignet (development version). This requires the cmake flag 'USE_INTEL_OCL' to be turned on, and the polly-gpu-runtime flag value to be 'libopencl'. The transformation of LLVM IR to SPIR is currently quite a hack, consisting in part of regex string transformations. Has been tested (working) with Polybench 3.2 on an Intel i7-5500U (integrated graphics chip). Reviewers: bollu, grosser, Meinersbur, singam-sanjay Reviewed By: grosser, singam-sanjay Subscribers: pollydev, nemanjai, mgorny, Anastasia, kbarton Tags: #polly Differential Revision: https://reviews.llvm.org/D35185 llvm-svn: 308751
* Annotate dump() functions with LLVM_DUMP_METHOD. NFC.Michael Kruse2017-07-212-6/+6
| | | | llvm-svn: 308749
* [ScopInfo] Don't compile dump() functions into non-assert builds. NFC.Michael Kruse2017-07-211-0/+8
| | | | | | This follows a convention used in LLVM. llvm-svn: 308748
* [ScopInfo] Print instructions in dump().Michael Kruse2017-07-217-19/+31
| | | | | | | | | | | | | | | | | | | Print a statement's instruction on dump() regardless of -polly-print-instructions. dump() is supposed to be used in the debugger only and never in regression tests. While debugging, get all the information we have and we are not bound to break anything. For non-dump purposes of print, forward the setting of -polly-print-instructions as parameters. Some calls to print() had to be changed because the PollyPrintInstructions setting is only available in ScopInfo.cpp. In ScheduleOptimizer.cpp, dump() was used in regression tests. That's not what dump() is for. The print parameter "PrintInstructions" will also be useful for an explicit print SCoP pass in a future patch. llvm-svn: 308746
* [NFC] [RegisterPasses] Fix typo: To early -> too early.Siddharth Bhat2017-07-211-1/+1
| | | | llvm-svn: 308743
* [NFC] [PPCGCodeGeneration] Print `verifyModule` failure to debug stream.Siddharth Bhat2017-07-211-0/+2
| | | | | | | If verifyModule fails, it is helpful to know why it failed. Add a log to the debug stream that prints the failure. llvm-svn: 308727
* Fix typo in function name Bllock -> BlockTobias Grosser2017-07-211-3/+3
| | | | llvm-svn: 308715
* [IslNodeBuilder] Relax complexity check in invariant loads and run it earlyTobias Grosser2017-07-202-23/+38
| | | | | | | | | | | | | | | | | | | | | | | | When performing invariant load hoisting we check that invariant load expressions are not too complex. Up to this commit, we performed this check by counting the sum of dimensions in the access range as a very simple heuristic. This heuristic is a little too conservative, as it prevents hoisting for any scops with a very large number of parameters. Hence, we update the heuristic to only count existentially quantified dimensions and set dimensions. We expect this to still detect the problematic expressions in h264 because of which this check was originally introduced. For some unknown reason, this complexity check was originally committed in IslNodeBuilder. It really belongs in ScopInfo, as there is no point in optimizing a program which we could have known earlier cannot be code generated. The benefit of running the check early is that we can avoid to even hoist checks that are expensive to code generate as invariant loads. This can be seen in the changed tests, where we now indeed detect the scop, but just not invariant load hoist the complicated access. We also improve the formatting of the code, document it, and use isl++ to simplify expressions. llvm-svn: 308659
* Support fabs and copysign in Polly-ACCTobias Grosser2017-07-201-2/+6
| | | | llvm-svn: 308649
* [PPCG] Compile fix for MSVC.Michael Kruse2017-07-201-4/+4
| | | | | | | | | Visual Studio, even the 2017 version, does not support C99 VLAs. For VLA paramters, the length of the outermost dimension is not required anyway, so remove it. llvm-svn: 308643
* [ScopInfo] Get a list of statements for a region node. NFC.Michael Kruse2017-07-201-8/+6
| | | | | | | | | | | When constructing a schedule true and there are multiple statements for a basic block, create a sequence node for these statements. Contributed-by: Nandini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D35679 llvm-svn: 308635
* [ScopInfo] Remove dependency of Scop::getLastStmtFor(BB) on getStmtFor(BB). NFC.Michael Kruse2017-07-201-0/+16
| | | | | | | | | | | | | We are working towards removing uses of Scop::getStmtFor(BB). In this patch, we remove dependency of Scop::getLastStmtFor(BB) on getStmtFor(BB). To do so, we get the list of all statements corresponding to the BB and then fetch the last one. Contributed-by: Nandini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D35665 llvm-svn: 308633
* [ScopInfo] Use map for lookupPHIReadOf. NFC.Michael Kruse2017-07-201-13/+10
| | | | | | | | | | | | | Introduce previously missing PHIReads analogous the the already existing PHIWrites/ValueWrites/ValueReads maps. PHIReads was initially not required and the later introduced lookupPHIReadOf() used a linear search instead. With PHIReads, lookupPHIReadOf() can now also do a map lookup and remove any surprising performance/behaviour differences to lookupPHIWriteOf(), lookupValueWriteOf() and lookupValueReadOf(). llvm-svn: 308630
* [Simplify] Remove unused instructions and accesses.Michael Kruse2017-07-203-1/+351
| | | | | | | | | | | | | | | | | | | | | | | | | | Use a mark-and-sweep algorithm to find and remove unused instructions and MemoryAccesses. This is useful in particular to remove scalar writes that are never used anywhere. A scalar write in a loop induces a write-after-write dependency that stops the loop iterations to be rescheduled. Such writes can be a result of previous transformations such as DeLICM and operand tree forwarding. It adds a new class VirtualInstruction that represents an instruction in a particular statement. At the moment an instruction can only belong to the statement that represents a BasicBlock. In the future, instructions can be in one of multiple statements representing a BasicBlock (Nandini's work), in different statements than its BasicBlock would indicate, and even multiple statements at once (by forwarding operand trees). It also integrates nicely with the VirtualUse class. ScopStmt::contains(Instruction*) currently uses the instruction's parent BasicBlock to check whether it contains the instruction. It will need to check the actual statement list when one of the aforementioned features become possible. Differential Revision: https://reviews.llvm.org/D35656 llvm-svn: 308626
* [PPCGCodeGen] [3/3] Update PPCGCodeGen + tests to latest ppcg.Siddharth Bhat2017-07-201-20/+77
| | | | | | | | | | | | | | | | | | | | | This commit *WILL COMPILE*. 1. `PPCG` now uses `isl_multi_pw_aff` instead of an array of `pw_aff`. This needs us to adjust how we index array bounds and how we construct array bounds. 2. `PPCG` introduces two new kinds of nodes: `init_device` and `clear_device`. We should investigate what the correct way to handle these are. 3. `PPCG` has gotten smarter with its use of live range reordering, so some of the tests have a qualitative improvement. 4. `PPCG` changed its output style, so many test cases need to be updated to fit the new style for `polly-acc-dump-code` checks. Differential Revision: https://reviews.llvm.org/D35677 llvm-svn: 308625
* [PPCG] [2/3] Make polly specific PPCG Changes.Siddharth Bhat2017-07-209-1386/+129
| | | | | | | | | | | | | | | - This commit *WILL NOT COMPILE*. `PPCGCodeGeneration` requires changes since some of PPCG's internal data structures have been modified. - Has polly-speific changes to PPCG. Polly exports certain functionality that is private to PPCG. It also creates stubs for large parts of the pet API as well as other functions in `ppcg/external.c` to keep the linker happy. - This commit includes changes to CMakeLists.txt. Differential Revision: https://reviews.llvm.org/D35676 llvm-svn: 308624
* [PPCG] [1/3] Bump up PPCG version to 0.07.Siddharth Bhat2017-07-2040-1224/+6113
| | | | | | | | | | - This commit *WILL NOT COMPILE*, as it checks in vanilla PPCG 0.07 - We choose to introduce this commit into the history to cleanly display the Polly-specific changes made to PPCG. Differential Revision: https://reviews.llvm.org/D35675 llvm-svn: 308623
* [ScopBuilder] Avoid use of getStmtFor(BB). NFC.Michael Kruse2017-07-201-4/+4
| | | | | | | | | | | | | Since there will be no more a 1:1 correspondence between statements and basic blocks, we would like to get rid of the method getStmtFor(BB) and its uses. Here we remove one of its uses in ScopBuilder by fetching the statement in which the instruction lies. Contributed-by: Nandini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D35610 llvm-svn: 308610
* [ScopInfo] Add support for wrap-around of integers in unsigned comparisons.Michael Kruse2017-07-201-6/+72
| | | | | | | | | | | | | | | | | | | | | | | | This is one possible solution to implement wrap-arounds for integers in unsigned icmp operations. For example, store i32 -1, i32* %A_addr %0 = load i32, i32* %A_addr %1 = icmp ult i32 %0, 0 %1 should hold false, because under the assumption of unsigned integers, -1 should wrap around to 2^32-1. However, previously. it was assumed that the MSB (Most Significant Bit - aka the Sign bit) was never set for integers in unsigned operations. This patch modifies the buildConditionSets function in ScopInfo.cpp to give better information about the integers in these unsigned comparisons. Contributed-by: Annanay Agarwal <cs14btech11001@iith.ac.in> Differential Revision: https://reviews.llvm.org/D35464 llvm-svn: 308608
* Make byref llvm::Use parameters const. NFC.Michael Kruse2017-07-192-2/+3
| | | | llvm-svn: 308522
* [ScopInfo] Integrate ScalarDefUseChain into polly::Scop. NFC.Michael Kruse2017-07-192-114/+84
| | | | | | | | | | | | | | | | | | | Before this patch, ScalarDefUseChain was a tool used by DeLICM to find all reads and writes of scalar accesses. It iterated once over all accesses and stores the accesses into maps. By integrating it into the Scop class, we can keep the maps up-to-date without the need for recomputing them. It will be needed for more than DeLICM in the future, such as SCoP simplification, code movement between virtual statements, and array expansion (GSoC project). Compared to ScalarUseDefChain, we save two maps by finding the ScopStmt a Def/PHIRead must reside in, and use its already existing lookup function to find the MemoryAccess. Differential Revision: https://reviews.llvm.org/D35631 llvm-svn: 308495
* Make the pattern matching work with modified memory accessesRoman Gareev2017-07-191-10/+10
| | | | | | | | | | | | | Some optimizations (e.g., DeLICM) can modify memory accesses (e.g., change their MemoryKind). Consequently, the pattern matching should take it into the account. Reviewed-by: Tobias Grosser <tobias@grosser.es>, Michael Kruse <llvm@meinersbur.de> Differential Revision: https://reviews.llvm.org/D33138 llvm-svn: 308494
* [ScopInfo] Do not create entries in map if non existsTobias Grosser2017-07-191-1/+1
| | | | | Suggested-by: Michael Kruse <llvm@meinersbur.de> llvm-svn: 308491
* [Simplify] Ensure all counters are reset before next SCoP is processed. NFC.Michael Kruse2017-07-191-0/+1
| | | | llvm-svn: 308473
* [ScopInfo] Introduce tryGetValueStoredTobias Grosser2017-07-191-7/+1
| | | | | | | | | | | | | | | | | | | | Summary: This makes code more readable and allows to reuse this functionality in the future at other places. Suggested-by Michael Kruse in post-commit review of r307660. Reviewers: Meinersbur, bollu, gareevroman, efriedma, huihuiz, sebpop, simbuerg Reviewed By: Meinersbur Subscribers: pollydev, llvm-commits Tags: #polly Differential Revision: https://reviews.llvm.org/D35585 llvm-svn: 308435
* [ScopInfo] Introduce list of statements in Scop::StmtMap. NFC.Michael Kruse2017-07-181-3/+4
| | | | | | | | | | | | Once statements are split, a BasicBlock will comprise of multiple statements. To prepare for this change in future, we introduce a list of statements in the statement map. Contributed-by: Nandini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D35301 llvm-svn: 308318
* [NFC] [PPCGCodeGeneration] cleanup kills related code.Siddharth Bhat2017-07-181-24/+29
| | | | | | | | We extended kills in Polly to handle both `phi` nodes and scalars that are not used within the Scop. Update the comments and choice of variable names to reflect this. llvm-svn: 308279
* [Polly] [OptDiag] Updating Polly Diagnostics RemarksEli Friedman2017-07-174-58/+207
| | | | | | | | | | | | | | | | | Utilizing newer LLVM diagnostic remark API in order to enable use of opt-viewer tool. Polly Diagnostic Remarks also now appear in YAML remark file. In this patch, I've added the OptimizationRemarkEmitter into certain classes where remarks are being emitted and update the remark emit calls itself. I also provide each remark a BasicBlock or Instruction from where it is being called, in order to compute the hotness of the remark. Patch by Tarun Rajendran! Differential Revision: https://reviews.llvm.org/D35399 llvm-svn: 308233
* [Polly] Avoid use of `getStmtFor(BB)` in PolyhedralInfo. NFCTobias Grosser2017-07-171-18/+17
| | | | | | | | | | | | | | | | Summary: Since there will be no more a 1-1 correspondence between statements and basic block, we would like to get rid of the method `getStmtFor(BB)` and its uses. Here we remove one of its uses in PolyhedralInfo, as suggested by Michael Sir. Reviewers: grosser, Meinersbur, bollu Reviewed By: grosser Subscribers: pollydev Tags: #polly Differential Revision: https://reviews.llvm.org/D35300 llvm-svn: 308220
* [ScopInfo] Simplify new access functions under domain contextTobias Grosser2017-07-171-0/+1
| | | | | | | | | | | | | | | | | | | | | | | Summary: We do not keep domain constraints on access functions when building the scop. Hence, for consistency reasons, it makes also sense to not include them when storing a new access function. This change results in simpler access functions that make output easier to read. This patch also helps to make DeLICMed memory accesses to be understood by our matrix multiplication pattern matching pass. Further changes to the matrix multiplication pattern matching are needed for this to work, so the corresponding test case will be added in a future commit. Reviewers: Meinersbur, bollu, gareevroman, efriedma, huihuiz, sebpop, simbuerg Subscribers: pollydev, llvm-commits Tags: #polly Differential Revision: https://reviews.llvm.org/D35237 llvm-svn: 308215
* [PPCGCodeGeneration] Generate invariant loads before trying to generate IR.Siddharth Bhat2017-07-171-0/+1
| | | | | | | | | - We should call `preloadInvariantLoads` to make sure that code is generated for invariant loads in the kernel. Differential Revision: https://reviews.llvm.org/D35410 llvm-svn: 308187
* ScopInfo: Remove not-in-DomainMap statements in separate functionTobias Grosser2017-07-162-18/+32
| | | | | | This separates ScopBuilder internal and ScopBuilder external functionality. llvm-svn: 308152
* Fix typo in comment [NFC]Tobias Grosser2017-07-161-1/+1
| | | | llvm-svn: 308149
* [Polly] Fix a typo [NFC]Tobias Grosser2017-07-161-2/+2
| | | | | | | | | | | | Reviewers: grosser, Meinersbur, bollu Tags: #polly Contributed-by: Nandini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D35459 llvm-svn: 308134
* [ScopDetection] If a loop is not part of a scop, none of it backedges can beTobias Grosser2017-07-152-3/+33
| | | | | | | | | | | | | | | | | | This patch makes sure that in case a loop is not fully contained within a region that later forms a SCoP, none of the loop backedges are allowed to be part of the region. We currently do not support the situation where only some of a loops backedges are part of a scop. Today, this can break both scop modeling and code generation. One such breaking test case is for example test/ScopDetectionDiagnostics/loop_partially_in_scop-2.ll, where we totally forgot to code generate some of the backedges. Fortunately, it is commonly not necessary to support these partial loops, it is way more common that either no backedge is included in a region or all loop backedge are included. This fixes a recent miscompile in MultiSource/Benchmarks/MiBench/consumer-typeset which was exposed after r306477. llvm-svn: 308113
* [Polly] Translate Scop::DomainMap to islppTobias Grosser2017-07-151-82/+64
| | | | | | | | | | | | | | Reviewers: grosser, Meinersbur, bollu Subscribers: pollydev Tags: #polly Contributed-by: Nandini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D35453 llvm-svn: 308093
* [Polly] Use Isl c++ for InvalidDomainMapTobias Grosser2017-07-152-54/+41
| | | | | | | | | | | | | | Reviewers: grosser, Meinersbur, bollu Subscribers: maxf, pollydev Tags: #polly Contributed-by: Nandini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D35308 llvm-svn: 308089
* update isl to: isl-0.18-791-ga22eb92Tobias Grosser2017-07-1412-93/+84
| | | | | | This is a regular maintenance update llvm-svn: 308013
* [PPCGCodeGeneration] Fix runtime check adjustments since they make ↵Siddharth Bhat2017-07-143-9/+14
| | | | | | | | | | | | | | | | | | | | | | | assumptions about BB layout. - There is a conditional branch that is used to switch between the old and new versions of the code. - If we detect that the build was unsuccessful, `PPCGCodeGeneration` will change the runtime check to be always set to false. - To actually *reach* this runtime check instruction, `PPCGCodeGeneration` was using assumptions about the layout of the BBs. - However, invariant load hoisting violates this assumption by inserting an extra basic block in the middle. - Fix the assumption on the layout by having `createScopConditionally` return the conditional branch instruction. - Use this reference to set to always-false. llvm-svn: 308010
* [Invariant Loads] Do not consider invariant loads to have dependences.Siddharth Bhat2017-07-135-7/+53
| | | | | | | | | | | | | | | | | We need to relax constraints on invariant loads so that they do not create fake RAW dependences. So, we do not consider invariant loads as scalar dependences in a region. During these changes, it turned out that we do not consider `llvm::Value` replacements correctly within `PPCGCodeGeneration` and `ISLNodeBuilder`. The replacements dictated by `ValueMap` were not being followed in all places. This was fixed in this commit. There is no clean way to decouple this change because this bug only seems to arise when the relaxed version of invariant load hoisting was enabled. Differential Revision: https://reviews.llvm.org/D35120 llvm-svn: 307907
* [PPCGCodeGen] Differentiate kernels based on their parent ScopSingapuram Sanjay Srivallabh2017-07-122-3/+16
| | | | | | | | | | | | | | | | | | | | | Summary: Add a sequence number that identifies a ptx_kernel's parent Scop within a function to it's name to differentiate it from other kernels produced from the same function, yet different Scops. Kernels produced from different Scops can end up having the same name. Consider a function with 2 Scops and each Scop being able to produce just one kernel. Both of these kernels have the name "kernel_0". This can lead to the wrong kernel being launched when the runtime picks a kernel from its cache based on the name alone. This patch supplements D33985, by differentiating kernels across Scops as well. Previously (even before D33985) while profiling kernels generated through JIT e.g. Julia, [[ https://groups.google.com/d/msg/polly-dev/J1j587H3-Qw/mR-jfL16BgAJ | kernels associated with different functions, and even different SCoPs within a function, would be grouped together due to the common name ]]. This patch prevents this grouping and the kernels are reported separately. Reviewers: grosser, bollu Reviewed By: grosser Subscribers: mehdi_amini, nemanjai, pollydev, kbarton Tags: #polly Differential Revision: https://reviews.llvm.org/D35176 llvm-svn: 307814
* [Simplify] Also remove redundant writes which originally came from PHI nodesTobias Grosser2017-07-111-1/+8
| | | | llvm-svn: 307660
* [Polly][CMake] Use the CMake Package instead of llvm-config in out-of-tree ↵Philip Pfaffe2017-07-111-49/+32
| | | | | | | | | | | | | | | | | | | | | | | builds Summary: As of now, Polly uses llvm-config to set up LLVM dependencies in an out-of-tree build. This is problematic for two reasons: 1) Right now, in-tree and out-of-tree builds in fact do different things. E.g., in an in-tree build, libPolly depends on a handful of LLVM libraries, while in an out-of-tree build it depends on all of them. This means that we often need to treat both paths seperately. 2) I'm specifically unhappy with the way libPolly is linked right now, because it just blindly links against all the LLVM libs. That doesn't make a lot of sense. For instance, one of these libs is LLVMTableGen, which contains a command line definition of a -o option. This means that I can not link an out-of-tree libPolly into a tool which might want to offer a -o option as well. This patch (mostly) drop the use of llvm-config in favor of LLVMs exported cmake package. However, building Polly with unittests requires access to the gtest sources (in the LLVM source tree). If we're building against an LLVM installation, this source tree is unavailable and must specified. I'm using llvm-config to provide a default in this case. Reviewers: Meinersbur, grosser Reviewed By: grosser Subscribers: tstellar, bollu, chapuni, mgorny, pollydev, llvm-commits Differential Revision: https://reviews.llvm.org/D33299 llvm-svn: 307650
OpenPOWER on IntegriCloud