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
Alkis Evlogimenos wrote:> On 4/25/06, Archie Cobbs <archie at dellroad.org> wrote: >> 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.If that were the implementation then yes that could work. But using a null pointer like this probably wouldn't be the case. In Java you have to load a class before you initialize it, so the pointer to the type structure will already be non-null. In JCVM for example, there is a bit in type->flags that determines whether the class is initialized or not. This bit has to be checked before every static method invocation or static field access. You could reserve an entire byte instead of a bit, but I don't know if that would make it any easier to do this optimization. ------ I'm not entirely convinced (or understanding) how the "no annotations" approach is supposed to work. For example, for optimizing away Java's "active use" checks as discussed above. How specifically does this optimzation get done? Saying that the implementation will "likely" use a null pointer is not an answer because, what if the implementation doesn't use a null pointer? I.e., my question is the more general one: how do optimizations that are specific to the front-end language get done? How does the front-end "secret knowledge" get passed through somehow so it can be used for optimization purposes? Apologies for sounding skeptical, I'm just trying to nail down an answer to a kindof philosophical question. ------ Another question: does LLVM know about or handle signal frames? What if code wants to unwind across a signal frame? This is another thing that would be required for Java if e.g. you wanted to detect null pointer access via signals. Note setjmp/longjmp works OK across signal frames. Thanks, -Archie __________________________________________________________________________ Archie Cobbs * CTO, Awarix * http://www.awarix.com
On Tue, 25 Apr 2006, Archie Cobbs wrote:> Another question: does LLVM know about or handle signal frames? What > if code wants to unwind across a signal frame? This is another thing > that would be required for Java if e.g. you wanted to detect null > pointer access via signals. Note setjmp/longjmp works OK across signal > frames.This is up to the unwinding library implementation for the target in question. LLVM will support it if your unwinder library supports it. -Chris -- http://nondot.org/sabre/ http://llvm.org/
On 4/25/06, Archie Cobbs <archie at dellroad.org> wrote:> Alkis Evlogimenos wrote: > > On 4/25/06, Archie Cobbs <archie at dellroad.org> wrote: > >> 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. > > If that were the implementation then yes that could work. But using > a null pointer like this probably wouldn't be the case. In Java you have > to load a class before you initialize it, so the pointer to the type > structure will already be non-null.That is why I said if you want it to be fast :-). My point was that if you want this to be fast you need to find a way to make it trap when a class is not initialized. If you employ the method you mention below for JCVM then you need to perform optimizations to simplify the conditionals.> In JCVM for example, there is a bit in type->flags that determines > whether the class is initialized or not. This bit has to be checked > before every static method invocation or static field access. You could > reserve an entire byte instead of a bit, but I don't know if that would > make it any easier to do this optimization. > > ------ > > I'm not entirely convinced (or understanding) how the "no annotations" > approach is supposed to work. For example, for optimizing away Java's > "active use" checks as discussed above. How specifically does this > optimzation get done? Saying that the implementation will "likely" use > a null pointer is not an answer because, what if the implementation > doesn't use a null pointer? I.e., my question is the more general one: > how do optimizations that are specific to the front-end language get > done? How does the front-end "secret knowledge" get passed through > somehow so it can be used for optimization purposes? > > Apologies for sounding skeptical, I'm just trying to nail down an > answer to a kindof philosophical question. > > ------ > > Another question: does LLVM know about or handle signal frames? What > if code wants to unwind across a signal frame? This is another thing > that would be required for Java if e.g. you wanted to detect null > pointer access via signals. Note setjmp/longjmp works OK across signal > frames. > > Thanks, > -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
>>>>> "Archie" == Archie Cobbs <archie at dellroad.org> writes:Archie> In JCVM for example, there is a bit in type->flags that Archie> determines whether the class is initialized or not. This bit Archie> has to be checked before every static method invocation or Archie> static field access. You could reserve an entire byte instead Archie> of a bit, but I don't know if that would make it any easier to Archie> do this optimization. My plan for this in my JIT is to just recompile the bytecode for the function after class initializations, constant pool resolutions, and the like. This is somewhat crude, but seems like it should work fine. The full plan is to have some kind of heuristic so we don't go around recompiling functions that are rarely called. Thoughts on that? Archie> I.e., my question is the more general one: Archie> how do optimizations that are specific to the front-end language get Archie> done? How does the front-end "secret knowledge" get passed through Archie> somehow so it can be used for optimization purposes? I was thinking that I would write some extra JVM-specific LLVM passes and add them to the pass manager I construct. I haven't started this, so I have no idea how I would handle passing the information back and forth. Tom