llvm dev - Dec 2016 - SCCP is not always correct in presence of undef (+ proposed fix)

On Fri, Dec 30, 2016, 9:04 PM Sanjoy Das via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi David,
>
> Looking at the original bug, it seems like a straightforward
> undef-propagation bug to me -- SCCP was folding "or undef,
constant"
> to "undef", which is wrong.  Why is changing that not the fix? 
That
> is, some variant of
>
You would still need to fix the iteration order of the resolver, or it will
make more wrong decisions.
As Davide discovered, there are bugs open with the same cause.
>
> diff --git a/lib/Transforms/Scalar/SCCP.cpp
> b/lib/Transforms/Scalar/SCCP.cpp
> index 8a6be97..45f1241 100644
> --- a/lib/Transforms/Scalar/SCCP.cpp
> +++ b/lib/Transforms/Scalar/SCCP.cpp
> @@ -908,8 +908,18 @@ void SCCPSolver::visitBinaryOperator(Instruction
&I) {
>    }
>
>    // If something is undef, wait for it to resolve.
> -  if (!V1State.isOverdefined() && !V2State.isOverdefined())
> -    return;
> +  if (!V1State.isOverdefined() && !V2State.isOverdefined()) {
> +    Constant *L = UndefValue::get(I.getOperand(0)->getType());
> +    if (V1State.isConstant())
> +      L = V1State.getConstant();
> +    Constant *R = UndefValue::get(I.getOperand(0)->getType());
> +    if (V2State.isConstant())
> +      R = V2State.getConstant();
> +    Constant *C = ConstantExpr::get(I.getOpcode(), L, R);
> +    if (isa<UndefValue>(C))
> +      return;
> +    return markConstant(IV, &I, C);
> +  }
>
>    // Otherwise, one of our operands is overdefined.  Try to produce
> something
>    // better than overdefined with some tricks.
>
>
>
>
> Also, did you mean to make the lattice as:
>
> digraph G {
>   Unknown -> Undef
>   Undef -> Constant1
>   Undef -> Constant2
>   Undef -> Constant3
>   Constant1 -> Bottom
>   Constant2 -> Bottom
>   Constant3-> Bottom
> }
>
> ?  In the lattice you've drawn, Constant MEET Undef will be Bottom,
> when it should ideally be Constant.
>
> Secondly, what's the purpose of splitting Unknown and Undef in the new
> scheme?


You need to distinguish between not visited and visited but undef.

  Is there a case in your algorithm in which treating an
> unknown as an undef will be a problem?
>
> Actually given the above lattice (assuming you're okay with that) we
know
> treating unknown as undef should not make us any less conservative
> (i.e. should be safe) since undef is lower than unknown.  IOW why not
> change
> the algorithm to start off each cell as undef and not unknown?
>
Because then you can't distinguish between not visited and undef.
>
> -- Sanjoy
>
> On Fri, Dec 30, 2016 at 9:27 AM, Davide Italiano via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
> > Hi.
> > I'm sending this email to -dev as this may be of interest of
> > many/people may have opinions/want to try the change before it goes in
> > to report problems.
> > I've been recently working on a patch to integrate `undef` in the
SCCP
> > solver, in the hope of fixing a tail of latent bugs in SCCP which
> > remained uncovered for many years. I think this is a decent time to
> > propose, so that it can (hopefully) be integrated in the 4.0 branch
> > (or backported, FWIW), if it gets reviewed and there are no
> > substantial problems.
> >
> > #### Background:
> > The current lattice for SCCP doesn't know about `undef`, that is,
it's
> > identical to the one described in [1]. There are three lattice states,
> > "Unknown"/"Constant"/"Overdefined" (the
first one is what the paper
> > calls "Undefined", but was renamed as "undefined"
in LLVM has a
> > different meaning).
> >
> > SCCP (or its interprocedural counterpart) currently consists of two
> phases:
> > 1) The solver, which implements the algorithm described in the paper.
> > At the end of this phase, if there are no `undef` values in the input,
> > all the values supposedly have been lowered (in a lattice-theoretical
> > sense) to either constant or overdefined. In presence of `undef`,
> > there may be values which are still in the 'unknown' state.
> > 2) The resolver assumes that everything in the 'unknown' state
is
> > undefined, and runs a procedure trying to plug the "correct"
value,
> > and in case something changed, runs the solver again.
> >
> > #### Problem/Motivation for the change:
> > 1) and 2) use different orders of visitation. 1) walks the use-def
> > chains, 2) visit the function in basic block order (starting from the
> > entry block of the function).
> > The fact that 2) walks over the function instead of the SSA graph
> > creates some issues where it cannot distinguish between the following
> > two cases:
> >
> > a) It doesn't know how to resolve this value
> > b) This value is really undef.
> >
> > and may plug in wrong/invalid values. For a real example, see the bug
> > in [3], for a proof of why it's wrong, see [2] (courtesy of Daniel
> > Berlin).
> >
> > #### Proposed fix:
> > Integrate `undef` in the solver. Undef is a lattice value lower than
> > `Unknown` but higher than `Overdefined` (at the same lattice level of
> > constant). Graphically:
> >
> >    unknown
> >     /     \      \
> >    /       \      \
> >  c1 ...  ck undefined
> >   \         |       /
> >    \        |      /
> >    overdefined
> >
> >
> > #### Benefits:
> > -> The code now is correct (modulo other bugs =)) in presence of
undefs
> > -> This allows us to keep the same lattice height and therefore all
> > the nice termination/convergence properties/bounds (see the paper for
> > reference).
> > -> This allows to remove a lot of code (pretty much the resolver)
and
> > makes the algorithm easier to understand
> > -> SCCP doesn't need anymore to roll its own tiny constant
folder
> > where we need to add cases everytime we realize there's something
> > missing, instead, it can leverage the full power of ConstantFolding
> > when something folds to undef.
> > -> Makes SCCP *slightly* faster.
> >
> > #### (Potential) drawbacks:
> > -> This change the behavior of `phi` handling, i.e. we lose some
cases
> > as we force phi to overdefined if not the values are constant. I
> > measured the impact on the llvm-testsuite and on some internal
> > benchmarks and I wasn't able to measure any substantial different
in
> > runtime performances. If you care about this case, please speak up =)
> > (or try the patch and report regressions). There are probably ways to
> > make this working but we (see [4], comment 7 and 8) think the gain in
> > precision is not worth the complexity (and what's here is *much
much*
> > better than what's in the tree as it tries at least to be
correct).
> >
> > #### Plan for integration
> > The patch is available at https://reviews.llvm.org/D28177
> > Any comments/feedback/testing is definitely welcome. This is a
> > self-contained change.
> >
> > #### (Possible) future work
> > If this goes in I'd like to implement constant propagation for
missing
> > IR constructs (in particular vectors), and make sure SCCP is on par
> > with the other two costant propagation passes we have in llvm (and
> > maybe garbage collect them).
> > Danny suggested an improvement could be that of propagating facts in
> > both directions (GCC does that as a separate pass
> > https://gcc.gnu.org/svn/gcc/trunk/gcc/gimple-ssa-backprop.c). I have
> > no immediate plans to work on this (I suspect NewGVN and other places
> > will keep me busy for a while), but I hope to eventually get there.
> >
> > #### Thanks
> > Eli Friedman and Daniel Berlin provided very insightful
> > conversations/suggestions on how to tackle the problems, and provided
> > early feedback on the change (other than reviewing large part if not
> > all my previous work on SCCP).
> >
> >
> > [1] https://www.cs.utexas.edu/users/lin/cs380c/wegman.pdf
> > [2]
>
http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20161107/403212.html
> > [3] https://llvm.org/bugs/show_bug.cgi?id=30448
> > [4] https://llvm.org/bugs/show_bug.cgi?id=30966#c8
> >
> > --
> > Davide
> >
> > "There are no solved problems; there are only problems that are
more
> > or less solved" -- Henri Poincare
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org
> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
> --
> Sanjoy Das
> http://playingwithpointers.com
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161231/a9f067d9/attachment-0001.html>

>
>
>   Is there a case in your algorithm in which treating an
>> unknown as an undef will be a problem?
>>
>> Yes, if you try to optimize undefs in any way, no if you move them to
overdefined :)

IE given phi [a, undef, undef, undef]

with just as many back edges, you will visit this node 4 times.

If you start out with

phi [a, undef, undef, undef], you may think "I know, i will make  these
undef's a".

So you move everything to value

phi [a, a, a, a]

But remember, you really haven't visited the other 4 edges yet, so you
don't know if this is a valid value for undef (because of the rules around
and/or/etc, see http://llvm.org/docs/LangRef.html#undefined-values).

(a, a, a, a of course, is just an example, you also don't know if it's
valid to always return undef, or 0, or 1, or anything at all, really).

It's not until you hit this node for the 4th time, that you can really
safely choose a value.

If you have unknown and undef, it goes from

phi [a, unknown, unknown, unknown] to phi [a, undef, unknown, unknown] to
...

you know, once you have no unknown values, that everything you need to know
to resolve it is known.

(this is also why there is no need for a resolver. There really is no safe
logic in the resolver that can't be pushed into the solver, though it may
make sense to structure it as a resolver if you think it's easier)

Similarly for or %x, undef.
You need to know if it's really undef, not "something i haven't
visited
yet".
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161230/063e2877/attachment.html>

Hi,

On Fri, Dec 30, 2016 at 9:23 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
>
>
> On Fri, Dec 30, 2016, 9:04 PM Sanjoy Das via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
>>
>> Hi David,
>>
>> Looking at the original bug, it seems like a straightforward
>> undef-propagation bug to me -- SCCP was folding "or undef,
constant"
>> to "undef", which is wrong.  Why is changing that not the
fix?  That
>> is, some variant of
>
>
> You would still need to fix the iteration order of the resolver, or it will
> make more wrong decisions.
> As Davide discovered, there are bugs open with the same cause.
Davide -- can you point me to those?
>> diff --git a/lib/Transforms/Scalar/SCCP.cpp
>> b/lib/Transforms/Scalar/SCCP.cpp
>> index 8a6be97..45f1241 100644
>> --- a/lib/Transforms/Scalar/SCCP.cpp
>> +++ b/lib/Transforms/Scalar/SCCP.cpp
>> @@ -908,8 +908,18 @@ void SCCPSolver::visitBinaryOperator(Instruction
&I)
>> {
>>    }
>>
>>    // If something is undef, wait for it to resolve.
>> -  if (!V1State.isOverdefined() && !V2State.isOverdefined())
>> -    return;
>> +  if (!V1State.isOverdefined() && !V2State.isOverdefined()) {
>> +    Constant *L = UndefValue::get(I.getOperand(0)->getType());
>> +    if (V1State.isConstant())
>> +      L = V1State.getConstant();
>> +    Constant *R = UndefValue::get(I.getOperand(0)->getType());
>> +    if (V2State.isConstant())
>> +      R = V2State.getConstant();
>> +    Constant *C = ConstantExpr::get(I.getOpcode(), L, R);
>> +    if (isa<UndefValue>(C))
>> +      return;
>> +    return markConstant(IV, &I, C);
>> +  }
>>
>>    // Otherwise, one of our operands is overdefined.  Try to produce
>> something
>>    // better than overdefined with some tricks.
>>
>>
>>
>>
>> Also, did you mean to make the lattice as:
>>
>> digraph G {
>>   Unknown -> Undef
>>   Undef -> Constant1
>>   Undef -> Constant2
>>   Undef -> Constant3
>>   Constant1 -> Bottom
>>   Constant2 -> Bottom
>>   Constant3-> Bottom
>> }
>>
>> ?  In the lattice you've drawn, Constant MEET Undef will be Bottom,
>> when it should ideally be Constant.
>>
>> Secondly, what's the purpose of splitting Unknown and Undef in the
new
>> scheme?
>
>
>
> You need to distinguish between not visited and visited but undef.
What I'm getting at is, if you're implementing something close to the
paper mentioned, I can't think of a case where you'd care to
distinguish between "not visited" and "visited but undef". 
That is,
instead of starting from "map each each instruction as not visited" we
should be able to (my unproven conjecture) start from "map each
instruction to undef", making the "unknown" element superfluous.

-- Sanjoy
>
>>   Is there a case in your algorithm in which treating an
>> unknown as an undef will be a problem?
>>
>> Actually given the above lattice (assuming you're okay with that)
we know
>> treating unknown as undef should not make us any less conservative
>> (i.e. should be safe) since undef is lower than unknown.  IOW why not
>> change
>> the algorithm to start off each cell as undef and not unknown?
>
> Because then you can't distinguish between not visited and undef.
>>
>>
>> -- Sanjoy
>>
>> On Fri, Dec 30, 2016 at 9:27 AM, Davide Italiano via llvm-dev
>> <llvm-dev at lists.llvm.org> wrote:
>> > Hi.
>> > I'm sending this email to -dev as this may be of interest of
>> > many/people may have opinions/want to try the change before it
goes in
>> > to report problems.
>> > I've been recently working on a patch to integrate `undef` in
the SCCP
>> > solver, in the hope of fixing a tail of latent bugs in SCCP which
>> > remained uncovered for many years. I think this is a decent time
to
>> > propose, so that it can (hopefully) be integrated in the 4.0
branch
>> > (or backported, FWIW), if it gets reviewed and there are no
>> > substantial problems.
>> >
>> > #### Background:
>> > The current lattice for SCCP doesn't know about `undef`, that
is, it's
>> > identical to the one described in [1]. There are three lattice
states,
>> > "Unknown"/"Constant"/"Overdefined"
(the first one is what the paper
>> > calls "Undefined", but was renamed as
"undefined" in LLVM has a
>> > different meaning).
>> >
>> > SCCP (or its interprocedural counterpart) currently consists of
two
>> > phases:
>> > 1) The solver, which implements the algorithm described in the
paper.
>> > At the end of this phase, if there are no `undef` values in the
input,
>> > all the values supposedly have been lowered (in a
lattice-theoretical
>> > sense) to either constant or overdefined. In presence of `undef`,
>> > there may be values which are still in the 'unknown'
state.
>> > 2) The resolver assumes that everything in the 'unknown'
state is
>> > undefined, and runs a procedure trying to plug the
"correct" value,
>> > and in case something changed, runs the solver again.
>> >
>> > #### Problem/Motivation for the change:
>> > 1) and 2) use different orders of visitation. 1) walks the use-def
>> > chains, 2) visit the function in basic block order (starting from
the
>> > entry block of the function).
>> > The fact that 2) walks over the function instead of the SSA graph
>> > creates some issues where it cannot distinguish between the
following
>> > two cases:
>> >
>> > a) It doesn't know how to resolve this value
>> > b) This value is really undef.
>> >
>> > and may plug in wrong/invalid values. For a real example, see the
bug
>> > in [3], for a proof of why it's wrong, see [2] (courtesy of
Daniel
>> > Berlin).
>> >
>> > #### Proposed fix:
>> > Integrate `undef` in the solver. Undef is a lattice value lower
than
>> > `Unknown` but higher than `Overdefined` (at the same lattice level
of
>> > constant). Graphically:
>> >
>> >    unknown
>> >     /     \      \
>> >    /       \      \
>> >  c1 ...  ck undefined
>> >   \         |       /
>> >    \        |      /
>> >    overdefined
>> >
>> >
>> > #### Benefits:
>> > -> The code now is correct (modulo other bugs =)) in presence
of undefs
>> > -> This allows us to keep the same lattice height and therefore
all
>> > the nice termination/convergence properties/bounds (see the paper
for
>> > reference).
>> > -> This allows to remove a lot of code (pretty much the
resolver) and
>> > makes the algorithm easier to understand
>> > -> SCCP doesn't need anymore to roll its own tiny constant
folder
>> > where we need to add cases everytime we realize there's
something
>> > missing, instead, it can leverage the full power of
ConstantFolding
>> > when something folds to undef.
>> > -> Makes SCCP *slightly* faster.
>> >
>> > #### (Potential) drawbacks:
>> > -> This change the behavior of `phi` handling, i.e. we lose
some cases
>> > as we force phi to overdefined if not the values are constant. I
>> > measured the impact on the llvm-testsuite and on some internal
>> > benchmarks and I wasn't able to measure any substantial
different in
>> > runtime performances. If you care about this case, please speak up
=)
>> > (or try the patch and report regressions). There are probably ways
to
>> > make this working but we (see [4], comment 7 and 8) think the gain
in
>> > precision is not worth the complexity (and what's here is
*much much*
>> > better than what's in the tree as it tries at least to be
correct).
>> >
>> > #### Plan for integration
>> > The patch is available at https://reviews.llvm.org/D28177
>> > Any comments/feedback/testing is definitely welcome. This is a
>> > self-contained change.
>> >
>> > #### (Possible) future work
>> > If this goes in I'd like to implement constant propagation for
missing
>> > IR constructs (in particular vectors), and make sure SCCP is on
par
>> > with the other two costant propagation passes we have in llvm (and
>> > maybe garbage collect them).
>> > Danny suggested an improvement could be that of propagating facts
in
>> > both directions (GCC does that as a separate pass
>> > https://gcc.gnu.org/svn/gcc/trunk/gcc/gimple-ssa-backprop.c). I
have
>> > no immediate plans to work on this (I suspect NewGVN and other
places
>> > will keep me busy for a while), but I hope to eventually get
there.
>> >
>> > #### Thanks
>> > Eli Friedman and Daniel Berlin provided very insightful
>> > conversations/suggestions on how to tackle the problems, and
provided
>> > early feedback on the change (other than reviewing large part if
not
>> > all my previous work on SCCP).
>> >
>> >
>> > [1] https://www.cs.utexas.edu/users/lin/cs380c/wegman.pdf
>> > [2]
>> >
http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20161107/403212.html
>> > [3] https://llvm.org/bugs/show_bug.cgi?id=30448
>> > [4] https://llvm.org/bugs/show_bug.cgi?id=30966#c8
>> >
>> > --
>> > Davide
>> >
>> > "There are no solved problems; there are only problems that
are more
>> > or less solved" -- Henri Poincare
>> > _______________________________________________
>> > LLVM Developers mailing list
>> > llvm-dev at lists.llvm.org
>> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>>
>>
>> --
>> Sanjoy Das
>> http://playingwithpointers.com
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


-- 
Sanjoy Das
http://playingwithpointers.com

On Fri, Dec 30, 2016 at 9:47 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
>
>>   Is there a case in your algorithm in which treating an
>>> unknown as an undef will be a problem?
>>>
>>> Yes, if you try to optimize undefs in any way, no if you move them
to
> overdefined :)
>
> IE given phi [a, undef, undef, undef]
>
> with just as many back edges, you will visit this node 4 times.
>
> If you start out with
>
> phi [a, undef, undef, undef], you may think "I know, i will make 
these
> undef's a".
>
> So you move everything to value
>
> phi [a, a, a, a]
>
> But remember, you really haven't visited the other 4 edges yet, so you
> don't know if this is a valid value for undef (because of the rules
around
> and/or/etc, see http://llvm.org/docs/LangRef.html#undefined-values).
>
> (a, a, a, a of course, is just an example, you also don't know if
it's
> valid to always return undef, or 0, or 1, or anything at all, really).
>
> It's not until you hit this node for the 4th time, that you can really
> safely choose a value.
>
> If you have unknown and undef, it goes from
>
> phi [a, unknown, unknown, unknown] to phi [a, undef, unknown, unknown] to
> ...
>
> you know, once you have no unknown values, that everything you need to
> know to resolve it is known.
>
> (this is also why there is no need for a resolver. There really is no safe
> logic in the resolver that can't be pushed into the solver, though it
may
> make sense to structure it as a resolver if you think it's easier)
>
> Similarly for or %x, undef.
> You need to know if it's really undef, not "something i
haven't visited
> yet".
>
Whoops, hit send earlier.

Most of this gets taken care of by iterating in def-use order, but not for
phis or things dependent on them.

(especially if you want to resolve a phi node from a real value to undef)
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161230/2bd8f75e/attachment.html>

>
>
> >
> > You need to distinguish between not visited and visited but undef.
>
> What I'm getting at is, if you're implementing something close to
the
> paper mentioned, I can't think of a case where you'd care to
> distinguish between "not visited" and "visited but
undef".  That is,
> instead of starting from "map each each instruction as not
visited" we
> should be able to (my unproven conjecture) start from "map each
> instruction to undef", making the "unknown" element
superfluous.
>
See the email i just sent.

Your scheme would work if you didn't want to optimize undef, because
you'd
just make meet (anything, undef) -> overdefined.
It's the "we want to fill in values for undef" that makes it so
you need to
know when you can actually do that.
(and as mentioned, you don't need a separate post-resolver to do *what we
do now*, and so far, it has just been a source of bugs :()
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161230/a0a0ac7d/attachment.html>