<br><br><div class="gmail_quote"><div dir="ltr">On Fri, Dec 30, 2016, 9:04 PM Sanjoy Das via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi David,<br class="gmail_msg">
<br class="gmail_msg">
Looking at the original bug, it seems like a straightforward<br class="gmail_msg">
undef-propagation bug to me -- SCCP was folding "or undef, constant"<br class="gmail_msg">
to "undef", which is wrong. Why is changing that not the fix? That<br class="gmail_msg">
is, some variant of<br class="gmail_msg"></blockquote></div><div><br></div><div>You would still need to fix the iteration order of the resolver, or it will make more wrong decisions.</div><div>As Davide discovered, there are bugs open with the same cause.</div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br class="gmail_msg">
diff --git a/lib/Transforms/Scalar/SCCP.cpp b/lib/Transforms/Scalar/SCCP.cpp<br class="gmail_msg">
index 8a6be97..45f1241 100644<br class="gmail_msg">
--- a/lib/Transforms/Scalar/SCCP.cpp<br class="gmail_msg">
+++ b/lib/Transforms/Scalar/SCCP.cpp<br class="gmail_msg">
@@ -908,8 +908,18 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) {<br class="gmail_msg">
}<br class="gmail_msg">
<br class="gmail_msg">
// If something is undef, wait for it to resolve.<br class="gmail_msg">
- if (!V1State.isOverdefined() && !V2State.isOverdefined())<br class="gmail_msg">
- return;<br class="gmail_msg">
+ if (!V1State.isOverdefined() && !V2State.isOverdefined()) {<br class="gmail_msg">
+ Constant *L = UndefValue::get(I.getOperand(0)->getType());<br class="gmail_msg">
+ if (V1State.isConstant())<br class="gmail_msg">
+ L = V1State.getConstant();<br class="gmail_msg">
+ Constant *R = UndefValue::get(I.getOperand(0)->getType());<br class="gmail_msg">
+ if (V2State.isConstant())<br class="gmail_msg">
+ R = V2State.getConstant();<br class="gmail_msg">
+ Constant *C = ConstantExpr::get(I.getOpcode(), L, R);<br class="gmail_msg">
+ if (isa<UndefValue>(C))<br class="gmail_msg">
+ return;<br class="gmail_msg">
+ return markConstant(IV, &I, C);<br class="gmail_msg">
+ }<br class="gmail_msg">
<br class="gmail_msg">
// Otherwise, one of our operands is overdefined. Try to produce something<br class="gmail_msg">
// better than overdefined with some tricks.<br class="gmail_msg">
<br class="gmail_msg">
<br class="gmail_msg">
<br class="gmail_msg">
<br class="gmail_msg">
Also, did you mean to make the lattice as:<br class="gmail_msg">
<br class="gmail_msg">
digraph G {<br class="gmail_msg">
Unknown -> Undef<br class="gmail_msg">
Undef -> Constant1<br class="gmail_msg">
Undef -> Constant2<br class="gmail_msg">
Undef -> Constant3<br class="gmail_msg">
Constant1 -> Bottom<br class="gmail_msg">
Constant2 -> Bottom<br class="gmail_msg">
Constant3-> Bottom<br class="gmail_msg">
}<br class="gmail_msg">
<br class="gmail_msg">
? In the lattice you've drawn, Constant MEET Undef will be Bottom,<br class="gmail_msg">
when it should ideally be Constant.<br class="gmail_msg">
<br class="gmail_msg">
Secondly, what's the purpose of splitting Unknown and Undef in the new<br class="gmail_msg">
scheme?</blockquote></div><div><br></div><div><br></div><div>You need to distinguish between not visited and visited but undef.</div><div><br></div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> Is there a case in your algorithm in which treating an<br class="gmail_msg">
unknown as an undef will be a problem?<br class="gmail_msg">
<br class="gmail_msg">
Actually given the above lattice (assuming you're okay with that) we know<br class="gmail_msg">
treating unknown as undef should not make us any less conservative<br class="gmail_msg">
(i.e. should be safe) since undef is lower than unknown. IOW why not change<br class="gmail_msg">
the algorithm to start off each cell as undef and not unknown?<br class="gmail_msg"></blockquote></div><div>Because then you can't distinguish between not visited and undef.</div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br class="gmail_msg">
-- Sanjoy<br class="gmail_msg">
<br class="gmail_msg">
On Fri, Dec 30, 2016 at 9:27 AM, Davide Italiano via llvm-dev<br class="gmail_msg">
<<a href="mailto:llvm-dev@lists.llvm.org" class="gmail_msg" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br class="gmail_msg">
> Hi.<br class="gmail_msg">
> I'm sending this email to -dev as this may be of interest of<br class="gmail_msg">
> many/people may have opinions/want to try the change before it goes in<br class="gmail_msg">
> to report problems.<br class="gmail_msg">
> I've been recently working on a patch to integrate `undef` in the SCCP<br class="gmail_msg">
> solver, in the hope of fixing a tail of latent bugs in SCCP which<br class="gmail_msg">
> remained uncovered for many years. I think this is a decent time to<br class="gmail_msg">
> propose, so that it can (hopefully) be integrated in the 4.0 branch<br class="gmail_msg">
> (or backported, FWIW), if it gets reviewed and there are no<br class="gmail_msg">
> substantial problems.<br class="gmail_msg">
><br class="gmail_msg">
> #### Background:<br class="gmail_msg">
> The current lattice for SCCP doesn't know about `undef`, that is, it's<br class="gmail_msg">
> identical to the one described in [1]. There are three lattice states,<br class="gmail_msg">
> "Unknown"/"Constant"/"Overdefined" (the first one is what the paper<br class="gmail_msg">
> calls "Undefined", but was renamed as "undefined" in LLVM has a<br class="gmail_msg">
> different meaning).<br class="gmail_msg">
><br class="gmail_msg">
> SCCP (or its interprocedural counterpart) currently consists of two phases:<br class="gmail_msg">
> 1) The solver, which implements the algorithm described in the paper.<br class="gmail_msg">
> At the end of this phase, if there are no `undef` values in the input,<br class="gmail_msg">
> all the values supposedly have been lowered (in a lattice-theoretical<br class="gmail_msg">
> sense) to either constant or overdefined. In presence of `undef`,<br class="gmail_msg">
> there may be values which are still in the 'unknown' state.<br class="gmail_msg">
> 2) The resolver assumes that everything in the 'unknown' state is<br class="gmail_msg">
> undefined, and runs a procedure trying to plug the "correct" value,<br class="gmail_msg">
> and in case something changed, runs the solver again.<br class="gmail_msg">
><br class="gmail_msg">
> #### Problem/Motivation for the change:<br class="gmail_msg">
> 1) and 2) use different orders of visitation. 1) walks the use-def<br class="gmail_msg">
> chains, 2) visit the function in basic block order (starting from the<br class="gmail_msg">
> entry block of the function).<br class="gmail_msg">
> The fact that 2) walks over the function instead of the SSA graph<br class="gmail_msg">
> creates some issues where it cannot distinguish between the following<br class="gmail_msg">
> two cases:<br class="gmail_msg">
><br class="gmail_msg">
> a) It doesn't know how to resolve this value<br class="gmail_msg">
> b) This value is really undef.<br class="gmail_msg">
><br class="gmail_msg">
> and may plug in wrong/invalid values. For a real example, see the bug<br class="gmail_msg">
> in [3], for a proof of why it's wrong, see [2] (courtesy of Daniel<br class="gmail_msg">
> Berlin).<br class="gmail_msg">
><br class="gmail_msg">
> #### Proposed fix:<br class="gmail_msg">
> Integrate `undef` in the solver. Undef is a lattice value lower than<br class="gmail_msg">
> `Unknown` but higher than `Overdefined` (at the same lattice level of<br class="gmail_msg">
> constant). Graphically:<br class="gmail_msg">
><br class="gmail_msg">
> unknown<br class="gmail_msg">
> / \ \<br class="gmail_msg">
> / \ \<br class="gmail_msg">
> c1 ... ck undefined<br class="gmail_msg">
> \ | /<br class="gmail_msg">
> \ | /<br class="gmail_msg">
> overdefined<br class="gmail_msg">
><br class="gmail_msg">
><br class="gmail_msg">
> #### Benefits:<br class="gmail_msg">
> -> The code now is correct (modulo other bugs =)) in presence of undefs<br class="gmail_msg">
> -> This allows us to keep the same lattice height and therefore all<br class="gmail_msg">
> the nice termination/convergence properties/bounds (see the paper for<br class="gmail_msg">
> reference).<br class="gmail_msg">
> -> This allows to remove a lot of code (pretty much the resolver) and<br class="gmail_msg">
> makes the algorithm easier to understand<br class="gmail_msg">
> -> SCCP doesn't need anymore to roll its own tiny constant folder<br class="gmail_msg">
> where we need to add cases everytime we realize there's something<br class="gmail_msg">
> missing, instead, it can leverage the full power of ConstantFolding<br class="gmail_msg">
> when something folds to undef.<br class="gmail_msg">
> -> Makes SCCP *slightly* faster.<br class="gmail_msg">
><br class="gmail_msg">
> #### (Potential) drawbacks:<br class="gmail_msg">
> -> This change the behavior of `phi` handling, i.e. we lose some cases<br class="gmail_msg">
> as we force phi to overdefined if not the values are constant. I<br class="gmail_msg">
> measured the impact on the llvm-testsuite and on some internal<br class="gmail_msg">
> benchmarks and I wasn't able to measure any substantial different in<br class="gmail_msg">
> runtime performances. If you care about this case, please speak up =)<br class="gmail_msg">
> (or try the patch and report regressions). There are probably ways to<br class="gmail_msg">
> make this working but we (see [4], comment 7 and 8) think the gain in<br class="gmail_msg">
> precision is not worth the complexity (and what's here is *much much*<br class="gmail_msg">
> better than what's in the tree as it tries at least to be correct).<br class="gmail_msg">
><br class="gmail_msg">
> #### Plan for integration<br class="gmail_msg">
> The patch is available at <a href="https://reviews.llvm.org/D28177" rel="noreferrer" class="gmail_msg" target="_blank">https://reviews.llvm.org/D28177</a><br class="gmail_msg">
> Any comments/feedback/testing is definitely welcome. This is a<br class="gmail_msg">
> self-contained change.<br class="gmail_msg">
><br class="gmail_msg">
> #### (Possible) future work<br class="gmail_msg">
> If this goes in I'd like to implement constant propagation for missing<br class="gmail_msg">
> IR constructs (in particular vectors), and make sure SCCP is on par<br class="gmail_msg">
> with the other two costant propagation passes we have in llvm (and<br class="gmail_msg">
> maybe garbage collect them).<br class="gmail_msg">
> Danny suggested an improvement could be that of propagating facts in<br class="gmail_msg">
> both directions (GCC does that as a separate pass<br class="gmail_msg">
> <a href="https://gcc.gnu.org/svn/gcc/trunk/gcc/gimple-ssa-backprop.c" rel="noreferrer" class="gmail_msg" target="_blank">https://gcc.gnu.org/svn/gcc/trunk/gcc/gimple-ssa-backprop.c</a>). I have<br class="gmail_msg">
> no immediate plans to work on this (I suspect NewGVN and other places<br class="gmail_msg">
> will keep me busy for a while), but I hope to eventually get there.<br class="gmail_msg">
><br class="gmail_msg">
> #### Thanks<br class="gmail_msg">
> Eli Friedman and Daniel Berlin provided very insightful<br class="gmail_msg">
> conversations/suggestions on how to tackle the problems, and provided<br class="gmail_msg">
> early feedback on the change (other than reviewing large part if not<br class="gmail_msg">
> all my previous work on SCCP).<br class="gmail_msg">
><br class="gmail_msg">
><br class="gmail_msg">
> [1] <a href="https://www.cs.utexas.edu/users/lin/cs380c/wegman.pdf" rel="noreferrer" class="gmail_msg" target="_blank">https://www.cs.utexas.edu/users/lin/cs380c/wegman.pdf</a><br class="gmail_msg">
> [2] <a href="http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20161107/403212.html" rel="noreferrer" class="gmail_msg" target="_blank">http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20161107/403212.html</a><br class="gmail_msg">
> [3] <a href="https://llvm.org/bugs/show_bug.cgi?id=30448" rel="noreferrer" class="gmail_msg" target="_blank">https://llvm.org/bugs/show_bug.cgi?id=30448</a><br class="gmail_msg">
> [4] <a href="https://llvm.org/bugs/show_bug.cgi?id=30966#c8" rel="noreferrer" class="gmail_msg" target="_blank">https://llvm.org/bugs/show_bug.cgi?id=30966#c8</a><br class="gmail_msg">
><br class="gmail_msg">
> --<br class="gmail_msg">
> Davide<br class="gmail_msg">
><br class="gmail_msg">
> "There are no solved problems; there are only problems that are more<br class="gmail_msg">
> or less solved" -- Henri Poincare<br class="gmail_msg">
> _______________________________________________<br class="gmail_msg">
> LLVM Developers mailing list<br class="gmail_msg">
> <a href="mailto:llvm-dev@lists.llvm.org" class="gmail_msg" target="_blank">llvm-dev@lists.llvm.org</a><br class="gmail_msg">
> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" class="gmail_msg" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br class="gmail_msg">
<br class="gmail_msg">
<br class="gmail_msg">
<br class="gmail_msg">
--<br class="gmail_msg">
Sanjoy Das<br class="gmail_msg">
<a href="http://playingwithpointers.com" rel="noreferrer" class="gmail_msg" target="_blank">http://playingwithpointers.com</a><br class="gmail_msg">
_______________________________________________<br class="gmail_msg">
LLVM Developers mailing list<br class="gmail_msg">
<a href="mailto:llvm-dev@lists.llvm.org" class="gmail_msg" target="_blank">llvm-dev@lists.llvm.org</a><br class="gmail_msg">
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" class="gmail_msg" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br class="gmail_msg">
</blockquote></div>