llvm-svn: 48994

The support for remat of instructions with a register operand is hackish, to say the least. Since the register operand guaranteed to be PIC base and that it is already live at all uses, we are making sure it will not be spilled after its uses are rematerialized for both performance and correctness reasons.

llvm-svn: 48976

llvm-svn: 48973

patch by David Chisnall.

llvm-svn: 48963

llvm-svn: 48947

Remove some unneeded code for LiveInterval joining, and fix a bug in the Phi elimination algorithm where we were accidentally reasoning about
the source rather than the destination.

llvm-svn: 48936

llvm-svn: 48916

llvm-svn: 48914

llvm-svn: 48908

In order to handle indexed nodes I had to introduce
a new constructor, and since I was there I factorized
the code in the various load constructors.

llvm-svn: 48894

nodes. This doesn't currently have much impact the generated code, but it
does produce simpler-looking SelectionDAGs, and consequently
simpler-looking ScheduleDAGs, because there are fewer spurious
dependencies.

In particular, CopyValueToVirtualRegister now uses the entry node as the
input chain dependency for new CopyToReg nodes instead of calling getRoot
and depending on the most recent memory reference.

Also, rename UnorderedChains to PendingExports and pull it up from being
a local variable in SelectionDAGISel::BuildSelectionDAG to being a
member variable of SelectionDAGISel, so that it doesn't have to be
passed around to all the places that need it.

llvm-svn: 48893

llvm-svn: 48873

called LimitedSumOfUnscheduledPredsOfSuccs. It terminates the computation
after a given treshold is reached. This new function is always faster, but
brings real wins only on bigger test-cases.

The old function SumOfUnscheduledPredsOfSuccs is left in-place for now and therefore a warning about an unused static function is produced.

llvm-svn: 48872

llvm-svn: 48853

be relocatable.  Describe why .set is needed better.

llvm-svn: 48848

llvm-svn: 48837

Avoid commuting a def MI in order to coalesce a copy instruction away if any use of the same val# is a copy instruction that has already been coalesced.

llvm-svn: 48833

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