<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Jan 3, 2017 at 9:45 AM, Davide Italiano <span dir="ltr"><<a href="mailto:davide@freebsd.org" target="_blank">davide@freebsd.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class="gmail-HOEnZb"><div class="gmail-h5">On Mon, Jan 2, 2017 at 3:26 PM, Sanjoy Das<br>
<<a href="mailto:sanjoy@playingwithpointers.com">sanjoy@playingwithpointers.<wbr>com</a>> wrote:<br>
> Hi Davide,<br>
><br>
> On Mon, Jan 2, 2017 at 2:48 PM, Davide Italiano <<a href="mailto:davide@freebsd.org">davide@freebsd.org</a>> wrote:<br>
>> Your comments are of course very welcome (that goes without saying).<br>
>> Are you happy with me experimenting with something similar to what<br>
>> Danny proposed (a pre-solver computing the SCCs on the SSA graph?).<br>
><br>
> SGTM!<br>
><br>
>> At<br>
>> this point this is my favourite solution because we can stick with the<br>
>> default algorithm (which will keep me happier as somebody else did the<br>
>> hard work of proving correct on my behalf).<br>
><br>
> Sounds good!<br>
><br>
> -- Sanjoy<br>
<br>
</div></div>Sending a real (updated) proposal to make sure we're all on the same<br>
page (and the idea makes sense), in case somebody not following the<br>
earlier discussion wants to comment. I haven't checked if LLVM has<br>
functions for solving the individual steps (feel free to suggest).<br>
<br>
The algorithm (if I understood the idea correctly) is more or less the<br>
following:<br>
1) Build the def-use chain graph.<br>
2) Compute the set of SCCs of the graph<br>
3) Compute RPO of the DAG formed at 2) and visit the nodes(SCCs)<br>
according to that order<br>
Within each SCC sort topologically and use RPO within the SCC (as a<br>
worklist) until a fixed-point is reached (as we do here<br>
<a href="https://github.com/dcci/llvm/blob/master/lib/Transforms/Scalar/ConstantProp.cpp#L78" rel="noreferrer" target="_blank">https://github.com/dcci/llvm/<wbr>blob/master/lib/Transforms/<wbr>Scalar/ConstantProp.cpp#L78</a><br>
just with a different visitation order). If something is found to be<br>
folded to `undef`, we propagate the information through the DAG.<br>
<br>
I think this should work for SCCP, I'm trying to convince myself how<br>
this generalizes to IPSCCP.</blockquote><div><br></div><div>It works trivially if you have either ip-ssa or ip-cfg's :)<br>Otherwise, you have to do some work.</div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> After the pre-solver run there shouldn't<br>
be `undef` values which can be propagated anymore and we can run the<br>
solver on a lattice which doesn't know (and shouldn't know) about<br>
undef.<br>
<br>
Any comment/correction is appreciated, that goes without saying =)<br>
<br>
P.S. (mainly curiosity). I wasn't able to find anything in literature<br>
describing an algorithm using this approach for CP (although I haven't<br>
tried really hard). </blockquote><div><br></div><div>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 :)</div><div><br></div><div>You will find it for value numbering:</div><div><a href="http://softlib.rice.edu/pub/CRPC-TRs/reports/CRPC-TR95636-S.pdf">http://softlib.rice.edu/pub/CRPC-TRs/reports/CRPC-TR95636-S.pdf</a></div><div><br></div><div>Here's the extended nuweb version, which has all the actual code:</div><div><a href="http://www.cs.ucsb.edu/~ckrintz/papers/valnum.ps.gz">http://www.cs.ucsb.edu/~ckrintz/papers/valnum.ps.gz</a><br></div><div><br></div><div>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.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Nielson's book describes the approach of using<br>
SCCs for a more intelligent worklist ordering<br>
<a href="http://www.imm.dtu.dk/~hrni/PPA/slides6.pdf" rel="noreferrer" target="_blank">http://www.imm.dtu.dk/~hrni/<wbr>PPA/slides6.pdf</a> for constraint solvers in<br>
general and <a href="http://homepages.dcc.ufmg.br/~fernando/publications/papers/CGO13_raphael.pdf" rel="noreferrer" target="_blank">http://homepages.dcc.ufmg.br/~<wbr>fernando/publications/papers/<wbr>CGO13_raphael.pdf</a><br>
applies this to range analysis (maybe SCCP can be somehow seen as a<br>
special case/simpler form of)<br></blockquote><div><br></div></div></div></div>