summaryrefslogtreecommitdiffstats
path: root/polly/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* [ScopInfo] Move addNonEmptyDomainConstraints to isl++ [NFCI]Tobias Grosser2018-06-181-2/+2
| | | | llvm-svn: 334938
* Move buildConditionSet to C++Tobias Grosser2018-06-181-16/+21
| | | | llvm-svn: 334937
* [ScopBuilder] Slightly improve code structure [NFCI]Tobias Grosser2018-06-111-1/+2
| | | | | | | | First build the surrounding loops and then build up the polyhedral structures. Before r326664 we had to mix these updates, clean this up to improve readability (slightly). llvm-svn: 334412
* [OpTree] Introduce shortcut for computing the def->target mapping. NFCI.Michael Kruse2018-06-061-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | In case the schedule has not changed and the operand tree root uses a value defined in an ancestor loop, the def-to-target mapping is trivial. For instance, the SCoP for (int i < 0; i < N; i+=1) { DefStmt: D = ...; for (int j < 0; j < N; j+=1) { TargetStmt: use(D); } } has DefStmt-to-TargetStmt mapping of { DefStmt[i] -> TargetStmt[i,j] } This should apply on the majority of def-to-target mappings. This patch detects this case and directly constructs the expected mapping. It assumes that the mapping never crosses the loop header DefStmt is in, which ForwardOpTree does not support at the moment anyway. Differential Revision: https://reviews.llvm.org/D47752 llvm-svn: 334134
* getDependences to new C++ interfaceTobias Grosser2018-06-062-12/+15
| | | | | | | | | | | | | | Reviewers: Meinersbur, grosser, bollu, cs15btech11044, jdoerfert Reviewed By: grosser Subscribers: pollydev, llvm-commits Tags: #polly Differential Revision: https://reviews.llvm.org/D47786 llvm-svn: 334092
* partitionSetParts from C to C++ interface.Tobias Grosser2018-06-011-41/+32
| | | | | | | | | | | | | | | | Summary: partitionSetParts from C to new C++ interface. Reviewers: grosser, Meinersbur, jdoerfert, bollu, cs15btech11044 Reviewed By: grosser, Meinersbur Subscribers: llvm-commits, pollydev Tags: #polly Differential Revision: https://reviews.llvm.org/D47252 llvm-svn: 333780
* [ScopInfo] Update Scop::addUserContext() to C++ interfaceTobias Grosser2018-05-281-21/+10
| | | | | | | | | | | | | | Summary: This patch updates `Scop::addUserContext()` function to the new C++ interface and replaces the `auto` keyword with explicit type wherever used in this function. Reviewers: grosser, bollu, philip.pfaffe, chelini, Meinersbur Reviewed By: grosser Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D47438 llvm-svn: 333366
* createNextIterationMap from C to C++ interfaceTobias Grosser2018-05-231-13/+13
| | | | | | | | | | | | | | | | Summary: update createNextIterationMap function to new C++ interface. Reviewers: grosser, Meinersbur, jdoerfert, bollu, cs15btech11044 Reviewed By: cs15btech11044 Subscribers: llvm-commits, pollydev Tags: #polly Differential Revision: https://reviews.llvm.org/D47102 llvm-svn: 333113
* [ScopInfo] Remove usage of isl_set_n_basic_set()Philip Pfaffe2018-05-161-14/+12
| | | | | | | | | | Summary: This patch aims to remove the usage of old C-styled isl functions (in this case `isl_set_n_basic_set()`) in favor of new C++ isl interface based methods in `ScopInfo.cpp`. Patch by Sahil Yerawar Differential Revision: https://reviews.llvm.org/D46935 llvm-svn: 332471
* [SI] Create Scop Name lazilyPhilip Pfaffe2018-05-151-2/+2
| | | | | | | | | | | | | Summary: Creating the Scop name is expensive, because creating the Region name it's derived from is expensive. So create the name lazily, because getName() is actually called rarely. This is a reiteration of r328666, which introduced a use-after-free and got reverted in r331363. Differential Revision: https://reviews.llvm.org/D46868 llvm-svn: 332359
* [polly] Update uses of DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-156-54/+60
| | | | | | | | | | | 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
* [ScopInfo] Remove bail out condition in buildMinMaxAccess().Michael Kruse2018-05-091-12/+10
| | | | | | | | | | | | | | | | | | | | | The condition was introduced in r267142 to mitigate a long compile-time case. In r306087, a max-computation limit was introduced that should handle the same case while leaving the max disjuncts heuristic it should have replaced intact. Today, the max disjuncts bail-out causes problems in that it prematurely stops SCoPs from being detected, e.g. in SPEC's lbm. This would hit less like if isl_set_coalesce would be called after isl_set_remove_divs (which makes more basic_set likely to be coalescable) instead of before. This patch tries to remove the premature max-disjuncts bail-out condition by using simple_hull() to reduce the computational overhead, instead of directly invalidating that SCoP. Differential Revision: https://reviews.llvm.org/D45066 Contributed-by: Sahil Girish Yerawar <cs15btech11044@iith.ac.in> llvm-svn: 331891
* Revert "[polly] [ScopInfo] Don't pre-compute the name of the Scop's region."Philip Pfaffe2018-05-021-2/+2
| | | | | | | | | This reverts commit 0f9dc03765dc301fff7a52e2a0e1dd3e5f3130c5, r328666. The change introduced a use-after-free, caused by the temporary name string being destroyed after converting it to a StringRef. llvm-svn: 331363
* Remove another set or release() callsTobias Grosser2018-04-291-1/+1
| | | | llvm-svn: 331129
* Remove the last uses of isl::give and isl::takeTobias Grosser2018-04-291-6/+5
| | | | llvm-svn: 331126
* [ScopDetect] Reject loop with multiple exit blocks.Michael Kruse2018-04-252-0/+38
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The current statement domain derivation algorithm does not (always) consider that different exit blocks of a loop can have different conditions to be reached. From the code for (int i = n; ; i-=2) { if (i <= 0) goto even; if (i <= 1) goto odd; A[i] = i; } even: A[0] = 42; return; odd: A[1] = 21; return; Polly currently derives the following domains: Stmt_even_critedge Domain := [n] -> { Stmt_even_critedge[] }; Stmt_odd Domain := [n] -> { Stmt_odd[] : (1 + n) mod 2 = 0 and n > 0 }; while the domain for the odd case is correct, Stmt_even is assumed to be executed unconditionally, which is obviously wrong. While projecting out the loop dimension in `adjustDomainDimensions`, it does not consider that there are other exit condition that have matched before. I don't know a how to fix this without changing a lot of code. Therefore This patch rejects loops with multiple exist blocks to fix the miscompile of test-suite's uuencode. The odd condition is transformed by LLVM to %cmp1 = icmp eq i64 %indvars.iv, 1 such that the project_out in adjustDomainDimensions() indeed only matches for odd n (using this condition only, we'd have an infinite loop otherwise). The even condition manifests as %cmp = icmp slt i64 %indvars.iv, 3 Because buildDomainsWithBranchConstraints() does not consider other exit conditions, it has to assume that the induction variable will eventually be lower than 3 and taking this exit. IMHO we need to reuse the algorithm that determines the number of iterations (addLoopBoundsToHeaderDomain) to determine which exit condition applies first. It has to happen in buildDomainsWithBranchConstraints() because the result will need to propagate to successor BBs. Currently addLoopBoundsToHeaderDomain() just look for union of all backedge conditions (which means leaving not the loop here). The patch in llvm.org/PR35465 changes it to look for exit conditions instead. This is required because there might be other exit conditions that do not alternatively go back to the loop header. Differential Revision: https://reviews.llvm.org/D45649 llvm-svn: 330858
* Allow arbitrary function calls for debugging purposes.Michael Kruse2018-04-203-1/+11
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [ScopDetect / ScopInfo] Get statistics for scops without any loop correctlyTobias Grosser2018-04-182-3/+13
| | | | | | Make sure we also counts scops not containing any loops. llvm-svn: 330285
* [ScopInfo] Avoid iterator invalidation.Michael Kruse2018-04-101-1/+3
| | | | | | | | | | | Commit r329640 introduced the removal of all MemoryAccesses of a Scop. It accidentally continued iterating over a vector whose iterators have been invalidated by a MemoryAccess removal. Make a copy of the MemoryAccesses to remove to iterate over while removing them. llvm-svn: 329653
* [ScopInfo] Completely remove MemoryAccesses when their parent statement is ↵Michael Kruse2018-04-091-10/+18
| | | | | | | | | | | | | | | removed. Removing a statement left its MemoryAccesses in some lists and maps of the SCoP. Which lists depends on at which phase of the SCoP construction the statement is deleted. Follow-up passes could still see the already deleted MemoryAccesses by iterating through these lists/maps, resulting in an access violation. When removing a ScopStmt, also remove all its MemoryAccesses by using the same mechnism that removes a MemoryAccess. llvm-svn: 329640
* [ScopInfo] Actually remove from list.Michael Kruse2018-04-091-2/+4
| | | | | | | | | | std::remove, despite its name, does not remove elements from a list, but only moves them to the end of a list. Call erase() to shorten the vector to the remaining elements. Test case included in next commit. llvm-svn: 329639
* [Polly][IslAst] Fix minimal dependence distance.Huihui Zhang2018-04-041-1/+2
| | | | | | | | | | | | | | | | | | | Summary: When checking the parallelism of a scheduling dimension, we first check if excluding reduction dependences the loop is parallel or not. If the loop is not parallel, then we need to return the minimal dependence distance of all data dependences, including the previously subtracted reduction dependences. Reviewers: grosser, Meinersbur, efriedma, eli.friedman, jdoerfert, bollu Reviewed By: Meinersbur Subscribers: llvm-commits, pollydev Tags: #polly Differential Revision: https://reviews.llvm.org/D45236 llvm-svn: 329214
* [polly] [ScopInfo] Don't pre-compute the name of the Scop's region.Eli Friedman2018-03-271-2/+2
| | | | | | | | | | | This gets very expensive for basic blocks which don't have a name: it calls printAsOperand, which numbers the entire module. We don't normally need the name anyway, though; it's only used for debug dumps, so don't compute it by default. Differential Revision: https://reviews.llvm.org/D44946 llvm-svn: 328666
* Adjust to clang-format changesTobias Grosser2018-03-205-8/+0
| | | | llvm-svn: 328005
* [ScopInfo] Do not use the set dimension ids to carry loop informationTobias Grosser2018-03-032-44/+18
| | | | | | | | | | | | | | isl does not guarantee that set dimension ids will be preserved, so using them to carry information is not a good idea. Furthermore, the loop information can be derived without problem from the statement itself. As this even requires less code than propagating loop information on set dimension ids, starting from this commit we just derive the loop information in collectSurroundingLoops directly from the IR. Interestingly this also results in a couple of isl sets to take a simpler representation. llvm-svn: 326664
* Use isl::manage_copy to simplify calls to isl::manage(isl_.._copy())Tobias Grosser2018-02-201-1/+1
| | | | | | | | | | | 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
* [ScopBuilder] scalar-indep: Fix mutually referencing PHIs.Michael Kruse2018-02-121-0/+39
| | | | | | | | | | | | | | Two or more PHIs mutually using each other directly or indirectly as incoming value could cause that a PHI WRITE be added before the PHI READ (i.e. it overwrites the current incoming value with the next incoming value before it being read). Fix by ensuring that the PHI WRITE and PHI READ are in the same statement. This should fix the miscompile of SingleSource/Benchmark/Misc/whetstone from the test-suite. llvm-svn: 324934
* [ScopBuilder] Make -polly-stmt-granularity=scalar-indep the default.Michael Kruse2018-02-031-1/+1
| | | | | | | | | | | | | | | | | | | | Splitting basic blocks into multiple statements if there are now additional scalar dependencies gives more freedom to the scheduler, but more statements also means higher compile-time complexity. Switch to finer statement granularity, the additional compile time should be limited by the number of operations quota. The regression tests are written for the -polly-stmt-granularity=bb setting, therefore we add that flag to those tests that break with the new default. Some of the tests only fail because the statements are named differently due to a basic block resulting in multiple statements, but which are removed during simplification of statements without side-effects. Previous commits tried to reduce this effect, but it is not completely avoidable. Differential Revision: https://reviews.llvm.org/D42151 llvm-svn: 324169
* [ScopInfo] Allow epilogues to be the main statement of a BB.Michael Kruse2018-02-031-1/+4
| | | | | | | | | | Do not add a "_last" suffix to the statement name if there is no (other) main statement for a basic block. In other words, it becomes the main statement itself. This further reduces the statement naming difference between -polly-stmt-granularity=bb and -polly-stmt-granularity=scalar-indep. llvm-svn: 324168
* Run clang-format after r324003. NFC.Michael Kruse2018-02-021-1/+5
| | | | llvm-svn: 324112
* Update polly for r323999.Benjamin Kramer2018-02-011-1/+1
| | | | llvm-svn: 324003
* [ScopBuilder] Prefer PHI Write accesses in the statement the incoming value ↵Michael Kruse2018-01-232-66/+30
| | | | | | | | | | | | | | | | | | is defined. Theoretically, a PHI write can be added to any statement that represents the incoming basic block. We previously always chose the last because the incoming value's definition is guaranteed to be defined. With this patch the PHI write is added to the statement that defines the incoming value. It avoids the requirement for a scalar dependency between the defining statement and the statement containing the write. As such the logic for -polly-stmt-granularity=scalar-indep that ensures that there is such scalar dependencies can be removed. Differential Revision: https://reviews.llvm.org/D42147 llvm-svn: 323284
* [ScopBuilder] Revise statement naming when there are multiple statements per BB.Michael Kruse2018-01-181-17/+47
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | The goal is to have -polly-stmt-granularity=bb and -polly-stmt-granularity=scalar-indep to have the same names if there is just one statement per basic block. This fixes a fluke when Polybench's jacobi-2d is optimized differently depending on the -polly-stmt-granularity option, although both options create the same SCoP, just with different statement names. The new naming scheme is: With -polly-use-llvm-names=0: Stmt<BBIdx as decimal><Idx within BB as letter> With -polly-use-llvm-names=1: Stmt_BBName_<Idx within BB as letter> The <Idx within BB> suffix is omitted for the main statement of a BB. The main statement is either the one containing the first store or call (those cannot be removed by the simplifyer), or if there is no such instruction, the first. If after simplification there is just a single statement left, it should be the main statement and have the same names as with -polly-stmt-granularity=bb. Differential Revision: https://reviews.llvm.org/D42136 llvm-svn: 322852
* [ScopInfo] Pass name to ScopStmt ctor. NFC.Michael Kruse2018-01-182-25/+45
| | | | | | | | This will give control of the statement's name to the caller. Required to give -polly-stmt-granularity=scalar-indep more control over the name of the generated statement in a follow-up commit. llvm-svn: 322851
* [polly] [ScopInfo] Don't use isl_val_get_num_si.Eli Friedman2018-01-171-3/+7
| | | | | | | | | | | | | | | | | isl_val_get_num_si crashes on overflow, so don't use it on arbitrary integers. Testcase only crashes on platforms where long is 32 bits because of the signature of isl_val_get_num_si; not sure if it's possible to write a testcase which crashes if long is 64 bits. There are a few other places in polly which use isl_val_get_num_si; they probably need to be fixed as well. I don't think polly uses any of the other "long" isl APIs in an unsafe manner. Differential Revision: https://reviews.llvm.org/D42129 llvm-svn: 322766
* [ScopBuilder] Split statements on encountering store instructions.Michael Kruse2017-12-111-4/+10
| | | | | | | | | | Introduce -polly-stmt-granularity=store option. Contributed-by: Nandini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D37337 llvm-svn: 320360
* [ScopBuilder] Fix typo. NFC.Michael Kruse2017-12-101-4/+4
| | | | | | | | Contributed-by: Nandini Singhal <cs15mtech01004@iith.ac.in> Differential Revision: https://reviews.llvm.org/D41047 llvm-svn: 320336
* Port SCEVAffinator to the isl c++ bindingsPhilip Pfaffe2017-12-061-6/+5
| | | | | | | | | | | | | | 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
* Update to latest clang-format. [NFC]Siddharth Bhat2017-12-051-3/+3
| | | | | | Differential Revision: https://reviews.llvm.org/D40791 llvm-svn: 319718
* Update format after clang-format change. NFC.Michael Kruse2017-11-301-3/+3
| | | | | | In r319314 clang-format changed its reflowing logic. llvm-svn: 319426
* Port ScopInfo to the isl cpp bindingsPhilip Pfaffe2017-11-191-178/+116
| | | | | | | | | | | | | | | | | | | | | 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
* [SI] Fix a potential use-after-freePhilip Pfaffe2017-11-161-14/+17
| | | | | | | | | | | | | | | | | | | Summary: There is a potential use-after-free bug in Scop::buildSchedule(Region *, LoopStackTy &, LoopInfo &). Before, we took a reference to LoopStack.back() which is a use after free, since back is popped off further below. This didn't crash before by pure chance, since LoopStack is actually a vector, and the memory isn't freed upon pop. I turned this into an iterator-based algorithm. Reviewers: grosser, bollu, Meinersbur Reviewed By: Meinersbur Subscribers: llvm-commits, pollydev Differential Revision: https://reviews.llvm.org/D39979 llvm-svn: 318415
* [Analysis] update to use new fast-math API - isFast()Sanjay Patel2017-11-061-2/+2
| | | | llvm-svn: 317491
* Rename OptimizationDiagnosticInfo.h to OptimizationRemarkEmitter.hAdam Nemet2017-10-095-5/+5
| | | | | | Polly version of r315249 on LLVM trunk. llvm-svn: 315253
* [ScopBuilder] Introduce -polly-stmt-granularity=scalar-indep option.Michael Kruse2017-10-051-2/+180
| | | | | | | | | | | | | | | | | | | | | | | | | The option splits BasicBlocks into minimal statements such that no additional scalar dependencies are introduced. The algorithm is based on a union-find structure, and unites sets if putting them into separate statements would introduce a scalar dependencies. As a consequence, instructions may be split into separate statements such their relative order is different than the statements they are in. This is accounted for instructions whose relative order matters (e.g. memory accesses). The algorithm is generic in that heuristic changes can be made relatively easily. We might relax the order requirement for read-reads or accesses to different base pointers. Forwardable instructions can be made to not cause a join. This implementation gives us a speed-up of 82% in SPEC 2006 456.hmmer benchmark by allowing loop-distribution in a hot loop such that one of the loops can be vectorized. Differential Revision: https://reviews.llvm.org/D38403 llvm-svn: 314983
* [ScopBuilder] Introduce -polly-stmt-granularity option. NFC.Michael Kruse2017-10-041-16/+33
| | | | | | | | | | The option is introduced with only one possible value -polly-stmt-granularity=bb which represents the current behaviour, which is outlined into the new function buildSequentialBlockStmts(). More options will be added in future commits. llvm-svn: 314900
* [ScopBuilder] Iterate over statement instructions. NFC.Michael Kruse2017-10-021-39/+28
| | | | | | | | | Iterate over statement instructions instead over basic block instructions when creating MemoryAccesses. It allows making the creation of MemoryAccesses independent of how the basic blocks are split into multiple ScopStmts. llvm-svn: 314665
* [ScopBuilder] Build invariant loads separately.Michael Kruse2017-10-021-3/+47
| | | | | | | | | | | | | | | | | | Create the MemoryAccesses of invariant loads separately and before all other MemoryAccesses. Invariant loads are classified as synthesizable and therefore are not contained in any statement. When iterating over all instructions of all statements, the invariant loads are consequently not processed and iterating over them separately becomes necessary. This patch can change the order in which MemoryAccesses are created, but otherwise has no functional change. Some temporary code is introduced to ensure correctness, but will be removed in the next commit. llvm-svn: 314664
* [ScopBuilder] Build escaping dependencies separately.Michael Kruse2017-10-021-2/+9
| | | | | | | | | | | | | Instructions that compute escaping values might be synthesizable and therefore not contained in any ScopStmt. When buildAccessFunctions is changed to only iterate over the instruction list of statement, "free" instructions still need to be written. We do this after the main MemoryAccesses have been created. This can change the order in which MemoryAccesses are created, but has otherwise no functional change. llvm-svn: 314663
* [ScopBuilder] Specialize exit block handling. NFC.Michael Kruse2017-10-021-15/+15
| | | | | | | | | | | Decouple handling of exit block PHIs and other MemoryAccesses. Exit PHIs only need the PHI handling part of buildAccessFunctions but requires code for skipping them in while creating other MemoryAcesses. This change will make it easier to modify how statement MemoryAccesses are created without considering the exit block special case. llvm-svn: 314662
OpenPOWER on IntegriCloud