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