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

buildbot failure.

llvm-svn: 95103

as output.  Needed for (functional) correctness in inline asm,
and should be generally beneficial.  7361612.

llvm-svn: 95050

llvm-svn: 94866

llvm-svn: 92595

in local register allocator.  If a reg-reg copy has a phys reg
input and a virt reg output, and this is the last use of the phys
reg, assign the phys reg to the virt reg.  If a reg-reg copy has
a phys reg output and we need to reload its spilled input, reload
it directly into the phys reg than passing it through another reg.

Following 76208, there is sometimes no dependency between the def of
a phys reg and its use; this creates a window where that phys reg
can be used for spilling (this is true in linear scan also).  This
is bad and needs to be fixed a better way, although 76208 works too
well in practice to be reverted.  However, there should normally be
no spilling within inline asm blocks.  The patch here goes a long way
towards making this actually be true.

llvm-svn: 91485

Add a bool flag to StackObjects telling whether they reference spill
slots.  The AsmPrinter will use this information to determine whether to
print a spill/reload comment.

Remove default argument values.  It's too easy to pass a wrong argument
value when multiple arguments have default values.  Make everything
explicit to trap bugs early.

Update all targets to adhere to the new interfaces..

llvm-svn: 87022

VISIBILITY_HIDDEN removal.

llvm-svn: 85043

Chris claims we should never have visibility_hidden inside any .cpp file but
that's still not true even after this commit.

llvm-svn: 85042

Distinquish stack slots from other stack objects. They (and fixed objects) get FixedStack PseudoSourceValues.

llvm-svn: 84326

llvm-svn: 79758

llvm-svn: 77754

 - Some clients which used DOUT have moved to DEBUG. We are deprecating the
   "magic" DOUT behavior which avoided calling printing functions when the
   statement was disabled. In addition to being unnecessary magic, it had the
   downside of leaving code in -Asserts builds, and of hiding potentially
   unnecessary computations.

llvm-svn: 77019

and abort()/exit() -> llvm_report_error().

llvm-svn: 75363

scavenger gets confused about register liveness if it doesn't see them.
I'm not thrilled with this solution, but it only comes up when there are dead
copies in the code, which is something that hopefully doesn't happen much.

Here is what happens in pr4100: As shown in the following excerpt from the
debug output of llc, the source of a move gets reloaded from the stack,
inserting a new load instruction before the move.  Since that source operand
is a kill, the physical register is free to be reused for the destination
of the move.  The move ends up being a no-op, copying R3 to R3, so it is
deleted.  But, it leaves behind the load to reload %reg1028 into R3, and
that load is not updated to show that it's destination operand (R3) is dead.
The scavenger gets confused by that load because it thinks that R3 is live.

Starting RegAlloc of: %reg1025<def,dead> = MOVr %reg1028<kill>, 14, %reg0, %reg0
  Regs have values: 
  Reloading %reg1028 into R3
  Last use of R3[%reg1028], removing it from live set
  Assigning R3 to %reg1025
  Register R3 [%reg1025] is never used, removing it from live set

Alternative solutions might be either marking the load as dead, or zapping
the load along with the no-op copy.  I couldn't see an easy way to do
either of those, though.

llvm-svn: 71196

llvm-svn: 71180

llvm-svn: 71179

register destinations that are tied to source operands.  The
TargetInstrDescr::findTiedToSrcOperand method silently fails for inline
assembly.  The existing MachineInstr::isRegReDefinedByTwoAddr was very
close to doing what is needed, so this revision makes a few changes to
that method and also renames it to isRegTiedToUseOperand (for consistency
with the very similar isRegTiedToDefOperand and because it handles both
two-address instructions and inline assembly with tied registers).

llvm-svn: 68714

llvm-svn: 67335

Local register allocator shouldn't assume only the entry and landing pad basic blocks have live-ins.

llvm-svn: 63323