On Mon, 24 Apr 2006, Archie Cobbs wrote:> Related idea.. what if all instructions (not just "invoke") could be > allowed to have an optional "except label ..."?This is the direction that we plan to go, when someone is interested enough to implement it. There are some rough high-level notes about this idea here: http://nondot.org/sabre/LLVMNotes/ExceptionHandlingChanges.txt -Chris -- http://nondot.org/sabre/ http://llvm.org/
Chris Lattner wrote:> On Mon, 24 Apr 2006, Archie Cobbs wrote: >> Related idea.. what if all instructions (not just "invoke") could be >> allowed to have an optional "except label ..."? > > This is the direction that we plan to go, when someone is interested > enough to implement it. There are some rough high-level notes about > this idea here: > http://nondot.org/sabre/LLVMNotes/ExceptionHandlingChanges.txtThose ideas make sense.. one question though:> Note that this bit is sufficient to represent many possible scenarios. In > particular, a Java compiler would mark just about every load, store and other > exception inducing operation as traping. If a load is marked potentially > trapping, the optimizer is required to preserve it (even if its value is not > used) unless it can prove that it dynamically cannot trap. In practice, this > means that standard LLVM analyses would be used to prove that exceptions > cannot happen, then clear the bit. As the bits are cleared, exception handlers > can be deleted and dead loads (for example) can also be removed.The idea of the optimizer computing that a trap can't happen is obviously desirable, but how does the front end tell the optimizer how to figure that out? I.e., consider this java: void foo(SomeClass x) { x.field1 = 123; x.field2 = 456; // no nNullPointerException possible here } Clearly an exception can happen with the first statement -- iff x is null. But no exception is possible on the second statement. But how does the optimizer "know" this without being Java specific? It seems like LLVM will have to have some built-in notion of a "null pointer" generated exception. Similarly for divide by zero, e.g.: void bar(int x) { if (x != 0) this.y = 100/x; // no ArithmeticException possible here } How will the optimizer "know" the exception can't happen? ------ Another random question: can a global variable be considered variable in one function but constant in another? Motivation: Java's "first active use" requirement for class initialization. When invoking a static method, it's possible that a class may need to be initialized, However, when invoking an instance method, that's not possible. Perhaps there should be a way in LLVM to specify predicates (or at least properties of global variables and parameters) that are known to be true at the start of each function... ? ----- In general, I agree with the idea that front-end annotations are fraught with questions and complexity. But the alternative requires expressing all that same information explicitly in LLVM, which is what I'm wondering about. ----- Trying to summarize this thread a bit, here is a list of some of the issues brought up relating to the goal of "best case" Java support... 1. Definition and clarification of the memory model. 2. Need some instructions for atomic operations. 3. Explicit support for exceptions from instructions other than invoke. 4. Ensuring there are mechanisms for passing through all appropriate optimization-useful information from the front end to LLVM in a non-Java-specific way (e.g., see "active use" check above). -Archie __________________________________________________________________________ Archie Cobbs * CTO, Awarix * http://www.awarix.com
On 4/25/06, Archie Cobbs <archie at dellroad.org> wrote:> Chris Lattner wrote: > > On Mon, 24 Apr 2006, Archie Cobbs wrote: > >> Related idea.. what if all instructions (not just "invoke") could be > >> allowed to have an optional "except label ..."? > > > > This is the direction that we plan to go, when someone is interested > > enough to implement it. There are some rough high-level notes about > > this idea here: > > http://nondot.org/sabre/LLVMNotes/ExceptionHandlingChanges.txt > > Those ideas make sense.. one question though: > > > Note that this bit is sufficient to represent many possible scenarios. In > > particular, a Java compiler would mark just about every load, store and other > > exception inducing operation as traping. If a load is marked potentially > > trapping, the optimizer is required to preserve it (even if its value is not > > used) unless it can prove that it dynamically cannot trap. In practice, this > > means that standard LLVM analyses would be used to prove that exceptions > > cannot happen, then clear the bit. As the bits are cleared, exception handlers > > can be deleted and dead loads (for example) can also be removed. > > The idea of the optimizer computing that a trap can't happen is obviously > desirable, but how does the front end tell the optimizer how to figure > that out? I.e., consider this java: > > void foo(SomeClass x) { > x.field1 = 123; > x.field2 = 456; // no nNullPointerException possible here > } > > Clearly an exception can happen with the first statement -- iff x is null. > But no exception is possible on the second statement. But how does the > optimizer "know" this without being Java specific? It seems like LLVM > will have to have some built-in notion of a "null pointer" generated > exception. Similarly for divide by zero, e.g.:I think this is feasible to optimize in llvm. This would require to write an optimization pass (that can be used by any language implementation). Since x.field1 and x.field2 will involve getelementptr instructions, we can have some logic in an optimization pass to prove what you are saying: if x is null then only the first memop through a getelementptr on x will trap.> void bar(int x) { > if (x != 0) > this.y = 100/x; // no ArithmeticException possible here > } > > How will the optimizer "know" the exception can't happen?This should be pretty straight forward to implement as well (by writing the proper optimization pass).> ------ > > Another random question: can a global variable be considered variable > in one function but constant in another?No.> Motivation: Java's "first active use" requirement for class initialization. > When invoking a static method, it's possible that a class may need to > be initialized, However, when invoking an instance method, that's not > possible. > > Perhaps there should be a way in LLVM to specify predicates (or at least > properties of global variables and parameters) that are known to be true > at the start of each function... ?I think this will end up being the same as the null pointer trapping instruction optimization. The implementation will very likely involve some pointer to the description of the class. To make this fast this pointer will be null if the class is not loaded and you trap when you try to use it and perform initialization. So in the end the same optimization pass that was used for successive field accesses can be used for class initialization as well.> ----- > > In general, I agree with the idea that front-end annotations are fraught > with questions and complexity. But the alternative requires expressing all > that same information explicitly in LLVM, which is what I'm wondering about. > > ----- > > Trying to summarize this thread a bit, here is a list of some of the > issues brought up relating to the goal of "best case" Java support... > > 1. Definition and clarification of the memory model. > 2. Need some instructions for atomic operations. > 3. Explicit support for exceptions from instructions other than invoke. > 4. Ensuring there are mechanisms for passing through all appropriate > optimization-useful information from the front end to LLVM in a > non-Java-specific way (e.g., see "active use" check above). > > -Archie > > __________________________________________________________________________ > Archie Cobbs * CTO, Awarix * http://www.awarix.com > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-- Alkis
On Mon, 24 Apr 2006, Archie Cobbs wrote:> The idea of the optimizer computing that a trap can't happen is obviously > desirable, but how does the front end tell the optimizer how to figureIt depends on the front-end. If you're coming from C, there is no good way. C can't express these properties well. However, this this specific case:> that out? I.e., consider this java: > > void foo(SomeClass x) { > x.field1 = 123; > x.field2 = 456; // no nNullPointerException possible here > } > > Clearly an exception can happen with the first statement -- iff x is null. > But no exception is possible on the second statement. But how does the > optimizer "know" this without being Java specific?This isn't specific to Java. LLVM pointers can't wrap around the end of the address space, so if the first access successed, the second must also. LLVM won't guarantee exceptions for bogus pointers, just null pointers, so it could do this without a problem.> Another random question: can a global variable be considered variable > in one function but constant in another?No.> Motivation: Java's "first active use" requirement for class initialization. > When invoking a static method, it's possible that a class may need to > be initialized, However, when invoking an instance method, that's not > possible.You need to modify the isConstant flag on the global after the initializer has been run. This requires JIT compilation. Note that the LLVM optimizer should already do a reasonable job of optimizing some common cases of this, as a similar thing happens when initializing C++ static variables.> Perhaps there should be a way in LLVM to specify predicates (or at least > properties of global variables and parameters) that are known to be true > at the start of each function... ?We don't have something like this currently. It sounds tricky to get right.> Trying to summarize this thread a bit, here is a list of some of the > issues brought up relating to the goal of "best case" Java support... > > 1. Definition and clarification of the memory model. > 2. Need some instructions for atomic operations. > 3. Explicit support for exceptions from instructions other than invoke. > 4. Ensuring there are mechanisms for passing through all appropriate > optimization-useful information from the front end to LLVM in a > non-Java-specific way (e.g., see "active use" check above).Yup. -Chris -- http://nondot.org/sabre/ http://llvm.org/