<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p><br>
</p>
<div class="moz-cite-prefix">On 06/29/2017 07:26 PM, Peter Lawrence
wrote:<br>
</div>
<blockquote
cite="mid:56CF6936-E6DC-445C-AAEA-FB51E4FB89D5@sbcglobal.net"
type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
<div class="">Hal,</div>
<div class=""> Mehdi points out I mis-quoted you, I apologize
sincerely.</div>
<div class=""><br class="">
</div>
Mehdi,
<div class=""> Thank you for forcing me to go back and
re-read what Hal wrote,</div>
<div class="">I could have sworn Hal and I were in agreement at
the time I wrote you,</div>
<div class="">Must have been asleep at the wheel, not enough sleep
last night</div>
<div class="">However my request for a more concrete example
stands</div>
<div class=""><br class="">
</div>
<div class="">Here’s what I said</div>
<div class="">
<blockquote
cite="mid:8D1216F2-8E1C-4895-8DA2-19932A92BD1B@sbcglobal.net"
type="cite" style="background-color: rgb(255, 255, 255);"
class="">
<div class="">This doesn’t make sense to me, a shift amount of
48 is “undefined” for unsigned char,</div>
<div class="">How do we know this isn’t a source code bug,</div>
<div class="">What makes us think the the user intended the
result to be “0”.</div>
</blockquote>
<br class="">
Here’s what Hal said in response<br style="background-color:
rgb(255, 255, 255);" class="">
<span style="background-color: rgb(255, 255, 255);" class="">>
As I said, this is representation of what the real code did,
and looked like, after other </span></div>
<div class=""><span style="background-color: rgb(255, 255, 255);"
class="">> inlining had taken place, etc. In the original
form, the user's intent was </span></div>
<div class=""><span style="background-color: rgb(255, 255, 255);"
class="">> clear. That code is never executed when T is a
small integer type.</span><br style="background-color:
rgb(255, 255, 255);" class="">
<br style="background-color: rgb(255, 255, 255);" class="">
</div>
<div class=""><br class="">
</div>
<div class="">The problem is I don’t know how to interpret what
Hal said here,</div>
<div class="">I can’t construct the “real” example from the
“representative” example</div>
<div class="">given his advise.</div>
</blockquote>
<br>
Hopefully, the description I later provided helps. I can't share the
"real" code, but I reconstructed this example from my memory of the
original code plus some of the intermediate IR I'd looked at.<br>
<br>
<blockquote
cite="mid:56CF6936-E6DC-445C-AAEA-FB51E4FB89D5@sbcglobal.net"
type="cite">
<div class=""><br class="">
</div>
<div class="">If by “that code” he means the “if(cond)” code then
the only way I see that</div>
<div class="">the user can make it clear that “that code” is never
execute is if “cond” is</div>
<div class="">always false. But if “cond” is always false then the
if-statement is just plain</div>
<div class="">old dead code, has nothing to do with undefined
behavior.</div>
</blockquote>
<br>
Right, the condition is always false when the function, templated on
the small type, is called. However, while there is code that insures
that this true dynamically, it is not something the compiler can see
via constant propagation / inlining (i.e. it was in a different
translation unit, but frankly, it is not even clear to me than we'd
get this under LTO because of details not necessary for the
example).<br>
<br>
But, the user wanted the compiler to "know" that the condition had
to always be false (even though the compiler had no way to infer
that from data flow alone), and use that information to do dead-code
elimination. It is true that the user did not start out knowing
that, exactly, but we figured that out after seemingly unrelated
changes caused the optimizer to stop doing this as well as it had
before. The problem, in this context, is that we don't do this
robustly. The user noticed the performance change. With the new
(self-consistent) semantics for undef/poison, we'll be able to make
the compiler consistently get this right.<br>
<br>
<blockquote
cite="mid:56CF6936-E6DC-445C-AAEA-FB51E4FB89D5@sbcglobal.net"
type="cite">
<div class=""><br class="">
</div>
<div class="">So I am puzzled, </div>
<div class=""><br class="">
</div>
<div class="">That’s why I’m still asking for a more concrete
example showing how</div>
<div class="">We can optimize based on undefined behavior.</div>
<div class=""><br class="">
</div>
<div class=""><br class="">
</div>
<div class="">Peter Lawrence.</div>
<div class=""><br class="">
</div>
<div class=""><br class="">
</div>
<div class="">For reference here’s your second version with the
plain “else” rather than “else if"</div>
</blockquote>
<br>
Without looking at it in detail again, I think the problem with this
version is that we fold the single branch condition to undef, and
then just pick one side of the diamond. The choice is arbitrary, but
it would be better to just eliminate all of the code on both sides
of the branch (because the branch must be dead code). With the
proposed undef/poison semantics, we'll be able to do that.<br>
<br>
-Hal<br>
<br>
<blockquote
cite="mid:56CF6936-E6DC-445C-AAEA-FB51E4FB89D5@sbcglobal.net"
type="cite">
<div class=""><br class="">
</div>
<div class=""><br class="">
</div>
<div class="">
<div class="">void do_something_1(int);</div>
<div class="">void do_something_2();</div>
<div class=""><br class="">
</div>
<div class=""><br class="">
</div>
<div class="">template <typename T></div>
<div class="">int do_something(T mask, bool cond) {</div>
<div class=""> if (mask & 2)</div>
<div class=""> return 42;</div>
<div class=""><br class="">
</div>
<div class=""> if (cond) {</div>
<div class=""> T high_mask = mask >> 48;</div>
<div class=""> if (high_mask > 5)</div>
<div class=""> do_something_1(high_mask);</div>
<div class=""> else</div>
<div class=""> do_something_2();</div>
<div class=""> }</div>
<div class=""><br class="">
</div>
<div class=""> return 0;</div>
<div class="">}</div>
<div class=""><br class="">
</div>
<div class="">char foo();</div>
<div class="">bool alwaysfalse();</div>
<div class="">char f = do_something<char>(foo(),
alwaysfalse());</div>
</div>
<div class=""><br class="">
</div>
<div class=""><br class="">
</div>
<div class=""><br class="">
</div>
<div class=""><br class="">
</div>
<div class=""><br class="">
</div>
<div class=""><br class="">
<div>
<blockquote type="cite" class="">
<div class="">On Jun 29, 2017, at 2:49 PM, Mehdi AMINI <<a
moz-do-not-send="true" href="mailto:joker.eph@gmail.com"
class="">joker.eph@gmail.com</a>> wrote:</div>
<br class="Apple-interchange-newline">
<div class="">
<div dir="ltr" class=""><br class="">
<div class="gmail_extra"><br class="">
<div class="gmail_quote">2017-06-29 14:32 GMT-07:00
Peter Lawrence <span dir="ltr" class=""><<a
moz-do-not-send="true"
href="mailto:peterl95124@sbcglobal.net"
target="_blank" class="">peterl95124@sbcglobal.net</a>></span>:<br
class="">
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div style="word-wrap:break-word" class="">Mehdi,
<div class=""> I think the following
was the point of the conversation,</div>
<div class="">That both those examples are
illegal C programs.</div>
<div class="">They are both “undefined behavior”
because they both</div>
<div class="">use a shift amount that is too
large.</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
<div class="">Can you confirm that even if the shift
isn't executed the program exhibits undefined
behavior?</div>
<div class="">That wasn't my understanding, so I
don't believe this program exhibits UB.</div>
<div class=""><br class="">
</div>
<div class=""> </div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div style="word-wrap:break-word" class="">
<div class="">They both should have been
rejected by the compiler</div>
<div class="">even though they weren’t.</div>
<div class="">Hal agrees wth this assessment,</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
<div class="">I'm surprise by the confidence you're
exhibiting while speaking for others.</div>
<div class=""><br class="">
</div>
<div class="">-- </div>
<div class="">Mehdi</div>
<div class=""><br class="">
</div>
<div class=""> </div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div style="word-wrap:break-word" class="">
<div class="">That’s why we’re waiting for a
more complete example.</div>
<div class=""><br class="">
</div>
<div class="">My belief is that undefined
behavior is an optimization hazard,</div>
<div class="">Not an optimization opportunity.
Its just a belief, I could be proved</div>
<div class="">Wrong at any moment, but it feels
right to me.</div>
<div class=""><br class="">
</div>
<div class="">I would start looking for a more
complete example myself, but my</div>
<div class="">Belief is so strong that
"optimizing undefined behavior" seems </div>
<div class="">like a self-contradiction to me,
and I don’t know where to</div>
<div class="">Even start looking.</div>
<div class=""><br class="">
</div>
<div class="">I write compiler test programs in
my spare time as a hobby,</div>
<div class="">(which someday I’d like to
contribute to llvm)</div>
<div class="">So it’s not like I don’t have the
knowledge or the inclination,</div>
<div class="">I just don’t know how to approach
this problem.</div>
<div class=""><br class="">
</div>
<div class=""><br class="">
</div>
<div class="">You would think that since
“optimization of undefined behavior”</div>
<div class="">Has become such a bedrock concept
in llvm that by now some</div>
<div class="">Concrete examples would be readily
at hand,</div>
<div class="">But this doesn’t seem to be the
case.</div>
<div class=""><br class="">
</div>
<div class="">So I’m eagerly awaiting Hal’s (or
anyone else's) next email</div>
<div class="">That has a complete example.</div>
<span class="HOEnZb"><font class=""
color="#888888">
<div class=""><br class="">
</div>
<div class=""><br class="">
</div>
<div class="">Peter Lawrence.</div>
</font></span>
<div class="">
<div class="h5">
<div class=""><br class="">
</div>
<div class=""><br class="">
<div class="">
<blockquote type="cite" class="">
<div class="">
<div dir="ltr" class="">
<div class="gmail_extra">
<div class="gmail_quote">
<blockquote
class="gmail_quote"
style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div
style="word-wrap:break-word"
class="">
<div class="">
<div
class="m_-1990967588241278101gmail-h5">
<div class="">
<blockquote
type="cite"
class="">
<div class="">
<blockquote
type="cite"
style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255)"
class="">
<div class="">
<blockquote
type="cite"
class="">
<div class="">
<div
bgcolor="#FFFFFF"
class=""><br
class="">
I can't
comment on
SPEC, but this
does remind me
of code I was
working on
recently. To
abstract the
relevant
parts, it
looked
something like
this:<br
class="">
<br class="">
template
<typename
T><br
class="">
int
do_something(T
mask, bool
cond) {<br
class="">
<span
class="m_-1990967588241278101gmail-m_-3269729547621288564Apple-converted-space"> </span>if
(mask & 2)<br
class="">
<span
class="m_-1990967588241278101gmail-m_-3269729547621288564Apple-converted-space"> </span>return
1;<br class="">
<br class="">
<span
class="m_-1990967588241278101gmail-m_-3269729547621288564Apple-converted-space"> </span>if
(cond) {<br
class="">
<span
class="m_-1990967588241278101gmail-m_-3269729547621288564Apple-converted-space"> </span>T
high_mask =
mask >>
48;<br
class="">
<span
class="m_-1990967588241278101gmail-m_-3269729547621288564Apple-converted-space"> </span>if
(high_mask
> 5)<br
class="">
<span
class="m_-1990967588241278101gmail-m_-3269729547621288564Apple-converted-space"> </span>do_something_1(high_mask<wbr
class="">);<br
class="">
<span
class="m_-1990967588241278101gmail-m_-3269729547621288564Apple-converted-space"> </span>else
if (high_mask
> 3)<br
class="">
<span
class="m_-1990967588241278101gmail-m_-3269729547621288564Apple-converted-space"> </span>do_something_2();<br
class="">
<span
class="m_-1990967588241278101gmail-m_-3269729547621288564Apple-converted-space"> </span>}<br
class="">
<br class="">
<span
class="m_-1990967588241278101gmail-m_-3269729547621288564Apple-converted-space"> </span>return
0;<br class="">
}<br class="">
<br class="">
This function
ended up being
instantiated
on different
types T (e.g.
unsigned char,
unsigned int,
unsigned long,
etc.) and,
dynamically,
cond was
always false
when T was
char. The
question is:
Can the
compiler
eliminate all
of the code
predicated on
cond for the
smaller types?
In this case,
this code was
hot, and
moreover,
performance
depended on
the fact that,
for T =
unsigned char,
the function
was inlined
and the branch
on cond was
eliminated. In
the relevant
translation
unit, however,
the compiler
would never
see how cond
was set.<br
class="">
<br class="">
Luckily, we do
the right
thing here
currently. In
the case where
T = unsigned
char, we end
up folding
both of the
high_mask
tests as
though they
were false.
That entire
part of the
code is
eliminated,
the function
is inlined,
and everyone
is happy.<br
class="">
<br class="">
Why was I
looking at
this? As it
turns out, if
the 'else if'
in this
example is
just 'else',
we don't
actually
eliminate both
sides of the
branch. The
same is true
for many other
variants of
the
conditionals
(i.e. we don't
recognize all
of the code as
dead).</div>
</div>
</blockquote>
<div class="">
<div class=""><br
class="">
</div>
<div class=""><br
class="">
</div>
<div class="">I
apologize in
advance if I
have missed
something here
and am
misreading
your
example...</div>
<div class=""><br
class="">
</div>
</div>
<div class="">This
doesn’t make
sense to me, a
shift amount
of 48 is
“undefined”
for unsigned
char,</div>
<div class="">How
do we know
this isn’t a
source code
bug,</div>
<div class="">What
makes us think
the the user
intended the
result to be
“0”.</div>
</div>
</blockquote>
<br
style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255)"
class="">
<span
style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);float:none;display:inline"
class="">As I
said, this is
representation
of what the
real code did,
and looked
like, after
other inlining
had taken
place, etc. In
the original
form, the
user's intent
was clear.
That code is
never executed
when T is a
small integer
type.</span><br
style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255)"
class="">
</div>
</blockquote>
<br class="">
</div>
<div class=""><br
class="">
</div>
</div>
</div>
<div class="">I will still
have a hard time
believing this until I
see a real example, can
you fill in the details
?</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
<div class=""><br class="">
</div>
<div class="">Hal gave you a
real example, have you
tried? I feel like you're
asking more effort from
others than you are ready to
put in: it took me less than
5 minutes to reproduce what
Hal was describing using his
snippet:</div>
<div class=""><br class="">
</div>
<div class="">See the
difference between <a
moz-do-not-send="true"
href="https://godbolt.org/g/YYtsxB"
target="_blank" class="">https://godbolt.org/g/YYtsxB</a>
and <a
moz-do-not-send="true"
href="https://godbolt.org/g/dTBBDq"
target="_blank" class="">https://godbolt.org/g/<wbr
class="">dTBBDq</a></div>
<div class=""><br class="">
</div>
<div class="">-- </div>
<div class="">Mehdi</div>
<div class=""><br class="">
</div>
<div class=""><br class="">
</div>
<div class=""><br class="">
</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
<br class="">
</div>
</div>
</div>
</div>
</blockquote>
</div>
<br class="">
</div>
</div>
</div>
</blockquote>
</div>
<br class="">
</div>
</blockquote>
<br>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</body>
</html>