and TargetInstrDescriptor::ImplicitUses to always point to a null
terminated array and never be null. So there is no need to check for
pointer validity when iterating over those sets. Code that looked
like:

if (const unsigned* AS = TID.ImplicitDefs) {
  for (int i = 0; AS[i]; ++i) {
    // use AS[i]
  }
}

was changed to:

for (const unsigned* AS = TID.ImplicitDefs; *AS; ++AS) {
  // use *AS
}

llvm-svn: 8960

llvm-svn: 8955

llvm-svn: 8954

llvm-svn: 8952

llvm-svn: 8951

llvm-svn: 8930

logarithmic conditional branch sequences instead of linear sequences.  Thanks Bill!

llvm-svn: 8928

llvm-svn: 8922

Thanks to Brian for fixing this obvious oops

llvm-svn: 8899

llvm-svn: 8898

llvm-svn: 8895

llvm-svn: 8894

of callees between executions.

On eon, in release mode, this changes the inliner from taking 11.5712s
to taking 2.2066s.  In debug mode, it went from taking 14.4148s to
taking 7.0745s.  In release mode, this is a 24.7% speedup of gccas, in
debug mode, it's a total speedup of 11.7%.

This also makes it slightly more aggressive.  This could be because we
are not judging the size of the functions quite as accurately as before.
When we start looking at the performance of the generated code, this can
be investigated further.

llvm-svn: 8893

llvm-svn: 8892

Running the inliner on 252.eon used to take 48.4763s, now it takes 14.4148s.

In release mode, it went from taking 25.8741s to taking 11.5712s.

This also fixes a FIXME.

llvm-svn: 8890

llvm-svn: 8889

want you to include <sys/stat.h> for fstat(), struct stat, and friends.

llvm-svn: 8887

"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: 8874

llvm-svn: 8872

llvm-svn: 8871

do not support stack unwinding yet

llvm-svn: 8869

llvm-svn: 8868

This reduces the time to verify a function from eon with a large number of
large PHI nodes from 22996s (6.38 hours) to 10.5499s

llvm-svn: 8866

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

Print literal doubles using ftostr instead of <<, because it yields higher precision numbers.

llvm-svn: 8855

constants as necessary due to type resolution.  With this change, the
following spec benchmarks now link: 176.gcc, 177.mesa, 252.eon,
253.perlbmk, & 300.twolf.  IOW, all SPEC INT and FP benchmarks now link.

llvm-svn: 8853

and because, while the class used by the interface is abstract, the actual
concept is not.

llvm-svn: 8850

as 'by reference' arguments.

llvm-svn: 8849

llvm-svn: 8848