llvm-svn: 11655

1. LiveIntervals now implement a 4 slot per instruction model. Load,
   Use, Def and a Store slot. This is required in order to correctly
   represent caller saved register clobbering on function calls,
   register reuse in the same instruction (def resues last use) and
   also spill code added later by the allocator. The previous
   representation (2 slots per instruction) was insufficient and as a
   result was causing subtle bugs.

2. Fixes in spill code generation. This was the major cause of
   failures in the test suite.

3. Linear scan now has core support for folding memory operands. This
   is untested and not enabled (the live interval update function does
   not attempt to fold loads/stores in instructions).

4. Lots of improvements in the debugging output of both live intervals
   and linear scan. Give it a try... it is beautiful :-)

In summary the above fixes all the issues with the recent reserved
register elimination changes and get the allocator very close to the
next big step: folding memory operands.

llvm-svn: 11654

llvm-svn: 11629

variable information to take into account the change of instruction
address.

llvm-svn: 11628

llvm-svn: 11627

llvm-svn: 11625

by operator<< on MachineInstr's, and looking up what register "24" is all of the
time was greatly annoying.

llvm-svn: 11623

llvm-svn: 11622

llvm-svn: 11619

llvm-svn: 11609

llvm-svn: 11578

llvm-svn: 11577

llvm-svn: 11575

llvm-svn: 11574

llvm-svn: 11573

and it was only for debugging in the first place.

llvm-svn: 11557

that need them.  This is very useful on CISCy targets like the X86 because it
reduces the total spill pressure, and makes better use of it's (large)
instruction set.  Though the X86 backend doesn't know how to rewrite many
instructions yet, this already makes a substantial difference on 176.gcc for
example:

Before:
Time:
   8.0099 ( 31.2%)   0.0100 ( 12.5%)   8.0199 ( 31.2%)   7.7186 ( 30.0%)  Local Register Allocator

Code quality:
734559 asm-printer           - Number of machine instrs printed
111395 ra-local              - Number of registers reloaded
 79902 ra-local              - Number of registers spilled
231554 x86-peephole          - Number of peephole optimization performed

After:
Time:
   7.8700 ( 30.6%)   0.0099 ( 19.9%)   7.8800 ( 30.6%)   7.7892 ( 30.2%)  Local Register Allocator
Code quality:
733083 asm-printer           - Number of machine instrs printed
  2379 ra-local              - Number of reloads fused into instructions
109046 ra-local              - Number of registers reloaded
 79881 ra-local              - Number of registers spilled
230658 x86-peephole          - Number of peephole optimization performed

So by fusing 2300 instructions, we reduced the  static number of instructions
by 1500, and reduces the number of peepholes (and thus the work) by about 900.
This also clearly reduces the number of reload/spill instructions that are
emitted.

llvm-svn: 11542

llvm-svn: 11535

llvm-svn: 11517

llvm-svn: 11516

llvm-svn: 11515

Move out of line member functions of MachineBasicBlock to
MachineBasicBlock.cpp.

llvm-svn: 11497

analysis. It should only preserve them and update LiveVariables if it
already ran.

llvm-svn: 11479

Remove one of the operands of a two operand instruction

llvm-svn: 11478

MRegisterInfo::getNumRegs() instead of
MRegisterInfo::FirstVirtualRegister.

Also use MRegisterInfo::is{Physical,Virtual}Register where
appropriate.

llvm-svn: 11477

llvm-svn: 11476

clobber them by allocating other objects in the same space!

llvm-svn: 11454

that will be responsible for the creation of MachineFunctions and will
be required by all MachineFunctionPass passes.

llvm-svn: 11453

llvm-svn: 11449

llvm-svn: 11430

std::numeric_limits<float>::max() for weighting preallocated
intervals.

llvm-svn: 11427

llvm-svn: 11393

Whitespace cleanups.

llvm-svn: 11389

Add MachineBasicBlock::dump().

llvm-svn: 11364

Rename SetMachineOperandConst's formal parameters to match other methods here.
Mark some methods as being used only by the SPARC back-end.
Fix a missing-paren bug in OutputValue().

llvm-svn: 11363

MachineBasicBlock. Also change opcode to a short and numImplicitRefs
to an unsigned char so that overall MachineInstr's size stays the
same.

llvm-svn: 11357

llvm-svn: 11348

llvm-svn: 11346

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