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

llvm-svn: 151821

llvm-svn: 151818

llvm-svn: 151816

Allows us to de-virtualize the function and provides access to it in
the instruction printer, which is useful for handling composite
physical registers (e.g., ARM register lists).

llvm-svn: 151815

This reverts commit 151760.

We want to move getSubReg() from TargetRegisterInfo into MCRegisterInfo,
but to do that, the type of the lookup table needs to be the same for
all targets.

llvm-svn: 151814

Make darwin bots happier.

llvm-svn: 151813

llvm-svn: 151811

Fix a codegen fault in which log2 or exp2 could be dead-code eliminated even though they could have sideeffects.

Only allow log2/exp2 to be converted to an intrinsic if they are declared "readnone".

llvm-svn: 151807

This allows us to make TRC non-polymorphic and value-initializable, eliminating a huge static
initializer and a ton of cruft from the generated code.

Shrinks ARMBaseRegisterInfo.o by ~100k.

llvm-svn: 151806

llvm-svn: 151795

llvm-svn: 151792

objects for big endian and little endian targets.

Patch by Jack Carter.

llvm-svn: 151788

Simply treat bundles as instructions. Spill code is inserted between
bundles, never inside a bundle.  Rewrite all operands in a bundle at
once.

Don't attempt and memory operand folding inside bundles.

llvm-svn: 151787

* Add begin_dynamic_table() / end_dynamic_table() private interface to ELFObjectFile.
* Add begin_libraries_needed() / end_libraries_needed() interface to ObjectFile, for grabbing the list of needed libraries for a shared object or dynamic executable.
* Implement this new interface completely for ELF, leave stubs for COFF and MachO.
* Add 'llvm-readobj' tool for dumping ObjectFile information.

llvm-svn: 151785

This allows the function to be inlined, and makes it suitable for use in
getInstructionIndex().

Also provide a const version. C++ is great for touch typing practice.

llvm-svn: 151782

Shrinks BasicAliasAnalysis.o from 106k to 56k on i386.

llvm-svn: 151781

While we're at it - don't copy vreg implicit operands while rematerializing.
This fixes PR12138.

llvm-svn: 151779

llvm-svn: 151778

code sections when needed.  It just had a conditional
the wrong way around.

llvm-svn: 151777

- The search bounds are constant, in the worst case (ARM target) it will scan over 30 uint16_ts.
- This method isn't very hot, I had problems finding a testcase where it's called more than a dozen of times (no perf impact).

llvm-svn: 151773

So with darwin's otool(1) an x86_64 hello world .o file will print:
leaq	L_.str(%rip), %rax ## literal pool for: Hello world

llvm-svn: 151769

llvm-svn: 151764

Doesn't help ARM with its massive register set, but halves the size on x86 and all other targets.

llvm-svn: 151760

llvm-svn: 151758

llvm-svn: 151756

llvm-svn: 151755

Instead of nested switch statements, use a lookup table. On ARM, this replaces
a 23k (x86_64 release build) function with a 16k table. Its not unlikely to
be faster, as well.

llvm-svn: 151751

std::vector.
 - Good for 1-2% speedup on writing PCH for Cocoa.h.
 - Clang side API match to follow shortly, there wasn't an easy way to make this
   non-breaking.

llvm-svn: 151750

llvm-svn: 151749

and remove getBuffer().

llvm-svn: 151748

llvm-svn: 151747

Patch by Tyler Nowicki!

llvm-svn: 151743

llvm-svn: 151732

LegalizeIntegerTypes: Reorder operations in the "big shift by small amount" optimization, making the lives of later passes easier.

llvm-svn: 151722

a constant.  This fixes PR1768.

llvm-svn: 151713

pin it down is undefined behaviour.

llvm-svn: 151710

[Object] Add symbol attribute flags: ST_ThreadLocal, ST_Common, and ST_Undefined. Implement these completely for ELF.
Rename ST_External to ST_Unknown, and slightly change its semantics. It now only indicates that the symbol's type
is unknown, not that the symbol is undefined. (For that, use ST_Undefined).

llvm-svn: 151696

llvm-svn: 151694

This transformation is not correct for not-equal conditions:

(trunc x) != C1 & (and x, CA) != C2 -> (and x, CA|CMAX) != C1|C2

Let
  C1 == 0
  C2 == 0
  CA == 0xFF0000
  CMAX == 0xFF
and truncating to i8.

The original truth table:

    x   | A: trunc x != 0 | B: x & 0xFF0000 != 0 | A & B != 0
--------------------------------------------------------------
0x00000 |        0        |          0           |     0
0x00001 |        1        |          0           |     0
0x10000 |        0        |          1           |     0
0x10001 |        1        |          1           |     1

The truth table of the replacement:

    x   | x & 0xFF00FF != 0
----------------------------
0x00000 |        0
0x00001 |        1
0x10000 |        1
0x10001 |        1

So they are different.

llvm-svn: 151691