Marcello Maggioni
2011-Nov-02 11:17 UTC
[LLVMdev] How to make Polly ignore some non-affine memory accesses
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 :(
2011/11/1 Marcello Maggioni <hayarms at
gmail.com>:> Mmm, this code seems to kill polly:
>
> #include <stdio.h>
> #include <stdlib.h>
>
> int main()
> {
> char *B;
> int i,j,k,h;
> const int x = 0, y=0;
> B = (char *)malloc(sizeof(char)*1024*1024);
>
> for (i = 1; i < 1024; i++)
> for (j = 1; j < 1024; j++)
> {
> if (i+j > 1000)
> B[j] = i;
> }
> printf("Random Value: %d", B[rand() % 1024*1024]);
>
> return 0;
> }
>
> running:
>
> opt -load ${PATH_TO_POLLY_LIB}/LLVMPolly.dylib -polly-scops -analyze
> code.preopt.ll
>
> I get:
>
> Printing analysis 'Polly - Create polyhedral description of Scops'
for
> region: 'for.body3 => for.inc.single_exit' in function
'main':
> Invalid Scop!
> 0 libLLVM-3.1svn.dylib 0x0000000103fab905 _ZL15PrintStackTracePv + 53
> 1 libLLVM-3.1svn.dylib 0x0000000103fabf79 _ZL13SignalHandleri + 361
> 2 libsystem_c.dylib 0x00007fff94c8acfa _sigtramp + 26
> 3 libLLVM-3.1svn.dylib 0x0000000103526810
> llvm::SmallVectorTemplateCommon<llvm::SCEV
> const*>::operator[](unsigned int) + 128
> 4 LLVMPolly.dylib 0x0000000106867af8
> SCEVAffinator::getLoopDepth(llvm::Loop const*) + 72
> 5 LLVMPolly.dylib 0x00000001068676c7
> SCEVAffinator::visitAddRecExpr(llvm::SCEVAddRecExpr const*) + 247
> 6 LLVMPolly.dylib 0x000000010686710b
> llvm::SCEVVisitor<SCEVAffinator, isl_pw_aff*>::visit(llvm::SCEV
> const*) + 283
> 7 LLVMPolly.dylib 0x0000000106866f71
> SCEVAffinator::visit(llvm::SCEV const*) + 449
> 8 LLVMPolly.dylib 0x000000010686766c
> SCEVAffinator::visitAddRecExpr(llvm::SCEVAddRecExpr const*) + 156
> 9 LLVMPolly.dylib 0x000000010686710b
> llvm::SCEVVisitor<SCEVAffinator, isl_pw_aff*>::visit(llvm::SCEV
> const*) + 283
> 10 LLVMPolly.dylib 0x0000000106866f71
> SCEVAffinator::visit(llvm::SCEV const*) + 449
> 11 LLVMPolly.dylib 0x000000010685fd49
> SCEVAffinator::getPwAff(polly::ScopStmt const*, llvm::SCEV const*,
> llvm::Value const*) + 57
> 12 LLVMPolly.dylib 0x000000010685d076
> polly::ScopStmt::buildConditionSet(polly::Comparison const&) const +
> 54
> 13 LLVMPolly.dylib 0x000000010685d414
> polly::ScopStmt::addConditionsToDomain(isl_set*, polly::TempScop&,
> llvm::Region const&) const + 196
> 14 LLVMPolly.dylib 0x000000010685d519
> polly::ScopStmt::buildDomain(polly::TempScop&, llvm::Region const&)
> const + 169
> 15 LLVMPolly.dylib 0x000000010685d90d
> polly::ScopStmt::ScopStmt(polly::Scop&, polly::TempScop&,
llvm::Region
> const&, llvm::BasicBlock&,
llvm::SmallVectorImpl<llvm::Loop*>&,
> llvm::SmallVectorImpl<unsigned int>&) + 861
> 16 LLVMPolly.dylib 0x000000010685d59d
> polly::ScopStmt::ScopStmt(polly::Scop&, polly::TempScop&,
llvm::Region
> const&, llvm::BasicBlock&,
llvm::SmallVectorImpl<llvm::Loop*>&,
> llvm::SmallVectorImpl<unsigned int>&) + 77
> 17 LLVMPolly.dylib 0x000000010685ef60
> polly::Scop::buildScop(polly::TempScop&, llvm::Region const&,
> llvm::SmallVectorImpl<llvm::Loop*>&,
llvm::SmallVectorImpl<unsigned
> int>&, llvm::LoopInfo&) + 624
> 18 LLVMPolly.dylib 0x000000010685eeab
> polly::Scop::buildScop(polly::TempScop&, llvm::Region const&,
> llvm::SmallVectorImpl<llvm::Loop*>&,
llvm::SmallVectorImpl<unsigned
> int>&, llvm::LoopInfo&) + 443
> 19 LLVMPolly.dylib 0x000000010685ebee
> polly::Scop::Scop(polly::TempScop&, llvm::LoopInfo&,
> llvm::ScalarEvolution&, isl_ctx*) + 462
> 20 LLVMPolly.dylib 0x000000010685ea15
> polly::Scop::Scop(polly::TempScop&, llvm::LoopInfo&,
> llvm::ScalarEvolution&, isl_ctx*) + 53
> 21 LLVMPolly.dylib 0x000000010685f8f3
> polly::ScopInfo::runOnRegion(llvm::Region*, llvm::RGPassManager&) +
> 227
> 22 libLLVM-3.1svn.dylib 0x00000001034f4dc1
> llvm::RGPassManager::runOnFunction(llvm::Function&) + 1185
> 23 libLLVM-3.1svn.dylib 0x0000000103a0f261
> llvm::FPPassManager::runOnFunction(llvm::Function&) + 497
> 24 libLLVM-3.1svn.dylib 0x0000000103a0f5cd
> llvm::FPPassManager::runOnModule(llvm::Module&) + 125
> 25 libLLVM-3.1svn.dylib 0x0000000103a0f855
> llvm::MPPassManager::runOnModule(llvm::Module&) + 549
> 26 libLLVM-3.1svn.dylib 0x0000000103a0ffac
> llvm::PassManagerImpl::run(llvm::Module&) + 172
> 27 libLLVM-3.1svn.dylib 0x0000000103a10491
> llvm::PassManager::run(llvm::Module&) + 33
> 28 opt 0x00000001032dbb76 main + 6966
> 29 opt 0x00000001032ca5a4 start + 52
> Stack dump:
> 0. Program arguments: opt -load
> /Users/Kariddi/Documents/Sviluppo/Tesi/git-prefix/lib//LLVMPolly.dylib
> -polly-scops -analyze strange_pointer.preopt.ll
> 1. Running pass 'Function Pass Manager' on module
'strange_pointer.preopt.ll'.
> 2. Running pass 'Region Pass Manager' on function
'@main'
> 3. Running pass 'Polly - Create polyhedral description of
Scops' on
> basic block '%for.body3.single_entry'
> ./compile_ex.sh: line 9: 36824 Segmentation fault: 11 opt -load
> ${PATH_TO_POLLY_LIB}/LLVMPolly.dylib -polly-scops -analyze
> $1.preopt.ll
>
> Also I want to ask:
>
> Why Bitcast instructions make polly discard scops?
>
> Thanks
> Marcello
>
> 2011/10/27 Marcello Maggioni <hayarms at gmail.com>:
>> Perfect, thank you very much :)
>>
>> 2011/10/26 Tobias Grosser <tobias at grosser.es>:
>>> On 10/24/2011 11:32 PM, Marcello Maggioni wrote:
>>>>
>>>> Strange , with --enable-shared (I use auto tool by the way ...)
it gives:
>>>>
>>>> MacBook-Pro-di-Marcello:examples Kariddi$ ./compile_ex.sh
>>>> not_so_simple_loop
>>>> clang (LLVM option parsing): Unknown command line argument
>>>> '-enable-polly-viewer'. Try: 'clang (LLVM option
parsing) -help'
>>>> clang (LLVM option parsing): Did you mean
'-enable-polly-vector'?
>>>>
>>>> Seems like it doesn't compile the viewer option ...
>>>
>>> This error message is because the option name was changed. Try
-polly-show.
>>>
>>> Furthermore, I plan to commit the change to clang, that solves the
failure
>>> when loading clang. Though it will probably take a day until it
gets through
>>> review.
>>>
>>> Cheers
>>> Tobi
>>>
>>
>
Tobias Grosser
2011-Nov-03 08:56 UTC
[LLVMdev] How to make Polly ignore some non-affine memory accesses
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>
Marcello Maggioni
2011-Nov-14 00:27 UTC
[LLVMdev] How to make Polly ignore some non-affine memory accesses
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>
Tobias Grosser
2011-Nov-14 08:41 UTC
[LLVMdev] How to make Polly ignore some non-affine memory accesses
On 11/14/2011 01:24 AM, Marcello Maggioni wrote:> Hi Tobias. > > I worked on enabling Polly accepting non affine memory accesses and I > produced a patch.Great.> 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.Ups, sorry! However, I believe without these changes detecting non-affine memory access functions would have been a lot more complicated.> 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 .OK. Review is inlined in the patch.> 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.[remove backtrace & code]> 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.2I will look into this.> --- ./include/polly/ScopDetection.h 2011-11-13 02:37:59.000000000 +0100 > +++ ../llvm2/tools/polly/./include/polly/ScopDetection.h 2011-11-13 01:11:17.000000000 +0100 > @@ -145,6 +145,8 @@ > /// @return True if the call instruction is valid, false otherwise. > static bool isValidCallInst(CallInst&CI); > > + const Value *GetBaseValue(const SCEV *S) const;Why is this function needed? For me it looks like it implements the same as SCEVValue *Operand = dyn_cast<SCEVValue>(getPointerOperand()) if (!Operand) return invalid Value; return Operand->getValue();> /// @brief Check if a memory access can be part of a Scop. > /// > /// @param Inst The instruction accessing the memory. > --- ./include/polly/TempScopInfo.h 2011-11-13 02:37:59.000000000 +0100 > +++ ../llvm2/tools/polly/./include/polly/TempScopInfo.h 2011-11-13 02:34:47.000000000 +0100 > @@ -45,12 +45,13 @@ > private: > unsigned ElemBytes; > TypeKind Type; > + bool is_affine;I think IsAffine matches more the LLVM coding conventions.> > public: > explicit IRAccess (TypeKind Type, const Value *BaseAddress, > - const SCEV *Offset, unsigned elemBytes) > + const SCEV *Offset, unsigned elemBytes, bool affine)'affine' should start with an uppercase letter. Polly itself has some inconsistent naming, but we started to follow the LLVM coding conventions since a while.> : BaseAddress(BaseAddress), Offset(Offset), > - ElemBytes(elemBytes), Type(Type) {} > + ElemBytes(elemBytes), Type(Type), is_affine(affine) {} > > enum TypeKind getType() const { return Type; } > > @@ -60,7 +61,10 @@ > > unsigned getElemSizeInBytes() const { return ElemBytes; } > > + bool isAffine() const { return is_affine; } > + > bool isRead() const { return Type == READ; } > + > }; > > class Comparison { > --- ./lib/Analysis/ScopDetection.cpp 2011-11-13 02:38:06.000000000 +0100 > +++ ../llvm2/tools/polly/./lib/Analysis/ScopDetection.cpp 2011-11-13 01:28:00.000000000 +0100 > @@ -226,6 +226,24 @@ > return false; > } > > +const Value *ScopDetection::GetBaseValue(const SCEV *S) const { > + if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { > + // In an addrec, assume that the base will be in the start, rather > + // than the step. > + return GetBaseValue(AR->getStart()); > + } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) { > + // If there's a pointer operand, it'll be sorted at the end of the list. > + const SCEV *Last = A->getOperand(A->getNumOperands()-1); > + if (Last->getType()->isPointerTy()) > + return GetBaseValue(Last); > + } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { > + // This is a leaf node. > + return U->getValue(); > + } > + // No Identified object found. > + return 0; > +}As remarked earlier, I believ this can be replaced by getPointerOperand().> bool ScopDetection::isValidMemoryAccess(Instruction&Inst, > DetectionContext&Context) const { > Value *Ptr = getPointerOperand(Inst); > @@ -236,8 +254,12 @@ > BasePointer = dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction)); > > if (!BasePointer) > - INVALID(AffFunc, "No base pointer"); > - > + { > +// INVALID(AffFunc, "No base pointer"); > + BaseValue = (Value*) GetBaseValue(AccessFunction); > + } > + else > + { > BaseValue = BasePointer->getValue();I don't see a need for any change here. Both functions get the base pointer and we should fail, if we cannot derive a base pointer. Do you have a test case where getPointerBase() does not yield a valid base pointer, but GetBaseValue(AccessFunction) does?> if (isa<UndefValue>(BaseValue)) > @@ -245,8 +267,9 @@ > > AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer); > > - if (!isAffineExpr(&Context.CurRegion, AccessFunction, *SE, BaseValue)) > - INVALID(AffFunc, "Bad memory address "<< *AccessFunction); > + //if (!isAffineExpr(&Context.CurRegion, AccessFunction, *SE, BaseValue)) > + // INVALID(AffFunc, "Bad memory address "<< *AccessFunction);Can you leave this and add a command line option '-polly-allow-nonaffine' to allow non affine access functions.> + } > > // FIXME: Alias Analysis thinks IntToPtrInst aliases with alloca instructions > // created by IndependentBlocks Pass. > --- ./lib/Analysis/ScopInfo.cpp 2011-11-13 02:38:06.000000000 +0100 > +++ ../llvm2/tools/polly/./lib/Analysis/ScopInfo.cpp 2011-11-13 02:36:12.000000000 +0100 > @@ -310,9 +310,13 @@ > Type = Access.isRead() ? Read : Write; > statement = Statement; > > - isl_pw_aff *Affine = SCEVAffinator::getPwAff(Statement, Access.getOffset()); > BaseAddr = Access.getBase(); > > + if (Access.isAffine()) > + {This should be if (Access.isAffine()) {> + > + isl_pw_aff *Affine = SCEVAffinator::getPwAff(Statement, Access.getOffset()); > + > setBaseName(); > > // Devide the access function by the size of the elements in the array. > @@ -334,6 +338,12 @@ > AccessRelation = isl_map_set_tuple_name(AccessRelation, isl_dim_out, > getBaseName().c_str()); > } > + else > + {this should be } else {> + Type = MayWrite;You are right, we should use may-accesses here. But why always setting the type to may-write? A read should remain a read (as there is no difference between read and may-read).> + AccessRelation = isl_map_from_basic_map(createBasicAccessMap(Statement)); > + } > +} > > void MemoryAccess::realignParams() { > isl_space *ParamSpace = statement->getParent()->getParamSpace(); > --- ./lib/Analysis/TempScopInfo.cpp 2011-11-13 02:38:06.000000000 +0100 > +++ ../llvm2/tools/polly/./lib/Analysis/TempScopInfo.cpp 2011-11-13 02:35:22.000000000 +0100 > @@ -98,13 +98,24 @@ > dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction)); > > assert(BasePointer&& "Could not find base pointer"); > - > AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer); > + > + if (isAffineExpr(&R, AccessFunction, *SE, BasePointer->getValue())) > + {Put the '{' in the previous line.> + > Functions.push_back(std::make_pair(IRAccess(Type, > BasePointer->getValue(), > - AccessFunction, Size), > + AccessFunction, Size, true), > &Inst)); > } > + else > + {This should be } else {> + Functions.push_back(std::make_pair(IRAccess(Type, > + BasePointer->getValue(), > + AccessFunction, Size, false), > +&Inst)); > + } > + } > } > > if (Functions.empty())Besides the comments above, the patch looks great. It is a nice improvement to Polly. Can you repost it after the comments are addressed? Also could you include a minimal test case in the patch, that verifies this features is working correctly. Thanks Tobi P.S.: Please post patches to the mailing lists.
Tobias Grosser
2011-Nov-14 09:36 UTC
[LLVMdev] How to make Polly ignore some non-affine memory accesses
On 11/03/2011 09:56 AM, Tobias Grosser wrote:> 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.The recent rewrite of the SCEV validation fixed this bug. Tobi
Marcello Maggioni
2011-Nov-14 13:45 UTC
[LLVMdev] How to make Polly ignore some non-affine memory accesses
2011/11/14 Tobias Grosser <tobias at grosser.es>:> On 11/14/2011 01:24 AM, Marcello Maggioni wrote: >> >> Hi Tobias. >> >> I worked on enabling Polly accepting non affine memory accesses and I >> produced a patch. > > Great. > >> 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. > > Ups, sorry! However, I believe without these changes detecting non-affine > memory access functions would have been a lot more complicated.Indeed! The patch almost shrinked to half the code it was before those changes! Great work.>> 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 . > > OK. Review is inlined in the patch. > >> 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. > > [remove backtrace & code] > >> 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 > > I will look into this. > >> --- ./include/polly/ScopDetection.h 2011-11-13 02:37:59.000000000 >> +0100 >> +++ ../llvm2/tools/polly/./include/polly/ScopDetection.h 2011-11-13 >> 01:11:17.000000000 +0100 >> @@ -145,6 +145,8 @@ >> /// @return True if the call instruction is valid, false otherwise. >> static bool isValidCallInst(CallInst&CI); >> >> + const Value *GetBaseValue(const SCEV *S) const; > > Why is this function needed? For me it looks like it implements > the same as > > SCEVValue *Operand = dyn_cast<SCEVValue>(getPointerOperand()) > > if (!Operand) > return invalid Value; > > return Operand->getValue();Mmm, about this I think that depends on the fact that I'm still quite unexperienced on the topic and fail to be "optimal" in doing some things. In the old version of Polly in ScopDetection (isValidMemoryAccess function) there was an "isValidAffineFunction" that detected if the access function was affine or not. That function initialized a "Value* " pointer used for alias analysis later in the isValidMemoryAccess function itself. If the "isValidAffineFunction" failed that pointer was left uninitialized. I needed a way to get that pointer value in order to make the alias analysis work and the one used in "isValidAffineFunction" on affine functions didn't seemed to work (as far as I remember), so I searched for alternative methods and GetBaseValue did work. With the recent changes to Polly this function doesn't seem to be useful anymore though , and after removing that "if block" actually all the test cases I have seem to continue working well, so this code can be removed without problems I think!>> /// @brief Check if a memory access can be part of a Scop. >> /// >> /// @param Inst The instruction accessing the memory. >> --- ./include/polly/TempScopInfo.h 2011-11-13 02:37:59.000000000 >> +0100 >> +++ ../llvm2/tools/polly/./include/polly/TempScopInfo.h 2011-11-13 >> 02:34:47.000000000 +0100 >> @@ -45,12 +45,13 @@ >> private: >> unsigned ElemBytes; >> TypeKind Type; >> + bool is_affine; > > I think IsAffine matches more the LLVM coding conventions. > >> >> public: >> explicit IRAccess (TypeKind Type, const Value *BaseAddress, >> - const SCEV *Offset, unsigned elemBytes) >> + const SCEV *Offset, unsigned elemBytes, bool affine) > > 'affine' should start with an uppercase letter. Polly itself has some > inconsistent naming, but we started to follow the LLVM coding conventions > since a while. > >> : BaseAddress(BaseAddress), Offset(Offset), >> - ElemBytes(elemBytes), Type(Type) {} >> + ElemBytes(elemBytes), Type(Type), is_affine(affine) {} >> >> enum TypeKind getType() const { return Type; } >> >> @@ -60,7 +61,10 @@ >> >> unsigned getElemSizeInBytes() const { return ElemBytes; } >> >> + bool isAffine() const { return is_affine; } >> + >> bool isRead() const { return Type == READ; } >> + >> }; >> >> class Comparison { >> --- ./lib/Analysis/ScopDetection.cpp 2011-11-13 02:38:06.000000000 >> +0100 >> +++ ../llvm2/tools/polly/./lib/Analysis/ScopDetection.cpp 2011-11-13 >> 01:28:00.000000000 +0100 >> @@ -226,6 +226,24 @@ >> return false; >> } >> >> +const Value *ScopDetection::GetBaseValue(const SCEV *S) const { >> + if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { >> + // In an addrec, assume that the base will be in the start, rather >> + // than the step. >> + return GetBaseValue(AR->getStart()); >> + } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) { >> + // If there's a pointer operand, it'll be sorted at the end of the >> list. >> + const SCEV *Last = A->getOperand(A->getNumOperands()-1); >> + if (Last->getType()->isPointerTy()) >> + return GetBaseValue(Last); >> + } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { >> + // This is a leaf node. >> + return U->getValue(); >> + } >> + // No Identified object found. >> + return 0; >> +} > > As remarked earlier, I believ this can be replaced by getPointerOperand(). > >> bool ScopDetection::isValidMemoryAccess(Instruction&Inst, >> DetectionContext&Context) const { >> Value *Ptr = getPointerOperand(Inst); >> @@ -236,8 +254,12 @@ >> BasePointer >> dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction)); >> >> if (!BasePointer) >> - INVALID(AffFunc, "No base pointer"); >> - >> + { >> +// INVALID(AffFunc, "No base pointer"); >> + BaseValue = (Value*) GetBaseValue(AccessFunction); >> + } >> + else >> + { >> BaseValue = BasePointer->getValue(); > > I don't see a need for any change here. Both functions get the base pointer > and we should fail, if we cannot derive a base pointer. Do you have a test > case where getPointerBase() does not yield a valid base pointer, but > GetBaseValue(AccessFunction) does? > >> if (isa<UndefValue>(BaseValue)) >> @@ -245,8 +267,9 @@ >> >> AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer); >> >> - if (!isAffineExpr(&Context.CurRegion, AccessFunction, *SE, BaseValue)) >> - INVALID(AffFunc, "Bad memory address "<< *AccessFunction); >> + //if (!isAffineExpr(&Context.CurRegion, AccessFunction, *SE, >> BaseValue)) >> + // INVALID(AffFunc, "Bad memory address "<< *AccessFunction); > > Can you leave this and add a command line option > '-polly-allow-nonaffine' to allow non affine access functions. > >> + } >> >> // FIXME: Alias Analysis thinks IntToPtrInst aliases with alloca >> instructions >> // created by IndependentBlocks Pass. >> --- ./lib/Analysis/ScopInfo.cpp 2011-11-13 02:38:06.000000000 +0100 >> +++ ../llvm2/tools/polly/./lib/Analysis/ScopInfo.cpp 2011-11-13 >> 02:36:12.000000000 +0100 >> @@ -310,9 +310,13 @@ >> Type = Access.isRead() ? Read : Write; >> statement = Statement; >> >> - isl_pw_aff *Affine = SCEVAffinator::getPwAff(Statement, >> Access.getOffset()); >> BaseAddr = Access.getBase(); >> >> + if (Access.isAffine()) >> + { > > This should be > > if (Access.isAffine()) { > > >> + >> + isl_pw_aff *Affine = SCEVAffinator::getPwAff(Statement, >> Access.getOffset()); >> + >> setBaseName(); >> >> // Devide the access function by the size of the elements in the array. >> @@ -334,6 +338,12 @@ >> AccessRelation = isl_map_set_tuple_name(AccessRelation, isl_dim_out, >> getBaseName().c_str()); >> } >> + else >> + { > > this should be > } else { > >> + Type = MayWrite; > > You are right, we should use may-accesses here. But why always setting the > type to may-write? A read should remain a read (as there is no difference > between read and may-read).You are right, in the patch for the old version that was handled correctly, I don't know how this reverted back to this way in the patch for the new version , I'll get it fixed.>> + AccessRelation >> isl_map_from_basic_map(createBasicAccessMap(Statement)); >> + } >> +} >> >> void MemoryAccess::realignParams() { >> isl_space *ParamSpace = statement->getParent()->getParamSpace(); >> --- ./lib/Analysis/TempScopInfo.cpp 2011-11-13 02:38:06.000000000 >> +0100 >> +++ ../llvm2/tools/polly/./lib/Analysis/TempScopInfo.cpp 2011-11-13 >> 02:35:22.000000000 +0100 >> @@ -98,13 +98,24 @@ >> dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction)); >> >> assert(BasePointer&& "Could not find base pointer"); >> - >> AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer); >> + >> + if (isAffineExpr(&R, AccessFunction, *SE, BasePointer->getValue())) >> + { > > Put the '{' in the previous line. > >> + >> Functions.push_back(std::make_pair(IRAccess(Type, >> >> BasePointer->getValue(), >> - AccessFunction, Size), >> + AccessFunction, Size, >> true), >> &Inst)); >> } >> + else >> + { > > This should be > > } else { > >> + Functions.push_back(std::make_pair(IRAccess(Type, >> + >> BasePointer->getValue(), >> + AccessFunction, Size, >> false), >> +&Inst)); >> + } >> + } >> } >> >> if (Functions.empty())Yeah, there are quite a few stylistic problems actually, my bad!! I'll get all the style problems fixed as fast as possible! Sorry for that.> Besides the comments above, the patch looks great. It is a nice improvement > to Polly. Can you repost it after the comments are addressed? Also could you > include a minimal test case in the patch, that verifies this features is > working correctly.Thank you, for your time Tobias explaining all the issues with the patch so throughly and in a clear manner . Should I make a specific subdirectory for the test case?> Thanks > Tobi > > P.S.: Please post patches to the mailing lists. > >What do you mean with post patches to the mailing lists? Do you mean in llvm-dev or llvm-commit? The previous patch has been posted on llvm-dev, was that wrong? Thanks again. Marcello
Possibly Parallel Threads
- [LLVMdev] How to make Polly ignore some non-affine memory accesses
- [LLVMdev] How to make Polly ignore some non-affine memory accesses
- [LLVMdev] How to make Polly ignore some non-affine memory accesses
- [LLVMdev] How to make Polly ignore some non-affine memory accesses
- [LLVMdev] How to make Polly ignore some non-affine memory accesses