| 1 |
Date: Sun, 19 Nov 2000 16:23:57 -0600 (CST) |
| 2 |
From: Chris Lattner <[email protected]> |
| 3 |
To: Vikram Adve <[email protected]> |
| 4 |
Subject: Re: a few thoughts |
| 5 |
|
| 6 |
Okay... here are a few of my thoughts on this (it's good to know that we |
| 7 |
think so alike!): |
| 8 |
|
| 9 |
> 1. We need to be clear on our goals for the VM. Do we want to emphasize |
| 10 |
> portability and safety like the Java VM? Or shall we focus on the |
| 11 |
> architecture interface first (i.e., consider the code generation and |
| 12 |
> processor issues), since the architecture interface question is also |
| 13 |
> important for portable Java-type VMs? |
| 14 |
|
| 15 |
I forsee the architecture looking kinda like this: (which is completely |
| 16 |
subject to change) |
| 17 |
|
| 18 |
1. The VM code is NOT guaranteed safe in a java sense. Doing so makes it |
| 19 |
basically impossible to support C like languages. Besides that, |
| 20 |
certifying a register based language as safe at run time would be a |
| 21 |
pretty expensive operation to have to do. Additionally, we would like |
| 22 |
to be able to statically eliminate many bounds checks in Java |
| 23 |
programs... for example. |
| 24 |
|
| 25 |
2. Instead, we can do the following (eventually): |
| 26 |
* Java bytecode is used as our "safe" representation (to avoid |
| 27 |
reinventing something that we don't add much value to). When the |
| 28 |
user chooses to execute Java bytecodes directly (ie, not |
| 29 |
precompiled) the runtime compiler can do some very simple |
| 30 |
transformations (JIT style) to convert it into valid input for our |
| 31 |
VM. Performance is not wonderful, but it works right. |
| 32 |
* The file is scheduled to be compiled (rigorously) at a later |
| 33 |
time. This could be done by some background process or by a second |
| 34 |
processor in the system during idle time or something... |
| 35 |
* To keep things "safe" ie to enforce a sandbox on Java/foreign code, |
| 36 |
we could sign the generated VM code with a host specific private |
| 37 |
key. Then before the code is executed/loaded, we can check to see if |
| 38 |
the trusted compiler generated the code. This would be much quicker |
| 39 |
than having to validate consistency (especially if bounds checks have |
| 40 |
been removed, for example) |
| 41 |
|
| 42 |
> This is important because the audiences for these two goals are very |
| 43 |
> different. Architects and many compiler people care much more about |
| 44 |
> the second question. The Java compiler and OS community care much more |
| 45 |
> about the first one. |
| 46 |
|
| 47 |
3. By focusing on a more low level virtual machine, we have much more room |
| 48 |
for value add. The nice safe "sandbox" VM can be provided as a layer |
| 49 |
on top of it. It also lets us focus on the more interesting compilers |
| 50 |
related projects. |
| 51 |
|
| 52 |
> 2. Design issues to consider (an initial list that we should continue |
| 53 |
> to modify). Note that I'm not trying to suggest actual solutions here, |
| 54 |
> but just various directions we can pursue: |
| 55 |
|
| 56 |
Understood. :) |
| 57 |
|
| 58 |
> a. A single-assignment VM, which we've both already been thinking |
| 59 |
> about. |
| 60 |
|
| 61 |
Yup, I think that this makes a lot of sense. I am still intrigued, |
| 62 |
however, by the prospect of a minimally allocated VM representation... I |
| 63 |
think that it could have definite advantages for certain applications |
| 64 |
(think very small machines, like PDAs). I don't, however, think that our |
| 65 |
initial implementations should focus on this. :) |
| 66 |
|
| 67 |
Here are some other auxiliary goals that I think we should consider: |
| 68 |
|
| 69 |
1. Primary goal: Support a high performance dynamic compilation |
| 70 |
system. This means that we have an "ideal" division of labor between |
| 71 |
the runtime and static compilers. Of course, the other goals of the |
| 72 |
system somewhat reduce the importance of this point (f.e. portability |
| 73 |
reduces performance, but hopefully not much) |
| 74 |
2. Portability to different processors. Since we are most familiar with |
| 75 |
x86 and solaris, I think that these two are excellent candidates when |
| 76 |
we get that far... |
| 77 |
3. Support for all languages & styles of programming (general purpose |
| 78 |
VM). This is the point that disallows java style bytecodes, where all |
| 79 |
array refs are checked for bounds, etc... |
| 80 |
4. Support linking between different language families. For example, call |
| 81 |
C functions directly from Java without using the nasty/slow/gross JNI |
| 82 |
layer. This involves several subpoints: |
| 83 |
A. Support for languages that require garbage collectors and integration |
| 84 |
with languages that don't. As a base point, we could insist on |
| 85 |
always using a conservative GC, but implement free as a noop, f.e. |
| 86 |
|
| 87 |
> b. A strongly-typed VM. One question is do we need the types to be |
| 88 |
> explicitly declared or should they be inferred by the dynamic |
| 89 |
> compiler? |
| 90 |
|
| 91 |
B. This is kind of similar to another idea that I have: make OOP |
| 92 |
constructs (virtual function tables, class heirarchies, etc) explicit |
| 93 |
in the VM representation. I believe that the number of additional |
| 94 |
constructs would be fairly low, but would give us lots of important |
| 95 |
information... something else that would/could be important is to |
| 96 |
have exceptions as first class types so that they would be handled in |
| 97 |
a uniform way for the entire VM... so that C functions can call Java |
| 98 |
functions for example... |
| 99 |
|
| 100 |
> c. How do we get more high-level information into the VM while keeping |
| 101 |
> to a low-level VM design? |
| 102 |
> o Explicit array references as operands? An alternative is |
| 103 |
> to have just an array type, and let the index computations be |
| 104 |
> separate 3-operand instructions. |
| 105 |
|
| 106 |
C. In the model I was thinking of (subject to change of course), we |
| 107 |
would just have an array type (distinct from the pointer |
| 108 |
types). This would allow us to have arbitrarily complex index |
| 109 |
expressions, while still distinguishing "load" from "Array load", |
| 110 |
for example. Perhaps also, switch jump tables would be first class |
| 111 |
types as well? This would allow better reasoning about the program. |
| 112 |
|
| 113 |
5. Support dynamic loading of code from various sources. Already |
| 114 |
mentioned above was the example of loading java bytecodes, but we want |
| 115 |
to support dynamic loading of VM code as well. This makes the job of |
| 116 |
the runtime compiler much more interesting: it can do interprocedural |
| 117 |
optimizations that the static compiler can't do, because it doesn't |
| 118 |
have all of the required information (for example, inlining from |
| 119 |
shared libraries, etc...) |
| 120 |
|
| 121 |
6. Define a set of generally useful annotations to add to the VM |
| 122 |
representation. For example, a function can be analysed to see if it |
| 123 |
has any sideeffects when run... also, the MOD/REF sets could be |
| 124 |
calculated, etc... we would have to determine what is reasonable. This |
| 125 |
would generally be used to make IP optimizations cheaper for the |
| 126 |
runtime compiler... |
| 127 |
|
| 128 |
> o Explicit instructions to handle aliasing, e.g.s: |
| 129 |
> -- an instruction to say "I speculate that these two values are not |
| 130 |
> aliased, but check at runtime", like speculative execution in |
| 131 |
> EPIC? |
| 132 |
> -- or an instruction to check whether two values are aliased and |
| 133 |
> execute different code depending on the answer, somewhat like |
| 134 |
> predicated code in EPIC |
| 135 |
|
| 136 |
These are also very good points... if this can be determined at compile |
| 137 |
time. I think that an epic style of representation (not the instruction |
| 138 |
packing, just the information presented) could be a very interesting model |
| 139 |
to use... more later... |
| 140 |
|
| 141 |
> o (This one is a difficult but powerful idea.) |
| 142 |
> A "thread-id" field on every instruction that allows the static |
| 143 |
> compiler to generate a set of parallel threads, and then have |
| 144 |
> the runtime compiler and hardware do what they please with it. |
| 145 |
> This has very powerful uses, but thread-id on every instruction |
| 146 |
> is expensive in terms of instruction size and code size. |
| 147 |
> We would need to compactly encode it somehow. |
| 148 |
|
| 149 |
Yes yes yes! :) I think it would be *VERY* useful to include this kind |
| 150 |
of information (which EPIC architectures *implicitly* encode. The trend |
| 151 |
that we are seeing supports this greatly: |
| 152 |
|
| 153 |
1. Commodity processors are getting massive SIMD support: |
| 154 |
* Intel/Amd MMX/MMX2 |
| 155 |
* AMD's 3Dnow! |
| 156 |
* Intel's SSE/SSE2 |
| 157 |
* Sun's VIS |
| 158 |
2. SMP is becoming much more common, especially in the server space. |
| 159 |
3. Multiple processors on a die are right around the corner. |
| 160 |
|
| 161 |
If nothing else, not designing this in would severely limit our future |
| 162 |
expansion of the project... |
| 163 |
|
| 164 |
> Also, this will require some reading on at least two other |
| 165 |
> projects: |
| 166 |
> -- Multiscalar architecture from Wisconsin |
| 167 |
> -- Simultaneous multithreading architecture from Washington |
| 168 |
> |
| 169 |
> o Or forget all this and stick to a traditional instruction set? |
| 170 |
|
| 171 |
Heh... :) Well, from a pure research point of view, it is almost more |
| 172 |
attactive to go with the most extreme/different ISA possible. On one axis |
| 173 |
you get safety and conservatism, and on the other you get degree of |
| 174 |
influence that the results have. Of course the problem with pure research |
| 175 |
is that often times there is no concrete product of the research... :) |
| 176 |
|
| 177 |
> BTW, on an unrelated note, after the meeting yesterday, I did remember |
| 178 |
> that you had suggested doing instruction scheduling on SSA form instead |
| 179 |
> of a dependence DAG earlier in the semester. When we talked about |
| 180 |
> it yesterday, I didn't remember where the idea had come from but I |
| 181 |
> remembered later. Just giving credit where its due... |
| 182 |
|
| 183 |
:) Thanks. |
| 184 |
|
| 185 |
> Perhaps you can save the above as a file under RCS so you and I can |
| 186 |
> continue to expand on this. |
| 187 |
|
| 188 |
I think it makes sense to do so when we get our ideas more formalized and |
| 189 |
bounce it back and forth a couple of times... then I'll do a more formal |
| 190 |
writeup of our goals and ideas. Obviously our first implementation will |
| 191 |
not want to do all of the stuff that I pointed out above... be we will |
| 192 |
want to design the project so that we do not artificially limit ourselves |
| 193 |
at sometime in the future... |
| 194 |
|
| 195 |
Anyways, let me know what you think about these ideas... and if they sound |
| 196 |
reasonable... |
| 197 |
|
| 198 |
-Chris |
| 199 |
|