[LLVMdev] How to make Polly ignore some non-affine memory accesses

[Tobias Grosser]

On 11/02/2011 11:17 AM, Marcello Maggioni wrote:
> Mmm I found out a very strange behavior (to me) of the SCEV analysis
> of the loop bound of the external loop I posted.
> When in ScopDetection it gets the SCEV of the external loop bound in
> the "isValidLoop()" function with:
>      const SCEV *LoopCount = SE->getBackedgeTakenCount(L);
>
> It returns a SCEVCouldNotCompute, but if I change the "if" block
> inside the loop from:
>      if (i+j>  1000)
> to:
>      if (i>  1000)
>
> that SCEV results valid.
>
> Later in the ScopInfo pass it crashes analyzing the SCEV of the
> comparison expression (in buildConditionSets ) . It's like if it
> recognizes that "i" is a recurring expression that depends on the
> execution of a loop, but can't derive that loop, and segfaults in
> getLoopDepth ...
>
> Seems like a bug of the SCEV engine to me., but I'm not sure :(

Hi Marcello,

sorry for taking so long to reply. I just had a look at your test case
and found the problem. What happens is that Polly fails to accept the
outer loop (an unrelated issue), such that only the inner loop is 
detected as a scop (you can verify this with -view-scops). Now when
building the polyhedral representation we analyze the SCEV expressions
in the inner loop (the scop). Here the condition has an expression that
looks similar to this:

{1, +, 1024}<i> + {1,+,1024}<j>

We translate this expression. When reaching {1, +, 1024}<i> we do not
check if it is part of the scop and always handle it as a loop index.
This is incorrect and fails when we try to find the corresponding loop
in the scop. The right thing to do is to handle this expression as a 
parameter.

Consequently this is no SCEV bug, but an ordinary Polly bug. It most 
probably slipped in when I recently refactored the SCEV parsing. I 
attached a hackish patch that should fix the issue for exactly this
test case. Can you check it works for you?

I will commit a complete fix later on.

Cheers
Tobi
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Hack-around-parameter-handled-as-IV-issue.patch
Type: text/x-diff
Size: 1916 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20111103/03a95638/attachment.patch>