When splitting a critical edge, the registers live through the edge are:

- Used in a PHI instruction, or
- Live out from the predecessor, and
- Live in to the successor.

This allows the coalescer to eliminate even more phi joins.

llvm-svn: 89530

D0<def,dead> = ...
...
             = S0<use, kill>
S0<def>      = ...
...
D0<def>      = 

The first D0 def is correctly marked dead, however, livevariables should have
added an implicit def of S0 or we end up with a use without a def.

llvm-svn: 88690

- Edges are split before any phis are eliminated, so the code is SSA.

- Create a proper IR BasicBlock for the split edges.

- LiveVariables::addNewBlock now has same syntax as
  MachineDominatorTree::addNewBlock. Algorithm calculates predecessor live-out
  set rather than successor live-in set.

This feature still causes some miscompilations.

llvm-svn: 86867

Critical edges leading to a PHI node are split when the PHI source variable is
live out from the predecessor block. This help the coalescer eliminate more
PHI joins.

llvm-svn: 86725

When LiveVariables is adding implicit-def to model "partial dead", add the earlyclobber marker if the superreg def has it.

llvm-svn: 84153

Clean up LiveVariables and change how it deals with partial updates and kills. This also eliminate the horrible check which scan forward to the end of the basic block. It should be faster and more accurate.

llvm-svn: 82676

of the defs are processed.
Also fix a implicit_def propagation bug: a implicit_def of a physical register
should be applied to uses of the sub-registers.

llvm-svn: 82616

Fix PR5024. LiveVariables::FindLastPartialDef should return a set of sub-registers that were defined by the last partial def, not just a single sub-register.

llvm-svn: 82535

llvm-svn: 79873

MachineInstr and MachineOperand.  This required eliminating a
bunch of stuff that was using DOUT, I hope that bill doesn't
mind me stealing his fun. ;-)

llvm-svn: 79813

shouldn't do AU.setPreservesCFG(), because even though CodeGen passes
don't modify the LLVM IR CFG, they may modify the MachineFunction CFG,
and passes like MachineLoop are registered with isCFGOnly set to true.

llvm-svn: 77691

failures when building assorted projects with clang.

--- Reverse-merging r77654 into '.':
U    include/llvm/CodeGen/Passes.h
U    include/llvm/CodeGen/MachineFunctionPass.h
U    include/llvm/CodeGen/MachineFunction.h
U    include/llvm/CodeGen/LazyLiveness.h
U    include/llvm/CodeGen/SelectionDAGISel.h
D    include/llvm/CodeGen/MachineFunctionAnalysis.h
U    include/llvm/Function.h
U    lib/Target/CellSPU/SPUISelDAGToDAG.cpp
U    lib/Target/PowerPC/PPCISelDAGToDAG.cpp
U    lib/CodeGen/LLVMTargetMachine.cpp
U    lib/CodeGen/MachineVerifier.cpp
U    lib/CodeGen/MachineFunction.cpp
U    lib/CodeGen/PrologEpilogInserter.cpp
U    lib/CodeGen/MachineLoopInfo.cpp
U    lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
D    lib/CodeGen/MachineFunctionAnalysis.cpp
D    lib/CodeGen/MachineFunctionPass.cpp
U    lib/CodeGen/LiveVariables.cpp

llvm-svn: 77661

mechanism. To support this, make MachineFunctionPass a little more
complete.

llvm-svn: 77654

llvm-svn: 74857

llvm-svn: 73816

If there is a def of a super-register followed by a use of a sub-register, do *not* add an implicit def of the sub-register. e.g.
EAX = ..., AX<imp-def>
...
    = AX

This creates a double-def. Apparently this used to be necessary but is no longer needed.

Thanks to Anton for pointing this out. Anton, I cannot create a test case without your uncommitted ARM patches. Please check in a test case for me.

llvm-svn: 72755

entries as there are basic blocks in the function.  LiveVariables::getVarInfo
creates a VarInfo struct for every register in the function, leading to
quadratic space use.  This patch changes the BitVector to a SparseBitVector,
which doesn't help the worst-case memory use but does reduce the actual use in
very long functions with short-lived variables.

llvm-svn: 72426

llvm-svn: 72411

Fix PR3243: a LiveVariables bug. When HandlePhysRegKill is checking whether the last reference is also the last def (i.e. dead def), it should also check if last reference is the current machine instruction being processed. This can happen when it is processing a physical register use and setting the current machine instruction as sub-register's last ref.

llvm-svn: 62617

llvm-svn: 59841

BitVector, instead of manually testing each bit.

llvm-svn: 59246

isReg, etc., from isRegister, etc.

llvm-svn: 57006

Handle{Virt,Phys}Reg{Def,Use}. Remove a redundant check
for register zero, and redundant checks for isPhysicalRegister.

llvm-svn: 56412

llvm-svn: 54810

- Add a basic machine-level dead block eliminator.

These two have to go together, since many other parts of the code generator are unable to handle the unreachable blocks otherwise created.

llvm-svn: 54333

- Remove calls to copyKillDeadInfo which is an N^2 function. Instead, propagate kill / dead markers as new instructions are constructed in foldMemoryOperand, convertToThressAddress, etc.
- Also remove LiveVariables::instructionChanged, etc. Replace all calls with cheaper calls which update VarInfo kill list.

llvm-svn: 53097

llvm-svn: 53063

- Add LiveVariables::replaceKillInstruction. This does a subset of instructionChanged. That is, it only update the VarInfo.kills if the new instruction is known to have the correct dead and kill markers.
- CommuteInstruction copies kill / dead markers over to new instruction. So use replaceKillInstruction instead.

llvm-svn: 53061

This speeds up a particular testcase from 0.0302s to 0.0222s in LiveVariables.

llvm-svn: 52819

llvm-svn: 52744

    ,------.
    |      |
    |      v
    |   t2 = phi ... t1 ...
    |      |
    |      v
    |   t1 = ...
    |  ... = ... t1 ...
    |      |
    `------'

where there is a use in a PHI node that's a predecessor to the defining
block. We don't want to mark all predecessors as having the value "alive" in
this case. Also, the assert was too restrictive and didn't handle this case.

llvm-svn: 52655

Rewrite LiveVariable liveness computation. The new implementation is much simplified. It eliminated the nasty recursive routines and removed the partial def / use bookkeeping. There is also potential for performance improvement by replacing the conservative handling of partial physical register definitions. The code is currently disabled until live interval analysis is taught of the name scheme.

This patch also fixed a couple of nasty corner cases.

llvm-svn: 49784

Now that I am told MachineRegisterInfo also tracks physical register uses / defs, I can do away with the horribleness I introduced a while back. It's impossible to detect if there is any use of a physical register below an instruction (and before any def of the register) with some cheap book keeping.

llvm-svn: 49105

1. If part of a register is re-defined, an implicit kill and an implicit def are added to denote read / mod / write. However, this should only be necessary if the register is actually read later. This is a performance issue.
2. If a sub-register is being defined, and it doesn't have a previous use, do not add a implicit kill to the last use of a super-register:
   = EAX, AX<imp-use,kill>
...
AX =
In this case, EAX is live but AX is killed, this is wrong and will cause the coalescer to do bad things.

llvm-svn: 48521

findRegisterUseOperandIdx, findRegisterDefOperandIndx. Fix some naming inconsistencies.

llvm-svn: 47927

llvm-svn: 47453

No need to go up more levels. A def of a register also sets its sub-registers
(so if PhysRegInfo[SuperReg] is NULL, it means SuperReg's super registers are
not previously defined).

llvm-svn: 47399

llvm-svn: 47395

llvm-svn: 47389

Added two "FIXMEs" for code that looks dubious to me (but I could be
wrong).

llvm-svn: 47366