Page MenuHomePhabricator

[MemorySSA] Use SetVector to avoid nondeterminism.
ClosedPublic

Authored by asbirlea on Thu, Jul 11, 3:11 PM.

Diff Detail

Repository
rL LLVM

Event Timeline

asbirlea created this revision.Thu, Jul 11, 3:11 PM
Herald added a project: Restricted Project. · View Herald TranscriptThu, Jul 11, 3:11 PM

I'd be interested if there's a better way to use a SmallSetVector, without needing the "8". I don't see an Impl version.
The only alternative I came up with was something like:

template <class OrderedSetT>
void removeBlocks(const OrderedSetT &DeadBlocks);

I'd be interested if there's a better way to use a SmallSetVector, without needing the "8". I don't see an Impl version.
The only alternative I came up with was something like:

template <class OrderedSetT>
void removeBlocks(const OrderedSetT &DeadBlocks);

You can use SetVector's "getArrayRef" and pass it as "void removeBlocks(ArrayRef<BasicBlock *> DeadBlocks);"

You can use SetVector's "getArrayRef" and pass it as "void removeBlocks(ArrayRef<BasicBlock *> DeadBlocks);"

removeBlocks is querying DeadBlocks with count(...). I can change the code to walk the Vector/ArrayRef, but it defeats the purpose of building a set.
It may be ok to change all callsites to just use vector too, assuming the normal expected size is small, but it may be costly for pathological cases (large number of deadblocks).
If folks have a preference either way, please let me know.

You can use SetVector's "getArrayRef" and pass it as "void removeBlocks(ArrayRef<BasicBlock *> DeadBlocks);"

removeBlocks is querying DeadBlocks with count(...). I can change the code to walk the Vector/ArrayRef, but it defeats the purpose of building a set.
It may be ok to change all callsites to just use vector too, assuming the normal expected size is small, but it may be costly for pathological cases (large number of deadblocks).
If folks have a preference either way, please let me know.

Oh, sorry, I didn't look too closely & thought it was only iterating over the container.

Yeah, I'd just leave it the way you had it with the 8 in there.

Thanks! If it's easy to come up with a small regression test (like David mentioned on the bug, reverse_iteration may be a great help), please do so and commit it with this. Otherwise, LGTM as-is.

Yeah, I'd just leave it the way you had it with the 8 in there.

+1.

This revision is now accepted and ready to land.Thu, Jul 11, 4:27 PM

Hmm, AFAICT, there is no opt flag equivalent for LLVM_ENABLE_REVERSE_ITERATION. Did I miss it?

Would adding Mikael's test with the following checks work? I'm thinking the use list order is pretty specific to add as a CHECK, hence the arch restriction, but it may still be too specific.

; RUN: opt -simplifycfg -enable-mssa-loop-dependency -S --preserve-ll-uselistorder %s | FileCheck %s
; REQUIRES: x86-registered-target
; CHECK-LABEL: @n
; CHECK: uselistorder i16 0, { 3, 2, 4, 1, 5, 0, 6 }

Hmm, AFAICT, there is no opt flag equivalent for LLVM_ENABLE_REVERSE_ITERATION. Did I miss it?

Nah, you didn't miss it - for performance reasons (I think/assume/vaguely recall) it's not a value that can be changed at runtime - it's a compile time configuration option.

Much like writing a test that fails (or, once some bug is fixed, passes) under asan - it's OK that a test might have only demonstrated the failure under one build mode or another, not necessarily under all of them. (heck, lots of tests are run against specific targets (which isn't always great, because sometimes the tests could be written portably and aren't (I've done this as much/more than anyone else - lots of the debug info tests are x86 only)) - which aren't compiled on every buildbot)

Would adding Mikael's test with the following checks work? I'm thinking the use list order is pretty specific to add as a CHECK, hence the arch restriction, but it may still be too specific.

; RUN: opt -simplifycfg -enable-mssa-loop-dependency -S --preserve-ll-uselistorder %s | FileCheck %s
; REQUIRES: x86-registered-target
; CHECK-LABEL: @n
; CHECK: uselistorder i16 0, { 3, 2, 4, 1, 5, 0, 6 }

If the test case is as reduced as possible while still demonstrating a change in behavior between forward and reverse iteration - yeah, I think that's OK. (not ideal, and maybe leave a note that the test case might not carry its weight - if someone in the future finds maintaining the test to be especially burdensome, it can probably be deleted without a huge deal)

Does this test case exercise/justify all the container changes in this patch? (seemed like a lot of containers got changed - which I'm a bit wary of because the non-ordered containers are more efficient, so best not to switch to them unnecessarily)

  • Dave

I don't know if a bot exists with LLVM_ENABLE_REVERSE_ITERATION set to true, but if it does, then the check I proposed for the uselist order would likely fail, no?

; CHECK: uselistorder i16 0, { 3, 2, 4, 1, 5, 0, 6 }

Does this test case exercise/justify all the container changes in this patch?

The test shows the need for an ordered container in removeBlocks. The patch changes all callsites for this method, and the sets it changes are also not used for much except the call to removeBlocks, so I think it should be fine.

I don't know if a bot exists with LLVM_ENABLE_REVERSE_ITERATION set to true, but if it does, then the check I proposed for the uselist order would likely fail, no?

I believe there is (or some people with a vested interest in it - they might not be testing with an official buildbot). I think it's appropriate for you to validate that the test/change are justified by the reverse iteration mode before committing (by using a local build with reverse iteration).

; CHECK: uselistorder i16 0, { 3, 2, 4, 1, 5, 0, 6 }

Does this test case exercise/justify all the container changes in this patch?

The test shows the need for an ordered container in removeBlocks. The patch changes all callsites for this method, and the sets it changes are also not used for much except the call to removeBlocks, so I think it should be fine.

Ah, makes sense - sorry for being vague/not looking more closely at the patch.

Does it seem like all call sites have the same ordering requirement? (or could some callers benefit from/get away with an unordered container?) - maybe that question's not worth trying to answer, not sure.

asbirlea updated this revision to Diff 209612.Fri, Jul 12, 3:05 PM

Add test.
Tested with LLVM_ENABLE_REVERSE_ITERATION enabled and without.

asbirlea updated this revision to Diff 209616.Fri, Jul 12, 3:11 PM

Add comment in test.

dblaikie accepted this revision.Fri, Jul 12, 3:13 PM

Sounds good!

I'm planning to go ahead with the patch as is, and if the test tickles any bots, we can disable/remove/update it.

This revision was automatically updated to reflect the committed changes.