Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[Polly] The generation of the code for index expressions of copy statements in case of the base pointer computed within the SCoP #30842

Closed
llvmbot opened this issue Dec 29, 2016 · 11 comments
Labels
bugzilla Issues migrated from bugzilla polly

Comments

@llvmbot
Copy link
Collaborator

llvmbot commented Dec 29, 2016

Bugzilla Link 31494
Resolution FIXED
Resolved on Jan 17, 2017 06:02
Version unspecified
OS Linux
Attachments A test case.
Reporter LLVM Bugzilla Contributor
CC @Meinersbur,@tobiasgrosser

Extended Description

The attached test case causes an assertion failure due to the generation of the code for index expressions of copy statements in case of the base pointer computed within the SCoP.

opt -polly-invariant-load-hoisting -polly-process-unprofitable -polly-opt-isl -polly-pattern-matching-based-opts=true -polly-codegen < test.ll

WARNING: You're attempting to print out a bitcode file.
This is inadvisable as it may cause display problems. If
you REALLY want to taste LLVM bitcode first-hand, you
can force output with the `-f' option.

opt: /home/roman/Documents/polly/llvm/tools/polly/lib/CodeGen/IslNodeBuilder.cpp:762: isl_id_to_ast_expr* IslNodeBuilder::createNewAccesses(polly::ScopStmt*, isl_ast_node*): Assertion `!MA->getLatestScopArrayInfo()->getBasePtrOriginSAI() && "Generating new index expressions to indirect arrays not working"' failed.
#​0 0x00007fcd48d169b8 llvm::sys::PrintStackTrace(llvm::raw_ostream&) (/home/roman/Documents/polly/build/llvm_d/bin/../lib/libLLVMSupport.so.40+0xef9b8)
#​1 0x00007fcd48d14a1e llvm::sys::RunSignalHandlers() (/home/roman/Documents/polly/build/llvm_d/bin/../lib/libLLVMSupport.so.40+0xeda1e)
#​2 0x00007fcd48d14b94 SignalHandler(int) (/home/roman/Documents/polly/build/llvm_d/bin/../lib/libLLVMSupport.so.40+0xedb94)
#​3 0x00007fcd47c632f0 (/lib/x86_64-linux-gnu/libc.so.6+0x352f0)
#​4 0x00007fcd47c63267 gsignal /build/buildd/glibc-2.21/signal/../sysdeps/unix/sysv/linux/raise.c:55:0
#​5 0x00007fcd47c64eca abort /build/buildd/glibc-2.21/stdlib/abort.c:91:0
#​6 0x00007fcd47c5c03d __assert_fail_base /build/buildd/glibc-2.21/assert/assert.c:92:0
#​7 0x00007fcd47c5c0f2 (/lib/x86_64-linux-gnu/libc.so.6+0x2e0f2)
#​8 0x00007fcd4aa4eca8 IslNodeBuilder::createNewAccesses(polly::ScopStmt*, isl_ast_node*) (/home/roman/Documents/polly/build/llvm_d/bin/../lib/libPolly.so+0xccca8)
#​9 0x00007fcd4aa52923 IslNodeBuilder::createUser(isl_ast_node*) (/home/roman/Documents/polly/build/llvm_d/bin/../lib/libPolly.so+0xd0923)
#​10 0x00007fcd4aa55037 IslNodeBuilder::createForSequential(isl_ast_node*, bool) (/home/roman/Documents/polly/build/llvm_d/bin/../lib/libPolly.so+0xd3037)
#​11 0x00007fcd4aa55037 IslNodeBuilder::createForSequential(isl_ast_node*, bool) (/home/roman/Documents/polly/build/llvm_d/bin/../lib/libPolly.so+0xd3037)
#​12 0x00007fcd4aa4f0b8 IslNodeBuilder::createBlock(isl_ast_node*) (/home/roman/Documents/polly/build/llvm_d/bin/../lib/libPolly.so+0xcd0b8)
#​13 0x00007fcd4aa55037 IslNodeBuilder::createForSequential(isl_ast_node*, bool) (/home/roman/Documents/polly/build/llvm_d/bin/../lib/libPolly.so+0xd3037)
#​14 0x00007fcd4aa55154 IslNodeBuilder::createMark(isl_ast_node*) (/home/roman/Documents/polly/build/llvm_d/bin/../lib/libPolly.so+0xd3154)
#​15 0x00007fcd4aa59167 (anonymous namespace)::CodeGeneration::runOnScop(polly::Scop&) (/home/roman/Documents/polly/build/llvm_d/bin/../lib/libPolly.so+0xd7167)
#​16 0x00007fcd4a54389d llvm::RGPassManager::runOnFunction(llvm::Function&) (/home/roman/Documents/polly/build/llvm_d/bin/../lib/libLLVMAnalysis.so.40+0x1fa89d)
#​17 0x00007fcd49f56443 llvm::FPPassManager::runOnFunction(llvm::Function&) (/home/roman/Documents/polly/build/llvm_d/bin/../lib/libLLVMCore.so.40+0x17a443)
#​18 0x00007fcd49f564fc llvm::FPPassManager::runOnModule(llvm::Module&) (/home/roman/Documents/polly/build/llvm_d/bin/../lib/libLLVMCore.so.40+0x17a4fc)
#​19 0x00007fcd49f56d8a llvm::legacy::PassManagerImpl::run(llvm::Module&) (/home/roman/Documents/polly/build/llvm_d/bin/../lib/libLLVMCore.so.40+0x17ad8a)
#​20 0x000000000041b807 main (/home/roman/Documents/polly/build/llvm_d/bin/opt+0x41b807)
#​21 0x00007fcd47c4ea40 __libc_start_main /build/buildd/glibc-2.21/csu/libc-start.c:323:0
#​22 0x000000000041bf89 _start (/home/roman/Documents/polly/build/llvm_d/bin/opt+0x41bf89)
Stack dump:
0. Program arguments: /home/roman/Documents/polly/build/llvm_d/bin/opt -polly-invariant-load-hoisting -polly-process-unprofitable -polly-opt-isl -polly-pattern-matching-based-opts=true -polly-codegen

  1. Running pass 'Function Pass Manager' on module ''.
  2. Running pass 'Region Pass Manager' on function '@_Z4gemmRN5boost7numeric5ublas6matrixIdNS1_15basic_row_majorImlEENS1_15unbounded_arrayIdSaIdEEEEES9_S9_dd'
  3. Running pass 'Polly - Create LLVM-IR from SCoPs' on basic block '%for.cond3.preheader'
    Aborted (core dumped)

Additional information about the assert can be found in r282893.

@llvmbot
Copy link
Collaborator Author

llvmbot commented Dec 29, 2016

Hi Michael,

According to the r282893 [1], we could probably trigger that the base pointer has been already generated. Could you please advise me how to do it?

Refs.:

[1] - http://llvm.org/viewvc/llvm-project?view=revision&revision=282893

@Meinersbur
Copy link
Member

Hi Roman,

sorry for the delay, I wasn't very active during the holidays.

Tobias seems to already have partially tackled this in https://reviews.llvm.org/D28518. However, the code generation part might not work with this, without actually having tried.

If we try to reuse the old pointer, as you suggested, BlockGenerator::getNewValue() needs to handle this. The baseptr value could be in BBMap due to having been hoisted.

If handling it as a NewAccessRelation like D28518 does, the "If (AccessExpr) of generateLocationAccessed()" would handle it. It implicitly would also use the hoisted baseptr from BBMap. Note that this case can always be triggered if setNewAccessRelation is used by e.g. JSONImporter.

If these indeed already work, the only thing to do in addition to D28518 is to exceptionally allow load-hoisted baseptrs in the assertion. Eg.

BasePtr = MA->getLatestScopArrayInfo()->getBasePtrOriginSAI();
assert((!BasePtr || isLoadHoisted(BasePtr)) && "Generating new index expressions to indirect arrays not working");

with some implementation of isLoadHoisted(). SCoP::lookupInvariantEquivClass could be useful.

@tobiasgrosser
Copy link
Contributor

I yesterday discussed this issue with Michael. One observation I made is that in Polly the only base pointers we allow are always loop invariant, hence it seems that the cases that Michael listed always hold and this assert is not really needed.

However, Michael remembered that he committed this assert because of a bug he was seeing in his work. Unfortunately, the corresponding test case was not committed.

It seems we should understand if this assert is really needed. Michael was trying to see if he can remember / recover the failing test case.

@Meinersbur
Copy link
Member

When I add assertions it is usually because it occurred during a bug or happened while I was trying out something. There is no bug associated with it, which means I induced it with experimental code, found it non-working, and added the assertion to make life easier in case it happens again. In this case I was not aware that it was supposed to be working if the load-hoisted base pointers. There is no test case that failed nor anything in the test-suite.

Looking at the code in ScopDetection which should be verifying the 'hoistibility' of the base pointer in ScopDetection::isValidAccess, it seems incomplete.

if (!AS.isMustAlias()) {
if (PollyUseRuntimeAliasChecks) {
[...]
for (const auto &Ptr : AS) {
Instruction *Inst = dyn_cast(Ptr.getValue());
if (Inst && Context.CurRegion.contains(Inst)) {
auto *Load = dyn_cast(Inst);
if (Load && isHoistableLoad(Load, Context.CurRegion, *LI, *SE, *DT)) {
Context.RequiredILS.insert(Load);
continue;
}

  • Only enabled when AAnalysis says it might alias with something else (eg. alloca'd arrays would not alias with anything else)
  • Only enabled when PollyUseRuntimeAliasChecks (on by default, but switching it off means that CodeGen starts to fail)

It might be worth to review the load-hoisting of base pointers. If it is supposed to be a working feature, could we at least add a regression test?

@tobiasgrosser
Copy link
Contributor

Thank you Michael for this information.

I do not think we ever thought about modifiable access functions for computing base pointers so it mostly works just by accident.

I agree that if we want to drop the assert again, we should review the invariant load hoisting part and address the remarks you are giving.

However, I believe that alloc-ed arrays are also checked. AFAIU will the alias analysis just generate one-element alias sets for such kind of arrays (to be verified). Assuming this is true (and you did not run with -polly-ignore-aliasing), I still do not understand in which situation this failed for you.

Not sure we an solve this, but if you have an idea that would be great.

@tobiasgrosser
Copy link
Contributor

@​Roman: If you have time it would be good to get this resolved.

@Meinersbur
Copy link
Member

It happened by calling setNewAccessRelation() with a mapping to an "indirect" array. CodeGen has a different code path for when there is a NewAccessRelation which would also have required the BasePtr to be generated.

@tobiasgrosser
Copy link
Contributor

Is it easy to generate a JSON based test case? In case it is, I could try to fix this.

Best,
Tobias

@llvmbot
Copy link
Collaborator Author

llvmbot commented Jan 15, 2017

Thanks for looking into it! Sorry, I'm busy at the moment. I can try to fix it, if I have time.

@tobiasgrosser
Copy link
Contributor

Thanks for looking into it! Sorry, I'm busy at the moment. I can try to fix
it, if I have time.

I added the relevant test case in r292147.

Michael, you are right. In case we do not create alias checks we do not require the base pointers to be hoisted. That seems OK, but causes troubles when trying to rewrite such arrays. With invariant load hoisting enabled, this works reliably.

@tobiasgrosser
Copy link
Contributor

This was resolved in r292213.

This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bugzilla Issues migrated from bugzilla polly
Projects
None yet
Development

No branches or pull requests

3 participants