Fix a performance problem with the new SSAUpdater. This showed up in the
GCCAS time for MultiSource/Benchmarks/ASCI_Purple/SMG2000.

llvm-svn: 102009

Re-commit my previous SSAUpdater changes. The previous version naively tried
to determine where to place PHIs by iteratively comparing reaching definitions
at each block. That was just plain wrong.

Re-commit my previous SSAUpdater changes. The previous version naively tried
to determine where to place PHIs by iteratively comparing reaching definitions
at each block. That was just plain wrong. This version now computes the
dominator tree within the subset of the CFG where PHIs may need to be placed,
and then places the PHIs in the iterated dominance frontier of each definition.
The rest of the patch is mostly the same, with a few more performance
improvements added in.

llvm-svn: 101612

show more ...

Revert all my SSAUpdater patches. The PHI placement algorithm is not correct
(what was I thinking?) and there's also a problem with LCSSA. I'll try again
later with fixes.

--- Reverse-merging r100

Revert all my SSAUpdater patches. The PHI placement algorithm is not correct
(what was I thinking?) and there's also a problem with LCSSA. I'll try again
later with fixes.

--- Reverse-merging r100263 into '.':
U lib/Transforms/Utils/SSAUpdater.cpp
--- Reverse-merging r100177 into '.':
G lib/Transforms/Utils/SSAUpdater.cpp
--- Reverse-merging r100148 into '.':
G lib/Transforms/Utils/SSAUpdater.cpp
--- Reverse-merging r100147 into '.':
U include/llvm/Transforms/Utils/SSAUpdater.h
G lib/Transforms/Utils/SSAUpdater.cpp
--- Reverse-merging r100131 into '.':
G include/llvm/Transforms/Utils/SSAUpdater.h
G lib/Transforms/Utils/SSAUpdater.cpp
--- Reverse-merging r100130 into '.':
G lib/Transforms/Utils/SSAUpdater.cpp
--- Reverse-merging r100126 into '.':
G include/llvm/Transforms/Utils/SSAUpdater.h
G lib/Transforms/Utils/SSAUpdater.cpp
--- Reverse-merging r100050 into '.':
D test/Transforms/GVN/2010-03-31-RedundantPHIs.ll
--- Reverse-merging r100047 into '.':
G include/llvm/Transforms/Utils/SSAUpdater.h
G lib/Transforms/Utils/SSAUpdater.cpp

llvm-svn: 100264

show more ...

Add a DEBUG_TYPE for the SSAUpdater.

llvm-svn: 100263

Recommit 100158 now that the buildbots are happy again.

llvm-svn: 100177

Revert 100158 in case it is causing some of the buildbot problems.

llvm-svn: 100164

Check for terminating conditions before adding PHIs to the worklists.
This is more efficient than adding them to the worklist and then ignoring them.

llvm-svn: 100158

Remove trailing whitespace.

llvm-svn: 100148

Rewrite another SSAUpdater function to avoid recursion.

llvm-svn: 100147

Change another SSAUpdater function to avoid recursion.

llvm-svn: 100131

Simplify the code to check for existing PHIs, now that it is only used in
one place. This removes the template function added in svn 94690.

llvm-svn: 100130

The SSAUpdater should avoid recursive traversals of the CFG, since that may
blow out the stack for really big functions. Start by fixing an easy case.

llvm-svn: 100126

Rewrite part of the SSAUpdater to be more careful about inserting redundant
PHIs. The previous algorithm was unable to reliably detect when existing
PHIs in a cycle can be reused. I'm still working

Rewrite part of the SSAUpdater to be more careful about inserting redundant
PHIs. The previous algorithm was unable to reliably detect when existing
PHIs in a cycle can be reused. I'm still working on reducing a testcase.
Radar 7711900.

llvm-svn: 100047

show more ...

Avoid creating redundant PHIs in SSAUpdater::GetValueInMiddleOfBlock.
This was already being done in SSAUpdater::GetValueAtEndOfBlock so I've
just changed SSAUpdater to check for existing PHIs in bot

Avoid creating redundant PHIs in SSAUpdater::GetValueInMiddleOfBlock.
This was already being done in SSAUpdater::GetValueAtEndOfBlock so I've
just changed SSAUpdater to check for existing PHIs in both places.

llvm-svn: 94690

show more ...

Change errs() to dbgs().

llvm-svn: 92603

improve indentation avoid a pointless conversion from weakvh to trackingvh,
no functionality change.

llvm-svn: 91848

fix PR5837 by having SSAUpdate reuse phi nodes for the
'GetValueInMiddleOfBlock' case, instead of inserting
duplicates.

A similar fix is almost certainly needed by the machine-level
SSAUpdate imple

fix PR5837 by having SSAUpdate reuse phi nodes for the
'GetValueInMiddleOfBlock' case, instead of inserting
duplicates.

A similar fix is almost certainly needed by the machine-level
SSAUpdate implementation.

llvm-svn: 91820

show more ...

add an assert to make it really clear what this is doing. Return singularval as
a compile time perf optimization to avoid a load.

llvm-svn: 90507

alternate fix for PR5258 which avoids worklist problems, with reduced testcase.

llvm-svn: 84667

Fix PR5258, jump-threading creating invalid PHIs.
When an incoming value for a PHI is updated, we must also updated all other
incoming values for the same BB to match, otherwise we create invalid PHI

Fix PR5258, jump-threading creating invalid PHIs.
When an incoming value for a PHI is updated, we must also updated all other
incoming values for the same BB to match, otherwise we create invalid PHIs.

llvm-svn: 84638

show more ...

Strip trailing white space.

llvm-svn: 84256

add a simple helper method.

llvm-svn: 83745

add ability for clients of SSAUpdater to find out about the
PHI nodes inserted.

llvm-svn: 83744

add the ability to get a rewritten value from the middle of a block,
not just at the end. Add a big comment explaining when this could
be useful (which never happens for jump threading).

llvm-svn:

add the ability to get a rewritten value from the middle of a block,
not just at the end. Add a big comment explaining when this could
be useful (which never happens for jump threading).

llvm-svn: 83741

show more ...

rename GetValueInBlock -> GetValueAtEndOfBlock to better reflect
what it does.

llvm-svn: 83740