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

[Davide Italiano via llvm-dev]

Replying one mail at the time, still in a different timezone =)

On Fri, Dec 30, 2016 at 7:41 PM, Sean Silva <chisophugis at gmail.com> wrote:
>
>> -> 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?
>

Right now SCCP is implemented as a visitor for each instruction with
more or less the following structure:

visitInstruction(Instruction &I) {
   // This is not true in general because you can infer constant
values (sometimes) even if one of the operand is overdefined,
   // but just for simplicity
   if (operands are overdefined)
     markOverdefined(&I);
   [...]
   Constant *C = tryToConstantFold(...);
   if (isa<UndefValue>(C))
     return;
   markConstant(&I, C);
}

(see https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Scalar/SCCP.cpp#L797
for a concrete example).

Pretty much, the solver delegates the folding to ConstantFolding.cpp
et similia, but doesn't lower the lattice value to constant if the
result of folding is `undef` value. In other words, everything that's
undef/folds to undef won't be lowered in the Solver, i.e. will still
have an `Unknown` lattice state after the solver finishes.

What the resolver does is walking the BBs and trying to plug the
correct values with the informations it has.
See a couple of examples in `ResolvedUndefsIn`

https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Scalar/SCCP.cpp#L1382
or https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Scalar/SCCP.cpp#L1390

These are cases which the constant folder will get just right, but we
silently ignore because if something folds to undef then we don't
assign a constant value. Therefore, `ResolvedUndefsIn` has to perform
extra work to plug in the "correct" values.
>>
>> -> 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.
>

See comment above. Hope it makes sense. Thanks for pointing out and
sorry if it wasn't clear in the original mail (it wasn't obvious to me
in the beginning as well).

-- 
Davide

"There are no solved problems; there are only problems that are more
or less solved" -- Henri Poincare