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

[Davide Italiano via llvm-dev]

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. 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). 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)

-- 
Davide

"There are no solved problems; there are only problems that are more
or less solved" -- Henri Poincare