Polly and non affine branches in ScoPs

Hi, I'm using Polly to analyze memory access patterns for an
university project and I'm trying to get polly working on some loops
that polly marks as "containing non affine branches" .

From what I understand polly skips Scops that contain these branches

(which comprises something like "if (i % 2 == 0)" where i is a loop
varying variable) because these kind of branches can make , in
practice , non affine the accesses to the memory operands even if the
array subscript expression is affine itself, but I need a much more
"flow-insensitive" and less precise evaluation of the memory access
patterns , so, I would like polly to continue it's analysis on the
memory accesses of the scops even if these branches are present,
because even if the analysis gets wrong thanks to these branches it is
not that big of a deal for my project.

Can't this feature be implemented like the one that ignores the non
affine memory subscripts in ScoPs? To implement this would be needed a
change in TempScop and ScopInfo or a change only in the code that
verifies the branches in ScopDetection would be enough?

Thanks

Marcello

Hi, I'm using Polly to analyze memory access patterns for an
university project and I'm trying to get polly working on some loops
that polly marks as "containing non affine branches" .

Hi Marcello,

sorry for the long delay.

From what I understand polly skips Scops that contain these branches
(which comprises something like "if (i % 2 == 0)" where i is a loop
varying variable) because these kind of branches can make , in
practice , non affine the accesses to the memory operands even if the
array subscript expression is affine itself, but I need a much more
"flow-insensitive" and less precise evaluation of the memory access
patterns , so, I would like polly to continue it's analysis on the
memory accesses of the scops even if these branches are present,
because even if the analysis gets wrong thanks to these branches it is
not that big of a deal for my project.

Can't this feature be implemented like the one that ignores the non
affine memory subscripts in ScoPs? To implement this would be needed a
change in TempScop and ScopInfo or a change only in the code that
verifies the branches in ScopDetection would be enough?

OK. So here are several issues.

First of all, the following code is perfectly affine:

for (i
   if (i % 2 > 5)
     ...

A modulo were the right side is an integer constant, can easily be represented within the polyhedral model. We currently probably don't accept it, as scalar evolution may not be able to handle such modulo operations. If you post an actual test case, we can see how this can be solved.

To support branches, that are really non-affine represented, there are two choices:

1. You just want dependency analysis to be working.

In this case, you could just ignore the condition and conceptually
translate this code:

if COND then A else B

into

A;
B;

Where all memory accesses in A and B are may-write and may-read accesses.
This should give you a conservative dependency analysis for non-affine branches.

2. You also want to apply transformations and do code generation.

This requires techniques as described in the paper:

"The Polyhedral Model Is More Widely Applicable Than You Think"

Cheers
Tobi

Hi, I'm using Polly to analyze memory access patterns for an
university project and I'm trying to get polly working on some loops
that polly marks as "containing non affine branches" .

Hi Marcello,

sorry for the long delay.

Don't worry for that :slight_smile:

From what I understand polly skips Scops that contain these branches
(which comprises something like "if (i % 2 == 0)" where i is a loop
varying variable) because these kind of branches can make , in
practice , non affine the accesses to the memory operands even if the
array subscript expression is affine itself, but I need a much more
"flow-insensitive" and less precise evaluation of the memory access
patterns , so, I would like polly to continue it's analysis on the
memory accesses of the scops even if these branches are present,
because even if the analysis gets wrong thanks to these branches it is
not that big of a deal for my project.

Can't this feature be implemented like the one that ignores the non
affine memory subscripts in ScoPs? To implement this would be needed a
change in TempScop and ScopInfo or a change only in the code that
verifies the branches in ScopDetection would be enough?

OK. So here are several issues.

First of all, the following code is perfectly affine:

for (i
if (i % 2 > 5)
...

A modulo were the right side is an integer constant, can easily be
represented within the polyhedral model. We currently probably don't accept
it, as scalar evolution may not be able to handle such modulo operations. If
you post an actual test case, we can see how this can be solved.

To support branches, that are really non-affine represented, there are two
choices:

1. You just want dependency analysis to be working.

In this case, you could just ignore the condition and conceptually
translate this code:

if COND then A else B

into

A;
B;

Where all memory accesses in A and B are may-write and may-read accesses.
This should give you a conservative dependency analysis for non-affine
branches.

2. You also want to apply transformations and do code generation.

This requires techniques as described in the paper:

"The Polyhedral Model Is More Widely Applicable Than You Think"

Cheers
Tobi

I'm interested in something that sounds like option 1. I'm not
interested of code generation.

Attached is a an handwritten testcase of the situation I'm into.

ScopDetection refuses to analyze the external loop because there is a
branch that depends on an SCEVUnknown generated inside the same region
(SCEVValidator.cpp:267 is the check that returns invalid).

With "this code X into Y" you mean at the source level or at the IR
level ? :stuck_out_tongue: (I think I know the answer, just to be sure).

Marcello

testcase2.ll (999 Bytes)

To just check if it is working, I would just try it at the source level. Later on you might either do it at the LLVM-IR level, or just conceptually within Polly. Meaning, that you read the IR and in case you cannot analyze it, you just assume both branches are taken.

We could try to implement the analysis in a way, that it matches the analysis part of solution 2). This would allow us to commit it directly into Polly.

Tobi