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

Sun Nov 13 16:27:32 PST 2011

Hi Tobias.

I worked on enabling Polly accepting non affine memory accesses and I
produced a patch.
I saw that there were a lot of updates in Polly recently, so I had to
redo a lot of the work I did and that slowed me quite a bit.
I tested the patch on some programs and it seems to work and not to
break anything, but you know the topic much better than me, so if you
find something wrong please tell me! (at least it shouldn't produce a
crash I believe ... I tested the patch quite a lot from that point of
view ...). The patch is in the attachment to this mail and was last
tested on LLVM SVN revision 144502 .

I also found a bug in polly or ISL/GMP libraries. If polly encounters
an array access of type:

A[i][i]

it enters an infinite loop (I believe it is an infinite loop because I
waited 5 minutes and it didn't terminate compiling a code that was
like 15 lines long).  I tried to track down the problem with gdb , but
it seems to be in some gmp function called by ISL of which I'm not a
very expert of.
This is the backtrace of the manually terminated process in gdb:
(gdb) bt
#0  0x0000000101828422 in __gmpn_gcd_1 ()
#1  0x00000001018102ea in __gmpz_gcd ()
#2  0x0000000101cd0f33 in isl_aff_scale_down ()
#3  0x0000000101a5a175 in polly::MemoryAccess::MemoryAccess
(this=0x101911ed0, Access=@0x10190fc48, Statement=0x10190ffa0) at
/Users/Kariddi/Documents/Sviluppo/Tesi/llvm/tools/polly/lib/Analysis/ScopInfo.cpp:308
#4  0x0000000101a5b22a in polly::ScopStmt::buildAccesses
(this=0x10190ffa0, tempScop=@0x10190eb70, CurRegion=@0x10190eed0) at
/Users/Kariddi/Documents/Sviluppo/Tesi/llvm/tools/polly/lib/Analysis/ScopInfo.cpp:588
#5  0x0000000101a5bc08 in polly::ScopStmt::ScopStmt (this=0x10190ffa0,
parent=@0x10190fdf0, tempScop=@0x10190eb70, CurRegion=@0x10190eed0,
bb=@0x101905bd0, NestLoops=@0x7fff5fbfec20, Scatter=@0x7fff5fbfebe0)
at /Users/Kariddi/Documents/Sviluppo/Tesi/llvm/tools/polly/lib/Analysis/ScopInfo.cpp:716
#6  0x0000000101a5b86d in polly::ScopStmt::ScopStmt (this=0x10190ffa0,
parent=@0x10190fdf0, tempScop=@0x10190eb70, CurRegion=@0x10190eed0,
bb=@0x101905bd0, NestLoops=@0x7fff5fbfec20, Scatter=@0x7fff5fbfebe0)
at /Users/Kariddi/Documents/Sviluppo/Tesi/llvm/tools/polly/lib/Analysis/ScopInfo.cpp:699
#7  0x0000000101a5d460 in polly::Scop::buildScop (this=0x10190fdf0,
tempScop=@0x10190eb70, CurRegion=@0x10190eed0,
NestLoops=@0x7fff5fbfec20, Scatter=@0x7fff5fbfebe0, LI=@0x101909a40)
at /Users/Kariddi/Documents/Sviluppo/Tesi/llvm/tools/polly/lib/Analysis/ScopInfo.cpp:1032
#8  0x0000000101a5d3ab in polly::Scop::buildScop (this=0x10190fdf0,
tempScop=@0x10190eb70, CurRegion=@0x10190ef40,
NestLoops=@0x7fff5fbfec20, Scatter=@0x7fff5fbfebe0, LI=@0x101909a40)
at /Users/Kariddi/Documents/Sviluppo/Tesi/llvm/tools/polly/lib/Analysis/ScopInfo.cpp:1025
#9  0x0000000101a5d0de in polly::Scop::Scop (this=0x10190fdf0,
tempScop=@0x10190eb70, LI=@0x101909a40, ScalarEvolution=@0x10190b510,
Context=0x1019094b0) at
/Users/Kariddi/Documents/Sviluppo/Tesi/llvm/tools/polly/lib/Analysis/ScopInfo.cpp:918
#10 0x0000000101a5cf05 in polly::Scop::Scop (this=0x10190fdf0,
tempScop=@0x10190eb70, LI=@0x101909a40, ScalarEvolution=@0x10190b510,
Context=0x1019094b0) at
/Users/Kariddi/Documents/Sviluppo/Tesi/llvm/tools/polly/lib/Analysis/ScopInfo.cpp:907
#11 0x0000000101a5df23 in polly::ScopInfo::runOnRegion
(this=0x101909440, R=0x10190ef40, RGM=@0x10190ce80) at
/Users/Kariddi/Documents/Sviluppo/Tesi/llvm/tools/polly/lib/Analysis/ScopInfo.cpp:1085
#12 0x00000001003b5641 in llvm::RGPassManager::runOnFunction
(this=0x10190ce80, F=@0x1019052a0) at
/Users/Kariddi/Documents/Sviluppo/Tesi/llvm/lib/Analysis/RegionPass.cpp:96
#13 0x00000001005e90d1 in llvm::FPPassManager::runOnFunction
(this=0x10190a240, F=@0x1019052a0) at
/Users/Kariddi/Documents/Sviluppo/Tesi/llvm/lib/VMCore/PassManager.cpp:1512
#14 0x00000001005e943d in llvm::FPPassManager::runOnModule
(this=0x10190a240, M=@0x1019067f0) at
/Users/Kariddi/Documents/Sviluppo/Tesi/llvm/lib/VMCore/PassManager.cpp:1534
#15 0x00000001005e96c5 in llvm::MPPassManager::runOnModule
(this=0x1019089e0, M=@0x1019067f0) at
/Users/Kariddi/Documents/Sviluppo/Tesi/llvm/lib/VMCore/PassManager.cpp:1588
#16 0x00000001005e9e1c in llvm::PassManagerImpl::run
(this=0x1019086a0, M=@0x1019067f0) at
/Users/Kariddi/Documents/Sviluppo/Tesi/llvm/lib/VMCore/PassManager.cpp:1672
#17 0x00000001005ea301 in llvm::PassManager::run (this=0x7fff5fbffa38,
M=@0x1019067f0) at
/Users/Kariddi/Documents/Sviluppo/Tesi/llvm/lib/VMCore/PassManager.cpp:1716
#18 0x00000001000127d6 in main (argc=7, argv=0x7fff5fbffb38) at
/Users/Kariddi/Documents/Sviluppo/Tesi/llvm/tools/opt/opt.cpp:706
(gdb)

And this is the code that causes the problem:

#include <stdio.h>
#include <stdlib.h>

int main()
{
       int A[1024][1024];
       int i,j,k,h;
       const int x = 0, y=0;
       for (i = 1; i < 1024; i++)
               for (j = 1; j  < 1024 ; j++)
               {
                               A[i][j] = A[j][j];
               }
       printf("Random Value: %d", A[rand() % 1024*1024]);

       return 0;
}

I actually don't know if it is an ISL bug or an improper use by polly.
To compile isl I use gmp-5.0.2

Marcello

2011/11/3 Marcello Maggioni <hayarms at gmail.com>:
> The patch seems to work, great! :D
>
> 2011/11/3 Tobias Grosser <tobias at grosser.es>:
>> 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: accept_affine.patch
Type: application/octet-stream
Size: 5480 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20111114/e07ac47b/attachment.obj>