Page MenuHomePhabricator

[ADT] Allow K to be incomplete during DenseMap<K*, V> instantiation
ClosedPublic

Authored by rnk on Feb 27 2020, 1:26 PM.

Details

Summary

DenseMap requires two sentinel values for keys: empty and tombstone
values. To avoid undefined behavior, LLVM aligns the two sentinel
pointers to alignof(T). This requires T to be complete, which is
needlessly restrictive.

Instead, assume that DenseMap pointer keys have a maximum alignment of
4096, and use the same sentinel values for all pointer keys. The new
sentinels are:

empty:     static_cast<uintptr_t>(-1) << 12
tombstone: static_cast<uintptr_t>(-2) << 12

These correspond to the addresses of -4096 and -8192. Hopefully, such a
key is never inserted into a DenseMap.

I encountered this while looking at making clang's SourceManager not
require FileManager.h, but it has several maps keyed on classes defined
in FileManager.h. FileManager depends on various LLVM FS headers, which
cumulatively take ~200ms to parse, and are generally not needed.

Diff Detail

Event Timeline

rnk created this revision.Feb 27 2020, 1:26 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 27 2020, 1:26 PM
hans accepted this revision.Feb 28 2020, 1:48 AM

These correspond to the addresses of -4096 and -8192. Hopefully, such a key is never inserted into a DenseMap.

Maybe we could have an assert somewhere which checks that an empty or tombstone marker is never inserted by the user?

This revision is now accepted and ready to land.Feb 28 2020, 1:48 AM
rnk added a comment.Feb 28 2020, 12:29 PM

Yes, DenseMap already asserts if you try to lookup or insert the two sentinel keys. My comment had more to do with -4096 being a more plausible pointer value than -16/-8, so we are marginally more likely to hit that assert, maybe in a kernel context, like opencl drivers.

This revision was automatically updated to reflect the committed changes.