* Make the previous patch more efficient by not allocating a temporary MachineInstr
  to do analysis.

*** FOLD getelementptr instructions into loads and stores when possible,
    making use of some of the crazy X86 addressing modes.

For example, the following C++ program fragment:

struct complex {
    double re, im;
    complex(double r, double i) : re(r), im(i) {}
};
inline complex operator+(const complex& a, const complex& b) {
    return complex(a.re+b.re, a.im+b.im);
}
complex addone(const complex& arg) {
    return arg + complex(1,0);
}

Used to be compiled to:
_Z6addoneRK7complex:
        mov %EAX, DWORD PTR [%ESP + 4]
        mov %ECX, DWORD PTR [%ESP + 8]
***     mov %EDX, %ECX
        fld QWORD PTR [%EDX]
        fld1
        faddp %ST(1)
***     add %ECX, 8
        fld QWORD PTR [%ECX]
        fldz
        faddp %ST(1)
***     mov %ECX, %EAX
        fxch %ST(1)
        fstp QWORD PTR [%ECX]
***     add %EAX, 8
        fstp QWORD PTR [%EAX]
        ret

Now it is compiled to:
_Z6addoneRK7complex:
        mov %EAX, DWORD PTR [%ESP + 4]
        mov %ECX, DWORD PTR [%ESP + 8]
        fld QWORD PTR [%ECX]
        fld1
        faddp %ST(1)
        fld QWORD PTR [%ECX + 8]
        fldz
        faddp %ST(1)
        fxch %ST(1)
        fstp QWORD PTR [%EAX]
        fstp QWORD PTR [%EAX + 8]
        ret

Other programs should see similar improvements, across the board.  Note that
in addition to reducing instruction count, this also reduces register pressure
a lot, always a good thing on X86.  :)

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11819 91177308-0d34-0410-b5e6-96231b3b80d8

Add a helper to create an addressing mode given all of the pieces.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11818 91177308-0d34-0410-b5e6-96231b3b80d8

add an inefficient way of folding structure and constant array indexes together
into a single LEA instruction.  This should improve the code generated for
things like X->A.B.C[12].D.

The bigger benefit is still coming though.  Note that this uses an LEA instruction
instead of an add, giving the register allocator more freedom.  We should probably
never generate ADDri32's.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11817 91177308-0d34-0410-b5e6-96231b3b80d8

Implement special case for storing an immediate into memory so that we don't need
an intermediate register.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11816 91177308-0d34-0410-b5e6-96231b3b80d8

Cygwin defines log2 as a macro. Undef it here IFF it has already been defined,
so that we always get the inline function instead. Remember, kids, like it says
in the GCC manual, "An Inline Function is As Fast As a Macro."

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11815 91177308-0d34-0410-b5e6-96231b3b80d8

small portability fix.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11814 91177308-0d34-0410-b5e6-96231b3b80d8

Add support for 'rename'

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11813 91177308-0d34-0410-b5e6-96231b3b80d8

Make the verifier a little more explicit about this problem.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11811 91177308-0d34-0410-b5e6-96231b3b80d8

Add support for remove, fwrite, and fread

Also fix problem where we didn't check to see if a node pointer was null.
Though fclose(null) doesn't make a lot of sense, 300.twolf does it.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11810 91177308-0d34-0410-b5e6-96231b3b80d8

Added the VTune tests.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11809 91177308-0d34-0410-b5e6-96231b3b80d8

FunctionLiveVarInfo.h moved: include/llvm/CodeGen -> lib/Target/Sparc/LiveVar

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11804 91177308-0d34-0410-b5e6-96231b3b80d8

Fix some unexpected fallout from the config.h changes.  Because the CBE no
longer was getting this #include, it always fell back on the less precise
floating point initializer values, causing some testsuite failures.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11803 91177308-0d34-0410-b5e6-96231b3b80d8

Fix a faulty optimization on FP values

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11801 91177308-0d34-0410-b5e6-96231b3b80d8

Fixed minor typos.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11800 91177308-0d34-0410-b5e6-96231b3b80d8

If a block is made dead, make sure to promptly remove it.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11799 91177308-0d34-0410-b5e6-96231b3b80d8

Move machine code rewriter and spiller outside the register
allocator.

The implementation is completely rewritten and now employs several
optimizations not exercised before. For example for 164.gzip we have
997 loads and 699 stores vs the 1221 loads and 880 stores we have
before.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11798 91177308-0d34-0410-b5e6-96231b3b80d8

Implement SimplifyCFG/switch_switch_fold.ll
This case occurs many times in various benchmarks, especially when combined
with the previous patch.  This allows it to get stuff like:
  if (X == 4 || X == 3)
    if (X == 5 || X == 8)

and

switch (X) {
case 4: case 5: case 6:
  if (X == 4 || X == 5)

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11797 91177308-0d34-0410-b5e6-96231b3b80d8

New testcase.  Switch instructions that go to switch instructions should be
merged.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11796 91177308-0d34-0410-b5e6-96231b3b80d8

Add predicates for checking if a virtual register has a physical
register mapping or a stack slot mapping.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11795 91177308-0d34-0410-b5e6-96231b3b80d8

Add some helpful methods for dealing with switch instructions

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11794 91177308-0d34-0410-b5e6-96231b3b80d8

Rearrange code a bit

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11793 91177308-0d34-0410-b5e6-96231b3b80d8

Implement: test/Regression/Transforms/SimplifyCFG/switch_create.ll

This turns code like this:
  if (X == 4 | X == 7)
and
  if (X != 4 & X != 7)
into switch instructions.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11792 91177308-0d34-0410-b5e6-96231b3b80d8

The simplifycfg pass should be able to turn stuff like:
  if (X == 4 || X == 7)
and
  if (X != 4 && X != 7)

into switch instructions.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11791 91177308-0d34-0410-b5e6-96231b3b80d8

Wow, the description of the 'switch' instruction was out of date.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11790 91177308-0d34-0410-b5e6-96231b3b80d8

we no longer include boost

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11789 91177308-0d34-0410-b5e6-96231b3b80d8

Hrm, my find must have been faulty.  It didn't remove these as well.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11788 91177308-0d34-0410-b5e6-96231b3b80d8

Boost is now unneeded, thanks to the fix for PR253, contributed by Reid Spencer!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11787 91177308-0d34-0410-b5e6-96231b3b80d8

Now that's a new feature!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11786 91177308-0d34-0410-b5e6-96231b3b80d8

Use the new LLVM is_class template instead of the boost one, allowing us to
remove our dependency on boost!  Thanks to Reid Spencer for making this possible!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11785 91177308-0d34-0410-b5e6-96231b3b80d8

Check in a new type_traits header which provides the mysterious is_class
template.  Thanks go out to Reid Spencer for skillfully extracting this
from boost!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11784 91177308-0d34-0410-b5e6-96231b3b80d8

Noone cares about similarity to boost

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11783 91177308-0d34-0410-b5e6-96231b3b80d8

Make enum private as it is an implementation detail.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11782 91177308-0d34-0410-b5e6-96231b3b80d8

Remove '4Virt' from member function names as it is obvious.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11781 91177308-0d34-0410-b5e6-96231b3b80d8

Refactor VirtRegMap out of RegAllocLinearScan as the first part of bug
251 (providing a generic machine code rewriter/spiller).

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11780 91177308-0d34-0410-b5e6-96231b3b80d8

Include Config/config.h for SHLIBEXT.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11779 91177308-0d34-0410-b5e6-96231b3b80d8

DataTypes.h is now output from configure, and shortened

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11778 91177308-0d34-0410-b5e6-96231b3b80d8

Add SUBSTing checks for sys/types.h and inttypes.h; add DataTypes.h to AC_OUTPUT.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11777 91177308-0d34-0410-b5e6-96231b3b80d8

Regenerated with autoconf-2.57.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11776 91177308-0d34-0410-b5e6-96231b3b80d8

Generate much more efficient code in programs like pifft

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11775 91177308-0d34-0410-b5e6-96231b3b80d8

Fix a small typeo in my checkin last night that broke vortex and other programs :(

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11774 91177308-0d34-0410-b5e6-96231b3b80d8

Regenerated with autoheader-2.57.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11773 91177308-0d34-0410-b5e6-96231b3b80d8

Regenerated with autoconf-2.57.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11772 91177308-0d34-0410-b5e6-96231b3b80d8

Change test for pthreads to use AC_SUBST; add ThreadSupport.h as an AC_OUTPUT.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11771 91177308-0d34-0410-b5e6-96231b3b80d8

ThreadSupport.h is now output from configure.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11770 91177308-0d34-0410-b5e6-96231b3b80d8

Remove check for slist

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11769 91177308-0d34-0410-b5e6-96231b3b80d8

Fix InstCombine/2004-02-23-ShiftShiftOverflow.ll
Also, turn 'shr int %X, 1234' into 'shr int %X, 31'

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11768 91177308-0d34-0410-b5e6-96231b3b80d8

Test for the other way also

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11767 91177308-0d34-0410-b5e6-96231b3b80d8

New testcase

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11766 91177308-0d34-0410-b5e6-96231b3b80d8

Renamed to hash_set.in; move to using autoconf substitution tags.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11765 91177308-0d34-0410-b5e6-96231b3b80d8

Renamed to hash_map.in; move to using autoconf substitution tags.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11764 91177308-0d34-0410-b5e6-96231b3b80d8

Add include/Support/hash_map and include/Support/hash_set as AC_OUTPUT files.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11763 91177308-0d34-0410-b5e6-96231b3b80d8

Regenerated using autoheader-2.57.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11762 91177308-0d34-0410-b5e6-96231b3b80d8

Move HASH_* checks to using AC_SUBST instead of AC_DEFINE. Tighten up some whitespace and comments.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11761 91177308-0d34-0410-b5e6-96231b3b80d8

Regenerated using autoconf-2.57.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11760 91177308-0d34-0410-b5e6-96231b3b80d8

Add number of spilled registers statistic.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11759 91177308-0d34-0410-b5e6-96231b3b80d8

Fix bugs in finegrainification

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11758 91177308-0d34-0410-b5e6-96231b3b80d8

Finegrainify namespacification

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11757 91177308-0d34-0410-b5e6-96231b3b80d8

Use MachineBasicBlock::getParent().

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11756 91177308-0d34-0410-b5e6-96231b3b80d8

Remove implementation of default constructor as it is useless now.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11755 91177308-0d34-0410-b5e6-96231b3b80d8

Renamed from include/Support/iterator. Doxygenify comments; add autoconf substitution tags.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11754 91177308-0d34-0410-b5e6-96231b3b80d8

Replaced by include/Support/iterator.in.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11753 91177308-0d34-0410-b5e6-96231b3b80d8

Regenerated with autoheader-2.57.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11752 91177308-0d34-0410-b5e6-96231b3b80d8

Add include/Support/iterator as an AC_OUTPUT file.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11751 91177308-0d34-0410-b5e6-96231b3b80d8

Make all iterator checks use AC_SUBST instead of AC_DEFINE.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11750 91177308-0d34-0410-b5e6-96231b3b80d8

Regenerated with autoconf-2.57.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11749 91177308-0d34-0410-b5e6-96231b3b80d8

Refactor rewinding code for finding the first terminator of a basic
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).

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11748 91177308-0d34-0410-b5e6-96231b3b80d8

Simplify code a bit, don't go off the end of the block, now that the current
block we are in might be empty

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11744 91177308-0d34-0410-b5e6-96231b3b80d8

We were forgetting to add FP_REG_KILL instructions to basic blocks which will
eventually get an assignment due to elimination of PHIs.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11743 91177308-0d34-0410-b5e6-96231b3b80d8

Implement cast.ll::test14/15

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11742 91177308-0d34-0410-b5e6-96231b3b80d8

Add tests for casts that should be eliminated

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11741 91177308-0d34-0410-b5e6-96231b3b80d8

Refactor some code.  In the mul - setcc folding case, we really care about
whether this is the sign bit or not, so check unsigned comparisons as well.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11740 91177308-0d34-0410-b5e6-96231b3b80d8

Handle the unsigned form as well

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11739 91177308-0d34-0410-b5e6-96231b3b80d8

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11738 91177308-0d34-0410-b5e6-96231b3b80d8

Implement mul.ll:test11

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11737 91177308-0d34-0410-b5e6-96231b3b80d8

Add a slight variant of test10

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11736 91177308-0d34-0410-b5e6-96231b3b80d8

Implement "strength reduction" of   X <= C and X >= C

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11735 91177308-0d34-0410-b5e6-96231b3b80d8

Implement InstCombine/mul.ll:test10, which is a case that occurs when dealing
with "predication"

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11734 91177308-0d34-0410-b5e6-96231b3b80d8

This multiply can be eliminated

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11733 91177308-0d34-0410-b5e6-96231b3b80d8

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11732 91177308-0d34-0410-b5e6-96231b3b80d8

Update the 'new features' section

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11731 91177308-0d34-0410-b5e6-96231b3b80d8

Bug fixed

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11730 91177308-0d34-0410-b5e6-96231b3b80d8

Work around a gas bug.  Print '-9223372036854775808' as unsigned.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11729 91177308-0d34-0410-b5e6-96231b3b80d8

Implement cast fp -> bool

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11728 91177308-0d34-0410-b5e6-96231b3b80d8

Add testcase for the casts that are missing in PR249

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11727 91177308-0d34-0410-b5e6-96231b3b80d8

Stop passing iterators around by reference now that we have ilists!

Implement cast Type::ULongTy -> double

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11726 91177308-0d34-0410-b5e6-96231b3b80d8

Some code cleanups from Chris

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11724 91177308-0d34-0410-b5e6-96231b3b80d8

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11723 91177308-0d34-0410-b5e6-96231b3b80d8

Add a new cmove instruction

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11722 91177308-0d34-0410-b5e6-96231b3b80d8

Move LiveIntervals.h up to be the first included header

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11721 91177308-0d34-0410-b5e6-96231b3b80d8

Pull PhysRegTracker out of RegAllocLinearScan as it can be used by other allocators as well

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11720 91177308-0d34-0410-b5e6-96231b3b80d8

Move LiveIntervals.h to lib/CodeGen since it shouldn't be exposed to other parts of the compiler

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11719 91177308-0d34-0410-b5e6-96231b3b80d8

Only insert FP_REG_KILL instructions in MachineBasicBlocks that actually
use FP instructions.  This reduces the number of instructions inserted in
176.gcc (for example) from 58074 to 101 (it doesn't use much FP, which
is typical).  This reduction speeds up the entire code generator.  In the
case of 176.gcc, llc went from taking 31.38s to 24.78s.  The passes that
sped up the most are the register allocator and the 2 live variable analysis
passes, which sped up 2.3, 1.3, and 1.5s respectively.  The asmprinter
pass also sped up because it doesn't print the instructions in comments :)

Note that this patch is likely to expose latent bugs in machine code passes,
because now basicblock can be empty, where they were never empty before.  I
cleaned out regalloclocal, but who knows about linscan :)

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11717 91177308-0d34-0410-b5e6-96231b3b80d8

Another bug fix for empty MBB's

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11716 91177308-0d34-0410-b5e6-96231b3b80d8

Move MOTy::UseType enum into MachineOperand. This eliminates the
switch statements in the constructors and simplifies the
implementation of the getUseType() member function. You will have to
specify defs using MachineOperand::Def instead of MOTy::Def though
(similarly for Use and UseAndDef).

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11715 91177308-0d34-0410-b5e6-96231b3b80d8

Fix a bug where we were implicitly assuming that there would be at least
one terminator instruction in each basic block.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11714 91177308-0d34-0410-b5e6-96231b3b80d8

Reduce the number of pointless copies inserted due to constant pointer refs.
Also, make an assertion actually fireable!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11713 91177308-0d34-0410-b5e6-96231b3b80d8

Fix bug in previous checkout: leave the iterator at the first instruction
AFTER the GEP that was emitted.  :(

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11712 91177308-0d34-0410-b5e6-96231b3b80d8

Fix silly bug in implementation of getUseType(). Thanks Misha.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11711 91177308-0d34-0410-b5e6-96231b3b80d8

Completely rewrite how getelementptr instructions are expanded.  This has two
(minor) benefits right now:

1. An extra dummy MOVrr32 is gone.  This move would often be coallesced by
   both allocators anyway.
2. The code now uses the gep_type_iterator to walk the gep, which should future
   proof it a bit.  It still assumes that array indexes are Longs though.

These don't really justify rewriting the code.  The big benefit will come later
though.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11710 91177308-0d34-0410-b5e6-96231b3b80d8

When folding memory operands in machine instructions be careful to
leave register operands with the same use/def flags as the original
instruction.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11709 91177308-0d34-0410-b5e6-96231b3b80d8