llvm dev - Feb 2012 - [LLVMdev] 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

On 02/08/2012 08:08 PM, Marcello Maggioni wrote:
> 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

2012/2/12 Tobias Grosser <tobias at grosser.es>:
> On 02/08/2012 08:08 PM, Marcello Maggioni wrote:
>>
>> 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 :)
>>  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 ? :P (I think I know the answer, just to be sure).

Marcello
-------------- next part --------------
A non-text attachment was scrubbed...
Name: testcase2.ll
Type: application/octet-stream
Size: 999 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120214/6fe88356/attachment.obj>