[Debuginfo][LSR] Add salvaging variadic dbg.value intrinsics [2/2]

This relands commit 8f550368b169b0a3d4ebc3e65efec49ec1e0798a.

The test is amended with REQUIRES: x86-registered-target, in line wi

[Debuginfo][LSR] Add salvaging variadic dbg.value intrinsics [2/2]

This relands commit 8f550368b169b0a3d4ebc3e65efec49ec1e0798a.

The test is amended with REQUIRES: x86-registered-target, in line with
the other debuginfo-scev-salvage tests.

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

show more ...

Revert [Debuginfo][LSR] Add salvaging variadic dbg.value intrinsics[2/2]

This reverts commit 8f550368b169b0a3d4ebc3e65efec49ec1e0798a.

[Debuginfo][LSR] Add salvaging variadic dbg.value intrinsics [2/2]

Second of two patches to extend SCEV-based salvaging to dbg.value
intrinsics that have multiple location ops pre-LSR. This second p

[Debuginfo][LSR] Add salvaging variadic dbg.value intrinsics [2/2]

Second of two patches to extend SCEV-based salvaging to dbg.value
intrinsics that have multiple location ops pre-LSR. This second patch
adds the core implementation.

Reviewers: @StephenTozer, @djtodoro

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

show more ...

[SCEV] Use getConstant to construct SCEV for ConstantInt (NFC).

We already know that we will construct a SCEVConstant. Directly use
getConstant, rather than going through getSCEV.

[SCEV] Use constant ranges when determining reachable blocks (PR54434)

This avoids false positive verification failures if the condition
is not literally true/false, but SCEV still makes use of the

[SCEV] Use constant ranges when determining reachable blocks (PR54434)

This avoids false positive verification failures if the condition
is not literally true/false, but SCEV still makes use of the fact
that a loop is not reachable through more complex reasoning.

Fixes https://github.com/llvm/llvm-project/issues/54434.

show more ...

[SCEV] Verify all IR -> SCEV mappings

This extends SCEV verification to check not only backedge-taken
counts, but all entries in the IR -> SCEV cache. The restrictions
are the same as for the BECoun

[SCEV] Verify all IR -> SCEV mappings

This extends SCEV verification to check not only backedge-taken
counts, but all entries in the IR -> SCEV cache. The restrictions
are the same as for the BECount case, i.e. we ignore expressions
based on undef, we only diagnose constant deltas (there are way
too many false positives otherwise) and we limit to reachable code.

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

show more ...

[SCEV] Enable verification under EXPENSIVE_CHECKS

SCEV verification should no longer affect results of subsequent
queries, and our lit tests as well as llvm-test-suite pass with
SCEV verification en

[SCEV] Enable verification under EXPENSIVE_CHECKS

SCEV verification should no longer affect results of subsequent
queries, and our lit tests as well as llvm-test-suite pass with
SCEV verification enabled, so I think we can enable it by default
under EXPENSIVE_CHECKS now.

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

show more ...

[SCEV] Enable verification in LoopPM

Currently, we hardly ever actually run SCEV verification, even in
tests with -verify-scev. This is because the NewPM LPM does not
verify SCEV. The reason for thi

[SCEV] Enable verification in LoopPM

Currently, we hardly ever actually run SCEV verification, even in
tests with -verify-scev. This is because the NewPM LPM does not
verify SCEV. The reason for this is that SCEV verification can
actually change the result of subsequent SCEV queries, which means
that you see different transformations depending on whether
verification is enabled or not.

To allow verification in the LPM, this limits verification to
BECounts that have actually been cached. It will not calculate
new BECounts.

BackedgeTakenInfo::getExact() is still not entirely readonly,
it still calls getUMinFromMismatchedTypes(). But I hope that this
is not problematic in the same way. (This could be avoided by
performing the umin in the other SCEV instance, but this would
require duplicating some of the code.)

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

show more ...

[SCEV] Fully invalidate SCEVUnknown on RAUW

When a SCEVUnknown gets RAUWd, we currently drop it from the folding
set, but don't forget memoized values. I believe we should be
treating RAUW the same

[SCEV] Fully invalidate SCEVUnknown on RAUW

When a SCEVUnknown gets RAUWd, we currently drop it from the folding
set, but don't forget memoized values. I believe we should be
treating RAUW the same way as deletion here and invalidate all
caches and dependent expressions.

I don't have any specific cases where this causes issues right now,
but it does address the FIXME in https://reviews.llvm.org/D119488.

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

show more ...

Revert "[SCEV] Infer ranges for SCC consisting of cycled Phis"

This reverts commit fc539b0004d4fe8072aca00e38599a2300a955ce.

Causes miscompiles, see D110620.

Cleanup includes: LLVMAnalysis

Number of lines output by preprocessor:
before: 1065940348
after: 1065307662

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Diff

Cleanup includes: LLVMAnalysis

Number of lines output by preprocessor:
before: 1065940348
after: 1065307662

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Differential Revision: https://reviews.llvm.org/D120659

show more ...

[SCEV] Only verify BECounts for reachable loops (PR50523)

For unreachable loops, any BECount is legal, and since D98706 SCEV
can make use of this for loops that are unreachable due to constant
branc

[SCEV] Only verify BECounts for reachable loops (PR50523)

For unreachable loops, any BECount is legal, and since D98706 SCEV
can make use of this for loops that are unreachable due to constant
branches. To avoid false positives, adjust SCEV verification to only
check BECounts in reachable loops.

Fixes https://github.com/llvm/llvm-project/issues/50523.

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

show more ...

[SCEV] Return ArrayRef from getSCEVValues() (NFC)

Return a read-only view on this set. For the one internal use,
directly access ExprValueMap.

[SCEV] Don't try to reuse expressions with offset

SCEVs ExprValueMap currently tracks not only which IR Values
correspond to a given SCEV expression, but additionally stores that
it may be expanded

[SCEV] Don't try to reuse expressions with offset

SCEVs ExprValueMap currently tracks not only which IR Values
correspond to a given SCEV expression, but additionally stores that
it may be expanded in the form X+Offset. In theory, this allows
reusing existing IR Values in more cases.

In practice, this doesn't seem to be particularly useful (the test
changes are rather underwhelming) and adds a good bit of complexity.
Per https://github.com/llvm/llvm-project/issues/53905, we have an
invalidation issue with these offseted expressions.

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

show more ...

[ScalarEvolution] Control flag for nonstrict inequalities in finite loops

D118090 causes a pretty significant (19%) regression in some Eigen
benchmarks. Investigating is a bit time consuming as the

[ScalarEvolution] Control flag for nonstrict inequalities in finite loops

D118090 causes a pretty significant (19%) regression in some Eigen
benchmarks. Investigating is a bit time consuming as the compilation
unit where this occurs is large. Rather than revert, this patch adds a
flag controlling that behavior (enabled by default).

show more ...

[SCEV] Do not erase LoopUsers. PR53969

This patch fixes a logical error in how we work with `LoopUsers` map.
It maps a loop onto a set of AddRecs that depend on it. The Addrecs
are added to this map

[SCEV] Do not erase LoopUsers. PR53969

This patch fixes a logical error in how we work with `LoopUsers` map.
It maps a loop onto a set of AddRecs that depend on it. The Addrecs
are added to this map only once when they are created and put to
the UniqueSCEVs` map.

The only purpose of this map is to make sure that, whenever we forget
a loop, all (directly or indirectly) dependent SCEVs get forgotten too.

Current code erases SCEVs from dependent set of a given loop whenever
we forget this loop. This is not a correct behavior due to the following scenario:

1. We have a loop `L` and an AddRec `AR` that depends on it;
2. We modify something in the loop, but don't destroy it. We still call forgetLoop on it;
3. `AR` is no longer dependent on `L` according to `LoopUsers`. It is erased from
ValueExprMap` and `ExprValue map, but still exists in UniqueSCEVs;
4. We can later request the very same AddRec for the very same loop again, and get existing
SCEV `AR`.
5. Now, `AR` exists and is used again, but its notion that it depends on `L` is lost;
6. Then we decide to delete `L`. `AR` will not be forgotten because we have lost it;
7. Just you wait when you run into a dangling pointer problem, or any other kind of problem
because an active SCEV is now referecing a non-existent loop.

The solution to this is to stop erasing values from `LoopUsers`. Yes, we will maybe forget something
that is already not used, but it's cheap.

This fixes a functional bug and potentially may have negative compile time impact on methods with
huge or numerous loops.

Differential Revision: https://reviews.llvm.org/D120303
Reviewed By: nikic

show more ...

[SCEV][NFC] Replace contains+insert check with insert.second

[SCEV] Infer ranges for SCC consisting of cycled Phis

Our current strategy of computing ranges of SCEVUnknown Phis was to simply
compute the union of ranges of all its inputs. In order to avoid infi

[SCEV] Infer ranges for SCC consisting of cycled Phis

Our current strategy of computing ranges of SCEVUnknown Phis was to simply
compute the union of ranges of all its inputs. In order to avoid infinite recursion,
we mark Phis as pending and conservatively return full set for them. As result,
even simplest patterns of cycled phis always have a range of full set.

This patch makes this logic a bit smarter. We basically do the same, but instead
of taking inputs of single Phi we find its strongly connected component (SCC)
and compute the union of all inputs that come into this SCC from outside.

Processing entire SCC together has one more advantage: we can set range for all
of them at once, because the only thing that happens to them is the same value is
being passed between those Phis. So, despite we spend more time analyzing a
single Phi, overall we may save time by not processing other SCC members, so
amortized compile time spent should be approximately the same.

Differential Revision: https://reviews.llvm.org/D110620
Reviewed By: reames

show more ...

[NFC][SCEV] Recognize umin_seq when operand is zext'ed in zero-check

zext(umin(x,y)) == umin(zext(x),zext(y))
zext(x) == 0 -> x == 0

While it is not a very likely scenario, we probably should not

[NFC][SCEV] Recognize umin_seq when operand is zext'ed in zero-check

zext(umin(x,y)) == umin(zext(x),zext(y))
zext(x) == 0 -> x == 0

While it is not a very likely scenario, we probably should not expect
that instcombine already dropped such a redundant zext,
but handle directly. Moreover, perhaps there was no ZExtInst,
and SCEV somehow managed to pull out said zext out of the SCEV expression.

show more ...

[NFC][SCEV] Recognize umin_seq when operand is zext'ed in umin but not in zero-check

zext(umin(x,y)) == umin(zext(x),zext(y))
zext(x) == 0 -> x == 0

Extra leading zeros do not affect the result o

[NFC][SCEV] Recognize umin_seq when operand is zext'ed in umin but not in zero-check

zext(umin(x,y)) == umin(zext(x),zext(y))
zext(x) == 0 -> x == 0

Extra leading zeros do not affect the result of comparison with zero,
nor do they matter for the unsigned min/max,
so we should not be dissuaded when we find a zero-extensions,
but instead we should just skip it.

show more ...

[SCEVPredicate] Remove getExpr mechanism [NFC]

This mechanism was used for a couple of purposes, but the primary one was keeping track of which predicates in a union might apply to an expression. A

[SCEVPredicate] Remove getExpr mechanism [NFC]

This mechanism was used for a couple of purposes, but the primary one was keeping track of which predicates in a union might apply to an expression. As these sets are small and agressively deduped, this has little value.

show more ...

[NFCI][SCEV] `SCEVTraversal`: if search terminated, don't push further ops of nary

Even if the search is marked as terminated after only looking at
the first operand, we'd still look at the remainin

[NFCI][SCEV] `SCEVTraversal`: if search terminated, don't push further ops of nary

Even if the search is marked as terminated after only looking at
the first operand, we'd still look at the remaining operands
before actually ending the search.

This seems pointless and wasteful, let's not do that.

show more ...

[SCEV] Generalize umin_seq matching

Since we don't greedily flatten `umin_seq(a, umin(b, c))` into `umin_seq(a, b, c)`,
just looking at the operands of the outer-level `umin` is not sufficient,
and

[SCEV] Generalize umin_seq matching

Since we don't greedily flatten `umin_seq(a, umin(b, c))` into `umin_seq(a, b, c)`,
just looking at the operands of the outer-level `umin` is not sufficient,
and we need to recurse into all same-typed `umin`'s.

show more ...

[SCEV] Recognize `x == 0 ? 0 : umin_seq(..., x, ...) -> umin_seq(x, umin_seq(...))`

[SCEV] Recognize `x == 0 ? 0 : umin(..., x, ...) -> umin_seq(x, umin(...))`

That is the canonical expansion for umin_seq,
so we really should roundtrip it.