Patch by Pranav Bhandarkar!

llvm-svn: 142556

We want heuristics to be based on accurate data, but more importantly
we don't want llvm to behave randomly. A benign trunc inserted by an
upstream pass should not cause a wild swings in optimization
level. See PR11034. It's a general problem with threshold-based
heuristics, but we can make it less bad.

llvm-svn: 140919

This changes loop unrolling to use the same mechanism for trip count
computation as indvars. This is a stronger check that tends to unroll
more loops. A very common side-effect is that many single iteration
loops will be removed sooner. The real goal was simply to remove
dependence on canonical IVs.

x86 is break even.
ARM performance changes to expect (+ is good):
External/SPEC/CFP2000/183.equake/183.equake +13%
SingleSource/Benchmarks/Dhrystone/fldry     +21%
MultiSource/Applications/spiff/spiff         +3%
SingleSource/Benchmarks/Stanford/Puzzle     -14%

The Puzzle regression is actually an improvement in loop optimization
that defeats GVN: rdar://problem/10065079.

llvm-svn: 139009

SCEV unrolling can unroll loops with arbitrary induction variables. It
is a prerequisite for -disable-iv-rewrite performance. It is also
easily handles loops of arbitrary structure including multiple exits
and is generally more robust.

This is under a temporary option to avoid affecting default
behavior for the next couple of weeks. It is needed so that I can
checkin unit tests for updateUnloop.

llvm-svn: 137384

llvm-svn: 137203

removes its dependence on canonical induction variables.

llvm-svn: 135829

llvm-svn: 135828

llvm-svn: 129501

llvm-svn: 129450

Passing unroll parameters (unroll-count, threshold, and partial unroll) via LoopUnroll class's ctor. Doing so 
will allow multiple context with different loop unroll parameters to run.  This is a minor change and no effect 
on existing application.

llvm-svn: 129449

without whatever this was trying to do.  When/if someone has the time to do some empirical
evaluations, it might be worth it to figure out what this code was trying to do and see if
it's worth resurrecting/fixing.

llvm-svn: 123684

llvm-svn: 123221

size of a loop header instead of its own code size estimator.
This allows it to handle bitcasts etc more precisely.

llvm-svn: 122681

they do not also require them.  This allows us to reduce inter-pass linkage
dependencies.

llvm-svn: 116854

Get rid of static constructors for pass registration.  Instead, every pass exposes an initializeMyPassFunction(), which
must be called in the pass's constructor.  This function uses static dependency declarations to recursively initialize
the pass's dependencies.

Clients that only create passes through the createFooPass() APIs will require no changes.  Clients that want to use the
CommandLine options for passes will need to manually call the appropriate initialization functions in PassInitialization.h
before parsing commandline arguments.

I have tested this with all standard configurations of clang and llvm-gcc on Darwin.  It is possible that there are problems
with the static dependencies that will only be visible with non-standard options.  If you encounter any crash in pass
registration/creation, please send the testcase to me directly.

llvm-svn: 116820

perform initialization without static constructors AND without explicit initialization
by the client.  For the moment, passes are required to initialize both their
(potential) dependencies and any passes they preserve.  I hope to be able to relax
the latter requirement in the future.

llvm-svn: 116334

llvm-svn: 115996

llvm-svn: 115053

register pressure and thus excess spills, which we don't currently recover from well.  This should
be re-evaluated in the future if our ability to generate good spills/splits improves.

Partial fix for <rdar://problem/7635585>.

llvm-svn: 114919

Lower the unrolling theshold to 150.  Empirical tests indicate that this is a sweet spot in the performance per
code size increase curve.

llvm-svn: 113595

not unrolling loops that contain calls that would be better off getting inlined.  This mostly
comes up when an interleaved devirtualization pass has devirtualized a call which the inliner
will inline on a future pass.  Thus, rather than blocking all loops containing calls, add
a metric for "inline candidate calls" and block loops containing those instead.

llvm-svn: 113535

Revert r113439, which relaxed the requirement that loops containing calls cannot be unrolled.  After some discussion,
there seems to be a better way to achieve the same effect.

llvm-svn: 113528

llvm-svn: 113527

llvm-svn: 113526

Next step is to recalculate the threshold values given this new heuristic.

llvm-svn: 113525

Relax the "don't unroll loops containing calls" rule.  Instead, when a loop contains a call, lower the
unrolling threshold to the optimize-for-size threshold.  Basically, for loops containing calls, unrolling
can still be profitable as long as the loop is REALLY small.

llvm-svn: 113439

The threshold value of 50 is arbitrary, and I chose it simply by analogy to the inlining thresholds, where
the baseline unrolling threshold is slightly smaller than the baseline inlining threshold.  This could
undoubtedly use some tuning.

llvm-svn: 113306

for the unroller to pretend it supports updating it.  It still
has a horrible hack for DomTree.

llvm-svn: 112444

llvm-svn: 110460

llvm-svn: 110410

ID member as the sole unique type identifier.  Clean up APIs related to this change.

llvm-svn: 110396

Experiments show that we can safely increase our unrolling threshold without unduly impacting code size, particularly
since unrolling is not enabled at -Os.

llvm-svn: 110233

dependence on DominanceFrontier. Instead, add an explicit DominanceFrontier
pass in StandardPasses.h to ensure that it gets scheduled at the right
time.

Declare that loop unrolling preserves ScalarEvolution, and shuffle some
getAnalysisUsages.

This eliminates one LoopSimplify and one LCCSA run in the standard
compile opts sequence.

llvm-svn: 109413

llvm-svn: 109045

compute a set of reachable blocks for itself each time it is called, which
is fairly frequently.

llvm-svn: 98179

llvm-svn: 95454

llvm-svn: 92623

the new common CodeMetrics code.

llvm-svn: 85663

llvm-svn: 85661

LoopUnrollPass.cpp, for consistency with other passes which are
similarly split.

llvm-svn: 85659