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>
Hi Andrew, On 22/07/13 09:32, Andrew Trick wrote:> > On Jul 21, 2013, at 11:55 PM, Duncan Sands <baldrick at free.fr > <mailto: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:my understanding is different. I'm pretty sure that what I'm about to say is the traditional way these things have been viewed in LLVM. That doesn't mean that it's the best way to view these things.> - nounwind means no dwarf EH. AbsenceI guess you mean presence. 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.nounwind has nothing to do with dwarf, since exceptions themselves need have nothing to do with dwarf (which is just one way of implementing exception handling). Don't forget setjmp/longjmp exception handling, and also exception handling by returning an extra invisible parameter (which I mentioned in another email) which IIRC was actually implemented by someone at the codegen level at some point as it was faster than dwarf for code that throws exceptions a lot. An additional point is that while in C++ you create an exception object, not all languages associate an object with an exception, some just want to do the equivalent of a non-local goto. Creating an exception object means allocating memory, mucking around with global data structures and obviously writing memory. A non-local goto doesn't have to do more than unwind the stack until it gets to the right frame then do a jump. It's not clear to me that that should be considered as writing memory. Here's my take: a call to an function marked nounwind either never returns (eg infinite loop or exits the program) or returns normally. It doesn't "return" by unwinding the stack out of the caller. On the other hand a function that is not marked nounwind may "return" by unwinding the stack; control in this case doesn't continue in the caller, it continues at least one further up the stack. Thus in this case the instructions after the call instruction are not executed. Note I'm talking about an ordinary call here, not an invoke. In the case of an invoke control may continue in the caller function, but only at a well-defined point (the landing pad).> - Things that throw exceptions or trap in defined ways are not readonly.See above for why throwing an exception doesn't have to write memory. Dwarf exception handling, and anything which can be used to implement C++ exception handling, is clearly writing memory and thus cannot be used inside a readonly function. So yes, any function Clang produces that throws an exception is not going to be readonly. But as I mentioned above some languages have no exception object and just unwind the stack. For these the expression "throwing an exception" (which implicitly includes the idea that there is an exception object) is not really appropriate; "unwinds the stack" is the basic concept here. This is basically orthogonal to 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.I agree with this. Ciao, Duncan.> - 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 <mailto:LLVMdev at cs.uiuc.edu>http://llvm.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 <mailto:LLVMdev at cs.uiuc.edu>http://llvm.cs.uiuc.edu >> <http://llvm.cs.uiuc.edu/> >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >
On Jul 22, 2013, at 12:56 AM, Duncan Sands <baldrick at free.fr> wrote:> my understanding is different. I'm pretty sure that what I'm about to say is > the traditional way these things have been viewed in LLVM. That doesn't mean > that it's the best way to view these things. > >> - nounwind means no dwarf EH. Absence > > I guess you mean presence. > > 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. > > nounwind has nothing to do with dwarf, since exceptions themselves need have > nothing to do with dwarf (which is just one way of implementing exception > handling). Don't forget setjmp/longjmp exception handling, and also exception > handling by returning an extra invisible parameter (which I mentioned in > another email) which IIRC was actually implemented by someone at the codegen > level at some point as it was faster than dwarf for code that throws exceptions > a lot. An additional point is that while in C++ you create an exception object, > not all languages associate an object with an exception, some just want to do > the equivalent of a non-local goto. Creating an exception object means > allocating memory, mucking around with global data structures and obviously > writing memory. A non-local goto doesn't have to do more than unwind the stack > until it gets to the right frame then do a jump. It's not clear to me that that > should be considered as writing memory. > > Here's my take: a call to an function marked nounwind either never returns > (eg infinite loop or exits the program) or returns normally. It doesn't > "return" by unwinding the stack out of the caller. On the other hand a > function that is not marked nounwind may "return" by unwinding the stack; > control in this case doesn't continue in the caller, it continues at least one > further up the stack. Thus in this case the instructions after the call > instruction are not executed. Note I'm talking about an ordinary call here, > not an invoke. In the case of an invoke control may continue in the caller > function, but only at a well-defined point (the landing pad).Good explanation. Your definition of nounwind is completely logical. I would prefer not to rely on it though because - Realistically, the semantics won’t be well tested. - It doesn’t seem terribly important to treat nonlocal gotos as readonly (though maybe it is to you :) - When it is important to optimize memory access around nonlocal gotos, I prefer to expose control flow to the optimizer explicitly. e.g. why not just use invokes for all your may-throw calls, then you’re free to mark them readonly? -Andy>> - Things that throw exceptions or trap in defined ways are not readonly. > > See above for why throwing an exception doesn't have to write memory. Dwarf > exception handling, and anything which can be used to implement C++ exception > handling, is clearly writing memory and thus cannot be used inside a readonly > function. So yes, any function Clang produces that throws an exception is not > going to be readonly. But as I mentioned above some languages have no > exception object and just unwind the stack. For these the expression "throwing > an exception" (which implicitly includes the idea that there is an exception > object) is not really appropriate; "unwinds the stack" is the basic concept > here. This is basically orthogonal to 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. > > I agree with this.-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130722/ccfcb60f/attachment.html>