Page MenuHomePhabricator

[LoopVectorize] Use MapVector rather than DenseMap for MinBWs.
ClosedPublic

Authored by chatur01 on Nov 25 2015, 3:39 AM.

Details

Summary

The order in which instructions are truncated in truncateToMinimalBitwidths
effects code generation. Switch to a map with a determinisic order, since the
iteration order over a DenseMap is not defined.

This code is not hot, so the difference in container performance isn't
interesting.

Many thanks to David Blaikie for making me aware of MapVector!

Fixes PR25490.

Diff Detail

Repository
rL LLVM

Event Timeline

chatur01 retitled this revision from to [LoopVectorize] Use std::map rather than DenseMap for MinBWs..
chatur01 updated this object.
chatur01 added reviewers: jmolloy, mcrosier.
chatur01 set the repository for this revision to rL LLVM.
chatur01 added a subscriber: llvm-commits.

Hi Charlie,

The iteration order over std::map is defined by the order of the keys (Instruction *). Wouldn't this also be non-deterministic?

Thanks,
Silviu

chatur01 abandoned this revision.Nov 25 2015, 4:06 AM

Yep, thanks Silviu. I messed this up. I fixed the small testcase in the PR (by luck) and not the larger ones I have access to. Apologies.

We have mapvector, if the insertion order is stable

chatur01 retitled this revision from [LoopVectorize] Use std::map rather than DenseMap for MinBWs. to [LoopVectorize] Use MapVector rather than DenseMap for MinBWs..
chatur01 updated this object.
chatur01 removed rL LLVM as the repository for this revision.

Nice one David! This saved me from publishing a nasty hack to maintain my own vector in LoopVectorize.

The insertion order looks stable to me. It comes from computeMinimumValueSizes in VectorUtils. They get inserted into the MapVector from the equivalence class iterators (driven underneath by an ordered set), which in turn are created from a vector of Value* in basic block order.

My larger test case no longer has non-determinisic order, as well as the test-case in the PR.

dblaikie accepted this revision.Nov 25 2015, 11:59 AM
dblaikie added a reviewer: dblaikie.

Looks good. I assume you're going to (re)commit the now-stable test along with this?

(generally I think it better to revert the actual instability (it is a bug - we really don't want unstable output of the compiler) along with the test if it's got problems - then recommit with the fix together)

A couple of places look like they're doing excess copying of this data structure - perhaps you could fix those (if I've correctly diagnosed them) in a separate commit?

lib/Transforms/Vectorize/LoopVectorize.cpp
329 ↗(On Diff #41158)

Tangentially related: Isn't there a std::move missing here? (the argument is passed by value, allowing movement from the caller, then copied into the member when it could be moved instead)

1893 ↗(On Diff #41158)

looks like MinBWs isn't used after this point (similarly in the else clause) & could be std::moved in both places?

This revision is now accepted and ready to land.Nov 25 2015, 11:59 AM
chatur01 edited edge metadata.

Added a test-case. This might violate the test guidelines of only comitting robust test cases. By definition I can't do that for a non-determinism bug, but I'm running the test case 5 times, which at least locally was always enough to catch the non-determinism on my computer, of course I can't guarantee that.

I'm requesting a sanity check on my test case before comitting it.

Many thanks again David for your review.

mcrosier edited edge metadata.Nov 26 2015, 11:31 AM

FWIW, the test case provided in the PR was reduced from an external benchmark. I don't believe a simpler test can be created.

This revision was automatically updated to reflect the committed changes.