IR: Change PointerType to derive from Type rather than SequentialType.

As proposed on llvm-dev:
http://lists.llvm.org/pipermail/llvm-dev/2016-October/106640.html

This is for a couple of reasons:

-

IR: Change PointerType to derive from Type rather than SequentialType.

As proposed on llvm-dev:
http://lists.llvm.org/pipermail/llvm-dev/2016-October/106640.html

This is for a couple of reasons:

- Values of type PointerType are unlike the other SequentialTypes (arrays
and vectors) in that they do not hold values of the element type. By moving
PointerType we can unify certain aspects of how the other SequentialTypes
are handled.
- PointerType will have no place in the SequentialType hierarchy once
pointee types are removed, so this is a necessary step towards removing
pointee types.

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

llvm-svn: 288462

show more ...

[PM] Change the static object whose address is used to uniquely identify
analyses to have a common type which is enforced rather than using
a char object and a `void *` type when used as an identifie

[PM] Change the static object whose address is used to uniquely identify
analyses to have a common type which is enforced rather than using
a char object and a `void *` type when used as an identifier.

This has a number of advantages. First, it at least helps some of the
confusion raised in Justin Lebar's code review of why `void *` was being
used everywhere by having a stronger type that connects to documentation
about this.

However, perhaps more importantly, it addresses a serious issue where
the alignment of these pointer-like identifiers was unknown. This made
it hard to use them in pointer-like data structures. We were already
dodging this in dangerous ways to create the "all analyses" entry. In
a subsequent patch I attempted to use these with TinyPtrVector and
things fell apart in a very bad way.

And it isn't just a compile time or type system issue. Worse than that,
the actual alignment of these pointer-like opaque identifiers wasn't
guaranteed to be a useful alignment as they were just characters.

This change introduces a type to use as the "key" object whose address
forms the opaque identifier. This both forces the objects to have proper
alignment, and provides type checking that we get it right everywhere.
It also makes the types somewhat less mysterious than `void *`.

We could go one step further and introduce a truly opaque pointer-like
type to return from the `ID()` static function rather than returning
`AnalysisKey *`, but that didn't seem to be a clear win so this is just
the initial change to get to a reliably typed and aligned object serving
is a key for all the analyses.

Thanks to Richard Smith and Justin Lebar for helping pick plausible
names and avoid making this refactoring many times. =] And thanks to
Sean for the super fast review!

While here, I've tried to move away from the "PassID" nomenclature
entirely as it wasn't really helping and is overloaded with old pass
manager constructs. Now we have IDs for analyses, and key objects whose
address can be used as IDs. Where possible and clear I've shortened this
to just "ID". In a few places I kept "AnalysisID" to make it clear what
was being identified.

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

llvm-svn: 287783

show more ...

Fix comment typos. NFC.

Identified by Pedro Giffuni in PR27636.

llvm-svn: 287490

[SCEV] limit recursion depth of CompareSCEVComplexity

Summary:
CompareSCEVComplexity goes too deep (50+ on a quite a big unrolled loop) and runs almost infinite time.

Added cache of "equal" SCEV pa

[SCEV] limit recursion depth of CompareSCEVComplexity

Summary:
CompareSCEVComplexity goes too deep (50+ on a quite a big unrolled loop) and runs almost infinite time.

Added cache of "equal" SCEV pairs to earlier cutoff of further estimation. Recursion depth limit was also introduced as a parameter.

Reviewers: sanjoy

Subscribers: mzolotukhin, tstellarAMD, llvm-commits

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

llvm-svn: 287232

show more ...

test commit, changed tab to spaces, NFC

llvm-svn: 287116

Analysis: Simplify the ScalarEvolution::getGEPExpr() interface. NFCI.

All existing callers were manually extracting information out of an existing
GEP instruction and passing it to getGEPExpr(). Sim

Analysis: Simplify the ScalarEvolution::getGEPExpr() interface. NFCI.

All existing callers were manually extracting information out of an existing
GEP instruction and passing it to getGEPExpr(). Simplify the interface by
changing it to take a GEPOperator instead.

llvm-svn: 286751

show more ...

[SCEV] Eta reduce some lambdas; NFC

llvm-svn: 286429

[SCEV] Refactor out a useful pattern; NFC

llvm-svn: 286386

[SCEV] Try to order n-ary expressions in CompareValueComplexity

llvm-svn: 285535

[SCEV] In CompareValueComplexity, order global values by their name

llvm-svn: 285529

[SCEV] Use auto for consistency with an upcoming change; NFC

llvm-svn: 285528

[LoopUnroll] Keep the loop test only on the first iteration of max-or-zero loops

When we have a loop with a known upper bound on the number of iterations, and
furthermore know that either the number

[LoopUnroll] Keep the loop test only on the first iteration of max-or-zero loops

When we have a loop with a known upper bound on the number of iterations, and
furthermore know that either the number of iterations will be either exactly
that upper bound or zero, then we can fully unroll up to that upper bound
keeping only the first loop test to check for the zero iteration case.

Most of the work here is in plumbing this 'max-or-zero' information from the
part of scalar evolution where it's detected through to loop unrolling. I've
also gone for the safe default of 'false' everywhere but howManyLessThans which
could probably be improved.

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

llvm-svn: 284818

show more ...

[SCEV] Add a threshold to restrict number of mul operands to be inlined into SCEV

This is to avoid inlining too many multiplication operands into a SCEV, which could
take exponential time in the wo

[SCEV] Add a threshold to restrict number of mul operands to be inlined into SCEV

This is to avoid inlining too many multiplication operands into a SCEV, which could
take exponential time in the worst case.

Reviewers: Sanjoy Das, Mehdi Amini, Michael Zolotukhin

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

llvm-svn: 284784

show more ...

[SCEV] Make CompareValueComplexity a little bit smarter

This helps canonicalization in some cases.

Thanks to Pankaj Chawla for the investigation and the test case!

llvm-svn: 284501

[SCEV] Extract out a helper function; NFC

llvm-svn: 284500

[SCEV] More accurate calculation of max backedge count of some less-than loops

In loops that look something like
i = n;
do {
...
} while(i++ < n+k);
where k is a constant, the maximum backedge

[SCEV] More accurate calculation of max backedge count of some less-than loops

In loops that look something like
i = n;
do {
...
} while(i++ < n+k);
where k is a constant, the maximum backedge count is k (in fact the backedge
count will be either 0 or k, depending on whether n+k wraps). More generally
for LHS < RHS if RHS-(LHS of first comparison) is a constant then the loop will
iterate either 0 or that constant number of times.

This allows for more loop unrolling with the recent upper bound loop unrolling
changes, and I'm working on a patch that will let loop unrolling additionally
make use of the loop being executed either 0 or k times (we need to retain the
loop comparison only on the first unrolled iteration).

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

llvm-svn: 284465

show more ...

[SCEV] Consider delinearization pattern with extension with identity factor

Summary: The delinearization algorithm did not consider terms which had an extension without a multiply factor, i.e. a ide

[SCEV] Consider delinearization pattern with extension with identity factor

Summary: The delinearization algorithm did not consider terms which had an extension without a multiply factor, i.e. a identify factor. We lose cases where size is char type where there will no multiply factor.

Reviewers: sanjoy, grosser

Subscribers: mzolotukhin, Eugene.Zelenko, llvm-commits, mssimpso, sanjoy, grosser

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

llvm-svn: 284378

show more ...

Reapply "[LoopUnroll] Use the upper bound of the loop trip count to fullly unroll a loop"

Reappy r284044 after revert in r284051. Krzysztof fixed the error in r284049.

The original summary:

This p

Reapply "[LoopUnroll] Use the upper bound of the loop trip count to fullly unroll a loop"

Reappy r284044 after revert in r284051. Krzysztof fixed the error in r284049.

The original summary:

This patch tries to fully unroll loops having break statement like this

for (int i = 0; i < 8; i++) {
if (a[i] == value) {
found = true;
break;
}
}

GCC can fully unroll such loops, but currently LLVM cannot because LLVM only
supports loops having exact constant trip counts.

The upper bound of the trip count can be obtained from calling
ScalarEvolution::getMaxBackedgeTakenCount(). Part of the patch is the
refactoring work in SCEV to prevent duplicating code.

The feature of using the upper bound is enabled under the same circumstance
when runtime unrolling is enabled since both are used to unroll loops without
knowing the exact constant trip count.

llvm-svn: 284053

show more ...

Revert "[LoopUnroll] Use the upper bound of the loop trip count to fullly unroll a loop"

This reverts commit r284044.

llvm-svn: 284051

[LoopUnroll] Use the upper bound of the loop trip count to fullly unroll a loop

This patch tries to fully unroll loops having break statement like this

for (int i = 0; i < 8; i++) {
if (a[i] ==

[LoopUnroll] Use the upper bound of the loop trip count to fullly unroll a loop

This patch tries to fully unroll loops having break statement like this

for (int i = 0; i < 8; i++) {
if (a[i] == value) {
found = true;
break;
}
}

GCC can fully unroll such loops, but currently LLVM cannot because LLVM only
supports loops having exact constant trip counts.

The upper bound of the trip count can be obtained from calling
ScalarEvolution::getMaxBackedgeTakenCount(). Part of the patch is the
refactoring work in SCEV to prevent duplicating code.

The feature of using the upper bound is enabled under the same circumstance
when runtime unrolling is enabled since both are used to unroll loops without
knowing the exact constant trip count.

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

llvm-svn: 284044

show more ...

[SCEV] Rely on ConstantRange instead of custom logic; NFCI

This was first landed in rL283058 and subsequenlty reverted since a
change this depends on (rL283057) was buggy and had to be reverted.

ll

[SCEV] Rely on ConstantRange instead of custom logic; NFCI

This was first landed in rL283058 and subsequenlty reverted since a
change this depends on (rL283057) was buggy and had to be reverted.

llvm-svn: 283079

show more ...

Revert r283057 and r283058

They've broken the sanitizer-bootstrap bots. Reverting while I investigate.

Original commit messages:

r283057: "[ConstantRange] Make getEquivalentICmp smarter"

r283058

Revert r283057 and r283058

They've broken the sanitizer-bootstrap bots. Reverting while I investigate.

Original commit messages:

r283057: "[ConstantRange] Make getEquivalentICmp smarter"

r283058: "[SCEV] Rely on ConstantRange instead of custom logic; NFCI"
llvm-svn: 283062

show more ...

Remove duplicated code; NFC

ICmpInst::makeConstantRange does exactly the same thing as
ConstantRange::makeExactICmpRegion.

llvm-svn: 283059

[SCEV] Rely on ConstantRange instead of custom logic; NFCI

llvm-svn: 283058

[SCEV] Remove commented out code; NFC

llvm-svn: 283056