Vectorizing global struct pointers

Project Infrastructure LLVM Dev List Archives
#1

Hi all,

One of the reasons the Livermore Loops couldn’t be vectorized is that it was using global structures to hold the arrays. Today, I’m investigating why is that so and how to fix it.

My investigation brought me to LoopVectorizationLegality::canVectorizeMemory():

if (WriteObjects.count(*it)) {
DEBUG(dbgs() << “LV: Found a possible read/write reorder:”
<< **it <<"\n");
return false;
}

In the first pass, it registers all underlying objects for writes, than it does it again for reads, if the value was already there, it’s a conflict.

However, the read is from Foo.bl / Foo.cl and the write to Foo.al, so why is GetUnderlyingObjects() returning the same objects/pointers?

A quick look at it revealed me the problem:

llvm::GetUnderlyingObject(Value *V, const DataLayout *TD, unsigned MaxLookup) yields:

→ GEPOperator *GEP = dyn_cast(V)

→ V = GEP->getPointerOperand();
→ GlobalAlias *GA = dyn_cast(V)

→ V = GA->getAliasee();
return V;

In this case, V is a reference to the structure, not the element. It seems to me that assigning the pointer operand from GEP is too simplistic. Either GetUnderlyingObject() should store the indices to return the correct object, or GetUnderlyingObjects() should create a special case for it (as it does with selects and phi nodes).

Does that make sense?

cheers,
–renato

PS:

A simplified version of the IR:

%struct.anon = type { [256 x i64], [256 x i64], [256 x i64] }

@Foo = common global %struct.anon zeroinitializer, align 8

…

%arrayidx = getelementptr inbounds %struct.anon* @Foo, i32 0, i32 1, i32 %idxprom
%0 = load i64* %arrayidx, align 8
%arrayidx2 = getelementptr inbounds %struct.anon* @Foo, i32 0, i32 2, i32 %idxprom
%1 = load i64* %arrayidx2, align 8
%mul = mul nsw i64 %1, %0
%arrayidx4 = getelementptr inbounds %struct.anon* @Foo, i32 0, i32 0, i32 %idxprom
store i64 %mul, i64* %arrayidx4, align 8

#2

If I understand you correctly, conceptually you want two different objects to be returned for Foo.bl and Foo.al?

Here is my take on this (take this with a grain of salt, Dan is the expert on this):

http://llvm.org/docs/GetElementPtr.html#what-happens-if-an-array-index-is-out-of-bounds

LLVM's semantic allows for arrays to be accessed out of bounds - this allows you to walk from the first array { [256 x i64] #<<, [256 x i64], [256 x i64] } to the second { [256 x i64], [256 x i64]#<<, [256 x i64] }. I believe, one reason for having it defined this way is to be able to handle C's zero (variable) length arrays. LLVM's concept of memory is untyped (http://llvm.org/docs/LangRef.html#pointeraliasing). You can get types through TBAA.
We would need to strengthen TBAA to handle this for C.

#3

Not necessarily. The vectorizer is implemented expecting that the objects
will be different, but that's a limitation on the vectorizer itself.

However, changing the vectorizer to recognize GEP offsets is probably not
the best course of action, but by the time we get the object back, we have
no information if it was a GEP, and if so, what was its offset.

Maybe I could work back (via uses) and identify the GEP and store the
offset with the object locally, so that the list would not think different
members are the same object. But I wanted to know first if the underlying
object concept is correct. From the docs you sent me, it seems it is.

TBAA seems a bit too much for this case, though.

cheers,
--renato

#4

If I understand you correctly, conceptually you want two different objects to be returned for Foo.bl and Foo.al?

Here is my take on this (take this with a grain of salt, Dan is the expert on this):

http://llvm.org/docs/GetElementPtr.html#what-happens-if-an-array-index-is-out-of-bounds

LLVM's semantic allows for arrays to be accessed out of bounds - this allows you to walk from the first array { [256 x i64] #<<, [256 x i64], [256 x i64] } to the second { [256 x i64], [256 x i64]#<<, [256 x i64] }. I believe, one reason for having it defined this way is to be able to handle C's zero (variable) length arrays. LLVM's concept of memory is untyped (http://llvm.org/docs/LangRef.html#pointeraliasing). You can get types through TBAA.
We would need to strengthen TBAA to handle this for C.

I think that the potential for overlap is indeed there, but don't we already insert runtime overlap checks as necessary? This seems like it would just be another such case.

-Hal

#5

We insert runtime overlap checks only for unidentified objects. The problem here is that the vectorizer thinks that A,B,C are all pointers to the same array, so it gives up. If A,B,C were different arrays then it could have used runtime checks.

#6

Yes, that is exactly the code that creates the run-time checks. :wink:

I'll try to inspect the uses for GEPs and store the offsets in a map. If it
works, we can think of a better implementation.

cheers,
--renato

#7

Exactly. My point is that this is the logic to look at generalizing.

-Hal

#8

Note that the final index(es) and size of accessed memory have to be the same, and no zero length arrays must be involved that means you have to look at the type of the gep (and I am sure I am missing other conditions here). Essentially, you have to symbolically evaluate the address computation and take the size of the access into account. Something along the lines of BasicAA::aliasGEP.

You can assume that

%arrayidx = getelementptr inbounds %struct.anon* @Foo, i32 0, i32 1, i32 %idxprom
%0 = load i64* %arrayidx, align 8
%arrayidx4 = getelementptr inbounds %struct.anon* @Foo, i32 0, i32 0, i32 %idxprom
store i64 %mul, i64* %arrayidx4, align 8

don’t overlap, but not so for:

%arrayidx = getelementptr inbounds %struct.anon* @Foo, i32 0, i32 1, i32 %idxprom
%0 = load i64* %arrayidx, align 8
%arrayidx4 = getelementptr inbounds %struct.anon* @Foo, i32 0, i32 0, i32 %anotheridx
store i64 %mul, i64* %arrayidx4, align 8