precisely track pressure on a selection DAG, but we can at least keep
it balanced. This design accounts for various interesting aspects of
selection DAGS: register and subregister copies, glued nodes, dead
nodes, unused registers, etc.

Added SUnit::NumRegDefsLeft and ScheduleDAGSDNodes::RegDefIter.

Note: I disabled PrescheduleNodesWithMultipleUses when register
pressure is enabled, based on no evidence other than I don't think it
makes sense to have both enabled.

llvm-svn: 124853

Fix a few cases where the scheduler is not checking for phys reg copies. The scheduling node may have a NULL DAG node, yuck.

llvm-svn: 122544

DAG scheduling during isel. Most new functionality is currently
guarded by -enable-sched-cycles and -enable-sched-hazard.

Added InstrItineraryData::IssueWidth field, currently derived from
ARM itineraries, but could be initialized differently on other targets.

Added ScheduleHazardRecognizer::MaxLookAhead to indicate whether it is
active, and if so how many cycles of state it holds.

Added SchedulingPriorityQueue::HasReadyFilter to allowing gating entry
into the scheduler's available queue.

ScoreboardHazardRecognizer now accesses the ScheduleDAG in order to
get information about it's SUnits, provides RecedeCycle for bottom-up
scheduling, correctly computes scoreboard depth, tracks IssueCount, and
considers potential stall cycles when checking for hazards.

ScheduleDAGRRList now models machine cycles and hazards (under
flags). It tracks MinAvailableCycle, drives the hazard recognizer and
priority queue's ready filter, manages a new PendingQueue, properly
accounts for stall cycles, etc.

llvm-svn: 122541

llvm-svn: 122208

llvm-svn: 107244

llvm-svn: 103936

llvm-svn: 101143

llvm-svn: 92585

Remove some old experimental code that is no longer needed. Remove additional, speculative scheduling pass as its cost did not translate into significant performance improvement. Minor tweaks.

llvm-svn: 89471

llvm-svn: 87015

Do a scheduling pass ignoring anti-dependencies to identify candidate registers that should be renamed.

llvm-svn: 85939

basic blocks that are so long that their size overflows a short.

Also assert that overflow does not happen in the future, as requested by Evan.

This fixes PR4401.

llvm-svn: 83159

llvm-svn: 79760

llvm-svn: 78687

llvm-svn: 76963

instruction index across each part. Instruction indices are used
to make live range queries, and live ranges can extend beyond
scheduling region boundaries.

Refactor the ScheduleDAGSDNodes class some more so that it
doesn't have to worry about this additional information.

llvm-svn: 64288

an index. This code is on the hot-path because the current
way SDep edges are uniqued has quadratic complexity.

llvm-svn: 64262

scheduling, and generalize is so that preserves state across
scheduling regions. This fixes incorrect live-range information around
terminators and labels, which are effective region boundaries.

In place of looking for terminators to anchor inter-block dependencies,
introduce special entry and exit scheduling units for this purpose.

llvm-svn: 64254

and every other instruction in their blocks to keep the terminator
instructions at the end, teach the post-RA scheduler how to operate
on ranges of instructions, and exclude terminators from the range
of instructions that get scheduled.

Also, exclude mid-block labels, such as EH_LABEL instructions, and
schedule code before them separately from code after them. This
fixes problems with the post-RA scheduler moving code past
EH_LABELs.

llvm-svn: 62366

to support MachineInstr-based scheduling in addition to
SDNode-based scheduling.

llvm-svn: 62284

and into the ScheduleDAGInstrs class, so that they don't get
destructed and re-constructed for each block. This fixes a
compile-time hot spot in the post-pass scheduler.

To help facilitate this, tidy and do some minor reorganization
in the scheduler constructor functions.

llvm-svn: 62275

been modified, to avoid trouble in the (unlikely) scenario that
D is a reference to an element in one of those arrays.

llvm-svn: 62173

with latency 0, since it doesn't affect the depth or height.

llvm-svn: 61762

llvm-svn: 61371

up on a profile.

llvm-svn: 61344

llvm-svn: 61277

and setDepthDirty(), respectively. This fixes PR3241.

llvm-svn: 61276

Depth and Height members directly, as they may not be
current.

llvm-svn: 61121

computation code. Also, avoid adding output-depenency edges when both
defs are dead, which frequently happens with EFLAGS defs.

Compute Depth and Height lazily, and always in terms of edge latency
values. For the schedulers that don't care about latency, edge latencies
are set to 1.

Eliminate Cycle and CycleBound, and LatencyPriorityQueue's Latencies array.
These are all subsumed by the Depth and Height fields.

llvm-svn: 61073

llvm-svn: 61067

The Cost field is removed. It was only being used in a very limited way,
to indicate when the scheduler should attempt to protect a live register,
and it isn't really needed to do that. If we ever want the scheduler to
start inserting copies in non-prohibitive situations, we'll have to
rethink some things anyway.

A Latency field is added. Instead of giving each node a single
fixed latency, each edge can have its own latency. This will eventually
be used to model various micro-architecture properties more accurately.

The PointerIntPair class and an internal union are now used, which
reduce the overall size.

llvm-svn: 60806

llvm-svn: 60769

introduce any new spilling; it just uses unused registers.

Refactor the SUnit topological sort code out of the RRList scheduler and
make use of it to help with the post-pass scheduler.

llvm-svn: 59999

less mysterious.

llvm-svn: 59782

llvm-svn: 59692

extend it a bit, and make use of it in all schedulers, to
ensure consistent checking.

llvm-svn: 59689

is currently off by default, and can be enabled with
-disable-post-RA-scheduler=false.

This doesn't have a significant impact on most code yet because it doesn't
yet do anything to address anti-dependencies and it doesn't attempt to
disambiguate memory references. Also, several popular targets
don't have pipeline descriptions yet.

The majority of the changes here are splitting the SelectionDAG-specific
code out of ScheduleDAG, so that ScheduleDAG can be moved to
libLLVMCodeGen.a. The interface between ScheduleDAG-using code and
the rest of the scheduling code is somewhat rough and will evolve.

llvm-svn: 59676