statement naming

- A recent ppcg/isl update caused the grid/block size upper bounds to
deviate by one from the oracle. This is not an effect that's visible at
runtime.
- Statement naming changed in polly. Update the testcases.

llvm-svn: 333090

An assertion was not prepared to be passed a nullptr because the
out-of-quota limit was exceeded.  Bail-out before the assertion
since the assertion does not apply on out-of-quote.

This fixes llvm.org/PR37477.

llvm-svn: 332488

nullptr is not a valid affine expression, and none of the callers check
for null, so we eventually hit an isl error and crash.

Instead, invalidate the scop and return a constant zero.

Differential Revision: https://reviews.llvm.org/D46445

llvm-svn: 332309

Rename variable to retainedNodes. This unbreaks the Polly builds.

llvm-svn: 331960

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

This test case does not require undef to be present in branch
conditions. Replace these undef values with true/false values to clarify
the control-flow required to reach the loop under testing.

llvm-svn: 331744

Summary:
Occasionally you need an include or similar things to be configured
when making a new testcase. Allow passing these to the script and down to the
compiler calls.

Reviewers: grosser, Meinersbur, bollu

Reviewed By: Meinersbur

Subscribers: bollu, llvm-commits, pollydev

Differential Revision: https://reviews.llvm.org/D46359

llvm-svn: 331364

Add the options -polly-codegen-trace-stmts and
-polly-codegen-trace-scalars. When enabled, adds a call to the
beginning of every generated statement that prints the executed
statement instance. With -polly-codegen-trace-scalars, it also prints
the value of all scalars that are used in the statement, and PHIs
defined in the beginning of the statement.

Differential Revision: https://reviews.llvm.org/D45743

llvm-svn: 330864

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

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

Make sure we also counts scops not containing any loops.

llvm-svn: 330285

Summary:
As of rL329273, LLVM has a mechanism to load new-pm plugins in opt. Use
this API in Polly.

Reviewers: grosser, Meinersbur, bollu

Reviewed By: grosser, Meinersbur

Subscribers: lksbhm, bollu, pollydev, llvm-commits

Differential Revision: https://reviews.llvm.org/D45484

llvm-svn: 330181

A check in assert-builds was meant to verify that a load provides a
value in all statement instances (i.e. its domain).  The domain is
commonly gist'ed within the parameter context to contain fewer
constraints.  However, statement instances outside the context are
no valid executions, hence the value provided can be undefined.

Refine the check for valid loads to only needed to be defined within
the SCoP context.

In addition, the JSONImporter had to be changed to allow importing
access relations that are broader than the current access relation,
but still defined over all statement instances.

This should fix the compiler crash in test-suite's oggenc of the
-polly-process-unprofitable buildbot.

llvm-svn: 329655

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

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

This patch removes the heuristic in
- Polly :: lib/Support/ScopHelper.cpp

The heuristic forces blocks that directly follow a loop header to not to be considered error blocks.
It was introduced in r249611 with the following commit message:

>   This replaces the support for user defined error functions by a
>   heuristic that tries to determine if a call to a non-pure function
>   should be considered "an error". If so the block is assumed not to be
>   executed at runtime. While treating all non-pure function calls as
>   errors will allow a lot more regions to be analyzed, it will also
>   cause us to dismiss a lot again due to an infeasible runtime context.
>   This patch tries to limit that effect. A non-pure function call is
>   considered an error if it is executed only in conditionally with
>   regards to a cheap but simple heuristic.

In the code below `CCK_Abort2()` would be considered as an error block, but not `CCK_Abort1()` due to this heuristic.
```
for (int i = 0; i < n; i+=1) {
  if (ErrorCondition1)
    CCK_Abort1(); // No __attribute__((noreturn))
  if (ErrorCondition2)
    CCK_Abort2(); // No __attribute__((noreturn))
}
```

This does not seem useful. Checking error conditions in the beginning of some work is quite common. It causes a switch default-case to be not considered an error block in SPEC's cactuBSSN. The comment justifying the heuristic mentions a "load", which does not seem to be applicable here. It has been proposed to remove the heuristic.

In addition, the patch fixes the following test cases:
- Polly :: ScopDetect/mod_ref_read_pointer.ll
- Polly :: ScopInfo/max-loop-depth.ll
- Polly :: ScopInfo/mod_ref_access_pointee_arguments.ll
- Polly :: ScopInfo/mod_ref_read_pointee_arguments.ll
- Polly :: ScopInfo/mod_ref_read_pointer.ll
- Polly :: ScopInfo/mod_ref_read_pointers.ll

The test cases failed after removing the heuristic.

Differential Revision: https://reviews.llvm.org/D45274



Contributed-by: Lorenzo Chelini <l.chelini@icloud.com>
llvm-svn: 329548

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

llvm-svn: 327857

Summary:
When building polly as part of the monorepo (actually, as part of any setup
using LLVM_ENABLE_PROJECTS), the LLVMPolly library used in the lit tests ends
up in a different directory in the build tree than in an in-tree build

Reviewers: Meinersbur, grosser, bollu

Reviewed By: Meinersbur

Subscribers: mgorny, bollu, pollydev, llvm-commits

Differential Revision: https://reviews.llvm.org/D44078

llvm-svn: 326702

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

This update:

  - Removes several deprecated functions (e.g., isl_band).
  - Improves the pretty-printing of sets by detecting modulos and "false"
    equalities.
  - Minor improvements to coalescing and increased robustness of the isl
    scheduler.

This update does not yet include isl commit isl-0.18-90-gd00cb45
(isl_pw_*_alloc: add missing check for compatible spaces, Wed Sep 6 12:18:04
2017 +0200), as this additional check is too tight and unfortunately causes
two test case failures in Polly. A patch has been submitted to isl and will be
included in the next isl update for Polly.

llvm-svn: 325557

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

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

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

except Darwin and Windows.  This prevents inserting an environment
variable with an empty name (which is illegal and leads to a Python
exception) on any of the BSDs.

llvm-svn: 323041

Summary:
 Upstream LLVM is changing the the prototypes of the @llvm.memcpy/memmove/memset
intrinsics. This change updates the polly tests for this change.

 The @llvm.memcpy/memmove/memset intrinsics currently have an explicit argument
which is required to be a constant integer. It represents the alignment of the
dest (and source), and so must be the minimum of the actual alignment of the
two.

 This change removes the alignment argument in favour of placing the alignment
attribute on the source and destination pointers of the memory intrinsic call.

 For example, code which used to read:
  call void @llvm.memcpy.p0i8.p0i8.i32(i8* %dest, i8* %src, i32 100, i32 4, i1 false)
will now read
  call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 4 %dest, i8* align 4 %src, i32 100, i1 false)

 At this time the source and destination alignments must be the same (Step 1).
Step 2 of the change, to be landed shortly, will relax that contraint and allow
the source and destination to have different alignments.

llvm-svn: 322963

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

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

Memory transfer instructions take two pointers. It is not defined to
which of those a noalias annotation applies. To ensure correctness,
do not add noalias annotations to memcpy/memmove instructions anymore.

The caused a miscompile with test-suite's MultiSource/Applications/obsequi.
Since r321138, the MemCpyOpt pass would remove memcpy/memmove calls if
known to copy uninitialized memory. In that case, it was initialized
by another memcpy, but the annotation for the target pointer said
it would not alias. The annotation was actually meant for the source
pointer, which was was an alloca and could not alias with the target
pointer.

llvm-svn: 321371

If an out-of-quota error occurred, the last error would be
isl_error_quota unless a different error occured. We typically check
whether the max-operations occured by comparing to that error value
after leaving the quota guard. This would check whether there ever
was a quota-error, not just in the last quota guards.

The observable bug occurred if the max-operations limit was reached in
DeLICM, and if -polly-dependences-computout=0, DependenceInfo would
think that the quota for computing dependencies was the reason,
i.e., fail the operation even if the calculation itself was successful.

Fix by reseting the last error to isl_error_none when entering a
quota guard, signaling that no quota error occured unless in the
guard's scope.

llvm-svn: 321329

Introduce -polly-stmt-granularity=store option.

Contributed-by: Nandini Singhal <cs15mtech01004@iith.ac.in>

Differential Revision: https://reviews.llvm.org/D37337

llvm-svn: 320360

Using numeric registers is flaky, since as soon as one additional
instruction is generated by us, all the tests need to be adapted.

llvm-svn: 319544

Summary:
This can be seen as a follow-up on my previous differential [D33411](https://reviews.llvm.org/D33411).
We received a bug report where this error was triggered. I have tried my best to recreate the issue in a minimal lit testcase which is also part of this differential.

I only handle return instructions as predecessors to a virtual TLR-exit right now. From inspecting the codebase, it seems `unreachable` instructions may also be of interest here. If requested, I can extend my patches to consider them as well. I would also apply this on `ScopHelper.cpp::isErrorBlock` (see D33411), of course.

Reviewers: philip.pfaffe, bollu

Reviewed By: bollu

Subscribers: Meinersbur, pollydev, llvm-commits

Tags: #polly

Differential Revision: https://reviews.llvm.org/D40492

llvm-svn: 319431

Isl does not allow generating isl_ast_expr from an isl_pw_aff that has an
empty domain (i.e. has no pieces). We already detected the case if the
isl_pw_aff comes with an empty domain.

isl_ast_build also considers the domain empty if it is disjoint with the
parameter context (e.g. parameters values that we exclude by runtime
versioning).

Intersect the access relation domain with the parameter context to
also detect such practically empty access domains. The effective
pointer used in the generated code is unimportand because it will never
be executed.

This fixes llvm.org/PR35362

llvm-svn: 318806

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

Represent PHIs by their incoming values instead of an opaque value of
themselves. This allows ForwardOpTree to "look through" the PHIs and
forward the incoming values since forwardings PHIs is currently not
supported.

This is particularly useful to cope with PHIs inserted by GVN LoadPRE.
The incoming values all resolve to a load from a single array element
which then can be forwarded.

It should in theory also reduce spurious conflicts in value mapping
(DeLICM), but I have not yet found a profitable case yet, so it is
not included here.

To avoid transitive closure and potentially necessary overapproximations
of those, PHIs that may reference themselves are excluded from
normalization and keep their opaque self-representation.

Differential Revision: https://reviews.llvm.org/D39333

llvm-svn: 317008

ForwardOpTree may already transform a scalar access to an array
accesses. The access remains implicit (isOriginalScalarKind(), meaning
that the access is always executed at the begin/end of a statement), but
targets an array (isLatestArrayKind(), which is unrelated to whether the
execution is implicit/explicit).

Fix by properly using isOriginalXXX() to determine execution order.

This fixes the buildbots on MultiSource/Benchmarks/DOE-ProxyApps-C/miniGMG.

llvm-svn: 316995

When collecting base pointers that need to be made available in parallel
subfunctions, use the base pointer associated with the latest
ScopArrayInfo, instead of the original one.

llvm-svn: 316983

Add missing %loadPolly directive to support out of tree builds. One of
the changes is somewhat bigger, because the directive turns on LLVM
names, and the testcase deosn't use those.

llvm-svn: 316870

For scalar accesses, change the access target to an array element that
is known to contain the same value.

This may become an alternative to forwardKnownLoad which creates new
loads (and therefore closer to forwarding speculatives). Reloading does
not require the known value originating from a load, but can be a store
as well.

Differential Revision: https://reviews.llvm.org/D39325

llvm-svn: 316766