[SCEV] Use umin_seq for BECount of multi-exit loops

When computing the BECount for multi-exit loops, we need to combine
individual exit counts using umin_seq rather than umin. This is
because an ear

[SCEV] Use umin_seq for BECount of multi-exit loops

When computing the BECount for multi-exit loops, we need to combine
individual exit counts using umin_seq rather than umin. This is
because an earlier exit may exit on the first iteration, in which
case later exit expressions will not be evaluated and could be
poisonous. We cannot propagate potential poison values from later
exits.

In particular, this avoids the introduction of "branch on poison"
UB when optimizing multi-exit loops.

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

show more ...

[NFC][llvm] Inclusive language: reword uses of sanity test and check

Part of continuing work to use more inclusive language. Reworded uses
of sanity check and sanity test in llvm/test/

[NFCI] SCEVExpander: emit intrinsics for integral {u,s}{min,max} SCEV expressions

These intrinsics, not the icmp+select are the canonical form nowadays,
so we might as well directly emit them.

This

[NFCI] SCEVExpander: emit intrinsics for integral {u,s}{min,max} SCEV expressions

These intrinsics, not the icmp+select are the canonical form nowadays,
so we might as well directly emit them.

This should not cause any regressions, but if it does,
then then they would needed to be fixed regardless.

Note that this doesn't deal with `SCEVExpander::isHighCostExpansion()`,
but that is a pessimization, not a correctness issue.

Additionally, the non-intrinsic form has issues with undef,
see https://reviews.llvm.org/D88287#2587863

show more ...

[IndVars] Eliminate loop exits with equivalent exit counts

We can end up with two loop exits whose exit counts are equivalent, but whose textual representation is different and non-obvious. For the

[IndVars] Eliminate loop exits with equivalent exit counts

We can end up with two loop exits whose exit counts are equivalent, but whose textual representation is different and non-obvious. For the sub-case where we have a series of exits which dominate one another (common), eliminate any exits which would iterate *after* a previous exit on the exiting iteration.

As noted in the TODO being removed, I'd always thought this was a good idea, but I've now seen this in a real workload as well.

Interestingly, in review, Nikita pointed out there's let another oppurtunity to leverage SCEV's reasoning. If we kept track of the min of dominanting exits so far, we could discharge exits with EC >= MDE. This is less powerful than the existing transform (since later exits aren't considered), but potentially more powerful for any case where SCEV can prove a >= b, but neither a == b or a > b. I don't have an example to illustrate that oppurtunity, but won't be suprised if we find one and return to handle that case as well.

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

llvm-svn: 375379

show more ...

Remove a stale comment, noted in post commit review for rL375038

llvm-svn: 375040

[IndVars] Fix a miscompile in off-by-default loop predication implementation

The problem is that we can have two loop exits, 'a' and 'b', where 'a' and 'b' would exit at the same iteration, 'a' prec

[IndVars] Fix a miscompile in off-by-default loop predication implementation

The problem is that we can have two loop exits, 'a' and 'b', where 'a' and 'b' would exit at the same iteration, 'a' precedes 'b' along some path, and 'b' is predicated while 'a' is not. In this case (see the previously submitted test case), we causing the loop to exit through 'b' whereas it should have exited through 'a'.

This only applies to loop exits where the exit counts are not provably inequal, but that isn't as much of a restriction as it appears. If we could order the exit counts, we'd have already removed one of the two exits. In theory, we might be able to prove inequality w/o ordering, but I didn't really explore that piece. Instead, I went for the obvious restriction and ensured we didn't predicate exits following non-predicateable exits.

Credit goes to Evgeny Brevnov for figuring out the problematic case. Fuzzing probably also found it (failures seen), but due to some silly infrastructure problems I hadn't gotten to the results before Evgeny hand reduced it from a benchmark (he manually enabled the transform). Once this is fixed, I'll try to filter through the fuzzer failures to see if there's anything additional lurking.

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

llvm-svn: 375038

show more ...

[Tests] Add a test demonstrating a miscompile in the off-by-default loop-pred transform

Credit goes to Evgeny Brevnov for figuring out the problematic case.

Fuzzing probably also found it (lots of

[Tests] Add a test demonstrating a miscompile in the off-by-default loop-pred transform

Credit goes to Evgeny Brevnov for figuring out the problematic case.

Fuzzing probably also found it (lots of failures), but due to some silly infrastructure problems I hadn't gotten to the results before Evgeny hand reduced it from a benchmark.

llvm-svn: 374812

show more ...

[IndVars] An implementation of loop predication without a need for speculation

This patch implements a variation of a well known techniques for JIT compilers - we have an implementation in tree as L

[IndVars] An implementation of loop predication without a need for speculation

This patch implements a variation of a well known techniques for JIT compilers - we have an implementation in tree as LoopPredication - but with an interesting twist. This version does not assume the ability to execute a path which wasn't taken in the original program (such as a guard or widenable.condition intrinsic). The benefit is that this works for arbitrary IR from any frontend (including C/C++/Fortran). The tradeoff is that it's restricted to read only loops without implicit exits.

This builds on SCEV, and can thus eliminate the loop varying portion of the any early exit where all exits are understandable by SCEV. A key advantage is that fixing deficiency exposed in SCEV - already found one while writing test cases - will also benefit all of full redundancy elimination (and most other loop transforms).

I haven't seen anything in the literature which quite matches this. Given that, I'm not entirely sure that keeping the name "loop predication" is helpful. Anyone have suggestions for a better name? This is analogous to partial redundancy elimination - since we remove the condition flowing around the backedge - and has some parallels to our existing transforms which try to make conditions invariant in loops.

Factoring wise, I chose to put this in IndVarSimplify since it's a generally applicable to all workloads. I could split this off into it's own pass, but we'd then probably want to add that new pass every place we use IndVars. One solid argument for splitting it off into it's own pass is that this transform is "too good". It breaks a huge number of existing IndVars test cases as they tend to be simple read only loops. At the moment, I've opted it off by default, but if we add this to IndVars and enable, we'll have to update around 20 test files to add side effects or disable this transform.

Near term plan is to fuzz this extensively while off by default, reflect and discuss on the factoring issue mentioned just above, and then enable by default. I also need to give some though to supporting widenable conditions in this framing.

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

llvm-svn: 373351

show more ...