[LLVMdev] Polly and non affine branches in ScoPs

[Tobias Grosser]

On 02/14/2012 03:16 PM, Marcello Maggioni wrote:
> 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).

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