• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1From: Chris Lattner <sabre@nondot.org>
2To: "Vikram S. Adve" <vadve@cs.uiuc.edu>
3Subject: Re: LLVM Feedback
4
5I've included your feedback in the /home/vadve/lattner/llvm/docs directory
6so that it will live in CVS eventually with the rest of LLVM.  I've
7significantly updated the documentation to reflect the changes you
8suggested, 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
19Very true.  We should discuss this more, but my reasoning is more of a
20consistency argument.  There are VERY few instructions that can have all
21of the types eliminated, and doing so when available unnecessarily makes
22the language more difficult to handle.  Especially when you see 'int
23%this' and 'bool %that' all over the place, I think it would be
24disorienting to see:
25
26  br %predicate, %iftrue, %iffalse
27
28for branches.  Even just typing that once gives me the creeps. ;)  Like I
29said, 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
37Great.  I added a note to the switch section commenting on how the VM
38should just use the instruction type as a hint, and that the
39implementation may choose altermate representations (such as predicated
40branches).
41
42> In the lookup-indirect form of the switch, is there a reason not to
43> make the val-type uint?
44
45No.  This was something I was debating for a while, and didn't really feel
46strongly 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
48that will be added is an additional 'cast' instruction.  I removed that
49from the spec.
50
51> I agree with your comment that we don't need 'neg'
52
53Removed.
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
74To be efficient and to avoid your '-' point above, we just have to be
75careful to specify that the instructions shall operate on all common
76types, therefore casting should be relatively uncommon.  For example all
77of 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
82Okay, that comment is removed.
83
84> and is more compact than uint.
85
86No, it isn't.  Remember that the bytecode encoding saves value slots into
87the bytecode instructions themselves, not constant values.  This is
88another case where we may introduce more cast instructions (but we will
89also reduce the number of opcode variants that must be supported by a
90virtual machine).  Because most shifts are by constant values, I don't
91think 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
96Agreed.  How about this proposal:
97
98malloc/free are either built in functions or actual opcodes.  They provide
99all of the type safety that the document would indicate, blah blah
100blah. :)
101
102Now, because of all of the excellent points that you raised, an
103implementation may want to override the default malloc/free behavior of
104the program.  To do this, they simply implement a "malloc" and
105"free" function.  The virtual machine will then be defined to use the user
106defined malloc/free function (which return/take void*'s, not type'd
107pointers like the builtin function would) if one is available, otherwise
108fall back on a system malloc/free.
109
110Does this sound like a good compromise?  It would give us all of the
111typesafety/elegance in the language while still allowing the user to do
112all 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
118Okay, once we get the above stuff figured out, I'll put it all in the
119spec.
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
125I worry too much.  :)  The other alternative has been removed. 'icall' is
126now 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
131Although I am just guessing, I believe it probably has to do with the fact
132that they want languages like Haskell and lisp to be efficiently runnable
133on 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
135feature 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
141What is 'load-linked'?  I think that (at least for now) I should add these
142to the 'possible extensions' section, because they are not immediately
143needed...
144
145> Other classes of instructions that are valuable for pipeline
146> performance:
147>    conditional-move
148>    predicated instructions
149
150Conditional move is effectly a special case of a predicated
151instruction... and I think that all predicated instructions can possibly
152be implemented later in LLVM.  It would significantly change things, and
153it doesn't seem to be very necessary right now.  It would seem to
154complicate flow control analysis a LOT in the virtual machine.  I would
155tend 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
157complication phase.  Also, if a basic block contains ONLY a move, then
158that 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
163Definitely.  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
169Agreed.  :)
170
171> What is the semantics of the IA64 stop bit?
172
173Basically, the IA64 writes instructions like this:
174mov ...
175add ...
176sub ...
177op xxx
178op xxx
179;;
180mov ...
181add ...
182sub ...
183op xxx
184op xxx
185;;
186
187Where the ;; delimits a group of instruction with no dependencies between
188them, which can all be executed concurrently (to the limits of the
189available functional units).  The ;; gets translated into a bit set in one
190of the opcodes.
191
192The advantages of this representation is that you don't have to do some
193kind of 'thread id scheduling' pass by having to specify ahead of time how
194many threads to use, and the representation doesn't have a per instruction
195overhead...
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
205My only comment will be to give you an example of why this is a bad
206idea.  :)
207
208Here is an example of using the switch statement (with my recommended
209syntax):
210
211switch uint %val, label %otherwise,
212       [%3 x {uint, label}] [ { uint %57, label %l1 },
213                              { uint %20, label %l2 },
214                              { uint %14, label %l3 } ]
215
216Here it is with the syntax you are proposing:
217
218switch 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
225Which is ambiguous and very verbose. It would be possible to specify
226constants with [] brackets as in my syntax, which would look like this:
227
228switch 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
233But then the syntax is inconsistent between type definition and constant
234definition (why do []'s enclose the constants but not the types??).
235
236Anyways, I'm sure that there is much debate still to be had over
237this... :)
238
239-Chris
240
241http://www.nondot.org/~sabre/os/
242http://www.nondot.org/MagicStats/
243http://korbit.sourceforge.net/
244
245
246