ScheduleDAG; they don't correspond to any actual instructions so they
don't need to be scheduled.

This fixes a bug where the EntryToken was being scheduled multiple
times in some cases, though it ended up not causing any trouble because 
EntryToken doesn't expand into anything. With this fixed the schedulers
reliably schedule the expected number of units, so we can check this
with an assertion.

This requires a tweak to test/CodeGen/X86/loop-hoist.ll because it
ends up getting scheduled differently in a trivial way, though it was
enough to fool the prcontext+grep that the test does.

llvm-svn: 49701

instead of blue to distinguish them from regular dependencies.

llvm-svn: 49696

llvm-svn: 49676

memory intrinsic expansion code.

llvm-svn: 49666

llvm-svn: 49652

much simpler than in LegalizeDAG because calls are
not yet expanded into call sequences: that happens
after type legalization has finished.

llvm-svn: 49634

in its maps.  Add some sanity checks that catch
this kind of thing.  Hopefully these can be
removed one day (once all problems are fixed!)
but for the moment it seems wise to have them in.

llvm-svn: 49612

llvm-svn: 49611

llvm-svn: 49583

on any current target and aren't optimized in DAGCombiner. Instead
of using intermediate nodes, expand the operations, choosing between
simple loads/stores, target-specific code, and library calls,
immediately.

Previously, the code to emit optimized code for these operations
was only used at initial SelectionDAG construction time; now it is
used at all times. This fixes some cases where rep;movs was being
used for small copies where simple loads/stores would be better.

This also cleans up code that checks for alignments less than 4;
let the targets make that decision instead of doing it in
target-independent code. This allows x86 to use rep;movs in
low-alignment cases.

Also, this fixes a bug that resulted in the use of rep;stos for
memsets of 0 with non-constant memory size when the alignment was
at least 4. It's better to use the library in this case, which
can be significantly faster when the size is large.

This also preserves more SourceValue information when memory
intrinsics are lowered into simple loads/stores.

llvm-svn: 49572

llvm-svn: 49524

review feedback from Chris quite a while ago. No functionality
change.

llvm-svn: 49348

by Dan Gohman is fixed.

llvm-svn: 49330

If it cannot be expanded, it will keep the old behaviour and try to shrink the constant.
Part of enhancement for PR2191.

llvm-svn: 49280

before an invoke.  Failure to do this causes references in
the landing pad to variables that were not set.  Fixes
g++.dg/eh/delayslot1.C
g++.dg/eh/fp-regs.C
g++.old-deja/g++.brendan/eh1.C

llvm-svn: 49243

There is no point in creating a long live range defined by an implicit_def. Scheduler now duplicates implicit_def instruction for each of its uses. Therefore, if an implicit_def node has multiple uses, it will become a number of very short live ranges, rather than a long one. This will make coalescer's job easier.

llvm-svn: 49164

llvm-svn: 49124

review feedback.
-enable-eh is still accepted but doesn't do anything.
EH intrinsics use Dwarf EH if the target supports that,
and are handled by LowerInvoke otherwise.
The separation of the EH table and frame move data is,
I think, logically figured out, but either one still
causes full EH info to be generated (not sure how to
split the metadata correctly).
MachineModuleInfo::needsFrameInfo is no longer used and
is removed.

llvm-svn: 49064

llvm-svn: 49046

llvm-svn: 49016

llvm-svn: 49014

llvm-svn: 49013

llvm-svn: 49012

not marked nounwind, or for all functions when -enable-eh
is set, provided the target supports Dwarf EH.

llvm-gcc generates nounwind in the right places; other FEs
will need to do so also.  Given such a FE, -enable-eh should
no longer be needed.

llvm-svn: 49006

llvm-svn: 48994

patch by David Chisnall.

llvm-svn: 48963

llvm-svn: 48947

llvm-svn: 48916

llvm-svn: 48914

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 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

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

llvm-svn: 48800

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: 48755