Reapply "blockfreq: Approximate irreducible control flow"

This reverts commit r207287, reapplying r207286.

I'm hoping that declaring an explicit struct and instantiating
`addBlockEdges()` directly works around the GCC crash from r207286.
This is a lot more boilerplate, though.

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

[X86] Add more details in the comments of X86TargetLowering::getScalingFactorCost.

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

[PM] Add pass run listeners to the pass manager.

This commit provides the necessary C/C++ APIs and infastructure to enable fine-
grain progress report and safe suspension points after each pass in the pass
manager.

Clients can provide a callback function to the pass manager to call after each
pass. This can be used in a variety of ways (progress report, dumping of IR
between passes, safe suspension of threads, etc).

The run listener list is maintained in the LLVMContext, which allows a multi-
threaded client to be only informed for it's own thread. This of course assumes
that the client created a LLVMContext for each thread.

This fixes <rdar://problem/16728690>

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

Fix comment

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

Modify the assertion in DIBuilder.cpp to cover the DWARF 5 languages

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

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

InstCombine: don't drop 'inalloca' in PromoteCastOfAllocation (PR19569)

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

Simplify ELFObjectWriter::ExecutePostLayoutBinding.

No functionality change. This removes the last use of AliasedSymbol in
ELFObjectWriter.cpp.

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

[ARM64] Fix an issue where we were always assuming a copy was coming from a D subregister.

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

Simplify isLocal().

No functionality change.

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

ARM: stop passing unused values up the TableGen hierarchy.

It's bad enough that I have to look up 5 different levels of TableGen class
definitions to work out what bits go where in a simple NEON instruction anyway,
without having to keep track of umpteen unused parameters.

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

Don't include an invalid symbol in the symbol table.

The symbol table itself has no relocations, so it is not possible to represent
things like

a = undefined + 1

With the patch we just omit these variables. That matches the behaviour of the
gnu assembler.

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

List the entire symbol table in this test.

This will allow us to extend this test to show that other symbols don't
show up in the symbol table.

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

Produce an error instead of a crash in an expr we cannot represent.

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

Fix gcc -Wsign-compare warning in X86DisassemblerTables.cpp.

X86_MAX_OPERANDS is changed to unsigned.

Also, add range-based for loops for affected loops. This in turn
needed an ArrayRef instead of a pointer-to-array in
InternalInstruction.

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

ARM64: diagnose use of v16-v31 in certain indexed NEON instructions.

Someone couldn't bear to have a completely orthogonal set of floating-point
registers, so we've got some instructions that only accept v0-v15 (coming in
ARMv9, V128_prime: you're allowed v2, v3, v5, v7, ...).

Anyway, we were permitting even the out of range registers during assembly
(CodeGen handled it correctly). This adds a diagnostic.

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

[LCG] Add the most basic of edge insertion to the lazy call graph. This
just handles the pre-DFS case. Also add some test cases for this case to
make sure it works.

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

[LCG] Make the return of the IntraSCC removal method actually match its
contract (and be much more useful). It now provides exactly the
post-order traversal a caller might need to perform on newly formed
SCCs.

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

Fix rampant quadratic behavior in UpdatePHINodes. The operation of
mapping from a basic block to an incoming value, either for removal or
just lookup, is linear in the number of predecessors, and we were doing
this for every entry in the 'Preds' list which is in many cases almost
all of them!

Unfortunately, the fixes are quite ugly. PHI nodes just don't make this
operation easy. The efficient way to fix this is to have a clever
'remove_if' operation on PHI nodes that lets us do a single pass over
all the incoming values of the original PHI node, extracting the ones we
care about. Then we could quickly construct the new phi node from this
list. This would remove the remaining underlying quadratic movement of
unrelated incoming values and the need for silly backwards looping to
"minimize" how often we hit the quadratic case.

This is the last obvious fix for PR19499. It shaves another 20% off the
compile time for me, and while UpdatePHINodes remains in the profile,
most of the time is now stemming from the well known inefficiencies of
LVI and jump threading.

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

Fix very poor compile-time in PR19499 due to excessive tree walks in
domtree. When finding a nearest common dominator, if neither A dominates
B nor B dominates A, we immediately resorted to a tree walk. The tree
walk here is *particularly* expensive because we have to build
a (potentially very large) set for one side's dominators and compare it
with the other side's.

If at any point we have DFS info, we don't need to do any of this. We
can just walk up one side's immediate dominators and return the first
one which dominates the other side. Because of the DFS info, the
dominates queries are trivially constant time.

This reduces the optimizers time in the test case on PR19499 by 70%. It
now optimizes in about 30 seconds for me. And there is still more to be
done for this case.

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

If building with LLVM_ENABLE_DOXYGEN and using CMake then
abort while configuring if doxygen could not be found. This
is desirable because if the build is going to fail then it should
fail as early as possible.

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

[inliner] Significantly improve the compile time in cases like PR19499
by avoiding inlining massive switches merely because they have no
instructions in them. These switches still show up where we fail to form
lookup tables, and in those cases they are actually going to cause
a very significant code size hit anyways, so inlining them is not the
right call. The right way to fix any performance regressions stemming
from this is to enhance the switch-to-lookup-table logic to fire in more
places.

This makes PR19499 about 5x less bad. It uncovers a second compile time
problem in that test case that is unrelated (surprisingly!).

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

[ARM64]Fix a bug cannot select UQSHL/SQSHL with constant i64 shift amount.

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

Convert more SelectionDAG functions to use ArrayRef.

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

[C++] Use 'nullptr'.

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

MC: range-loopify

Use C++11 range-based loops rather than explicit constructors.  NFC.

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

Use raw_ostream and Format.h on Windows so that we don't have to roll
our own portability system to cope without snprintf.

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

Update the Windows TimeValue formatting to match the new formatting on
Unix-like OSes.

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

Update tests to use the new format of printing a TimeValue. It's a bit
odd to have the output of 'llvm-ar tv' depend on the format of
TimeValue::str(), but that's what we have today. If anyone needs the
output to remain compatible with GNU ar or old versions of llvm-ar, just
shout and I'll switch the code to manually format its times.

Note that there isn't a portable format -- Mac and GNU have different
formats at least (thanks Rafael!) so...

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

Teach the pass manager's execution dump to print the current time before
each line. This is particularly nice for tracking which run of
a particular pass over a particular function was slow.

This also required making the TimeValue string much more useful. First,
there is a standard format for writing out a date and time. Let's use
that rather than strings that would have to be parsed. Second, actually
output the nanosecond resolution that timevalue claims to have.

This is proving useful working on PR19499, so I figured it would be
generally useful to commit.

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

CodeGen/AsmPrinter.h: Fix \param in r207369. [-Wdocumentation]

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

Convert AddNodeIDNode and SelectionDAG::getNodeIfExiists to use ArrayRef<SDValue>

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

Add emitThumbSet to the arm target streamer.

This fixes the asm printer implementation and lets the parser be unaware of
what .thumb_set is.

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

Fix an assert I accidentally broke to hopefully fix the build bots.

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

Convert SelectionDAGISel::MorphNode to use ArrayRef.

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

Convert SelectionDAG::MorphNodeTo to use ArrayRef.

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

Convert SelectionDAG::SelectNodeTo to use ArrayRef.

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

Convert one last signature of getNode to take an ArrayRef of SDUse.

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

Convert SDNode constructor to use ArrayRef.

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

Convert SelectionDAG::getMergeValues to use ArrayRef.

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

Const-correct SelectionDAG::getAtomic.

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

Clarify the doxygen comment for AsmPrinter::EmitDwarfRegOpPiece and add
default arguments to the function.

No functional change.

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

X86TTI: Adjust sdiv cost now that we can lower it on plain SSE2.

Includes a fix for a horrible typo that caused all SDIV costs to be
slightly off :)

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

X86: If SSE4.1 is missing lower SMUL_LOHI of v4i32 to pmuludq and fix up the high parts.

This is more expensive than pmuldq but still cheaper than scalarizing the whole thing.

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

Debug info: Refactor EmitDwarfRegOpPiece to be a member function of
AsmPrinter.
No functional change.

http://reviews.llvm.org/D3373
rdar://problem/15928306

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

Debug Info: Prepare DebugLocEntry to handle more than a single value per
entry. This is in preparation for generic DW_OP_piece support.
No functional change so far.

http://reviews.llvm.org/D3373
rdar://problem/15928306

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

Make getOrCreateSymbolData non virtual.

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

Avoid using MCSymbolData on the asm streamer.

Only the object streamers need to track if a symbol should be marked thumb or
not. This ports the ELF case. The COFF case is not ported since it is currently
not working for some other reason (I will report a bug).

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

MC: duplicate .file test for WoA (SVN r207341)

Since the COFF tests are dependent on X86, duplicate the test for ARM.  Use the
default check prefix.

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

Make helper functions static.

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

Remove redundant explicit default initialization of non-trivially constructed member.

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

Add the default constructor DwarfAccelTable::DataArray() to initialize (MCSymbol*)StrSym explicitly.

It will fix crash in codegen on msvc x64.

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

Revert r206989, "Mark llvm/test/BugPoint/compile-custom.ll as XFAIL:vg_leak." It has been fixed since r207265.

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

Update test not to check for a shuffle of an all-zero vector.

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

SelectionDAG: Aggressively fold shuffles of constant splats.

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

ARM: MSVC does not support = default

Explicitly "implement" the destructor as MSVC does not support defaulted methods
yet.

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

MC: restore behaviour of defaulting to ELF

This restores the previous behaviour of just assuming that if you dont specify a
valid triple that you really meant the default triple with an ELF object file.

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

tests: Windows ARM now supports object emission

Update lit.cfg with the fact that LLVM can now generate WoA PE/COFF objects.

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

COFF: move ARM COFF test to ARM directory

The COFF tests all assume X86.  Just move the new COFF tests under ARM to
appease the build bots.

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

Add WoA object file emission support

Introduce support for WoA PE/COFF object file emission from LLVM.  Add the new
target specific PE/COFF Streamer (ARMWinCOFFStreamer) that handles the ARM
specific behaviour of PE/COFF object emission.  ARM exception information is not
yet emitted and is a TODO item.

The ARM specific object writer (ARMWinCOFFObjectWriter) handles the ARM specific
relocation handling in conjunction with the WinCOFFObjectWriter in the MC layer.
The MC layer needs to be updated to deal with the relocation adjustments.
Branch relocations are adjusted by 4 bytes (unlikely their ELF counterparts).

Minor tweaks to switch multiple conditional checks into equivalent switch
statements.  The ObjectFileInfo is updated to relax the object file setup for
Windows COFF.  Move the architecture checks into an assertion.  Windows COFF is
currently only supported on x86, x86_64, and ARM (thumb).  Rather than
defaulting to ELF, we will refuse to generate an object file.  This is better
though as you do not get an (arbitrary) object file which is different from the
request.

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

MC: create X86WinCOFFStreamer for target specific behaviour

This introduces a target specific streamer, X86WinCOFFStreamer, which handles
the target specific behaviour (e.g. WinEH).  This is mostly to ensure that
differences between ARM and X86 remain disjoint and do not accidentally cross
boundaries.  This is the final staging change for enabling object emission for
Windows on ARM.

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

MC: rename WinCOFFStreamer and move declaration out-of-line

This is in preparation for promoting WinCOFFStreamer to a base class which will
be shared by the X86 and ARM specific target COFF streamers.  Also add a new
getOrCreateSymbolData interface (like MCELFStreamer) for the ARM COFF Streamer.
This makes the COFFStreamer more similar to the ELFStreamer.

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

MC: style tweaks to WinCOFFStreamer

Stylistic changes to prepare for splitting up the COFFStreamer into target
specific streamers.  Tweak some assertion messages.  No functional change.

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

ARM: Support SingleParameterDotFile on WoA

Currently, the integrated assembler is the only choice for assembling Windows on
ARM binaries.  IAS supports the .file <filename> directive which emits the file
symbol into the resulting object binary.  Mark the GNU COFF information to
indicate support for this feature.

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

[LCG] Re-organize the methods for mutating a call graph to make their
API requirements much more obvious.

The key here is that there are two totally different use cases for
mutating the graph. Prior to doing any SCC formation, it is very easy to
mutate the graph. There may be users that want to do small tweaks here,
and then use the already-built graph for their SCC-based operations.
This method remains on the graph itself and is documented carefully as
being cheap but unavailable once SCCs are formed.

Once SCCs are formed, and there is some in-flight DFS building them, we
have to be much more careful in how we mutate the graph. These mutation
operations are sunk onto the SCCs themselves, which both simplifies
things (the code was already there!) and helps make it obvious that
these interfaces are only applicable within that context. The other
primary constraint is that the edge being mutated is actually related to
the SCC on which we call the method. This helps make it obvious that you
cannot arbitrarily mutate some other SCC.

I've tried to write much more complete documentation for the interesting
mutation API -- intra-SCC edge removal. Currently one aspect of this
documentation is a lie (the result list of SCCs) but we also don't even
have tests for that API. =[ I'm going to add tests and fix it to match
the documentation next.

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

DAGCombiner: Simplify code a bit, make more transforms work with vectors.

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

[LCG] Add some pedantry to the use of ptrdiff_t to appease build bots.

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

[LCG] Eliminate more boiler plate by using the iterator facade base
class.

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

[LCG] Switch the node iterator to use the new fancy adaptor base. This
is *much* cleaner, makes the iterator a full random access iterator,
etc.

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

DwarfDebug: Roll argument into call.

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

DebugInfo: Fix and test a regression caused by r207263 causing the DW_AT_object_pointer to go missing on blocks

Noticed by inspection. Test coverage added.

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

Mark the growing path in SmallVector::push_back as cold.

It's vital for performance that the cold path of push_back isn't inlined.

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

Replace std::vector with SmallVector for some small, known size vectors.

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

Convert getMemIntrinsicNode to take ArrayRef of SDValue instead of pointer and size.

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

Trivial test commit.

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

Convert SelectionDAG::getNode methods to use ArrayRef<SDValue>.

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

Remove an unused version of getMemIntrinsicNode and getNode. Additionally, these were calling makeVTList with the pointers passed in which would were unlikely to belong to SelectionDAG and likely would have just been stack pointers.

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

Include C++ source for debug info test case committed in r207323

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

DWARF Type Units: Avoid emitting type units under fission if the type requires an address.

Since there's no way to ensure the type unit in the .dwo and the type
unit skeleton in the .o are correlated, this cannot work.

This implementation is a bit inefficient for a few reasons, called out
in comments.

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

Print X86ISD::PMULDQ nodes properly in debug output.

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

DwarfDebug: Minor refactoring around type unit construction

Sinking addition of the declaration attribute down to where the
signature is added. So that if the signature is not added neither is the
declaration attribute (this will come in handy when aborting type unit
construction to instead emit the type into the CU directly in some
cases)

Pull out type unit identifier hashing just to simplify the function a
little, it'll be getting longer.

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

X86TTI: i16/i32 vector div with a constant (splat) divisor are reasonably cheap now.

Turn vectorization back on.

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

X86: Lower SMUL_LOHI of v4i32 to pmuldq when SSE4.1 is available.

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

X86: Add patterns for MULHU/MULHS of v8i16 and v16i16.

This gets us pretty code for divs of i16 vectors. Turn the existing
intrinsics into the corresponding nodes.

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

Rip out X86-specific vector SDIV lowering, make the corresponding DAGCombiner transform work on vectors.

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

DAGCombiner: Turn divs of vector splats into vectorized multiplications.

Otherwise the legalizer would just scalarize everything. Support for
mulhi in the targets isn't that great yet so on most targets we get
exactly the same scalarized output. Add a test for x86 vector udiv.

I had to disable the mulhi nodes on ARM because there aren't any patterns
for it. As far as I know ARM has instructions for getting the high part of
a multiply so this should be fixed.

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

X86: Custom lower v4i32 UMUL_LOHI into 2 pmuludqs.

Test will follow soon.

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

Revert r206749 till a final decision about the intrinsics is made.

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

[LCG] Rather than removing nodes from the SCC entry set when we process
them, just skip over any DFS-numbered nodes when finding the next root
of a DFS. This allows the entry set to just be a vector as we populate
it from a uniqued source. It also removes the possibility for a linear
scan of the entry set to actually do the removal which can make things
go quadratic if we get unlucky.

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

[LCG] Rotate the full SCC finding algorithm to avoid round-trips through
the DFS stack for leaves in the call graph. As mentioned in my previous
commit, this is particularly interesting for graphs which have high fan
out but low connectivity resulting in many leaves. For such graphs, this
can remove a large % of the DFS stack traffic even though it doesn't
make the stack much smaller.

It's a bit easier to formulate this for the full algorithm because that
one stops completely for each SCC. For example, I was able to directly
eliminate the "Recurse" boolean used to continue an outer loop from the
inner loop.

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

[LCG] Hoist the main DFS loop out of the edge removal function. This
makes working through the worklist much cleaner, and makes it possible
to avoid the 'bool-to-continue-the-outer-loop' hack. Not a huge
difference, but I think this is approaching as polished as I can make
it.

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

RecursivelyDeleteTriviallyDeadInstructions() could remove
more than 1 instruction. The caller need to be aware of this
and adjust instruction iterators accordingly.

rdar://16679376

Repaired r207302.

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

Restore CloneFunction.cpp which got accidently
overwritten by previous backout of r207303

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

[LCG] In the incremental SCC re-formation, lift the node currently being
processed in the DFS out of the stack completely. Keep it exclusively in
a variable. Re-shuffle some code structure to make this easier. This can
have a very dramatic effect in some cases because call graphs tend to
look like a high fan-out spanning tree. As a consequence, there are
a large number of leaf nodes in the graph, and this technique causes
leaf nodes to never even go into the stack. While this only reduces the
max depth by 1, it may cause the total number of round trips through the
stack to drop by a lot.

Now, most of this isn't really relevant for the incremental version. =]
But I wanted to prototype it first here as this variant is in ways more
complex. As long as I can get the code factored well here, I'll next
make the primary walk look the same. There are several refactorings this
exposes I think.

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

[LCG] Special case the removal of self edges. These don't impact the SCC
graph in any way because we don't track edges in the SCC graph, just
nodes. This also lets us add a nice assert about the invariant that
we're working on at least a certain number of nodes within the SCC.

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

[DAG] During DAG legalization keep opaque constants even after expanding.

The included test case would return the incorrect results, because the expansion
of an shift with a constant shift amount of 0 would generate undefined behavior.

This is because ExpandShiftByConstant assumes that all shifts by constants with
a value of 0 have already been optimized away. This doesn't happen for opaque
constants and usually this isn't a problem, because opaque constants won't take
this code path - they are not supposed to. In the case that the opaque constant
has to be expanded by the legalizer, the legalizer would drop the opaque flag.
In this case we hit the limitations of ExpandShiftByConstant and create incorrect
code.

This commit fixes the legalizer by not dropping the opaque flag when expanding
opaque constants and adding an assertion to ExpandShiftByConstant to catch this
not supported case in the future.

This fixes <rdar://problem/16718472>

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

Revert commit r207302 since build failures
have been reported.

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

RecursivelyDeleteTriviallyDeadInstructions() could remove
more than 1 instruction. The caller need to be aware of this
and adjust instruction iterators accordingly.

rdar://16679376

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

[X86] Implement TargetLowering::getScalingFactorCost hook.
Scaling factors are not free on X86 because every "complex" addressing mode
breaks the related instruction into 2 allocations instead of 1.

<rdar://problem/16730541>

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

[LCG] Refactor the duplicated code I added in my last commit here into
a helper function. Also factor the other two places where we did the
same thing into the helper function. =] Much cleaner this way. NFC.

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

[InstCombine][X86] Teach how to fold calls to SSE2/AVX2 packed logical shift
right intrinsics.

A packed logical shift right with a shift count bigger than or equal to the
element size always produces a zero vector. In all other cases, it can be
safely replaced by a 'lshr' instruction.

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