[SCEV] createAddRecFromPHI: Optimize for the most common case.

Summary:
The existing implementation creates a symbolic SCEV expression every
time we analyze a phi node and then has to remove it, whe

[SCEV] createAddRecFromPHI: Optimize for the most common case.

Summary:
The existing implementation creates a symbolic SCEV expression every
time we analyze a phi node and then has to remove it, when the analysis
is finished. This is very expensive, and in most of the cases it's also
unnecessary. According to the data I collected, ~60-70% of analyzed phi
nodes (measured on SPEC) have the following form:
PN = phi(Start, OP(Self, Constant))
Handling such cases separately significantly speeds this up.

Reviewers: sanjoy, pete

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D32663

llvm-svn: 302096

show more ...

Rename isKnownNotFullPoison to programUndefinedIfPoison; NFC

Summary:
programUndefinedIfPoison makes more sense, given what the function
does; and I'm about to add a function with a name similar to

Rename isKnownNotFullPoison to programUndefinedIfPoison; NFC

Summary:
programUndefinedIfPoison makes more sense, given what the function
does; and I'm about to add a function with a name similar to
isKnownNotFullPoison (so do the rename to avoid confusion).

Reviewers: broune, majnemer, bjarke.roune

Reviewed By: broune

Subscribers: mcrosier, llvm-commits, mzolotukhin

Differential Revision: https://reviews.llvm.org/D30444

llvm-svn: 301776

show more ...

[SCEV] Use early exit in createAddRecFromPHI. NFC.

llvm-svn: 301703

Kill off the old SimplifyInstruction API by converting remaining users.

llvm-svn: 301673

[ValueTracking] Introduce a KnownBits struct to wrap the two APInts for computeKnownBits

This patch introduces a new KnownBits struct that wraps the two APInt used by computeKnownBits. This allows u

[ValueTracking] Introduce a KnownBits struct to wrap the two APInts for computeKnownBits

This patch introduces a new KnownBits struct that wraps the two APInt used by computeKnownBits. This allows us to treat them as more of a unit.

Initially I've just altered the signatures of computeKnownBits and InstCombine's simplifyDemandedBits to pass a KnownBits reference instead of two separate APInt references. I'll do similar to the SelectionDAG version of computeKnownBits/simplifyDemandedBits as a separate patch.

I've added a constructor that allows initializing both APInts to the same bit width with a starting value of 0. This reduces the repeated pattern of initializing both APInts. Once place default constructed the APInts so I added a default constructor for those cases.

Going forward I would like to add more methods that will work on the pairs. For example trunc, zext, and sext occur on both APInts together in several places. We should probably add a clear method that can be used to clear both pieces. Maybe a method to check for conflicting information. A method to return (Zero|One) so we don't write it out everywhere. Maybe a method for (Zero|One).isAllOnesValue() to determine if all bits are known. I'm sure there are many other methods we can come up with.

Differential Revision: https://reviews.llvm.org/D32376

llvm-svn: 301432

show more ...

Revert "[SCEV] Enable SCEV verification by default in EXPENSIVE_CHECKS builds"

This reverts commit r301150. It breaks CodeGen/Hexagon/hwloop-wrap2.ll, reverting
while I investigate.

llvm-svn: 3011

Revert "[SCEV] Enable SCEV verification by default in EXPENSIVE_CHECKS builds"

This reverts commit r301150. It breaks CodeGen/Hexagon/hwloop-wrap2.ll, reverting
while I investigate.

llvm-svn: 301154

show more ...

Fix unused variables / fields warnings in release builds

llvm-svn: 301151

[SCEV] Enable SCEV verification by default in EXPENSIVE_CHECKS builds

llvm-svn: 301150

[SCEV] Fix exponential time complexity by caching

llvm-svn: 301149

[SCEV] Move towards a verifier without false positives

This change reboots SCEV's current (off by default) verification logic
to avoid false failures. Instead of stringifying trip counts, it maps
o

[SCEV] Move towards a verifier without false positives

This change reboots SCEV's current (off by default) verification logic
to avoid false failures. Instead of stringifying trip counts, it maps
old and new trip counts to the same ScalarEvolution "universe" and
asks ScalarEvolution to compute the difference between them. If the
difference comes out to be a non-zero constant, then (barring some
corner cases) we *know* we messed up.

I've not yet enabled this by default since it hits an exponential time
issue in SCEV, but once I fix that, I'll flip it on by default in
EXPENSIVE_CHECKS builds.

llvm-svn: 301146

show more ...

Revert r300746 (SCEV analysis for or instructions).

There have been multiple reports of this causing problems: a
compile-time explosion on the LLVM testsuite, and a stack
overflow for an opencl kern

Revert r300746 (SCEV analysis for or instructions).

There have been multiple reports of this causing problems: a
compile-time explosion on the LLVM testsuite, and a stack
overflow for an opencl kernel.

llvm-svn: 300928

show more ...

[APInt] Rename getSignBit to getSignMask

getSignBit is a static function that creates an APInt with only the sign bit set. getSignMask seems like a better name to convey its functionality. In fact s

[APInt] Rename getSignBit to getSignMask

getSignBit is a static function that creates an APInt with only the sign bit set. getSignMask seems like a better name to convey its functionality. In fact several places use it and then store in an APInt named SignMask.

Differential Revision: https://reviews.llvm.org/D32108

llvm-svn: 300856

show more ...

[SCEV] Make SCEV or modeling more aggressive.

Use haveNoCommonBitsSet to figure out whether an "or" instruction
is equivalent to addition. This handles more cases than just
checking for a constant o

[SCEV] Make SCEV or modeling more aggressive.

Use haveNoCommonBitsSet to figure out whether an "or" instruction
is equivalent to addition. This handles more cases than just
checking for a constant on the RHS.

Differential Revision: https://reviews.llvm.org/D32239

llvm-svn: 300746

show more ...

[APInt] Use lshrInPlace to replace lshr where possible

This patch uses lshrInPlace to replace code where the object that lshr is called on is being overwritten with the result.

This adds an lshrInP

[APInt] Use lshrInPlace to replace lshr where possible

This patch uses lshrInPlace to replace code where the object that lshr is called on is being overwritten with the result.

This adds an lshrInPlace(const APInt &) version as well.

Differential Revision: https://reviews.llvm.org/D32155

llvm-svn: 300566

show more ...

[SCEV] Fix another unused variable warning in release builds.

llvm-svn: 300500

Fix an unused variable error in rL300494.

llvm-svn: 300499

[SCEV] Add a local cache for getZeroExtendExpr and getSignExtendExpr to prevent
the exponential behavior.

The patch is to fix PR32043. Functions getZeroExtendExpr and getSignExtendExpr
may call them

[SCEV] Add a local cache for getZeroExtendExpr and getSignExtendExpr to prevent
the exponential behavior.

The patch is to fix PR32043. Functions getZeroExtendExpr and getSignExtendExpr
may call themselves recursively more than once. This is potentially a 2^N
complexity behavior. The exponential behavior was not commonly exposed before
because of existing global cache mechnism like UniqueSCEVs or some early return
mechanism when flags FlagNSW or FlagNUW are seen. However, we still have case
which can expose the exponential behavior, like the case in PR32043, so we add
a local cache in getZeroExtendExpr and getSignExtendExpr. If the input of the
functions -- SCEV and type pair have been seen before, we can find the extended
expression directly in the local cache.

Differential Revision: https://reviews.llvm.org/D30350

llvm-svn: 300494

show more ...

[APInt] Move isMask and isShiftedMask out of APIntOps and into the APInt class. Implement them without memory allocation for multiword

This moves the isMask and isShiftedMask functions to be class m

[APInt] Move isMask and isShiftedMask out of APIntOps and into the APInt class. Implement them without memory allocation for multiword

This moves the isMask and isShiftedMask functions to be class methods. They now use the MathExtras.h function for single word size and leading/trailing zeros/ones or countPopulation for the multiword size. The previous implementation made multiple temorary memory allocations to do the bitwise arithmetic operations to match the MathExtras.h implementation.

Differential Revision: https://reviews.llvm.org/D31565

llvm-svn: 299362

show more ...

[APInt] Remove the mul/urem/srem/udiv/sdiv functions from the APIntOps namespace. Replace the few usages with calls to the class methods. NFC

llvm-svn: 299292

[ScalarEvolution] Re-enable Predicate implication from operations

The patch rL298481 was reverted due to crash on clang-with-lto-ubuntu build.
The reason of the crash was type mismatch between eithe

[ScalarEvolution] Re-enable Predicate implication from operations

The patch rL298481 was reverted due to crash on clang-with-lto-ubuntu build.
The reason of the crash was type mismatch between either a or b and RHS in the following situation:

LHS = sext(a +nsw b) > RHS.

This is quite rare, but still possible situation. Normally we need to cast all {a, b, RHS} to their widest type.
But we try to avoid creation of new SCEV that are not constants to avoid initiating recursive analysis that
can take a lot of time and/or cache a bad value for iterations number. To deal with this, in this patch we
reject this case and will not try to analyze it if the type of sum doesn't match with the type of RHS. In this
situation we don't need to create any non-constant SCEVs.

This patch also adds an assertion to the method IsProvedViaContext so that we could fail on it and not
go further into range analysis etc (because in some situations these analyzes succeed even when the passed
arguments have wrong types, what should not normally happen).

The patch also contains a fix for a problem with too narrow scope of the analysis caused by wrong
usage of predicates in recursive invocations.

The regression test on the said failure: test/Analysis/ScalarEvolution/implied-via-addition.ll

Reviewers: reames, apilipenko, anna, sanjoy

Reviewed By: sanjoy

Subscribers: mzolotukhin, mehdi_amini, llvm-commits

Differential Revision: https://reviews.llvm.org/D31238

llvm-svn: 299205

show more ...

Spelling mistakes in comments. NFCI.

llvm-svn: 299197

Revert "[ScalarEvolution] Re-enable Predicate implication from operations"

This reverts commit rL298690

Causes failures on clang.

llvm-svn: 298693

[ScalarEvolution] Re-enable Predicate implication from operations

The patch rL298481 was reverted due to crash on clang-with-lto-ubuntu build.
The reason of the crash was type mismatch between eithe

[ScalarEvolution] Re-enable Predicate implication from operations

The patch rL298481 was reverted due to crash on clang-with-lto-ubuntu build.
The reason of the crash was type mismatch between either a or b and RHS in the following situation:

LHS = sext(a +nsw b) > RHS.

This is quite rare, but still possible situation. Normally we need to cast all {a, b, RHS} to their widest type.
But we try to avoid creation of new SCEV that are not constants to avoid initiating recursive analysis that
can take a lot of time and/or cache a bad value for iterations number. To deal with this, in this patch we
reject this case and will not try to analyze it if the type of sum doesn't match with the type of RHS. In this
situation we don't need to create any non-constant SCEVs.

This patch also adds an assertion to the method IsProvedViaContext so that we could fail on it and not
go further into range analysis etc (because in some situations these analyzes succeed even when the passed
arguments have wrong types, what should not normally happen).

The patch also contains a fix for a problem with too narrow scope of the analysis caused by wrong
usage of predicates in recursive invocations.

The regression test on the said failure: test/Analysis/ScalarEvolution/implied-via-addition.ll

llvm-svn: 298690

show more ...

Model ashr(shl(x, n), m) as mul(x, 2^(n-m)) when n > m

Given below case:

%y = shl %x, n
%z = ashr %y, m

when n = m, SCEV models it as sext(trunc(x)). This patch tries to handle
the case where

Model ashr(shl(x, n), m) as mul(x, 2^(n-m)) when n > m

Given below case:

%y = shl %x, n
%z = ashr %y, m

when n = m, SCEV models it as sext(trunc(x)). This patch tries to handle
the case where n > m by using sext(mul(trunc(x), 2^(n-m)))) as the SCEV
expression.

llvm-svn: 298631

show more ...

revert test commit r298629

llvm-svn: 298630