Creates a configurable regalloc pipeline.

Ensure specific llc options do what they say and nothing more: -reglloc=... has no effect other than selecting the allocator pass itself. This patch introduces a new umbrella flag, "-optimize-regalloc", to enable/disable the optimizing regalloc "superpass". This allows for example testing coalscing and scheduling under -O0 or vice-versa.

When a CodeGen pass requires the MachineFunction to have a particular property, we need to explicitly define that property so it can be directly queried rather than naming a specific Pass. For example, to check for SSA, use MRI->isSSA, not addRequired<PHIElimination>.

CodeGen transformation passes are never "required" as an analysis

ProcessImplicitDefs does not require LiveVariables.

We have a plan to massively simplify some of the early passes within the regalloc superpass.

llvm-svn: 150226

llvm-svn: 150225

llvm-svn: 149816

The register allocators don't currently support adding reserved
registers while they are running.  Extend the MRI API to keep track of
the set of reserved registers when register allocation started.

Target hooks like hasFP() and needsStackRealignment() can look at this
set to avoid reserving more registers during register allocation.

llvm-svn: 147577

llvm-svn: 145897

llvm-svn: 145893

The very complicated VirtRegRewriter is going away.

llvm-svn: 144479

It is worth noting that the old spiller would split live ranges around
basic blocks. The new spiller doesn't do that.

PBQP should do its own live range splitting with
SplitEditor::splitSingleBlock() if desired.  See
RAGreedy::tryBlockSplit().

llvm-svn: 144476

A public interface is no longer needed since RegisterCoalescer is not an
analysis any more.

llvm-svn: 137082

remove the analysis group.

llvm-svn: 133899

llvm-svn: 133895

Add a hook for PBQP clients to run a custom pre-alloc pass to run prior to PBQP allocation. Patch by Arnaud Allard de Grandmaison.

llvm-svn: 133249

I think PBQP could use RegisterClassInfo, but it didn't fit neatly with
the external interfaces that PBQP uses, so I'll leave that to Lang.

llvm-svn: 133186

llvm-svn: 127388

llvm-svn: 118883

Get rid of static constructors for pass registration.  Instead, every pass exposes an initializeMyPassFunction(), which
must be called in the pass's constructor.  This function uses static dependency declarations to recursively initialize
the pass's dependencies.

Clients that only create passes through the createFooPass() APIs will require no changes.  Clients that want to use the
CommandLine options for passes will need to manually call the appropriate initialization functions in PassInitialization.h
before parsing commandline arguments.

I have tested this with all standard configurations of clang and llvm-gcc on Darwin.  It is possible that there are problems
with the static dependencies that will only be visible with non-standard options.  If you encounter any crash in pass
registration/creation, please send the testcase to me directly.

llvm-svn: 116820

Removed the older style (in-allocator) problem construction system from the PBQP allocator. Problem construction is now done exclusively with the new builders.

llvm-svn: 115502

Removed VNInfo::isDefAccurate(). Def "accuracy" can be checked by testing whether LiveIntervals::getInstructionFromIndex(def) returns NULL.

llvm-svn: 114791

Moved the PBQP allocator class out of the header and back in to the cpp file to hide the gory details.
Allocator instances can now be created by calling createPBQPRegisterAllocator.

Tidied up use of CoalescerPair as per Jakob's suggestions.

Made the new PBQPBuilder based construction process the default. The internal construction process
remains in-place and available via -pbqp-builder=false for now. It will be removed shortly if the new
process doesn't cause any regressions.

llvm-svn: 114626

llvm-svn: 114431

Added an additional PBQP problem builder which adds coalescing costs (both between pairs of virtuals, and between virtuals and physicals).

llvm-svn: 114429

llvm-svn: 114284

llvm-svn: 114273

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