ScalarEvolution invariants around wrapping flags

Hi,

I'm working on a bug somewhere between SCEV and IndVarSimplify, which
tacks an unwanted "nuw" onto an "add i32 %whatever, -1" (which
actually almost certainly will overflow), leading ultimately to an
infinite loop. A fuller description and test-case is at the end for
anyone interested.

The issue seems to be with ScalarEvolution's attempts to cache SCEV
objects, which don't include wrapping flags in the immutable state.
That means that once ScalarEvolution has created an expression as
"nuw" it will be that way forever, even if analysed from an entirely
separate part of the function where that's not necessarily the case.

Worse, callers can create an expression with specified flags through
the public interface, which would pollute all analysis after that
point with those unwanted flags. I don't know if any callers actually
do this but I could see it being useful for looking at hypothetical
cases.

To some degree mutation of wrapping flags is part of the design,
because SCEVAddRecExprs are explicitly const_casted to add flags in
multiple places so that they can be found again later. But that might
not be quite so harmful because they at least contain a Loop as a
contextual cue that prevents some leaking.

So, my real question is does anyone know what the contract with
ScalarEvolution is? I see a few possibilities:

1. Callers are expected to not engage in speculation. ScalarEvolution
itself must only create expressions it knows hold in all cases. This
sounds too restrictive to me.
2. Speculation not allowed outside ScalarEvolution, but
ScalarEvolution can speculate about a specific Loop. I think this
entails making non-AddRec expressions immutable (with Flags included
as part of the FoldingSetID) and ensuring that any modification of an
AddRec is provable within its Loop.
3. Speculation is allowed, and achieved by making all expressions
immutable. Sites currently const_casting AddRecExprs instead get a new
one with the flags they want. Sites trying to help out other codepaths
by cacheing this info are out of luck.
4. Speculation scenarios are allowed, and achieved by adding something
like a "HypothesisToken" to SCEV objects, to keep them separate from
each other and guaranteed properties. As in 2, maybe a Loop is enough
if public users can't speculate.

Any ideas gratefully received.

Cheers.

Tim.

Description of bug: the loop gets duplicated, with one copy guarded by
both "x == 0 && x != 0". This gets an "nuw" added to %dec (probably
legitimately since it's never executed). That "nuw" gets picked up in
the analysis of the other copy of the loop, which also gets "nuw". The
loop quickly gets turned into an infinite one because it's now riddled
with UB.

See test.c, compiled for a 32-bit platform (I've checked i686 and ARM,
mac & Linux) at -O3. Strangely I can't reproduce it in opt yet. I
suspect multiple runs of the same pass are needed.

test.c (2.17 KB)

Hi,

I'm working on a bug somewhere between SCEV and IndVarSimplify, which
tacks an unwanted "nuw" onto an "add i32 %whatever, -1" (which
actually almost certainly will overflow),

My understanding of the current contract is that this is a bug. We cannot add deduced flags to non-AddRec SCEVs precisely because they're cached across loops. AddRecs are different because they're tied to a particular loop.

Long term, I think that it would be cleaner to rework this so that all of the SCEV's are immutable and include their flags.

-Hal

leading ultimately to an
infinite loop. A fuller description and test-case is at the end for
anyone interested.

The issue seems to be with ScalarEvolution's attempts to cache SCEV
objects, which don't include wrapping flags in the immutable state.
That means that once ScalarEvolution has created an expression as
"nuw" it will be that way forever, even if analysed from an entirely
separate part of the function where that's not necessarily the case.

Worse, callers can create an expression with specified flags through
the public interface, which would pollute all analysis after that
point with those unwanted flags. I don't know if any callers actually
do this but I could see it being useful for looking at hypothetical
cases.

To some degree mutation of wrapping flags is part of the design,
because SCEVAddRecExprs are explicitly const_casted to add flags in
multiple places so that they can be found again later. But that might
not be quite so harmful because they at least contain a Loop as a
contextual cue that prevents some leaking.

So, my real question is does anyone know what the contract with
ScalarEvolution is? I see a few possibilities:

1. Callers are expected to not engage in speculation. ScalarEvolution
itself must only create expressions it knows hold in all cases. This
sounds too restrictive to me.
2. Speculation not allowed outside ScalarEvolution, but
ScalarEvolution can speculate about a specific Loop. I think this
entails making non-AddRec expressions immutable (with Flags included
as part of the FoldingSetID) and ensuring that any modification of an
AddRec is provable within its Loop.
3. Speculation is allowed, and achieved by making all expressions
immutable. Sites currently const_casting AddRecExprs instead get a new
one with the flags they want. Sites trying to help out other codepaths
by cacheing this info are out of luck.
4. Speculation scenarios are allowed, and achieved by adding something
like a "HypothesisToken" to SCEV objects, to keep them separate from
each other and guaranteed properties. As in 2, maybe a Loop is enough
if public users can't speculate.

Any ideas gratefully received.

Cheers.

Tim.

Description of bug: the loop gets duplicated, with one copy guarded by
both "x == 0 && x != 0". This gets an "nuw" added to %dec (probably
legitimately since it's never executed). That "nuw" gets picked up in
the analysis of the other copy of the loop, which also gets "nuw". The
loop quickly gets turned into an infinite one because it's now riddled
with UB.

See test.c, compiled for a 32-bit platform (I've checked i686 and ARM,
mac & Linux) at -O3. Strangely I can't reproduce it in opt yet. I
suspect multiple runs of the same pass are needed.

1. Callers are expected to not engage in speculation. ScalarEvolution
itself must only create expressions it knows hold in all cases.

This is correct. There is some more relevant text in
ScalarEvolution::isSCEVExprNeverPoison. And you're right, this is
quite restrictive.

Long term, I think that it would be cleaner to rework this so that all of the SCEV's are immutable and include their flags.

I proposed this in 2016 but Andy had some concerns and I dropped it.
See http://lists.llvm.org/pipermail/llvm-dev/2016-September/105108.html
and http://lists.llvm.org/pipermail/llvm-dev/2017-August/116324.html

+Andrew Trick

-- Sanjoy

1. Callers are expected to not engage in speculation. ScalarEvolution
itself must only create expressions it knows hold in all cases.

This is correct. There is some more relevant text in
ScalarEvolution::isSCEVExprNeverPoison. And you're right, this is
quite restrictive.

Long term, I think that it would be cleaner to rework this so that all of the SCEV's are immutable and include their flags.

I proposed this in 2016 but Andy had some concerns and I dropped it.
See http://lists.llvm.org/pipermail/llvm-dev/2016-September/105108.html
and http://lists.llvm.org/pipermail/llvm-dev/2017-August/116324.html

+Andrew Trick

— Sanjoy

I was never able to reconcile integrating nsw/nuw flags into SCEV. They violate the spirit of SCEV, in the sense that algabraically equivalent expressions must be uniquely identified, and that the the order that expressions are evaluated should not affect the outcome.

My understanding matches Hal's, that we can imbue AddRec's with flags because they're already tied to the IR. It's usually incorrect to imbue regular Adds with nsw/nuw flags.

In the past I advocated for removing the flags from SCEV, or at least from non-AddRecs, and keeping them in some side channel that's associated with IR operations for those optimizations that need them.

The alternative, of course, is to treat the flags as input to the SCEV expression. I'm not opposed to this, I'm just not certain how easy it will be to do without creating new problems. Either SCEV-based analysis weakens in the presence of flags, or its algorithmic complexity increases by some power, or some arbitrary cutoffs are chosen that seem to work in practice but aren't very principled.

-Andy

1. Callers are expected to not engage in speculation. ScalarEvolution
itself must only create expressions it knows hold in all cases.

This is correct. There is some more relevant text in
ScalarEvolution::isSCEVExprNeverPoison. And you're right, this is
quite restrictive.

Long term, I think that it would be cleaner to rework this so that all of the SCEV's are immutable and include their flags.

I proposed this in 2016 but Andy had some concerns and I dropped it.
See http://lists.llvm.org/pipermail/llvm-dev/2016-September/105108.html
and http://lists.llvm.org/pipermail/llvm-dev/2017-August/116324.html

+Andrew Trick

— Sanjoy

I was never able to reconcile integrating nsw/nuw flags into SCEV. They violate the spirit of SCEV, in the sense that algabraically equivalent expressions must be uniquely identified, and that the the order that expressions are evaluated should not affect the outcome.

My understanding matches Hal's, that we can imbue AddRec's with flags because they're already tied to the IR. It's usually incorrect to imbue regular Adds with nsw/nuw flags.

In the past I advocated for removing the flags from SCEV, or at least from non-AddRecs, and keeping them in some side channel that's associated with IR operations for those optimizations that need them.

The alternative, of course, is to treat the flags as input to the SCEV expression. I'm not opposed to this, I'm just not certain how easy it will be to do without creating new problems. Either SCEV-based analysis weakens in the presence of flags, or its algorithmic complexity increases by some power, or some arbitrary cutoffs are chosen that seem to work in practice but aren't very principled.

One subtlety that hasn't been mentioned yet is that flags on an IR node (and thus on a corresponding SCEV) are only valid for the current set of uses in the IR. If you add a use which didn't exist in the original program, you may have to strip flags both from IR and SCEV. The original expression could have been poison without triggering UB (i.e. it wasn't branched on) and the new use might trigger UB.

In terms of proper design, I prefer treating flags as operands to the SCEV and thus having "add nsw" be distinct from "add nuw" or "add".

Once we do that though, we end with a result quality problem which is a bit subtle. We can discover overflow facts after forming SCEVs. (There's subtle interactions between SCEV construction order and trip count computations.) As such, we'll have to essentially form a "specialize SCEV given overflow fact" interface, and use it from most of the places we currently manipulate flags.

Thanks for the information everyone, it's clarified my thinking
significantly. With that better understanding I've tracked the problem
I'm seeing down to r366419 (https://reviews.llvm.org/D64868), which
got committed in July.

To me it looks like the patch is invalid because isAddRecNeverPoison
is a loop-relative computation. To add the flags to the increment we'd
need to know that the loop is guaranteed to execute at least once,
which doesn't really have a query available.

Does that sound right? And if so should we revert it or try to
incorporate a loop-executed check? I probably tend towards revert.

Cheers.

Tim.

Your reasoning sounds correct to me. Let's revert for now?

I don't think there is an easy fix, we'll have to do a global "must be
executed" analysis to reapply the patch soundly. And that's difficult
since any external functional call can call "exit(0)".

-- Sanjoy

This patch made it into clang-9.0, I would flag the revert for 9.1.

+Tom (I don’t know the current process to flag patches for dot releases)

Your reasoning sounds correct to me. Let's revert for now?

Sounds good, I've reverted it with r373184 (and r373185 to polly,
which fixed up some tests after the original commit).

I don't think there is an easy fix, we'll have to do a global "must be
executed" analysis to reapply the patch soundly. And that's difficult
since any external functional call can call "exit(0)".

Oh yes, that didn't even occur to me.

Cheers.

Tim.

Thank for reverting it.

For the original issue in https://reviews.llvm.org/D64868, if we want to make sure nsw can be correctly added to increment SCEV, we need to also check isLoopEntryGuardedByCond? Is this a right way to go?

BRS//
Chen Zheng

Thank for reverting it.

For the original issue in https://reviews.llvm.org/D64868, if we want to make sure nsw can be correctly added to increment SCEV, we need to also check isLoopEntryGuardedByCond? Is this a right way to go?

I don't see how that would help, but I can be more specific if you are
more specific. :slight_smile: How exactly are you suggesting we use
isLoopEntryGuardedByCond?

-- Sanjoy