This is an archive of the discontinued LLVM Phabricator instance.

[ADCE] Use MapVector for BlockInfo to make iteration order deterministic
ClosedPublic

Authored by uabelho on Nov 3 2017, 5:28 AM.

Details

Summary

Also added a reserve() method to MapVector since we want to use that from
ADCE.

DenseMap does not provide deterministic iteration order so with that
we will handle the members of BlockInfo in random order, eventually
leading to random order of the blocks in the predecessor lists.

Without this change, I get the same predecessor order in about 90% of the
time when I compile a certain reproducer and in 10% I get a different one.

No idea how to make a proper test case for this.

Diff Detail

Event Timeline

uabelho created this revision.Nov 3 2017, 5:28 AM

I don't know who should review this. Added David, who seems to have introduced the BlockInfo map,
and Jakub who has done non-NFC changes to ADCE fairly recently.

I see the random changes in output when I run opt on the attached foo.ll with:

opt -S -Os -o foo.opt.ll foo.ll -bdce -jump-threading -adce

In some cases I get
bb11: ; preds = %bb8, %bb4
and in some cases I get
bb11: ; preds = %bb4, %bb8

kuhar added inline comments.Nov 3 2017, 5:43 AM
lib/Transforms/Scalar/ADCE.cpp
214

I can see that MapVector doesn't expose .reserve -- what is the reason for that? While I don't claim that it would have any noticeable performance impact here, I'm a bit surprised by that.

uabelho added inline comments.Nov 3 2017, 5:50 AM
lib/Transforms/Scalar/ADCE.cpp
214

Unfortunately I have no idea. I just noticed there is no such function, and thus removed the call.

I don't really understand the comment preceding the original reserve call though, it says "so we grow the structure to twice that size", but then it only reserves NumBlocks anyway? Not 2*Numblocks?

kuhar added inline comments.Nov 3 2017, 6:05 AM
lib/Transforms/Scalar/ADCE.cpp
214

I think it was meant to be .reserve(NumBlocks * 2), but it also makes sense to just reduce the number of allocations.

I looked at MapVector and it should very easy to add reserve to it. Then, I think it would make sense to keep it here, and to update the comment or size for whichever makes more sense.

uabelho updated this revision to Diff 121467.Nov 3 2017, 6:27 AM
uabelho edited the summary of this revision. (Show Details)

Added a reserve method to MapVector, and restored the call to BlockInfo.reserve(NumBlocks) in ADCE.

MapVector::reserve() just passes on the call to Vector.reserve()

uabelho added inline comments.Nov 3 2017, 6:28 AM
lib/Transforms/Scalar/ADCE.cpp
214

Yes, you're right. I created a reserve method now. I left the original reserve code and comment in ADCE
in place since I don't know what makes most sense, and also, fixing the amout we reserve is not the focus of this patch anyway.

kuhar added inline comments.Nov 3 2017, 6:28 AM
include/llvm/ADT/MapVector.h
62 ↗(On Diff #121467)

Shouldn't this reserve Map as well?

uabelho added inline comments.Nov 3 2017, 6:34 AM
include/llvm/ADT/MapVector.h
62 ↗(On Diff #121467)

Ah, I guess so. Sorry, I'll update. Thanks!

uabelho updated this revision to Diff 121468.Nov 3 2017, 6:47 AM

Pass on MapVector::reserve to Map.reserve() as well as Vector.reserve()

uabelho marked an inline comment as done.Nov 3 2017, 6:48 AM
kuhar accepted this revision.Nov 3 2017, 6:48 AM

LGTM

This revision is now accepted and ready to land.Nov 3 2017, 6:48 AM

Thanks a bunch for the comments! I'll push this in a bit.

This revision was automatically updated to reflect the committed changes.