| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| ... | |
| |
|
|
|
|
|
| |
Delinearization is now enabled by default and does not need to explicitly need
to be enabled in our tests.
llvm-svn: 264154
|
| |
|
|
|
|
|
|
|
| |
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
|
| |
|
|
|
|
|
|
|
|
| |
This might be useful to evaluate the benefit of us handling modref funciton
calls. Also, a new bug that was triggered by modref function calls was
recently reported http://llvm.org/PR27035. To ensure the same issue does not
cause troubles for other people, we temporarily disable this until the bug
is resolved.
llvm-svn: 264140
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
ISL can conclude additional conditions on parameters from restrictions
on loop variables. Such conditions persist when leaving the loop and the
loop variable is projected out. This results in a narrower domain for
exiting the loop than entering it and is logically impossible for
non-infinite loops.
We fix this by not adding a lower bound i>=0 when constructing BB
domains, but defer it to when also the upper bound it computed, which
was done redundantly even before this patch.
This reduces the number of LNT fails with -polly-process-unprofitable
-polly-position=before-vectorizer from 8 to 6.
llvm-svn: 264118
|
| |
|
|
|
|
|
|
|
|
|
|
| |
We bail out if current scop has a complex control flow as this could lead to
building of large domain conditions. This is to reduce compile time. This
addresses r26382.
Contributed-by: Chris Jenneisch <chrisj@codeaurora.org>
Differential Revision: http://reviews.llvm.org/D18362
llvm-svn: 264105
|
| |
|
|
|
|
|
| |
Affine branches are fully modeled and regenerated from the polyhedral domain and
consequently do not require any input conditions to be propagated.
llvm-svn: 263678
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Index calculations can use the last value that come out of a loop.
Ideally, ScalarEvolution can compute that exit value directly without
depending on the loop induction variable, but not in all cases.
This changes isAffine to not consider such loop exit values as affine to
avoid that SCEVExpander adds uses of the original loop induction
variable.
This fix is analogous to r262404 that applies to general uses of loop
exit values instead of index expressions and loop bouds as in this
patch.
This reduces the number of LNT test-suite fails with
-polly-position=before-vectorizer -polly-unprofitable
from 10 to 8.
llvm-svn: 262665
|
| |
|
|
| |
llvm-svn: 262649
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Value merging is only necessary for scalars when they are used outside
of the scop. While an array's base pointer can be used after the scop,
it gets an extra ScopArrayInfo of type MK_Value. We used to generate
phi's for both of them, where one was assuming the reault of the other
phi would be the original value, because it has already been replaced by
the previous phi. This resulted in IR that the current IR verifier
allows, but is probably illegal.
This reduces the number of LNT test-suite fails with
-polly-position=before-vectorizer -polly-process-unprofitable
from 16 to 10.
Also see llvm.org/PR26718.
llvm-svn: 262629
|
| |
|
|
|
|
|
|
|
| |
This should fix PR19422.
Thanks to Jeremy Huddleston Sequoia for reporting this.
Thanks to Roman Gareev for his investigation and the reduced test case.
llvm-svn: 262612
|
| |
|
|
|
|
|
|
|
|
|
| |
Polly recognizes affine loops that ScalarEvolution does not, in
particular those with loop conditions that depend on hoisted invariant
loads. Check for SCEVAddRec dependencies on such loops and do not
consider their exit values as synthesizable because SCEVExpander would
generate them as expressions that depend on the original induction
variables. These are not available in generated code.
llvm-svn: 262404
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
In order to speed up compile time and to avoid random timeouts we now
separately track assumptions and restrictions. In this context
assumptions describe parameter valuations we need and restrictions
describe parameter valuations we do not allow. During AST generation
we create a runtime check for both, whereas the one for the
restrictions is negated before a conjunction is build.
Except the In-Bounds assumptions we currently only track restrictions.
Differential Revision: http://reviews.llvm.org/D17247
llvm-svn: 262328
|
| |
|
|
|
|
| |
This cures the symptoms we see in h264 of SPEC2006 but not the cause.
llvm-svn: 262327
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Originally committed in r261899 and reverted in r262202 due to failing
in out-of-LLVM tree builds.
Replace the use of LLVM_TOOLS_BINARY_DIR by LLVM_TOOLS_DIR which exists
in both, in-tree and out-of-tree builds.
Original commit message:
The script updates a lit test case that uses FileCheck using the actual
output of the 'RUN:'-lines program. Useful when updating test cases due
to expected output changes and diff'ing expected and actual output.
llvm-svn: 262227
|
| |
|
|
|
|
|
|
| |
This reverts commit r261899. Even though I am not yet 100% certain, this is
commit is the only one that has some relation to the recent cmake failures
in Polly.
llvm-svn: 262202
|
| |
|
|
| |
llvm-svn: 262101
|
| |
|
|
|
|
|
|
| |
schedules tree with either the id of memory access or memory references.
Differential Revision: http://reviews.llvm.org/D17381
llvm-svn: 262039
|
| |
|
|
|
|
|
|
| |
The script updates a lit test case that uses FileCheck using the actual
output of the 'RUN:'-lines program. Useful when updating test cases due
expected output changes and diff'ing expected and actual output.
llvm-svn: 261899
|
| |
|
|
|
|
|
|
|
| |
Check the ModRefBehaviour of functions in order to decide whether or
not a call instruction might be acceptable.
Differential Revision: http://reviews.llvm.org/D5227
llvm-svn: 261866
|
| |
|
|
|
|
|
|
|
| |
The generated dedicated subregion exit block was assumed to have the same
dominance relation as the original exit block. This is incorrect if the exit
block receives other edges than only from the subregion, which results in that
e.g. the subregion's entry block does not dominate the exit block.
llvm-svn: 261865
|
| |
|
|
|
|
|
| |
From now on we bail only if a non-trivial alias group contains a non-affine
access, not when we discover aliasing and non-affine accesses are allowed.
llvm-svn: 261863
|
| |
|
|
|
|
|
|
|
|
| |
The test style guide defines that opt should get its input from stdin.
(instead by file argument to avoid that the file name appears in its
output)
CHECK-FORCED is not recognized by FileCheck; remove it.
llvm-svn: 261786
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Use 'mark' nodes annotate a SIMD loop during ScheduleTransformation and skip
parallelism checks.
The buildbot shows the following compile/execution time changes:
Compile time:
Improvements Δ Previous Current σ
…/gesummv -6.06% 0.2640 0.2480 0.0055
…/gemver -4.46% 0.4480 0.4280 0.0044
…/covariance -4.31% 0.8360 0.8000 0.0065
…/adi -3.23% 0.9920 0.9600 0.0065
…/doitgen -2.53% 0.9480 0.9240 0.0090
…/3mm -2.33% 1.0320 1.0080 0.0087
Execution time:
Regressions Δ Previous Current σ
…/viterbi 1.70% 5.1840 5.2720 0.0074
…/smallpt 1.06% 12.4920 12.6240 0.0040
Reviewed-by: Tobias Grosser <tobias@grosser.es>
Differential Revision: http://reviews.llvm.org/D14491
llvm-svn: 261620
|
| |
|
|
| |
llvm-svn: 261501
|
| |
|
|
|
|
|
|
|
|
|
|
|
| |
This patch adds support for memcpy, memset and memmove intrinsics. They are
represented as one (memset) or two (memcpy, memmove) memory accesses in the
polyhedral model. These accesses have an access range that describes the
summarized effect of the intrinsic, i.e.,
memset(&A[i], '$', N);
is represented as a write access from A[i] to A[i+N].
Differential Revision: http://reviews.llvm.org/D5226
llvm-svn: 261489
|
| |
|
|
| |
llvm-svn: 261488
|
| |
|
|
|
|
|
|
|
|
|
|
| |
To support non-aligned accesses we introduce a virtual element size
for arrays that divides each access function used for this array. The
adjustment of the access function based on the element size of the
array was therefore moved after this virtual element size was
determined, thus after all accesses have been created.
Differential Revision: http://reviews.llvm.org/D17246
llvm-svn: 261226
|
| |
|
|
| |
llvm-svn: 260955
|
| |
|
|
|
|
|
|
|
|
| |
A load can only be invariant if its base pointer is invariant too. To
this end, we check if the base pointer is defined inside the region or
outside. In the former case we recursively check if we can (and
therefore will) hoist the base pointer too. Only if that happends we
can hoist the load.
llvm-svn: 260886
|
| |
|
|
|
|
|
|
|
| |
This reverts commit 98efa006c96ac981c00d2e386ec1102bce9f549a.
The fix was broken since we do not use AA in the ScopDetection anymore to
check for invariant accesses.
llvm-svn: 260884
|
| |
|
|
|
|
|
|
|
|
| |
Before this patch it could happen that we did not hoist a load that
was a base pointer of another load even though AA already declared the
first one as invariant (during ScopDetection). If this case arises we
will now skipt the "can be overwriten" check because in this case the
over-approximating nature causes us to generate broken code.
llvm-svn: 260862
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
So far we separated constant factors from multiplications, however,
only when they are at the outermost level of a parameter SCEV. Now,
we also separate constant factors from the parameter SCEV if the
outermost expression is a SCEVAddRecExpr. With the changes to the
SCEVAffinator we can now improve the extractConstantFactor(...)
function at will without worrying about any other code part. Thus,
if needed we can implement a more comprehensive
extractConstantFactor(...) function that will traverse the SCEV
instead of looking only at the outermost level.
Four test cases were affected. One did not change much and the other
three were simplified.
llvm-svn: 260859
|
| |
|
|
|
|
|
|
|
|
|
|
|
| |
We now distinguish invariant loads to the same memory location if they
have different types. This will cause us to pre-load an invariant
location once for each type that is used to access it. However, we can
thereby avoid invalid casting, especially if an array is accessed
though different typed/sized invariant loads.
This basically reverts the changes in r260023 but keeps the test
cases.
llvm-svn: 260045
|
| |
|
|
| |
llvm-svn: 260031
|
| |
|
|
|
|
|
|
| |
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
|
| |
|
|
|
|
|
|
|
|
| |
Invariant load hoisting of memory accesses with non-canonical element
types lacks support for equivalence classes that contain elements of
different width/size. This support should be added, but to get our buildbots
back to green, we disable load hoisting for memory accesses with non-canonical
element size for now.
llvm-svn: 260023
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Always use access-instruction pointer type to load the invariant values.
Otherwise mismatches between ScopArrayInfo element type and memory access
element type will result in invalid casts. These type mismatches are after
r259784 a lot more common and also arise with types of different size, which
have not been handled before.
Interestingly, this change actually simplifies the code, as we now have only
one code path that is always taken, rather then a standard code path for the
common case and a "fixup" code path that replaces the standard code path in
case of mismatching types.
llvm-svn: 260009
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
The previously implemented approach is to follow value definitions and
create write accesses ("push defs") while searching for uses. This
requires the same relatively validity- and requirement conditions to be
replicated at multiple locations (PHI instructions, other instructions,
uses by PHIs).
We replace this by iterating over the uses in a SCoP ("pull in
requirements"), and add writes only when at least one read has been
added. It turns out to be simpler code because each use is only iterated
over once and writes are added for the first access that reads it. We
need another iteration to identify escaping values (uses not in the
SCoP), which also makes the difference between such accesses more
obvious. As a side-effect, the order of scalar MemoryAccess can change.
Differential Revision: http://reviews.llvm.org/D15706
llvm-svn: 259987
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
This allows code such as:
void multiple_types(char *Short, char *Float, char *Double) {
for (long i = 0; i < 100; i++) {
Short[i] = *(short *)&Short[2 * i];
Float[i] = *(float *)&Float[4 * i];
Double[i] = *(double *)&Double[8 * i];
}
}
To model such code we use as canonical element type of the modeled array the
smallest element type of all original array accesses, if type allocation sizes
are multiples of each other. Otherwise, we use a newly created iN type, where N
is the gcd of the allocation size of the types used in the accesses to this
array. Accesses with types larger as the canonical element type are modeled as
multiple accesses with the smaller type.
For example the second load access is modeled as:
{ Stmt_bb2[i0] -> MemRef_Float[o0] : 4i0 <= o0 <= 3 + 4i0 }
To support code-generating these memory accesses, we introduce a new method
getAccessAddressFunction that assigns each statement instance a single memory
location, the address we load from/store to. Currently we obtain this address by
taking the lexmin of the access function. We may consider keeping track of the
memory location more explicitly in the future.
We currently do _not_ handle multi-dimensional arrays and also keep the
restriction of not supporting accesses where the offset expression is not a
multiple of the access element type size. This patch adds tests that ensure
we correctly invalidate a scop in case these accesses are found. Both types of
accesses can be handled using the very same model, but are left to be added in
the future.
We also move the initialization of the scop-context into the constructor to
ensure it is already available when invalidating the scop.
Finally, we add this as a new item to the 2.9 release notes
Reviewers: jdoerfert, Meinersbur
Differential Revision: http://reviews.llvm.org/D16878
llvm-svn: 259784
|
| |
|
|
| |
llvm-svn: 259737
|
| |
|
|
| |
llvm-svn: 259693
|
| |
|
|
|
|
| |
This reverts commit (@259587). It needs some further discussions.
llvm-svn: 259629
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
We support now code such as:
void multiple_types(char *Short, char *Float, char *Double) {
for (long i = 0; i < 100; i++) {
Short[i] = *(short *)&Short[2 * i];
Float[i] = *(float *)&Float[4 * i];
Double[i] = *(double *)&Double[8 * i];
}
}
To support such code we use as element type of the modeled array the smallest
element type of all original array accesses. Accesses with larger types are
modeled as multiple accesses with the smaller type.
For example the second load access is modeled as:
{ Stmt_bb2[i0] -> MemRef_Float[o0] : 4i0 <= o0 <= 3 + 4i0 }
To support jscop-rewritable memory accesses we need each statement instance to
only be assigned a single memory location, which will be the address at which
we load the value. Currently we obtain this address by taking the lexmin of
the access function. We may consider keeping track of the memory location more
explicitly in the future.
llvm-svn: 259587
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
For schedule generation we assumed that the reverse post order traversal used by
the domain generation is sufficient, however it is not. Once a loop is
discovered, we have to completely traverse it, before we can generate the
schedule for any block/region that is only reachable through a loop exiting
block.
To this end, we add a "loop stack" that will keep track of loops we
discovered during the traversal but have not yet traversed completely.
We will never visit a basic block (or region) outside the most recent
(thus smallest) loop in the loop stack but instead queue such blocks
(or regions) in a waiting list. If the waiting list is not empty and
(might) contain blocks from the most recent loop in the loop stack the
next block/region to visit is drawn from there, otherwise from the
reverse post order iterator.
We exploit the new property of loops being always completed before additional
loops are processed, by removing the LoopSchedules map and instead keep all
information in LoopStack. This clarifies that we indeed always only keep a
stack of in-process loops, but will never keep incomplete schedules for an
arbitrary set of loops. As a result, we can simplify some of the existing code.
This patch also adds some more documentation about how our schedule construction
works.
This fixes http://llvm.org/PR25879
This patch is an modified version of Johannes Doerfert's initial fix.
Differential Revision: http://reviews.llvm.org/D15679
llvm-svn: 259354
|
| |
|
|
|
|
|
|
|
|
|
| |
The autotools build system is based on and requires LLVM's autotools
build system to work, which has been depricated and finally removed in
r258861. Consequently we also remove the autotools build system from
Polly.
Differential Revision: http://reviews.llvm.org/D16655
llvm-svn: 259041
|
| |
|
|
|
|
|
|
|
|
|
|
|
| |
Before adding a MK_Value READ MemoryAccess, check whether the read is
necessary or synthesizable. Synthesizable values are later generated by
the SCEVExpander and therefore do not need to be transferred
explicitly. This can happen because the check for synthesizability has
presumbly been forgotten in the case where a phi's incoming value has
been defined in a different statement.
Differential Revision: http://reviews.llvm.org/D15687
llvm-svn: 258998
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Ensure that there is at most one phi write access per PHINode and
ScopStmt. In particular, this would be possible for non-affine
subregions with multiple exiting blocks. We replace multiple MAY_WRITE
accesses by one MUST_WRITE access. The written value is constructed
using a PHINode of all exiting blocks. The interpretation of the PHI
WRITE's "accessed value" changed from the incoming value to the PHI like
for PHI READs since there is no unique incoming value.
Because region simplification shuffles around PHI nodes -- particularly
with exit node PHIs -- the PHINodes at analysis time does not always
exist anymore in the code generation pass. We instead remember the
incoming block/value pair in the MemoryAccess.
Differential Revision: http://reviews.llvm.org/D15681
llvm-svn: 258809
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Ensure there is at most one write access per definition of an
llvm::Value. Keep track of already created value write access by using
a (dense) map.
Replace addValueWriteAccess by ensureValueStore which can be uses more
liberally without worrying to add redundant accesses. It will be used,
e.g. in a logical correspondant for value reads -- ensureValueReload --
to ensure that the expected definition has been written when loading it.
Differential Revision: http://reviews.llvm.org/D15483
llvm-svn: 258807
|
| |
|
|
| |
llvm-svn: 258803
|
| |
|
|
| |
llvm-svn: 258802
|
