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

[Daniel Berlin via llvm-dev]

On Tue, Jan 3, 2017 at 9:45 AM, Davide Italiano <davide at freebsd.org> wrote:

> On Mon, Jan 2, 2017 at 3:26 PM, Sanjoy Das
> <sanjoy at playingwithpointers.com> wrote:
> > Hi Davide,
> >
> > On Mon, Jan 2, 2017 at 2:48 PM, Davide Italiano <davide at freebsd.org>
> wrote:
> >> Your comments are of course very welcome (that goes without saying).
> >> Are you happy with me experimenting with something similar to what
> >> Danny proposed (a pre-solver computing the SCCs on the SSA graph?).
> >
> > SGTM!
> >
> >> At
> >> this point this is my favourite solution because we can stick with the
> >> default algorithm (which will keep me happier as somebody else did the
> >> hard work of proving correct on my behalf).
> >
> > Sounds good!
> >
> > -- Sanjoy
>
> Sending a real (updated) proposal to make sure we're all on the same
> page (and the idea makes sense), in case somebody not following the
> earlier discussion wants to comment. I haven't checked if LLVM has
> functions for solving the individual steps (feel free to suggest).
>
> The algorithm (if I understood the idea correctly) is more or less the
> following:
> 1) Build the def-use chain graph.
> 2) Compute the set of SCCs of the graph
> 3) Compute RPO of the DAG formed at 2) and visit the nodes(SCCs)
> according to that order
> Within each SCC sort topologically and use RPO within the SCC (as a
> worklist) until a fixed-point is reached (as we do here
> https://github.com/dcci/llvm/blob/master/lib/Transforms/
> Scalar/ConstantProp.cpp#L78
> just with a different visitation order). If something is found to be
> folded to `undef`, we propagate the information through the DAG.
>
> I think this should work for SCCP, I'm trying to convince myself how
> this generalizes to IPSCCP.


It works trivially if you have either ip-ssa or ip-cfg's :)
Otherwise, you have to do some work.


> After the pre-solver run there shouldn't
> be `undef` values which can be propagated anymore and we can run the
> solver on a lattice which doesn't know (and shouldn't know) about
> undef.
>
> Any comment/correction is appreciated, that goes without saying =)
>
> P.S. (mainly curiosity). I wasn't able to find anything in literature
> describing an algorithm using this approach for CP (although I haven't
> tried really hard).


It's generally not necessary, and it goes without saying it's going to be
hard to find a compiler that basically has a value type that requires
constraint solving as part of constant propagation :)

You will find it for value numbering:
http://softlib.rice.edu/pub/CRPC-TRs/reports/CRPC-TR95636-S.pdf

Here's the extended nuweb version, which has all the actual code:
http://www.cs.ucsb.edu/~ckrintz/papers/valnum.ps.gz

The only difference in practice is a lattice instead of a hash table, and
for a lattice, you should not need a valid vs optimistic table.


> Nielson's book describes the approach of using
> SCCs for a more intelligent worklist ordering
> http://www.imm.dtu.dk/~hrni/PPA/slides6.pdf for constraint solvers in
> general and http://homepages.dcc.ufmg.br/~fernando/publications/papers/
> CGO13_raphael.pdf
> applies this to range analysis (maybe SCCP can be somehow seen as a
> special case/simpler form of)
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170103/6cc9fe9b/attachment.html>