[llvm-dev] Improving SCEV's behavior around IR level no-wrap flags

[Sanjoy Das via llvm-dev]

Hi Andy,

Andrew Trick wrote:

[snip]

 >> *I think the current representation of nsw/nuw in SCEV expressions is
 >> not congruent with LLVM's specification of poison values, and that is
 >> blocking us from exploiting poison values as intended by LLVM's
 >> design.*
 >
 > I’m not 100% sure what you mean, but since SCEV expressions don’t
 > represent IR values, mapping poison semantics, which are specific to
 > IR values, onto SCEV expressions never made sense to me.

I agree that making SCEV a pure 2's complement is cleaner (and
something I find preferable personally, tbqh); but in practice users
tend to prefer SCEV do at least some reasoning based on no-wrap flags
present in the IR.  If we decide SCEV is not the right tool for the
job, we at least need to discuss what is the right tool.

[snip]

 >> This means we'd treat "add %x, %y" as a different SCEV expression than
 >> "add nsw %x, %y", since the latter sometimes produces poison while the
 >> former doesn't.  The latter would be known to not overflow, and SCEV
 >> would use that fact in the usual ways.
 >
 > Ok. What happens when you canonicalize the SCEV expressions?
 > Reassociation is just one of the ways the nsw flags will be lost.

We'll just have to make the no-wrap-ness part of the algebra, like
everything else.  So

((a +nsw b) +nsw c) ==> (+nsw a b c)

((a +nsw b) + c) ==> (+ a b c)

and so on.

I suspect a very conservative approach of dropping the no-wrap flags
for anything beyond the simplest cases will be better than what we
have today.

[snip]

 >> will have to be changed to do
 >>
 >>   SCEV *X = ...
 >>   SCEV *Y = ...
 >>   if (X->equals(Y))
 >>     ...
 >>
 >> This has potential for compile-time regressions.  Hopefully they'll
 >> all be addressable.
 >
 > That’s the main reason we never did this. It wasn’t clear to me what
 > impact it might have on reducing SCEV expressions in general. Are you
 > saying that this will not affect the outcome of SCEV
 > reduction/canonicalization as long as we pay the cost of slow
 > comparisons? What about nested expressions? Won’t this require
 > scanning the whole SCEV tree for each comparison?

Yes, in some cases getting satisfactory results will require scanning
and matching whole expression trees.  There are things we can do to
make that hurt less (e.g. maintain a hash with every expression that
ignores the no-wrap flags) or try to recover the difference elsewhere,
but I will admit that this is the weakest part of the proposal.

[snip]

 >> ComputedFlags will, in general, depend on AxiomaticFlags.  For
 >> instance if AxiomaticFlags is "nsw" for, say, {1,+,1}, we can add
 >> "nuw" to its ComputedFlags.  There is no need to further distinguish
 >> "{1,+,1}-axiomatic<nsw>" on the computed<nuw>  dimension since
 >> "{1,+,1}-axiomatic<nsw>" will always be computed<nuw>.
 >
 > Great. That answers my question above.

Okay, I didn't bother re-answering then. :)

[snip]

 > The alternative is to represent proofs about IR values independent
 > from SCEV. I don’t know how much net value we get out of embedding
 > these facts within SCEV (aside from the convenience given the current
 > implementation). SCEV is about canonicalizing and algebraic reduction
 > so that simple relations between IR values can be discovered. Of
 > course, computing trip count needs this information, but is could
 > always look elsewhere for those facts. The question is what SCEV
 > reductions themselves need the nsw/nuw info, vs. simply propagating
 > the flags. Can those reductions in turn be pulled out of as some high
 > level analysis? I think sign-extend elimination would need some
 > serious thought. But the current situation with reducing
 > truncations/extensions in SCEV is not good anyway. It defeats SCEVs
 > canonical form—you can get different answers depending on the order of
 > reductions.

I may have misunderstood your proposal, but I think by the point we
have a SCEV expression it is already too late to do a precise
poison-value analysis.

For instance, say we have:

   %t0 = add     %x, 1
   %t1 = add nsw %x, 1
   ...
   br i1 %cond, label %exit_loop, label %take_backedge

Now lets say SCEV says the trip count of the loop is "(smax (x + 1)
x)".  Given only that information, I don't have a way of knowing if
the (x + 1) in the trip count is %t0 (which can be assumed to
overflow) or %t1 (which is no-wrap).  It could also have come from
some completely different reduction altogether (say "(x + y) - (y -
1)"), and unless we have the provenance of all the terms it will be
difficult to exploit language specific no-wrap behavior.

Did that make sense?

-- Sanjoy