Move Passes.h (which defines the interface to this file) to the top.
Move statistics to the top of the file.
Add a comment

llvm-svn: 11034

any test cases :-)

llvm-svn: 11032

of a linear search to find the first range for comparisons. This cuts
down the linear scan register allocator running time by a factor of 3
in 254.perlbmk and by a factor of 2.2 in 176.gcc.

llvm-svn: 11030

llvm-svn: 11029

Simplification of LiveIntervals::Interval::overlaps() and addition of
examples to overlaps() and liveAt() to make them clearer.

llvm-svn: 11028

Implement LiveVariables::getIndexMachineBasicBlock

llvm-svn: 11018

choose an ostream.

llvm-svn: 11016

when joining we need to check if we overlap with the second interval
or any of its aliases.

Also make joining intervals the default.

llvm-svn: 10973

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

with the current one.

llvm-svn: 10959

virtReg lives on the stack. Now a virtual register has an entry in the
virtual->physical map or the virtual->stack slot map but never in
both.

llvm-svn: 10958

llvm-svn: 10957

llvm-svn: 10956

llvm-svn: 10926

Moved iterators to common file.

llvm-svn: 10925

register yet (2nd try).

llvm-svn: 10896

register yet.

llvm-svn: 10895

LiveIntervals::Interval::expiredAt() and simplify regalloc code.

llvm-svn: 10894

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

llvm-svn: 10834

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

of a physical register is always dominated by a def).

llvm-svn: 10821

llvm-svn: 10820

overlap before adding their spill weight.

llvm-svn: 10819

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

LiveVariables::HandlePhysRegDef private they use information that is
not in memory when LiveVariables finishes the analysis.

Also update the TwoAddressInstructionPass to not use this interface.

llvm-svn: 10755

llvm-svn: 10749

This should get hunked over to the Sparc backend, along with
MachineCodeForInstruction and a bunch of files in include/llvm/Codegen,
but those battles will have to wait for a later time.

llvm-svn: 10731

llvm-svn: 10730

llvm-svn: 10728

of the register allocator as follows:

       before   after
mesa   2.3790  1.5994
vpr    2.6008  1.2078
gcc    1.9840  0.5273
mcf    0.2569  0.0470
eon    1.8468  1.4359
twolf  0.9475  0.2004
burg   1.6807  1.3300
lambda 1.2191  0.3764

Speedups range anyware from 30% to over 400% :-)

llvm-svn: 10712

llvm-svn: 10711

llvm-svn: 10710

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

llvm-svn: 10707