Add a basic verifier for SCEV's backedge taken counts.

Enabled with -verify-scev. This could be extended significantly but hopefully
catches the common cases now. Note that it's not enabled by defau

Add a basic verifier for SCEV's backedge taken counts.

Enabled with -verify-scev. This could be extended significantly but hopefully
catches the common cases now. Note that it's not enabled by default in any
configuration because the way it tries to distinguish SCEVs is still fragile and
may produce false positives. Also the test-suite isn't clean yet, one example
is that it fails if a pass drops an NSW bit but it's still present in SCEV's
cached. Cleaning up all those cases will take some time.

llvm-svn: 166786

show more ...

getSmallConstantTripMultiple should never return zero.

When the trip count is -1, getSmallConstantTripMultiple could return zero,
and this would cause runtime loop unrolling to assert. Instead of re

getSmallConstantTripMultiple should never return zero.

When the trip count is -1, getSmallConstantTripMultiple could return zero,
and this would cause runtime loop unrolling to assert. Instead of returning
zero, one is now returned (consistent with the existing overflow cases).
Fixes PR14167.

llvm-svn: 166612

show more ...

Add in support for getIntPtrType to get the pointer type based on the address space.
This checkin also adds in some tests that utilize these paths and updates some of the
clients.

llvm-svn: 166578

Move TargetData to DataLayout.

llvm-svn: 165402

Revert 'Fix a typo 'iff' => 'if''. iff is an abreviation of if and only if. See: http://en.wikipedia.org/wiki/If_and_only_if Commit 164767

llvm-svn: 164768

Fix a typo 'iff' => 'if'

llvm-svn: 164767

Release build: guard dump functions with
"#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)"

No functional change. Update r163344.

llvm-svn: 163679

Release build: guard dump functions with "ifndef NDEBUG"

No functional change.

llvm-svn: 163344

Stay rational; don't assert trying to take the square root of a negative value.
If it's negative, the loop is already proven to be infinite. Fixes PR13489!

llvm-svn: 161107

Factor SCEV traversal code so I can use it elsewhere. No functionality.

llvm-svn: 160203

Delete code for folding undefs in ScalarEvolution. It's invalid in
obscure ways, and it isn't actually important in the real world.

llvm-svn: 159969

Reduce use list thrashing by using DenseMap's find_as for maps with ValueHandle keys.

No functionality change.

llvm-svn: 159497

If the step value is a constant zero, the loop isn't going to terminate. Fixes
the assert reported in PR13228!

llvm-svn: 159393

Fix typos found by http://github.com/lyda/misspell-check

llvm-svn: 157885

Make sure that we're dealing with a binary SCEVExpr when simplifying.

llvm-svn: 157704

Teach SCEV's icmp simplification logic that a-b == 0 is equivalent to a == b.

This also required making recursive simplifications until
nothing changes or a hard limit (currently 3) is hit.

With th

Teach SCEV's icmp simplification logic that a-b == 0 is equivalent to a == b.

This also required making recursive simplifications until
nothing changes or a hard limit (currently 3) is hit.

With the simplification in place indvars can canonicalize
loops of the form
for (unsigned i = 0; i < a-b; ++i)
into
for (unsigned i = 0; i != a-b; ++i)
which used to fail because SCEV created a weird umax expr
for the backedge taken count.

llvm-svn: 157701

show more ...

SCEV: Handle a corner case reducing AddRecExpr * AddRecExpr

If integer overflow causes one of the terms to reach zero, that can
force the entire expression to zero.

Fixes PR12929: cast<Ty>() argume

SCEV: Handle a corner case reducing AddRecExpr * AddRecExpr

If integer overflow causes one of the terms to reach zero, that can
force the entire expression to zero.

Fixes PR12929: cast<Ty>() argument of incompatible type

llvm-svn: 157673

show more ...

Reformat the loop that does AddRecExpr * AddRecExpr reduction.

No functionality.

llvm-svn: 157672

SCEV: Add MarkPendingLoopPredicates to avoid recursive isImpliedCond.

getUDivExpr attempts to simplify by checking for overflow.
isLoopEntryGuardedByCond then evaluates the loop predicate which
may

SCEV: Add MarkPendingLoopPredicates to avoid recursive isImpliedCond.

getUDivExpr attempts to simplify by checking for overflow.
isLoopEntryGuardedByCond then evaluates the loop predicate which
may lead to the same getUDivExpr causing endless recursion.

Fixes PR12868: clang 3.2 segmentation fault.

llvm-svn: 157092

show more ...

reuse the result of some expensive computations in getSignExtendExpr() and getZeroExtendExpr()
this gives a speedup of > 80 in a debug build in the test case of PR12825 (php_sha512_crypt_r)

llvm-svn

reuse the result of some expensive computations in getSignExtendExpr() and getZeroExtendExpr()
this gives a speedup of > 80 in a debug build in the test case of PR12825 (php_sha512_crypt_r)

llvm-svn: 156849

show more ...

minor simplification to code: Ty is already a SCEV type; don't need to run getEffectiveSCEVType() twice

llvm-svn: 156823

Rewrite ScalarEvolution::hasOperand to use an explicit worklist instead
of recursion, to avoid excessive stack usage on deep expressions.

llvm-svn: 156554

Revert "SCEV: When expanding a GEP the final addition to the base pointer has NUW but not NSW."

This isn't right either, reverting for now.

llvm-svn: 154910

SCEV: When expanding a GEP the final addition to the base pointer has NUW but not NSW.

Found by inspection.

llvm-svn: 154262

Always compute all the bits in ComputeMaskedBits.
This allows us to keep passing reduced masks to SimplifyDemandedBits, but
know about all the bits if SimplifyDemandedBits fails. This allows instcomb

Always compute all the bits in ComputeMaskedBits.
This allows us to keep passing reduced masks to SimplifyDemandedBits, but
know about all the bits if SimplifyDemandedBits fails. This allows instcombine
to simplify cases like the one in the included testcase.

llvm-svn: 154011

show more ...