[llvm-dev] SCCP is not always correct in presence of undef (+ proposed fix)
Daniel Berlin via llvm-dev
llvm-dev at lists.llvm.org
Fri Dec 30 21:23:39 PST 2016
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>
More information about the llvm-dev
mailing list