This is an archive of the discontinued LLVM Phabricator instance.

[DemandedBits] Use SetVector for Worklist
ClosedPublic

Authored by nikic on Jan 6 2019, 9:50 AM.

Details

Summary

DemandedBits currently uses a simple vector for the worklist, which means that instructions may be inserted multiple times into it. Especially in combination with the deep lattice, this may cause instructions too be recomputed very often. To avoid this, switch to a SetVector.

Here's two debug traces for a very simple example before and after this change: https://gist.github.com/nikic/83ea77186f1b873725135299b31aff3c Notice that %x is recomputed 31 times before and once after.

Diff Detail

Repository
rL LLVM

Event Timeline

nikic created this revision.Jan 6 2019, 9:50 AM
hfinkel accepted this revision.Jan 7 2019, 9:22 AM

LGTM

This revision is now accepted and ready to land.Jan 7 2019, 9:22 AM
This revision was automatically updated to reflect the committed changes.
nikic reopened this revision.Jan 7 2019, 10:21 AM

Aaand reverted :/ Assertion failure in clang CodeGen/builtins-systemz-zvector.c:

clang: /srv/llvm-buildbot-srcatch/llvm-build-dir/clang-x86_64-debian-fast/llvm.src/include/llvm/ADT/DenseMap.h:1167: llvm::SmallDenseMap::LargeRep llvm::SmallDenseMap<llvm::Instruction *, llvm::detail::DenseSetEmpty, 128, llvm::DenseMapInfo<llvm::Instruction *>, llvm::detail::DenseSetPair<llvm::Instruction *> >::allocateBuckets(unsigned int) [KeyT = llvm::Instruction *, ValueT = llvm::detail::DenseSetEmpty, InlineBuckets = 128, KeyInfoT = llvm::DenseMapInfo<llvm::Instruction *>, BucketT = llvm::detail::DenseSetPair<llvm::Instruction *>]: Assertion `Num > InlineBuckets && "Must allocate more buckets than are inline"' failed.

This revision is now accepted and ready to land.Jan 7 2019, 10:21 AM
fhahn added a subscriber: fhahn.Jan 8 2019, 4:41 AM
nikic updated this revision to Diff 180739.Jan 8 2019, 2:29 PM

Use less inline elements in SmallSetVector.

nikic added a comment.Jan 8 2019, 2:32 PM

I've submitted D56455 to fix the SmallDenseMap bug this triggered. Also reduced this to use 16 instead of 128 inline elements. That seems to be a more typical value and also sidesteps the issue :)

This revision was automatically updated to reflect the committed changes.