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

llvm-svn: 122537

llvm-svn: 122509

llvm-svn: 122507

llvm-svn: 122491

Converted LiveRegCycles to LiveRegGens. It's easier to work with and allows multiple nodes per cycle.

llvm-svn: 122474

llvm-svn: 122473

In the bottom-up selection DAG scheduling, handle two-address
instructions that read/write unspillable registers. Treat
the entire chain of two-address nodes as a single live range.

llvm-svn: 122472

new gcc warning that complains on self-assignments and
self-initializations.

llvm-svn: 122458

DAGCombine add (sext i1), X into sub X, (zext i1) if sext from i1 is illegal.  The latter usually compiles into smaller code.

example code:
unsigned foo(unsigned x, unsigned y) {
  if (x != 0) y--;
  return y;
}

before:
  _foo:                           ## @foo
    cmpl  $1, 4(%esp)             ## encoding: [0x83,0x7c,0x24,0x04,0x01]
    sbbl  %eax, %eax              ## encoding: [0x19,0xc0]
    notl  %eax                    ## encoding: [0xf7,0xd0]
    addl  8(%esp), %eax           ## encoding: [0x03,0x44,0x24,0x08]
    ret                           ## encoding: [0xc3]

after:
  _foo:                           ## @foo
    cmpl  $1, 4(%esp)             ## encoding: [0x83,0x7c,0x24,0x04,0x01]
    movl  8(%esp), %eax           ## encoding: [0x8b,0x44,0x24,0x08]
    adcl  $-1, %eax               ## encoding: [0x83,0xd0,0xff]
    ret                           ## encoding: [0xc3]

llvm-svn: 122455

pick the victim with the lowest total spill weight.

llvm-svn: 122445

llvm-svn: 122444

loads properly.  We miscompiled the testcase into:

_test:                                  ## @test
	movl	$128, (%rdi)
	movzbl	1(%rdi), %eax
	ret

Now we get a proper:

_test:                                  ## @test
	movl	$128, (%rdi)
	movsbl	(%rdi), %eax
	movzbl	%ah, %eax
	ret

This fixes PR8757.

llvm-svn: 122392

unhanded cases faster and simplify code.

llvm-svn: 122391

llvm-svn: 122389

the same physical register. Simplifies the fix from the previous
checkin r122211.

llvm-svn: 122370

llvm-svn: 122368

the shift type was needed one place, the shift count
type another.  The transform in 123555 had the same
problem.

llvm-svn: 122366

llvm-svn: 122360

llvm-svn: 122355

count operand.  These should be the same but apparently are
not always, and this is cleaner anyway.  This improves the
code in an existing test.

llvm-svn: 122354

llvm-svn: 122353

llvm-svn: 122349

llvm-svn: 122345

llvm-svn: 122342

of the problems with my last attempt were in the updating of LiveIntervals
rather than the coalescing itself. Therefore, I decided to get that right first
by essentially reimplementing the existing PHIElimination using LiveIntervals.

It works correctly, with only a few tests failing (which may not be legitimate
failures) and no new verifier failures (at least as far as I can tell, I didn't
count the number per file).

llvm-svn: 122321

something that just glues two nodes together, even if it is
sometimes used for flags.

llvm-svn: 122310

they are just as useless, but at least a bit more gramatical

llvm-svn: 122305

Edge bundles is an annotation on the CFG that turns it into a bipartite directed
graph where each basic block is connected to an outgoing and an ingoing bundle.
These bundles are useful for identifying regions of the CFG for live range
splitting.

llvm-svn: 122301

llvm-svn: 122296

llvm-svn: 122259

out-edges. Fixes PR8824.

llvm-svn: 122228

begin at DEF slots. Fixes the second half of PR8813.

llvm-svn: 122225

llvm-svn: 122224

ARM (and other 32-bit-only) targets support for i8 and i16 overflow 
multiplies.  The generated code isn't great, but this at least fixes
CodeGen/Generic/overflow.ll when running on ARM hosts.

llvm-svn: 122221

the register; it may be a dead def instead. Fixes PR8820.

llvm-svn: 122218

Imagine we see:

EFLAGS = inst1
EFLAGS = inst2 FLAGS
gpr = inst3 EFLAGS

Previously, we would refuse to schedule inst2 because it clobbers
the EFLAGS of the predecessor.  However, it also uses the EFLAGS
of the predecessor, so it is safe to emit.  SDep edges ensure that
the right order happens already anyway.

This fixes 2 testsuite crashes with the X86 patch I'm going to
commit next.

llvm-svn: 122211

llvm-svn: 122209

llvm-svn: 122208