[llvm-dev] [LAA] RtCheck on pointers of different address spaces.
Stefanos Baziotis via llvm-dev
llvm-dev at lists.llvm.org
Sun Jul 26 15:46:31 PDT 2020
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 :)
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 at apple.com> έγραψε:
> 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
>
> On Jul 26, 2020, at 18:52, Devadasan, Christudasan via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
> 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 at quicinc.com>
> Date: Thu Jul 2 13:53:20 2020 +0100
> 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
>
> *From:* Stefanos Baziotis <stefanos.baziotis at gmail.com>
> *Sent:* Sunday, July 26, 2020 6:09 PM
> *To:* Devadasan, Christudasan <Christudasan.Devadasan at amd.com>
> *Cc:* LLVM Dev <llvm-dev at lists.llvm.org>
> *Subject:* Re: [llvm-dev] [LAA] RtCheck on pointers of different address
> spaces.
>
> [CAUTION: External Email]
> 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 at lists.llvm.org> έγραψε:
>
> 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
> <https://nam11.safelinks.protection.outlook.com/?url=https%3A%2F%2Fllvm.org%2Fdocs%2FAMDGPUUsage.html%23address-spaces&data=02%7C01%7CChristudasan.Devadasan%40amd.com%7C4a42db7316004baa429c08d83160f7e7%7C3dd8961fe4884e608e11a82d994e183d%7C0%7C0%7C637313639833494292&sdata=r7fk%2FU%2FCZLt8RKZNc0lAco6wBJKKDj%2Br621r%2FaBOI6A%3D&reserved=0>
> )
>
> 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:
>
> -----------------------------------------------------------------------------------------------------------------------
> bool AccessAnalysis::canCheckPtrAtRT(...) {
> ----------
> // If the pointers that we would use for the bounds comparison have
> different
> // address spaces, assume the values aren't directly comparable, so we
> can't
> // use them for the runtime check. We also have to assume they could
> // overlap. In the future there should be metadata for whether address
> spaces
> // are disjoint.
> unsigned NumPointers = RtCheck.Pointers.size();
> for (unsigned i = 0; i < NumPointers; ++i) {
> for (unsigned j = i + 1; j < NumPointers; ++j) {
> // 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;
> }
> }
>
> ----------------------------------------------------------------------------------------------------
> More details about the objects, the pointers and the memory operations:
>
> ----------------------------------------------------------------------------------------------------
> %struct_var1 = type { <2 x float> }
> %struct_var2 = type { %struct_var1 }
> %class_var1 = type { i32, i32, i32, %struct_var2*, i32, i32, i32}
> %class_var2 = type { %class_var1, i8, i8*, i32 }
>
> Objects:
> @Obj1 = external protected local_unnamed_addr addrspace(4)
> externally_initialized global %class_var2, align 8
> @Obj2 = internal unnamed_addr addrspace(3) constant [4000 x float] undef,
> align 16
>
> Pointers:
>
> 1. %struct_var1.cast = bitcast %struct_var1* %struct_var2.gep to
> i64* (write) // AS1
>
> 2. %struct_var2.cast = bitcast %struct_var2* %arrayidx74 to i64*
> (read-only) // AS1
>
> 3. %arrayidx1705 = getelementptr inbounds [4000 x float], [4000 x
> float] addrspace(3)* @Obj2, i32 0, i32 %add125 (read-only) // AS2
>
> 4. %arrayidx274 = getelementptr inbounds [4000 x float], [4000 x
> float] addrspace(3)* @Obj2, i32 0, i32 %arg1 (read-only) // AS2
>
> While the pointers 1 & 2 belong to one Alias Set (AS1), pointers 3 & 4
> belong to a different set (AS2). It is because, the Global Alias Analysis
> found there is no alias between these two sets of pointers.
> The crash occurs with the pointers 1 & 4 which are from AS1 and AS2
> respectively.
> The DependenceSetId will be reset to 1 before processing a new AS and the
> pointers in question, ended up having the same DependenceSetId (1), though
> they are from different AS.
>
>
> ----------------------------------------------------------------------------------------------------------------------------------------------------------
> The load/store (memory operations) using these pointers in the
> loop. (extracted only the relevant instructions):
>
> ----------------------------------------------------------------------------------------------------------------------------------------------------------
> define protected amdgpu_kernel void @test_func(i32 %arg1, i32
> %arg2) {
> entry:
> *%arrayidx274 = getelementptr inbounds [4000 x float], [4000 x float]
> addrspace(3)* @Obj2, i32 0, i32 %arg1*
> ---------
> br i1 %cmp1, label %header, label %for.end
>
> header:
> % *struct_var2.ld* = load %struct_var2*, %struct_var2* addrspace(4)*
> getelementptr inbounds (%class_var2, %class_var2 addrspace(4)* @Obj1, i64
> 0, i32 0, i32 3), align 8
> %struct_var2.gep = getelementptr inbounds %struct_var2, %struct_var2*
> %struct_var2.ld, i64 undef, i32 0
> * %struct_var1.cast = bitcast %struct_var1* %struct_var2.gep to i64**
> br label %for.body
>
> for.body:
> ---------
> %arrayidx74 = getelementptr inbounds %struct_var2, %struct_var2*
> %struct_var2.ld, i64 %idxprom73
> * %struct_var2.cast = bitcast %struct_var2* %arrayidx74 to i64**
> %for.body.ld = load i64, i64* %*struct_var2.cast*, align 8
> ---------
> br i1 %cmp2, label %if.then, label %if.end
>
> if.then:
> %rem = srem i32 1, %arg2
> %add125 = add nuw nsw i32 %rem, 1
> * %arrayidx1705 = getelementptr inbounds [4000 x float], [4000 x float]
> addrspace(3)* @Obj2, i32 0, i32 %add125*
> %arrayidx1705.ld = load float, float addrspace(3)* %*arrayidx1705*,
> align 4
> %arrayidx274.ld = load float, float addrspace(3)* %*arrayidx274*, align
> 4
> ---------
> br label %if.end
>
> if.end:
> store i64 %for.body.ld, i64* %*struct_var1.cast*, align 8
> ---------
> br i1 %cmp3, label %for.body, label %for.end
>
> for.end:
> br exit
>
> exit:
> }
>
>
> ----------------------------------------------------------------------------------------------------------------------------------------------------------
> The actual crash and the back-trace:
>
> ----------------------------------------------------------------------------------------------------------------------------------------------------------
> opt: $SRC/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:2165: const
> llvm::SCEV *llvm::ScalarEvolution::getAddExpr(SmallVectorImpl<const
> llvm::SCEV *> &, SCEV::NoWrapFlags, unsigned int): Assertion
> `getEffectiveSCEVType(Ops[i]->getType()) == ETy && "SCEVAddExpr operand
> types don't match!"' failed.
> PLEASE submit a bug report to https://bugs.llvm.org/
> <https://nam11.safelinks.protection.outlook.com/?url=https%3A%2F%2Fbugs.llvm.org%2F&data=02%7C01%7CChristudasan.Devadasan%40amd.com%7C4a42db7316004baa429c08d83160f7e7%7C3dd8961fe4884e608e11a82d994e183d%7C0%7C0%7C637313639833494292&sdata=L20o6evK45pVbZE4E8csnx6Oc2mBvNihZNNTh0qYMN8%3D&reserved=0>
> and include the crash backtrace.
> Stack dump:
> 0. Program arguments: $Tools/bin/opt -O3 test.ll -o out.ll
>
> llvm::ScalarEvolution::getAddExpr(llvm::SmallVectorImpl<llvm::SCEV
> const*>&, llvm::SCEV::NoWrapFlags, unsigned int)
> $SRC/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:2164:5
> llvm::ScalarEvolution::getAddExpr(llvm::SCEV const*, llvm::SCEV const*,
> llvm::SCEV::NoWrapFlags, unsigned int)
> $SRC/llvm-project/llvm/include/llvm/Analysis/ScalarEvolution.h:526:3
> llvm::ScalarEvolution::getMinusSCEV(llvm::SCEV const*, llvm::SCEV const*,
> llvm::SCEV::NoWrapFlags, unsigned int)
> $SRC/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:3833:3
> getMinFromExprs(llvm::SCEV const*, llvm::SCEV const*,
> llvm::ScalarEvolution*)
> $SRC/llvm-project/llvm/lib/Analysis/LoopAccessAnalysis.cpp:275:15
> llvm::RuntimeCheckingPtrGroup::addPointer(unsigned int)
> $SRC/llvm-project/llvm/lib/Analysis/LoopAccessAnalysis.cpp:292:15
> llvm::RuntimePointerChecking::groupChecks(llvm::EquivalenceClasses<llvm::PointerIntPair<llvm::Value*,
> 1u, bool, llvm::PointerLikeTypeTraits<llvm::Value*>,
> llvm::PointerIntPairInfo<llvm::Value*, 1u,
> llvm::PointerLikeTypeTraits<llvm::Value*> > > >&, bool)
> $SRC/llvm-project/llvm/lib/Analysis/LoopAccessAnalysis.cpp:413:13
> llvm::RuntimePointerChecking::generateChecks(llvm::EquivalenceClasses<llvm::PointerIntPair<llvm::Value*,
> 1u, bool, llvm::PointerLikeTypeTraits<llvm::Value*>,
> llvm::PointerIntPairInfo<llvm::Value*, 1u,
> llvm::PointerLikeTypeTraits<llvm::Value*> > > >&, bool)
> $SRC/llvm-project/llvm/lib/Analysis/LoopAccessAnalysis.cpp:259:12
> (anonymous
> namespace)::AccessAnalysis::canCheckPtrAtRT(llvm::RuntimePointerChecking&,
> llvm::ScalarEvolution*, llvm::Loop*, llvm::DenseMap<llvm::Value const*,
> llvm::Value*, llvm::DenseMapInfo<llvm::Value const*>,
> llvm::detail::DenseMapPair<llvm::Value const*, llvm::Value*> > const&,
> bool) $SRC/llvm-project/llvm/lib/Analysis/LoopAccessAnalysis.cpp:830:3
> llvm::LoopAccessInfo::analyzeLoop(llvm::AAResults*, llvm::LoopInfo*,
> llvm::TargetLibraryInfo const*, llvm::DominatorTree*)
> $SRC/llvm-project/llvm/lib/Analysis/LoopAccessAnalysis.cpp:2038:8
> llvm::LoopAccessInfo::LoopAccessInfo(llvm::Loop*, llvm::ScalarEvolution*,
> llvm::TargetLibraryInfo const*, llvm::AAResults*, llvm::DominatorTree*,
> llvm::LoopInfo*)
> $SRC/llvm-project/llvm/lib/Analysis/LoopAccessAnalysis.cpp:2222:1
> std::_MakeUniq<llvm::LoopAccessInfo>::__single_object
> std::make_unique<llvm::LoopAccessInfo, llvm::Loop*&,
> llvm::ScalarEvolution*&, llvm::TargetLibraryInfo const*&,
> llvm::AAResults*&, llvm::DominatorTree*&, llvm::LoopInfo*&>(llvm::Loop*&,
> llvm::ScalarEvolution*&, llvm::TargetLibraryInfo const*&,
> llvm::AAResults*&, llvm::DominatorTree*&, llvm::LoopInfo*&)
> /usr/bin/../lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/unique_ptr.h:821:34
> llvm::LoopAccessLegacyAnalysis::getInfo(llvm::Loop*)
> $SRC/llvm-project/llvm/lib/Analysis/LoopAccessAnalysis.cpp:2275:5
> (anonymous
> namespace)::LoopLoadElimination::runOnFunction(llvm::Function&)::'lambda'(llvm::Loop&)::operator()(llvm::Loop&)
> const
> $SRC/llvm-project/llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp:651:53
> llvm::LoopAccessInfo const& llvm::function_ref<llvm::LoopAccessInfo const&
> (llvm::Loop&)>::callback_fn<(anonymous
> namespace)::LoopLoadElimination::runOnFunction(llvm::Function&)::'lambda'(llvm::Loop&)>(long,
> llvm::Loop&) $SRC/llvm-project/llvm/include/llvm/ADT/STLExtras.h:185:5
> llvm::function_ref<llvm::LoopAccessInfo const&
> (llvm::Loop&)>::operator()(llvm::Loop&) const
> $SRC/llvm-project/llvm/include/llvm/ADT/STLExtras.h:203:5
> eliminateLoadsAcrossLoops(llvm::Function&, llvm::LoopInfo&,
> llvm::DominatorTree&, llvm::BlockFrequencyInfo*, llvm::ProfileSummaryInfo*,
> llvm::function_ref<llvm::LoopAccessInfo const& (llvm::Loop&)>)
> $SRC/llvm-project/llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp:618:53
> (anonymous namespace)::LoopLoadElimination::runOnFunction(llvm::Function&)
> $SRC/llvm-project/llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp:649:5
> llvm::FPPassManager::runOnFunction(llvm::Function&)
> $SRC/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1587:23
> llvm::FPPassManager::runOnModule(llvm::Module&)
> $SRC/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1629:16
> (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&)
> $SRC/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1698:23
> llvm::legacy::PassManagerImpl::run(llvm::Module&)
> $SRC/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:614:16
> llvm::legacy::PassManager::run(llvm::Module&)
> $SRC/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1824:3
> main $SRC/llvm-project/llvm/tools/opt/opt.cpp:955:3
> __libc_start_main
> /build/glibc-2ORdQG/glibc-2.27/csu/../csu/libc-start.c:344:0
> _start ($Tools/bin/opt+0xc98b6a)
> Aborted (core dumped)
>
> -----------------------------------------------------------------------------------------------------------------------------------------------------------------
>
> Regards,
> CD
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> <https://nam11.safelinks.protection.outlook.com/?url=https%3A%2F%2Flists.llvm.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fllvm-dev&data=02%7C01%7CChristudasan.Devadasan%40amd.com%7C4a42db7316004baa429c08d83160f7e7%7C3dd8961fe4884e608e11a82d994e183d%7C0%7C0%7C637313639833494292&sdata=vexV9bKO2%2Be4t7ix84mMUfJuSWXHf6hAR8PJSNNtg1k%3D&reserved=0>
>
> <testcase.ll>_______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200727/65717aad/attachment.html>
More information about the llvm-dev
mailing list