llvm-svn: 158647

I don't know how useful these are for SmallDenseMap, I'll leave that decision to Chandler.

llvm-svn: 158646

It always returns the iterator for the first inserted element, or the passed in
iterator if the inserted range was empty. Flesh out the unit test more and fix
all the cases it uncovered so far.

llvm-svn: 158645

SmallVector: return a valid iterator for the rare case of inserting an empty range into a SmallVector.

Patch by Johannes Schaub!

llvm-svn: 158643

SmallDenseMap::swap.

First, make it parse cleanly. Yay for uninstantiated methods.

Second, make the inline-buckets case work correctly. This is way
trickier than it should be due to the uninitialized values in empty and
tombstone buckets.

Finally fix a few typos that caused construction/destruction mismatches
in the counting unittest.

llvm-svn: 158641

implementation of the class layout for the V8 type.

llvm-svn: 158640

destruction and fix a bug in SmallDenseMap they caught.

This is kind of a poor-man's version of the testing that just adds the
addresses to a set on construction and removes them on destruction. We
check that double construction and double destruction don't occur.
Amusingly enough, this is enough to catch a lot of SmallDenseMap issues
because we spend a lot of time with fixed stable addresses in the inline
buffer.

The SmallDenseMap bug fix included makes grow() not double-destroy in
some cases. It also fixes a FIXME there, the code was pretty crappy. We
now don't have any wasted initialization, but we do move the entries in
inline bucket array an extra time. It's probably a better tradeoff, and
is much easier to get correct.

llvm-svn: 158639

implementation.

This type includes an inline bucket array which is used initially. Once
it is exceeded, an array of 64 buckets is allocated on the heap. The
bucket count grows from there as needed. Some highlights of this
implementation:

- The inline buffer is very carefully aligned, and so supports types
  with alignment constraints.
- It works hard to avoid aliasing issues.
- Supports types with non-trivial constructors, destructors, copy
  constructions, etc. It works reasonably hard to minimize copies and
  unnecessary initialization. The most common initialization is to set
  keys to the empty key, and so that should be fast if at all possible.

This class has a performance / space trade-off. It tries to optimize for
relatively small maps, and so packs the inline bucket array densely into
the object. It will be marginally slower than a normal DenseMap in a few
use patterns, so it isn't appropriate everywhere.

The unit tests for DenseMap have been generalized a bit to support
running over different map implementations in addition to different
key/value types. They've then been automatically extended to cover the
new container through the magic of GoogleTest's typed tests.

All of this is still a bit rough though. I'm going to be cleaning up
some aspects of the implementation, documenting things better, and
adding tests which include non-trivial types. As soon as I'm comfortable
with the correctness, I plan to switch existing users of SmallMap over
to this class as it is already more correct w.r.t. construction and
destruction of objects iin the map.

Thanks to Benjamin Kramer for all the reviews of this and the lead-up
patches. That said, more review on this would really be appreciated. As
I've noted a few times, I'm quite surprised how hard it is to get the
semantics for a hashtable-based map container with a small buffer
optimization correct. =]

llvm-svn: 158638

construct just for my sanity.

llvm-svn: 158637

llvm-svn: 158601

Merge the SmallBitVector and BitVector unit tests with gtest's typed test magic and bring SmallBitVector up to date.

llvm-svn: 158600

platforms.

Also, remove one assertion on MSVC because it produces a completely
preposterous result, claiming something needs 12-byte alignment.

llvm-svn: 158599

making the bounds all '1', and chunking it a bit.

llvm-svn: 158598

array of a suitable size and alignment for any of a number of different
types to be stored into the character array.

The mechanisms for producing an explicitly aligned type are fairly
complex because this operation is poorly supported on all compilers.
We've spent a fairly significant amount of time experimenting with
different implementations inside of Google, and the one using explicitly
expanded templates has been the most robust.

Credit goes to Nick Lewycky for writing the first 20 versions or so of
this logic we had inside of Google. I based this on the only one to
actually survive. In case anyone is worried, yes we are both explicitly
re-contributing and re-licensing it for LLVM. =]

Once the issues with actually specifying the alignment are finished, it
turns out that most compilers don't in turn align anything the way they
are instructed. Testing of this logic against both Clang and GCC
indicate that the alignment constraints are largely ignored by both
compilers! I've come up with and used a work-around by wrapping each
alignment-hinted type directly in a struct, and using that struct to
align the character array through a union. This elaborate hackery is
terrifying, but I've included testing that caught a terrifying number of
bugs in every other technique I've tried.

All of this in order to implement a poor C++98 programmers emulation of
C++11 unrestricted unions in classes such as SmallDenseMap.

llvm-svn: 158597

of typename. GCC and Clang were fine with this, but MSVC won't accept
it. Fortunately, it also doesn't need it. Yuck.

Thanks to Nakamura for pointing this out in IRC.

llvm-svn: 158593

These were already trying to be type parameterized over different
key/value pairs. I've realized this goal using GoogleTest's typed test
functionality. This allows us to easily replicate the tests across
different key/value combinations and soon different mapping templates.

I've fixed a few bugs in the tests and extended them a bit in the
process as many tests were only applying to the int->int mapping.

llvm-svn: 158589

LLVM is now -Wunused-private-field clean except for
- lib/MC/MCDisassembler/Disassembler.h. Not sure why it keeps all those unaccessible fields.
- gtest.

llvm-svn: 158096

llvm-svn: 158046

IntegersSubsetMapping: added exclude operation, that allows to exclude subset of integers from current mapping.

llvm-svn: 157989

Changed type of Items collection: from std::vector to std::list.
Also some small fixes made in IntegersSubset.h, IntegersSubsetMapping.h and IntegersSubsetTest.cpp.

llvm-svn: 157987

- Fixed IntegersSubsetGeneric copy/assignment behaviour. 
- Fixed IntegersSubsetGeneric::getSize/getSingleValue methods.
- Fixed IntegersSubsetGeneric::verify method.

Also IntegersSubset.h and IntegersSubsetMapping.h headers was fixed.

llvm-svn: 157887

llvm-svn: 157885

This back-end was deprecated in favor of the NVPTX back-end.

NV_CONTRIB

llvm-svn: 157417

based on a patch by Preston Briggs, with some modifications

llvm-svn: 157231

this fixes the missed optimization I was seeing in the CorrelatedValuePropagation pass

llvm-svn: 157032

on MIPS where they are not implemented.

llvm-svn: 156935

llvm-svn: 156812

llvm-svn: 156810

Returning a temporary BitVector is very expensive. If you must, create
the temporary explicitly: Use BitVector(A).flip() instead of ~A.

llvm-svn: 156768

The existing operation (A & B).any() is very slow.

llvm-svn: 156760

llvm-svn: 156652

llvm-svn: 156507

llvm-svn: 155791

Fixed SmallMap test. The order of items is undefined in DenseMap. So being checking the increment for big mode, we can only check that all items are in map.

llvm-svn: 155651

Comparing ~0UL with an unsigned will always return false when long is 64 bits long.

llvm-svn: 155568

This reverts commit 76271a3366731d4c372fdebcd8d3437e6e09a61b.

as it's breaking the bots.

llvm-svn: 155562

- FlatArrayMap. Very simple map container that uses flat array inside.
- MultiImplMap. Map container interface, that has two modes, one for small amount of elements and one for big amount.
- SmallMap. SmallMap is DenseMap compatible MultiImplMap. It uses FlatArrayMap for small mode, and DenseMap for big mode. 

Also added unittests for new classes and update for ProgrammersManual.
For more details about new classes see ProgrammersManual and comments in sourcecode.

llvm-svn: 155557

This nicely handles the most common case of virtual register sets, but
also handles anticipated cases where we will map pointers to IDs.

The goal is not to develop a completely generic SparseSet
template. Instead we want to handle the expected uses within llvm
without any template antics in the client code. I'm adding a bit of
template nastiness here, and some assumption about expected usage in
order to make the client code very clean.

The expected common uses cases I'm designing for:
- integer keys that need to be reindexed, and may map to additional
  data
- densely numbered objects where we want pointer keys because no
  number->object map exists.

llvm-svn: 155227

llvm-svn: 154930

llvm-svn: 154850