[LLVMdev] Polly and non affine branches in ScoPs

[Marcello Maggioni]

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>