This is an archive of the discontinued LLVM Phabricator instance.

[SCCP] Use SimplifyBinOp for non-integer constant/expressions & overdef.
ClosedPublic

Authored by fhahn on Mar 19 2020, 3:17 PM.

Details

Summary

For non-integer constants/expressions and overdefined, I think we can
just use SimplifyBinOp to do common folds. By just passing a context
with the DL, SimplifyBinOp should not try to get additional information
from looking at definitions.

For overdefined values, it should be enough to just pass the original
operand.

Note: The comment before the if (isconstant(V1State)... was wrong
originally: isConstant() also matches integer ranges with a single
element. It is correct now.

This patch depends on a few ConstantRange improvements for all tests to
pass.

Diff Detail

Event Timeline

fhahn created this revision.Mar 19 2020, 3:17 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 19 2020, 3:17 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
fhahn updated this revision to Diff 252316.Mar 24 2020, 7:32 AM

Simplified the code a bit, by first trying simplifying to constant if either operand is a constant, followed by simplifying to a constant range as next step.

By just passing a context with the DL, SimplifyBinOp should not try to get additional information from looking at definitions.

What context is legal to use here?

llvm/lib/Transforms/Scalar/SCCP.cpp
989

Sort of orthogonal, but the thought occurred to me: should we be trying to use the "undef" lattice state here?

By just passing a context with the DL, SimplifyBinOp should not try to get additional information from looking at definitions.

What context is legal to use here?

I think SimplifyBinOp is not allowed to look at anything besides the values we pass in. In particular, looking at the definitions of the operands could potentially lead to it making assumption about undef values, which might lead to contradictions with the view SCCP has. I think this would lead to correctness issues similar to what NewGVN currently suffers from.

I initially thought passing in a context without DT & CxtI would be enough to ensure that, but I had another look and now I am not too sure. It seems like the SImplify* functions at least pass to operands to helpers from ValueTracking, which in turn may look at the operands of the operand, if it is an instruction. Not sure how to best prevent that now. One way would be to restrict that behavior via a new flag. Or create some kind of freestanding value that does not leak any information. What do you think?

The problem I see here is that InstSimplify could take a possibly-undef value, and turn it into a simple constant; then we would lose track of the fact that the value might be undef. (For example, we transform "undef & -2 -> 0", and then incorrectly merge the result with a ConstantRange.)

For NewGVN, you're talking about https://bugs.llvm.org/show_bug.cgi?id=36335 ? I don't think that sort of issue applies here. The operand we're passing to InstSimplify is the operand of the actual operation, so any context InstSimplify could derive is the correct context. We don't try to apply the result to any other instruction.

fhahn updated this revision to Diff 256264.Apr 9 2020, 5:55 AM

Updated to mark constants as may including undef, which in turn will ensure constant ranges are marked as including undef, for integer constants.

The problem I see here is that InstSimplify could take a possibly-undef value, and turn it into a simple constant; then we would lose track of the fact that the value might be undef. (For example, we transform "undef & -2 -> 0", and then incorrectly merge the result with a ConstantRange.)

Ah I see what you mean. I don't think the example "undef & -2 -> 0" would cause any issues because we get a single constant and will replace all uses. For the AND example, I think the only problem would be if a constant expression could evaluate to either undef or a constant. I cannot think of a case where this might be possible off the top of my head, but we can make sure that the constant range we create includes undef, if we simplify to an integer constant. That should conservatively preserve the fact that the result may include undef.

What do you think?

For NewGVN, you're talking about https://bugs.llvm.org/show_bug.cgi?id=36335 ? I don't think that sort of issue applies here. The operand we're passing to InstSimplify is the operand of the actual operation, so any context InstSimplify could derive is the correct context. We don't try to apply the result to any other instruction.

Yes that was what I was thinking about. But as you said, it seems like it won't be an issue here, as we only pass constants or the original value.

efriedma accepted this revision.Apr 9 2020, 12:26 PM

LGTM

I guess you're right that it doesn't cause any practical problem at the moment. If we actually resolve a value to a single constant, we can treat it as a simple constant in SCCP. The model is technically wrong as we're building it, but SCCP will replace the possibly-undef constant with a plain constant, and at that point the model is consistent with the transform. It would only become problematic if we didn't eventually perform that replacement.

This revision is now accepted and ready to land.Apr 9 2020, 12:26 PM
This revision was automatically updated to reflect the committed changes.