On Wed, Jun 17, 2009 at 3:01 PM, Ray Cromwell <cromwell...@gmail.com> wrote:
> Bruce, By type cloning, do you mean using typeflow information to compute
> a set of types for a given reference, and then speculatively type
> tightening?
>
I'm talking about something else, but you're right about the Will explain
more in the bottom section.
>
> We can compute the set of potential concrete types for 'list' as
> {LinkedList, ArrayList}. Therefore, we can inline the call to list.get(n),
> as:
>
This is what Scott and Lex have been calling something like, "set-base type
tightening".
If someNonInlineableMethod() is only ever reached from blocks where the
> parameter is ArrayList, then the 'l' parameter can be tightened to
> ArrayList. You need CFG/flow analysis because methodA(List l) might call
> methodB(List l) where the chain is only ever invoked with ArrayList.
>
We do a CFG-independent version of what you're talking about. We do tighten
parameter types, but only based on the (tightened) types of all the call
sites, without regard to control flow.
=== Type Cloning ===
What I mean by type cloning is this: for every unique (lexical) occurrence
of an allocation of type T, clone T into T' as if it were an independent
type, but arrange that T' is indistinguishable from T w.r.t. casts,
instanceof, and getClass(). In other words, you could never determine at
runtime that the object wasn't actually a genuine T. Now, optimize as
normal. To see how this could play out:
class BasicList<E> {
private E[] elems;
@SuppressWarnings("unchecked")
public void add(E elem) {
if (elems == null) {
elems = (E[]) new Object[] {elem};
} else {
E[] newElems = (E[]) new Object[elems.length + 1];
System.arraycopy(elems, 0, newElems, 0, elems.length);
newElems[newElems.length - 1] = elem;
elems = newElems;
}
}
public int size() {
return elems == null ? 0 : elems.length;
}
public Iterator<E> iterator() {
final int n = size();
return new Iterator<E>() {
private final int i = 0;
public boolean hasNext() {
return i < n;
}
public E next() {
return elems[i];
}
public void remove() {
// nothing
}
};
}
}
// Then in some other code, you could write...
void foo() {
BasicList<String> b = new BasicList<String>();
for (int i = 0, n = b.size(); i < n; ++i) {
// Removed by dead code elim.
}
for (String s: b) {
// Also removed by dead code elim.
}
}
In the above, b is of type BasicList' (a clone of BasicList that can be
independently optimized). Thus, you can see that BasicList' does not have
the add() method called, which means that, for this particular use of the
type, the 'elems' field will always be null. Consequently, size() can be
statically known to return 0. Similarly, the iterator's hasNext() method can
be statically shown to always return false in the for/each loop.
The key point is that the usage of a type in one context would not affect
how the type itself could be optimized in other contexts. As it stands
today, we can't do the above optimization if anywhere in the program someone
calls BasicList#add(). A great practical example is Widgets firing events.
You want widgets to be *able* to fire events *if* someone actually wants to
listen to them. In the cases where you can see that there are no listeners
to a widget, you'd really like the entirely of the even-firing infrastructur
to completely disappear. So, I think it can be a big win.
--~--~---------~--~----~------------~-------~--~----~
http://groups.google.com/group/Google-Web-Toolkit-Contributors
-~----------~----~----~----~------~----~------~--~---
