Oops - LiveIntervalUnion.cpp file does use std::find. Moving STL header include to LiveIntervalUnion.cpp file.

llvm-svn: 147089

This is possible now that we now longer provide an interface to iterate
the interference overlaps.

llvm-svn: 137397

The Query class now holds two iterators instead of an InterferenceResult
instance. The iterators are used as bookmarks for repeated
collectInterferingVRegs calls.

llvm-svn: 137380

collectInterferingVRegs will be the primary function for interference
checks.

llvm-svn: 137354

The InterferenceResult iterator turned out to be less important than we
thought it would be.  LiveIntervalUnion clients want higher level
information, like the list of interfering virtual registers.

llvm-svn: 137346

RAGreedy::tryAssign will now evict interference from the preferred
register even when another register is free.

To support this, add the EvictionCost struct that counts how many hints
are broken by an eviction. We don't want to break one hint just to
satisfy another.

Rename canEvict to shouldEvict, and add the first bit of eviction policy
that doesn't depend on spill weights: Always make room in the preferred
register as long as the evictees can be split and aren't already
assigned to their preferred register.

Also make the CSR avoidance more accurate. When looking for a cheaper
register it is OK to use a new volatile register. Only CSR aliases that
have never been used before should be avoided.

llvm-svn: 134735

weight limit has been exceeded.

llvm-svn: 129305

This particularly helps with the initial transfer of fixed intervals.

llvm-svn: 129277

The tag is updated whenever the live interval union is changed, and it is tested
before using cached information.

llvm-svn: 125224

Print virtual registers numbered from 0 instead of the arbitrary
FirstVirtualRegister. The first virtual register is printed as %vreg0.
TRI::NoRegister is printed as %noreg.

llvm-svn: 123107

interference.

llvm-svn: 122108

This is a three-way interval list intersection between a virtual register, a
live interval union, and a loop. It will be used to identify interference-free
loops for live range splitting.

llvm-svn: 122034

live range splitting around loops guided by register pressure.

So far, trySplit() simply prints a lot of debug output.

llvm-svn: 121918

llvm-svn: 121783

LiveIntervalUnions.

llvm-svn: 121781

llvm-svn: 121410

heuristic to reshuffle register assignments when we can't find an
available reg.

llvm-svn: 121388

references instead.

Similarly, IntervalMap::begin() is almost as expensive as find(), so use find(x)
instead of begin().advanceTo(x);

This makes RegAllocBasic run another 5% faster.

llvm-svn: 121344

llvm-svn: 121319

This speeds up RegAllocBasic by 20%, not counting releaseMemory which becomes
way faster.

llvm-svn: 121201

llvm-svn: 120504

in favor of the widespread llvm style. Capitalize variables and add
newlines for visual parsing. Rename variables for readability.
And other cleanup.

llvm-svn: 120490

benchmarks hitting an assertion.
Adds LiveIntervalUnion::collectInterferingVRegs.
Fixes "late spilling" by checking for any unspillable live vregs among
all physReg aliases.

llvm-svn: 118701

(retry now that the windows build is green)

llvm-svn: 118630

llvm-svn: 118613

llvm-svn: 118604

handle cases in which a register is unavailable for spill code.
Adds LiveIntervalUnion::extract. While processing interferences on a
live virtual register, reuses the same Query object for each
physcial reg.

llvm-svn: 118423

them, but hopefully we won't. And this is not the right data structure
to do it anyway.

llvm-svn: 117412

llvm-svn: 117384

was found by a GCC warning. ;]

llvm-svn: 117199

framework. It's purpose is not to improve register allocation per se,
but to make it easier to develop powerful live range splitting. I call
it the basic allocator because it is as simple as a global allocator
can be but provides the building blocks for sophisticated register
allocation with live range splitting. 

A minimal implementation is provided that trivially spills whenever it
runs out of registers. I'm checking in now to get high-level design
and style feedback. I've only done minimal testing. The next step is
implementing a "greedy" allocation algorithm that does some register
reassignment and makes better splitting decisions.

llvm-svn: 117174