[PBQP] Replace the interference-constraints algorithm with a faster version
loosely based on linear scan.

On x86-64 this is good for a ~2% drop in compile time on the nightly test suite.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@220143 91177308-0d34-0410-b5e6-96231b3b80d8
[PBQP] Move register-allocation specific PBQP code into RegAllocPBQP.h.

Just clean-up - no functional change.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@220145 91177308-0d34-0410-b5e6-96231b3b80d8
Clean up the formatting and trailing whitespace of a routine before
editting it.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@220146 91177308-0d34-0410-b5e6-96231b3b80d8
Clean up doxygen syntax and reword comments to flow better, have a brief
section, and not have unfinished sentence fragments.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@220147 91177308-0d34-0410-b5e6-96231b3b80d8
More formatting cleanup brought to you by clang-format.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@220149 91177308-0d34-0410-b5e6-96231b3b80d8
Fix the other comment to use modern doxygen style and be a bit more
direct. Notably, comment on the fact that the loaded type is significant
in that it determines how wide of an access must be safe.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@220150 91177308-0d34-0410-b5e6-96231b3b80d8
Rename 'TD' to 'DL' in this function as the argument is now a DataLayout
argument.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@220151 91177308-0d34-0410-b5e6-96231b3b80d8
Use triple predicate functions instead of checking values directly. NFC.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@220155 91177308-0d34-0410-b5e6-96231b3b80d8
Switch how the datalayout availability test is handled in this code to
make much more sense and in theory be more correct.

If you trace the code alllll the way back to when it was first
introduced, the comments make it slightly more clear what was going on
here. At that time, the only way Base != V was if DL (then TD) was
non-null. As a consequence, if DL *was* null, that meant we were loading
directly from the alloca or global found above the test. After
refactoring, this has become at least terribly subtle and potentially
incorrect. There are many forms of pointer manipulation that can be
traversed without DataLayout, and some of them would in fact change the
size of object being loaded vs. allocated.

Rather than this subtlety, I've hoisted the actual 'return true' bits
into the code which actually found an alloca or global and based them on
the loaded pointer being that alloca or global. This is both more clear
and safer. I've also added comments about exactly why this set of
predicates is used.

I've also corrected a misleading comment about globals -- if overridden
they may not just have a different size, they may be null and completely
unsafe to load from!

Hopefully this confuses the next reader a bit less. I don't have any
test cases or anything, the patch is motivated strictly to improve the
readability of the code.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@220156 91177308-0d34-0410-b5e6-96231b3b80d8
Fix a long-standing miscompile in the load analysis that was uncovered
by my refactoring of this code.

The method isSafeToLoadUnconditionally assumes that the load will
proceed with the preferred type alignment. Given that, it has to ensure
that the alloca or global is at least that aligned. It has always done
this historically when a datalayout is present, but has never checked it
when the datalayout is absent. When I refactored the code in r220156,
I exposed this path when datalayout was present and that turned the
latent bug into a patent bug.

This fixes the issue by just removing the special case which allows
folding things without datalayout. This isn't worth the complexity of
trying to tease apart when it is or isn't safe without actually knowing
the preferred alignment.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@220161 91177308-0d34-0410-b5e6-96231b3b80d8
InstCombine: Optimize icmp eq/ne (shl Const2, A), Const1

The following implements the optimization for sequences of the form:
icmp eq/ne (shl Const2, A), Const1

Such sequences can be transformed to:
icmp eq/ne A, (TrailingZeros(Const1) - TrailingZeros(Const2))

This handles only the equality operators for now. Other operators need
to be handled.

Patch by Ankur Garg!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@220162 91177308-0d34-0410-b5e6-96231b3b80d8
InstCombine: (sub (or A B) (xor A B)) --> (and A B)

The following implements the transformation:
(sub (or A B) (xor A B)) --> (and A B).

Patch by Ankur Garg!

Differential Revision: http://reviews.llvm.org/D5719

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@220163 91177308-0d34-0410-b5e6-96231b3b80d8
Move previously dead code to handle computing the known bits of an alias
up to where it actually works as intended. The problem is that
a GlobalAlias isa GlobalValue and so the prior block handled all of the
cases.

This allows us to constant fold based on the actual constant expression
in the global alias. As an example, see the last function in the newly
added test case which explicitly aligns an unaligned pointer using
constant expression math. Without this change, we fail to see that and
fold an alignment test to zero.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@220164 91177308-0d34-0410-b5e6-96231b3b80d8
Do a better and more complete job of preserving metadata when combining
loads.

This handles many more cases than just the AA metadata, some of them
suggested by Hal in his review of the AA metadata handling patch. I've
tried to test this behavior where tractable to do so.

I'll point out that I have specifically *not* included a test for
debuginfo because it was going to require 2 or 3 times as much work to
craft some input which would survive the "helpful" stripping of debug
info metadata that doesn't match the desired schema. This is another
good example of why the current state of write-ability for our debug
info metadata is unacceptable. I spent over 30 minutes trying to conjure
some test case that would survive, even copying from other debug info
tests, but it always failed to survive with no explanation of why or how
I might fix it. =[

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@220165 91177308-0d34-0410-b5e6-96231b3b80d8
[ADT] Add a 'find_as' operation to DenseSet.

This operation is analogous to its counterpart in DenseMap: It allows lookup
via cheap-to-construct keys (provided that getHashValue and isEqual are
implemented for the cheap key-type in the DenseMapInfo specialization).

Thanks to Chandler for the review.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@220168 91177308-0d34-0410-b5e6-96231b3b80d8
[PowerPC] Re-enable VSX test line for fma.ll with -mcpu=pwr7

The VSX testing variant in test/CodeGen/PowerPC/fma.ll had to be
disabled because of unexpected behavior on many of the builders.  I
tracked this down to a situation that occurs when the VSX attribute is
enabled for a target that disables the MI early scheduling pass.  This
patch adds -mcpu=pwr7 to make this predictable.  The other issue will
be addressed separately.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@220171 91177308-0d34-0410-b5e6-96231b3b80d8
[PowerPC] Temporarily disable VSX for PowerPC fast-isel tests

Patch by Bill Seurer; some comment formatting changes by me.

There are a few PowerPC test cases for FastISel support that currently
fail with VSX support enabled.  The temporary workaround under
discussion in http://reviews.llvm.org/D5362 helps, but the tests still
fail because they specify -fast-isel-abort, and the VSX workaround
punts back to SelectionDAG.  We have plans to fix FastISel permanently
for VSX, but until that's in place these tests are preventing us from
enabling VSX by default.  Therefore we are adding -mattr=-vsx to these
tests until the full support is ready.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@220172 91177308-0d34-0410-b5e6-96231b3b80d8
[PowerPC] Clean up -mattr=+vsx tests to always specify -mcpu

We recently discovered an issue that reinforces what a good idea it is
to always specify -mcpu in our code generation tests, particularly for
-mattr=+vsx.  This patch ensures that all tests that specify
-mattr=+vsx also specify -mcpu=pwr7 or -mcpu=pwr8, as appropriate.

Some of the uses of -mattr=+vsx added recently don't make much sense
(when specified for -mtriple=powerpc-apple-darwin8 or -march=ppc32,
for example).  For cases like this I've just removed the extra VSX
test commands; there's enough coverage without them.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@220173 91177308-0d34-0410-b5e6-96231b3b80d8
Always use -Wl,-gc-sections on our build.

Both bfd ld and gold correctly handle --export-dynamic, so gc-sections is safe even for binaries
that support plugins.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@220174 91177308-0d34-0410-b5e6-96231b3b80d8
Add a datalayout string to this test so that it exercises the full gamut
of InstCombine rather than just the bits enabled when datalayout is
optional.

The primary fixes here are because now things are little endian.

In good news, silliness like this seems like it will be going away as
we've got pretty stong consensus on dropping optional datalayout
entirely.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@220176 91177308-0d34-0410-b5e6-96231b3b80d8