llvm-svn: 151921

This could probably be made a lot smarter, but this is a common case and doesn't require LVI to scan a lot
of code. With this change CVP can optimize away the "shift == 0" case in Hashing.h that only gets hit when
"shift" is in a range not containing 0.

llvm-svn: 151919

Hashing: microoptimize a truncate on 64 bit away. This currently blocks dead code eliminating the conditional.

The optimizer should handle this eventually, but currently LVI isn't really designed for this kind of stuff.

llvm-svn: 151918

llvm-svn: 151909

llvm-svn: 151908

folks who know something about PPC tell me that the byte swap is crazy
fast and without this the bit mixture would actually be different. It
might not be worse, but I've not measured it and so I'd rather not trust
it. This way, the algorithm is identical on both endianness hosts. I'll
look into any performance issues etc stemming from this.

llvm-svn: 151892

just ensure that the number of bytes in the pair is the sum of the bytes
in each side of the pair. As long as thats true, there are no extra
bytes that might be padding.

Also add a few tests that previously would have slipped through the
checking. The more accurate checking mechanism catches these and ensures
they are handled conservatively correctly.

Thanks to Duncan for prodding me to do this right and more simply.

llvm-svn: 151891

This change replaces getTypeStoreSize with getTypeAllocSize in AddressSanitizer
instrumentation for stack allocations.

One case where old behaviour produced undesired results is an optimization in
InstCombine pass (PromoteCastOfAllocation), which can replace  alloca(T) with
alloca(S), where S has the same AllocSize, but a smaller StoreSize. Another
case is memcpy(long double => long double), where ASan will poison bytes 10-15
of a stack-allocated long double (StoreSize  10, AllocSize 16,
sizeof(long double) = 16).

See http://llvm.org/bugs/show_bug.cgi?id=12047 for more context.

llvm-svn: 151887

llvm-svn: 151886

for 32-bit builds in here.

llvm-svn: 151885

offsetof buildbot errors to go away...

llvm-svn: 151884

hashable data. This matters when we have pair<T*, U*> as a key, which is
quite common in DenseMap, etc. To that end, we need to detect when this
is safe. The requirements on a generic std::pair<T, U> are:

1) Both T and U must satisfy the existing is_hashable_data trait. Note
   that this includes the requirement that T and U have no internal
   padding bits or other bits not contributing directly to equality.
2) The alignment constraints of std::pair<T, U> do not require padding
   between consecutive objects.
3) The alignment constraints of U and the size of T do not conspire to
   require padding between the first and second elements.

Grow two somewhat magical traits to detect this by forming a pod
structure and inspecting offset artifacts on it. Hopefully this won't
cause any compilers to panic.

Added and adjusted tests now that pairs, even nested pairs, are treated
as just sequences of data.

Thanks to Jeffrey Yasskin for helping me sort through this and reviewing
the somewhat subtle traits.

llvm-svn: 151883

an open question of whether we can do better than this by treating pairs
as boring data containers and directly hashing the two subobjects. This
at least makes the API reasonable.

In order to make this change, I reorganized the header a bit. I lifted
the declarations of the hash_value functions up to the top of the header
with their doxygen comments as these are intended for users to interact
with. They shouldn't have to wade through implementation details. I then
defined them at the very end so that they could be defined in terms of
hash_combine or any other hashing infrastructure.

Added various pair-hashing unittests.

llvm-svn: 151882

In this instance we are generating the tail-call during legalizeDAG.  The 2nd
floor call can't be a tail call because it clobbers %xmm1, which is defined by
the first floor call.  The first floor call can't be a tail-call because it's
not in the tail position.  The only reasonable way I could think to fix this
in a target-independent manner was to check for glue logic on the copy reg.

rdar://10930395

llvm-svn: 151877

llvm-svn: 151875

llvm-svn: 151874

to the string table for the function name, not the function name.

llvm-svn: 151873

can insert a new element, invalidating iterators. Use find
instead, and handle the case where the key is not found explicitly.

llvm-svn: 151871

llvm-svn: 151869

the hash_code. I'm not sure what I was thinking here, the use cases for
special values are in the *keys*, not in the hashes of those keys.

We can always resurrect this if needed, or clients can accomplish the
same goal themselves. This makes the general case somewhat faster (~5
cycles faster on my machine) and smaller with less branching.

llvm-svn: 151865

The inline table needs to be constructed ahead of time so that it doesn't try to
create new strings while we're emitting everything.

This reverts commit a8ff9bccb399183cdd5f1c3cec2bda763664b4b0.

llvm-svn: 151864

floating point equality comparisons into integer ones with -ffast-math. The
issue is the optimization causes +0.0 != -0.0.

Now the optimization is only done when one side is known to be 0.0. The other
side's sign bit is masked off for the comparison.

rdar://10964603

llvm-svn: 151861

to keep this around -- updating golden tests is annoying otherwise.

Thanks to Benjamin for pointing this omission out on IRC.

llvm-svn: 151860

to do more invasive refactoring here to get FoldingSet to use size_t or
even hash_code directly, but for now this is a good first step to remove
Yet Another Hashing Algorithm from LLVM.

llvm-svn: 151859

do this initially, sorry.

llvm-svn: 151857

This function could have r12 live across a function call when compiling
thumb1 code.

The test case for this is not included because it is very long. It must
provoke emergency spilling near a function call. The behavior is
provoked by MultiSource/Applications/JM/lencod, and it triggers an
assertion in the scavenger.

<rdar://problem/10963642>

llvm-svn: 151855

fixups that are being used to determine section offsets. Reduces
the total number of fixups by 50% for a non-trivial testcase.

Part of rdar://10413936

llvm-svn: 151852

rdar://10965031

llvm-svn: 151850

llvm-svn: 151849

llvm-svn: 151847

Add ObjectFile::getLoadName() for retrieving the soname/installname of a shared object.

llvm-svn: 151845

runs into the undefined 15 condition code value.

llvm-svn: 151844

and stores was added.

- SelectAddr should return false if Parent is an unaligned f32 load or store.
- Only aligned load and store nodes should be matched to select reg+imm
  floating point instructions.
- MIPS does not have support for f64 unaligned load or store instructions.

llvm-svn: 151843

BumpPtrAllocator: Make sure threshold cannot be initialized with a value smaller than the slab size.

This replaces r151834 with a simpler fix.

llvm-svn: 151842

llvm-svn: 151839

increase the slab size.

llvm-svn: 151834

so that the test will not fail when run on an Intel Atom
processor, due to the Atom scheduler producing an instruction sequence that is
different from that which is normally expected.

llvm-svn: 151832

llvm-svn: 151828

r151822, sorry sorry. =[

We need 'git svn nothave' or some such...

llvm-svn: 151824

of the proposed standard hashing interfaces (N3333), and to use
a modified and tuned version of the CityHash algorithm.

Some of the highlights of this change:
 -- Significantly higher quality hashing algorithm with very well
    distributed results, and extremely few collisions. Should be close to
    a checksum for up to 64-bit keys. Very little clustering or clumping of
    hash codes, to better distribute load on probed hash tables.
 -- Built-in support for reserved values.
 -- Simplified API that composes cleanly with other C++ idioms and APIs.
 -- Better scaling performance as keys grow. This is the fastest
    algorithm I've found and measured for moderately sized keys (such as
    show up in some of the uniquing and folding use cases)
 -- Support for enabling per-execution seeds to prevent table ordering
    or other artifacts of hashing algorithms to impact the output of
    LLVM. The seeding would make each run different and highlight these
    problems during bootstrap.

This implementation was tested extensively using the SMHasher test
suite, and pased with flying colors, doing better than the original
CityHash algorithm even.

I've included a unittest, although it is somewhat minimal at the moment.
I've also added (or refactored into the proper location) type traits
necessary to implement this, and converted users of GeneralHash over.

My only immediate concerns with this implementation is the performance
of hashing small keys. I've already started working to improve this, and
will continue to do so. Currently, the only algorithms faster produce
lower quality results, but it is likely there is a better compromise
than the current one.

Many thanks to Jeffrey Yasskin who did most of the work on the N3333
paper, pair-programmed some of this code, and reviewed much of it. Many
thanks also go to Geoff Pike Pike and Jyrki Alakuijala, the original
authors of CityHash on which this is heavily based, and Austin Appleby
who created MurmurHash and the SMHasher test suite.

Also thanks to Nadav, Tobias, Howard, Jay, Nick, Ahmed, and Duncan for
all of the review comments! If there are further comments or concerns,
please let me know and I'll jump on 'em.

llvm-svn: 151822