llvm-svn: 11759

llvm-svn: 11758

llvm-svn: 11757

llvm-svn: 11756

llvm-svn: 11755

block into MachineBasicBlock::getFirstTerminator().

This also fixes a bug in the implementation of the above in both
RegAllocLocal and InstrSched, where instructions where added after the
terminator if the basic block's only instruction was a terminator (it
shouldn't matter for RegAllocLocal since this case never occurs in
practice).

llvm-svn: 11748

Improved PhysRegTracker interface. RegAlloc lazily allocates the register tracker using a std::auto_ptr

llvm-svn: 11738

Simplify iterator usage now that we have next(). Also don't pass iterators by reference now that MachineInstr* are in an ilist

llvm-svn: 11732

llvm-svn: 11724

Fix comments in PhysRegTracker and rename isPhysRegAvail to isRegAvail to be consistent with the other two

llvm-svn: 11723

llvm-svn: 11721

llvm-svn: 11720

llvm-svn: 11719

llvm-svn: 11716

one terminator instruction in each basic block.

llvm-svn: 11714

llvm-svn: 11704

Also make it less aggressive as the current implementation breaks in
some cases.

llvm-svn: 11696

llvm-svn: 11687

llvm-svn: 11676

llvm-svn: 11675

llvm-svn: 11674

llvm-svn: 11659

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