Cleanup. Make ScalarEvolution an explicit argument of the
SimplifyIndVar utility since it is required.

llvm-svn: 137202

Added a SimplifyIndVar utility to simplify induction variable users
based on ScalarEvolution without changing the induction variable phis.

This utility is the main tool of IndVarSimplifyPass, but th

Added a SimplifyIndVar utility to simplify induction variable users
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

show more ...

Made SCEV's UDiv expressions more canonical. When dividing a
recurrence, the initial values low bits can sometimes be ignored.

To take advantage of this, added FoldIVUser to IndVarSimplify to fold
a

Made SCEV's UDiv expressions more canonical. When dividing a
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

show more ...

Cleanup: make std::pair usage slightly less indecipherable without actually naming variables!

llvm-svn: 135684

move tier out of an anonymous namespace, it doesn't make sense
to for it to be an an anon namespace and be in a header.

Eliminate some extraenous uses of tie.

llvm-svn: 135669

Fix a GCC warning.

llvm-svn: 135581

indvars: Added getInsertPointForUses to find a valid place to truncate the IV.

llvm-svn: 135568

indvars -disable-iv-rewrite: Add NarrowIVDefUse to cache def-use
info. Holding Use* pointers is bad form even though it happened to
work in this case.

llvm-svn: 135566

indvars -disable-iv-rewrite fix: derived GEP IVs

llvm-svn: 135558

Compiler warning.

llvm-svn: 135426

indvars: LinearFunctionTestReplace for non-canonical IVs.

For -disable-iv-rewrite, perform LFTR without generating a new
"canonical" induction variable. Instead find the "best" existing
induction va

indvars: LinearFunctionTestReplace for non-canonical IVs.

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

show more ...

indvars: Added verification that LFTR and other indvars goodness does
not interfere with BackedgeTakenCount computation.

llvm-svn: 135412

indvars: Added isHighCostExpansion. Avoid generating extra ops in the
preheader for the sole purpose of LFTR, since LFTR itself is usually not
a clear optimization.

llvm-svn: 135409

land David Blaikie's patch to de-constify Type, with a few tweaks.

llvm-svn: 135375

indvars: fix a pass-sensitivity issue that would hit the SCEVExpander
assertion I added in r135333. Check for the existence of a preheader
before expanding a recurrence.

llvm-svn: 135335

indvars: remove ExprToIVMap because it won't be needed by LFTR.

llvm-svn: 135334

indvars: Code reorganization in preparation for
LinearFunctionTestReplace rewrite. No functionality.

I've been wanting to group the indvar subphases into sections and
order them by their logical seq

indvars: Code reorganization in preparation for
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

show more ...

indvars -disable-iv-rewrite: ExprToMap lives in Pass data, so be more
careful about referencing values.

llvm-svn: 134537

indvars -disable-iv-rewrite: Added SimplifyCongruentIVs.

llvm-svn: 134530

Preserve debug loc.

llvm-svn: 134441

indvars -disable-iv-rewrite: avoid multiple IVs in weird cases.

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

llvm-svn: 134423

indvars -disable-iv-rewrite: bug fix involving weird geps and related cleanup.

llvm-svn: 134306

indvars -disable-iv-rewrite: handle cloning binary operators that cannot overflow.

llvm-svn: 134177

indvars -disable-iv-rewrite: handle an edge case involving identity phis.

llvm-svn: 134124

indvars -disable-iv-rewrite: insert new trunc instructions carefully.

llvm-svn: 134112