LLVM Value/Use does and MachineRegisterInfo/MachineOperand does.
This allows constant time for all uses list maintenance operations.

The idea was suggested by Chris. Reviewed by Evan and Dan.
Patch is tested and approved by Dan.

On normal use-cases compilation speed is not affected. On very big basic
blocks there are compilation speedups in the range of 15-20% or even better. 

llvm-svn: 48822

llvm-svn: 48819

This fixes Bugzilla #1835 (http://llvm.org/bugs/show_bug.cgi?id=1835).
This patched is reviewed by Tanya and Dan. Dan tested and approved it.

The reason for the bad performance of the old algorithm is that it is very naive and scans every
time all nodes of the DAG in the worst case.

This patch introduces  a new algorithm based on the paper "Online algorithms
for maintaining the topological order of a directed acyclic graph" by
David J.Pearce and Paul H.J.Kelly. This is the MNR algorithm. It has a
linear time worst-case and performs much better in most situations.

The paper can be found here:
http://fano.ics.uci.edu/cites/Document/Online-algorithms-for-maintaining-the-topological-order-of-a-directed-acyclic-graph.html

The main idea of the new algorithm is to compute the topological ordering of the SNodes in the
DAG and to maintain it even after DAG modifications. The topological ordering allows for very fast 
node reachability checks. 

Tests on very big  input files with tens of thousands of instructions in a BB indicate huge 
speed-ups (up to 10x compilation time improvement) compared to the old version.

llvm-svn: 48817

llvm-svn: 48811

llvm-svn: 48803

llvm-svn: 48802

marked read-write. Use const so that they can be allocated in a
read-only segment.

llvm-svn: 48800

llvm-svn: 48797

llvm-svn: 48794

Handle a special case xor undef, undef -> 0. Technically this should be transformed to undef. But this is such a common idiom (misuse) we are going to handle it.

llvm-svn: 48792

llvm-svn: 48779

llvm-svn: 48759

llvm-svn: 48755

If the coalescer commuted a def MI to allow coalescing, it can changed a previously coalesced copy into an non-identity copy.

llvm-svn: 48752

llvm-svn: 48751

llvm-svn: 48739

llvm-svn: 48726

With this pass, StrongPHIElim can compile very simple testcases correctly.  There's still a ways
to go before it's ready for prime time, though.

llvm-svn: 48719

llvm-svn: 48683

llvm-svn: 48673

adding <map> to many files that actually do need it.

llvm-svn: 48667

llvm-svn: 48664

llvm-svn: 48653

flags.  This is needed by the new legalize types
infrastructure which wants to expand the 64 bit
constants previously used to hold the flags on
32 bit machines.  There are two functional changes:
(1) in LowerArguments, if a parameter has the zext
attribute set then that is marked in the flags;
before it was being ignored; (2) PPC had some bogus
code for handling two word arguments when using the
ELF 32 ABI, which was hard to convert because of
the bogusness.  As suggested by the original author
(Nicolas Geoffray), I've disabled it for the moment.
Tested with "make check" and the Ada ACATS testsuite.

llvm-svn: 48640

llvm-svn: 48580

llvm-svn: 48578

llvm-svn: 48577

Fix X86's isTruncateFree to not claim that truncate to i1 is free. This fixes Bill's testcase that failed for r48491.

llvm-svn: 48542

llvm-svn: 48526

1. If part of a register is re-defined, an implicit kill and an implicit def are added to denote read / mod / write. However, this should only be necessary if the register is actually read later. This is a performance issue.
2. If a sub-register is being defined, and it doesn't have a previous use, do not add a implicit kill to the last use of a super-register:
   = EAX, AX<imp-use,kill>
...
AX =
In this case, EAX is live but AX is killed, this is wrong and will cause the coalescer to do bad things.

llvm-svn: 48521

llvm-svn: 48510

llvm-svn: 48493

Target independent DAG transform to use truncate for field extraction + sign extend on targets where this is profitable. Passes nightly on x86-64.

llvm-svn: 48491

Rewrite code that propagate isDead information after a dead copy is coalesced. This remove some ugly spaghetti code and fixed a number of subtle bugs.

llvm-svn: 48490

the coalescer.  This doesn't really work, but gets us farther than
before.

llvm-svn: 48446

Make insert_subreg a two-address instruction, vastly simplifying LowerSubregs pass. Add a new TII, subreg_to_reg, which is like insert_subreg except that it takes an immediate implicit value to insert into rather than a register.

llvm-svn: 48412

llvm-svn: 48381

Replace all target specific implicit def instructions with a target independent one: TargetInstrInfo::IMPLICIT_DEF.

llvm-svn: 48380

table for nounwind calls.

llvm-svn: 48373

Fix PR2138. Apparently any modification to a std::multimap (including remove entries for a different key) can invalidate multimap iterators.

llvm-svn: 48371