Add a utility function that detects whether a loop is guaranteed to be finite.

Use it to safely handle less-than-or-equals-to exit conditions in loops. These
also occur when the loop exit branch is

Add a utility function that detects whether a loop is guaranteed to be finite.

Use it to safely handle less-than-or-equals-to exit conditions in loops. These
also occur when the loop exit branch is exit on true because SCEV inverses the
icmp predicate.

Use it again to handle non-zero strides, but only with an unsigned comparison
in the exit condition.

llvm-svn: 59528

show more ...

Remove unused variable.

llvm-svn: 59515

Don't brute-force analyze cubic or higher polynomials.

If this patch causes a performance regression for anyone, please let me know,
and it can be fixed in a different way with much more effort.

ll

Don't brute-force analyze cubic or higher polynomials.

If this patch causes a performance regression for anyone, please let me know,
and it can be fixed in a different way with much more effort.

llvm-svn: 59384

show more ...

Silence unused variable warning.

llvm-svn: 59064

Don't crash analyzing certain quadratics (addrec of {X,+,Y,+,1}).
We're still waiting on code that actually analyzes them properly.

llvm-svn: 58592

Disallow the construction of SCEVs with could-not-compute operands. Catch CNCs
returned by BinomialCoefficient and don't try to operate with them. This
replaces the previous fix for PR2857.

llvm-svn

Disallow the construction of SCEVs with could-not-compute operands. Catch CNCs
returned by BinomialCoefficient and don't try to operate with them. This
replaces the previous fix for PR2857.

llvm-svn: 57431

show more ...

Allow the construction of SCEVs with SCEVCouldNotCompute operands, by
implementing folding. Fixes PR2857.

llvm-svn: 57049

Finally re-apply r46959. This is made feasible by the combination
of r56230, r56232, and r56246.

llvm-svn: 56247

Improve instcombine's handling of integer min and max in two ways:
- Recognize expressions like "x > -1 ? x : 0" as min/max and turn them
into expressions like "x < 0 ? 0 : x", which is easily re

Improve instcombine's handling of integer min and max in two ways:
- Recognize expressions like "x > -1 ? x : 0" as min/max and turn them
into expressions like "x < 0 ? 0 : x", which is easily recognizable
as a min/max operation.
- Refrain from folding expression like "y/2 < 1" to "y < 2" when the
comparison is being used as part of a min or max idiom, like
"y/2 < 1 ? 1 : y/2". In that case, the division has another use, so
folding doesn't eliminate it, and obfuscates the min/max, making it
harder to recognize as a min/max operation.

These benefit ScalarEvolution, CodeGen, and anything else that wants to
recognize integer min and max.

llvm-svn: 56246

show more ...

Teach ScalarEvolution to consider loop preheaders in the search for
an if statement that guards a loop, to allow indvars to avoid smax
operations in more situations.

llvm-svn: 56232

Fix WriteAsOperand to not emit a leading space character. Adjust
its callers to emit a space character before calling it when a
space is needed.

This fixes several spurious whitespace issues in
Scal

Fix WriteAsOperand to not emit a leading space character. Adjust
its callers to emit a space character before calling it when a
space is needed.

This fixes several spurious whitespace issues in
ScalarEvolution's debug dumps. See the test changes for
examples.

This also fixes odd space-after-tab indentation in the output
for switch statements, and changes calls from being printed like
this:
call void @foo( i32 %x )
to this:
call void @foo(i32 %x)

llvm-svn: 56196

show more ...

Extend ScalarEvolution's executesAtLeastOnce logic to be able to
continue past the first conditional branch when looking for a
relevant test. This helps it avoid using MAX expressions in
loop trip co

Extend ScalarEvolution's executesAtLeastOnce logic to be able to
continue past the first conditional branch when looking for a
relevant test. This helps it avoid using MAX expressions in
loop trip counts in more cases.

llvm-svn: 54697

show more ...

Canonicalize nested AddRecs in by nesting them in order of loop depth.

llvm-svn: 54545

PR2621: Improvements to the SCEV AddRec binomial expansion. This
version uses a new algorithm for evaluating the binomial coefficients
which is significantly more efficient for AddRecs of more tha

PR2621: Improvements to the SCEV AddRec binomial expansion. This
version uses a new algorithm for evaluating the binomial coefficients
which is significantly more efficient for AddRecs of more than 2 terms
(see the comments in the code for details on how the algorithm works).
It also fixes some bugs: it removes the arbitrary length restriction for
AddRecs, it fixes the silent generation of incorrect code for AddRecs
which require a wide calculation width, and it fixes an issue where we
were incorrectly truncating the iteration count too far when evaluating
an AddRec expression narrower than the induction variable.

There are still a few related issues I know of: I think there's
still an issue with the SCEVExpander expansion of AddRec in terms of
the width of the induction variable used. The hack to avoid generating
too-wide integers shouldn't be necessary; instead, the callers should be
considering the cost of the expansion before expanding it (in addition
to not expanding too-wide integers, we might not want to expand
expressions that are really expensive, especially when optimizing for
size; calculating an length-17 32-bit AddRec currently generates about 250
instructions of straight-line code on X86). Also, for long 32-bit
AddRecs on X86, CodeGen really sucks at scheduling the code. I'm planning on
filing follow-up PRs for these issues.

llvm-svn: 54332

show more ...

Another SCEV issue from PR2607; essentially the same issue, but this
time applying to the implicit comparison in smin expressions. The
correct way to transform an inequality into the opposite
ineq

Another SCEV issue from PR2607; essentially the same issue, but this
time applying to the implicit comparison in smin expressions. The
correct way to transform an inequality into the opposite
inequality, either signed or unsigned, is with a not expression.

I looked through the SCEV code, and I don't think there are any more
occurrences of this issue.

llvm-svn: 54194

show more ...

Fix for PR2607: SCEV miscomputing the loop count for loops with an
SGT exit condition. Essentially, the correct way to flip an inequality
in 2's complement is the not operator, not the negation op

Fix for PR2607: SCEV miscomputing the loop count for loops with an
SGT exit condition. Essentially, the correct way to flip an inequality
in 2's complement is the not operator, not the negation operator.
That said, the difference only affects cases involving INT_MIN.

Also, enhance the pre-test search logic to be a bit smarter about
inequalities flipped with a not operator, so it can eliminate the smax
from the iteration count for simple loops.

llvm-svn: 54184

show more ...

Revert r53812 -- premature. LegalizeTypes isn't actually on yet!

llvm-svn: 53816

Switch on the use of arbitrary precision integers in scalar evolution. This will
bail after 256-bits to avoid producing code that the backends can't handle.
Previously, we capped it at 64-bits, prefe

Switch on the use of arbitrary precision integers in scalar evolution. This will
bail after 256-bits to avoid producing code that the backends can't handle.
Previously, we capped it at 64-bits, preferring to miscompile in those cases.

This change also reverts much of r52248 because the invariants the code was
expecting are now being met.

llvm-svn: 53812

show more ...

This header isn't necessary now.

llvm-svn: 53811

Fix PR2088. Use modulo linear equation solver to compute loop iteration
count.

llvm-svn: 53810

Correct this inversion!
I swear that didn't show up in svn diff...

llvm-svn: 53587

Fix up comments.

llvm-svn: 53586

Stop creating extraneous smax/umax in SCEV. This removes a regression where we
started complicating many loops ('for' loops, in fact).

llvm-svn: 53508

Remove getValueRange from SCEV. It wasn't doing anything there anyways, and a
more complete version is now available from the LoopVR pass.

llvm-svn: 53269

Handle 'lshr' instruction with SCEVUDiv object.
Comment the xor %x, -1 case.

llvm-svn: 53167