Add SplitEditor::markOverlappedComplement().

This function is used to flag values where the complement interval may
overlap other intervals.  Call it from overlapIntv, and use the flag to
fully recompute those live ranges in transferValues().

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

Teach the Thumb ASM parser that BKPT is allowed in IT blocks, even though it is always executed unconditionally.

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

Eliminate the extendRange() wrapper.

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

It is not necessary to search for mipsallegrex in target triple string.

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

Fix encoding of Thumb2 shifted register operands with RRX shifts.

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

Switch extendInBlock() to take a kill slot instead of the last use slot.

Three out of four clients prefer this interface which is consistent with
extendIntervalEndTo() and LiveRangeCalc::extend().

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

Use a separate LiveRangeCalc for the complement in spill modes.

The complement interval may overlap the other intervals created, so use
a separate LiveRangeCalc instance to compute its live range.

A LiveRangeCalc instance can only be shared among non-overlapping
intervals.

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

Maintain hexadecimal order.

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

In ClangAttrEmitter.cpp emit code that allows attributes to keep their source range.

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

Only disassembler instructions with vvvv != 1111 if the instruction actually uses the vvvv field to encode an operand. Fixes PR10851.

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

Remove filter that was preventing MOVDQU/MOVDQA and their VEX forms from being disassembled. Also added encodings for the other register/register form of these instructions. Fixes PR10848.

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

Fix encoding of VMOVDQU to not simultaneously be 'TB OpSize' and 'XS'. 'XS' is correct and seems to have been taking priority.

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

[indvars] Revert r139579 until 401.bzip -arch i386 miscompilation is fixed. PR10920.

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

Unbreak msvc.

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

Disable IV rewriting by default. See PR10916.

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

Generalize test case to handle multiple indvars modes.

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

Generalize this test's CHECK statements to handle different indvars modes.

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

This test only makes sense with -enable-iv-rewrite.

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

Zap some junk from the ARM instruction descriptions.

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

[indvars] Fix bugs in floating point IV range checks noticed by inspection.

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

Silence false positive uninitialized variable warnings from GCC.

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

Extract live range calculations from SplitKit.

SplitKit will soon need two copies of these data structures, and the
algorithms will also be useful when LiveIntervalAnalysis becomes
independent of LiveVariables.

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

Add comment to clarify the behavior of a helper in DSE.

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

Correct grammar.

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

Fix the assembler strings for a couple of atomic instructions.  Doesn't really matter much in practice, but it's a bit cleaner.

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

Tidy up a bit.

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

Conditionalize indvars test that relies on SCEV expansion of geps,
which is only relevant with canonical IVs

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

Change testcase commandline to be more strict and silence buildbots

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

Fix PR10845. SUBREG_TO_REG shouldn't be used when the input and
destination types are equal!

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

indvars test only relevant for -enable-iv-rewrite.

Otherwise this case is now covered by no-iv-rewrite.ll.

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

Fix a failing ELF Thumb test.  I _think_ this is right, but it's not totally clear to me what this test is doing.  Could someone on an ELF platform check?

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

Introduce a bit of a hack.

Splitting a landing pad takes considerable care because of PHIs and other
nasties. The problem is that the jump table needs to jump to the landing pad
block. However, the landing pad block can be jumped to only by an invoke
instruction. So we clone the landingpad instruction into its own basic block,
have the invoke jump to there. The landingpad instruction's basic block's
successor is now the target for the jump table.

But because of PHI nodes, we need to create another basic block for the jump
table to jump to. This is definitely a hack, because the values for the PHI
nodes may not be defined on the edge from the jump table. But that's okay,
because the jump table is simply a construct to mimic what is happening in the
CFG. So the values are mysteriously there, even though there is no value for the
PHI from the jump table's edge (hence calling this a hack).

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

gold plugin: don't report error on non-bitcode (e.g. ELF) files.

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

Thumb2 POP's don't allow the PC as an operand, and PUSH's don't allow the SP either.

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

Revert the wrong part of r139528, and fix testcases.

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

Fix encoding of PC-relative LDRSHW with an immediate offset.

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

Conditionalize indvars tests that rely on SCEV expansion of geps,
which is relevant with canonical IVs. Anything else being checked by
these tests is already covered by early CSE.

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

Change a bunch of isVolatile() checks to check for atomic load/store as well.

No tests; these changes aren't really interesting in the sense that the logic is the same for volatile and atomic.

I believe this completes all of the changes necessary for the optimizer to handle loads and stores correctly.  I'm going to try and come up with some additional testing, though.

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

There's no need to add additional predicate operands when converting a tB to a tBfar now.  Fixes nightly test failures on armv6 Thumb.  <rdar://problem/10110404>

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

Fix typo.

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

Not sure how CMPPS and CMPPD had already ever worked, I guess it didn't.
However with this fix it does now.

Basically the operand order for the x86 target specific node
is not the same as the instruction, but since the intrinsic need that
specific order at the instruction definition, just change the order
during legalization. Also, there were some wrong invertions of condition
codes, such as GE => LE, GT => LT, fix that too. Fix PR10907.

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

Organize a bit the operand names for CMPPS and CMPPD

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

Realign BLEND patterns to match the general style for patterns in .td file.

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

Fix 80-columns

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

Port more encoding tests to decoding tests, and correct an improper Thumb2 pre-indexed load decoding this uncovered.

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

Removing indvars tests that directly test canonical IVs and nothing else.

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

Rename -disable-iv-rewrite to -enable-iv-rewrite=false in preparation for default change.

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

Add asserts to keep front-ends honest while encoding debug info into LLVM IR using DIBuilder.

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

Fix mistake in test runline.

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

Test case for r139453, WidenIV::GetExtendedOperandRecurrence.

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

Add DW_ATE_UTF, which clang started using in my previous commit!

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

Remove the -compact-regions flag.

It has been enabled by default for a while, it was only there to allow
performance comparisons.

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

Add an interface for SplitKit complement spill modes.

SplitKit always computes a complement live range to cover the places
where the original live range was live, but no explicit region has been
allocated.

Currently, the complement live range is created to be as small as
possible - it never overlaps any of the regions.  This minimizes
register pressure, but if the complement is going to be spilled anyway,
that is not very important.  The spiller will eliminate redundant
spills, and hoist others by making the spill slot live range overlap
some of the regions created by splitting.  Stack slots are cheap.

This patch adds the interface to enable spill modes in SplitKit.  In
spill mode, SplitKit will assume that the complement is going to spill,
so it will allow it to overlap regions in order to avoid back-copies.
By doing some of the spiller's work early, the complement live range
becomes simpler.  In some cases, it can become much simpler because no
extra PHI-defs are required.  This will speed up both splitting and
spilling.

This is only the interface to enable spill modes, no implementation yet.

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

Update comments to reflect some (not so) recent changes.

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

Associate a MemOperand with LDWCP nodes introduced during ISel.

This information is required if we want LDWCP to be hoisted out of loops.

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

Mark LDWCP as having no side effects.

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

Format patterns, remove unused X86blend patterns

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

Fix disassembling of one of the register/register forms of MOVUPS/MOVUPD/MOVAPS/MOVAPD/MOVSS/MOVSD and their VEX equivalents. Fixes PR10877.

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

Fix disassembling of reverse register/register forms of ADD/SUB/XOR/OR/AND/SBB/ADC/CMP/MOV.

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

Fix disassembling of PAUSE instruction. Fixes PR10900. Also fixed NOP disassembling to ignore OpSize and REX.W.

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

s/SequeuentiallyConsistent/SequentiallyConsistent/g

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

Fix verb tense agreement.

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

CR fixes per Bruno's request.

Undo the changes from r139285 which added custom lowering to vselect.
Add tablegen lowering for vselect.

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

Really un-XFAIL the testcase, like I said I would in r139458.

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

r139454 activates an assert in a case where we were doing the right thing anyway.  Make that explicit, and un-XFAIL the testcase.

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

Fix the asserts in lib/Target/X86/X86ELFWriterInfo.cpp and
lib/ExecutionEngine/MCJIT/MCJIT.cpp from:

  assert("error");

to:

  assert(0 && "error");

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

Fixed an assert from:

  assert("not implemented for target shuffle node");

to:

  assert(0 && "not implemented for target shuffle node");

This causes a test failure in CodeGen/X86/palignr.ll which has
been marked as XFAIL for the time being.
Test failure filed at PR10901.

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

[disable-iv-rewrite] Allow WidenIV to handle NSW/NUW operations
better.

Don't immediately give up when an add operation can't be trivially
sign/zero-extended within a loop. If it has NSW/NUW flags, generate a
new expression with sign extended (non-recurrent) operand. As before,
if SCEV says that all sign extends are loop invariant, then we can
widen the operation.

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

Set NSW/NUW flags on SCEVAddExpr when the operation is flagged as
such.

I'm doing this now for completeness because I can't think of/remember
any reason that it was left out. I'm not sure it will help anything,
but if we don't do it we need to explain why in comments.

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

Fix asserts in CodeGen from:

  assert("error");

to:

  assert(0 && "error");

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

Thumb2 parsing and encoding for MOV(immediate).

Some aliases for MOV(register) also to keep existing T1 tests happy when
run in thumbv7 mode.

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

Fix test cases.
Generate code for Mips32r1 unless a Mips32r2 feature is tested.

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

LDM writeback is not allowed if Rn is in the target register list.

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

Fix an ambiguously nested if.

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

Fix buildbot breakage caused by r139415.  I missed one instance of a manually create ARM::tB.

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

Fix assembly/disassembly of Thumb2 ADR instructions with immediate operands.

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

O64 will not be supported.

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

Make F31 and D15 non-reserved registers.

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

tidy up a bit

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

Thumb unconditional branches are allowed in IT blocks, and therefore should have a predicate operand, unlike conditional branches.

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

Update Clang AST attribute reader tblgen generation to match with ASTReader change

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

Mips32 does not reserve even-numbered floating point registers.

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

Make the SelectionDAG verify that all the operands of BUILD_VECTOR have the same type.  Teach DAGCombiner::visitINSERT_VECTOR_ELT not to make invalid BUILD_VECTORs.  Fixes PR10897.

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

Drop support for Mips1 and Mips2.

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

Implement vector-select support for avx256. Refactor the vblend implementation to have tablegen match the instruction by the node type

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

Thumb2 assembly parsing and encoding for MLA and MLS.

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

Don't tack "Instruction not interpretable yet!" onto the end of
the instruction.

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

Thumb2 assembly parsing and encoding for MCR, MCR2, MCRR, MCRR2.

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

Tidy up formatting a bit.

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

Thumb2 assembly parsing and encoding for LSL.

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

Thumb2 assembly parsing and encoding for LDRT.

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

Thumb2 assembly parsing and encoding for LDRSHT.

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

Thumb2 assembly parsing and encoding for LDRSH.

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

Thumb2 assembly parsing and encoding for LDRSBT.

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

Thumb2 assembly parsing and encoding for LDRSB.

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

Thumb2 assembly parsing and encoding for LDRH.

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

Shuffle a bit.

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

Drop support for Allegrex. Allegrex implements a variant of Mips2.

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

Thumb2 assembly parsing and encoding for LDREX/LDREXB/LDREXD/LDREXH.

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

Reapply r139247: Cache intermediate results during traceSiblingValue.

In some cases such as interpreters using indirectbr, the CFG can be very
complicated, and live range splitting may be forced to insert a large
number of phi-defs.  When that happens, traceSiblingValue can spend a
lot of time zipping around in the CFG looking for defs and reloads.

This patch causes more information to be cached in SibValues, and the
cached values are used to terminate searches early.  This speeds up
spilling by 20x in one interpreter test case.  For more typical code,
this is just a 10% speedup of spilling.

The previous version had bugs that caused miscompilations. They have
been fixed.

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