[LLVMdev] Polly and non affine branches in ScoPs

[Tobias Grosser]

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