After uses of a live range are removed, recompute the live range to only cover
the remaining uses. This is necessary after rematerializing the value before
some (but not all) uses.

llvm-svn: 125058

llvm-svn: 125054

<rdar://problem/8959122> illegal register operands for UMULL instruction in cfrac nightly test
I'm stil working on a unit test, but the case is:
rx = movcc rx, r3
r2 = ldr
r2, r3 = umull r2, r2

The anti-dep breaker should not convert this into an illegal instruction:
r2, r2 = umull

llvm-svn: 124932

If the interference overlaps the instruction, we cannot separate it.

llvm-svn: 124918

If these inequalities don't hold, we are creating a live range split that won't
allocate.

llvm-svn: 124917

In that case we simply ignore the landing pad and split live ranges before the
first terminator.

llvm-svn: 124907

llvm-svn: 124904

purpose. Fixes PR9080!

llvm-svn: 124903

If interference reaches the last split point, it is effectively live out and
should be marked as 'MustSpill'.

This can make a difference when the terminator uses a register. There is no way
that register can be reused in the outgoing CFG bundle, even if it isn't live
out.

llvm-svn: 124900

A live range cannot be split everywhere in a basic block. A split must go before
the first terminator, and if the variable is live into a landing pad, the split
must happen before the call that can throw.

llvm-svn: 124894

We should not be attempting a region split if it won't lead to at least one
directly allocatable interval. That could cause infinite splitting loops.

llvm-svn: 124893

precisely track pressure on a selection DAG, but we can at least keep
it balanced. This design accounts for various interesting aspects of
selection DAGS: register and subregister copies, glued nodes, dead
nodes, unused registers, etc.

Added SUnit::NumRegDefsLeft and ScheduleDAGSDNodes::RegDefIter.

Note: I disabled PrescheduleNodesWithMultipleUses when register
pressure is enabled, based on no evidence other than I don't think it
makes sense to have both enabled.

llvm-svn: 124853

DebugLoc associated with a machine instruction is used to emit location entries. DebugLoc associated with a DBG_VALUE is used to identify lexical scope of the variable. After register allocation, while inserting DBG_VALUE remember original debug location for the first instruction and reuse it, otherwise dwarf writer may be mislead in identifying the variable's scope.

llvm-svn: 124845

llvm-svn: 124843

llvm-svn: 124842

When the live range is live through a block that doesn't use the register, but
that has interference, region splitting wants to split at the top and bottom of
the basic block.

llvm-svn: 124839

Allow a live range to end with a kill flag, but don't allow a kill flag that
doesn't end the live range.

This makes the machine code verifier more useful during register allocation when
kill flag computation is deferred.

llvm-svn: 124838

llvm-svn: 124827

llvm-svn: 124815

llvm-svn: 124814

llvm-svn: 124813

If the found value is not live-through the block, we should only add liveness up
to the requested slot index. When the value is live-through, the whole block
should be colored.

Bug found by SSA verification in the machine code verifier.

llvm-svn: 124812

These end points come from the inserted copies, and can be passed directly to
useIntv. This simplifies the coloring code.

llvm-svn: 124799

llvm-svn: 124798

llvm-svn: 124779

llvm-svn: 124778

The greedy register allocator revealed some problems with the value mapping in
SplitKit. We would sometimes start mapping values before all defs were known,
and that could change a value from a simple 1-1 mapping to a multi-def mapping
that requires ssa update.

The new approach collects all defs and register assignments first without
filling in any live intervals. Only when finish() is called, do we compute
liveness and mapped values. At this time we know with certainty which values map
to multiple values in a split range.

This also has the advantage that we can compute live ranges based on the
remaining uses after rematerializing at split points.

The current implementation has many opportunities for compile time optimization.

llvm-svn: 124765

llvm-svn: 124755

llvm-svn: 124752

the load, then it may be legal to transform the load and store to integer
load and store of the same width.

This is done if the target specified the transformation as profitable. e.g.
On arm, this can transform:
vldr.32 s0, []
vstr.32 s0, []

to

ldr r12, []
str r12, []

rdar://8944252

llvm-svn: 124708

llvm-svn: 124688

llvm-svn: 124611

llvm-svn: 124587

llvm-svn: 124569

This is similar to the -unroll-threshold option. There should be no change in
behavior when -tail-dup-size is not explicit on the llc command line.

llvm-svn: 124564

Teach DAGCombine to fold fold (sra (trunc (sr x, c1)), c2) -> (trunc (sra x, c1+c2) when c1 equals the amount of bits that are truncated off.

This happens all the time when a smul is promoted to a larger type.

On x86-64 we now compile "int test(int x) { return x/10; }" into
  movslq  %edi, %rax
  imulq $1717986919, %rax, %rax
  movq  %rax, %rcx
  shrq  $63, %rcx
  sarq  $34, %rax <- used to be "shrq $32, %rax; sarl $2, %eax"
  addl  %ecx, %eax

This fires 96 times in gcc.c on x86-64.

llvm-svn: 124559

This happens e.g. for code like "X - X%10" where we lower the modulo operation
to a series of multiplies and shifts that are then subtracted from X, leading to
this missed optimization.

llvm-svn: 124532

llvm-svn: 124526

llvm-svn: 124522

Re-commit r124462 with fixes. Tail recursion elim will now dup ret into unconditional predecessor to enable TCE on demand.

llvm-svn: 124518