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

[Davide Italiano via llvm-dev]

Hi.
I'm sending this email to -dev as this may be of interest of
many/people may have opinions/want to try the change before it goes in
to report problems.
I've been recently working on a patch to integrate `undef` in the SCCP
solver, in the hope of fixing a tail of latent bugs in SCCP which
remained uncovered for many years. I think this is a decent time to
propose, so that it can (hopefully) be integrated in the 4.0 branch
(or backported, FWIW), if it gets reviewed and there are no
substantial problems.

#### Background:
The current lattice for SCCP doesn't know about `undef`, that is, it's
identical to the one described in [1]. There are three lattice states,
"Unknown"/"Constant"/"Overdefined" (the first one is what the paper
calls "Undefined", but was renamed as "undefined" in LLVM has a
different meaning).

SCCP (or its interprocedural counterpart) currently consists of two phases:
1) The solver, which implements the algorithm described in the paper.
At the end of this phase, if there are no `undef` values in the input,
all the values supposedly have been lowered (in a lattice-theoretical
sense) to either constant or overdefined. In presence of `undef`,
there may be values which are still in the 'unknown' state.
2) The resolver assumes that everything in the 'unknown' state is
undefined, and runs a procedure trying to plug the "correct" value,
and in case something changed, runs the solver again.

#### Problem/Motivation for the change:
1) and 2) use different orders of visitation. 1) walks the use-def
chains, 2) visit the function in basic block order (starting from the
entry block of the function).
The fact that 2) walks over the function instead of the SSA graph
creates some issues where it cannot distinguish between the following
two cases:

a) It doesn't know how to resolve this value
b) This value is really undef.

and may plug in wrong/invalid values. For a real example, see the bug
in [3], for a proof of why it's wrong, see [2] (courtesy of Daniel
Berlin).

#### Proposed fix:
Integrate `undef` in the solver. Undef is a lattice value lower than
`Unknown` but higher than `Overdefined` (at the same lattice level of
constant). Graphically:

   unknown
    /     \      \
   /       \      \
 c1 ...  ck undefined
  \         |       /
   \        |      /
   overdefined


#### Benefits:
-> 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
-> 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.
-> 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