Revert r260086 and r260085. They have broken the memory
sanitizer bots.

llvm-svn: 260087

[SCEV][LAA] Add no wrap SCEV predicates and use use them to improve strided pointer detection

Summary:
This change adds no wrap SCEV predicates with:
- support for runtime checking
- support for

[SCEV][LAA] Add no wrap SCEV predicates and use use them to improve strided pointer detection

Summary:
This change adds no wrap SCEV predicates with:
- support for runtime checking
- support for expression rewriting:
(sext ({x,+,y}) -> {sext(x),+,sext(y)}
(zext ({x,+,y}) -> {zext(x),+,sext(y)}

Note that we are sign extending the increment of the SCEV, even for
the zext case. This is needed to cover the fairly common case where y would
be a (small) negative integer. In order to do this, this change adds two new
flags: nusw and nssw that are applicable to AddRecExprs and permit the
transformations above.

We also change isStridedPtr in LAA to be able to make use of
these predicates. With this feature we should now always be able to
work around overflow issues in the dependence analysis.

Reviewers: mzolotukhin, sanjoy, anemet

Subscribers: mzolotukhin, sanjoy, llvm-commits, rengolin, jmolloy, hfinkel

Differential Revision: http://reviews.llvm.org/D15412

llvm-svn: 260085

show more ...

[SCEV] Add boolean accessors for NSW, NUW and NW; NFC

llvm-svn: 259809

[SCEV] Try to reuse existing value during SCEV expansion

Current SCEV expansion will expand SCEV as a sequence of operations
and doesn't utilize the value already existed. This will introduce
redund

[SCEV] Try to reuse existing value during SCEV expansion

Current SCEV expansion will expand SCEV as a sequence of operations
and doesn't utilize the value already existed. This will introduce
redundent computation which may not be cleaned up throughly by
following optimizations.

This patch introduces an ExprValueMap which is a map from SCEV to the
set of equal values with the same SCEV. When a SCEV is expanded, the
set of values is checked and reused whenever possible before generating
a sequence of operations.

The original commit triggered regressions in Polly tests. The regressions
exposed two problems which have been fixed in current version.

1. Polly will generate a new function based on the old one. To generate an
instruction for the new function, it builds SCEV for the old instruction,
applies some tranformation on the SCEV generated, then expands the transformed
SCEV and insert the expanded value into new function. Because SCEV expansion
may reuse value cached in ExprValueMap, the value in old function may be
inserted into new function, which is wrong.
In SCEVExpander::expand, there is a logic to check the cached value to
be used should dominate the insertion point. However, for the above
case, the check always passes. That is because the insertion point is
in a new function, which is unreachable from the old function. However
for unreachable node, DominatorTreeBase::dominates thinks it will be
dominated by any other node.
The fix is to simply add a check that the cached value to be used in
expansion should be in the same function as the insertion point instruction.

2. When the SCEV is of scConstant type, expanding it directly is cheaper than
reusing a normal value cached. Although in the cached value set in ExprValueMap,
there is a Constant type value, but it is not easy to find it out -- the cached
Value set is not sorted according to the potential cost. Existing reuse logic
in SCEVExpander::expand simply chooses the first legal element from the cached
value set.
The fix is that when the SCEV is of scConstant type, don't try the reuse
logic. simply expand it.

Differential Revision: http://reviews.llvm.org/D12090

llvm-svn: 259736

show more ...

Revert r259662, which caused regressions on polly tests.

llvm-svn: 259675

[SCEV] Try to reuse existing value during SCEV expansion

Current SCEV expansion will expand SCEV as a sequence of operations
and doesn't utilize the value already existed. This will introduce
redund

[SCEV] Try to reuse existing value during SCEV expansion

Current SCEV expansion will expand SCEV as a sequence of operations
and doesn't utilize the value already existed. This will introduce
redundent computation which may not be cleaned up throughly by
following optimizations.

This patch introduces an ExprValueMap which is a map from SCEV to the
set of equal values with the same SCEV. When a SCEV is expanded, the
set of values is checked and reused whenever possible before generating
a sequence of operations.

Differential Revision: http://reviews.llvm.org/D12090

llvm-svn: 259662

show more ...

[SCEV] Clean up isKnownPredicateViaConstantRanges; NFCI

- ScalarEvolution::isKnownPredicateViaConstantRanges duplicates some
logic already present in ConstantRange, use ConstantRange for those

[SCEV] Clean up isKnownPredicateViaConstantRanges; NFCI

- ScalarEvolution::isKnownPredicateViaConstantRanges duplicates some
logic already present in ConstantRange, use ConstantRange for those
bits.

- In some cases ScalarEvolution::isKnownPredicateViaConstantRanges
returns `false` to mean "definitely false" (e.g. see the
`LHSRange.getSignedMin().sge(RHSRange.getSignedMax())` case for
`ICmpInst::ICMP_SLT`), but for `isKnownPredicateViaConstantRanges`,
`false` actually means "don't know". Get rid of this extra bit of
code to avoid confusion.

llvm-svn: 259401

show more ...

[SCEV] Rename isKnownPredicateWithRanges; NFC

Make it obvious that it uses constant ranges, and use `Via` instead of
`With`, like other similar functions in SCEV.

llvm-svn: 259400

[opaque pointer types] [NFC] Add an explicit type argument to ConstantFoldLoadFromConstPtr.

Reviewers: mjacob, dblaikie

Subscribers: llvm-commits

Differential Revision: http://reviews.llvm.org/D16

[opaque pointer types] [NFC] Add an explicit type argument to ConstantFoldLoadFromConstPtr.

Reviewers: mjacob, dblaikie

Subscribers: llvm-commits

Differential Revision: http://reviews.llvm.org/D16418

llvm-svn: 258472

show more ...

Change ConstantFoldInstOperands to take Instruction instead of opcode and type. NFC.

Summary:
The previous form, taking opcode and type, is moved to an internal
helper and the new form, taking an i

Change ConstantFoldInstOperands to take Instruction instead of opcode and type. NFC.

Summary:
The previous form, taking opcode and type, is moved to an internal
helper and the new form, taking an instruction, is a wrapper around this
helper.

Although this is a slight cleanup on its own, the main motivation is to
refactor the constant folding API to ease migration to opaque pointers.
This will be follow-up work.

Reviewers: eddyb

Subscribers: dblaikie, llvm-commits

Differential Revision: http://reviews.llvm.org/D16383

llvm-svn: 258391

show more ...

[SCEV] Fix PR26207

In some cases, the max backedge taken count can be more conservative
than the exact backedge taken count (for instance, because
ScalarEvolution::getRange is not control-flow sensi

[SCEV] Fix PR26207

In some cases, the max backedge taken count can be more conservative
than the exact backedge taken count (for instance, because
ScalarEvolution::getRange is not control-flow sensitive whereas
computeExitLimitFromICmp can be). In these cases,
computeExitLimitFromCond (specifically the bit that deals with `and` and
`or` instructions) can create an ExitLimit instance with a
`SCEVCouldNotCompute` max backedge count expression, but a computable
exact backedge count expression. This violates an implicit SCEV
assumption: a computable exact BE count should imply a computable max BE
count.

This change

- Makes the above implicit invariant explicit by adding an assert to
ExitLimit's constructor

- Changes `computeExitLimitFromCond` to be more robust around
conservative max backedge counts

llvm-svn: 258184

show more ...

[SCEV] Use range-for; NFC

llvm-svn: 258183

[opaque pointer types] [NFC] GEP: replace get(Pointer)ElementType uses with get{Source,Result}ElementType.

Summary:
GEPOperator: provide getResultElementType alongside getSourceElementType.
This is

[opaque pointer types] [NFC] GEP: replace get(Pointer)ElementType uses with get{Source,Result}ElementType.

Summary:
GEPOperator: provide getResultElementType alongside getSourceElementType.
This is made possible by adding a result element type field to GetElementPtrConstantExpr, which GetElementPtrInst already has.

GEP: replace get(Pointer)ElementType uses with get{Source,Result}ElementType.

Reviewers: mjacob, dblaikie

Subscribers: llvm-commits

Differential Revision: http://reviews.llvm.org/D16275

llvm-svn: 258145

show more ...

Fix SCEV r256338.

llvm-svn: 256344

[SCEV] Fix getLoopBackedgeTakenCounts

The way `getLoopBackedgeTakenCounts` is written right now isn't
correct. It will try to compute and store the BE counts of a Loop
#{child loop} number of times

[SCEV] Fix getLoopBackedgeTakenCounts

The way `getLoopBackedgeTakenCounts` is written right now isn't
correct. It will try to compute and store the BE counts of a Loop
#{child loop} number of times (which may be zero).

llvm-svn: 256338

show more ...

[SCEV] Add and use SCEVConstant::getAPInt; NFCI

llvm-svn: 255921

Revert r254592 (virtual dtor in SCEVPredicate).

Clang has better diagnostics in this case. It is not necessary therefore
to change the destructor to avoid what is effectively an invalid warning
in

Revert r254592 (virtual dtor in SCEVPredicate).

Clang has better diagnostics in this case. It is not necessary therefore
to change the destructor to avoid what is effectively an invalid warning
in gcc. Instead, better handle the warning flags given to the compiler.

llvm-svn: 255905

show more ...

Re-commit r255115, with the PredicatedScalarEvolution class moved to
ScalarEvolution.h, in order to avoid cyclic dependencies between the Transform
and Analysis modules:

[LV][LAA] Add a layer over S

Re-commit r255115, with the PredicatedScalarEvolution class moved to
ScalarEvolution.h, in order to avoid cyclic dependencies between the Transform
and Analysis modules:

[LV][LAA] Add a layer over SCEV to apply run-time checked knowledge on SCEV expressions

Summary:
This change creates a layer over ScalarEvolution for LAA and LV, and centralizes the
usage of SCEV predicates. The SCEVPredicatedLayer takes the statically deduced knowledge
by ScalarEvolution and applies the knowledge from the SCEV predicates. The end goal is
that both LAA and LV should use this interface everywhere.

This also solves a problem involving the result of SCEV expression rewritting when
the predicate changes. Suppose we have the expression (sext {a,+,b}) and two predicates
P1: {a,+,b} has nsw
P2: b = 1.

Applying P1 and then P2 gives us {a,+,1}, while applying P2 and the P1 gives us
sext({a,+,1}) (the AddRec expression was changed by P2 so P1 no longer applies).
The SCEVPredicatedLayer maintains the order of transformations by feeding back
the results of previous transformations into new transformations, and therefore
avoiding this issue.

The SCEVPredicatedLayer maintains a cache to remember the results of previous
SCEV rewritting results. This also has the benefit of reducing the overall number
of expression rewrites.

Reviewers: mzolotukhin, anemet

Subscribers: jmolloy, sanjoy, llvm-commits

Differential Revision: http://reviews.llvm.org/D14296

llvm-svn: 255122

show more ...

[SCEV] Use for-each; NFC

llvm-svn: 255069

[SCEV] Move some struct declarations inside functions; NFC

Reduces the scope over which the struct is visible, making its usages
obvious. I did not move structs in cases where this wasn't a clear
w

[SCEV] Move some struct declarations inside functions; NFC

Reduces the scope over which the struct is visible, making its usages
obvious. I did not move structs in cases where this wasn't a clear
win (the struct is too large, or is grouped in some other interesting
way).

llvm-svn: 255003

show more ...

[SCEV] Fix indentation; NFC

llvm-svn: 255002

Fix class SCEVPredicate has virtual functions and accessible non-virtual destructor.

It is not enough to simply make the destructor virtual since there is a g++ 4.7
issue (see https://gcc.gnu.org/bu

Fix class SCEVPredicate has virtual functions and accessible non-virtual destructor.

It is not enough to simply make the destructor virtual since there is a g++ 4.7
issue (see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=53613) that throws the
error "looser throw specifier for ... overridding ~SCEVPredicate() noexcept".

llvm-svn: 254592

show more ...

Introduce a range version of std::find, and use in SCEV

Reviewers: dblaikie, pcc

Subscribers: llvm-commits

Differential Revision: http://reviews.llvm.org/D15064

llvm-svn: 254391

Introduce a range version of std::any_of, and use it in SCEV

Reviewers: dblaikie, pcc

Subscribers: llvm-commits

Differential Revision: http://reviews.llvm.org/D15063

llvm-svn: 254390

[SCEV] Use lambda instead of std::bind; NFC

The lambda is more readable.

llvm-svn: 254276