wilson@uicbert.eecs.uic.edu (10/02/88)
To motivate the discussion of dynamic optimization, here's a simple example of why I think it might be worthwhile. Suppose you have a language in which you can have homogeneous collections like array-of-integer. (Or an implementation that lets you declare them.) Suppose also that the language is basically dynamically typed, and that the declared types are attached to the objects at runtime. So an array of integer would have a header saying so. Now suppose we define a routine that processes collections, looping to apply some operation to its elements. A dynamic optimizing system would generate a generic version of the code that checks the types of the arguments and then dispatches to an optimized version for those types. If it has never seen that combination of types before, a new version is created on the fly. So the first time this generic code sees an array-of-integer, it compiles a version of the looping routine that assumes each element is an integer, omitting tag checks, unrolling the loop, etc. The generic code must always check the collection's type when it is executed, but the compiled code it dispatches to needn't. (If it's not a homogeneous collection, it simply dispatches to a normal version with type checking.) The nice thing about this is that the code is still generic from the programmer's point of view, and type checking is not abandoned. (Unlike systems in which declarations tell the compiler to make assumptions at a particular point in the code.) My guess is that for most programs, most routines are only ever given one kind of argument, so there wouldn't be an explosion of versions. (You can always use a cache and throw away disused versions.) At least for this example, the optimization would be transparent and safe. If somebody changes (at another point in the code) the type of some object that is passed to the optimized routine, the dynamic check will ensure that an appropriate version is generated. Now the question is how general this system could be, using more sophisticated type inference than recognizing homogeneous collections. And can it be combined with nifty trace-scheduling techniques to precompute paths through often-executed chunks of code and seriously optimize them? Paul R. Wilson Human-Computer Interaction Laboratory U. of Illin. at C. EECS Dept. (M/C 154) wilson%uicbert@uxc.cso.uiuc.edu Box 4348 Chicago,IL 60680