Added a separate class (PBQPBuilder) for PBQP Problem construction. This class can be extended to support custom constraints.

For now the allocator still uses the old (internal) construction mechanism by default. This will be phased out soon assuming 
no issues with the builder system come up.

To invoke the new construction mechanism just pass '-regalloc=pbqp -pbqp-builder' to llc. To provide custom constraints a
Target just needs to extend PBQPBuilder and pass an instance of their derived builder to the RegAllocPBQP constructor.

llvm-svn: 114272

Added support for register allocators to record which intervals are spill intervals, and where the uses and defs of the original intervals were in the original code.

Spill intervals can be hidden using the "-rmf-intervals=virt-nospills*" option.

llvm-svn: 112811

llvm-svn: 112742

llvm-svn: 110460

llvm-svn: 110410

ID member as the sole unique type identifier.  Clean up APIs related to this change.

llvm-svn: 110396

Updated renderer to use allocation information from VirtRegMap (if
available) to render spilled intervals differently.

llvm-svn: 108815

pressure estimates and liveness alongside.

Still experimental.

llvm-svn: 108698

LoopSplitter be run prior to register allocation.

Entirely for testing purposes at the moment.

llvm-svn: 108634

any command line paramater changed the register allocation produced by
PBQP.

Turns out variety is not the spice of life.

Fixed some comparators, added others. All good now.

llvm-svn: 108613

TII::isMoveInstr is going tobe completely removed.

llvm-svn: 108507

physical register can be allocated in the class of the virtual are sufficient.

I think that the test for virtual registers is more strict than it needs to be,
it should be possible to coalesce two virtual registers the class of one
is a subclass of the other.

llvm-svn: 108118

patch by Evzen Muller!

llvm-svn: 103876

out by Russell Wallace.

llvm-svn: 96579

Removed an early out which was causing the PBQP allocator to not compute live-in sets or run the rewriter.

llvm-svn: 96450

Previously spill registers, whose def indexes are not defined, would sometimes be improperly marked as coalescable with conflicting registers. The new findCoalesces routine conservatively assumes that any register with at least one undefined def is not coalescable with any register it interferes with.

llvm-svn: 95636

* Fixed a reduction bug which occasionally led to infinite-cost (invalid)
  register allocation solutions despite the existence finite-cost solutions.
* Significantly reduced memory usage (>50% reduction).
* Simplified a lot of the solver code.

llvm-svn: 94514

llvm-svn: 92586

Moved spill weight calculation out of SimpleRegisterCoalescing and into its own pass: CalculateSpillWeights.

llvm-svn: 91273

Added an assert to the PBQP allocator to catch infinite cost solutions which might otherwise lead to miscompilations.

llvm-svn: 88829

This introduces a new pass, SlotIndexes, which is responsible for numbering
instructions for register allocation (and other clients). SlotIndexes numbering
is designed to match the existing scheme, so this patch should not cause any
changes in the generated code.

For consistency, and to avoid naming confusion, LiveIndex has been renamed
SlotIndex.

The processImplicitDefs method of the LiveIntervals analysis has been moved
into its own pass so that it can be run prior to SlotIndexes. This was
necessary to match the existing numbering scheme.

llvm-svn: 85979

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

llvm-svn: 83254

llvm-svn: 82355

about by icc (#593, partial).  Patch by Erick Tryzelaar.

llvm-svn: 81115

a new class, MachineInstrIndex, which hides arithmetic details from
most clients. This is a step towards allowing the register allocator
to update/insert code during allocation.

llvm-svn: 81040

Fixed a test that ensures the LocalRewriter does not attempt to
avoid reloads by reusing clobbered registers.

This was causing issues in 256.bzip2 when compiled with PIC for
a while (starting at r78217), though the problem has since been masked. 

llvm-svn: 80872

llvm-svn: 79564

llvm-svn: 79397

llvm-svn: 79378

llvm-svn: 78840

llvm-svn: 78667

llvm-svn: 78664

Modified VNInfo. The "copy" member is now a union which holds the copy for a register interval, or the defining register for a stack interval. Access is via getCopy/setCopy and getReg/setReg.

llvm-svn: 78620

llvm-svn: 78601

llvm-svn: 78447

New C++ PBQP solver. Currently about as fast (read _slow_) as the old C based solver, but I'll be working to improve that. The PBQP allocator has been updated to use the new solver.

llvm-svn: 78354

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

llvm-svn: 73634