a condition's grouping. Every other use of Allocatable.test(Hint) groups it the
same way as it is indented, so move the parentheses to agree with that
grouping.

llvm-svn: 103869

When working top-down in a basic block, substituting physregs for virtregs, the use-def chains are kept up to date. That means we can recognize a virtreg kill by the use-def chain becoming empty.

This makes the fast allocator independent of incoming kill flags.

llvm-svn: 103866

llvm-svn: 103831

llvm-svn: 103828

llvm-svn: 103823

llvm-svn: 103821

llvm-svn: 103820

- Kill is implicit when use and def registers are identical.
- Only virtual registers can differ.

Add a -verify-fast-regalloc to run the verifier before the fast allocator.

llvm-svn: 103797

This adds extra security against using clobbered physregs, and it adds kill
markers to physreg uses.

llvm-svn: 103784

llvm-svn: 103764

llvm-svn: 103748

This loop is quadratic in the capacity for a DenseMap:

  while(!map.empty())
    map.erase(map.begin());

Instead we now do a normal begin() - end() iteration followed by map.clear().
That also has the nice sideeffect of shrinking the map capacity on demand.

llvm-svn: 103747

llvm-svn: 103739

This causes way more identity copies to be generated, ripe for coalescing.

llvm-svn: 103686

llvm-svn: 103685

The X86 floating point stack pass and others depend on good kill flags.

llvm-svn: 103635

llvm-svn: 103530

llvm-svn: 103528

llvm-svn: 103522

This allows us to add accurate kill markers, something the scavenger likes.
Add some more tests from ARM that needed this.

llvm-svn: 103521

closure after allocating all blocks.

Add a few more test cases for -regalloc=fast.

llvm-svn: 103500

Sorry for the big change. The path leading up to this patch had some TableGen
changes that I didn't want to commit before I knew they were useful. They
weren't, and this version does not need them.

The fast register allocator now does no liveness calculations. Instead it relies
on kill flags provided by isel. (Currently those kill flags are also ignored due
to isel bugs). The allocation algorithm is supposed to work with any subset of
valid kill flags. More kill flags simply means fewer spills inserted.

Registers are allocated from a working set that contains no aliases. That means
most allocations can be done directly without expensive alias checks. When the
working set runs out of registers we do the full alias check to find new free
registers.

llvm-svn: 103488

llvm-svn: 103450

llvm-svn: 103193

This actually makes everything slower, but the plan is to have isel add <kill>
flags the way it is already adding <dead> flags. Then LiveVariables can be
removed again.

When ignoring the time spent in LiveVariables, -regalloc=fast is now twice as
fast as -regalloc=local.

llvm-svn: 102034

So far this is just a clone of -regalloc=local that has been lobotomized to run
25% faster. It drops the least-recently-used calculations, and is just plain
stupid when it runs out of registers.

The plan is to make this go even faster for -O0 by taking advantage of the short
live intervals in unoptimized code. It should not be necessary to calculate
liveness when most virtual registers are killed 2-3 instructions after they are
born.

llvm-svn: 102006

Revert "Use a simpler data structure to calculate the least recently used register in RegAllocLocal."

This reverts commit 101392. It broke a buildbot.

llvm-svn: 101595

This makes the local register allocator about 20% faster.

llvm-svn: 101574

llvm-svn: 100709

llvm-svn: 99989

llvm-svn: 98838

llvm-svn: 98604

"used outside of the block". If the block ends in a return, then it won't be
used outside of it.

llvm-svn: 98599

at older buildbot messages, I see the failure predates
this patch.

llvm-svn: 96307

but it's harder to believe it's the other candidate,
so reverting.  Temporarily I hope.

llvm-svn: 96303

llvm-svn: 96294

llvm-svn: 96207

llvm-svn: 95730

into TargetOpcodes.h.  #include the new TargetOpcodes.h
into MachineInstr.  Add new inline accessors (like isPHI())
to MachineInstr, and start using them throughout the 
codebase.

llvm-svn: 95687

llvm-svn: 95183