My (dumb?) question would be: why is llvm.assume being handled any differently than llvm.assert ?
Other than one trapping and one not-trapping, they should be identical, in both cases they are giving
The optimizers information, and that shouldn’t be any different from being inside an “if” statement with the same condition ?
–Peter Lawrence.
My (dumb?) question would be: why is llvm.assume being handled any
differently than llvm.assert ?
There is no llvm.assert intrinsic, so i'm not sure what you mean here. Care
to give an example?
Note:, the example would optimize if it was multiple blocks with an if.
The problem with assume is two fold:
Their is not proper control dependence infrastructure to know not to move them, we rely on marking them as memory touching instructions, which they are not. This causes all sorts of fun side-effects like adding assumes causing things to go from readnone to readonly or readwrite, not just during functionattrs, but during inlining, etc.
Their scope is implicit. Things have to track and figure out what they apply to.
In extended-ssa (which is basically assume, if the assumes produced a value that was used by things that make use of the information), all use-sites are post-dominated by the conditional.
IE extended-ssa is something like
%2 = icmp eq %foo, 3
%3 = llvm.assume(%foo eq 3)
<use of %3 instead of %foo>
So for conditionals, it will produce two assumes, one in each branch, and all things in that branch using %foo would instead use the result of the assume for that side of the branch.
Daniel,
Well then my next (dumb?) question is why aren’t we using source level assert information
For optimization ?
–Peter Lawrence.
We do, implicitly, because assert generates if conditions. Or at least, gvn knows how to propagate that implicit info. We can do better by exposing it more, most likely
From: "Daniel Berlin via llvm-dev" <llvm-dev@lists.llvm.org>
To: "Peter Lawrence" <c_plawre@qca.qualcomm.com>
Cc: llvm-dev@lists.llvm.org
Sent: Friday, June 10, 2016 8:32:06 PM
Subject: Re: [llvm-dev] Early CSE clobbering llvm.assume
We do, implicitly, because assert generates if conditions. Or at
least, gvn knows how to propagate that implicit info. We can do
better by exposing it more, most likely
Are you asking why we don't assume the asserted condition when NDEBUG is defined?
-Hal
Daniel,
My point is this,
If (cond) ---- optimizer takes advantage of knowing cond == true within the “then” part
Assert(cond) ---- optimizer takes advantage of knowing cond == true for the rest of the scope
Assume(cond) ---- optimizer takes advantage of knowing cond == true for the rest of the scope
If we aren’t implementing these in a consistent manner (like using an intrinsic for one but not the others)
Then we aren’t doing a good job of engineering,
IE we should be able to get “assume” to work for free if we are doing it right.
Asking “how do I get this intrinsic to work” is perhaps the wrong question,
Perhaps the right question is, how do we represent assume so that we get it for free.
—Peter Lawrence.
Daniel,
Allow me to elaborate some more…
You seem to be trying to get “Constant-propagation” out of an “assume”,
But a good compiler does so much more
if(A > B), assert(A > B), assume(A > B), should all result in same optimizations
if(A>B && A<C), assert(A>B && A<C), assume(A>B & A<C), should all result in same optimizations
if(A & 0x1), assert(A & 0x1), assume(A & 0x1), should all result in same optimizations
if(A & (A-1)), assert(A & (A-1)), assume(A & (A-1)), should all result in same optimizations
OK, maybe the last one, or two, are a stretch, maybe we only want to generalize to
Value-propagation, and Range-propagation, and not arbitrary Property-propagation,
But this should be the goal,
The question is, is an “intrinsic” the right way to go about it.
–Peter Lawrence.
So,
Daniel,
Allow me to elaborate some more…
You seem to be trying to get “Constant-propagation” out of an “assume”,
Actually, no. That is mostly what llvm tries to get, not me. It does get some range info, but not a lot.
I think it’s pretty much designed wrong, and in need of revision to get good info out of. Not that I think it was a bad idea to start with something, but I think we need to revise it.
But a good compiler does so much more
Fwiw, gvn already gets all these, but it is very complicated.
Hi,
Daniel,
My point is this,If (cond) ---- optimizer takes advantage of knowing cond == true within the “then” part
Assert(cond) ---- optimizer takes advantage of knowing cond == true for the rest of the scope
Assume(cond) ---- optimizer takes advantage of knowing cond == true for the rest of the scopeIf we aren’t implementing these in a consistent manner (like using an intrinsic for one but not the others)
Then we aren’t doing a good job of engineering,
It is not clear cut for me.
First the Assert(cond) is not an llvm construct AFAIK. At the source level it is usually a macro that turns into `if (!Cond) abort()` and thus can be reduced to your first case.
(Also I believe it disappears in optimized build and the optimizer/LLVM will never see the test).
And second, it seems to me that there is a fundamental difference between the first and last case: in the first case the optimizer deduces some properties from the control flow (i.e. cond==true within the "then" part), while in the assume case it is an information that the optimizer can't deduce itself, and that is *not related to the control flow* but is present thanks to a hint from the programmer (or the front-end).
It is not clear that these two sources of information can be reconcile easily with a common representation.
IE we should be able to get “assume” to work for free if we are doing it right.
I'm not sure what you mean by "work for free"?
Hi,
Daniel,
My point is this,If (cond) ---- optimizer takes advantage of knowing cond == true within
the “then” part
Assert(cond) ---- optimizer takes advantage of knowing cond == true for
the rest of the scope
Assume(cond) ---- optimizer takes advantage of knowing cond == true for
the rest of the scopeIf we aren’t implementing these in a consistent manner (like using an
intrinsic for one but not the others)
Then we aren’t doing a good job of engineering,It is not clear cut for me.
First the Assert(cond) is not an llvm construct AFAIK. At the source level
it is usually a macro that turns into `if (!Cond) abort()` and thus can be
reduced to your first case.
(Also I believe it disappears in optimized build and the optimizer/LLVM
will never see the test).And second, it seems to me that there is a fundamental difference between
the first and last case: in the first case the optimizer deduces some
properties from the control flow (i.e. cond==true within the "then" part),
while in the assume case it is an information that the optimizer can't
deduce itself, and that is *not related to the control flow* but is present
thanks to a hint from the programmer (or the front-end).It is not clear that these two sources of information can be reconcile
easily with a common representation.
Perhaps a naive question then is: why don't we represent assume as `if
(!cond) unreachable; else <the rest of the code>`?
-- Sean Silva
As I understand it, in theory this is fine, but in practice it may end
up breaking optimizations. For instance, today we can hoist loads
across calls to assume, but it may not be obviously safe if you have
the branch-to-unreachable representation. The control flow
representation may also bloat compile time / memory usage due to more
basic blocks.
-- Sanjoy
What he said 
It also, representationally, has a related issue our current assume does in terms of figuring out the set of assumptions applied. Given an instruction, in extended SSA, because " assume" produces a value used by things, it’s trivial to find the chain of assumptions you can use for it. In a straight control flow representation, it requires finding which side of the branch you are on all the way up the control dependence tree
Daniel,
What am I missing in the following chain of logic:
As far as constant-prop, value-prop, range-prop, and general property-propagation,
the compiler/optimizer has to get it right for if-then-else and while-do or else we should all start over J
“assert” takes advantage of this by being translated into if-then logic early on in the compilation
“assume” should also take advantage of this the same way. (generate a call to “pseudoabort” which
At some late stage gets deleted)
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”.
And any argument you can make about needing to handle “assume” conditions in some special way can be
Turned around and applied to “if-then” conditions, but again no one is arguing that we need to re-design “if-then”
Information propagation.
Thanks,
–Peter.
Daniel,
What am I missing in the following chain of logic:
As far as constant-prop, value-prop, range-prop, and general
property-propagation,1. the compiler/optimizer **has** to get it right for if-then-else and
while-do or else we should all start over J
Only certain parts of the compiler know how to do this.
This is precisely one of the reasons i'm proposing we've gotten it wrong.
2. “assert” takes advantage of this by being translated into if-then logic
early on in the compilation3. “assume” should also take advantage of this the same way. (generate a
call to “pseudoabort” whichAt some late stage gets deleted)
This would fix precisely nothing, because of the above.
Sanjoy’s argument is faulty, if it were true we would also find our
handling of “assert” to be unacceptablebut this is not the case, no one is arguing that we need to re-design
“assert”.
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.
I would also argue our current way of propagating information for if-then
conditions is in fact, quite crappy. Only a small number of passes know how
to do it, and they do it either by ad-hoc analysis (GVN) or very expensive
methods (LVI).
And any argument you can make about needing to handle “assume” conditions
in some special way can beTurned around and applied to “if-then” conditions, but again no one is
arguing that we need to re-design “if-then”Information propagation.
I would argue we do, in fact need to do that.
That said, it is a larger longer term change.
Fixing assume is a good start on that, and by fixing assume, we can prove
out whether a new model will work well and expand it.
If we start by trying to fix the general propagation problem, that's a huge
job to start, and if we get it wrong, a lot larger to fix.
Better to start small and go from there.
From: "Daniel Berlin via llvm-dev" <llvm-dev@lists.llvm.org>
To: "Peter Lawrence" <c_plawre@qca.qualcomm.com>
Cc: llvm-dev@lists.llvm.org
Sent: Tuesday, June 14, 2016 12:45:50 PM
Subject: Re: [llvm-dev] Early CSE clobbering llvm.assume
> Daniel,
> What am I missing in the following chain of logic:
> As far as constant-prop, value-prop, range-prop, and general
> property-propagation,> 1. the compiler/optimizer * has * to get it right for if-then-else
> and while-do or else we should all start over JOnly certain parts of the compiler know how to do this.
This is precisely one of the reasons i'm proposing we've gotten it
wrong.
> 2. “assert” takes advantage of this by being translated into
> if-then
> logic early on in the compilation> 3. “assume” should also take advantage of this the same way.
> (generate a call to “pseudoabort” which> At some late stage gets deleted)
This would fix precisely nothing, because of the above.
> 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". For clarify, I'll note that:
1. assert is defined to be a macro that does not result in semantically-analyzable code when NDEBUG is defined. We cannot elide this, it how the feature is defined. The body of the assert might not even be parsable code when NDEBUG is defined. It might, for example, refer to variables that are only declared when NDEBUG is not defined.
2. Even saying that we'd get around this by ignoring parsing errors within the assert when NDEBUG is defined, but otherwise assuming the result is not desirable. There are large bodies of code which do this;
assert(i > 5);
if (i <= 5) throw a_strange_error();
so that, in production builds, the program does not crash, but instead unwinds. There are all sorts of reasons we can use to argue this is a bad coding practice, and I personally agree, but that does not change the fact that braking this idiom is not something we should do.
The contracts features being discussed for future versions of the C++ standard should be better in this regard.
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.
-Hal
Sanjoy’s argument is faulty, if it were true we would also find our
handling of “assert” to be unacceptablebut 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,
To simplify this discussion, lets first just focus on code without asserts and assumes,
I don’t follow your logic, you seem to be implying we don’t optimize property-propagation through “if-then” and “while-do” well ?
–Peter.
I don’t follow your logic, you seem to be implying we don’t optimize
property-propagation through “if-then” and “while-do” well ?
As far as property propagation is concerned, control flow is just as
good as assumes in theory (and I doubt you'll find realistic cases
where we do better with assumes than we do with control flow); but
replacing all assumes with control flow is not a good idea for other
reasons.
E.g we can LICM the load in f_0 (not today, we've regressed after some
recent changes that I'll fix right now) but not f_1 since it isn't
obvious that the load from %ptr can be speculated above the control
flow. In this case hoisting the load is easy (since all %leave does
is "unreachable" and thus "can never happen"), but e.g. you could have
sunk a call instruction (which could internally calls exit(0)) down
that path and then it would not be so obvious to see "%leave" as a
"can never happen" branch.
declare void @llvm.assume(i1)
define void @f_0(i1 %cond, i32* %ptr) {
entry:
br label %loop
loop:
%x = phi i32 [ 0, %entry ], [ %x.inc, %loop ]
call void @llvm.assume(i1 %cond)
%val = load i32, i32* %ptr
%x.inc = add i32 %x, %val
br label %loop
}
define void @f_1(i1 %cond, i32* %ptr) {
entry:
br label %loop
loop:
%x = phi i32 [ 0, %entry ], [ %x.inc, %stay ]
br i1 %cond, label %stay, label %leave
stay:
call void @llvm.assume(i1 %cond)
%val = load i32, i32* %ptr
%x.inc = add i32 %x, %val
br label %loop
leave:
unreachable
}
You're right that in both the cases all (edge/call) dominated uses of
%cond can be folded to true, but changing all assumes to be control
flow can still be a net regression by breaking optimizations like
above.
Note: using pseudo abort does not save you either, since you could
start with:
for (;
{
// lowered assume
some_call();
if (!cond) {
pseudo_abort();
unreachable;
}
int x = obj->field;
}
==> sink call down both paths
for (; {
// lowered assume
if (!cond) {
some_call();
pseudo_abort();
unreachable;
}
some_call();
int x = obj->field;
}
and now the "failing" branch of the assume no longer just a
pseudo-abort (so the branch is necessary now). And consider what
happens if the body of "some_call()" is basically:
void some_call() {
while (receive_request())
service_request();
unreachable;
}
after inlining some_call(), the pseudo_abort() will just disappear
too!
What an intrinsic assume gives us today is by "internalizing" the
control flow it ensures that
for (; {
// lowered assume
some_call();
if (!cond) {
pseudo_abort();
unreachable;
}
int x = obj->field;
}
can only be optimized to
for (; {
// lowered assume
if (!cond) {
pseudo_abort();
unreachable;
}
some_call();
int x = obj->field;
}
avoiding the problem above.
-- Sanjoy
Hal,
To simplify this discussion, lets first just focus on code without asserts and assumes,
I don’t follow your logic, you seem to be implying we don’t optimize property-propagation through “if-then” and “while-do” well ?
–Peter.