llvm dev - Jun 2016 - Early CSE clobbering llvm.assume

>
>
>> Sanjoy’s argument is faulty, if it were true we would also find our
>> handling of “assert” to be unacceptable
>>
>> but this is not the case, no one is arguing that we need to re-design
>> “assert”
>>
> Sure, but no one should make this argument anyway: assert is not for
> optimization. In fact, we don't really want it to be used for
optimization,
> because if we do, then we might end up in a situation where the -DNDEBUG
> build generates worse code than the build with asserts enabled.
>
:)

>
> Also, I'll note that the reason that assume is an intrinsic, instead of
a
> branch around unreachable, is that we aggressively remove branches around
> unreachable as part of our canonicalization process. We do this in order to
> simplify code, and this is important in order to remove abstraction
> penalties. Note that unreachables are also generated from undefined
> behavior, and one of the ways we use undefined behavior is to assume it is
> unreachable, enabling us to eliminate what should be dead code. This is an
> important technique for limiting abstraction penalties from, for example,
> heavily templated C++ code.
>
> Thus, somewhat unfortunately, Sanjoy's argument is not faulty.
>
>
>
> Asserts occur much more often than assumes, it may or may not be sensible
> to handle them the same way.
> I would argue it is sensible, but it's also reasonable to argue it is
not.
>
> We need to be careful what we mean by "in the same way".
>
Yes, i simply meant "extract information from the control flow structure
and comparisons they generate when they are enabled".

You are correct with all of your observations :)
>
> We can certainly improve the representations of assumes, perhaps as Danny
> has suggested by converting their control dependencies into extended SSA
> token vales, and better capture knowledge from conditional branches, but
> the tradeoffs here are not trivial.
>
>
100% agreed, this is something that requires some exploration and messing
around, and then a design document going through the tradeoffs of various
approaches with real data.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160614/0d472154/attachment.html>

Daniel,
              This first part is to whoever you are quoting, I can’t tell from
the email,

The more information made available to the optimizers the better the
optimizations,
Asserts provide more information,
You *should* expect better code with asserts enabled.

And this is *not* a bad thing !!!

And IMHO there is no winning argument that says we should not use this
information.

In other words saying “asserts aren’t for optimization” isn’t a winning
argument,
Its information and it isn’t useful to throw that information away.
It’s not very far removed from saying “if, while, and for conditions” aren’t for
optimization.



This second part is for your response,

Hmmm, I don’t get how you go from “assert having a call to abort()” to a bunch
of talk
About “branch around unreachable” ?  the condition isn’t unreachable, the abort
isn’t
Unreachable, what’s unreachable ???


--Peter.




From: Daniel Berlin [mailto:dberlin at dberlin.org]
Sent: Tuesday, June 14, 2016 11:23 AM
To: Hal Finkel <hfinkel at anl.gov>
Cc: Lawrence, Peter <c_plawre at qca.qualcomm.com>; llvm-dev <llvm-dev
at lists.llvm.org>
Subject: Re: [llvm-dev] Early CSE clobbering llvm.assume


Sanjoy’s argument is faulty, if it were true we would also find our handling of
“assert” to be unacceptable
but this is not the case, no one is arguing that we need to re-design “assert”
Sure, but no one should make this argument anyway: assert is not for
optimization. In fact, we don't really want it to be used for optimization,
because if we do, then we might end up in a situation where the -DNDEBUG build
generates worse code than the build with asserts enabled.
:)


Also, I'll note that the reason that assume is an intrinsic, instead of a
branch around unreachable, is that we aggressively remove branches around
unreachable as part of our canonicalization process. We do this in order to
simplify code, and this is important in order to remove abstraction penalties.
Note that unreachables are also generated from undefined behavior, and one of
the ways we use undefined behavior is to assume it is unreachable, enabling us
to eliminate what should be dead code. This is an important technique for
limiting abstraction penalties from, for example, heavily templated C++ code.

Thus, somewhat unfortunately, Sanjoy's argument is not faulty.


Asserts occur much more often than assumes, it may or may not be sensible to
handle them the same way.
I would argue it is sensible, but it's also reasonable to argue it is not.
We need to be careful what we mean by "in the same way".

Yes, i simply meant "extract information from the control flow structure
and comparisons they generate when they are enabled".

You are correct with all of your observations :)

We can certainly improve the representations of assumes, perhaps as Danny has
suggested by converting their control dependencies into extended SSA token
vales, and better capture knowledge from conditional branches, but the tradeoffs
here are not trivial.

100% agreed, this is something that requires some exploration and messing
around, and then a design document going through the tradeoffs of various
approaches with real data.


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160615/874c0c89/attachment.html>

----- Original Message -----
> From: "Peter Lawrence" <c_plawre at qca.qualcomm.com>
> To: "Daniel Berlin" <dberlin at dberlin.org>, "Hal
Finkel"
> <hfinkel at anl.gov>
> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>
> Sent: Tuesday, June 14, 2016 9:04:16 PM
> Subject: RE: [llvm-dev] Early CSE clobbering llvm.assume
> Daniel,
> This first part is to whoever you are quoting, I can’t tell from the
> email,
> The more information made available to the optimizers the better the
> optimizations,
> Asserts provide more information,
> You * should * expect better code with asserts enabled.
> And this is * not * a bad thing !!!
> And IMHO there is no winning argument that says we should not use
> this information.
> In other words saying “asserts aren’t for optimization” isn’t a
> winning argument,
> Its information and it isn’t useful to throw that information away.
Unfortunately, it is not that simple. When asserts are enabled, the conditions
they encapsulate need to be checked at runtime. This checking has a cost
(especially if the asserted condition is not cheap to compute), and also
introduces extra control flow which can inhibit optimization. It might also
provide additional information which can help optimization, but generally
speaking, in part because of usage conventions (e.g. using expensive-to-compute
expressions in the assert), enabling asserts does not generally help
performance.
> It’s not very far removed from saying “if, while, and for conditions”
> aren’t for optimization.
It is quite far removed. 

Unfortunately, asserts are a feature designed to help debugging, and not
optimization. This is why defining NDEBUG turns them off. We would like a
feature, similar in spirit, that is intended to help optimization. This is what
assume is for. The contracts feature being discussed for C++ also has specific
allowances for usage for optimization.
> This second part is for your response,
> Hmmm, I don’t get how you go from “assert having a call to abort()”
> to a bunch of talk
> About “branch around unreachable” ? the condition isn’t unreachable,
> the abort isn’t
> Unreachable, what’s unreachable ???
I think we're confusing several branches of the conversation here. There
actually is an unreachable after the abort because the abort does not return. We
were talking, however, about using an alternate representation for assumes which
used control flow and unreachable. In this case, there would be no abort, just
the unreachable.

-Hal 
> --Peter.
> From: Daniel Berlin [mailto:dberlin at dberlin.org]
> Sent: Tuesday, June 14, 2016 11:23 AM
> To: Hal Finkel <hfinkel at anl.gov>
> Cc: Lawrence, Peter <c_plawre at qca.qualcomm.com>; llvm-dev
> <llvm-dev at lists.llvm.org>
> Subject: Re: [llvm-dev] Early CSE clobbering llvm.assume
> > > > Sanjoy’s argument is faulty, if it were true we would also
find
> > > > our
> > > > handling of “assert” to be unacceptable
> > > 
> > 
> 
> > > > but this is not the case, no one is arguing that we need to
> > > > re-design
> > > > “assert”
> > > 
> > 
> 
> > Sure, but no one should make this argument anyway: assert is not
> > for
> > optimization. In fact, we don't really want it to be used for
> > optimization, because if we do, then we might end up in a situation
> > where the -DNDEBUG build generates worse code than the build with
> > asserts enabled.
> 
> :)
> Also, I'll note that the reason that assume is an intrinsic, instead
> of a branch around unreachable, is that we aggressively remove
> branches around unreachable as part of our canonicalization process.
> We do this in order to simplify code, and this is important in order
> to remove abstraction penalties. Note that unreachables are also
> generated from undefined behavior, and one of the ways we use
> undefined behavior is to assume it is unreachable, enabling us to
> eliminate what should be dead code. This is an important technique
> for limiting abstraction penalties from, for example, heavily
> templated C++ code.
> Thus, somewhat unfortunately, Sanjoy's argument is not faulty.
> Asserts occur much more often than assumes, it may or may not be
> sensible to handle them the same way.
> I would argue it is sensible, but it's also reasonable to argue it is
> not.
> We need to be careful what we mean by "in the same way".
> Yes, i simply meant "extract information from the control flow
> structure and comparisons they generate when they are enabled".
> You are correct with all of your observations :)
> We can certainly improve the representations of assumes, perhaps as
> Danny has suggested by converting their control dependencies into
> extended SSA token vales, and better capture knowledge from
> conditional branches, but the tradeoffs here are not trivial.
> 100% agreed, this is something that requires some exploration and
> messing around, and then a design document going through the
> tradeoffs of various approaches with real data.
-- 

Hal Finkel 
Assistant Computational Scientist 
Leadership Computing Facility 
Argonne National Laboratory 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160614/29839e41/attachment.html>

On Tue, Jun 14, 2016 at 7:04 PM, Lawrence, Peter via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> The more information made available to the optimizers the better the
> optimizations,
>
> Asserts provide more information,
>
> You *should* expect better code with asserts enabled.
>
> And this is *not* a bad thing !!!
>
> And IMHO there is no winning argument that says we should not use this
> information.
>
> In other words saying “asserts aren’t for optimization” isn’t a winning
> argument,
>
> Its information and it isn’t useful to throw that information away.
I think what you're missing (and something I've tried to highlight
above) is that control flow does not just add information, but it also
takes away information (so adding control flow is not an obvious net
win, and there is a trade-off).

E.g. the compiler can prove

%t0 = load i32, i32* %ptr0
%t1 = load i32, i32* %ptr1

is equivalent to

%t1 = load i32, i32* %ptr1
%t0 = load i32, i32* %ptr0

but it cannot prove

%t0 = load i32, i32* %ptr0
if (!PREDICATE(%t0)) { fail_assert("msg0"); unreachable; }
%t1 = load i32, i32* %ptr1
if (!PREDICATE(%t1)) { fail_assert("msg1"); unreachable; }

is the same as

%t1 = load i32, i32* %ptr1
if (!PREDICATE(%t1)) { fail_assert("msg1"); unreachable; }
%t0 = load i32, i32* %ptr0
if (!PREDICATE(%t0)) { fail_assert("msg0"); unreachable; }

because it isn't.

In particular, without the control flow it is trivial to show that
%ptr1 can be safely dereferenced at before the load from %ptr1, since
the program would have undefined behavior otherwise.  But with the
control flow you no longer know that, since the dereferenceability of
%t1 could be control dependent on PREDICATE(%t0) being true.

You could pattern match a specific call instruction "fail_assert" that
is known to be the "failing branch" of an assert; but that is not a
general solution, since code sinking will break that.

You also have compile time implications of having more basic blocks,
but that's secondary.

-- Sanjoy

I suspect this thread has become deep enough that it is becoming somewhat
unproductive and if we really want to carry it on, it may be more useful to
do so at a social or something.

I suspect this mainly because you can't tell who i'm quoting, and folks
are
replying to things other people have not quite said, due to the quoting :)

There seem to be other confusions, such as use of common llvm terminology
that is not always common in other parts of the world of compilers
(unreachable, undef, etc).

On Tue, Jun 14, 2016 at 7:04 PM, Lawrence, Peter <c_plawre at
qca.qualcomm.com>
wrote:
> Daniel,
>
>               This first part is to whoever you are quoting, I can’t tell
> from the email,
>
>
>
> The more information made available to the optimizers the better the
> optimizations,
>
> Asserts provide more information,
>
> You **should** expect better code with asserts enabled.
>
>
>
> And this is **not** a bad thing !!!
>
>
>
> And IMHO there is no winning argument that says we should not use this
> information.
>
>
>
> In other words saying “asserts aren’t for optimization” isn’t a winning
> argument,
>
> Its information and it isn’t useful to throw that information away.
>
> It’s not very far removed from saying “if, while, and for conditions”
> aren’t for optimization.
>
>
>
>
>
>
>
> This second part is for your response,
>
>
>
> Hmmm, I don’t get how you go from “assert having a call to abort()” to a
> bunch of talk
>
> About “branch around unreachable” ?  the condition isn’t unreachable, the
> abort isn’t
>
> Unreachable, what’s unreachable ???
>
>
>
>
>
> --Peter.
>
>
>
>
>
>
>
>
>
> *From:* Daniel Berlin [mailto:dberlin at dberlin.org]
> *Sent:* Tuesday, June 14, 2016 11:23 AM
> *To:* Hal Finkel <hfinkel at anl.gov>
> *Cc:* Lawrence, Peter <c_plawre at qca.qualcomm.com>; llvm-dev <
> llvm-dev at lists.llvm.org>
> *Subject:* Re: [llvm-dev] Early CSE clobbering llvm.assume
>
>
>
>
>
> Sanjoy’s argument is faulty, if it were true we would also find our
> handling of “assert” to be unacceptable
>
> but this is not the case, no one is arguing that we need to re-design
> “assert”
>
> Sure, but no one should make this argument anyway: assert is not for
> optimization. In fact, we don't really want it to be used for
optimization,
> because if we do, then we might end up in a situation where the -DNDEBUG
> build generates worse code than the build with asserts enabled.
>
> :)
>
>
>
>
> Also, I'll note that the reason that assume is an intrinsic, instead of
a
> branch around unreachable, is that we aggressively remove branches around
> unreachable as part of our canonicalization process. We do this in order to
> simplify code, and this is important in order to remove abstraction
> penalties. Note that unreachables are also generated from undefined
> behavior, and one of the ways we use undefined behavior is to assume it is
> unreachable, enabling us to eliminate what should be dead code. This is an
> important technique for limiting abstraction penalties from, for example,
> heavily templated C++ code.
>
> Thus, somewhat unfortunately, Sanjoy's argument is not faulty.
>
>
>
>
>
> Asserts occur much more often than assumes, it may or may not be sensible
> to handle them the same way.
>
> I would argue it is sensible, but it's also reasonable to argue it is
not.
>
> We need to be careful what we mean by "in the same way".
>
>
>
> Yes, i simply meant "extract information from the control flow
structure
> and comparisons they generate when they are enabled".
>
>
>
> You are correct with all of your observations :)
>
>
> We can certainly improve the representations of assumes, perhaps as Danny
> has suggested by converting their control dependencies into extended SSA
> token vales, and better capture knowledge from conditional branches, but
> the tradeoffs here are not trivial.
>
>
>
> 100% agreed, this is something that requires some exploration and messing
> around, and then a design document going through the tradeoffs of various
> approaches with real data.
>
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160614/d73fadaa/attachment.html>