This is an archive of the discontinued LLVM Phabricator instance.

Differential D18062

Fix Load Control Dependence in MemCpy Generation
ClosedPublic

Authored by niravd on Mar 10 2016, 2:05 PM.

Details

Reviewers
jyknight
• tstellarAMD
hfinkel
Commits
rG66f485f4e291: Fix Load Control Dependence in MemCpy Generation
rL265836: Fix Load Control Dependence in MemCpy Generation
Summary

In Memcpy lowering we had missed a dependence from the load of the operation to successor operations. This causes us to potentially construct an in initial DAG with a memory dependence not fully represented in the chain sub-DAG but rather require looking at the entire DAG breaking alias analysis by allowing incorrect repositioning of memory operations.

To work around this, r200033 changed DAGCombiner::GatherAllAliases to be conservative if any possible issues to happen. Unfortunately this check forbade many non-problematic situations as well. For example, it's common for incoming argument lowering to add a non-aliasing load hanging off of EntryNode. Then, if GatherAllAliases visited EntryNode, it would find that other (unvisited) use of the EntryNode chain, and just give up entirely. Furthermore, the check was incomplete: it would not actually detect all such potentially problematic DAG constructions, because GatherAllAliases did not guarantee to visit all chain nodes going up to the root EntryNode. This is in general fine -- giving up early will just miss a potential optimization, not generate incorrect results. But, for this non-chain dependency detection code, it's possible that you could have a load attached to a higher-up chain node than any which were visited. If that load aliases your store, but the only dependency is through the value operand of a non-aliasing store, it would've been missed by this code, and potentially reordered.

With the dependence added, this check can be removed and Alas Analysis can be much more aggressive. This fixes code quality regression in the Consecutive Store Merge cleanup (D14834).

Test Change:

ppc64-align-long-double.ll now may see multiple serializations
of its stores

Diff Detail

Repository
rL LLVM

Event Timeline

niravd updated this revision to Diff 50349.Mar 10 2016, 2:05 PM
niravd retitled this revision from to Fix Load Control Dependence in MemCpy Generation.
niravd updated this object.
niravd added reviewers: jyknight, hfinkel.
jyknight edited edge metadata.Mar 11 2016, 8:51 AM

Great! I'm fairly certain the reasoning we discussed (and that I've written below) is correct, but I'd really appreciate if Hal would chime in too, as a sanity check.

A longer commit message is really needed here, though, since it's pretty tricky. Here's more description:

In memcpy lowering, add dependency on loads to outgoing chain, and revert the hack added in r200033.
The code in DAGCombiner::GatherAllAliases which this deletes was a hack which guarded against a situation that ought not to occur -- a memory dependency which has been expressed only through value dependence. All such memory dependencies ought to be encoded by the chain, not by random other dag value edges.

That is trivially true for all loads and stores coming directly from IR (since they all start chained together, and only get relaxed by alias analysis), but other DAG-building code must handle the chain properly as well to preserve that property. Unfortunately, memcpy lowering did not, which is what prompted the hack to be added in the first place.

Unfortunately, the check was not just theoretically-redundant, but also forbade many situations which were not problematic. For example, it's common for incoming argument lowering to add a non-aliasing load hanging off of EntryNode. Then, if GatherAllAliases visited EntryNode, it would find that other (unvisited) use of the EntryNode chain, and just give up entirely.

Furthermore, the check was incomplete: it would not actually detect all such potentially problematic DAG constructions, because GatherAllAliases did not guarantee to visit all chain nodes going up to the root EntryNode. This is in general fine -- giving up early will just miss a potential optimization, not generate incorrect results. But, for this non-chain dependency detection code, it's possible that you could have a load attached to a higher-up chain node than any which were visited. If that load aliases your store, but the only dependency is through the value operand of a non-aliasing store, it would've been missed by this code, and potentially reordered.

safely lift instructions in cases.

You mean "in some cases"?

niravd added a child revision: D14834: In visitSTORE, always use FindBetterChain, rather than only when UseAA is enabled..Mar 17 2016, 12:31 PM
niravd updated this revision to Diff 51038.Mar 18 2016, 10:26 AM
niravd edited edge metadata.
  • In visitSTORE, always use FindBetterChain, rather than only when UseAA
Herald added a reviewer: • tstellarAMD. · View Herald TranscriptMar 18 2016, 10:26 AM
Herald added subscribers: dsanders, qcolombet. · View Herald Transcript
niravd updated this revision to Diff 51043.Mar 18 2016, 10:44 AM
niravd edited edge metadata.

Overwrite accidentally added diff

niravd added a subscriber: llvm-commits.Mar 21 2016, 10:58 AM
niravd updated this object.Mar 21 2016, 11:21 AM
niravd updated this revision to Diff 51196.Mar 21 2016, 11:25 AM
  • In visitSTORE, always use FindBetterChain, rather than only when UseAA
niravd added a subscriber: niravd.Mar 21 2016, 11:29 AM

Oops. I didn't send this to the mailing list so the summary is missing.
Adding below:

In Memcpy lowering we had missed a dependence from the load of the
operation to successor operations. This causes us to potentially construct
an in initial DAG with a memory dependence not fully represented in the
chain sub-DAG but rather require looking at the entire DAG breaking alias
analysis by allowing incorrect repositioning of memory operations.

To work around this, r200033 changed DAGCombiner::GatherAllAliases to be
conservative if any possible issues to happen. Unfortunately this check
forbade many non-problematic situations as well. For example, it's common
for incoming argument lowering to add a non-aliasing load hanging off of
EntryNode. Then, if GatherAllAliases visited EntryNode, it would find that
other (unvisited) use of the EntryNode chain, and just give up entirely.
Furthermore, the check was incomplete: it would not actually detect all
such potentially problematic DAG constructions, because GatherAllAliases
did not guarantee to visit all chain nodes going up to the root EntryNode.
This is in general fine -- giving up early will just miss a potential
optimization, not generate incorrect results. But, for this non-chain
dependency detection code, it's possible that you could have a load
attached to a higher-up chain node than any which were visited. If that
load aliases your store, but the only dependency is through the value
operand of a non-aliasing store, it would've been missed by this code, and
potentially reordered.

With the dependence added, this check can be removed and Alas Analysis can
be much more aggressive. This fixes code quality regression in the
Consecutive Store Merge cleanup (D14834).

Test Change:

ppc64-align-long-double.ll now may see multiple serializations
of its stores

niravd added a comment.Mar 23 2016, 10:56 AM

Ping. Your thoughts on this Hal?

hfinkel edited edge metadata.Mar 23 2016, 12:02 PM
In D18062#381709, @niravd wrote:

Ping. Your thoughts on this Hal?

This is quite interesting. The question is: Can we guarantee that all data dependencies are also encoded as chain dependencies? If so, then I'm happy with this -- although I'd also like some loud comments (maybe in include/llvm/CodeGen/ISDOpcodes.h), and ideally some verification code which can be enabled under expensive checks.

My worry here is not just about what we generate, but about what FindBetterChain might do. It would need to specifically not remove a chain dependency that was present to protect/represent a value dependency.

ppc64-align-long-double.ll now may see multiple serializations of its stores

What does this mean? I see you've put in CHECK-DAGs, but do you mean the order has changed or that there are now multiple stores?

jyknight added a comment.Mar 23 2016, 12:39 PM
In D18062#381815, @hfinkel wrote:
In D18062#381709, @niravd wrote:

Ping. Your thoughts on this Hal?

This is quite interesting. The question is: Can we guarantee that all data dependencies are also encoded as chain dependencies? If so, then I'm happy with this -- although I'd also like some loud comments (maybe in include/llvm/CodeGen/ISDOpcodes.h), and ideally some verification code which can be enabled under expensive checks.

*NO* we can't, as is exemplified by newly reported issue in D18336 (which is broken both before and after this change). However, what we *should* guarantee is that memory dependencies are always encoded by the chain, and not indirectly through value dependencies. That was what was happening before, in the memcpy expansion, and what ought not happen.

To fix that other issue, we will need to ensure none of the stores being merged are a predecessor of any others.

My worry here is not just about what we generate, but about what FindBetterChain might do. It would need to specifically not remove a chain dependency that was present to protect/represent a value dependency.

Well, this code being removed here did not actually try to prevent that. As it turns out, neither did anything else. (But that's another bug!)

I think the chain should not need to represent value dependencies (it doesn't now), but neither should value dependencies represent memory ordering dependencies (and this hack added because memcpy was using them that way).

ppc64-align-long-double.ll now may see multiple serializations of its stores

What does this mean? I see you've put in CHECK-DAGs, but do you mean the order has changed or that there are now multiple stores?

niravd added a comment.Mar 23 2016, 1:17 PM

ppc64-align-long-double.ll now may see multiple serializations of its stores

What does this mean? I see you've put in CHECK-DAGs, but do you mean the order has changed or that there are now multiple stores?

Just that we no longer have an order dependencies so the store so they may appear in any order.

niravd added a parent revision: D18336: Prevent construction of cycle in DAG store merge.Mar 24 2016, 11:23 AM
niravd added a comment.EditedMar 28 2016, 7:06 AM

Now that D18336 is committed, Hal's concerns should be addressed so I think we can move on this.

niravd mentioned this in D18546: Prevent X86IselLowering from merging volatile loads.Mar 30 2016, 7:14 AM
spatel added a subscriber: spatel.Mar 30 2016, 7:34 AM
jyknight accepted this revision.Apr 8 2016, 11:27 AM
jyknight edited edge metadata.

LGTM.

This revision is now accepted and ready to land.Apr 8 2016, 11:27 AM
Closed by commit rL265836: Fix Load Control Dependence in MemCpy Generation (authored by niravd). · Explain WhyApr 8 2016, 12:50 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents

PathSize
llvm/
trunk/
lib/
CodeGen/
SelectionDAG/
57 lines
1 line
test/
CodeGen/
PowerPC/
16 lines

Diff 53065

llvm/trunk/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

  • This file is larger than 256 KB, so syntax highlighting is disabled by default.
Show First 20 Lines • Show All 14,704 Lines • ▼ Show 20 Lines case ISD::TokenFactor:
break; break;
default: default:
// For all other instructions we will just have to take what we can get. // For all other instructions we will just have to take what we can get.
Aliases.push_back(Chain); Aliases.push_back(Chain);
break; break;
} }
} }
// We need to be careful here to also search for aliases through the
// value operand of a store, etc. Consider the following situation:
// Token1 = ...
// L1 = load Token1, %52
// S1 = store Token1, L1, %51
// L2 = load Token1, %52+8
// S2 = store Token1, L2, %51+8
// Token2 = Token(S1, S2)
// L3 = load Token2, %53
// S3 = store Token2, L3, %52
// L4 = load Token2, %53+8
// S4 = store Token2, L4, %52+8
// If we search for aliases of S3 (which loads address %52), and we look
// only through the chain, then we'll miss the trivial dependence on L1
// (which also loads from %52). We then might change all loads and
// stores to use Token1 as their chain operand, which could result in
// copying %53 into %52 before copying %52 into %51 (which should
// happen first).
//
// The problem is, however, that searching for such data dependencies
// can become expensive, and the cost is not directly related to the
// chain depth. Instead, we'll rule out such configurations here by
// insisting that we've visited all chain users (except for users
// of the original chain, which is not necessary). When doing this,
// we need to look through nodes we don't care about (otherwise, things
// like register copies will interfere with trivial cases).
SmallVector<const SDNode *, 16> Worklist;
for (const SDNode *N : Visited)
if (N != OriginalChain.getNode())
Worklist.push_back(N);
while (!Worklist.empty()) {
const SDNode *M = Worklist.pop_back_val();
// We have already visited M, and want to make sure we've visited any uses
// of M that we care about. For uses that we've not visisted, and don't
// care about, queue them to the worklist.
for (SDNode::use_iterator UI = M->use_begin(),
UIE = M->use_end(); UI != UIE; ++UI)
if (UI.getUse().getValueType() == MVT::Other &&
Visited.insert(*UI).second) {
if (isa<MemSDNode>(*UI)) {
// We've not visited this use, and we care about it (it could have an
// ordering dependency with the original node).
Aliases.clear();
Aliases.push_back(OriginalChain);
return;
}
// We've not visited this use, but we don't care about it. Mark it as
// visited and enqueue it to the worklist.
Worklist.push_back(*UI);
}
}
} }
/// Walk up chain skipping non-aliasing memory nodes, looking for a better chain /// Walk up chain skipping non-aliasing memory nodes, looking for a better chain
/// (aliasing node.) /// (aliasing node.)
SDValue DAGCombiner::FindBetterChain(SDNode *N, SDValue OldChain) { SDValue DAGCombiner::FindBetterChain(SDNode *N, SDValue OldChain) {
SmallVector<SDValue, 8> Aliases; // Ops for replacing token factor. SmallVector<SDValue, 8> Aliases; // Ops for replacing token factor.
// Accumulate all the aliases to this node. // Accumulate all the aliases to this node.
▲ Show 20 Lines • Show All 101 Lines • Show Last 20 Lines

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

  • This file is larger than 256 KB, so syntax highlighting is disabled by default.
Show First 20 Lines • Show All 4,388 Lines • ▼ Show 20 Lines if (!Store.getNode()) {
// to Load/Store if NVT==VT. // to Load/Store if NVT==VT.
// FIXME does the case above also need this? // FIXME does the case above also need this?
EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT); EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
assert(NVT.bitsGE(VT)); assert(NVT.bitsGE(VT));
Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain, Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
DAG.getMemBasePlusOffset(Src, SrcOff, dl), DAG.getMemBasePlusOffset(Src, SrcOff, dl),
SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false, SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
false, MinAlign(SrcAlign, SrcOff)); false, MinAlign(SrcAlign, SrcOff));
OutChains.push_back(Value.getValue(1));
Store = DAG.getTruncStore(Chain, dl, Value, Store = DAG.getTruncStore(Chain, dl, Value,
DAG.getMemBasePlusOffset(Dst, DstOff, dl), DAG.getMemBasePlusOffset(Dst, DstOff, dl),
DstPtrInfo.getWithOffset(DstOff), VT, isVol, DstPtrInfo.getWithOffset(DstOff), VT, isVol,
false, Align); false, Align);
} }
OutChains.push_back(Store); OutChains.push_back(Store);
SrcOff += VTSize; SrcOff += VTSize;
DstOff += VTSize; DstOff += VTSize;
▲ Show 20 Lines • Show All 2,923 Lines • Show Last 20 Lines

llvm/trunk/test/CodeGen/PowerPC/ppc64-align-long-double.ll

Show All 12 Lines
define ppc_fp128 @test(%struct.S* byval %x) nounwind { define ppc_fp128 @test(%struct.S* byval %x) nounwind {
entry: entry:
%b = getelementptr inbounds %struct.S, %struct.S* %x, i32 0, i32 1 %b = getelementptr inbounds %struct.S, %struct.S* %x, i32 0, i32 1
%0 = load ppc_fp128, ppc_fp128* %b, align 16 %0 = load ppc_fp128, ppc_fp128* %b, align 16
ret ppc_fp128 %0 ret ppc_fp128 %0
} }
; CHECK: std 6, 72(1) ; CHECK-DAG: std 6, 72(1)
; CHECK: std 5, 64(1) ; CHECK-DAG: std 5, 64(1)
; CHECK: std 4, 56(1) ; CHECK-DAG: std 4, 56(1)
; CHECK: std 3, 48(1) ; CHECK-DAG: std 3, 48(1)
; CHECK: lfd 1, 64(1) ; CHECK: lfd 1, 64(1)
; CHECK: lfd 2, 72(1) ; CHECK: lfd 2, 72(1)
; CHECK-VSX: std 6, 72(1) ; CHECK-VSX-DAG: std 6, 72(1)
; CHECK-VSX: std 5, 64(1) ; CHECK-VSX-DAG: std 5, 64(1)
; CHECK-VSX: std 4, 56(1) ; CHECK-VSX-DAG: std 4, 56(1)
; CHECK-VSX: std 3, 48(1) ; CHECK-VSX-DAG: std 3, 48(1)
; CHECK-VSX: li 3, 16 ; CHECK-VSX: li 3, 16
; CHECK-VSX: addi 4, 1, 48 ; CHECK-VSX: addi 4, 1, 48
; CHECK-VSX: lxsdx 1, 4, 3 ; CHECK-VSX: lxsdx 1, 4, 3
; CHECK-VSX: li 3, 24 ; CHECK-VSX: li 3, 24
; CHECK-VSX: lxsdx 2, 4, 3 ; CHECK-VSX: lxsdx 2, 4, 3