ilist of MachineInstr objects. This allows constant time removal and
insertion of MachineInstr instances from anywhere in each
MachineBasicBlock. It also allows for constant time splicing of
MachineInstrs into or out of MachineBasicBlocks.

llvm-svn: 11340

llvm-svn: 11283

slots each. As a concequence they get numbered as 0, 2, 4 and so
on. The first slot is used for operand uses and the second for
defs. Here's an example:

0: A = ...
2: B = ...
4: C = A + B ;; last use of A

The live intervals should look like:

A = [1, 5)
B = [3, x)
C = [5, y)

llvm-svn: 11141

access. Rather we only have to do it on the creation of the interval.

llvm-svn: 11135

outside of loops = 0.

llvm-svn: 11085

llvm-svn: 11057

llvm-svn: 11054

llvm-svn: 11048

llvm-svn: 11047

MRegisterInfo::isVirtualRegister.

llvm-svn: 11045

llvm-svn: 11040

llvm-svn: 11038

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

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

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