This is an archive of the discontinued LLVM Phabricator instance.

[DAGCombine] Fix alias analysis for unaligned accesses
ClosedPublic

Authored by dmgreen on Feb 27 2020, 4:00 AM.

Details

Summary

The alias analysis in DAG Combine looks at the BaseAlign, the Offset and the Size of two accesses, and determines if they are known to access different parts of memory by the fact that they are different offsets from inside that "alignment window". It does not seem to account for accesses that are not a multiple of the size, and may overflow from one alignment window into another.

For example in the test case we have a 19byte memset that is splits into a 16 byte neon store and an unaligned 4 byte store with a 15 byte offset. This 15byte offset (with a base align of 8) wraps around to the next alignment windows. When compared to an access that is a 16byte offset (of the same 4byte size and 8byte basealign), the two accesses are said not to alias.

I've fixed this here by just ensuring that the offsets are a multiple of the size, ensuring that they don't overlap by wrapping. Fixes PR45035, which was exposed by the UseAA changes in the arm backend.

Diff Detail

Event Timeline

dmgreen created this revision.Feb 27 2020, 4:00 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 27 2020, 4:00 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
nickdesaulniers marked an inline comment as done.Feb 27 2020, 11:15 AM
nickdesaulniers added inline comments.
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
21135

Probably should hoist MUC0.NumBytes and MUC1.NumBytes above the if into their own locals, like the offsets and alignments; would help make this condition and block more readable.

Also, was mod'ing SrcValueOffset1 by *MUC0.NumBytes intentional? Should it be *MUC1.NumBytes?

llvm/test/CodeGen/ARM/memset-align.ll
3

What is going on with this target triple? LOL

srhines marked an inline comment as done.Feb 27 2020, 11:40 AM
srhines added a subscriber: srhines.
srhines added inline comments.
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
21135

*MUC0.NumBytes == *MUC1.NumBytes from earlier in this conditional.

llvm/test/CodeGen/ARM/memset-align.ll
3

The "10000" changes the Android target API level to 10000 (which basically means everything is available). I think it is safe to remove it for the purpose of this test, but @yabinc 's example used this in the command line because of how it works on the platform build for Android.

Thanks for the fix! I have verified that it fixes tests broken by using AA.

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

Still...

dmgreen marked 2 inline comments as done.Feb 27 2020, 2:21 PM

Thanks for the fix! I have verified that it fixes tests broken by using AA.

Brilliant, thanks!

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

Yeah, it was intentional from the fact that they are equal. I can change it though, it sounds cleaner that way.

llvm/test/CodeGen/ARM/memset-align.ll
3

Righteo. I'll changed it to.. thumbv8-unknown-linux-android. Let me know if something else would be better.

dmgreen updated this revision to Diff 247109.Feb 27 2020, 2:27 PM

Added variables and new triple.

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

The hunk you modify on L21156-L21157 highlights was looks like maybe a pre-existing incorrect usage of Optional::operator*; there's no check that MUC0.NumBytes hasValue before making use of the value (which may not exist). In particular, I'm concerned what the value of -1 might do in those expressions.

Or you could do:

auto& Size0 = MUC0.NumBytes;
auto& Size1 = MUC1.NumBytes;

if ( ... && Size0.hasValue() && Size0.hasValue() && ...)
  foo(*Size0, *Size1)

Though I'm not sure whether the lower hunk should have a guard as well vs use a value of 0. Using -1 for a possible value of the Optional<int64_t> might be problematic, though I assume the number of bytes in a "memory use characteristic" is unlikely. (I wish the "LLVM Programmers Manual" had a section on llvm::Optional). So maybe it's ok to keep as is, but then I really think the lower hunk should also have some kind of guard.

dmgreen marked an inline comment as done.Feb 28 2020, 5:07 AM
dmgreen added inline comments.
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
21131

Good point

I chose -1 as it's the same as MemoryLocation::UnknownSize (and only didn't use that directly here as (int64_t)MemoryLocation::UnknownSize makes things difficult to follow with how verbose it is). That Size is not passed straight through to AA->alias below though, so might cause weirdness if there was ever a case where MUC0.MMO had a value but Size didn't.

I'll changed it to how you suggest, with the references, and added the checks below too in case.

dmgreen updated this revision to Diff 247231.Feb 28 2020, 5:09 AM
nickdesaulniers accepted this revision.Feb 28 2020, 10:23 AM

Right on, sorry my suggestion turned into a bit of a yak shave, but I think the added guard may have fixed another pre-existing bug. Assuming that change didn't trip up any exists tests, LGTM. Thanks for the quick fix!

This revision is now accepted and ready to land.Feb 28 2020, 10:23 AM
dmgreen added a subscriber: hans.Feb 28 2020, 10:47 AM

Thanks. The test seem fine and the benchmarks/codesize tests I ran didn't show any change.

I presume this is one for the branch. @hans if this doesn't have any trouble with the buildbots, do you mind?

This revision was automatically updated to reflect the committed changes.