Lawrence, Peter via llvm-dev
2016-Jun-14 18:48 UTC
[llvm-dev] Early CSE clobbering llvm.assume
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. From: Hal Finkel [mailto:hfinkel at anl.gov] Sent: Tuesday, June 14, 2016 11:12 AM To: Lawrence, Peter <c_plawre at qca.qualcomm.com> Cc: llvm-dev at lists.llvm.org; Daniel Berlin <dberlin at dberlin.org> Subject: Re: [llvm-dev] Early CSE clobbering llvm.assume ________________________________ From: "Daniel Berlin via llvm-dev" <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> To: "Peter Lawrence" <c_plawre at qca.qualcomm.com<mailto:c_plawre at qca.qualcomm.com>> Cc: llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org> Sent: Tuesday, June 14, 2016 12:45:50 PM Subject: Re: [llvm-dev] Early CSE clobbering llvm.assume On Tue, Jun 14, 2016 at 10:36 AM, Lawrence, Peter <c_plawre at qca.qualcomm.com<mailto:c_plawre at qca.qualcomm.com>> wrote: 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 ☺ 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 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 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 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. 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. _______________________________________________ LLVM Developers mailing list llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev -- 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/05ce6647/attachment.html>
> 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
----- Original Message -----> From: "Peter Lawrence" <c_plawre at qca.qualcomm.com> > To: "Hal Finkel" <hfinkel at anl.gov> > Cc: llvm-dev at lists.llvm.org, "Daniel Berlin" <dberlin at dberlin.org> > Sent: Tuesday, June 14, 2016 1:48:44 PM > Subject: RE: [llvm-dev] Early CSE clobbering llvm.assume> 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.No, what I'm saying is that we optimize away this pattern: if (cond) { unreachable } else { ... } by dropping the information about the unreachable's control dependencies. This does mean that we drop information that cond is false in the '...'. I'm not sure this says anything, in general, about our ability to optimize. -Hal> From: Hal Finkel [mailto:hfinkel at anl.gov] > Sent: Tuesday, June 14, 2016 11:12 AM > To: Lawrence, Peter <c_plawre at qca.qualcomm.com> > Cc: llvm-dev at lists.llvm.org; Daniel Berlin <dberlin at dberlin.org> > Subject: Re: [llvm-dev] Early CSE clobbering llvm.assume> ----- Original Message -----> > From: "Daniel Berlin via llvm-dev" < llvm-dev at lists.llvm.org > > > > To: "Peter Lawrence" < c_plawre at qca.qualcomm.com > > > > Cc: llvm-dev at lists.llvm.org > > > Sent: Tuesday, June 14, 2016 12:45:50 PM > > > Subject: Re: [llvm-dev] Early CSE clobbering llvm.assume >> > On Tue, Jun 14, 2016 at 10:36 AM, Lawrence, Peter < > > c_plawre at qca.qualcomm.com > wrote: > > > > 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 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 > > 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 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. > > > > > 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. >> > _______________________________________________ > > > LLVM Developers mailing list > > > llvm-dev at lists.llvm.org > > > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > > --> Hal Finkel > Assistant Computational Scientist > Leadership Computing Facility > Argonne National Laboratory-- 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/7a90b64b/attachment.html>
On Tue, Jun 14, 2016 at 12:51 PM, Hal Finkel via llvm-dev <llvm-dev at lists.llvm.org> wrote:> No, what I'm saying is that we optimize away this pattern: > > if (cond) { > unreachable > } else { > ... > } > > by dropping the information about the unreachable's control dependencies. > This does mean that we drop information that cond is false in the '...'. I'm > not sure this says anything, in general, about our ability to optimize.I think Peter's suggestion was to do: if (cond) { pseudo_abort(); unreachable; } else { } instead which would avoid the information loss due to simplifycfg. However, I think that too is not obviously a good idea, since it introduces non-trivial control dependence that - may break safety checks - may make the optimizer transform the program in ways such that we'd have to actually materialize "cond" (e.g sinking a side effect to both sides of the branch) with an assume-like representation, none of the above happens. -- Sanjoy> > -Hal > > > > > > From: Hal Finkel [mailto:hfinkel at anl.gov] > Sent: Tuesday, June 14, 2016 11:12 AM > To: Lawrence, Peter <c_plawre at qca.qualcomm.com> > Cc: llvm-dev at lists.llvm.org; Daniel Berlin <dberlin at dberlin.org> > Subject: Re: [llvm-dev] Early CSE clobbering llvm.assume > > > > > > ________________________________ > > From: "Daniel Berlin via llvm-dev" <llvm-dev at lists.llvm.org> > To: "Peter Lawrence" <c_plawre at qca.qualcomm.com> > Cc: llvm-dev at lists.llvm.org > Sent: Tuesday, June 14, 2016 12:45:50 PM > Subject: Re: [llvm-dev] Early CSE clobbering llvm.assume > > > > > > On Tue, Jun 14, 2016 at 10:36 AM, Lawrence, Peter > <c_plawre at qca.qualcomm.com> wrote: > > 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 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 > > 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 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. > > 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. > > > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > > > > > -- > > Hal Finkel > Assistant Computational Scientist > Leadership Computing Facility > Argonne National Laboratory > > > > > -- > Hal Finkel > Assistant Computational Scientist > Leadership Computing Facility > Argonne National Laboratory > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >-- Sanjoy Das http://playingwithpointers.com
On Tue, Jun 14, 2016 at 12:49 PM, Sanjoy Das <sanjoy at playingwithpointers.com> wrote:> 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'tFixed in http://reviews.llvm.org/rL272703