[SCEV] Handle nusw/nuw gep flags for addrecs

Set the nw flag is gep has any nowrap flags. Transfer the nuw
flag. Also set nuw for the nusw + nneg combination.

[SCEV] Transfer gep nusw and nuw flags

nusw implies nsw offset and nuw base+offset arithmetic if offset
is non-negative. nuw implies nuw offset and base+offset arithmetic.
As usual, we can only tran

[SCEV] Transfer gep nusw and nuw flags

nusw implies nsw offset and nuw base+offset arithmetic if offset
is non-negative. nuw implies nuw offset and base+offset arithmetic.
As usual, we can only transfer is poison implies UB.

show more ...

[SCEV] Print predicate backedge count only if new information available

When printing the result of SCEV's analysis, we can avoid printing
the predicated backedge taken count and the predicates if t

[SCEV] Print predicate backedge count only if new information available

When printing the result of SCEV's analysis, we can avoid printing
the predicated backedge taken count and the predicates if the predicates
are empty and no new information is provided. This helps to reduce the
verbosity of the output.

show more ...

[SCEV] Include type when printing constant max backedge taken count

When printing the result of the analysis, i8 -1 and i64 -1 are quite
different in terms of analysis quality. In a recent conversi

[SCEV] Include type when printing constant max backedge taken count

When printing the result of the analysis, i8 -1 and i64 -1 are quite
different in terms of analysis quality. In a recent conversion with
a new contributor, we ran into exactly this confusion.

Adding the type for constant scevs more globally seems worthwhile, but
introduces a much larger test diff. I'm splitting this off first since
it addresses the immediate need, and then going to do some further
changes to clarify a few related bits of analysis result output.

show more ...

[SCEV] Regenerate test checks (NFC)

There have been some minor but pervasive changes to the generated
CHECK lines, so regenerate all of them, to minimize future diffs.

[SCEV] Fix incorrect nsw inference for multiply of addrec (#66500)

SCEV currently preserves the nsw flag when performing an nsw multiply of
an nsw addrec. While this is legal for nuw, this is not g

[SCEV] Fix incorrect nsw inference for multiply of addrec (#66500)

SCEV currently preserves the nsw flag when performing an nsw multiply of
an nsw addrec. While this is legal for nuw, this is not generally the
case for nsw.

This is because nsw mul does not distribute over nsw add:
https://alive2.llvm.org/ce/z/mergCt

Instead, we need either both nuw and nsw to be set
(https://alive2.llvm.org/ce/z/7wpgGc) or explicitly prove that the
distributed multiplications are also nsw
(https://alive2.llvm.org/ce/z/wef9su).

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

show more ...

[SCEV] Clarify inference in isAddRecNeverPoison()

The justification in isAddRecNeverPoison() no longer applies, as
it dates back to a time where LLVM had an unconditional forward
progress guarantee.

[SCEV] Clarify inference in isAddRecNeverPoison()

The justification in isAddRecNeverPoison() no longer applies, as
it dates back to a time where LLVM had an unconditional forward
progress guarantee. However, we also no longer need it, because we
can exploit branch on poison UB instead.

For a single exit loop (without abnormal exits) we know that all
instructions dominating the exit will be executed, so if any of
them trigger UB on poison that means that addrec is not poison.

This is slightly stronger than the previous code, because a) we
don't need the exit to also be the latch and b) we don't need the
value to be used in the exit branch in particular, any UB-producing
instruction is fine.

I don't expect much practical impact from this change, this is
mainly to clarify the reasoning behind this logic.

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

show more ...

[SCEV] Add additional tests for addrec nowrap flags (NFC)

[SCEV] Strengthen nowrap flags via ranges for ARs on construction.

At the moment, proveNoWrapViaConstantRanges is only used when creating
SCEV[Zero,Sign]ExtendExprs. We can get significant improveme

[SCEV] Strengthen nowrap flags via ranges for ARs on construction.

At the moment, proveNoWrapViaConstantRanges is only used when creating
SCEV[Zero,Sign]ExtendExprs. We can get significant improvements by
strengthening flags after creating the AddRec.

I'll also share a follow-up patch that removes the code to strengthen
flags when creating SCEV[Zero,Sign]ExtendExprs. Modifying AddRecs while
creating those can lead to surprising changes.

Compile-time looks neutral:
https://llvm-compile-time-tracker.com/compare.php?from=94676cf8a13c511a9acfc24ed53c98964a87bde3&to=aced434e8b103109104882776824c4136c90030d&stat=instructions:u

Reviewed By: mkazantsev, nikic

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

show more ...

[SCEV] Convert tests to opaque pointers (NFC)

[SCEV] Name instructions in test (NFC)

[SCEV] Fix misplaced \n in printout of max symbolic exit counts

[SCEV] Add printout of symbolic max backedge-taken and block exit count

We do compute it and use in optimizations, but never print it out. We need
to do it in order to be able to track improvements

[SCEV] Add printout of symbolic max backedge-taken and block exit count

We do compute it and use in optimizations, but never print it out. We need
to do it in order to be able to track improvements in its computation.

show more ...

[SCEV] Rename max backedge-taken count -> constant max backedge taken-count in printout

This is a preparatory step for introducing symbolic max backedge-taken count.

[ValueTracking] Enable -branch-on-poison-as-ub by default

Now that SimpleLoopUnswitch and other transforms no longer introduce
branch on poison, enable the -branch-on-poison-as-ub option by
default.

[ValueTracking] Enable -branch-on-poison-as-ub by default

Now that SimpleLoopUnswitch and other transforms no longer introduce
branch on poison, enable the -branch-on-poison-as-ub option by
default. The practical impact of this is mostly better flag
preservation in SCEV, and some freeze instructions no longer being
necessary.

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

show more ...

[SCEV] Search operand tree for scope bound when inferring flags from IR

When checking to see if we can apply IR flags to a SCEV, we need to identify a bound on the defining scope of the SCEV to be p

[SCEV] Search operand tree for scope bound when inferring flags from IR

When checking to see if we can apply IR flags to a SCEV, we need to identify a bound on the defining scope of the SCEV to be produced. We'd previously added support for a couple SCEVExpr types which trivially imply bounds, but hadn't handled types such as umax where the bounds come from the bounds of the operands. This does the obvious thing, and recurses through operands searching for a tighter bound on the defining scope.

I'm honestly surprised by how little this seems to mater on existing tests, but it's worth doing for completeness sake alone.

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

show more ...

[tests] precommit test changes for D111191

Returning poison from a function w/ noundef return attribute is UB

This does for readability of returns within said function as what we do for the caller side when reasoning about what might be pois

Returning poison from a function w/ noundef return attribute is UB

This does for readability of returns within said function as what we do for the caller side when reasoning about what might be poison.

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

show more ...

[SCEV] Infer flags from add/gep in any block

This patch removes a compile time restriction from isSCEVExprNeverPoison. We've strengthened our ability to reason about flags on scopes other than addre

[SCEV] Infer flags from add/gep in any block

This patch removes a compile time restriction from isSCEVExprNeverPoison. We've strengthened our ability to reason about flags on scopes other than addrecs, and this bailout prevents us from using it. The comment is also suspect as well in that we're in the middle of constructing a SCEV for I. As such, we're going to visit all operands *anyways*.

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

show more ...

[test] factor out reliance on noundef return value

[test] rework recently added SCEV tests

These are meant to check a future patch which recurses through operands of SCEVs, but because all SCEVs are trivially bounded by function entry, we need to ar

[test] rework recently added SCEV tests

These are meant to check a future patch which recurses through operands of SCEVs, but because all SCEVs are trivially bounded by function entry, we need to arrange the trivial scope not to be valid. (i.e. we specifically need a lower defining scope)

show more ...

[tests] Cover cases we could infer SCEV flags, but don't

[SCEV] Use trivial bound on defining scope of all SCEVs when computing flags

This addresses a comment from review on D109845. Even for SCEVs which we can't find true bounds without recursing throug

[SCEV] Use trivial bound on defining scope of all SCEVs when computing flags

This addresses a comment from review on D109845. Even for SCEVs which we can't find true bounds without recursing through operands, entry to the function forms a trivial upper bound. In some cases, this trivial bound is enough to prove safety of flag inference.

show more ...

[SCEV] Use full logic when infering flags on add and gep

This is a followon to D109845. With that landed, we will have fixed all known instances of pr51817, and can thus start inferring flags more a

[SCEV] Use full logic when infering flags on add and gep

This is a followon to D109845. With that landed, we will have fixed all known instances of pr51817, and can thus start inferring flags more aggressively with greatly reduced risk of miscompiles. This patch simply applies the same inference logic used in that patch to our other major flag inference path.

We can still do much better here (on both paths), but this is our first step.

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

show more ...

[SCEV] Correctly propagate nowrap flags across scopes when folding invariant add through addrec

This fixes a violation of the wrap flag rules introduced in c4048d8f. This is an alternate fix to D106

[SCEV] Correctly propagate nowrap flags across scopes when folding invariant add through addrec

This fixes a violation of the wrap flag rules introduced in c4048d8f. This is an alternate fix to D106852.

The basic problem being fixed is that we infer a set of flags which is valid at some inner scope S1 (usually by correctly propagating them from IR), and then (incorrectly) extend them to a SCEV in scope S2 where S1 != S2. This is not in general safe per the wrap flags semantics recently defined.

In this patch, I include a simple inference step to handle the case where we can prove that S2 is the preheader of the loop S1, and that entry into S2 implies execution of S1. See the code for a more detailed explanation.

One worry I have with this patch is that I might be over-fitting what shows up in tests - and thus hiding negative impact we'd see in the real world. My best defense is that the rule used here very closely follows the one used to propagate the flags from IR to the inner add to start with, and thus if one is reasonable, so probably is the other. Curious what others think about that piece.

The test diffs are roughly as expected. Mostly analysis only, with two transform changes. Oddly, the result looks better in the loop-idiom test, and I don't understand the PPC output enough to have tell. Nothing terrible looking though. (For context, without the scope inference peephole, the test delta includes a couple of vectorization tests. Again, not super concerning, but slightly more so.)

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

show more ...