in SSAUpdaterImpl.h

Verifying live intervals revealed that the old method was completely wrong, and
we need an iterative approach to calculating PHI placemant. Fortunately, we have
MachineDominators available, so we don't have to compute that over and over
like SSAUpdaterImpl.h must.

Live-out values are cached between calls to mapValue() and computed in a greedy
way, so most calls will be working with very small block sets.

Thanks to Bob for explaining how this should work.

llvm-svn: 117599

proper SSA updating.

This doesn't cause MachineDominators to be recomputed since we are already
requiring MachineLoopInfo which uses dominators as well.

llvm-svn: 117598

live out.

This doesn't prevent us from inserting a loop preheader later on, if that is
better.

llvm-svn: 117424

Critical edges going into a loop are not as bad as critical exits. We can handle
them by splitting the critical edge, or by having both inside and outside
registers live out of the predecessor.

llvm-svn: 117423

the remainder register.

Example:

bb0:
  x = 1
bb1:
  use(x)
  ...
  x = 2
  jump bb1

When x is isolated in bb1, the inner part breaks into two components, x1 and x2:

bb0:
  x0 = 1
bb1:
  x1 = x0
  use(x1)
  ...
  x2 = 2
  x0 = x2
  jump bb1

llvm-svn: 117408

necessary to get correct hasPHIKill flags.

llvm-svn: 117406

llvm-svn: 117405

When a block has exactly two uses and the register is both live-in and live-out,
don't isolate the block. We would be inserting two copies, so we haven't really
made any progress.

If the live-in and live-out values separate into disconnected components after
splitting, we would be making progress. We can't detect that for now.

llvm-svn: 117169

An exit block with a critical edge must only have predecessors in the loop, or
just before the loop. This guarantees that the inserted copies in the loop
predecessors dominate the exit block.

llvm-svn: 117144

llvm-svn: 117143

Parent - union(Y, ...). Doh.

llvm-svn: 117042

llvm-svn: 116547

All registers created during splitting or spilling are assigned to the same
stack slot as the parent register.

When splitting or rematting, we may not spill at all. In that case the stack
slot is still assigned, but it will be dead.

llvm-svn: 116546

splitting or spillling, and to help with rematerialization.

Use LiveRangeEdit in InlineSpiller and SplitKit. This will eventually make it
possible to share remat code between InlineSpiller and SplitKit.

llvm-svn: 116543

Before we would also split around a loop if any peripheral block had multiple
uses. This could cause repeated splitting when splitting a different live range
would insert uses into the periphery.

Now -spiller=inline passes the nightly test suite again.

llvm-svn: 116494

functions: computeRemainder and rewrite.

When the remainder breaks up into multiple components, remember to rewrite those
uses as well.

llvm-svn: 116121

connected components. These components should be allocated different virtual
registers because there is no reason for them to be allocated together.

Add the ConnectedVNInfoEqClasses class to calculate the connected components,
and move values to new LiveIntervals.

Use it from SplitKit::rewrite by creating new virtual registers for the
components.

llvm-svn: 116006

llvm-svn: 115951

llvm-svn: 115950

do one find().

llvm-svn: 115929

llvm-svn: 115928

llvm-svn: 115710

reusable, but that is no longer relevant since a split will always replace the
original.

llvm-svn: 115709

llvm-svn: 115708

llvm-svn: 115696

never kept after splitting.

Keeping the original interval made sense when the split region doesn't modify
the register, and the original is spilled. We can get the same effect by
detecting reloaded values when spilling around copies.

llvm-svn: 115695

llvm-svn: 115694

erasing it from the visited set. That ensures we create the right phi defs.

llvm-svn: 115666

Insert copy after defining instruction.

Fix LiveIntervalMap::extendTo to properly handle live segments starting before
the current basic block.

Make sure the open live range is extended to the inserted copy's use slot.

llvm-svn: 115665

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

llvm-svn: 114791

creating it before and subtracting split ranges.

This way, the SSA update code in LiveIntervalMap can properly create and use new
phi values in dupli. Now it is possible to create split regions where a value
escapes along two different CFG edges, creating phi values outside the split
region.

This is a work in progress and probably quite broken.

llvm-svn: 114492

great deal because we don't have to worry about maintaining SSA form.

Unconditionally copy back to dupli when the register is live out of the split
range, even if the live-out value was defined outside the range. Skipping the
back-copy only makes sense when the live range is going to spill outside the
split range, and we don't know that it will. Besides, this was a hack to avoid
SSA update issues.

Clear up some confusion about the end point of a half-open LiveRange. Methinks
LiveRanges need to be closed so both start and end are included in the range.
The low bits of a SlotIndex are symbolic, so a half-open range doesn't really
make sense. This would be a pervasive change, though.

llvm-svn: 114043

edited without actually using LiveIntervalMap functionality.

llvm-svn: 113816

llvm-svn: 113815

pointer and work around that.

llvm-svn: 113788

The Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 16.00.30319.01
implements parts of C++0x based on the draft standard. An old version of
the draft had a bug that makes std::pair<T1*, T2*>(something, 0) fail to
compile. This is because the template<class U, class V> pair(U&& x, V&& y)
constructor is selected, even though it later fails to implicitly convert
U and V to frist_type and second_type.

This has been fixed in n3090, but it seems that Microsoft is not going to
update msvc.

llvm-svn: 111535

map discovers the iterated dominance frontier for free.

llvm-svn: 111400

We must complete the DFS, otherwise we might miss needed phi-defs, and
prematurely color live ranges with a non-dominating value.

This is not a big deal since we get to color more of the CFG and the next
mapValue call will be faster.

llvm-svn: 111397

llvm-svn: 111394

LiveIntervalMap maps values from a parent LiveInterval to a child interval that
is a strict subset. It will create phi-def values as needed to preserve the
VNInfo SSA form in the child interval.

This leads to an algorithm very similar to the one in SSAUpdaterImpl.h, but with
enough differences that the code can't be reused:

- We don't need to manipulate PHI instructions.
- LiveIntervals have kills.
- We have MachineDominatorTree.
- We can use df_iterator.

llvm-svn: 111393