runs (if coalescing is disabled for example).

llvm-svn: 16259

analysis running time from 2.7869secs to 2.5226secs on 176.gcc.

llvm-svn: 16244

llvm-svn: 16153

Patch contributed by Paolo Invernizzi!

llvm-svn: 16152

Move include/Config and include/Support into include/llvm/Config,
include/llvm/ADT and include/llvm/Support. From here on out, all LLVM
public header files must be under include/llvm/.

llvm-svn: 16137

llvm-svn: 16123

runs after the initial run of the live interval analysis.

llvm-svn: 16075

llvm-svn: 16060

 Regression.CodeGen.Generic.2004-04-09-SameValueCoalescing.llx and the
code size problem.

This bug prevented us from doing most register coallesces.

llvm-svn: 16031

llvm-svn: 15784

llvm-svn: 15490

llvm-svn: 15489

llvm-svn: 15196

same as the PHI use.  This is not correct as the PHI use value is different
depending on which branch is taken.  This fixes espresso with aggressive
coallescing, and perhaps others.

llvm-svn: 15189

llvm-svn: 15187

LiveInterval>. This saves some space and removes the pointer
indirection caused by following the pointer.

llvm-svn: 15167

llvm-svn: 15157

ownership of the intervals.

llvm-svn: 15155

Interval.  This generalizes the isDefinedOnce mechanism that we used before
to help us coallesce ranges that overlap.  As part of this, every logical
range with a different value is assigned a different number in the interval.
For example, for code that looks like this:

0  X = ...
4  X += ...
  ...
N    = X

We now generate a live interval that contains two ranges: [2,6:0),[6,?:1)
reflecting the fact that there are two different values in the range at
different positions in the code.

Currently we are not using this information at all, so this just slows down
liveintervals.  In the future, this will change.

Note that this change also substantially refactors the joinIntervalsInMachineBB
method to merge the cases for virt-virt and phys-virt joining into a single
case, adds comments, and makes the code a bit easier to follow.

llvm-svn: 15154

 * Inline some functions
 * Eliminate some comparisons from the release build

This is good for another .3 on gcc.

llvm-svn: 15144

llvm-svn: 15135

will soon be renamed) into their own file.  The new file should not emit
DEBUG output or have other side effects.  The LiveInterval class also now
doesn't know whether its working on registers or some other thing.

In the future we will want to use the LiveInterval class and friends to do
stack packing.  In addition to a code simplification, this will allow us to
do it more easily.

llvm-svn: 15134

Use an explicit LiveRange class to represent ranges instead of an std::pair.
This is a minor cleanup, but is really intended to make a future patch simpler
and less invasive.

Alkis, could you please take a look at LiveInterval::liveAt?  I suspect that
you can add an operator<(unsigned) to LiveRange, allowing us to speed up the
upper_bound call by quite a bit (this would also apply to other callers of
upper/lower_bound).  I would do it myself, but I still don't understand that
crazy liveAt function, despite the comment. :)

Basically I would like to see this:
    LiveRange dummy(index, index+1);
    Ranges::const_iterator r = std::upper_bound(ranges.begin(),
                                                ranges.end(),
                                                dummy);

Turn into:
    Ranges::const_iterator r = std::upper_bound(ranges.begin(),
                                                ranges.end(),
                                                index);

llvm-svn: 15130

interfere.  Because these intervals have a single definition, and one of them
is a copy instruction, they are always safe to merge even if their lifetimes
interfere.  This slightly reduces the amount of spill code, for example on
252.eon, from:

 12837 spiller               - Number of loads added
  7604 spiller               - Number of stores added
  5842 spiller               - Number of register spills
 18155 liveintervals         - Number of identity moves eliminated after coalescing

to:

  12754 spiller               - Number of loads added
   7585 spiller               - Number of stores added
   5803 spiller               - Number of register spills
  18262 liveintervals         - Number of identity moves eliminated after coalescing

The much much bigger win would be to merge intervals with multiple definitions
(aka phi nodes) but this is not that day.

llvm-svn: 15124

llvm-svn: 15115

intervals need not be sorted anymore. Removing this redundant step
improves LiveIntervals running time by 5% on 176.gcc.

llvm-svn: 15106

fortunately, they are easy to handle if we know about them.  This patch fixes
some serious pessimization of code produced by the linscan register allocator.

llvm-svn: 15092

llvm-svn: 15089

llvm-svn: 15031

llvm-svn: 15005

is a simple change, but seems to improve code a little.  For example, on
256.bzip2, we went from 75.0s -> 73.33s (2% speedup).

llvm-svn: 15004

llvm-svn: 15003

ask instructions for their parent.

llvm-svn: 14998

llvm-svn: 14997

* vreg <-> vreg joining now works, enable it unconditionally when joining
  is enabled (which is the default).
* Fix a serious pessimization of spill code where we were saying that a
  spilled DEF operand was live into the subsequent instruction.  This allows
  for substantially better code when spilling starts to happen.

llvm-svn: 14993

order, causing the inactive list in the linearscan list to get unsorted, which
basically fuxored everything up severely.

These seems to fix the joiner, so with more testing I will enable it by default.

llvm-svn: 14992

Heavily refactor handleVirtualRegisterDef, adding comments and making it more
efficient.  It is also much easier to follow and convince ones self that it is
correct :)

Add -debug output to the joine, showing the result of joining the intervals.

llvm-svn: 14989

but make virtreg->virtreg joining stay off by default

llvm-svn: 14916

llvm-svn: 14720

llvm-svn: 14719