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

Significantly simplify gep_type_iterator, and make its interface more general/powerful

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

Fix a soon-to-be-missing #include

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

Get all instruction definitions

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

Wow this is out of date.  When we have _real_ code generator documentation,
this should be folded into it.

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

Print basic block boundaries in machine instruction debug output.

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

Link to most recent "LLVM document"

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

Implement Transforms/InstCombine/cast.ll:test13, a case which occurs in a
hot 164.gzip loop.

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

Test that the instruction combiner can fold away a cast in a GEP instruction.
This occurs in 164.gzip, as a result of it declaring arrays extern.

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

The two address pass cannot handle two addr instructions where one incoming
value is a physreg and one is a virtreg.  For this reason, disable copy folding
entirely for physregs.  Also, use the new isMoveInstr target hook which gives us
folding of FP moves as well.

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

Abstract merging of ranges away from number of slots per instruction.

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

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

Use isNull instead of getNode() to test for existence of a node, this is cheaper.

FIX MAJOR BUG, whereby we didn't merge null edges correctly. Correcting this
fixes poolallocation on 175.vpr, and possibly others.

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

Fix an iterator invalidation problem which was causing some nodes to not be
correctly merged over!

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

Use handy method

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

Update comments and add warning

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

`cat' is usually in /bin, not /usr/bin, at least on our systems.

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

When printing a stack trace, demangle it if possible.  Since we are potentially
in a signal handler, allocating memory or doing other unsafe things is bad,
which means we should do it in a different process.

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

Make 'fold' statistic's description the same in both allocators.

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

Instead of cloning the globals for main into the globals graph at the end of
BU propagation, clone the globals into the GG of EACH FUNCTION that finishes
processing!  The GlobalsGraph *must* include all globals and effects from
all functions in the program.  Fixing this makes pool allocation work better
on 175.vpr, but it still ultimately crashes.

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

There is no need to merge the globals graph into the function graphs at the
end of the BU and CBU passes.  The globals will be marked incomplete, so it
doesn't matter if they are missing some info, and merging isn't guaranteed
to bring everything in anyway!

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

Add two missing returns, which caused us to be very pessimistic about the
printf and scanf families!

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

new testcase

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

Added the POVRAY_ROOT to locate Povray.

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

Added an option for configuring Povray.  By default, it should find my local
installation of Povray (and not do anything for people who don't have it).

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

Build an archive for use with Povray.

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

Some more statistics improvements.

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

Disambiguate statistic descriptions.

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

Rename statistic and add another one.

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

Add support for some string functions, the scanf family, and sprintf

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

Add a simple implementation of strncpy

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

New testcase, do not emit a call to __builtin_sqrt, emit a call to sqrt instead!

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

Bug fixed

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

PR244: [llvm-gcc] miscompilation when a function is re-declared as static

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

Add checks for <execinfo.h> and backtrace().

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

Fix crash in debug output.

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

Use backtrace() and include execinfo.h, if they were detected by autoconf.

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

Regenerated using autoheader-2.57.

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

Regenerated using autoconf-2.57.

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

Fix instruction numbering in debug output.

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

Too many changes in one commit:

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.

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

If bugpoint can't match the reference output, at LEAST provide the output
we can get.

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

Wild and passionate uncontrolled goose chases are amusing to watch, but not
very helpful.  Let bugpoint favor being helpful instead of determined.

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

Format a bit more nicely

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

It is totally unacceptable to print out (literally) millions of zeros when
compiling 129.compress... so don't!

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

Add strndup

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

Add a method useful for updating DSA

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

Disable the stack trace thing until we can get an autoconf test for it.  This
call breaks on sparcs

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

Make sure to print a stack trace whenever an error signal is delivered
to the tool.

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

Make sure to print a stack trace whenever an error signal is delivered to
the tool.

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

Make sure to print a stack trace whenever an error signal is delivered to the
tool.

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

Implement new function

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

Add a new function

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

Fix RA::verifyAssignment()

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

Fix problem fusing spill code into instructions: we didn't update the live
variable information to take into account the change of instruction
address.

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

Fix an iterator invalidation problem.  :(

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

ADd a method for when an instruction moves

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

Add method to update livevar when an instruction moves

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

Be a bit more robust.  Explicitly check for a code generator crash.

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

Fix a __LONG__ term annoyance of mine: symbolic registers weren't being printed
by operator<< on MachineInstr's, and looking up what register "24" is all of the
time was greatly annoying.

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

Add a MachineBasicBlock::getParent() method

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

Make ToolExecutionError inherit std::exception and implement its
interface: getMessage() is gone, use what() instead.

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

Print stacktrace in STDERR before dying on a fatal signal. Currently
the symbols are not demangled.

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

Rename reloads/spills to loads/stores.

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

This is needed by assignment verification in linear-scan.

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

Fix the "horribly N^2'd" problem when deleting individual instructions.

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

Document the code generator debugger.

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

document the -march=c option

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

* Predicate the optimizer crash debugger on a function.
* Implement a new code generator crash debugger which uses this predicate

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

Add a new method for use by the code generator crash debugger.

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

Don't crash if there are no passes in the PassesToRun list

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

Add support for just running the code generator

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

Add support for just compiling a program

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

Implement assignment correctness verification.

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

Move unused typedefs in private section. Add method to return interval
given a register.

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

Make the executeProgram method exception safe, not leaving around bytecode
files.

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

Make more stuff public.  Make the instruction argument to
deleteInstructionFromProgram be const

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

make a bunch of methods public

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

A couple of minor cleanups: don't forward declare private classes, put private
classes in an anon namespace

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

Cleanup and simplify manipulation of the program, eliminate the need for so
many 'friends' of bugdriver.

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

Add a stub for debugging code generator crashes

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

indent correctly

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

Don't yell.  BUGPOINT should yell, not the tool runner :)

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

Update comments, if we are running with the CBE, make sure the Interpreter
variable and the CBE variable are pointer equal.

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

Byebye method

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

If there is an error running a tool, include the error message (e.g. assertion failure) in the exception

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

Add a label for the bump when we started counting llvm/projects

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

ctor arguments changed order

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

Catch exception and print message as appropriate

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

When an error occurs executing a tool, we now throw an exception instead
of calling exit(1).

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

Change the order of the arguments to the ctor, allowing us to make the boolean default to true

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