>>>>> "Archie" == Archie Cobbs <archie at dellroad.org> writes:>> In the JIT, devirtualization looks doable, though somewhat fiddly. At >> least, that is true for straightforward things like calls to methods >> in final classes, or calls to methods on objects allocated with 'new' >> in the current function. (The latter could be done AOT, at least if >> you defined a way to do the appropriate runtime link; I've considered >> it for gcj.)Archie> I'm not that familiar with how your stuff works, but it sounds like Archie> you would have to do these optimizations before converting to LLVM Archie> format, right? Nope, I do all the optimizations after converting to LLVM, and in particular after the "promote memory to registers" pass has run (this fits into an implementation detail of my jit...). It is just much simpler to do these kinds of things on the SSA representation. I thought more about what you are saying, and I think I understand the problem. E.g., suppose we want to devirtualize not because a method is being called on the result of 'new' (since this is a particularly simple case) but because a method is being called on an object whose class happens to be 'final'. In this case we need to know some properties of the java type. (And, you can construct plenty of examples where java type information yields optimization opportunities.) But, I don't think this sort of thing is a big deal to deal with. In fact it seems to me that the only possible cases are method return types and field types (both instance and static of course). Like Chris said, you could have annotations for things on the side. E.g., map from functions to their java types, a map from global variables to their java types, etc. I think this plan wouldn't work so well if we had to annotate arbitrary values this way, since we wouldn't know whether passes might create or destroy values behind our back, but it seems to suffice to be able to map back to these four kinds of objects, and this is pretty easy. For precompilation, the situation is a bit different. But again, for precompilation of java you need to think about your linking strategy. And, if you want to preserve java semantics and allow multiple class loaders to load the "same" code, then you end up in the same kind of scenario -- the compiled form of a class has to indirectly refer to other classes, and this indirection can be used to recover "lost" type information. Anyway... I've written about 80% of a simple devirtualization pass for my jit, just as an experiment. (I also wrote it for gcj for good measure -- this one actually works :-). No big issues here, and I've been thinking about other little jvm-specific passes I could add. I'll check this in whenever I get around to finishing it. Tom
Tom Tromey wrote:>>> In the JIT, devirtualization looks doable, though somewhat fiddly. At >>> least, that is true for straightforward things like calls to methods >>> in final classes, or calls to methods on objects allocated with 'new' >>> in the current function. (The latter could be done AOT, at least if >>> you defined a way to do the appropriate runtime link; I've considered >>> it for gcj.) > > Archie> I'm not that familiar with how your stuff works, but it sounds like > Archie> you would have to do these optimizations before converting to LLVM > Archie> format, right? > > Nope, I do all the optimizations after converting to LLVM, and in > particular after the "promote memory to registers" pass has run (this > fits into an implementation detail of my jit...). It is just much > simpler to do these kinds of things on the SSA representation. > > I thought more about what you are saying, and I think I understand the > problem. E.g., suppose we want to devirtualize not because a method > is being called on the result of 'new' (since this is a particularly > simple case) but because a method is being called on an object whose > class happens to be 'final'. In this case we need to know some > properties of the java type. (And, you can construct plenty of > examples where java type information yields optimization > opportunities.) > > But, I don't think this sort of thing is a big deal to deal with. In > fact it seems to me that the only possible cases are method return > types and field types (both instance and static of course). Like > Chris said, you could have annotations for things on the side. E.g., > map from functions to their java types, a map from global variables to > their java types, etc. I think this plan wouldn't work so well if we > had to annotate arbitrary values this way, since we wouldn't know > whether passes might create or destroy values behind our back, but it > seems to suffice to be able to map back to these four kinds of > objects, and this is pretty easy. > > For precompilation, the situation is a bit different. But again, for > precompilation of java you need to think about your linking strategy. > And, if you want to preserve java semantics and allow multiple class > loaders to load the "same" code, then you end up in the same kind of > scenario -- the compiled form of a class has to indirectly refer to > other classes, and this indirection can be used to recover "lost" type > information.I see.. I hadn't thought of it that way, but you're right: knowing the java type of a LLVM object for optimization purposes is just a special case of a more general problem that you'd have to solve anyway, namely, knowing the java type of any LLVM variable or function for linking purposes. Instead of carrying the information along explicitly via annotations (or some equivalent), you just recompute it each time you need it. As long as that process is efficient, it's a perfectly valid strategy. So e.g. you would define symbols whose names encode the associated type info This is in fact what JCVM does inside ELF objects, using symbols such as "java_lang_Thread$class_object", for the same reason. Thanks, -Archie __________________________________________________________________________ Archie Cobbs * CTO, Awarix * http://www.awarix.com
On 29 Apr 2006 20:38:58 -0600, Tom Tromey <tromey at redhat.com> wrote:> >>>>> "Archie" == Archie Cobbs <archie at dellroad.org> writes: > > >> In the JIT, devirtualization looks doable, though somewhat fiddly. At > >> least, that is true for straightforward things like calls to methods > >> in final classes, or calls to methods on objects allocated with 'new' > >> in the current function. (The latter could be done AOT, at least if > >> you defined a way to do the appropriate runtime link; I've considered > >> it for gcj.) > > Archie> I'm not that familiar with how your stuff works, but it sounds like > Archie> you would have to do these optimizations before converting to LLVM > Archie> format, right? > > Nope, I do all the optimizations after converting to LLVM, and in > particular after the "promote memory to registers" pass has run (this > fits into an implementation detail of my jit...). It is just much > simpler to do these kinds of things on the SSA representation. > > I thought more about what you are saying, and I think I understand the > problem. E.g., suppose we want to devirtualize not because a method > is being called on the result of 'new' (since this is a particularly > simple case) but because a method is being called on an object whose > class happens to be 'final'. In this case we need to know some > properties of the java type. (And, you can construct plenty of > examples where java type information yields optimization > opportunities.)I think this example is even simpler than the method caled on the result of new. When translating invokevitual on objects of final classes just call the method directly and don't perform an indirect function call though the vtable. Ditto for final methods. -- Alkis
>>>>> "Alkis" == Alkis Evlogimenos <alkis at evlogimenos.com> writes:>> E.g., suppose we want to devirtualize not because a method >> is being called on the result of 'new' (since this is a particularly >> simple case) but because a method is being called on an object whose >> class happens to be 'final'. In this case we need to know some >> properties of the java type.Alkis> I think this example is even simpler than the method caled on the Alkis> result of new. When translating invokevitual on objects of final Alkis> classes just call the method directly and don't perform an indirect Alkis> function call though the vtable. Ditto for final methods. I think I didn't flesh out the example enough. A java compiler will emit invokevirtual calls using the qualifying type as seen in the source. So for instance, in a case like: Object x = "string"; int z = x.hashCode(); (which is dumb, but you get the idea :-) the compiler will generate an invokevirtual of 'Object.hashCode'. However, at runtime the jit could infer that the real type of 'x' is always String, and so emit a direct call to String.hashCode instead. In non-trivial cases it is a lot simpler to do this kind of thing on the SSA representation (as I'm sure you know :-). And in this case you need to be able to map from the LLVM representation back to the java types. Tom