| 1 |
From: Chris Lattner <[email protected]> |
| 2 |
To: "Vikram S. Adve" <[email protected]> |
| 3 |
Subject: Re: LLVM Feedback |
| 4 |
|
| 5 |
I've included your feedback in the /home/vadve/lattner/llvm/docs directory |
| 6 |
so that it will live in CVS eventually with the rest of LLVM. I've |
| 7 |
significantly updated the documentation to reflect the changes you |
| 8 |
suggested, as specified below: |
| 9 |
|
| 10 |
> We should consider eliminating the type annotation in cases where it is |
| 11 |
> essentially obvious from the instruction type: |
| 12 |
> br bool <cond>, label <iftrue>, label <iffalse> |
| 13 |
> I think your point was that making all types explicit improves clarity |
| 14 |
> and readability. I agree to some extent, but it also comes at the |
| 15 |
> cost of verbosity. And when the types are obvious from people's |
| 16 |
> experience (e.g., in the br instruction), it doesn't seem to help as |
| 17 |
> much. |
| 18 |
|
| 19 |
Very true. We should discuss this more, but my reasoning is more of a |
| 20 |
consistency argument. There are VERY few instructions that can have all |
| 21 |
of the types eliminated, and doing so when available unnecessarily makes |
| 22 |
the language more difficult to handle. Especially when you see 'int |
| 23 |
%this' and 'bool %that' all over the place, I think it would be |
| 24 |
disorienting to see: |
| 25 |
|
| 26 |
br %predicate, %iftrue, %iffalse |
| 27 |
|
| 28 |
for branches. Even just typing that once gives me the creeps. ;) Like I |
| 29 |
said, we should probably discuss this further in person... |
| 30 |
|
| 31 |
> On reflection, I really like your idea of having the two different |
| 32 |
> switch types (even though they encode implementation techniques rather |
| 33 |
> than semantics). It should simplify building the CFG and my guess is it |
| 34 |
> could enable some significant optimizations, though we should think |
| 35 |
> about which. |
| 36 |
|
| 37 |
Great. I added a note to the switch section commenting on how the VM |
| 38 |
should just use the instruction type as a hint, and that the |
| 39 |
implementation may choose altermate representations (such as predicated |
| 40 |
branches). |
| 41 |
|
| 42 |
> In the lookup-indirect form of the switch, is there a reason not to |
| 43 |
> make the val-type uint? |
| 44 |
|
| 45 |
No. This was something I was debating for a while, and didn't really feel |
| 46 |
strongly about either way. It is common to switch on other types in HLL's |
| 47 |
(for example signed int's are particularly common), but in this case, all |
| 48 |
that will be added is an additional 'cast' instruction. I removed that |
| 49 |
from the spec. |
| 50 |
|
| 51 |
> I agree with your comment that we don't need 'neg' |
| 52 |
|
| 53 |
Removed. |
| 54 |
|
| 55 |
> There's a trade-off with the cast instruction: |
| 56 |
> + it avoids having to define all the upcasts and downcasts that are |
| 57 |
> valid for the operands of each instruction (you probably have |
| 58 |
> thought of other benefits also) |
| 59 |
> - it could make the bytecode significantly larger because there could |
| 60 |
> be a lot of cast operations |
| 61 |
|
| 62 |
+ You NEED casts to represent things like: |
| 63 |
void foo(float); |
| 64 |
... |
| 65 |
int x; |
| 66 |
... |
| 67 |
foo(x); |
| 68 |
in a language like C. Even in a Java like language, you need upcasts |
| 69 |
and some way to implement dynamic downcasts. |
| 70 |
+ Not all forms of instructions take every type (for example you can't |
| 71 |
shift by a floating point number of bits), thus SOME programs will need |
| 72 |
implicit casts. |
| 73 |
|
| 74 |
To be efficient and to avoid your '-' point above, we just have to be |
| 75 |
careful to specify that the instructions shall operate on all common |
| 76 |
types, therefore casting should be relatively uncommon. For example all |
| 77 |
of the arithmetic operations work on almost all data types. |
| 78 |
|
| 79 |
> Making the second arg. to 'shl' a ubyte seems good enough to me. |
| 80 |
> 255 positions seems adequate for several generations of machines |
| 81 |
|
| 82 |
Okay, that comment is removed. |
| 83 |
|
| 84 |
> and is more compact than uint. |
| 85 |
|
| 86 |
No, it isn't. Remember that the bytecode encoding saves value slots into |
| 87 |
the bytecode instructions themselves, not constant values. This is |
| 88 |
another case where we may introduce more cast instructions (but we will |
| 89 |
also reduce the number of opcode variants that must be supported by a |
| 90 |
virtual machine). Because most shifts are by constant values, I don't |
| 91 |
think that we'll have to cast many shifts. :) |
| 92 |
|
| 93 |
> I still have some major concerns about including malloc and free in the |
| 94 |
> language (either as builtin functions or instructions). |
| 95 |
|
| 96 |
Agreed. How about this proposal: |
| 97 |
|
| 98 |
malloc/free are either built in functions or actual opcodes. They provide |
| 99 |
all of the type safety that the document would indicate, blah blah |
| 100 |
blah. :) |
| 101 |
|
| 102 |
Now, because of all of the excellent points that you raised, an |
| 103 |
implementation may want to override the default malloc/free behavior of |
| 104 |
the program. To do this, they simply implement a "malloc" and |
| 105 |
"free" function. The virtual machine will then be defined to use the user |
| 106 |
defined malloc/free function (which return/take void*'s, not type'd |
| 107 |
pointers like the builtin function would) if one is available, otherwise |
| 108 |
fall back on a system malloc/free. |
| 109 |
|
| 110 |
Does this sound like a good compromise? It would give us all of the |
| 111 |
typesafety/elegance in the language while still allowing the user to do |
| 112 |
all the cool stuff they want to... |
| 113 |
|
| 114 |
> 'alloca' on the other hand sounds like a good idea, and the |
| 115 |
> implementation seems fairly language-independent so it doesn't have the |
| 116 |
> problems with malloc listed above. |
| 117 |
|
| 118 |
Okay, once we get the above stuff figured out, I'll put it all in the |
| 119 |
spec. |
| 120 |
|
| 121 |
> About indirect call: |
| 122 |
> Your option #2 sounded good to me. I'm not sure I understand your |
| 123 |
> concern about an explicit 'icall' instruction? |
| 124 |
|
| 125 |
I worry too much. :) The other alternative has been removed. 'icall' is |
| 126 |
now up in the instruction list next to 'call'. |
| 127 |
|
| 128 |
> I believe tail calls are relatively easy to identify; do you know why |
| 129 |
> .NET has a tailcall instruction? |
| 130 |
|
| 131 |
Although I am just guessing, I believe it probably has to do with the fact |
| 132 |
that they want languages like Haskell and lisp to be efficiently runnable |
| 133 |
on their VM. Of course this means that the VM MUST implement tail calls |
| 134 |
'correctly', or else life will suck. :) I would put this into a future |
| 135 |
feature bin, because it could be pretty handy... |
| 136 |
|
| 137 |
> A pair of important synchronization instr'ns to think about: |
| 138 |
> load-linked |
| 139 |
> store-conditional |
| 140 |
|
| 141 |
What is 'load-linked'? I think that (at least for now) I should add these |
| 142 |
to the 'possible extensions' section, because they are not immediately |
| 143 |
needed... |
| 144 |
|
| 145 |
> Other classes of instructions that are valuable for pipeline |
| 146 |
> performance: |
| 147 |
> conditional-move |
| 148 |
> predicated instructions |
| 149 |
|
| 150 |
Conditional move is effectly a special case of a predicated |
| 151 |
instruction... and I think that all predicated instructions can possibly |
| 152 |
be implemented later in LLVM. It would significantly change things, and |
| 153 |
it doesn't seem to be very necessary right now. It would seem to |
| 154 |
complicate flow control analysis a LOT in the virtual machine. I would |
| 155 |
tend to prefer that a predicated architecture like IA64 convert from a |
| 156 |
"basic block" representation to a predicated rep as part of it's dynamic |
| 157 |
complication phase. Also, if a basic block contains ONLY a move, then |
| 158 |
that can be trivally translated into a conditional move... |
| 159 |
|
| 160 |
> I agree that we need a static data space. Otherwise, emulating global |
| 161 |
> data gets unnecessarily complex. |
| 162 |
|
| 163 |
Definitely. Also a later item though. :) |
| 164 |
|
| 165 |
> We once talked about adding a symbolic thread-id field to each |
| 166 |
> .. |
| 167 |
> Instead, it could a great topic for a separate study. |
| 168 |
|
| 169 |
Agreed. :) |
| 170 |
|
| 171 |
> What is the semantics of the IA64 stop bit? |
| 172 |
|
| 173 |
Basically, the IA64 writes instructions like this: |
| 174 |
mov ... |
| 175 |
add ... |
| 176 |
sub ... |
| 177 |
op xxx |
| 178 |
op xxx |
| 179 |
;; |
| 180 |
mov ... |
| 181 |
add ... |
| 182 |
sub ... |
| 183 |
op xxx |
| 184 |
op xxx |
| 185 |
;; |
| 186 |
|
| 187 |
Where the ;; delimits a group of instruction with no dependencies between |
| 188 |
them, which can all be executed concurrently (to the limits of the |
| 189 |
available functional units). The ;; gets translated into a bit set in one |
| 190 |
of the opcodes. |
| 191 |
|
| 192 |
The advantages of this representation is that you don't have to do some |
| 193 |
kind of 'thread id scheduling' pass by having to specify ahead of time how |
| 194 |
many threads to use, and the representation doesn't have a per instruction |
| 195 |
overhead... |
| 196 |
|
| 197 |
> And finally, another thought about the syntax for arrays :-) |
| 198 |
> Although this syntax: |
| 199 |
> array <dimension-list> of <type> |
| 200 |
> is verbose, it will be used only in the human-readable assembly code so |
| 201 |
> size should not matter. I think we should consider it because I find it |
| 202 |
> to be the clearest syntax. It could even make arrays of function |
| 203 |
> pointers somewhat readable. |
| 204 |
|
| 205 |
My only comment will be to give you an example of why this is a bad |
| 206 |
idea. :) |
| 207 |
|
| 208 |
Here is an example of using the switch statement (with my recommended |
| 209 |
syntax): |
| 210 |
|
| 211 |
switch uint %val, label %otherwise, |
| 212 |
[%3 x {uint, label}] [ { uint %57, label %l1 }, |
| 213 |
{ uint %20, label %l2 }, |
| 214 |
{ uint %14, label %l3 } ] |
| 215 |
|
| 216 |
Here it is with the syntax you are proposing: |
| 217 |
|
| 218 |
switch uint %val, label %otherwise, |
| 219 |
array %3 of {uint, label} |
| 220 |
array of {uint, label} |
| 221 |
{ uint %57, label %l1 }, |
| 222 |
{ uint %20, label %l2 }, |
| 223 |
{ uint %14, label %l3 } |
| 224 |
|
| 225 |
Which is ambiguous and very verbose. It would be possible to specify |
| 226 |
constants with [] brackets as in my syntax, which would look like this: |
| 227 |
|
| 228 |
switch uint %val, label %otherwise, |
| 229 |
array %3 of {uint, label} [ { uint %57, label %l1 }, |
| 230 |
{ uint %20, label %l2 }, |
| 231 |
{ uint %14, label %l3 } ] |
| 232 |
|
| 233 |
But then the syntax is inconsistent between type definition and constant |
| 234 |
definition (why do []'s enclose the constants but not the types??). |
| 235 |
|
| 236 |
Anyways, I'm sure that there is much debate still to be had over |
| 237 |
this... :) |
| 238 |
|
| 239 |
-Chris |
| 240 |
|
| 241 |
http://www.nondot.org/~sabre/os/ |
| 242 |
http://www.nondot.org/MagicStats/ |
| 243 |
http://korbit.sourceforge.net/ |
| 244 |
|
| 245 |
|