Use more type helper functions

llvm-svn: 193109

Fix creating bitcasts between address spaces in SCEV.

The test before wasn't successfully testing this
since it was missing the datalayout piece to change
the size of the second address space.

llvm

Fix creating bitcasts between address spaces in SCEV.

The test before wasn't successfully testing this
since it was missing the datalayout piece to change
the size of the second address space.

llvm-svn: 193102

show more ...

Remove unused SCEV functions

llvm-svn: 193097

SCEV should use NSW to get trip count for positive nonunit stride loops.

SCEV currently fails to compute loop counts for nonunit stride
loops. This comes up frequently. It prevents loop optimization

SCEV should use NSW to get trip count for positive nonunit stride loops.

SCEV currently fails to compute loop counts for nonunit stride
loops. This comes up frequently. It prevents loop optimization and
forces vectorization to insert extra loop checks.

For example:
void foo(int n, int *x) {
for (int i = 0; i < n; i += 3) {
x[i] = i;
x[i+1] = i+1;
x[i+2] = i+2;
}
}

We need to properly handle the case in which limit > INT_MAX-stride. In
the above case: n > INT_MAX-3. In this case the loop counter will step
beyond the limit and overflow at the same time. However, knowing that
signed integer overlow in undefined, we can assume the loop test
behavior is arbitrary after overflow. This obeys both C undefined
behavior rules, and the more strict LLVM poison value rules.

I'm finally fixing this in response to Hal Finkel's persistence.
The most probable reason that we never optimized this before is that
we were being careful to handle case where the developer expected a
side-effect free infinite loop relying on overflow:

for (int i = 0; i < n; i += s) {
++j;
}
return j;

If INT_MAX+1 is a multiple of s and n > INT_MAX-s, then we might
expect an infinite loop. However there are plenty of ways to achieve
this effect without relying on undefined behavior of signed overflow.

llvm-svn: 193015

show more ...

Minor code simplification

llvm-svn: 191579

Teach ScalarEvolution about pointer address spaces

llvm-svn: 190425

Fix a severe compile time problem when forming large SCEV expressions.

This fix is very lightweight. The same fix already existed for AddRec
but was missing for NAry expressions.

This is obviously

Fix a severe compile time problem when forming large SCEV expressions.

This fix is very lightweight. The same fix already existed for AddRec
but was missing for NAry expressions.

This is obviously an improvement and I'm unsure how to test compile
time problems.

Patch by Xiaoyi Guo!

llvm-svn: 187475

show more ...

Stylistic change.

Thank Nick for figuring out these problems.

llvm-svn: 186146

Use SmallVectorImpl& instead of SmallVector to avoid repeating small vector size.

llvm-svn: 186098

Don't use a potentially expensive shift if all we want is one set bit.

No functionality change.

llvm-svn: 186095

Don't crash in SE dealing with ashr x, -1

ScalarEvolution::getSignedRange uses ComputeNumSignBits from ValueTracking on
ashr instructions. ComputeNumSignBits can return zero, but this case was not
h

Don't crash in SE dealing with ashr x, -1

ScalarEvolution::getSignedRange uses ComputeNumSignBits from ValueTracking on
ashr instructions. ComputeNumSignBits can return zero, but this case was not
handled correctly by the code in getSignedRange which was calling:
APInt::getSignedMinValue(BitWidth).ashr(NS - 1)
with NS = 0, resulting in an assertion failure in APInt::ashr.

Now, we just return the conservative result (as with NS == 1).

Another bug found by llvm-stress.

llvm-svn: 185955

show more ...

Fix a SCEV update problem.

The symptom is seg-fault, and the root cause is that a SCEV contains a SCEVUnknown
which has null-pointer to a llvm::Value.

This is how the problem take place:
=======

Fix a SCEV update problem.

The symptom is seg-fault, and the root cause is that a SCEV contains a SCEVUnknown
which has null-pointer to a llvm::Value.

This is how the problem take place:
===================================
1). In the pristine input IR, there are two relevant instrutions Op1 and Op2,
Op1's corresponding SCEV (denoted as SCEV(op1)) is a SCEVUnknown, and
SCEV(Op2) contains SCEV(Op1). None of these instructions are dead.

Op1 : V1 = ...
...
Op2 : V2 = ... // directly or indirectly (data-flow) depends on Op1

2) Optimizer (LSR in my case) generates an instruction holding the equivalent
value of Op1, making Op1 dead.
Op1': V1' = ...
Op1: V1 = ... ; now dead)
Op2 : V2 = ... //Now deps on Op1', but the SCEV(Op2) still contains SCEV(Op1)

3) Op1 is deleted, and call-back function is called to reset
SCEV(Op1) to indicate it is invalid. However, SCEV(Op2) is not
invalidated as well.

4) Following pass get the cached, invalid SCEV(Op2), and try to manipulate it,
and cause segfault.

The fix:
========
It seems there is no clean yet inexpensive fix. I write to dev-list
soliciting good solution, unforunately no ack. So, I decide to fix this
problem in a brute-force way:

When ScalarEvolution::getSCEV is called, check if the cached SCEV
contains a invalid SCEVUnknow, if yes, remove the cached SCEV, and
re-evaluate the SCEV from scratch.

I compile buch of big *.c and *.cpp, fortunately, I don't see any increase
in compile time.

Misc:
=====
The reduced test-case has 2357 lines of code+other-stuff, too big to commit.

rdar://14283433

llvm-svn: 185843

show more ...

Use SmallVectorImpl::iterator/const_iterator instead of SmallVector to avoid specifying the vector size.

llvm-svn: 185540

Silencing an MSVC warning about */ being found outside of a comment.

llvm-svn: 183175

Prevent loop-unroll from making assumptions about undefined behavior.

Fixes rdar:14036816, PR16130.

There is an opportunity to compute precise trip counts for 'or'
expressions and multi-exit loops.

Prevent loop-unroll from making assumptions about undefined behavior.

Fixes rdar:14036816, PR16130.

There is an opportunity to compute precise trip counts for 'or'
expressions and multi-exit loops.
rdar:14038809: Optimize trip count computation for multi-exit loops.

To do this we need to record the fact that ExitLimit assumes NSW. When
it does not we can safely assume that the loop trip count is the
minimum ExitLimt across all subexpressions and loop exits.

llvm-svn: 183060

show more ...

Fix ScalarEvolution::ComputeExitLimitFromCond for 'or' conditions.

Fixes PR16130 - clang produces incorrect code with loop/expression at -O2.

This is a 2+ year old bug that's now holding up the rel

Fix ScalarEvolution::ComputeExitLimitFromCond for 'or' conditions.

Fixes PR16130 - clang produces incorrect code with loop/expression at -O2.

This is a 2+ year old bug that's now holding up the release. It's a
case where we knowingly made aggressive assumptions about undefined
behavior. These assumptions are wrong when SCEV is computing a
subexpression that does not directly control the branch. With this
fix, we avoid making assumptions in those cases but still optimize the
common case. SCEV's trip count computation for exits controlled by
'or' expressions is now analagous to the trip count computation for
loops with multiple exits. I had already fixed the multiple exit case
to be conservative.

llvm-svn: 182989

show more ...

Fix SCEV forgetMemoizedResults should search and destroy backedge exprs.

Fixes PR15570: SEGV: SCEV back-edge info invalid after dead code removal.

Indvars creates a SCEV expression for the loop's b

Fix SCEV forgetMemoizedResults should search and destroy backedge exprs.

Fixes PR15570: SEGV: SCEV back-edge info invalid after dead code removal.

Indvars creates a SCEV expression for the loop's back edge taken
count, then determines that the comparison is always true and
removes it.

When loop-unroll asks for the expression, it contains a NULL
SCEVUnknkown (as a CallbackVH).

forgetMemoizedResults should invalidate the loop back edges expression.

llvm-svn: 177986

show more ...

Move all of the header files which are involved in modelling the LLVM IR
into their new header subdirectory: include/llvm/IR. This matches the
directory structure of lib, and begins to correct a long

Move all of the header files which are involved in modelling the LLVM IR
into their new header subdirectory: include/llvm/IR. This matches the
directory structure of lib, and begins to correct a long standing point
of file layout clutter in LLVM.

There are still more header files to move here, but I wanted to handle
them in separate commits to make tracking what files make sense at each
layer easier.

The only really questionable files here are the target intrinsic
tablegen files. But that's a battle I'd rather not fight today.

I've updated both CMake and Makefile build systems (I think, and my
tests think, but I may have missed something).

I've also re-sorted the includes throughout the project. I'll be
committing updates to Clang, DragonEgg, and Polly momentarily.

llvm-svn: 171366

show more ...

Use the new script to sort the includes of every file under lib.

Sooooo many of these had incorrect or strange main module includes.
I have manually inspected all of these, and fixed the main module

Use the new script to sort the includes of every file under lib.

Sooooo many of these had incorrect or strange main module includes.
I have manually inspected all of these, and fixed the main module
include to be the nearest plausible thing I could find. If you own or
care about any of these source files, I encourage you to take some time
and check that these edits were sensible. I can't have broken anything
(I strictly added headers, and reordered them, never removed), but they
may not be the headers you'd really like to identify as containing the
API being implemented.

Many forward declarations and missing includes were added to a header
files to allow them to parse cleanly when included first. The main
module rule does in fact have its merits. =]

llvm-svn: 169131

show more ...

Follow up to 168711: It's safe to base this analysis on the found compare, just return the value for the right predicate.

Thanks to Andy for catching this.

llvm-svn: 168921

Improve isImpliedCond comment a bit.

llvm-svn: 168914

SCEV: Even if the latch terminator is foldable we can't deduce the result of an unrelated condition with it.

Fixes PR14432.

llvm-svn: 168711

Revert the series of commits starting with r166578 which introduced the
getIntPtrType support for multiple address spaces via a pointer type,
and also introduced a crasher bug in the constant folder

Revert the series of commits starting with r166578 which introduced the
getIntPtrType support for multiple address spaces via a pointer type,
and also introduced a crasher bug in the constant folder reported in
PR14233.

These commits also contained several problems that should really be
addressed before they are re-committed. I have avoided reverting various
cleanups to the DataLayout APIs that are reasonable to have moving
forward in order to reduce the amount of churn, and minimize the number
of commits that were reverted. I've also manually updated merge
conflicts and manually arranged for the getIntPtrType function to stay
in DataLayout and to be defined in a plausible way after this revert.

Thanks to Duncan for working through this exact strategy with me, and
Nick Lewycky for tracking down the really annoying crasher this
triggered. (Test case to follow in its own commit.)

After discussing with Duncan extensively, and based on a note from
Micah, I'm going to continue to back out some more of the more
problematic patches in this series in order to ensure we go into the
LLVM 3.2 branch with a reasonable story here. I'll send a note to
llvmdev explaining what's going on and why.

Summary of reverted revisions:

r166634: Fix a compiler warning with an unused variable.
r166607: Add some cleanup to the DataLayout changes requested by
Chandler.
r166596: Revert "Back out r166591, not sure why this made it through
since I cancelled the command. Bleh, sorry about this!
r166591: Delete a directory that wasn't supposed to be checked in yet.
r166578: Add in support for getIntPtrType to get the pointer type based
on the address space.
llvm-svn: 167221

show more ...

SCEV validator: Ignore CouldNotCompute/undef on both sides. This is mostly noise and blocks finding more severe bugs.

llvm-svn: 166873

SCEV validator: Add workarounds for some common false positives due to the way it handles strings.

llvm-svn: 166872