Convert several std::vectors over to SmallVector, and use reserve() as appropriate for cases where std::vector is still used.

llvm-svn: 54820

llvm-svn: 54770

Make the allocation of LiveIntervals explicit, rather than holding them in the r2iMap_ by value.  This will prevent references to them from being invalidated
if the map is changed.

llvm-svn: 54763

to multiply the instruction count by a constant factor in a few places, which
caused the register allocator to require many more iterations.

llvm-svn: 53959

live intervals itself to use an instruction count approximation that is 
not affected by inserting empty indices.

llvm-svn: 53937

as a questionable case, but the code isn't actually needed.

llvm-svn: 52657

Enhanced heuristic to determine the *best* register to spill. Instead of picking the register with the lowest spill weight. Consider (up to) 2 additional registers with spill weights that are close to the lowest spill weight. The one with fewest defs and uses that conflicts with the current interval (weighted by loop depth) is the spill candidate.

This is not always a win, but there are much more wins than loses and wins tend to be more noticeable.

llvm-svn: 52554

llvm-svn: 52040

llvm-svn: 51934

llvm-svn: 49544

llvm-svn: 49167

llvm-svn: 48751

llvm-svn: 48341

When the register allocator runs out of registers, spill a physical register around the def's and use's of the interval being allocated to make it possible for the interval to target a register and spill it right away and restore a register for uses. This likely generates terrible code but is before than aborting.

llvm-svn: 48218

llvm-svn: 48204

llvm-svn: 48175

instead of init'ing it maximally to zeros on entry.  getFreePhysReg
is pretty hot and only a few elements are typically used.  This speeds
up linscan by 5% on 176.gcc.

llvm-svn: 47631

llvm-svn: 47629

would have been a Godsend here!

llvm-svn: 47625

llvm-svn: 47375

llvm-svn: 46930

preserved.

llvm-svn: 45596

that "machine" classes are used to represent the current state of
the code being compiled.  Given this expanded name, we can start 
moving other stuff into it.  For now, move the UsedPhysRegs and
LiveIn/LoveOuts vectors from MachineFunction into it.

Update all the clients to match.

This also reduces some needless #includes, such as MachineModuleInfo
from MachineFunction.

llvm-svn: 45467

llvm-svn: 45418

llvm-svn: 44838

When a live interval is being spilled, rather than creating short, non-spillable
intervals for every def / use, split the interval at BB boundaries. That is, for
every BB where the live interval is defined or used, create a new interval that
covers all the defs and uses in the BB.

This is designed to eliminate one common problem: multiple reloads of the same
value in a single basic block. Note, it does *not* decrease the number of spills
since no copies are inserted so the split intervals are *connected* through
spill and reloads (or rematerialization). The newly created intervals can be
spilled again, in that case, since it does not span multiple basic blocks, it's
spilled in the usual manner. However, it can reuse the same stack slot as the
previously split interval.

This is currently controlled by -split-intervals-at-bb.

llvm-svn: 44198

llvm-svn: 44154

llvm-svn: 44153

llvm-svn: 44010

If an interval is being undone clear its preference as well since the source interval may have been undone as well.

llvm-svn: 43670

can be eliminated by the allocator is the destination and source targets the
same register. The most common case is when the source and destination registers
are in different class. For example, on x86 mov32to32_ targets GR32_ which
contains a subset of the registers in GR32.

The allocator can do 2 things:
1. Set the preferred allocation for the destination of a copy to that of its source.
2. After allocation is done, change the allocation of a copy destination (if
   legal) so the copy can be eliminated.

This eliminates 443 extra moves from 403.gcc.

llvm-svn: 43662

llvm-svn: 43069

llvm-svn: 43061

llvm-svn: 43043

llvm-svn: 42898

Pluggable coalescers inplementation.

llvm-svn: 41743

Re-implement trivial rematerialization. This allows def MIs whose live intervals that are coalesced to be rematerialized.

llvm-svn: 41060

simultaneously.  Move that pass to SimpleRegisterCoalescing.

This makes it easier to implement alternative register allocation and
coalescing strategies while maintaining reuse of the existing live
interval analysis.

llvm-svn: 37520

certain linkers...

llvm-svn: 36944

llvm-svn: 36662