SimplifyIndVar utility since it is required.

llvm-svn: 137202

based on ScalarEvolution without changing the induction variable phis.

This utility is the main tool of IndVarSimplifyPass, but the pass also
restructures induction variables in strange ways that are sensitive to
pass ordering. This provides a way for other loop passes to simplify
new uses of induction variables created during transformation. The
utility may be used by any pass that preserves ScalarEvolution. Soon
LoopUnroll will use it.

The net effect in this checkin is to cleanup the IndVarSimplify pass
by factoring out the SimplifyIndVar algorithm into a standalone utility.

llvm-svn: 137197

recurrence, the initial values low bits can sometimes be ignored.

To take advantage of this, added FoldIVUser to IndVarSimplify to fold
an IV operand into a udiv/lshr if the operator doesn't affect the
result.

-indvars -disable-iv-rewrite now transforms

i = phi i4
i1 = i0 + 1
idx = i1 >> (2 or more)
i4 = i + 4

into

i = phi i4
idx = i0 >> ...
i4 = i + 4

llvm-svn: 137013

llvm-svn: 135684

to for it to be an an anon namespace and be in a header.

Eliminate some extraenous uses of tie.

llvm-svn: 135669

llvm-svn: 135581

llvm-svn: 135568

info. Holding Use* pointers is bad form even though it happened to
work in this case.

llvm-svn: 135566

llvm-svn: 135558

llvm-svn: 135426

For -disable-iv-rewrite, perform LFTR without generating a new
"canonical" induction variable. Instead find the "best" existing
induction variable for use in the loop exit test and compute the final
value of that IV for use in the new loop exit test. In short,
convert to a simple eq/ne exit test as long as it's cheap to do so.

llvm-svn: 135420

not interfere with BackedgeTakenCount computation.

llvm-svn: 135412

preheader for the sole purpose of LFTR, since LFTR itself is usually not
a clear optimization.

llvm-svn: 135409

llvm-svn: 135375

assertion I added in r135333. Check for the existence of a preheader
before expanding a recurrence.

llvm-svn: 135335

llvm-svn: 135334

LinearFunctionTestReplace rewrite. No functionality.

I've been wanting to group the indvar subphases into sections and
order them by their logical sequence. My next checkin adds functions
related to LFTR, and doing the reorg now should help reviewers. Since,
most of the code in IndVarSimplify.cpp has recently been replaced or
will be replaced soon, obscuring blame should not be an issue. This
seems like an ideal time to shuffle the code around.

I'm happy to take more suggestions for cleaning up the code. Or if
you've been wanting to cleanup anything in this file yourself, now is
a good time.

llvm-svn: 134941

careful about referencing values.

llvm-svn: 134537

llvm-svn: 134530

llvm-svn: 134441

Putting back the helper that I removed on 7/1 to do this right.

llvm-svn: 134423

llvm-svn: 134306

llvm-svn: 134177

llvm-svn: 134124

llvm-svn: 134112

mean they can be removed.

llvm-svn: 134054

llvm-svn: 134010

llvm-svn: 133992

llvm-svn: 133988

evaluates all other IV exprs.

llvm-svn: 133982

a bit more control over the order SCEVs are evaluated.

llvm-svn: 133959

llvm-svn: 133636

llvm-svn: 133518

ops.

This is a rewrite of the IV simplification algorithm used by
-disable-iv-rewrite. To avoid perturbing the default mode, I
temporarily split the driver and created SimplifyIVUsersNoRewrite. The
idea is to avoid doing opcode/pattern matching inside
IndVarSimplify. SCEV already does it. We want to optimize with the
full generality of SCEV, but optimize def-use chains top down on-demand rather
than rewriting the entire expression bottom-up. This was easy to do
for operations that SCEV can prove are identity function. So we're now
eliminating bitmasks and zero extends this way.

A result of this rewrite is that indvars -disable-iv-rewrite no longer
requires IVUsers.

llvm-svn: 133502

Use a proper worklist for use-def traversal without holding onto an
iterator. Now that we process all IV uses, we need complete logic for
resusing existing derived IV defs. See HoistStep.

llvm-svn: 132103

cleanup and overdue test cases.

llvm-svn: 132038

No functionality enabled by default. Use -disable-iv-rewrite.
Extended IVUsers to keep track of the phi that represents the users' IV.
Added the WidenIV transform to replace a narrow IV with a wide IV
by doing a one-for-one replacement of IV users instead of expanding the
SCEV expressions. [sz]exts are removed and truncs are inserted.

llvm-svn: 131744

llvm-svn: 131716

the users.

llvm-svn: 131277

Interleave IV simplifications. Currently involves EliminateComparison
and EliminateRemainder. Next I'll add EliminateExtend.

llvm-svn: 131210