[LLVMdev] Bug 16257 - fmul of undef ConstantExpr not folded to undef

[Duncan Sands]

Hi Oleg,

On 26/08/14 21:20, Oleg Ranevskyy wrote:
> Hi Duncan,
>
> Thank you for your comment to the bug 16257.
>
> I am new to LLVM, so not all the aspects of LLVM's /"undef"/ seem clear to me yet.
> I read and understood the examples from the LLVM documentation:
> http://llvm.org/docs/LangRef.html#undefined-values
>
> However, those examples do not cover all of the possible contexts where
> /"undef"/ can appear.
> E.g., I can't realize why /"fmul undef, undef"/ may not result in/"undef"/
> whereas /"mul undef, undef"/ is always folded to /"undef"/. Seems I am missing
> something important about floats here.

in the case of mul undef, undef, the two inputs may be anything.  In order to 
fold the mul to undef you have to prove that the output may be anything (any bit 
pattern).  For example it would be wrong to fold "mul 0, undef" to undef since 
no matter what value you substitute for "undef" the output of the mul will 
always be zero.  Note that in something like "mul undef, undef", where undef 
occurs more than once, you are allowed to assume that the two undefs are 
independent of each other, uncorrelated, i.e. in your reasoning you can insert 
any bit pattern for the first undef and any other bit pattern for the second undef.

Here is a proof that "mul undef, undef" is undef.  Let R represent an arbitrary 
bit pattern.  We have to find two bit patterns X and Y such that "mul X, Y" is 
equal to R.  For example set X to 1 and Y to R.  This ends the proof.

Now consider "fmul undef, undef".  You could try to apply the same reasoning, 
and maybe it is OK.  Let R represent an arbitrary bit pattern.  Set Y = R and 
set X to be the bit pattern for the floating point number 1.0.  Then "fmul X, Y" 
is equal to R, proving that "fmul undef, undef" can be folded to "undef". 
But... is this correct?  Is it always true that "fmul 1.0, R" always has exactly 
the same bits as R (this is not the same as the output comparing equal to R 
using a floating point comparison)?  After all, R might be something funky like 
a signed zero, an infinity, or a NaN.  I don't know if it is always true if 
"fmul 1.0, R" always has the same bits as R, hopefully a floating point expert 
can tell us.

You could always argue that you could choose "undef" to be a signalling NaN, 
causing the program to have undefined behaviour at the point of the 
multiplication, in which case you could do anything, but kindly instead just 
fold the fmul to undef.  I don't much like using snans like this though since 
they can be made non-signalling by poking the processor AFAIK.

>
> The same applies to "fdiv".
> /"fdiv undef, undef"/ is not folded but /"div %X, undef"/ and /"div undef, %X"/
> are folded to /"undef"/ (SimplifyFDivInst function in
> lib/Analysis/InstructionSimplify.cpp).

Here is the argument for "div %X, undef -> undef".  The undef value might be 
zero (div %X, 0), so lets choose it to be zero.  That means that the program has 
undefined behaviour at this point, and so we could fold the div to "exit(1)" or 
"launch nuclear missile".  But instead we only fold it to undef.

You are wrong to say that "div undef, %X" is folded to "undef" by 
InstructionSimplify, it is folded to zero.  It would be wrong to fold to undef, 
since (eg) if %X is 2 then you can't obtain an arbitrary bit pattern as the output.

Fdiv is harder than div because a floating point division by 0.0 has a defined 
result, unlike for div.

  Moreover, SimplifyFDivInst does not take
> into account whether signalling of SNaNs can be switched off or not - it always
> folds if one of the operands is /"undef"/.

This is either a mistake, or a decision that in LLVM IR snans are always 
considered to be signalling.

>
> Another mysterious thing for me is folding of /"mul %X, undef"/.
> The result depends on whether %X is odd or even:
>
>   * "undef" if %X is odd or equal to "undef";
>   * 0 otherwise.

InstructionSimplify folds "mul %X, undef" to 0 always, since after all "undef" 
could be zero, in which case the output is 0.  It would be wrong to fold it to 
undef, as you point out, and it isn't folded to undef.

>
> There is a similar bug 16258 about folding of /"fadd undef, undef"/. /"Add"
> /gets folded to /"undef"/ if one or both its operands are /"undef"/.
> Should /"fadd"/ behave differently than integer /"add"/ too?

It's the same problem.  It is easy to show that "add undef, %X" can produce any 
desired bit pattern as output, but it is less clear whether that is true for 
fadd, unless you use the snan argument.

Ciao, Duncan.

>
> I've tried to google these questions, scanned StackOverflow, but didn't find any
> good articles / posts answering them. LLVM's /"undef"/ is covered quite poorly.
>
> Duncan, do you know of any web resources explaining this in more detail?
>
> Thank you in advance for any help.
>
> Kind regards,
> Oleg