summaryrefslogtreecommitdiffstats
path: root/polly/lib
Commit message (Collapse)AuthorAgeFilesLines
* Typo: ToComplex -> TooComplex. NFC.Michael Kruse2016-05-021-4/+4
| | | | llvm-svn: 268224
* Rename Conjuncts -> Disjunctions. NFC.Michael Kruse2016-05-023-13/+14
| | | | | | | | The check for complexity compares the number of polyhedra in a set, which are combined by disjunctions (union, "OR"), not conjunctions (intersection, "AND"). llvm-svn: 268223
* [ScheduleOptimizer] Add -polly-opt-outer-coincidence option.Michael Kruse2016-05-021-0/+20
| | | | | | | | | | | | Add a command line switch to set the isl_options_set_schedule_outer_coincidence option. ISL then tries to build schedules where the outer member of a band satisfies the coincidence constraints. In practice this allows loop skewing for more parallelism in inner loops. llvm-svn: 268222
* Typo: isToComplex -> isTooComplex. NFC.Michael Kruse2016-05-021-5/+5
| | | | llvm-svn: 268220
* Allow unsigned divisionsJohannes Doerfert2016-04-292-27/+72
| | | | | | | | | | | | | After zero-extend operations and unsigned comparisons we now allow unsigned divisions. The handling is basically the same as for signed division, except the interpretation of the operands. As the divisor has to be constant in both cases we can simply interpret it as an unsigned value without additional complexity in the representation. For the dividend we could choose from the different representation schemes introduced for zero-extend operations but for now we will simply use an assumption. llvm-svn: 268032
* Refactor SCEVAffinator [NFC]Johannes Doerfert2016-04-291-14/+12
| | | | llvm-svn: 268031
* ScopInfo: Add option to control abort on isl errorsTobias Grosser2016-04-291-1/+7
| | | | | | | For debugging it is often convenient to not abort at the very first memory management error. This option allows to control this behavior at run-time. llvm-svn: 268030
* [FIX] Unsigned comparisons change invalid domainJohannes Doerfert2016-04-292-26/+24
| | | | | | | | | It does not suffice to take a global assumptions for unsigned comparisons but we also need to adjust the invalid domain of the statements guarded by such an assumption. To this end we allow to specialize the getPwAff call now in order to indicate unsigned interpretation. llvm-svn: 268025
* [FIX] Prevent division/modulo by zero in parametersJohannes Doerfert2016-04-291-2/+20
| | | | | | | | | | | | When we materialize parameter SCEVs we did so without considering the side effects they might have, e.g., both division and modulo are undefined if the right hand side is zero. This is a problem because we potentially extended the domain under which we evaluate parameters, thus we might have introduced such undefined behaviour. To prevent that from happening we will now guard divisions and modulo operations in the parameters with a compare and select. llvm-svn: 268023
* [FIX] Correct assumption simplificationJohannes Doerfert2016-04-281-4/+20
| | | | | | | | Assumptions and restrictions can both be simplified with the domain of a statement but not the same way. After this patch we will correctly distinguish them. llvm-svn: 267885
* BlockGenerator: Drop leftover debug statementTobias Grosser2016-04-281-1/+0
| | | | llvm-svn: 267874
* [FIX] Propagate execution domain of invariant loadsJohannes Doerfert2016-04-272-8/+16
| | | | | | | | | | | If the base pointer of an invariant load is is loaded conditionally, that condition needs to hold for the invariant load too. The structure of the program will imply this for domain constraints but not for imprecisions in the modeling. To this end we will propagate the execution context of base pointers during code generation and thus ensure the derived pointer does not access an invalid base pointer. llvm-svn: 267707
* Allow unsigned comparisonsJohannes Doerfert2016-04-263-28/+12
| | | | | | | | With this patch we will optimistically assume that the result of an unsigned comparison is the same as the result of the same comparison interpreted as signed. llvm-svn: 267559
* [FIX] Adjust assumption space for zext instructionsJohannes Doerfert2016-04-261-1/+2
| | | | llvm-svn: 267552
* Do not use the number of parameters in the complexity checkJohannes Doerfert2016-04-261-5/+12
| | | | llvm-svn: 267532
* Do not add but record signed-unsigned assumptionsJohannes Doerfert2016-04-261-1/+1
| | | | llvm-svn: 267528
* Extract some constant factors from "SCEVAddExprs"Johannes Doerfert2016-04-251-0/+26
| | | | | | | | | Additive expressions can have constant factors too that we can extract and thereby simplify the internal representation. For now we do compute the gcd of all constant factors but only extract the same (possibly negated) factor if there is one. llvm-svn: 267445
* Do not check all GEPs for assumptionsJohannes Doerfert2016-04-251-10/+11
| | | | | | | | | | Before, we checked all GEPs in a statement in order to derive out-of-bound assumptions. However, this can not only introduce new parameters but it is also not clear what we can learn from GEPs that are not immediately used in a memory accesses inside the SCoP. As this case is very rare, no actual change in the behaviour is expected. llvm-svn: 267442
* Only add user assumptions on known parameters [NFC]Johannes Doerfert2016-04-251-1/+25
| | | | | | | | | | | | Before, assumptions derived from llvm.assume could reference new parameters that were not known to the SCoP before. These were neither beneficial to the representation nor to the user that reads the emitted remark. Now we project them out and keep only user assumptions on known parameters. Nevertheless, the new parameters are still part of the SCoPs parameter space as the SCEVAffinator currently adds them on demand. llvm-svn: 267441
* Refactor Scop parameter handlingJohannes Doerfert2016-04-251-43/+37
| | | | | | | | | The new handling is consistent with the remaining code, e.g., we do not create a new parameter id for each lookup call but copy an existing one. Additionally, we now use the implicit order defined by the Parameters set instead of an explicit one defined in a map. llvm-svn: 267423
* Model zext-extend instructionsJohannes Doerfert2016-04-253-21/+119
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | A zero-extended value can be interpreted as a piecewise defined signed value. If the value was non-negative it stays the same, otherwise it is the sum of the original value and 2^n where n is the bit-width of the original (or operand) type. Examples: zext i8 127 to i32 -> { [127] } zext i8 -1 to i32 -> { [256 + (-1)] } = { [255] } zext i8 %v to i32 -> [v] -> { [v] | v >= 0; [256 + v] | v < 0 } However, LLVM/Scalar Evolution uses zero-extend (potentially lead by a truncate) to represent some forms of modulo computation. The left-hand side of the condition in the code below would result in the SCEV "zext i1 <false, +, true>for.body" which is just another description of the C expression "i & 1 != 0" or, equivalently, "i % 2 != 0". for (i = 0; i < N; i++) if (i & 1 != 0 /* == i % 2 */) /* do something */ If we do not make the modulo explicit but only use the mechanism described above we will get the very restrictive assumption "N < 3", because for all values of N >= 3 the SCEVAddRecExpr operand of the zero-extend would wrap. Alternatively, we can make the modulo in the operand explicit in the resulting piecewise function and thereby avoid the assumption on N. For the example this would result in the following piecewise affine function: { [i0] -> [(1)] : 2*floor((-1 + i0)/2) = -1 + i0; [i0] -> [(0)] : 2*floor((i0)/2) = i0 } To this end we can first determine if the (immediate) operand of the zero-extend can wrap and, in case it might, we will use explicit modulo semantic to compute the result instead of emitting non-wrapping assumptions. Note that operands with large bit-widths are less likely to be negative because it would result in a very large access offset or loop bound after the zero-extend. To this end one can optimistically assume the operand to be positive and avoid the piecewise definition if the bit-width is bigger than some threshold (here MaxZextSmallBitWidth). We choose to go with a hybrid solution of all modeling techniques described above. For small bit-widths (up to MaxZextSmallBitWidth) we will model the wrapping explicitly and use a piecewise defined function. However, if the bit-width is bigger than MaxZextSmallBitWidth we will employ overflow assumptions and assume the "former negative" piece will not exist. llvm-svn: 267408
* Check only loop control of loops that are part of the regionJohannes Doerfert2016-04-252-4/+2
| | | | | | | This also removes a duplicated line of code in the region generator that caused a SPEC benchmark to fail with the new SCoPs. llvm-svn: 267404
* Initialize the invalid domain of an access with an empty setJohannes Doerfert2016-04-251-1/+3
| | | | llvm-svn: 267403
* Do not propagate invalid domains over back edgesJohannes Doerfert2016-04-251-0/+4
| | | | llvm-svn: 267402
* Introduce a parameter set type [NFC]Johannes Doerfert2016-04-252-19/+15
| | | | llvm-svn: 267401
* Remove unnecessary argument of the SCEVValidator [NFC]Johannes Doerfert2016-04-253-29/+18
| | | | llvm-svn: 267400
* Add an invalid domain to memory accessesJohannes Doerfert2016-04-231-7/+22
| | | | | | | | | Memory accesses can have non-precisely modeled access functions that would cause us to build incorrect execution context for hoisted loads. This is the same issue that occurred during the domain construction for statements and it is dealt with the same way. llvm-svn: 267289
* Translate SCEVs to isl_pw_aff and their invalid domainJohannes Doerfert2016-04-232-72/+105
| | | | | | | | | | | | | The SCEVAffinator will now produce not only the isl representaiton of a SCEV but also the domain under which it is invalid. This is used to record possible overflows that can happen in the statement domains in the statements invalid domain. The result is that invalid loads have an accurate execution contexts with regards to the validity of their statements domain. While the SCEVAffinator currently is only taking "no-wrapping" assumptions, we can add more withouth worrying about the execution context of loads that are optimistically hoisted. llvm-svn: 267288
* Track invalid domains not invalid contexts for statementsJohannes Doerfert2016-04-231-35/+52
| | | | | | | | | | | | | | The invalid context is not enough to describe the parameter constraints under which a statement is not modeled precisely. The reason is that during the domain construction the bounds on the induction variables are not known but needed to check if e.g., an overflow can actually happen. To this end we replace the invalid context of a statement with an invalid domain. It is initialized during domain construction and intersected with the domain once it was completely build. Later this invalid domain allows to eliminate falsely assumed wrapping cases and other falsely assumed mismatches in the modeling. llvm-svn: 267286
* Improve accuracy of Scop::hasFeasibleRuntimeContextJohannes Doerfert2016-04-231-3/+6
| | | | | | | If the AssumptionContext is a subset of the InvalidContext the runtime context is not feasible. llvm-svn: 267285
* Simplify the execution context for dereferencable loadsJohannes Doerfert2016-04-231-5/+40
| | | | | | | If we know it is safe to execute a load we do not need an execution context, however only if we are sure it was modeled correctly. llvm-svn: 267284
* Remove simplification calls for the execution domain [NFC]Johannes Doerfert2016-04-231-3/+0
| | | | | | | These calls were sometimes costly and do not show any improvements on our small test cases. llvm-svn: 267283
* Bail for complex execution contexts of invariant loadsJohannes Doerfert2016-04-221-1/+10
| | | | llvm-svn: 267146
* Early exit for addInvariantLoadsJohannes Doerfert2016-04-221-0/+3
| | | | llvm-svn: 267143
* Bail for complex alias checksJohannes Doerfert2016-04-221-2/+7
| | | | llvm-svn: 267142
* Relate domains to statements during construction [NFC]Johannes Doerfert2016-04-191-17/+21
| | | | | | | Instead of the Scop::getPwAff() function we now use the ScopStmt::getPwAff() function during the statements domain construction. llvm-svn: 266741
* Add user assumptions after domain generation [NFC]Johannes Doerfert2016-04-191-1/+2
| | | | llvm-svn: 266740
* Do not build domains for out of SCoP blocks [NFC]Johannes Doerfert2016-04-191-0/+7
| | | | llvm-svn: 266739
* Mark Scop::getDomainConditions as const [NFC]Johannes Doerfert2016-04-191-2/+2
| | | | llvm-svn: 266738
* SCoPValidator: Use SCEVTraversal to simplify SCEVInRegionDependencesTobias Grosser2016-04-181-101/+33
| | | | llvm-svn: 266622
* [FIX] Check the invalid context agains the context to rule out SCoPsJohannes Doerfert2016-04-121-0/+1
| | | | llvm-svn: 266096
* Do not by default minimize remarksJohannes Doerfert2016-04-121-10/+17
| | | | | | | | | | | | | We used checks to minimize the number of remarks we present to a user but these checks can become expensive, especially since all wrapping assumptions are emitted separately. Because there is not benefit for a "headless" run we put these checks under a command line flag. Thus, if the flag is not given we will emit "non-effective" remarks, e.g., duplicates and revert to the old behaviour if it is given. As this also changes the internal representation of some sets we set the flag by default for our unit tests. llvm-svn: 266087
* Record wrapping assumptions earlyJohannes Doerfert2016-04-122-57/+31
| | | | | | | | Utilizing the record option for assumptions we can simplify the wrapping assumption generation a lot. Additionally, we can now report locations together with wrapping assumptions, though they might not be accurate yet. llvm-svn: 266069
* Record assumptions first and add them laterJohannes Doerfert2016-04-121-7/+32
| | | | | | | | | | | | | | | | | | There are three reasons why we want to record assumptions first before we add them to the assumed/invalid context: 1) If the SCoP is not profitable or otherwise invalid without the assumed/invalid context we do not have to compute it. 2) Information about the context are gathered rather late in the SCoP construction (basically after we know all parameters), thus the user might see overly complicated assumptions to be taken while they would have been simplified later on. 3) Currently we cannot take assumptions at any point but have to wait, e.g., for the domain generation to finish. This makes wrapping assumptions much more complicated as they need to be and it will have a similar effect on "signed-unsigned" assumptions later. llvm-svn: 266068
* Introduce and use MemoryAccess::getPwAff() [NFC]Johannes Doerfert2016-04-121-4/+9
| | | | llvm-svn: 266066
* Do not assume switch modeling optimizes a SCoPJohannes Doerfert2016-04-121-1/+0
| | | | llvm-svn: 266065
* Introduce an invalid context for each statementJohannes Doerfert2016-04-121-30/+44
| | | | | | | | | | Collect the error domain contexts (formerly in the ErrorDomainCtxMap) for each statement in the new InvalidContext member variable. While this commit is basically a [NFC] it is a first step to make hoisting sound by allowing a more fine grained record of invalid contexts, e.g., here on statement level. llvm-svn: 266053
* Simplify SCEVAffinator code [NFC]Johannes Doerfert2016-04-121-15/+8
| | | | llvm-svn: 266051
* Allow overflow of indices with constant dim-sizes.Michael Kruse2016-04-111-0/+60
| | | | | | | | | | | | | | | | | | | Allow overflow of indices into the next higher dimension if it has constant size. E.g. float A[32][2]; ((float*)A)[5]; is effectively the same as A[2][1]; This can happen since r265379 as a side effect if ScopDetection recognizes an access as affine, but ScopInfo rejects the GetElementPtr. Differential Revision: http://reviews.llvm.org/D18878 llvm-svn: 265942
* Do not bind a non-const reference to a rvalue. NFC.Michael Kruse2016-04-111-2/+3
| | | | | | | | | | MSVC warns with: warning C4239: nonstandard extension used: 'initializing': conversion from 'llvm::DebugLoc' to 'llvm::DebugLoc &' note: A non-const reference may only be bound to an lvalue Change the reference to a const reference. llvm-svn: 265937
OpenPOWER on IntegriCloud