<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
Hi Duncan,<br>
<br>
Thank you a lot for your time to provide that great and informative
explanation.<br>
<div class="moz-cite-prefix">Now the "undef" logic makes much more
sense for me.<br>
<br>
>> <i>You are wrong to say that "div undef, %X" is folded
to "undef" by InstructionSimplify, it is folded to zero.</i><br>
My mistake. I meant to say "<b>f</b><b></b><b>div</b> undef, %X"
is folded to "undef" (not integer "div").<br>
<br>
>> <i>Fdiv is harder than div because a floating point
division by 0.0 has a defined result, unlike for div.
</i><br>
Probably, the "Undefined Values" section of LLVM IR documentation
(<a class="moz-txt-link-freetext" href="http://llvm.org/docs/LangRef.html#undefined-values">http://llvm.org/docs/LangRef.html#undefined-values</a>) needs a
correction.<br>
For the statement "fdiv %X, undef" it states:<br>
"because the undef is allowed to be an arbitrary value, we are
allowed to assume that it could be zero. <b>*</b><b>Since a
divide by zero has undefined behavior</b><b>*</b>...".<br>
This is not true for floats.<br>
<br>
>> <i>This is either a mistake, or a decision that in LLVM
IR snans are always considered to be signalling.
</i><br>
Yes, this seems to be an agreement to treat "undef" as a SNaN for
"fdiv".<br>
The question is whether we can make the same assumption for other
floating point operations, or "fdiv" needs a correction to prevent
folding since signalling of SNaNs might be disabled.<br>
<br>
>> <i>InstructionSimplify folds "mul %X, undef" to 0 always</i><br>
Sorry, I malformed this line and forgot to highlight that by "%X"
I meant a constant here. So, constant folding comes into play. The
result depends on the constant parity. E.g.:<br>
mul i64 5, undef --> undef<br>
mul i64 4, undef --> 0<br>
I still have difficulty understanding why the first one is folded
to "undef".<br>
"Undef" could be zero, so the result is also zero. Besides, if
"undef" isn't zero, it's impossible to get an arbitrary bit
pattern anyway. The result will always be divisible by 5.<br>
<br>
Would you be able to elaborate on this please?<br>
Thank you!<br>
<br>
Kind regards,<br>
Oleg<br>
<br>
On 26.08.2014 15:47, Duncan Sands wrote:<br>
</div>
<blockquote cite="mid:53FCAC2C.1070501@deepbluecap.com" type="cite">Hi
Oleg,
<br>
<br>
On 26/08/14 21:20, Oleg Ranevskyy wrote:
<br>
<blockquote type="cite">Hi Duncan,
<br>
<br>
Thank you for your comment to the bug 16257.
<br>
<br>
I am new to LLVM, so not all the aspects of LLVM's /"undef"/
seem clear to me yet.
<br>
I read and understood the examples from the LLVM documentation:
<br>
<a class="moz-txt-link-freetext" href="http://llvm.org/docs/LangRef.html#undefined-values">http://llvm.org/docs/LangRef.html#undefined-values</a>
<br>
<br>
However, those examples do not cover all of the possible
contexts where
<br>
/"undef"/ can appear.
<br>
E.g., I can't realize why /"fmul undef, undef"/ may not result
in/"undef"/
<br>
whereas /"mul undef, undef"/ is always folded to /"undef"/.
Seems I am missing
<br>
something important about floats here.
<br>
</blockquote>
<br>
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.
<br>
<br>
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.
<br>
<br>
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.
<br>
<br>
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.
<br>
<br>
<blockquote type="cite">
<br>
The same applies to "fdiv".
<br>
/"fdiv undef, undef"/ is not folded but /"div %X, undef"/ and
/"div undef, %X"/
<br>
are folded to /"undef"/ (SimplifyFDivInst function in
<br>
lib/Analysis/InstructionSimplify.cpp).
<br>
</blockquote>
<br>
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.
<br>
<br>
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.
<br>
<br>
Fdiv is harder than div because a floating point division by 0.0
has a defined result, unlike for div.
<br>
<br>
Moreover, SimplifyFDivInst does not take
<br>
<blockquote type="cite">into account whether signalling of SNaNs
can be switched off or not - it always
<br>
folds if one of the operands is /"undef"/.
<br>
</blockquote>
<br>
This is either a mistake, or a decision that in LLVM IR snans are
always considered to be signalling.
<br>
<br>
<blockquote type="cite">
<br>
Another mysterious thing for me is folding of /"mul %X, undef"/.
<br>
The result depends on whether %X is odd or even:
<br>
<br>
* "undef" if %X is odd or equal to "undef";
<br>
* 0 otherwise.
<br>
</blockquote>
<br>
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.
<br>
<br>
<blockquote type="cite">
<br>
There is a similar bug 16258 about folding of /"fadd undef,
undef"/. /"Add"
<br>
/gets folded to /"undef"/ if one or both its operands are
/"undef"/.
<br>
Should /"fadd"/ behave differently than integer /"add"/ too?
<br>
</blockquote>
<br>
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.
<br>
<br>
Ciao, Duncan.
<br>
<br>
<blockquote type="cite">
<br>
I've tried to google these questions, scanned StackOverflow, but
didn't find any
<br>
good articles / posts answering them. LLVM's /"undef"/ is
covered quite poorly.
<br>
<br>
Duncan, do you know of any web resources explaining this in more
detail?
<br>
<br>
Thank you in advance for any help.
<br>
<br>
Kind regards,
<br>
Oleg
<br>
</blockquote>
<br>
</blockquote>
<br>
</body>
</html>