15016
|
1 /* |
|
2 |
|
3 Copyright (C) 2012 Max Brister <max@2bass.com> |
|
4 |
|
5 This file is part of Octave. |
|
6 |
|
7 Octave is free software; you can redistribute it and/or modify it |
|
8 under the terms of the GNU General Public License as published by the |
|
9 Free Software Foundation; either version 3 of the License, or (at your |
|
10 option) any later version. |
|
11 |
|
12 Octave is distributed in the hope that it will be useful, but WITHOUT |
|
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
|
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
|
15 for more details. |
|
16 |
|
17 You should have received a copy of the GNU General Public License |
|
18 along with Octave; see the file COPYING. If not, see |
|
19 <http://www.gnu.org/licenses/>. |
|
20 |
|
21 */ |
|
22 |
|
23 #if !defined (octave_jit_typeinfo_h) |
|
24 #define octave_jit_typeinfo_h 1 |
|
25 |
|
26 #ifdef HAVE_LLVM |
|
27 |
|
28 #include <map> |
|
29 #include <vector> |
|
30 |
|
31 #include "Range.h" |
|
32 #include "jit-util.h" |
|
33 |
|
34 // Defines the type system used by jit and a singleton class, jit_typeinfo, to |
|
35 // manage the types. |
|
36 // |
|
37 // FIXME: |
|
38 // Operations are defined and implemented in jit_typeinfo. Eventually they |
|
39 // should be moved elsewhere. (just like with octave_typeinfo) |
|
40 |
|
41 // jit_range is compatable with the llvm range structure |
|
42 struct |
|
43 jit_range |
|
44 { |
|
45 jit_range (const Range& from) : base (from.base ()), limit (from.limit ()), |
|
46 inc (from.inc ()), nelem (from.nelem ()) |
|
47 {} |
|
48 |
|
49 operator Range () const |
|
50 { |
|
51 return Range (base, limit, inc); |
|
52 } |
|
53 |
|
54 bool all_elements_are_ints () const; |
|
55 |
|
56 double base; |
|
57 double limit; |
|
58 double inc; |
|
59 octave_idx_type nelem; |
|
60 }; |
|
61 |
|
62 std::ostream& operator<< (std::ostream& os, const jit_range& rng); |
|
63 |
|
64 // jit_array is compatable with the llvm array/matrix structures |
|
65 template <typename T, typename U> |
|
66 struct |
|
67 jit_array |
|
68 { |
|
69 jit_array (T& from) : array (new T (from)) |
|
70 { |
|
71 update (); |
|
72 } |
|
73 |
|
74 void update (void) |
|
75 { |
|
76 ref_count = array->jit_ref_count (); |
|
77 slice_data = array->jit_slice_data () - 1; |
|
78 slice_len = array->capacity (); |
|
79 dimensions = array->jit_dimensions (); |
|
80 } |
|
81 |
|
82 void update (T *aarray) |
|
83 { |
|
84 array = aarray; |
|
85 update (); |
|
86 } |
|
87 |
|
88 operator T () const |
|
89 { |
|
90 return *array; |
|
91 } |
|
92 |
|
93 int *ref_count; |
|
94 |
|
95 U *slice_data; |
|
96 octave_idx_type slice_len; |
|
97 octave_idx_type *dimensions; |
|
98 |
|
99 T *array; |
|
100 }; |
|
101 |
|
102 typedef jit_array<NDArray, double> jit_matrix; |
|
103 |
|
104 std::ostream& operator<< (std::ostream& os, const jit_matrix& mat); |
|
105 |
|
106 // calling convention |
|
107 namespace |
|
108 jit_convention |
|
109 { |
|
110 enum |
|
111 type |
|
112 { |
|
113 // internal to jit |
|
114 internal, |
|
115 |
|
116 // an external C call |
|
117 external, |
|
118 |
|
119 length |
|
120 }; |
|
121 } |
|
122 |
|
123 // Used to keep track of estimated (infered) types during JIT. This is a |
|
124 // hierarchical type system which includes both concrete and abstract types. |
|
125 // |
|
126 // The types form a lattice. Currently we only allow for one parent type, but |
|
127 // eventually we may allow for multiple predecessors. |
|
128 class |
|
129 jit_type |
|
130 { |
|
131 public: |
|
132 typedef llvm::Value *(*convert_fn) (llvm::IRBuilderD&, llvm::Value *); |
|
133 |
|
134 jit_type (const std::string& aname, jit_type *aparent, llvm::Type *allvm_type, |
|
135 int aid); |
|
136 |
|
137 // a user readable type name |
|
138 const std::string& name (void) const { return mname; } |
|
139 |
|
140 // a unique id for the type |
|
141 int type_id (void) const { return mid; } |
|
142 |
|
143 // An abstract base type, may be null |
|
144 jit_type *parent (void) const { return mparent; } |
|
145 |
|
146 // convert to an llvm type |
|
147 llvm::Type *to_llvm (void) const { return llvm_type; } |
|
148 |
|
149 // how this type gets passed as a function argument |
|
150 llvm::Type *to_llvm_arg (void) const; |
|
151 |
|
152 size_t depth (void) const { return mdepth; } |
|
153 |
|
154 // -------------------- Calling Convention information -------------------- |
|
155 |
|
156 // A function declared like: mytype foo (int arg0, int arg1); |
|
157 // Will be converted to: void foo (mytype *retval, int arg0, int arg1) |
|
158 // if mytype is sret. The caller is responsible for allocating space for |
|
159 // retval. (on the stack) |
|
160 bool sret (jit_convention::type cc) const { return msret[cc]; } |
|
161 |
|
162 void mark_sret (jit_convention::type cc = jit_convention::external) |
|
163 { msret[cc] = true; } |
|
164 |
|
165 // A function like: void foo (mytype arg0) |
|
166 // Will be converted to: void foo (mytype *arg0) |
|
167 // Basically just pass by reference. |
|
168 bool pointer_arg (jit_convention::type cc) const { return mpointer_arg[cc]; } |
|
169 |
|
170 void mark_pointer_arg (jit_convention::type cc = jit_convention::external) |
|
171 { mpointer_arg[cc] = true; } |
|
172 |
|
173 // Convert into an equivalent form before calling. For example, complex is |
|
174 // represented as two values llvm vector, but we need to pass it as a two |
|
175 // valued llvm structure to C functions. |
|
176 convert_fn pack (jit_convention::type cc) { return mpack[cc]; } |
|
177 |
|
178 void set_pack (jit_convention::type cc, convert_fn fn) { mpack[cc] = fn; } |
|
179 |
|
180 // The inverse operation of pack. |
|
181 convert_fn unpack (jit_convention::type cc) { return munpack[cc]; } |
|
182 |
|
183 void set_unpack (jit_convention::type cc, convert_fn fn) |
|
184 { munpack[cc] = fn; } |
|
185 |
|
186 // The resulting type after pack is called. |
|
187 llvm::Type *packed_type (jit_convention::type cc) |
|
188 { return mpacked_type[cc]; } |
|
189 |
|
190 void set_packed_type (jit_convention::type cc, llvm::Type *ty) |
|
191 { mpacked_type[cc] = ty; } |
|
192 private: |
|
193 std::string mname; |
|
194 jit_type *mparent; |
|
195 llvm::Type *llvm_type; |
|
196 int mid; |
|
197 size_t mdepth; |
|
198 |
|
199 bool msret[jit_convention::length]; |
|
200 bool mpointer_arg[jit_convention::length]; |
|
201 |
|
202 convert_fn mpack[jit_convention::length]; |
|
203 convert_fn munpack[jit_convention::length]; |
|
204 |
|
205 llvm::Type *mpacked_type[jit_convention::length]; |
|
206 }; |
|
207 |
|
208 // seperate print function to allow easy printing if type is null |
|
209 std::ostream& jit_print (std::ostream& os, jit_type *atype); |
|
210 |
|
211 class jit_value; |
|
212 |
|
213 // An abstraction for calling llvm functions with jit_values. Deals with calling |
|
214 // convention details. |
|
215 class |
|
216 jit_function |
|
217 { |
|
218 friend std::ostream& operator<< (std::ostream& os, const jit_function& fn); |
|
219 public: |
|
220 // create a function in an invalid state |
|
221 jit_function (); |
|
222 |
|
223 jit_function (llvm::Module *amodule, jit_convention::type acall_conv, |
|
224 const llvm::Twine& aname, jit_type *aresult, |
|
225 const std::vector<jit_type *>& aargs); |
|
226 |
|
227 // Use an existing function, but change the argument types. The new argument |
|
228 // types must behave the same for the current calling convention. |
|
229 jit_function (const jit_function& fn, jit_type *aresult, |
|
230 const std::vector<jit_type *>& aargs); |
|
231 |
|
232 jit_function (const jit_function& fn); |
|
233 |
|
234 bool valid (void) const { return llvm_function; } |
|
235 |
|
236 std::string name (void) const; |
|
237 |
|
238 llvm::BasicBlock *new_block (const std::string& aname = "body", |
|
239 llvm::BasicBlock *insert_before = 0); |
|
240 |
|
241 llvm::Value *call (llvm::IRBuilderD& builder, |
|
242 const std::vector<jit_value *>& in_args) const; |
|
243 |
|
244 llvm::Value *call (llvm::IRBuilderD& builder, |
|
245 const std::vector<llvm::Value *>& in_args |
|
246 = std::vector<llvm::Value *> ()) const; |
|
247 |
|
248 #define JIT_PARAM_ARGS llvm::IRBuilderD& builder, |
|
249 #define JIT_PARAMS builder, |
|
250 #define JIT_CALL(N) JIT_EXPAND (llvm::Value *, call, llvm::Value *, const, N) |
|
251 |
|
252 JIT_CALL (1) |
|
253 JIT_CALL (2) |
|
254 JIT_CALL (3) |
|
255 JIT_CALL (4) |
|
256 JIT_CALL (5) |
|
257 |
|
258 #undef JIT_CALL |
|
259 |
|
260 #define JIT_CALL(N) JIT_EXPAND (llvm::Value *, call, jit_value *, const, N) |
|
261 |
|
262 JIT_CALL (1); |
|
263 JIT_CALL (2); |
|
264 |
|
265 #undef JIT_CALL |
|
266 #undef JIT_PARAMS |
|
267 #undef JIT_PARAM_ARGS |
|
268 |
|
269 llvm::Value *argument (llvm::IRBuilderD& builder, size_t idx) const; |
|
270 |
|
271 void do_return (llvm::IRBuilderD& builder, llvm::Value *rval = 0); |
|
272 |
|
273 llvm::Function *to_llvm (void) const { return llvm_function; } |
|
274 |
|
275 // If true, then the return value is passed as a pointer in the first argument |
|
276 bool sret (void) const { return mresult && mresult->sret (call_conv); } |
|
277 |
|
278 bool can_error (void) const { return mcan_error; } |
|
279 |
|
280 void mark_can_error (void) { mcan_error = true; } |
|
281 |
|
282 jit_type *result (void) const { return mresult; } |
|
283 |
|
284 jit_type *argument_type (size_t idx) const |
|
285 { |
|
286 assert (idx < args.size ()); |
|
287 return args[idx]; |
|
288 } |
|
289 |
|
290 const std::vector<jit_type *>& arguments (void) const { return args; } |
|
291 private: |
|
292 llvm::Module *module; |
|
293 llvm::Function *llvm_function; |
|
294 jit_type *mresult; |
|
295 std::vector<jit_type *> args; |
|
296 jit_convention::type call_conv; |
|
297 bool mcan_error; |
|
298 }; |
|
299 |
|
300 std::ostream& operator<< (std::ostream& os, const jit_function& fn); |
|
301 |
|
302 |
|
303 // Keeps track of information about how to implement operations (+, -, *, ect) |
|
304 // and their resulting types. |
|
305 class |
|
306 jit_operation |
|
307 { |
|
308 public: |
|
309 void add_overload (const jit_function& func) |
|
310 { |
|
311 add_overload (func, func.arguments ()); |
|
312 } |
|
313 |
|
314 void add_overload (const jit_function& func, |
|
315 const std::vector<jit_type*>& args); |
|
316 |
|
317 const jit_function& overload (const std::vector<jit_type *>& types) const; |
|
318 |
|
319 jit_type *result (const std::vector<jit_type *>& types) const |
|
320 { |
|
321 const jit_function& temp = overload (types); |
|
322 return temp.result (); |
|
323 } |
|
324 |
|
325 #define JIT_PARAMS |
|
326 #define JIT_PARAM_ARGS |
|
327 #define JIT_OVERLOAD(N) \ |
|
328 JIT_EXPAND (const jit_function&, overload, jit_type *, const, N) \ |
|
329 JIT_EXPAND (jit_type *, result, jit_type *, const, N) |
|
330 |
|
331 JIT_OVERLOAD (1); |
|
332 JIT_OVERLOAD (2); |
|
333 JIT_OVERLOAD (3); |
|
334 |
|
335 #undef JIT_PARAMS |
|
336 #undef JIT_PARAM_ARGS |
|
337 |
|
338 const std::string& name (void) const { return mname; } |
|
339 |
|
340 void stash_name (const std::string& aname) { mname = aname; } |
|
341 private: |
|
342 Array<octave_idx_type> to_idx (const std::vector<jit_type*>& types) const; |
|
343 |
|
344 std::vector<Array<jit_function> > overloads; |
|
345 |
|
346 std::string mname; |
|
347 }; |
|
348 |
|
349 // A singleton class which handles the construction of jit_types and |
|
350 // jit_operations. |
|
351 class |
|
352 jit_typeinfo |
|
353 { |
|
354 public: |
|
355 static void initialize (llvm::Module *m, llvm::ExecutionEngine *e); |
|
356 |
|
357 static jit_type *join (jit_type *lhs, jit_type *rhs) |
|
358 { |
|
359 return instance->do_join (lhs, rhs); |
|
360 } |
|
361 |
|
362 static jit_type *get_any (void) { return instance->any; } |
|
363 |
|
364 static jit_type *get_matrix (void) { return instance->matrix; } |
|
365 |
|
366 static jit_type *get_scalar (void) { return instance->scalar; } |
|
367 |
|
368 static llvm::Type *get_scalar_llvm (void) |
|
369 { return instance->scalar->to_llvm (); } |
|
370 |
|
371 static jit_type *get_range (void) { return instance->range; } |
|
372 |
|
373 static jit_type *get_string (void) { return instance->string; } |
|
374 |
|
375 static jit_type *get_bool (void) { return instance->boolean; } |
|
376 |
|
377 static jit_type *get_index (void) { return instance->index; } |
|
378 |
|
379 static llvm::Type *get_index_llvm (void) |
|
380 { return instance->index->to_llvm (); } |
|
381 |
|
382 static jit_type *get_complex (void) { return instance->complex; } |
|
383 |
|
384 // Get the jit_type of an octave_value |
|
385 static jit_type *type_of (const octave_value& ov) |
|
386 { |
|
387 return instance->do_type_of (ov); |
|
388 } |
|
389 |
|
390 static const jit_operation& binary_op (int op) |
|
391 { |
|
392 return instance->do_binary_op (op); |
|
393 } |
|
394 |
|
395 static const jit_operation& grab (void) { return instance->grab_fn; } |
|
396 |
|
397 static const jit_function& get_grab (jit_type *type) |
|
398 { |
|
399 return instance->grab_fn.overload (type); |
|
400 } |
|
401 |
|
402 static const jit_operation& release (void) |
|
403 { |
|
404 return instance->release_fn; |
|
405 } |
|
406 |
|
407 static const jit_function& get_release (jit_type *type) |
|
408 { |
|
409 return instance->release_fn.overload (type); |
|
410 } |
|
411 |
|
412 static const jit_operation& print_value (void) |
|
413 { |
|
414 return instance->print_fn; |
|
415 } |
|
416 |
|
417 static const jit_operation& for_init (void) |
|
418 { |
|
419 return instance->for_init_fn; |
|
420 } |
|
421 |
|
422 static const jit_operation& for_check (void) |
|
423 { |
|
424 return instance->for_check_fn; |
|
425 } |
|
426 |
|
427 static const jit_operation& for_index (void) |
|
428 { |
|
429 return instance->for_index_fn; |
|
430 } |
|
431 |
|
432 static const jit_operation& make_range (void) |
|
433 { |
|
434 return instance->make_range_fn; |
|
435 } |
|
436 |
|
437 static const jit_operation& paren_subsref (void) |
|
438 { |
|
439 return instance->paren_subsref_fn; |
|
440 } |
|
441 |
|
442 static const jit_operation& paren_subsasgn (void) |
|
443 { |
|
444 return instance->paren_subsasgn_fn; |
|
445 } |
|
446 |
|
447 static const jit_operation& logically_true (void) |
|
448 { |
|
449 return instance->logically_true_fn; |
|
450 } |
|
451 |
|
452 static const jit_operation& cast (jit_type *result) |
|
453 { |
|
454 return instance->do_cast (result); |
|
455 } |
|
456 |
|
457 static const jit_function& cast (jit_type *to, jit_type *from) |
|
458 { |
|
459 return instance->do_cast (to, from); |
|
460 } |
|
461 |
|
462 static llvm::Value *insert_error_check (llvm::IRBuilderD& bld) |
|
463 { |
|
464 return instance->do_insert_error_check (bld); |
|
465 } |
|
466 private: |
|
467 jit_typeinfo (llvm::Module *m, llvm::ExecutionEngine *e); |
|
468 |
|
469 // FIXME: Do these methods really need to be in jit_typeinfo? |
|
470 jit_type *do_join (jit_type *lhs, jit_type *rhs) |
|
471 { |
|
472 // empty case |
|
473 if (! lhs) |
|
474 return rhs; |
|
475 |
|
476 if (! rhs) |
|
477 return lhs; |
|
478 |
|
479 // check for a shared parent |
|
480 while (lhs != rhs) |
|
481 { |
|
482 if (lhs->depth () > rhs->depth ()) |
|
483 lhs = lhs->parent (); |
|
484 else if (lhs->depth () < rhs->depth ()) |
|
485 rhs = rhs->parent (); |
|
486 else |
|
487 { |
|
488 // we MUST have depth > 0 as any is the base type of everything |
|
489 do |
|
490 { |
|
491 lhs = lhs->parent (); |
|
492 rhs = rhs->parent (); |
|
493 } |
|
494 while (lhs != rhs); |
|
495 } |
|
496 } |
|
497 |
|
498 return lhs; |
|
499 } |
|
500 |
|
501 jit_type *do_difference (jit_type *lhs, jit_type *) |
|
502 { |
|
503 // FIXME: Maybe we can do something smarter? |
|
504 return lhs; |
|
505 } |
|
506 |
|
507 jit_type *do_type_of (const octave_value &ov) const; |
|
508 |
|
509 const jit_operation& do_binary_op (int op) const |
|
510 { |
|
511 assert (static_cast<size_t>(op) < binary_ops.size ()); |
|
512 return binary_ops[op]; |
|
513 } |
|
514 |
|
515 const jit_operation& do_cast (jit_type *to) |
|
516 { |
|
517 static jit_operation null_function; |
|
518 if (! to) |
|
519 return null_function; |
|
520 |
|
521 size_t id = to->type_id (); |
|
522 if (id >= casts.size ()) |
|
523 return null_function; |
|
524 return casts[id]; |
|
525 } |
|
526 |
|
527 const jit_function& do_cast (jit_type *to, jit_type *from) |
|
528 { |
|
529 return do_cast (to).overload (from); |
|
530 } |
|
531 |
|
532 jit_type *new_type (const std::string& name, jit_type *parent, |
|
533 llvm::Type *llvm_type); |
|
534 |
|
535 |
|
536 void add_print (jit_type *ty); |
|
537 |
|
538 void add_binary_op (jit_type *ty, int op, int llvm_op); |
|
539 |
|
540 void add_binary_icmp (jit_type *ty, int op, int llvm_op); |
|
541 |
|
542 void add_binary_fcmp (jit_type *ty, int op, int llvm_op); |
|
543 |
|
544 jit_function create_function (jit_convention::type cc, |
|
545 const llvm::Twine& name, jit_type *ret, |
|
546 const std::vector<jit_type *>& args |
|
547 = std::vector<jit_type *> ()); |
|
548 |
|
549 #define JIT_PARAM_ARGS jit_convention::type cc, const llvm::Twine& name, \ |
|
550 jit_type *ret, |
|
551 #define JIT_PARAMS cc, name, ret, |
|
552 #define CREATE_FUNCTION(N) JIT_EXPAND(jit_function, create_function, \ |
|
553 jit_type *, /* empty */, N) |
|
554 |
|
555 CREATE_FUNCTION(1); |
|
556 CREATE_FUNCTION(2); |
|
557 CREATE_FUNCTION(3); |
|
558 CREATE_FUNCTION(4); |
|
559 |
|
560 #undef JIT_PARAM_ARGS |
|
561 #undef JIT_PARAMS |
|
562 #undef CREATE_FUNCTION |
|
563 |
|
564 jit_function create_identity (jit_type *type); |
|
565 |
|
566 llvm::Value *do_insert_error_check (llvm::IRBuilderD& bld); |
|
567 |
|
568 void add_builtin (const std::string& name); |
|
569 |
|
570 void register_intrinsic (const std::string& name, size_t id, |
|
571 jit_type *result, jit_type *arg0) |
|
572 { |
|
573 std::vector<jit_type *> args (1, arg0); |
|
574 register_intrinsic (name, id, result, args); |
|
575 } |
|
576 |
|
577 void register_intrinsic (const std::string& name, size_t id, jit_type *result, |
|
578 const std::vector<jit_type *>& args); |
|
579 |
|
580 void register_generic (const std::string& name, jit_type *result, |
|
581 jit_type *arg0) |
|
582 { |
|
583 std::vector<jit_type *> args (1, arg0); |
|
584 register_generic (name, result, args); |
|
585 } |
|
586 |
|
587 void register_generic (const std::string& name, jit_type *result, |
|
588 const std::vector<jit_type *>& args); |
|
589 |
|
590 octave_builtin *find_builtin (const std::string& name); |
|
591 |
|
592 jit_function mirror_binary (const jit_function& fn); |
|
593 |
|
594 llvm::Function *wrap_complex (llvm::Function *wrap); |
|
595 |
|
596 static llvm::Value *pack_complex (llvm::IRBuilderD& bld, |
|
597 llvm::Value *cplx); |
|
598 |
|
599 static llvm::Value *unpack_complex (llvm::IRBuilderD& bld, |
|
600 llvm::Value *result); |
|
601 |
|
602 llvm::Value *complex_real (llvm::Value *cx); |
|
603 |
|
604 llvm::Value *complex_real (llvm::Value *cx, llvm::Value *real); |
|
605 |
|
606 llvm::Value *complex_imag (llvm::Value *cx); |
|
607 |
|
608 llvm::Value *complex_imag (llvm::Value *cx, llvm::Value *imag); |
|
609 |
|
610 llvm::Value *complex_new (llvm::Value *real, llvm::Value *imag); |
|
611 |
|
612 void create_int (size_t nbits); |
|
613 |
|
614 jit_type *intN (size_t nbits) const; |
|
615 |
|
616 static jit_typeinfo *instance; |
|
617 |
|
618 llvm::Module *module; |
|
619 llvm::ExecutionEngine *engine; |
|
620 int next_id; |
|
621 |
|
622 llvm::GlobalVariable *lerror_state; |
|
623 |
|
624 std::vector<jit_type*> id_to_type; |
|
625 jit_type *any; |
|
626 jit_type *matrix; |
|
627 jit_type *scalar; |
|
628 jit_type *range; |
|
629 jit_type *string; |
|
630 jit_type *boolean; |
|
631 jit_type *index; |
|
632 jit_type *complex; |
|
633 jit_type *unknown_function; |
|
634 std::map<size_t, jit_type *> ints; |
|
635 std::map<std::string, jit_type *> builtins; |
|
636 |
|
637 llvm::StructType *complex_ret; |
|
638 |
|
639 std::vector<jit_operation> binary_ops; |
|
640 jit_operation grab_fn; |
|
641 jit_operation release_fn; |
|
642 jit_operation print_fn; |
|
643 jit_operation for_init_fn; |
|
644 jit_operation for_check_fn; |
|
645 jit_operation for_index_fn; |
|
646 jit_operation logically_true_fn; |
|
647 jit_operation make_range_fn; |
|
648 jit_operation paren_subsref_fn; |
|
649 jit_operation paren_subsasgn_fn; |
|
650 |
|
651 // type id -> cast function TO that type |
|
652 std::vector<jit_operation> casts; |
|
653 |
|
654 // type id -> identity function |
|
655 std::vector<jit_function> identities; |
|
656 |
|
657 llvm::IRBuilderD& builder; |
|
658 }; |
|
659 |
|
660 #endif |
|
661 #endif |