(except the part about choosing direction)

llvm-svn: 157437

llvm-svn: 157429

llvm-svn: 157428

The Hazard checker implements in-order contraints, or interlocked
resources. Ready instructions with hazards do not enter the available
queue and are not visible to other heuristics.

The major code change is the addition of SchedBoundary to encapsulate
the state at the top or bottom of the schedule, including both a
pending and available queue.

The scheduler now counts cycles in sync with the hazard checker. These
are minimum cycle counts based on known hazards.

Targets with no itinerary (x86_64) currently remain at cycle 0. To fix
this, we need to provide some maximum issue width for all targets. We
also need to add the concept of expected latency vs. minimum latency.

llvm-svn: 157427

llvm-svn: 157426

llvm-svn: 157425

llvm-svn: 157424

llvm-svn: 157423

llvm-svn: 157422

llvm-svn: 157377

Live ranges with a constrained register class may benefit from splitting
around individual uses. It allows the remaining live range to use a
larger register class where it may allocate. This is like spilling to a
different register class.

This is only attempted on constrained register classes.

<rdar://problem/11438902>

llvm-svn: 157354

llvm-svn: 157349

llvm-svn: 157348

Now that the coalescer keeps live intervals and machine code in sync at
all times, it needs to deal with identity copies differently.

When merging two virtual registers, all identity copies are removed
right away. This means that other identity copies must come from
somewhere else, and they are going to have a value number.

Deal with such copies by merging the value numbers before erasing the
copy instruction. Otherwise, we leave dangling value numbers in the live
interval.

This fixes PR12927.

llvm-svn: 157340

llvm-svn: 157319

Part of rdar://11496790

llvm-svn: 157303

llvm-svn: 157274

llvm-svn: 157273

Also make sure registers aren't erased twice if the dead def mentions
the register twice.

This fixes PR12911.

llvm-svn: 157254

Fix use of an unitialized value in the LegalizeOps expansion for ISD::SUB.  No in-tree targets exercise this path.

Patch by Micah Villmow.

llvm-svn: 157215

llvm-svn: 157195

This helps compile time when the greedy register allocator splits live
ranges in giant functions. Without the bias, we would try to grow
regions through the giant edge bundles, usually to find out that the
region became too big and expensive.

If a live range has many uses in blocks near the giant bundle, the small
negative bias doesn't make a big difference, and we still consider
regions including the giant edge bundle.

Giant edge bundles are usually connected to landing pads or indirect
branches.

llvm-svn: 157174

With physreg joining out of the way, it is easy to recognize the
instructions that need their kill flags cleared while testing for
interference.

This allows us to skip the final scan of all instructions for an 11%
speedup of the coalescer pass.

llvm-svn: 157169

It can be necessary to restrict to a sub-class before accessing
sub-registers.

llvm-svn: 157164

When rewriting operands, make sure the new registers have a compatible
register class.

llvm-svn: 157163

may be RAUW'd by the recursive call to LegalizeOps; instead, retrieve
the other operands when calling UpdateNodeOperands.  Fixes PR12889.

llvm-svn: 157162

Found by valgrind.

llvm-svn: 157160

llvm-svn: 157155

Not all GR64 registers have sub_8bit sub-registers.

llvm-svn: 157150

X86 has 2-addr instructions with different constraints on the tied def
and use operands. One is GR32, one is GR32_NOSP.

llvm-svn: 157149

llvm-svn: 157148

This function adds copies to be erased to DupCopies, avoid also adding
them to DeadCopies.

llvm-svn: 157147

Avoid looking at the operands of a potentially erased instruction.

llvm-svn: 157146

llvm-svn: 157145

llvm-svn: 157144

That struct ought to be a LiveInterval implementation detail.

llvm-svn: 157143

llvm-svn: 157142

llvm-svn: 157137

Dead code elimination during coalescing could cause a virtual register
to be split into connected components. The following rewriting would be
confused about the already joined copies present in the code, but
without a corresponding value number in the live range.

Erase all joined copies instantly when joining intervals such that the
MI and LiveInterval representations are always in sync.

llvm-svn: 157135

Dead code and joined copies are now eliminated on the fly, and there is
no need for a post pass.

This makes the coalescer work like other modern register allocator
passes: Code is changed on the fly, there is no pending list of changes
to be committed.

llvm-svn: 157132