[Polly] Crash with "We do not yet change the type of the access base during code generation."

[tobiasgrosser]

Bugzilla Link	21113
Resolution	FIXED
Resolved on	Jan 18, 2016 17:01
Version	unspecified
OS	Linux
Attachments	Failing test case
CC	@jdoerfert

Extended Description

The new isl alias check crashes with:

opt: /home/grosser/Projects/polly/git/tools/polly/lib/CodeGen/IslExprBuilder.cpp:136: llvm::Value polly::IslExprBuilder::createAccessAddress(isl_ast_expr ):

Assertion `( PtrElTy->isIntOrIntVectorTy() || PtrElTy->isFPOrFPVectorTy() || PtrElTy->isPtrOrPtrVectorTy()) && "We do not yet change the type of the access base during code generation."' failed.

for the following simple test case:

%struct = type { float, float }

define void @​Fft(%struct %z, %struct %w) { entry: br label %for

for: %indvar = phi i64 [ %indvar.next, %for ], [ 0, %entry ] %scevgep.A = getelementptr %struct %w, i64 0 %scevgep.A.cast = bitcast %struct %scevgep.A to i64 %scevgep.B = getelementptr %struct %z, i64 0 %scevgep.B.cast = bitcast %struct %scevgep.B to i64 %val = load i64 %scevgep.A.cast, align 4 store i64 %val, i64 %scevgep.B.cast, align 4 %indvar.next = add i64 %indvar, 1 br i1 false, label %for, label %end

end: ret void }

It is unclear to me why we check for specific types here and how this is related to possibly changing the access base during code generation. Removing this assert makes the code compile.

Johannes, any idea how to solve this bug. Is just dropping the assert the right solution?

For information: This is one of the current failures in the LNT run appearing e.g. in SingleSource/Benchmarks/Stanford/Oscar

[tlattner]

Move to Polly Product.

[tobiasgrosser]

Fixed in r219077

[tobiasgrosser]

On 01/10/2014 14:26, bugzilla-daemon@llvm.org wrote:

Johannes Doerfert mailto:doerfert@cs.uni-saarland.de changed bug 21113 http://llvm.org/bugs/show_bug.cgi?id=21113 What Removed Added Status NEW ASSIGNED

Comment # 1 http://llvm.org/bugs/show_bug.cgi?id=21113#c1 on bug 21113 http://llvm.org/bugs/show_bug.cgi?id=21113 from Johannes Doerfert mailto:doerfert@cs.uni-saarland.de

I don't think the assert is missplaced and it only compiles without it, it is sound more by accident.

Thanks for clarifying.

The problem is the struct base pointer which is like a black box for the IslExprBuilder at the moment. When the access function of an access looks like "A[i+3]" we assume that it means the i+3 element after the base pointer A. However, this assumption implicitly uses the type and size of the elements of A. This fact is hidden in the GEP we create. If now the base pointer is a complex struct type or there are bitcasts involved we currently only have the type information of the initial base pointer of the memory access, but not the type we actually want to produce by the access. This can actually causes two types of bugs. One will be "detected" by this assertion the other will just silently emit wrong code. I make an example for both but first let me stress again that they are caused by the same underlying problem: The IslExprBuilder doesn not know what type the access it creates is supposed to have.

I tried to fix it inhttp://reviews.llvm.org/D5414 but that attempt just hides the problem better...

I only thought about this patch in terms of in-scop base pointers and did not realize this patch also addresses another problem. Sorry for not paying enough attention.

Thanks for the interesting test cases.

Problem 1 (Structs which crash instead of creating possibly wrong code): ; RUN: opt %loadPolly -S -polly-code-generator=isl -polly-codegen-isl < %s | FileCheck %s ; ; We should only access (or compute the address of) "the first element" of %S ; as it is a single struct not a struct array. The maximal access to S, thus ; S->B[1023] is for ScalarEvolution an access with offset of 1423, 1023 for the ; index inside the B part of S and 400 to skip the Dummy array in S. Note that ; these numbers are relative to the actual type of &S->B[i] (char) not to the ; type of S (struct st ) or something else.

I did not realize SCEV is linearising all these different elements.

; Verify that we do not use the offset 1423 into a non existent S array when we ; compute runtime alias checks: ; Only a 0 is a valid ; first index. ; ; CHECK-NOT: getelementptr %struct.st %S, i{{(32|64)}} 1 ; ; struct st { ; int Dummy[100]; ; char B[100]; ; }; ; ; void jd(int A, struct st *S) { ; for (int i = 0; i < 1024; i++) ; A[i] = S->B[i]; ; }

In which way is using 1424 wrong? I understand that 1424 does not correspond to the source code, but the actual memory addresses and the run-time check we generate (if dropping the assert) seems to do what we want.

if (1 && (&MemRef_S[1424] <= &MemRef_A[0] || &MemRef_A[1024] <= &MemRef_S[400]))

Did I miss something?

Problem 2 (Bitcasts which cause us to create wrong code):

; RUN: opt %loadPolly -S -polly-code-generator=isl -polly-codegen-isl < %s | FileCheck %s ; ; We should never access %B as an i32 pointer:

With 'access' you mean the load/store to this pointer or that we use the i32 as data type in the getelementptr instruction?

When running opt -polly-code-generator=isl -S -polly-codegen-isl the code generated for the statements inside the scop seems to correctly access the pointer as i16. The run-time check however uses i32. Is this the incorrectness you have been talking about?

As we ensure that all load/store instructions use the same type (otherwise we report invalid) and all access functions (and the derived offsets) are expressed according to this type, it seems we should cast the base pointer to a ptr pointing to this type before using it in the run-time check, no?

Cheers, Tobias.

[jdoerfert]

I don't think the assert is missplaced and it only compiles without it, it is sound more by accident. The problem is the struct base pointer which is like a black box for the IslExprBuilder at the moment. When the access function of an access looks like "A[i+3]" we assume that it means the i+3 element after the base pointer A. However, this assumption implicitly uses the type and size of the elements of A. This fact is hidden in the GEP we create. If now the base pointer is a complex struct type or there are bitcasts involved we currently only have the type information of the initial base pointer of the memory access, but not the type we actually want to produce by the access. This can actually causes two types of bugs. One will be "detected" by this assertion the other will just silently emit wrong code. I make an example for both but first let me stress again that they are caused by the same underlying problem: The IslExprBuilder doesn not know what type the access it creates is supposed to have.

I tried to fix it in http://reviews.llvm.org/D5414 but that attempt just hides the problem better...

Problem 1 (Structs which crash instead of creating possibly wrong code): ; RUN: opt %loadPolly -S -polly-code-generator=isl -polly-codegen-isl < %s | FileCheck %s ; ; We should only access (or compute the address of) "the first element" of %S ; as it is a single struct not a struct array. The maximal access to S, thus ; S->B[1023] is for ScalarEvolution an access with offset of 1423, 1023 for the ; index inside the B part of S and 400 to skip the Dummy array in S. Note that ; these numbers are relative to the actual type of &S->B[i] (char) not to the ; type of S (struct st ) or something else. ; ; Verify that we do not use the offset 1423 into a non existent S array when we ; compute runtime alias checks: ; ; Only a 0 is a valid ; first index. ; ; CHECK-NOT: getelementptr %struct.st %S, i{{(32|64)}} 1 ; ; struct st { ; int Dummy[100]; ; char B[100]; ; }; ; ; void jd(int A, struct st *S) { ; for (int i = 0; i < 1024; i++) ; A[i] = S->B[i]; ; } ; target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"

%struct.st = type { [100 x i32], [100 x i8] }

define void @​jd(i32 %A, %struct.st %S) { entry: br label %for.cond

for.cond: ; preds = %for.inc, %entry %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ] %exitcond = icmp ne i64 %indvars.iv, 1024 br i1 %exitcond, label %for.body, label %for.end

for.body: ; preds = %for.cond %arrayidx = getelementptr inbounds %struct.st %S, i64 0, i32 1, i64 %indvars.iv %tmp = load i8 %arrayidx, align 1 %conv = sext i8 %tmp to i32 %arrayidx2 = getelementptr inbounds i32 %A, i64 %indvars.iv store i32 %conv, i32 %arrayidx2, align 4 br label %for.inc

for.inc: ; preds = %for.body %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 br label %for.cond

for.end: ; preds = %for.cond ret void }

Problem 2 (Bitcasts which cause us to create wrong code):

; RUN: opt %loadPolly -S -polly-code-generator=isl -polly-codegen-isl < %s | FileCheck %s ; ; We should never access %B as an i32 pointer: ; ; CHECK-NOT: getelementptr i32 %B ; ; void jd(int A, int B) { ; for (int i = 0; i < 1024; i++) ; A[i] = ((short )B)[i]; ; } ; target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"

define void @​jd(i32 %A, i32 %B) { entry: br label %for.cond

for.cond: ; preds = %for.inc, %entry %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ] %exitcond = icmp ne i64 %indvars.iv, 1024 br i1 %exitcond, label %for.body, label %for.end

for.body: ; preds = %for.cond %tmp = bitcast i32 %B to i16 %arrayidx = getelementptr inbounds i16 %tmp, i64 %indvars.iv %tmp1 = load i16 %arrayidx, align 2 %conv = sext i16 %tmp1 to i32 %arrayidx2 = getelementptr inbounds i32 %A, i64 %indvars.iv store i32 %conv, i32 %arrayidx2, align 4 br label %for.inc

for.inc: ; preds = %for.body %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 br label %for.cond

for.end: ; preds = %for.cond ret void }