llvm-svn: 192398

Previously LiveInterval has been used, but having a spill weight and
register number is unnecessary for a register unit.

llvm-svn: 192397

This makes the API a bit more natural to use and makes it easier to make
LiveRanges implementation details private.

llvm-svn: 192394

The Segment struct contains a single interval; multiple instances of this struct
are used to construct a live range, but the struct is not a live range by
itself.

llvm-svn: 192392

A DBG_VALUE is register-indirect iff the first operand is a register
_and_ the second operand is an immediate.

llvm-svn: 190821

When new virtual registers are created during splitting/spilling, defer
creation of the live interval until we need to use the live interval.

Along with the recent commits to notify LiveRangeEdit when new virtual
registers are created, this makes it possible for functions like
TargetInstrInfo::loadRegFromStackSlot() and
TargetInstrInfo::storeRegToStackSlot() to create multiple virtual
registers as part of the process of generating loads/stores for
different register classes, and then have the live intervals for those
new registers computed when they are needed.

llvm-svn: 188437

llvm-svn: 186014

llvm-svn: 184574

The main advantages here are way better heuristics, taking into account not
just loop depth but also __builtin_expect and other static heuristics and will
eventually learn how to use profile info. Most of the work in this patch is
pushing the MachineBlockFrequencyInfo analysis into the right places.

This is good for a 5% speedup on zlib's deflate (x86_64), there were some very
unfortunate spilling decisions in its hottest loop in longest_match(). Other
benchmarks I tried were mostly neutral.

This changes register allocation in subtle ways, update the tests for it.
2012-02-20-MachineCPBug.ll was deleted as it's very fragile and the instruction
it looked for was gone already (but the FileCheck pattern picked up unrelated
stuff).

llvm-svn: 184105

Rather than using the full power of target-specific addressing modes in
DBG_VALUEs with Frame Indicies, simply use Frame Index + Offset. This
reduces the complexity of debug info handling down to two
representations of values (reg+offset and frame index+offset) rather
than three or four.

Ideally we could ensure that frame indicies had been eliminated by the
time we reached an assembly or dwarf generation, but I haven't spent the
time to figure out where the FIs are leaking through into that & whether
there's a good place to convert them. Some FI+offset=>reg+offset
conversion is done (see PrologEpilogInserter, for example) which is
necessary for some SelectionDAG assumptions about registers, I believe,
but it might be possible to make this a more thorough conversion &
ensure there are no remaining FIs no matter how instruction selection
is performed.

llvm-svn: 184066

Lets us use a SetVector instead of an explicit set + vector combination.

llvm-svn: 182586

No functionality change.

llvm-svn: 181149

Sooooo many of these had incorrect or strange main module includes.
I have manually inspected all of these, and fixed the main module
include to be the nearest plausible thing I could find. If you own or
care about any of these source files, I encourage you to take some time
and check that these edits were sensible. I can't have broken anything
(I strictly added headers, and reordered them, never removed), but they
may not be the headers you'd really like to identify as containing the
API being implemented.

Many forward declarations and missing includes were added to a header
files to allow them to parse cleanly when included first. The main
module rule does in fact have its merits. =]

llvm-svn: 169131

No functional change, just moved header files.

Targets can inject custom passes between register allocation and
rewriting. This makes it possible to tweak the register allocation
before rewriting, using the full global interference checking available
from LiveRegMatrix.

llvm-svn: 168806

Add an analyzePhysReg() function to MachineOperandIteratorBase that analyses an instruction's use of a physical register, analogous to analyzeVirtReg.

Rename RegInfo to VirtRegInfo so as not to be confused with the new PhysRegInfo.

llvm-svn: 163694

llvm-svn: 163059

No test case, there are no in-tree targets that require this.

llvm-svn: 160219

llvm-svn: 158575

LLVM is now -Wunused-private-field clean except for
- lib/MC/MCDisassembler/Disassembler.h. Not sure why it keeps all those unaccessible fields.
- gtest.

llvm-svn: 158096

llvm-svn: 157142

llvm-svn: 153906

Refactored the LiveRangeEdit interface so that MachineFunction, TargetInstrInfo, MachineRegisterInfo, LiveIntervals, and VirtRegMap are all passed into the constructor and stored as members instead of passed in to each method.

llvm-svn: 153903

Simply treat bundles as instructions. Spill code is inserted between
bundles, never inside a bundle.  Rewrite all operands in a bundle at
once.

Don't attempt and memory operand folding inside bundles.

llvm-svn: 151787

If a value is defined by a COPY, that instuction can easily and cheaply
be found by getInstructionFromIndex(VNI->def).

This reduces the size of VNInfo from 24 to 16 bytes, and improves
llc compile time by 3%.

llvm-svn: 149763

If we create new intervals for a variable that is being spilled, then those new intervals are not guaranteed to also spill.  This means that anything reading from the original spilling value might not get the correct value if spills were missed.

Fixes <rdar://problem/10546864>

llvm-svn: 146428

generator to it. For non-bundle instructions, these behave exactly the same
as the MC layer API.

For properties like mayLoad / mayStore, look into the bundle and if any of the
bundled instructions has the property it would return true.
For properties like isPredicable, only return true if *all* of the bundled
instructions have the property.
For properties like canFoldAsLoad, isCompare, conservatively return false for
bundles.

llvm-svn: 146026

llvm-svn: 144517

This makes no difference for normal defs, but early clobber dead defs
now look like:

  [Slot_EarlyClobber; Slot_Dead)

instead of:

  [Slot_EarlyClobber; Slot_Register).

Live ranges for normal dead defs look like:

  [Slot_Register; Slot_Dead)

as before.

llvm-svn: 144512

The old naming scheme (load/use/def/store) can be traced back to an old
linear scan article, but the names don't match how slots are actually
used.

The load and store slots are not needed after the deferred spill code
insertion framework was deleted.

The use and def slots don't make any sense because we are using
half-open intervals as is customary in C code, but the names suggest
closed intervals.  In reality, these slots were used to distinguish
early-clobber defs from normal defs.

The new naming scheme also has 4 slots, but the names match how the
slots are really used.  This is a purely mechanical renaming, but some
of the code makes a lot more sense now.

llvm-svn: 144503

Nobody cared, StackSlotColoring scans the instructions to find used stack
slots.

llvm-svn: 144485

The TII.foldMemoryOperand hook preserves implicit operands from the
original instruction.  This is not what we want when those implicit
operands refer to the register being spilled.

Implicit operands referring to other registers are preserved.

This fixes PR11347.

llvm-svn: 144247

When spilling around an instruction with a dead def, remember to add a
value number for the def.

The missing value number wouldn't normally create problems since there
would be an incoming live range as well.  However, due to another bug
we could spill a dead V_SET0 instruction which doesn't read any values.

The missing value number caused an empty live range to be created which
is dangerous since it doesn't interfere with anything.

This fixes part of PR11125.

llvm-svn: 141923

If the source register is live after the copy being spilled, there is no
point to hoisting it.  Hoisting inside a basic block only serves to
resolve interferences by shortening the live range of the source.

llvm-svn: 139882

When -split-spill-mode is enabled, spill hoisting is performed by
SplitKit instead of by InlineSpiller.  This hidden command line option
is for testing the splitter spill mode.

llvm-svn: 139845

The number of spills could go negative since a folded COPY is just a
spill, and it may be eliminated.

llvm-svn: 139815

Adjust counters when removing spill and reload instructions.

We still don't account for reloads being removed by eliminateDeadDefs().

llvm-svn: 139806

When traceSiblingValue() encounters a PHI-def value created by live
range splitting, don't look at all the predecessor blocks.  That can be
very expensive in a complicated CFG.

Instead, consider that all the non-PHI defs jointly dominate all the
PHI-defs.  Tracing directly to all the non-PHI defs is much faster that
zipping around in the CFG when there are many PHIs with many
predecessors.

This significantly improves compile time for indirectbr interpreters.

llvm-svn: 139797

In some cases such as interpreters using indirectbr, the CFG can be very
complicated, and live range splitting may be forced to insert a large
number of phi-defs.  When that happens, traceSiblingValue can spend a
lot of time zipping around in the CFG looking for defs and reloads.

This patch causes more information to be cached in SibValues, and the
cached values are used to terminate searches early.  This speeds up
spilling by 20x in one interpreter test case.  For more typical code,
this is just a 10% speedup of spilling.

The previous version had bugs that caused miscompilations. They have
been fixed.

llvm-svn: 139378

It broke the self host and clang-x86_64-darwin10-RA.

llvm-svn: 139259

In some cases such as interpreters using indirectbr, the CFG can be very
complicated, and live range splitting may be forced to insert a large
number of phi-defs.  When that happens, traceSiblingValue can spend a
lot of time zipping around in the CFG looking for defs and reloads.

This patch causes more information to be cached in SibValues, and the
cached values are used to terminate searches early.  This speeds up
spilling by 20x in one interpreter test case.  For more typical code,
this is just a 10% speedup of spilling.

llvm-svn: 139247