llvm-svn: 15334

llvm-svn: 14247

non-deterministic things like the ordering of blocks in the dominance
frontier of a BB.  Unfortunately, I don't know of a better way to solve
this problem than to explicitly sort the BB's in function-order before
processing them.  This is guaranteed to slow the pass down a bit, but
is absolutely necessary to get usable diffs between two different tools
executing the mem2reg or scalarrepl pass.

Before this, bazillions of spurious diff failures occurred all over the
place due to the different order of processing PHIs:

-       %tmp.111 = getelementptr %struct.Connector_struct* %upcon.0.0, uint 0, uint 0
+       %tmp.111 = getelementptr %struct.Connector_struct* %upcon.0.1, uint 0, uint 0

Now, the diffs match.

llvm-svn: 14244

llvm-svn: 12779

process them all as a group.  This speeds up SRoA/mem2reg from 28.46s to
0.62s on the testcase from PR209.

llvm-svn: 11100

SRoA/mem2reg from 41.2s to 27.5s on the testcase in PR209.

llvm-svn: 11099

case that the C/C++ front-end generates.

llvm-svn: 10761

llvm-svn: 10727

llvm-svn: 9903

Header files will be on the way.

llvm-svn: 9298

llvm-svn: 9227

"minimal" SSA form (in other words, it doesn't insert dead PHIs).  This
speeds up the mem2reg pass very significantly because it doesn't have to
do a lot of frivolous work in many common cases.

In the 252.eon function I have been playing with, this doesn't even insert
the 120 PHI nodes that it used to which were trivially dead (in the process
of promoting 356 alloca instructions overall).  This speeds up the mem2reg
pass from 1.2459s to 0.1284s.  More significantly, the DCE pass used to take
2.4138s to remove the 120 dead PHI nodes that mem2reg constructed, now it
takes 0.0134s (which is the time to scan the function and decide that there
is nothing dead).  So overall, on this one function, we speed things up a
total of 3.5179s, which is a 24.8x speedup!  :)

This change is tested by the Mem2Reg/2003-10-05-DeadPHIInsertion.ll test,
which now passes.

llvm-svn: 8884

llvm-svn: 8883

basic block.  This is amazingly common in code generated by the C/C++ front-ends.
This change makes it not have to insert ANY phi nodes, whereas before it would insert
a ton of dead ones which DCE would have to clean up.

Thus, this fix improves compile-time performance of these trivial allocas in two ways:
  1. It doesn't have to do the walking and book-keeping for renaming
  2. It does not insert dead phi nodes for them which would have to
     subsequently be cleaned up.

On my favorite testcase from 252.eon, this special case handles 305 out of
356 promoted allocas in the function.  It speeds up the mem2reg pass from 7.5256s
to 1.2505s.  It inserts 677 fewer dead PHI nodes, which speeds up a subsequent
-dce pass from 18.7524s to 2.4806s.

There are still 120 trivially dead PHI nodes being inserted for variables used
in multiple basic blocks, but they are not handled by this patch.

llvm-svn: 8881

llvm-svn: 8865

The VersionNumbers vector is only used during PHI placement.  Turn it into an argument, allowing us to get rid of the vector.

llvm-svn: 8864

*** Revamp the code which handled unreachable code in the function.  Now the
    code is much more efficient for high-degree basic blocks, such as those
    that occur in the 252.eon SPEC benchmark.

For the interested, the time to promote a SINGLE alloca in _ZN7mrScene4ReadERSi
function used to be > 3.5s.  Now it is < .075s.  The function has a LOT of
allocas in it, so it appeared to be infinite looping, this should make it much
nicer.  :)

llvm-svn: 8863

llvm-svn: 8862

work-list of value definitions.  This allows elimination of the explicit
'iterative' step of the algorithm, and also reuses temporary memory better.

llvm-svn: 8861

need to be an instance variable!

llvm-svn: 8860

* Fuse two parallel loops
* Use a more specific type for AllocaLookup

llvm-svn: 8859

 * Do not insert a new entry into NewPhiNodes during the rename pass if there are no PHIs in a block.
 * Do not compute WriteSets in parallel

llvm-svn: 8858

* Eliminate the KillList instance variable, instead, just delete loads and
  stores as they are "renamed", and delete allocas when they are done
* Make the 'visited' set an instance variable to avoid passing it on the stack.

llvm-svn: 8857

llvm-svn: 7944

llvm-svn: 5919

llvm-svn: 5895

llvm-svn: 5824

llvm-svn: 5810

* Make Mem2Reg assign version numbers now for renamed variables instead of
  .mem2reg suffixes.  This produces what people think of as SSA.

llvm-svn: 5771

llvm-svn: 5685

a pass which wraps the function.  This allows other passes to use the functionality

llvm-svn: 5610

llvm-svn: 5608

    setPreservesCFG to be less confusing.

llvm-svn: 4255

    * Renamed StatisticReporter.h/cpp to Statistic.h/cpp
    * Broke constructor to take two const char * arguments instead of one, so
      that indendation can be taken care of automatically.
    * Sort the list by pass name when printing
    * Make sure to print all statistics as a group, instead of randomly when
      the statistics dtors are called.
    * Updated ProgrammersManual with new semantics.

llvm-svn: 4002

llvm-svn: 3917

Clean up code due to auto-insert constructors

llvm-svn: 3665

llvm-svn: 3487

- Cleaned up the interface to AnalysisUsage to take analysis class names
   instead of ::ID's.
 - Pass::getAnalysis<> now no longer takes an optional argument

llvm-svn: 3265

* Add support for different "PassType's"
* Add new RegisterOpt/RegisterAnalysis templates for registering passes that
  are to show up in opt or analyze
* Register Analyses now
* Change optimizations to use RegisterOpt instead of RegisterPass
* Add support for different "PassType's"
* Add new RegisterOpt/RegisterAnalysis templates for registering passes that
  are to show up in opt or analyze
* Register Analyses now
* Change optimizations to use RegisterOpt instead of RegisterPass
* Remove getPassName implementations from various subclasses

llvm-svn: 3113

llvm-svn: 3016