Check overflows in RTCs and bail accordingly

We utilize assumptions on the input to model IR in polyhedral world.
To verify these assumptions we version the code and guard it with a
runtime-ch

Check overflows in RTCs and bail accordingly

We utilize assumptions on the input to model IR in polyhedral world.
To verify these assumptions we version the code and guard it with a
runtime-check (RTC). However, since the RTCs are themselves generated
from the polyhedral representation we generate them under the same
assumptions that they should verify. In other words, the guarantees
that we try to provide with the RTCs do not hold for the RTCs
themselves. To this end it is necessary to employ a different check
for the RTCs that will verify the assumptions did hold for them too.

Differential Revision: http://reviews.llvm.org/D20165

llvm-svn: 269299

show more ...

Collect and verify generated parallel subfunctions

We verify the optimized function now for a long time and it helped to track
down bugs early. This will now also happen for all parallel subfunc

Collect and verify generated parallel subfunctions

We verify the optimized function now for a long time and it helped to track
down bugs early. This will now also happen for all parallel subfunctions we
generate.

llvm-svn: 265823

show more ...

Codegen:Do not invalidate dominator tree when bailing out during code generation

When codegenerating invariant loads in some rare cases we cannot generate code
and bail out. This change ensures that

Codegen:Do not invalidate dominator tree when bailing out during code generation

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 <[email protected]>
llvm-svn: 264142

show more ...

Adapt to LLVM head, again

llvm-svn: 261905

Revert "Adapt to LLVM head. NFC"

This reverts commit 4d3753b9646a69c00d234ccd6e91dc3d0ea5d643.

llvm-svn: 261892

Adapt to LLVM head. NFC

llvm-svn: 261886

Codegen: Print error in Polly code verification and allow to disable verfication.

We now always print the reason why the code did not pass the LLVM verifier and
we also allow to disable verfication

Codegen: Print error in Polly code verification and allow to disable verfication.

We now always print the reason why the code did not pass the LLVM verifier and
we also allow to disable verfication with -polly-codegen-verify=false. Before
this change the first assertion had generally no information why or what might
have gone wrong and it was also impossible to -view-cfg without recompile. This
change makes debugging bugs that result in incorrect IR a lot easier.

llvm-svn: 261320

show more ...

CodeGeneration: Add back verification of generated code

This got accidentally dropped in r260025

llvm-svn: 260857

Make memory accesses with different element types optional

We also disable this feature by default, as there are still some issues in
combination with invariant load hoisting that slipped through my

Make memory accesses with different element types optional

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

show more ...

Adjust formatting to clang-format changes in 256149

llvm-svn: 256151

IR cleanup after CodeGeneration

Re-run canonicalization passes after Polly's code generation.

The set of passes currently added here are nearly all the passes between
--polly-position=early and --p

IR cleanup after CodeGeneration

Re-run canonicalization passes after Polly's code generation.

The set of passes currently added here are nearly all the passes between
--polly-position=early and --polly-position=before-vectorizer, i.e. all
passes that would usually run after Polly.

In order to run these only if Polly actually modified the code, we add a
function attribute "polly-optimzed" to a function that contains
generated code. The cleanup pass is skipped if the function does not
have this attribute.

There is no support by the (legacy) PassManager to run passes only under
some conditions. One could have wrapped all transformation passes to run
only when CodeGeneration changed the code, but the analyses would run
anyway. This patch creates an independent pass manager. The
disadvantages are that all analyses have to re-run even if preserved and
it does not honor compiler switches like the PassManagerBuilder does.

Differential Revision: http://reviews.llvm.org/D14333

llvm-svn: 254150

show more ...

[FIX] Use unreachable to indicate dead code and repair dominance

When we bail out early we make the partially build new code path
practically dead, though it was not unreachable. To remove domin

[FIX] Use unreachable to indicate dead code and repair dominance

When we bail out early we make the partially build new code path
practically dead, though it was not unreachable. To remove dominance
problems we now make it not only dead but also prevent the control
flow to join with the original code path, thus allow to use original
values after the SCoP without any PHI nodes.

This fixes bug 25447.

llvm-svn: 252420

show more ...

Verify IR after we bail out

The bail out in r252412 left the code generation without verifying the (so
far) generated IR. This will change now and ensure we always run the
verifier.

Suggested

Verify IR after we bail out

The bail out in r252412 left the code generation without verifying the (so
far) generated IR. This will change now and ensure we always run the
verifier.

Suggested-by: Tobias Grosser <[email protected]>
llvm-svn: 252419

show more ...

[FIX] Bail out if there is a dependence cycle between invariant loads

While the program cannot cause a dependence cycle between invariant
loads, additional constraints (e.g., to ensure finite lo

[FIX] Bail out if there is a dependence cycle between invariant loads

While the program cannot cause a dependence cycle between invariant
loads, additional constraints (e.g., to ensure finite loops) can
introduce them. It is hard to detect them in the SCoP description,
thus we will only check for them at code generation time. If such a
recursion is detected we will bail out the code generation and place a
"false" runtime check to guarantee the original code is used.

This fixes bug 25443.

llvm-svn: 252412

show more ...

polly/ADT: Remove implicit ilist iterator conversions, NFC

Remove all the implicit ilist iterator conversions from polly, in
preparation for making them illegal in ADT. There was one oddity I came

polly/ADT: Remove implicit ilist iterator conversions, NFC

Remove all the implicit ilist iterator conversions from polly, in
preparation for making them illegal in ADT. There was one oddity I came
across: at line 95 of lib/CodeGen/LoopGenerators.cpp, there was a
post-increment `Builder.GetInsertPoint()++`.

Since it was a no-op, I removed it, but I admit I wonder if it might be
a bug (both before and after this change)? Perhaps it should be a
pre-increment?

llvm-svn: 252357

show more ...

Remove independent blocks pass

Polly can now be used as a analysis only tool as long as the code
generation is disabled. However, we do not have an alternative to the
independent blocks pass i

Remove independent blocks pass

Polly can now be used as a analysis only tool as long as the code
generation is disabled. However, we do not have an alternative to the
independent blocks pass in place yet, though in the relevant cases
this does not seem to impact the performance much. Nevertheless, a
virtual alternative that allows the same transformations without
changing the input region will follow shortly.

llvm-svn: 250652

show more ...

Allow invariant loads in the SCoP description

This patch allows invariant loads to be used in the SCoP description,
e.g., as loop bounds, conditions or in memory access functions.

First we co

Allow invariant loads in the SCoP description

This patch allows invariant loads to be used in the SCoP description,
e.g., as loop bounds, conditions or in memory access functions.

First we collect "required invariant loads" during SCoP detection that
would otherwise make an expression we care about non-affine. To this
end a new level of abstraction was introduced before
SCEVValidator::isAffineExpr() namely ScopDetection::isAffine() and
ScopDetection::onlyValidRequiredInvariantLoads(). Here we can decide
if we want a load inside the region to be optimistically assumed
invariant or not. If we do, it will be marked as required and in the
SCoP generation we bail if it is actually not invariant. If we don't
it will be a non-affine expression as before. At the moment we
optimistically assume all "hoistable" (namely non-loop-carried) loads
to be invariant. This causes us to expand some SCoPs and dismiss them
later but it also allows us to detect a lot we would dismiss directly
if we would ask e.g., AliasAnalysis::canBasicBlockModify(). We also
allow potential aliases between optimistically assumed invariant loads
and other pointers as our runtime alias checks are sound in case the
loads are actually invariant. Together with the invariant checks this
combination allows to handle a lot more than LICM can.

The code generation of the invariant loads had to be extended as we
can now have dependences between parameters and invariant (hoisted)
loads as well as the other way around, e.g.,
test/Isl/CodeGen/invariant_load_parameters_cyclic_dependence.ll
First, it is important to note that we cannot have real cycles but
only dependences from a hoisted load to a parameter and from another
parameter to that hoisted load (and so on). To handle such cases we
materialize llvm::Values for parameters that are referred by a hoisted
load on demand and then materialize the remaining parameters. Second,
there are new kinds of dependences between hoisted loads caused by the
constraints on their execution. If a hoisted load is conditionally
executed it might depend on the value of another hoisted load. To deal
with such situations we sort them already in the ScopInfo such that
they can be generated in the order they are listed in the
Scop::InvariantAccesses list (see compareInvariantAccesses). The
dependences between hoisted loads caused by indirect accesses are
handled the same way as before.

llvm-svn: 249607

show more ...

Make ScopAnnotator a function-local variable to ensure it is freed at each run

When the ScopAnnotator was a class member variable some of the maps it contains
have not been properly cleared. As a re

Make ScopAnnotator a function-local variable to ensure it is freed at each run

When the ScopAnnotator was a class member variable some of the maps it contains
have not been properly cleared. As a result we had dangling pointers to
llvm::Value(s) which got detected by the AssertingVH we recently added.

No test case as this issue is hard to reproduce reliably as subsequent
optimizations need to delete some of the llvm::Values we still keep in our
lists.

llvm-svn: 249269

show more ...

Identify and hoist definitively invariant loads

As a first step in the direction of assumed invariant loads (loads
that are not written in some context) we now detect and hoist
definitively in

Identify and hoist definitively invariant loads

As a first step in the direction of assumed invariant loads (loads
that are not written in some context) we now detect and hoist
definitively invariant loads. These invariant loads will be preloaded
in the code generation and used in the optimized version of the SCoP.
If the load is only conditionally executed the preloaded version will
also only be executed under the same condition, hence we will never
access memory that wouldn't have been accessed otherwise. This is also
the most distinguishing feature to licm.

As hoisting can make statements empty we will simplify the SCoP and
remove empty statements that would otherwise cause artifacts in the
code generation.

Differential Revision: http://reviews.llvm.org/D13194

llvm-svn: 248861

show more ...

[NFC] Consistenly use commented and annotated ScopPass functions

The changes affect methods that are part of the Pass interface and
include:
- Comments that describe the methods purpose.

[NFC] Consistenly use commented and annotated ScopPass functions

The changes affect methods that are part of the Pass interface and
include:
- Comments that describe the methods purpose.
- A consistent use of the keywords override and virtual.
Additionally, the printScop method is now optional and removed from
SCoP passes that do not implement it.

llvm-svn: 248685

show more ...

Sort includes using Chandler's sort_includes.py script

llvm-svn: 248568

Merge TempScopInfo into ScopInfo

The TempScopInfo (-polly-analyze-ir) pass is removed and its work taken
over by ScopInfo (-polly-scops). Several tests depend on
-polly-analyze-ir and use -polly-sco

Merge TempScopInfo into ScopInfo

The TempScopInfo (-polly-analyze-ir) pass is removed and its work taken
over by ScopInfo (-polly-scops). Several tests depend on
-polly-analyze-ir and use -polly-scops instead which for the moment
prints the output of both passes. This again is not expected by some
other tests, especially those with negative searches, which have been
adapted.

Differential Version: http://reviews.llvm.org/D12694

llvm-svn: 247288

show more ...

Merge TempScopInfo.{cpp|h} into ScopInfo.{cpp|h}

This prepares for a series of patches that merges TempScopInfo into ScopInfo to
reduce Polly's code complexity. Only ScopInfo.{cpp|h} will be left th

Merge TempScopInfo.{cpp|h} into ScopInfo.{cpp|h}

This prepares for a series of patches that merges TempScopInfo into ScopInfo to
reduce Polly's code complexity. Only ScopInfo.{cpp|h} will be left thereafter.
Moving the code of TempScopInfo in one commit makes the mains diffs simpler to
understand.

In detail, merging the following classes is planned:
TempScopInfo into ScopInfo
TempScop into Scop
IRAccess into MemoryAccess

Only moving code, no functional changes intended.

Differential Version: http://reviews.llvm.org/D12693

llvm-svn: 247274

show more ...

[PM] Update Polly for the new AA infrastructure landed in r247167.

llvm-svn: 247198

Fix Polly after SCEV port to new pass manager

This fixes compilation after LLVM commit r245193.

llvm-svn: 245211