generated code over the simple spiller.  The new local spiller generates
substantially better code than the simple one in some cases, by reusing
values that are loaded out of stack slots and kept available in registers.

This primarily helps programs that are spilling a lot, and there is still
stuff that can be done to improve it.  This patch makes the local spiller
the default, as it's only a tiny bit slower than the simple spiller (it
increases the runtime of llc by < 1%).

Here are some numbers with speedups.

Program    #reuse  old(s)    new(s)  Speedup

Povray:     3452,  16.87 ->  15.93   (5.5%)
177.mesa:   2176,   2.77 ->   2.76   (0%)
179.art:      35,  28.43 ->  28.01   (1.5%)
183.equake:   55,  61.44 ->  61.41   (0%)
188.ammp:    869, 174    -> 149      (15%)

164.gzip:     43,  40.73 ->  40.71   (0%)
175.vpr:     351,  18.54 ->  17.34   (6.5%)
176.gcc:    2471,   5.01 ->   4.92   (1.8%)
181.mcf       42,  79.30 ->  75.20   (5.2%)
186.crafty:  484,  29.73 ->  30.04   (-1%)
197.parser:  251,  10.47 ->  10.67   (-1%)
252.eon:    1501,   1.98 ->   1.75   (12%)
253.perlbm: 1183,  14.83 ->  14.42   (2.8%)
254.gap:     825,   7.46 ->   7.29   (2.3%)
255.vortex:  285,  10.51 ->  10.27   (2.3%)
256.bzip2:    63,  55.70 ->  55.20   (0.9%)
300.twolf:   830,  21.63 ->  22.00   (-1%)

PtrDist/ks    14,  32.75 -> 17.53    (46.5%)
Olden/tsp     46,   8.71 ->  8.24    (5.4%)
Free/distray  70,   1.09 ->  0.99    (9.2%)

llvm-svn: 16629

llvm-svn: 16628

llvm-svn: 16626

targets that supported multiple memory operands.

llvm-svn: 16614

llvm-svn: 16613

* Add const_iterator stuff
* Add a print method, which means that I can now call dump() from the
  debugger.

llvm-svn: 16612

llvm-svn: 16609

two spillers produce perfectly identical code (at least on povray and eon),
but the simple spiller is substantially faster than the local spiller. Once
the local spiller is improved, we can switch back.

Switching cuts 5.2% off of the llc time for povray (about 1.3s).

llvm-svn: 16608

use a simple vector.  This speeds up -spiller=simple from taking 22s to taking
.1s on povray (debug build).  This change does not modify the generated code.

llvm-svn: 16607

data structures).  Fix the print method to send to the right ostream, not
always cerr.  Delete typedefs that are only used once.

llvm-svn: 16606

the beginning of processing the next one.

llvm-svn: 16605

prune #includes, add print/dump methods, etc.  No functionality changes.

llvm-svn: 16604

compile on windows. This patch was contributed by Paolo Invernizzi.

llvm-svn: 16539

llvm-svn: 16533

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: 16188

llvm-svn: 16187

llvm-svn: 16153

Patch contributed by Paolo Invernizzi!

llvm-svn: 16152

free allocatable register, we prefer the a free one with the most uses
of inactive intervals.

llvm-svn: 16148

free allocatable register, we prefer the a free one with the most uses
of inactive intervals. This causes less spills and performes a bit
better compared to gcc:

Program                 | GCC/LLC (Before)| GCC/LLC (After)
164.gzip/164.gzip       | 0.59            | 0.60
175.vpr/175.vpr         | 0.57            | 0.58
176.gcc/176.gcc         | 0.59            | 0.61
181.mcf/181.mcf         | 0.94            | 0.95
186.crafty/186.crafty   | 0.62            | 0.62
197.parser/197.parser   | 0.89            | 0.88
252.eon/252.eon         | 0.61            | 0.66
253.perlbmk/253.perlbmk | 0.79            | 0.84
254.gap/254.gap         | 0.81            | 0.81
255.vortex/255.vortex   | 0.92            | 0.93
256.bzip2/256.bzip2     | 0.69            | 0.69
300.twolf/300.twolf     | 0.91            | 0.90

llvm-svn: 16147

stored in a binary heap.

llvm-svn: 16143

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

lists. Instead of scanning the vector backwards, scan it forward and
swap each element we want to erase. Then at the end erase all removed
intervals at once. This doesn't save much: 0.08s out of 4s when
compiling 176.gcc.

llvm-svn: 16136

llvm-svn: 16135

llvm-svn: 16123

Put this change back in after testing from Reid proved its innocence.  getSpillSize now returns value in bits

llvm-svn: 16102

llvm-svn: 16077

LiveVariables.

llvm-svn: 16076

runs after the initial run of the live interval analysis.

llvm-svn: 16075

investicated further as the linearscan variants don't really need
LiveVariables...

llvm-svn: 16074

Back out change to divide getSpillSize by 8 until I figure out why it breaks x86, which has register sizes in bits.

llvm-svn: 16073

llvm-svn: 16071

llvm-svn: 16070

register set anymore. Its users now use the MRegisterInfo API.

llvm-svn: 16061

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

with emitting .xwords when not on an 8-byte boundary (.xword 0 is not the
same as 8 .byte 0's).  Because we do not know when or when we are not aligned,
just emit bytes like the old V9 asmprinter did.

llvm-svn: 16006

bytes.

llvm-svn: 15970