[LAA] RtCheck on pointers of different address spaces.

Hello,

I Have a question related to the RT check on pointers during Loop Access Analysis pass.

There is a testcase with loop code that consist of 4 different memory operations referring two global objects of different address spaces.

One from global constant (address space 4, addr_size = 64) and the other from local, LDS (address space 3, addr_size= 32).

(Details of various address spaces available for AMDGPU backend: https://llvm.org/docs/AMDGPUUsage.html#address-spaces)

With upstream compiler, the testcase fails with a crash (given at the end of the e-mail) in the opt while trying to generate the RT check for these pointers. Precisely, with two pointers of different address spaces.

The operand type check fails while trying to insert a ‘AddExpr’ SCEV node as their effective type differs for these pointers (One with 32-bit and the other with 64-bit)

Question: Is this intended to try for the RtCheck on pointers from different address spaces?

The comments given in the code snippet (below) hints they aren’t.

Code snippet from LoopAccessAnalysis.cpp:

Hi,

There are a lot of things going on here, but given this:

The crash occurs with the pointers 1 & 4 which are from AS1 and AS2 respectively.

and the trace, I’m not sure how that can happen. groupChecks() will only try to group pointers that
are on the same alias set (because it will only try to group pointers that are in the same Eq class
in DepCands, which if you see its construction in processMemAccesses(), won’t put two pointers
from different alias sets in the same Eq Class because theoretically, two such pointers can’t
share an underlying object).

Do maybe have a simplified but complete IR ? Is that a possibility?

Kind regards,
Stefanos Baziotis

Στις Κυρ, 26 Ιουλ 2020 στις 1:06 μ.μ., ο/η Devadasan, Christudasan via llvm-dev <llvm-dev@lists.llvm.org> έγραψε:

Hi Stefanos,

Attached the testcase. I tried to reduce it further, but the problem goes away when I remove the instructions further.

There is a nested loop and the fault occurs while processing the inner loop (for.body)

To reproduce the crash:

opt -O3 testcase.ll -o out.ll

groupChecks() will only try to group pointers that are on the same alias set.

If that’s true, the RT check should have been prevented for these pointers in question.

Additional details about the problem:

The crash first appeared after the following llvm commit to preserve the Global AA.

commit e6cf796bab7e02d2b8ac7fd495f14f5e21494270

Author: Ryan Santhiraraja rsanthir@quicinc.com

Preserve GlobalsAA analysis result in LowerConstantIntrinsics

The Global AA now finds out that these pointers refer different objects and won’t alias each other, and eventually ended up in different alias sets.

Prior to this commit, none of the alias analysis could appropriate the noAlias property for these pointers. (If you revert this patch locally, the testcase will compile successfully).

The address-space validation (given below) prevented the RT check for these pointers earlier which I expected even to get triggered with the upstream compiler today.

But it didn’t occur as they have the same DependenceSetId value. (The DependenceSetId starts from 1 for each Alias Set and hence pointers of

different AS can have the same Id. If it is intended, I am not sure that the early continue here, only based on the DependenceSetId, handled all cases)

// Only need to check pointers between two different dependency sets.

if (RtCheck.Pointers[i].DependencySetId ==

RtCheck.Pointers[j].DependencySetId)

continue;

// Only need to check pointers in the same alias set.

if (RtCheck.Pointers[i].AliasSetId != RtCheck.Pointers[j].AliasSetId)

continue;

Value *PtrI = RtCheck.Pointers[i].PointerValue;

Value *PtrJ = RtCheck.Pointers[j].PointerValue;

unsigned ASi = PtrI->getType()->getPointerAddressSpace();

unsigned ASj = PtrJ->getType()->getPointerAddressSpace();

if (ASi != ASj) {

LLVM_DEBUG(

dbgs() << “LAA: Runtime check would require comparison between”

" different address spaces\n");

return false;

}

Regards,

CD

testcase.ll (5.05 KB)

Thanks for sharing the reproducer. I reduced it a bit and filed a bug report https://bugs.llvm.org/show_bug.cgi?id=46854

Cheers,
Florian

Hi,

Florian thanks for creating the bug report. Actually, I couldn’t reproduce the bug with -O3, but with -globals-aa -loop-load-elim I can. Not sure why.

Attached the testcase.

Thanks for that!

groupChecks() will only try to group pointers that are on the same alias set.

If that’s true, the RT check should have been prevented for these pointers in question.

Exactly, that was my point :slight_smile:

Now, a little info from my trying to find the source of the bug for anyone interested:

In the test case we have 4 pointers as you said:

%tmp4 = bitcast %struct.barney* %tmp3 to i64* – AS1
%tmp12 = bitcast %struct.wombat* %tmp11 to i64* – AS1
%tmp16 = getelementptr inbounds [4000 x float], [4000 x float] addrspace(3)* @global.1, i32 0, i32 %tmp15 – AS2
%tmp = getelementptr inbounds [4000 x float], [4000 x float] addrspace(3)* @global.1, i32 0, i32 %arg – AS2

First of all, the claim above holds for this case too: groupChecks() won’t try to group pointers that are
not in the same alias set because they won’t be in the same EqClass in DepCands. While groupChecks()
here tries to group %tmp4 and %tmp16 together, this is not because they’re in the same EqClass
but because of a bug.

You see, groupChecks() starts by assigning an index to each pointer in Pointers (using PositionMap).
But if you put a debug print in that loop, you’ll see that %tmp16 is not in Pointers. So, there’s no
index assigned to it.

But, %tmp16 is in the same EqClass with %tmp. And %tmp is in Pointers. Because of the latter,
it means we’ll come across it in the next loop. Which in turn means that we’ll come across any pointer
in %tmp’s EqClass (will try to addPointer() it to some Group). So, at some point, we’ll try to handle %tmp16.
But remember, %tmp16 does not have an entry in PositionMap. So, this line:
unsigned Pointer = PositionMap[MI->getPointer()];

will make Pointer = 0 (you get 0 when it’s not found in this DenseMap).

Now, then we proceed by calling addPointer() which has this line:
const SCEV *Start = RtCheck.Pointers[Index].Start;

Remember, Index here is equal to Pointer previously. So, 0. But if you remember, when
we assigned indexes to pointers (in the PositionMap loop), we started from 0. So, some pointer
has an index of 0. And that happens to be %tmp4. Calling then getMinFromExprs() eventually
results in the crash you saw.

I’m not sure how we should solve that. I mean, it would be good if we used
1-based indexing somehow and assert that we never get a 0 back when
we query PositionMap but that’s not the root of the problem.

P.S. The reason that %tmp16 doesn’t make it to Pointers is because in createCheckForAccess(),
which is called from canCheckPtrAtRT(), we couldn’t find its bounds.

Cheers,
Stefanos

Στις Δευ, 27 Ιουλ 2020 στις 12:34 π.μ., ο/η Florian Hahn <florian_hahn@apple.com> έγραψε:

Thanks for looking into it Stefanos and Florian.

Truly appreciate your effort with the analysis and initiating the fix.

Regards,

CD