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

Now that SROA can form alloca's for dynamic vector accesses, further improve it to be able to replace operations on these vector alloca's with insert/extract element insts

llvm-svn: 158623

llvm-svn: 158610

llvm-svn: 158608

This cleans up the method used to find trip counts in order to form CTR loops on PPC.
This refactoring allows the pass to find loops which have a constant trip count but also
happen to end with a comparison to zero. This also adds explicit FIXMEs to mark two different
classes of loops that are currently ignored.

In addition, we now search through all potential induction operations instead of just the first.
Also, we check the predicate code on the conditional branch and abort the transformation if the
code is not EQ or NE, and we then make sure that the branch to be transformed matches the
condition register defined by the comparison (multiple possible comparisons will be considered).

llvm-svn: 158607

The present implementation handles only TBAA and FP metadata, discarding everything else.
For debug metadata, the current behavior is maintained (the debug metadata associated with
one of the instructions will be kept, discarding that attached to the other).

This should address PR 13040.

llvm-svn: 158606

There are other passes, BBVectorize specifically, that also need some of
this functionality.

llvm-svn: 158605

llvm-svn: 158604

llvm-svn: 158603

llvm-svn: 158602

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

It's not deterministic to iterate over SmallPtrSet. Replace it with SmallSetVector. Patch by Daniel Reynaud. rdar://11671029

llvm-svn: 158594

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

Dynamic GEPs created by SROA needed to insert extra "i32 0"
operands to index through structs and arrays to get to the
vector being indexed.

llvm-svn: 158590

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

rather than the base class. Add a pile of boilerplate to indirect around
this.

This is pretty ugly, but it allows the super class to change the
representation of these values, which will be key for doing
a SmallDenseMap.

Suggestions on better method structuring / naming are welcome, but keep
in mind that SmallDenseMap won't have an 'unsigned' member to expose
a reference to... =/

llvm-svn: 158586

and a derived class that provides the allocation and growth strategy.

This is the first (and biggest) step toward building a SmallDenseMap
that actually behaves exactly the same as DenseMap, and supports all the
same types and interface points with the same semantics.

llvm-svn: 158585

the address of it. Found by a checking STL implementation used on
a dragonegg builder. Sorry about this one. =/

llvm-svn: 158582

This is likely only the tip of the ice berg, but this particular bug
caused any double-free on a glibc system to turn into a deadlock! It is
not generally safe to either allocate or release heap memory from within
the signal handler. The 'pop_back()' in RemoveFilesToRemove was deleting
memory and causing the deadlock. What's worse, eraseFromDisk in PathV1
has lots of allocation and deallocation paths. We even passed 'true' in
a place that would have caused the *signal handler* to try to run the
'system' system call and shell out to 'rm -rf'. That was never going to
work...

This patch switches the file removal to use a vector of strings so that
the exact text needed for the 'unlink' system call can be stored there.
It switches the loop to be a boring indexed loop, and directly calls
unlink without looking at the error. It also works quite hard to ensure
that calling 'c_str()' is safe, by ensuring that the non-signal-handling
code path that manipulates the vector always leaves it in a state where
every element has already had 'c_str()' called at least once.

I dunno exactly how overkill this is, but it fixes the
deadlock-on-double free issue, and seems likely to prevent any other
issues from sneaking up.

Sorry for not having a test case, but I *really* don't know how to test
signal handling code easily....

llvm-svn: 158580

We now have a proper machine code verifier pass between register
allocation and rewriting.

llvm-svn: 158577

llvm-svn: 158575

llvm-svn: 158570

Calling checkRegMaskInterference(VirtReg) checks if VirtReg crosses any
regmask operands, regardless of the registers they clobber.

llvm-svn: 158563

llvm-svn: 158561

iaspr, espr and xpsr which also needed to have 0b10 in their mask encoding bits.

llvm-svn: 158560

This patch will optimize abs(x-y)
FROM
sub, movs, rsbmi
TO
subs, rsbmi

For abs, we will use cmp instead of movs. This is necessary because we already
have an existing peephole pass which optimizes away cmp following sub.

rdar: 11633193
llvm-svn: 158551

llvm-svn: 158543

For non-address users, Base and Scaled registers are not specially
associated to fit an address mode, so SCEVExpander should apply normal
expansion rules. Otherwise we may sink computation into inner loops
that have already been optimized.

llvm-svn: 158537

llvm-svn: 158536

llvm-svn: 158535

llvm-svn: 158534

Allow SROA to split up an array of vectors into multiple vectors, even when the vectors are dynamically indexed

llvm-svn: 158529

linkonce linkage. For example, it is not valid to add unnamed_addr.

This also fixes a crash in g++.dg/opt/static5.C.

llvm-svn: 158528