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

Wed Nov 2 04:17:36 PDT 2011

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
>>>
>>
>