DAGCombiner: Assume invariant load cannot alias a store

[arsenm]

Summary

The motivation is to allow GatherAllAliases / FindBetterChain
to not give up on dependent loads of a pointer from constant memory.

This is important for AMDGPU, because most loads are pointers
derived from a load of a kernel argument from constant memory.

[arsenm]

This seems to uncover another problem with FindBetterChain.

A simple case of merging 4 constants stores looks like this:

A, ch = CopyFromReg ...
B, ch = load A:1, (add A:0, ...) invariant
C = store B:1, K0, B
D = store C:1, K1, (add B, 4)
E = store D:1, K2, (add B, 8)
F = store E:1, K3, (add B, 12)

Now that the store is known to not alias the load, GatherAllAliases decides that the best chain for the store at chain F is the CopyFromReg chain, putting it on the same chain as the load. This seems broken, but I don't think it will cause any actual problems.

The store at chain C correctly remains on the chain from the load of the pointer, and the other two stores are untouched because they give up on the MemSDNode of the other stores.

However, if I only have 2 stores,
A, ch = CopyFromReg ...
B, ch = load A:1, (add A:0, ...) invariant
C = store B:1, K0, B
D = store C:1, K1, (add B, 4)

The 2nd store correctly has its chain moved to be the same as the 1st's, which is the correct chain out of the load of the pointer

[reames]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13821

Not sure about this, but is writeMem correct here? At least most places, we use a conservative notion for writes. i.e. it *may* write, not it *must* write. If we had an instruction which may write, but actually just reads in this context, the aliasing could be wrong.

!mayLoad might be a possibility.

13832

Is this case handled by the UseAA option below? I'd really expect it to be. Is enabling that for your target an option?

[arsenm]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13821

The mayLoad/mayStore are properties on a MachineInstr, but these are DAG nodes which I don't think have the same concept.

13832

That's actually the source of the set of problems I'm working on now.

The short version is enabling AA results in worse code partially because of this check.

UseAA enables trying to use FindBetterChain to try to move loads and stores to the same chain, but it doesn't work very well. Pretty much all loads are dependent on the constant kernel argument load, so this fix allows it to work sometimes. However, I run into more problems from that because both the existing code in MergeConsecutiveStores assumes stores are on consecutive chains, and FindBetterChain doesn't do a great job at finding the same chain for all of the adjacent stores.

[arsenm]

Now that the store is known to not alias the load, GatherAllAliases decides that the best chain for the store at chain F is the CopyFromReg chain, putting it on the same chain as the load. This seems broken, but I don't think it will cause any actual problems.

This patch seems to solve the problem of moving the store’s chain to the CopyFromReg’s chain by not continuing the chain search unless the chained node is a MemSDNode. This seems only break 2 tests (PPC/ppc64-align-long-double.ll and SystemZ/spill-01.ll)

• 0001-Don-t-search-up-chain-through-non-memory-dependencie.patch1 KBDownload
• msg-12037-195.html233 BDownload

[arsenm]

ping

[hfinkel]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13821

The situation here is somewhat subtle. writeMem delegates to MachineMemOperand::isStore(), which checks whether the MOStore flag is set. What has this flag set? For the most part, just actual stores (trunc stores, atomic stores, etc.). However, this does include the MMOs on masked stores (which might or might not actually store anything), and also include all memory intrinsic nodes that might write to memory. The intrinsics include things like ISD::PREFETCH (which is tagged as writing for dependency reasons, but never writes anything). In short, care is required. But I think this does not hurt anything assuming you special-case ISD::PREFETCH here, so please do that.

[arsenm]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13821

I don't think prefetch matters here. isAlias's operands are LSBaseSDNode, so this seems to only handle loads and stores. It seems ISD::PREFETCH is a MemSDNode

[hfinkel]

LGTM.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13821

Ah, okay. In that case, then yes, it does not matter here. You may want to add a comment to this effect, however, just in case someone later decides to extend isAlias to handle intrinsics too. That does not seem unlikely. I'm not insisting on it.

[arsenm]

r241948

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

 /// Return true if there is any possibility that the two addresses overlap.
 bool DAGCombiner::isAlias(LSBaseSDNode *Op0, LSBaseSDNode *Op1) const {
   // If they are the same then they must be aliases.
   if (Op0->getBasePtr() == Op1->getBasePtr()) return true;
 
   // If they are both volatile then they cannot be reordered.
   if (Op0->isVolatile() && Op1->isVolatile()) return true;
 
+  // If one operation reads from invariant memory, and the other is a store,
+  // they cannot alias.
+  if (Op0->isInvariant() && Op1->writeMem())
+    return false;
+
+  if (Op1->isInvariant() && Op0->writeMem())
+    return false;
+
   // Gather base node and offset information.
   SDValue Base1, Base2;
   int64_t Offset1, Offset2;
   const GlobalValue *GV1, *GV2;
   const void *CV1, *CV2;
   bool isFrameIndex1 = FindBaseOffset(Op0->getBasePtr(),
                                       Base1, Offset1, GV1, CV1);
   bool isFrameIndex2 = FindBaseOffset(Op1->getBasePtr(),
                                       Base2, Offset2, GV2, CV2);
 
   // If they have a same base address then check to see if they overlap.
   if (Base1 == Base2 || (GV1 && (GV1 == GV2)) || (CV1 && (CV1 == CV2)))
     return !((Offset1 + (Op0->getMemoryVT().getSizeInBits() >> 3)) <= Offset2 ||
              (Offset2 + (Op1->getMemoryVT().getSizeInBits() >> 3)) <= Offset1);

test/CodeGen/AMDGPU/invariant-load-no-alias-store.ll

+; RUN: llc -march=amdgcn -verify-machineinstrs < %s | FileCheck -check-prefix=GCN %s
+
+; GatherAllAliases gives up on trying to analyze cases where the
+; pointer may have been loaded from an aliased store, so make sure
+; that this works and allows moving the stores to a better chain to
+; allow them to be merged merged when it's clear the pointer is loaded
+; from constant/invariant memory.
+
+; GCN-LABEL: {{^}}test_merge_store_constant_i16_invariant_global_pointer_load:
+; GCN: buffer_load_dwordx2 [[PTR:v\[[0-9]+:[0-9]+\]]],
+; GCN: v_mov_b32_e32 [[K:v[0-9]+]], 0x1c8007b
+; GCN: buffer_store_dword [[K]], [[PTR]]
+define void @test_merge_store_constant_i16_invariant_global_pointer_load(i16 addrspace(1)* addrspace(1)* dereferenceable(4096) nonnull %in) #0 {
+  %ptr = load i16 addrspace(1)*, i16 addrspace(1)* addrspace(1)* %in, !invariant.load !0
+  %ptr.1 = getelementptr i16, i16 addrspace(1)* %ptr, i64 1
+  store i16 123, i16 addrspace(1)* %ptr, align 4
+  store i16 456, i16 addrspace(1)* %ptr.1
+  ret void
+}
+
+; GCN-LABEL: {{^}}test_merge_store_constant_i16_invariant_constant_pointer_load:
+; GCN: s_load_dwordx2 s{{\[}}[[SPTR_LO:[0-9]+]]:[[SPTR_HI:[0-9]+]]{{\]}}
+; GCN: v_mov_b32_e32 [[K:v[0-9]+]], 0x1c8007b
+; GCN: buffer_store_dword [[K]], s{{\[}}[[SPTR_LO]]:
+define void @test_merge_store_constant_i16_invariant_constant_pointer_load(i16 addrspace(1)* addrspace(2)* dereferenceable(4096) nonnull %in) #0 {
+  %ptr = load i16 addrspace(1)*, i16 addrspace(1)* addrspace(2)* %in, !invariant.load !0
+  %ptr.1 = getelementptr i16, i16 addrspace(1)* %ptr, i64 1
+  store i16 123, i16 addrspace(1)* %ptr, align 4
+  store i16 456, i16 addrspace(1)* %ptr.1
+  ret void
+}
+
+!0 = !{}
+
+attributes #0 = { nounwind }
 No newline at end of file