Speculation and control dependent no wrap flags

I’m looking at the bug (https://llvm.org/bugs/show_bug.cgi?id=31181) which was triggered by my change to make CVP mark adds as no wrap (https://reviews.llvm.org/rL278220) and I’d like to have some broader discussion of the problem. In this bug CVP correctly marks an add as nuw basing on the loop latch check, but later loop rotation pass moves the add to a point before the check. In the new context nuw is no longer valid and leads to an incorrect transformation of the loop. See https://llvm.org/bugs/show_bug.cgi?id=31181#c5 comment in the bug for more details.

Since nsw, nuw flags can be control dependent, it seems like we should be treating them as metadata, i.e. we should be stripping them when we speculate the instruction. I don’t think that we are doing this now anywhere. The problem was noticed on loop rotation, but I expect any other pass which speculates overflowing operations is suffering from the same problem.

Thoughts?

Artur

I'm looking at the bug (31181 – wrong code with "opt -instcombine -early-cse -jump-threading -correlated-propagation -loop-rotate -indvars -gvn") which was triggered by my change to make CVP mark adds as no wrap (https://reviews.llvm.org/rL278220) and I'd like to have some broader discussion of the problem. In this bug CVP correctly marks an add as nuw basing on the loop latch check, but later loop rotation pass moves the add to a point before the check. In the new context nuw is no longer valid and leads to an incorrect transformation of the loop. See https://llvm.org/bugs/show_bug.cgi?id=31181#c5 comment in the bug for more details.

Since nsw, nuw flags can be control dependent, it seems like we should be treating them as metadata, i.e. we should be stripping them when we speculate the instruction. I don’t think that we are doing this now anywhere. The problem was noticed on loop rotation, but I expect any other pass which speculates overflowing operations is suffering from the same problem.

Thoughts?

We generally don't strip these because violating the wrapping constraint does not immediately cause UB. Instead, it generates a poison value. So long as that poison value is not used in way which causes UB, then everything is fine. In this case, I suspect that we want to fix IndVars to strip the flag, or not do the transformation, when it might introduce this kind of issue (i.e. a situation where we might branch on a poison value).

  -Hal

Just yesterday I talked to Dan Gohman, who suggested we strip nowrap flags when speculating. It solves a lot of poison problems.

Personally, I'm in the "strip like metadata" camp. This is much easier to reason about.

Philip

Yes, this looks like a straight-forward IndVarSimplify bug to me since
IndVars is introducing a branch on poison. It needs to strip no-wrap
flags from the post inc value (or create a new post-inc value that
does not have those) before introducing a branch on it.

-- Sanjoy

Yes, stripping nowrap flags when speculating "solves" a lot of poison problems... in the sense that we could just redefine nsw to mean that overflow is UB rather than poison. IIRC, this was considered, but rejected because there are too many optimizations which hoist code (so we would lose the nsw flags too early in the pipeline). It's possible we could solve that problem some other way, like recording overflow assumptions with llvm.assume.

-Eli