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

[Daniel Berlin via llvm-dev]

>
>
>> -> The code now is correct (modulo other bugs =)) in presence of undefs
>> -> This allows us to keep the same lattice height and therefore all
>> the nice termination/convergence properties/bounds (see the paper for
>> reference).
>> -> This allows to remove a lot of code (pretty much the resolver) and
>> makes the algorithm easier to understand
>>
>
> How does this eliminate the need for the resolver? Without the resolver,
> what will plug in values for the undef's?
>
>

You don't need a separate resolver to plug in values for the undefs.

Even if you wanted to super-optimize them, you wouldn't do it the way the
resolver does it (there are better strategies :P)


> -> SCCP doesn't need anymore to roll its own tiny constant folder
>> where we need to add cases everytime we realize there's something
>> missing, instead, it can leverage the full power of ConstantFolding
>> when something folds to undef.
>>
>
> 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.
>
> -- Sean Silva
>
>
>> -> Makes SCCP *slightly* faster.
>>
>> #### (Potential) drawbacks:
>> -> This change the behavior of `phi` handling, i.e. we lose some cases
>> as we force phi to overdefined if not the values are constant. I
>> measured the impact on the llvm-testsuite and on some internal
>> benchmarks and I wasn't able to measure any substantial different in
>> runtime performances. If you care about this case, please speak up =)
>> (or try the patch and report regressions). There are probably ways to
>> make this working but we (see [4], comment 7 and 8) think the gain in
>> precision is not worth the complexity (and what's here is *much much*
>> better than what's in the tree as it tries at least to be correct).
>>
>> #### Plan for integration
>> The patch is available at https://reviews.llvm.org/D28177
>> Any comments/feedback/testing is definitely welcome. This is a
>> self-contained change.
>>
>> #### (Possible) future work
>> If this goes in I'd like to implement constant propagation for missing
>> IR constructs (in particular vectors), and make sure SCCP is on par
>> with the other two costant propagation passes we have in llvm (and
>> maybe garbage collect them).
>> Danny suggested an improvement could be that of propagating facts in
>> both directions (GCC does that as a separate pass
>> https://gcc.gnu.org/svn/gcc/trunk/gcc/gimple-ssa-backprop.c). I have
>> no immediate plans to work on this (I suspect NewGVN and other places
>> will keep me busy for a while), but I hope to eventually get there.
>>
>> #### Thanks
>> Eli Friedman and Daniel Berlin provided very insightful
>> conversations/suggestions on how to tackle the problems, and provided
>> early feedback on the change (other than reviewing large part if not
>> all my previous work on SCCP).
>>
>>
>> [1] https://www.cs.utexas.edu/users/lin/cs380c/wegman.pdf
>> [2] http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-
>> 20161107/403212.html
>> [3] https://llvm.org/bugs/show_bug.cgi?id=30448
>> [4] https://llvm.org/bugs/show_bug.cgi?id=30966#c8
>>
>> --
>> Davide
>>
>> "There are no solved problems; there are only problems that are more
>> or less solved" -- Henri Poincare
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20161230/b87bd07f/attachment.html>