GNU Octave  3.8.0
A high-level interpreted language, primarily intended for numerical computations, mostly compatible with Matlab
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Pages
jit-typeinfo.h
Go to the documentation of this file.
1 /*
2 
3 Copyright (C) 2012-2013 Max Brister
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 // Author: Max Brister <max@2bass.com>
24 
25 #if !defined (octave_jit_typeinfo_h)
26 #define octave_jit_typeinfo_h 1
27 
28 #ifdef HAVE_LLVM
29 
30 #include <map>
31 #include <vector>
32 
33 #include "Range.h"
34 #include "jit-util.h"
35 
36 // Defines the type system used by jit and a singleton class, jit_typeinfo, to
37 // manage the types.
38 //
39 // FIXME:
40 // Operations are defined and implemented in jit_typeinfo. Eventually they
41 // should be moved elsewhere. (just like with octave_typeinfo)
42 
43 // jit_range is compatable with the llvm range structure
44 struct
46 {
47  jit_range (const Range& from) : base (from.base ()), limit (from.limit ()),
48  inc (from.inc ()), nelem (from.nelem ())
49  { }
50 
51  operator Range () const
52  {
53  return Range (base, limit, inc);
54  }
55 
56  bool all_elements_are_ints () const;
57 
58  double base;
59  double limit;
60  double inc;
62 };
63 
64 std::ostream& operator << (std::ostream& os, const jit_range& rng);
65 
66 // jit_array is compatable with the llvm array/matrix structures
67 template <typename T, typename U>
68 struct
70 {
71  jit_array () : array (0) { }
72 
73  jit_array (T& from) : array (new T (from))
74  {
75  update ();
76  }
77 
78  void update (void)
79  {
80  ref_count = array->jit_ref_count ();
81  slice_data = array->jit_slice_data () - 1;
82  slice_len = array->capacity ();
83  dimensions = array->jit_dimensions ();
84  }
85 
86  void update (T *aarray)
87  {
88  array = aarray;
89  update ();
90  }
91 
92  operator T () const
93  {
94  return *array;
95  }
96 
97  int *ref_count;
98 
102 
103  T *array;
104 };
105 
107 
108 std::ostream& operator << (std::ostream& os, const jit_matrix& mat);
109 
110 // calling convention
111 namespace
112 jit_convention
113 {
114  enum
115  type
116  {
117  // internal to jit
118  internal,
119 
120  // an external C call
122 
124  };
125 }
126 
127 // Used to keep track of estimated (infered) types during JIT. This is a
128 // hierarchical type system which includes both concrete and abstract types.
129 //
130 // The types form a lattice. Currently we only allow for one parent type, but
131 // eventually we may allow for multiple predecessors.
132 class
133 jit_type
134 {
135 public:
136  typedef llvm::Value *(*convert_fn) (llvm::IRBuilderD&, llvm::Value *);
137 
138  jit_type (const std::string& aname, jit_type *aparent, llvm::Type *allvm_type,
139  bool askip_paren, int aid);
140 
141  // a user readable type name
142  const std::string& name (void) const { return mname; }
143 
144  // a unique id for the type
145  int type_id (void) const { return mid; }
146 
147  // An abstract base type, may be null
148  jit_type *parent (void) const { return mparent; }
149 
150  // convert to an llvm type
151  llvm::Type *to_llvm (void) const { return llvm_type; }
152 
153  // how this type gets passed as a function argument
154  llvm::Type *to_llvm_arg (void) const;
155 
156  size_t depth (void) const { return mdepth; }
157 
158  bool skip_paren (void) const { return mskip_paren; }
159 
160  // -------------------- Calling Convention information --------------------
161 
162  // A function declared like: mytype foo (int arg0, int arg1);
163  // Will be converted to: void foo (mytype *retval, int arg0, int arg1)
164  // if mytype is sret. The caller is responsible for allocating space for
165  // retval. (on the stack)
166  bool sret (jit_convention::type cc) const { return msret[cc]; }
167 
168  void mark_sret (jit_convention::type cc)
169  { msret[cc] = true; }
170 
171  // A function like: void foo (mytype arg0)
172  // Will be converted to: void foo (mytype *arg0)
173  // Basically just pass by reference.
174  bool pointer_arg (jit_convention::type cc) const { return mpointer_arg[cc]; }
175 
176  void mark_pointer_arg (jit_convention::type cc)
177  { mpointer_arg[cc] = true; }
178 
179  // Convert into an equivalent form before calling. For example, complex is
180  // represented as two values llvm vector, but we need to pass it as a two
181  // valued llvm structure to C functions.
182  convert_fn pack (jit_convention::type cc) { return mpack[cc]; }
183 
184  void set_pack (jit_convention::type cc, convert_fn fn) { mpack[cc] = fn; }
185 
186  // The inverse operation of pack.
187  convert_fn unpack (jit_convention::type cc) { return munpack[cc]; }
188 
189  void set_unpack (jit_convention::type cc, convert_fn fn)
190  { munpack[cc] = fn; }
191 
192  // The resulting type after pack is called.
193  llvm::Type *packed_type (jit_convention::type cc)
194  { return mpacked_type[cc]; }
195 
196  void set_packed_type (jit_convention::type cc, llvm::Type *ty)
197  { mpacked_type[cc] = ty; }
198 private:
199  std::string mname;
201  llvm::Type *llvm_type;
202  int mid;
203  size_t mdepth;
205 
207  bool mpointer_arg[jit_convention::length];
208 
209  convert_fn mpack[jit_convention::length];
210  convert_fn munpack[jit_convention::length];
211 
212  llvm::Type *mpacked_type[jit_convention::length];
213 };
214 
215 // seperate print function to allow easy printing if type is null
216 std::ostream& jit_print (std::ostream& os, jit_type *atype);
217 
218 class jit_value;
219 
220 // An abstraction for calling llvm functions with jit_values. Deals with
221 // calling convention details.
222 class
224 {
225  friend std::ostream& operator << (std::ostream& os, const jit_function& fn);
226 public:
227  // create a function in an invalid state
228  jit_function ();
229 
230  jit_function (llvm::Module *amodule, jit_convention::type acall_conv,
231  const llvm::Twine& aname, jit_type *aresult,
232  const std::vector<jit_type *>& aargs);
233 
234  // Use an existing function, but change the argument types. The new argument
235  // types must behave the same for the current calling convention.
236  jit_function (const jit_function& fn, jit_type *aresult,
237  const std::vector<jit_type *>& aargs);
238 
239  jit_function (const jit_function& fn);
240 
241  // erase the interal LLVM function (if it exists). Will become invalid.
242  void erase (void);
243 
244  template <typename T>
245  void add_mapping (llvm::ExecutionEngine *engine, T fn)
246  {
247  do_add_mapping (engine, reinterpret_cast<void *> (fn));
248  }
249 
250  bool valid (void) const { return llvm_function; }
251 
252  std::string name (void) const;
253 
254  llvm::BasicBlock *new_block (const std::string& aname = "body",
255  llvm::BasicBlock *insert_before = 0);
256 
257  llvm::Value *call (llvm::IRBuilderD& builder,
258  const std::vector<jit_value *>& in_args) const;
259 
260  llvm::Value *call (llvm::IRBuilderD& builder,
261  const std::vector<llvm::Value *>& in_args
262  = std::vector<llvm::Value *> ()) const;
263 
264 #define JIT_PARAM_ARGS llvm::IRBuilderD& builder,
265 #define JIT_PARAMS builder,
266 #define JIT_CALL(N) JIT_EXPAND (llvm::Value *, call, llvm::Value *, const, N)
267 
273 
274 #undef JIT_CALL
275 
276 #define JIT_CALL(N) JIT_EXPAND (llvm::Value *, call, jit_value *, const, N)
277 
278  JIT_CALL (1);
279  JIT_CALL (2);
280  JIT_CALL (3);
281 
282 #undef JIT_CALL
283 #undef JIT_PARAMS
284 #undef JIT_PARAM_ARGS
285 
286  llvm::Value *argument (llvm::IRBuilderD& builder, size_t idx) const;
287 
288  void do_return (llvm::IRBuilderD& builder, llvm::Value *rval = 0,
289  bool verify = true);
290 
291  llvm::Function *to_llvm (void) const { return llvm_function; }
292 
293  // If true, then the return value is passed as a pointer in the first argument
294  bool sret (void) const { return mresult && mresult->sret (call_conv); }
295 
296  bool can_error (void) const { return mcan_error; }
297 
298  void mark_can_error (void) { mcan_error = true; }
299 
300  jit_type *result (void) const { return mresult; }
301 
302  jit_type *argument_type (size_t idx) const
303  {
304  assert (idx < args.size ());
305  return args[idx];
306  }
307 
308  const std::vector<jit_type *>& arguments (void) const { return args; }
309 private:
310  void do_add_mapping (llvm::ExecutionEngine *engine, void *fn);
311 
312  llvm::Module *module;
313  llvm::Function *llvm_function;
315  std::vector<jit_type *> args;
318 };
319 
320 std::ostream& operator << (std::ostream& os, const jit_function& fn);
321 
322 
323 // Keeps track of information about how to implement operations (+, -, *, ect)
324 // and their resulting types.
325 class
327 {
328 public:
329  // type signature vector
330  typedef std::vector<jit_type *> signature_vec;
331 
332  virtual ~jit_operation (void);
333 
334  void add_overload (const jit_function& func)
335  {
336  add_overload (func, func.arguments ());
337  }
338 
339  void add_overload (const jit_function& func,
340  const signature_vec& args);
341 
342  const jit_function& overload (const signature_vec& types) const;
343 
344  jit_type *result (const signature_vec& types) const
345  {
346  const jit_function& temp = overload (types);
347  return temp.result ();
348  }
349 
350 #define JIT_PARAMS
351 #define JIT_PARAM_ARGS
352 #define JIT_OVERLOAD(N) \
353  JIT_EXPAND (const jit_function&, overload, jit_type *, const, N) \
354  JIT_EXPAND (jit_type *, result, jit_type *, const, N)
355 
359 
360 #undef JIT_PARAMS
361 #undef JIT_PARAM_ARGS
362 
363  const std::string& name (void) const { return mname; }
364 
365  void stash_name (const std::string& aname) { mname = aname; }
366 protected:
367  virtual jit_function *generate (const signature_vec& types) const;
368 private:
369  Array<octave_idx_type> to_idx (const signature_vec& types) const;
370 
371  const jit_function& do_generate (const signature_vec& types) const;
372 
374  {
375  bool operator() (const signature_vec *lhs, const signature_vec *rhs);
376  };
377 
378  typedef std::map<const signature_vec *, jit_function *, signature_cmp>
380 
382 
383  std::vector<Array<jit_function> > overloads;
384 
385  std::string mname;
386 };
387 
388 class
390 {
391 public:
392  jit_index_operation (void) : module (0), engine (0) { }
393 
394  void initialize (llvm::Module *amodule, llvm::ExecutionEngine *aengine)
395  {
396  module = amodule;
397  engine = aengine;
398  do_initialize ();
399  }
400 protected:
401  virtual jit_function *generate (const signature_vec& types) const;
402 
403  virtual jit_function *generate_matrix (const signature_vec& types) const = 0;
404 
405  virtual void do_initialize (void) = 0;
406 
407  // helper functions
408  // [start_idx, end_idx).
409  llvm::Value *create_arg_array (llvm::IRBuilderD& builder,
410  const jit_function &fn, size_t start_idx,
411  size_t end_idx) const;
412 
413  llvm::Module *module;
414  llvm::ExecutionEngine *engine;
415 };
416 
417 class
419 {
420 protected:
421  virtual jit_function *generate_matrix (const signature_vec& types) const;
422 
423  virtual void do_initialize (void);
424 private:
426 };
427 
428 class
430 {
431 protected:
432  jit_function *generate_matrix (const signature_vec& types) const;
433 
434  virtual void do_initialize (void);
435 private:
437 };
438 
439 // A singleton class which handles the construction of jit_types and
440 // jit_operations.
441 class
443 {
444 public:
445  static void initialize (llvm::Module *m, llvm::ExecutionEngine *e);
446 
447  static jit_type *join (jit_type *lhs, jit_type *rhs)
448  {
449  return instance->do_join (lhs, rhs);
450  }
451 
452  static jit_type *get_any (void) { return instance->any; }
453 
454  static jit_type *get_matrix (void) { return instance->matrix; }
455 
456  static jit_type *get_scalar (void) { return instance->scalar; }
457 
458  static llvm::Type *get_scalar_llvm (void)
459  { return instance->scalar->to_llvm (); }
460 
461  static jit_type *get_scalar_ptr (void) { return instance->scalar_ptr; }
462 
463  static jit_type *get_any_ptr (void) { return instance->any_ptr; }
464 
465  static jit_type *get_range (void) { return instance->range; }
466 
467  static jit_type *get_string (void) { return instance->string; }
468 
469  static jit_type *get_bool (void) { return instance->boolean; }
470 
471  static jit_type *get_index (void) { return instance->index; }
472 
473  static llvm::Type *get_index_llvm (void)
474  { return instance->index->to_llvm (); }
475 
476  static jit_type *get_complex (void) { return instance->complex; }
477 
478  // Get the jit_type of an octave_value
479  static jit_type *type_of (const octave_value& ov)
480  {
481  return instance->do_type_of (ov);
482  }
483 
484  static const jit_operation& binary_op (int op)
485  {
486  return instance->do_binary_op (op);
487  }
488 
489  static const jit_operation& unary_op (int op)
490  {
491  return instance->do_unary_op (op);
492  }
493 
494  static const jit_operation& grab (void) { return instance->grab_fn; }
495 
496  static const jit_function& get_grab (jit_type *type)
497  {
498  return instance->grab_fn.overload (type);
499  }
500 
501  static const jit_operation& release (void)
502  {
503  return instance->release_fn;
504  }
505 
506  static const jit_function& get_release (jit_type *type)
507  {
508  return instance->release_fn.overload (type);
509  }
510 
511  static const jit_operation& destroy (void)
512  {
513  return instance->destroy_fn;
514  }
515 
516  static const jit_operation& print_value (void)
517  {
518  return instance->print_fn;
519  }
520 
521  static const jit_operation& for_init (void)
522  {
523  return instance->for_init_fn;
524  }
525 
526  static const jit_operation& for_check (void)
527  {
528  return instance->for_check_fn;
529  }
530 
531  static const jit_operation& for_index (void)
532  {
533  return instance->for_index_fn;
534  }
535 
536  static const jit_operation& make_range (void)
537  {
538  return instance->make_range_fn;
539  }
540 
541  static const jit_operation& paren_subsref (void)
542  {
543  return instance->paren_subsref_fn;
544  }
545 
546  static const jit_operation& paren_subsasgn (void)
547  {
548  return instance->paren_subsasgn_fn;
549  }
550 
551  static const jit_operation& logically_true (void)
552  {
553  return instance->logically_true_fn;
554  }
555 
556  static const jit_operation& cast (jit_type *result)
557  {
558  return instance->do_cast (result);
559  }
560 
561  static const jit_function& cast (jit_type *to, jit_type *from)
562  {
563  return instance->do_cast (to, from);
564  }
565 
566  static llvm::Value *insert_error_check (llvm::IRBuilderD& bld)
567  {
568  return instance->do_insert_error_check (bld);
569  }
570 
571  static llvm::Value *insert_interrupt_check (llvm::IRBuilderD& bld)
572  {
573  return instance->do_insert_interrupt_check (bld);
574  }
575 
576  static const jit_operation& end (void)
577  {
578  return instance->end_fn;
579  }
580 
581  static const jit_function& end (jit_value *value, jit_value *index,
582  jit_value *count)
583  {
584  return instance->do_end (value, index, count);
585  }
586 
587  static const jit_operation& create_undef (void)
588  {
589  return instance->create_undef_fn;
590  }
591 
592  static llvm::Value *create_complex (llvm::Value *real, llvm::Value *imag)
593  {
594  return instance->complex_new (real, imag);
595  }
596 private:
597  jit_typeinfo (llvm::Module *m, llvm::ExecutionEngine *e);
598 
599  // FIXME: Do these methods really need to be in jit_typeinfo?
600  jit_type *do_join (jit_type *lhs, jit_type *rhs)
601  {
602  // empty case
603  if (! lhs)
604  return rhs;
605 
606  if (! rhs)
607  return lhs;
608 
609  // check for a shared parent
610  while (lhs != rhs)
611  {
612  if (lhs->depth () > rhs->depth ())
613  lhs = lhs->parent ();
614  else if (lhs->depth () < rhs->depth ())
615  rhs = rhs->parent ();
616  else
617  {
618  // we MUST have depth > 0 as any is the base type of everything
619  do
620  {
621  lhs = lhs->parent ();
622  rhs = rhs->parent ();
623  }
624  while (lhs != rhs);
625  }
626  }
627 
628  return lhs;
629  }
630 
631  jit_type *do_difference (jit_type *lhs, jit_type *)
632  {
633  // FIXME: Maybe we can do something smarter?
634  return lhs;
635  }
636 
637  jit_type *do_type_of (const octave_value &ov) const;
638 
639  const jit_operation& do_binary_op (int op) const
640  {
641  assert (static_cast<size_t>(op) < binary_ops.size ());
642  return binary_ops[op];
643  }
644 
645  const jit_operation& do_unary_op (int op) const
646  {
647  assert (static_cast<size_t> (op) < unary_ops.size ());
648  return unary_ops[op];
649  }
650 
651  const jit_operation& do_cast (jit_type *to)
652  {
653  static jit_operation null_function;
654  if (! to)
655  return null_function;
656 
657  size_t id = to->type_id ();
658  if (id >= casts.size ())
659  return null_function;
660  return casts[id];
661  }
662 
663  const jit_function& do_cast (jit_type *to, jit_type *from)
664  {
665  return do_cast (to).overload (from);
666  }
667 
668  const jit_function& do_end (jit_value *value, jit_value *index,
669  jit_value *count);
670 
671  jit_type *new_type (const std::string& name, jit_type *parent,
672  llvm::Type *llvm_type, bool skip_paren = false);
673 
674 
675  void add_print (jit_type *ty, void *fptr);
676 
677  void add_binary_op (jit_type *ty, int op, int llvm_op);
678 
679  void add_binary_icmp (jit_type *ty, int op, int llvm_op);
680 
681  void add_binary_fcmp (jit_type *ty, int op, int llvm_op);
682 
683  // create a function with an external calling convention
684  // forces the function pointer to be specified
685  template <typename T>
686  jit_function create_external (llvm::ExecutionEngine *ee, T fn,
687  const llvm::Twine& name, jit_type *ret,
688  const std::vector<jit_type *>& args
689  = std::vector<jit_type *> ())
690  {
691  jit_function retval = create_function (jit_convention::external, name, ret,
692  args);
693  retval.add_mapping (ee, fn);
694  return retval;
695  }
696 
697 #define JIT_PARAM_ARGS llvm::ExecutionEngine *ee, T fn, \
698  const llvm::Twine& name, jit_type *ret,
699 #define JIT_PARAMS ee, fn, name, ret,
700 #define CREATE_FUNCTION(N) JIT_EXPAND(template <typename T> jit_function, \
701  create_external, \
702  jit_type *, /* empty */, N)
703 
708 
709 #undef JIT_PARAM_ARGS
710 #undef JIT_PARAMS
711 #undef CREATE_FUNCTION
712 
713  // use create_external or create_internal directly
714  jit_function create_function (jit_convention::type cc,
715  const llvm::Twine& name, jit_type *ret,
716  const std::vector<jit_type *>& args
717  = std::vector<jit_type *> ());
718 
719  // create an internal calling convention (a function defined in llvm)
720  jit_function create_internal (const llvm::Twine& name, jit_type *ret,
721  const std::vector<jit_type *>& args
722  = std::vector<jit_type *> ())
723  {
724  return create_function (jit_convention::internal, name, ret, args);
725  }
726 
727 #define JIT_PARAM_ARGS const llvm::Twine& name, jit_type *ret,
728 #define JIT_PARAMS name, ret,
729 #define CREATE_FUNCTION(N) JIT_EXPAND(jit_function, create_internal, \
730  jit_type *, /* empty */, N)
731 
736 
737 #undef JIT_PARAM_ARGS
738 #undef JIT_PARAMS
739 #undef CREATE_FUNCTION
740 
741  jit_function create_identity (jit_type *type);
742 
743  llvm::Value *do_insert_error_check (llvm::IRBuilderD& bld);
744 
745  llvm::Value *do_insert_interrupt_check (llvm::IRBuilderD& bld);
746 
747  void add_builtin (const std::string& name);
748 
749  void register_intrinsic (const std::string& name, size_t id,
750  jit_type *result, jit_type *arg0)
751  {
752  std::vector<jit_type *> args (1, arg0);
753  register_intrinsic (name, id, result, args);
754  }
755 
756  void register_intrinsic (const std::string& name, size_t id, jit_type *result,
757  const std::vector<jit_type *>& args);
758 
759  void register_generic (const std::string& name, jit_type *result,
760  jit_type *arg0)
761  {
762  std::vector<jit_type *> args (1, arg0);
763  register_generic (name, result, args);
764  }
765 
766  void register_generic (const std::string& name, jit_type *result,
767  const std::vector<jit_type *>& args);
768 
769  octave_builtin *find_builtin (const std::string& name);
770 
771  jit_function mirror_binary (const jit_function& fn);
772 
773  llvm::Function *wrap_complex (llvm::Function *wrap);
774 
775  static llvm::Value *pack_complex (llvm::IRBuilderD& bld,
776  llvm::Value *cplx);
777 
778  static llvm::Value *unpack_complex (llvm::IRBuilderD& bld,
779  llvm::Value *result);
780 
781  llvm::Value *complex_real (llvm::Value *cx);
782 
783  llvm::Value *complex_real (llvm::Value *cx, llvm::Value *real);
784 
785  llvm::Value *complex_imag (llvm::Value *cx);
786 
787  llvm::Value *complex_imag (llvm::Value *cx, llvm::Value *imag);
788 
789  llvm::Value *complex_new (llvm::Value *real, llvm::Value *imag);
790 
791  void create_int (size_t nbits);
792 
793  jit_type *intN (size_t nbits) const;
794 
796 
797  llvm::Module *module;
798  llvm::ExecutionEngine *engine;
799  int next_id;
800 
801  llvm::GlobalVariable *lerror_state;
802  llvm::GlobalVariable *loctave_interrupt_state;
803 
804  llvm::Type *sig_atomic_type;
805 
806  std::vector<jit_type*> id_to_type;
810  jit_type *scalar_ptr; // a fake type for interfacing with C++
811  jit_type *any_ptr; // a fake type for interfacing with C++
818  std::map<size_t, jit_type *> ints;
819  std::map<std::string, jit_type *> builtins;
820 
821  llvm::StructType *complex_ret;
822 
823  std::vector<jit_operation> binary_ops;
824  std::vector<jit_operation> unary_ops;
839 
841 
842  // type id -> cast function TO that type
843  std::vector<jit_operation> casts;
844 
845  // type id -> identity function
846  std::vector<jit_function> identities;
847 
849 };
850 
851 #endif
852 #endif