llvm dev - Sep 2019 - ScalarEvolution invariants around wrapping flags

> 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
>
>  -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.
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
> --
> Hal Finkel
> Lead, Compiler Technology and Programming Languages
> Leadership Computing Facility
> Argonne National Laboratory
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

> On Sep 18, 2019, at 8:17 PM, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
> 
>> 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
> 
>> 
>> -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.
>> 
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>> 
>> --
>> Hal Finkel
>> Lead, Compiler Technology and Programming Languages
>> Leadership Computing Facility
>> Argonne National Laboratory
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

On 9/19/2019 9:41 AM, Andrew Trick via llvm-dev wrote:
>
>> On Sep 18, 2019, at 8:17 PM, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
>>
>>> 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.
> -Andy
>
>>> -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.
>>>
>>>
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> llvm-dev at lists.llvm.org
>>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>
>>> --
>>> Hal Finkel
>>> Lead, Compiler Technology and Programming Languages
>>> Leadership Computing Facility
>>> Argonne National Laboratory
>>>
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> llvm-dev at lists.llvm.org
>>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev