is a move between two registers, at least one of the registers is
virtual and the two live intervals do not overlap.

This results in about 40% reduction in intervals, 30% decrease in the
register allocators running time and a 20% increase in peephole
optimizations (mainly move eliminations).

The option can be enabled by passing -join-liveintervals where
appropriate.

llvm-svn: 10965

llvm-svn: 10957

llvm-svn: 10956

llvm-svn: 10893

when we join intervals and one of the two will need to be removed.

llvm-svn: 10892

llvm-svn: 10847

LiveIntervals::Interval::liveAt. Both were considering the live ranges
closed in the end, when they are actually open.

llvm-svn: 10835

be dead at the defining instruction but can only be killed in
subsequent ones.

llvm-svn: 10833

LiveVariables.

llvm-svn: 10830

llvm-svn: 10824

ranges, i.e. [a,b)

llvm-svn: 10822

when an implicitely defined register is later used by an alias. For example:

         call foo
         %reg1024 = mov %AL

The call implicitely defines EAX but only AL is used. Before this fix
no information was available on AL. Now EAX and all its aliases except
AL get defined and die at the call instruction whereas AL lives to be
killed by the assignment.

llvm-svn: 10813

30-50% decrease in running time of the linear scan register allocator.

llvm-svn: 10707

llvm-svn: 10695

which denotes the register we would like to be assigned to (virtual or
physical). In register allocation, if this hint exists and we can map
it to a physical register (it is either a physical register or it is a
virtual register that already got assigned to a physical one) we use
that register if it is available instead of a random one in the free
pool.

llvm-svn: 10634

with live intervals was missing registers that were used before they
were defined (in the arbitrary order live intervals numbers
instructions).

llvm-svn: 10603

llvm-svn: 10584

nesting level when computing it. Right now the allocator uses:

    w = sum_over_defs_uses( 10 ^ nesting level );

llvm-svn: 10569

for live ranges that fall into assigned registers' holes.

llvm-svn: 10566

instead, since this pass doesn't expose any state to its users.

llvm-svn: 10520

instruction pass. This also fixes all remaining bugs for this new
allocator to pass all tests under test/Programs.

llvm-svn: 10515

killing instruction is tracked. This causes the LiveIntervals to
create bogus intervals. The workaound is to add a range to the
interval from the redefinition to the end of the basic block.

llvm-svn: 10510

Move some of the longer LiveIntervals::Interval method out of the
header and add debug information to them. Fix bug and simplify range
merging code.

llvm-svn: 10509

llvm-svn: 10469

    a) remove opIsUse(), opIsDefOnly(), opIsDefAndUse()
    b) add isUse(), isDef()
    c) rename opHiBits32() to isHiBits32(),
              opLoBits32() to isLoBits32(),
              opHiBits64() to isHiBits64(),
              opLoBits64() to isLoBits64().

This results to much more readable code, for example compare
"op.opIsDef() || op.opIsDefAndUse()" to "op.isDef()" a pattern used
very often in the code.

llvm-svn: 10461

llvm-svn: 10449

llvm-svn: 10445

llvm-svn: 10290

llvm-svn: 10289

Merging the linear scan register allocator in trunk. It currently passes most tests under test/Programs/SingleSource/Benchmarks/Shootout so development will continue on trunk. The allocator is not enabled by default. You will need to pass -regallo=linearscan to lli or llc to use it.

llvm-svn: 10103