Does 'nounwind' have semantics that inform optimization passes? It seems
to in some cases, but not consistently. For example...
int32_t foo(int32_t* ptr) {
int i = 0;
int result;
do {
bar(ptr);
result = *ptr;
bar(ptr);
} while (i++ < *ptr);
return result;
}
Say we have a front end that declares bar as...
declare void @bar(i32*) readonly;
So 'bar' is 'readonly' and 'may-unwind'.
When LICM tries to hoist the load it interprets the 'may-unwind' as
"MayThrow" in LICM-language and bails. However, when it tries to sink
the call itself it sees the 'readonly', assumes no side effects and
sinks it below the loads. Hmm...
There doesn't appear to be a way to declare a function that is guaranteed
not to write to memory in a way that affects the caller, but may have another
well-defined side effect like aborting the program. This is interesting, because
that is the way runtime checks for safe languages would like to be defined.
I'm perfectly happy telling front ends to generate control flow for
well-defined traps, since I like lots of basic blocks in my IR. But I'm
still curious how others deal with this.
-Andy
On Sun, Jul 21, 2013 at 5:56 PM, Andrew Trick <atrick at apple.com> wrote:> Does 'nounwind' have semantics that inform optimization passes? It seems to in some cases, but not consistently. For example... > > int32_t foo(int32_t* ptr) { > int i = 0; > int result; > do { > bar(ptr); > result = *ptr; > bar(ptr); > } while (i++ < *ptr); > return result; > } > > Say we have a front end that declares bar as... > > declare void @bar(i32*) readonly; > > So 'bar' is 'readonly' and 'may-unwind'.It's impossible to write a readonly function which throws a DWARF exception. Given that, I would imagine there are all sorts of bugs nobody has ever run into. -Eli
Andrew Trick wrote:> Does 'nounwind' have semantics that inform optimization passes? It seems to in some cases, but not consistently. For example... > > int32_t foo(int32_t* ptr) { > int i = 0; > int result; > do { > bar(ptr); > result = *ptr; > bar(ptr); > } while (i++< *ptr); > return result; > } > > Say we have a front end that declares bar as... > > declare void @bar(i32*) readonly; > > So 'bar' is 'readonly' and 'may-unwind'. > > When LICM tries to hoist the load it interprets the 'may-unwind' as "MayThrow" in LICM-language and bails. However, when it tries to sink the call itself it sees the 'readonly', assumes no side effects and sinks it below the loads. Hmm... > > There doesn't appear to be a way to declare a function that is guaranteed not to write to memory in a way that affects the caller, but may have another well-defined side effect like aborting the program. This is interesting, because that is the way runtime checks for safe languages would like to be defined. I'm perfectly happy telling front ends to generate control flow for well-defined traps, since I like lots of basic blocks in my IR. But I'm still curious how others deal with this.Yes, we went through a phase where people would try to use "nounwind+readonly == no side-effects" to optimize. All such optimizations are wrong. Unless otherwise proven, a function may inf-loop, terminate the program, or longjmp. I tried to add 'halting' to help solve part of this a long time ago, but it never went in. The problem is that determining whether you have loops requires a FunctionPass (LoopInfo to find loops and SCEV to determine an upper bound) and applying function attributes is an SCC operation (indeed, an SCC is itself a loop), so it's all blocked behind fixing the PassManager to allow CGSGGPasses to depend on FunctionPasses. http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20100705/103670.html I'm now in a similar situation where I want 'nounwind' to mean "only exits by terminating the program or a return instruction" but unfortunately functions which longjmp are considered nounwind. I would like to change llvm to make longjmp'ing a form of unwinding (an exceptional exit to the function), but if I were to apply that rule today then we'd start putting dwarf eh tables on all our C code, oops. Nick
I'm not sure I understand why it's blocked on that, by the way. Even if we can't apply the attribute ourselves, I don't see why we wouldn't expose that ability to frontends. I'm not entirely sure "halting" is the right attribute either, by the way. What I, personally, would like to see is a way to specify a function call is safe to speculatively execute. That implies readnone (not just readonly), nounwind, halting - and Eris knows what else. Nick, is that too strong for you? Michael -----Original Message----- From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On Behalf Of Nick Lewycky Sent: Monday, July 22, 2013 07:08 To: Andrew Trick Cc: llvmdev at cs.uiuc.edu Subject: Re: [LLVMdev] Does nounwind have semantics? Andrew Trick wrote:> Does 'nounwind' have semantics that inform optimization passes? It seems to in some cases, but not consistently. For example... > > int32_t foo(int32_t* ptr) { > int i = 0; > int result; > do { > bar(ptr); > result = *ptr; > bar(ptr); > } while (i++< *ptr); > return result; > } > > Say we have a front end that declares bar as... > > declare void @bar(i32*) readonly; > > So 'bar' is 'readonly' and 'may-unwind'. > > When LICM tries to hoist the load it interprets the 'may-unwind' as "MayThrow" in LICM-language and bails. However, when it tries to sink the call itself it sees the 'readonly', assumes no side effects and sinks it below the loads. Hmm... > > There doesn't appear to be a way to declare a function that is guaranteed not to write to memory in a way that affects the caller, but may have another well-defined side effect like aborting the program. This is interesting, because that is the way runtime checks for safe languages would like to be defined. I'm perfectly happy telling front ends to generate control flow for well-defined traps, since I like lots of basic blocks in my IR. But I'm still curious how others deal with this.Yes, we went through a phase where people would try to use "nounwind+readonly == no side-effects" to optimize. All such optimizations are wrong. Unless otherwise proven, a function may inf-loop, terminate the program, or longjmp. I tried to add 'halting' to help solve part of this a long time ago, but it never went in. The problem is that determining whether you have loops requires a FunctionPass (LoopInfo to find loops and SCEV to determine an upper bound) and applying function attributes is an SCC operation (indeed, an SCC is itself a loop), so it's all blocked behind fixing the PassManager to allow CGSGGPasses to depend on FunctionPasses. http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20100705/103670.html I'm now in a similar situation where I want 'nounwind' to mean "only exits by terminating the program or a return instruction" but unfortunately functions which longjmp are considered nounwind. I would like to change llvm to make longjmp'ing a form of unwinding (an exceptional exit to the function), but if I were to apply that rule today then we'd start putting dwarf eh tables on all our C code, oops. Nick _______________________________________________ LLVM Developers mailing list LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev --------------------------------------------------------------------- Intel Israel (74) Limited This e-mail and any attachments may contain confidential material for the sole use of the intended recipient(s). Any review or distribution by others is strictly prohibited. If you are not the intended recipient, please contact the sender and delete all copies.
Hi Andrew, On 22/07/13 02:56, Andrew Trick wrote:> Does 'nounwind' have semantics that inform optimization passes? It seems to in some cases, but not consistently. For example... > > int32_t foo(int32_t* ptr) { > int i = 0; > int result; > do { > bar(ptr); > result = *ptr; > bar(ptr); > } while (i++ < *ptr); > return result; > } > > Say we have a front end that declares bar as... > > declare void @bar(i32*) readonly; > > So 'bar' is 'readonly' and 'may-unwind'. > > When LICM tries to hoist the load it interprets the 'may-unwind' as "MayThrow" in LICM-language and bails. However, when it tries to sink the call itself it sees the 'readonly', assumes no side effects and sinks it below the loads. Hmm...is your worry here about the following case? - the load will trap if executed - bar throws an exception Thus with the original code the trap will not occur, because an exception will be thrown first, while if you move the first bar call below the load then the tap will occur.> > There doesn't appear to be a way to declare a function that is guaranteed not to write to memory in a way that affects the caller, but may have another well-defined side effect like aborting the program.I'm pretty sure that exiting the program is considered to write memory, so bar can't do that itself. Ciao, Duncan. This is interesting, because that is the way runtime checks for safe languages would like to be defined. I'm perfectly happy telling front ends to generate control flow for well-defined traps, since I like lots of basic blocks in my IR. But I'm still curious how others deal with this.> > -Andy > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >
Hi Eli, On 22/07/13 03:37, Eli Friedman wrote:> On Sun, Jul 21, 2013 at 5:56 PM, Andrew Trick <atrick at apple.com> wrote: >> Does 'nounwind' have semantics that inform optimization passes? It seems to in some cases, but not consistently. For example... >> >> int32_t foo(int32_t* ptr) { >> int i = 0; >> int result; >> do { >> bar(ptr); >> result = *ptr; >> bar(ptr); >> } while (i++ < *ptr); >> return result; >> } >> >> Say we have a front end that declares bar as... >> >> declare void @bar(i32*) readonly; >> >> So 'bar' is 'readonly' and 'may-unwind'. > > It's impossible to write a readonly function which throws a DWARF > exception. Given that, I would imagine there are all sorts of bugs > nobody has ever run into.very true. That said, it is a pity not to support other ways of doing exception handling. For example, you could declare every function to return two results, the usual one and an additional i1 result. If the i1 value returned is 1 then this means that "an exception is being unwound", and the caller should jump to the landing pad if there is one; and if there isn't then it itself should return 1. This scheme doesn't write memory. OK, now imagine implementing this scheme where the additional return value is hidden, only implicitly present. You can argue that the function still doesn't write memory, though I admit you could also argue that the only way we have to model this extra parameter is to say that the function writes memory. What is a bit more problematic is that there is then also an implicit control flow construct ("if exception_value == 1 then return 1; end if") after every call. If everything was explicit then the above code bar(ptr); result = *ptr; bar(ptr); would be exc = bar(ptr); if (exc) return 1; result = *ptr; exc = bar(ptr); if (exc) return 1; At this point it is clear that because bar is readonly, the second bar call can be dropped, giving exc = bar(ptr); if (exc) return 1; result = *ptr; However it would have been wrong to drop the first bar call. This is all obvious when there are no hidden parameters and everything is explicit. I can't help feeling that either we should require everything to be explicit like this, or if it is implicit then probably we should say that bar does write memory (the invisible return parameter). But even then the implicit control flow after the bar call isn't modelled (already the case with the usual exception handling) which is an endless source of little bugs, though in practice as people don't raise exceptions much the bugs aren't noticed... Ciao, Duncan.
On Jul 21, 2013, at 11:55 PM, Duncan Sands <baldrick at free.fr> wrote:> Hi Andrew, > > On 22/07/13 02:56, Andrew Trick wrote: >> Does 'nounwind' have semantics that inform optimization passes? It seems to in some cases, but not consistently. For example... >> >> int32_t foo(int32_t* ptr) { >> int i = 0; >> int result; >> do { >> bar(ptr); >> result = *ptr; >> bar(ptr); >> } while (i++ < *ptr); >> return result; >> } >> >> Say we have a front end that declares bar as... >> >> declare void @bar(i32*) readonly; >> >> So 'bar' is 'readonly' and 'may-unwind'. >> >> When LICM tries to hoist the load it interprets the 'may-unwind' as "MayThrow" in LICM-language and bails. However, when it tries to sink the call itself it sees the 'readonly', assumes no side effects and sinks it below the loads. Hmm... > > is your worry here about the following case? > - the load will trap if executed > - bar throws an exception > Thus with the original code the trap will not occur, because an exception will > be thrown first, while if you move the first bar call below the load then the > tap will occur.Essentially, yes. My takeaway from looking into it is: - nounwind means no dwarf EH. Absence of nounwind means absence of dwarf EH. It would be unwise for optimization passes to reason about the semantics beyond that. I was momentarily mislead by the LICM code that handles MayThrow specially. - Things that throw exceptions or trap in defined ways are not readonly. - Runtime checks for overflow, div-by-zero, bounds checks, etc. should be implemented at the IR level as branches to noreturn calls because it can be done that way and I haven’t seen concrete evidence that it’s too expensive. Don’t try to do something fancy with intrinsics and attributes unless absolutely required. - Optimizing readonly calls in C is a tangentially related issue, as Nick explained. My answer to that problem is that C compilers are effectively forced to assume that calls terminate, so developers should not expect otherwise. If C developers don’t want the compiler to optimize their infinite loop or infinite recursion, they need to throw in a volatile dereference. -Andy>> >> There doesn't appear to be a way to declare a function that is guaranteed not to write to memory in a way that affects the caller, but may have another well-defined side effect like aborting the program. > > I'm pretty sure that exiting the program is considered to write memory, so bar > can't do that itself. > > Ciao, Duncan. > > This is interesting, because that is the way runtime checks for safe languages would like to be defined. I'm perfectly happy telling front ends to generate control flow for well-defined traps, since I like lots of basic blocks in my IR. But I'm still curious how others deal with this. >> >> -Andy >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130722/25ea056f/attachment.html>