GNU Octave  4.4.1
A high-level interpreted language, primarily intended for numerical computations, mostly compatible with Matlab
pt-jit.h
Go to the documentation of this file.
1 /*
2 
3 Copyright (C) 2012-2018 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
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
11 
12 Octave is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License 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 <https://www.gnu.org/licenses/>.
20 
21 */
22 
23 // Author: Max Brister <max@2bass.com>
24 
25 #if ! defined (octave_pt_jit_h)
26 #define octave_pt_jit_h 1
27 
28 #include "octave-config.h"
29 
30 #if defined (HAVE_LLVM)
31 
32 #include "jit-typeinfo.h"
33 #include "jit-ir.h"
34 #include "pt-walk.h"
35 #include "symscope.h"
36 
37 // octave_value_list is not (yet) in the octave namespace
38 class octave_value_list;
39 
40 namespace octave
41 {
42  namespace jit
43  {
44 #if defined (LEGACY_PASSMANAGER)
47 #else
50 #endif
51 
52  typedef std::unique_ptr<llvm::Module> ModuleOwner;
53  typedef std::unique_ptr<llvm::ExecutionEngine> EngineOwner;
54  }
55 
56  // Convert from the parse tree (AST) to the low level Octave IR.
57  class
58  jit_convert : public tree_walker
59  {
60  public:
61 
62  typedef std::pair<jit_type *, std::string> type_bound;
63  typedef std::vector<type_bound> type_bound_vector;
64  typedef std::map<std::string, jit_variable *> variable_map;
65 
66  jit_convert (tree& tee, jit_type *for_bounds = nullptr);
67 
68  jit_convert (octave_user_function& fcn, const std::vector<jit_type *>& args);
69 
70  template <typename ...Args>
71  jit_call * create_checked (const Args&... args)
72  {
73  jit_call *ret = m_factory.create<jit_call> (args...);
74  return create_checked_impl (ret);
75  }
76 
77  jit_block_list& get_blocks (void) { return m_blocks; }
78 
79  const type_bound_vector& get_bounds (void) const { return m_bounds; }
80 
81  jit_factory& get_factory (void) { return m_factory; }
82 
83  llvm::Function *get_function (void) const { return m_function; }
84 
85  const variable_map& get_variable_map (void) const { return m_vmap; }
86 
87  void visit_anon_fcn_handle (tree_anon_fcn_handle&);
88 
89  void visit_argument_list (tree_argument_list&);
90 
91  void visit_binary_expression (tree_binary_expression&);
92 
93  void visit_boolean_expression (tree_boolean_expression&);
94 
95  void visit_break_command (tree_break_command&);
96 
97  void visit_colon_expression (tree_colon_expression&);
98 
99  void visit_continue_command (tree_continue_command&);
100 
101  void visit_decl_command (tree_decl_command&);
102 
103  void visit_decl_init_list (tree_decl_init_list&);
104 
105  void visit_decl_elt (tree_decl_elt&);
106 
107  void visit_simple_for_command (tree_simple_for_command&);
108 
109  void visit_complex_for_command (tree_complex_for_command&);
110 
111  void visit_octave_user_script (octave_user_script&);
112 
113  void visit_octave_user_function (octave_user_function&);
114 
115  void visit_octave_user_function_header (octave_user_function&);
116 
117  void visit_octave_user_function_trailer (octave_user_function&);
118 
119  void visit_function_def (tree_function_def&);
120 
121  void visit_identifier (tree_identifier&);
122 
123  void visit_if_clause (tree_if_clause&);
124 
125  void visit_if_command (tree_if_command&);
126 
127  void visit_if_command_list (tree_if_command_list&);
128 
129  void visit_index_expression (tree_index_expression&);
130 
131  void visit_matrix (tree_matrix&);
132 
133  void visit_cell (tree_cell&);
134 
135  void visit_multi_assignment (tree_multi_assignment&);
136 
137  void visit_no_op_command (tree_no_op_command&);
138 
139  void visit_constant (tree_constant&);
140 
141  void visit_fcn_handle (tree_fcn_handle&);
142 
143  void visit_funcall (tree_funcall&);
144 
145  void visit_parameter_list (tree_parameter_list&);
146 
147  void visit_postfix_expression (tree_postfix_expression&);
148 
149  void visit_prefix_expression (tree_prefix_expression&);
150 
151  void visit_return_command (tree_return_command&);
152 
153  void visit_return_list (tree_return_list&);
154 
155  void visit_simple_assignment (tree_simple_assignment&);
156 
157  void visit_statement (tree_statement&);
158 
159  void visit_statement_list (tree_statement_list&);
160 
161  void visit_switch_case (tree_switch_case&);
162 
163  void visit_switch_case_list (tree_switch_case_list&);
164 
165  void visit_switch_command (tree_switch_command&);
166 
167  void visit_try_catch_command (tree_try_catch_command&);
168 
169  void visit_unwind_protect_command (tree_unwind_protect_command&);
170 
171  void visit_while_command (tree_while_command&);
172 
173  void visit_do_until_command (tree_do_until_command&);
174 
175  private:
176 
177  std::vector<std::pair<std::string, bool>> m_arguments;
179 
181 
182  // the scope of the function we are converting, or the current scope
184 
186 
187  // used instead of return values from visit_* functions
189 
191 
193 
195 
196  llvm::Function *m_function;
197 
199 
200  std::vector<jit_magic_end::context> m_end_context;
201 
205 
207 
208  void initialize (const symbol_scope& s);
209 
210  jit_call * create_checked_impl (jit_call *ret);
211 
212  // get an existing vairable. If the variable does not exist, it will not be
213  // created
214  jit_variable * find_variable (const std::string& vname) const;
215 
216  // get a variable, create it if it does not exist. The type will default to
217  // the variable's current type in the symbol table.
218  jit_variable * get_variable (const std::string& vname);
219 
220  // create a variable of the given name and given type. Will also insert an
221  // extract statement
222  jit_variable * create_variable (const std::string& vname, jit_type *type,
223  bool isarg = true);
224 
225  // The name of the next for loop iterator. If inc is false, then the
226  // iterator counter will not be incremented.
227  std::string next_iterator (bool inc = true)
228  { return next_name ("#iter", m_iterator_count, inc); }
229 
230  std::string next_for_bounds (bool inc = true)
231  { return next_name ("#for_bounds", m_for_bounds_count, inc); }
232 
234  { return next_name ("#shortcircut_result", m_short_count, inc); }
235 
236  std::string next_name (const char *prefix, size_t& count, bool inc);
237 
238  jit_instruction * resolve (tree_index_expression& exp,
239  jit_value *extra_arg = nullptr, bool lhs = false);
240 
241  jit_value * do_assign (tree_expression *exp, jit_value *rhs,
242  bool artificial = false);
243 
244  jit_value * do_assign (const std::string& lhs, jit_value *rhs, bool print,
245  bool artificial = false);
246 
247  jit_value * visit (tree *tee) { return visit (*tee); }
248 
249  jit_value * visit (tree& tee);
250 
251  typedef std::list<jit_block *> block_list;
254 
255  void finish_breaks (jit_block *dest, const block_list& lst);
256  };
257 
258  // Convert from the low level Octave IR to LLVM
259  class
261  {
262  public:
263 
264  llvm::Function * convert_loop (const jit_module& module,
265  const jit_block_list& blocks,
266  const std::list<jit_value *>& constants,
267  const std::string& llvm_function_name);
268 
269  jit_function convert_function (const jit_module& module,
270  const jit_block_list& blocks,
271  const std::list<jit_value *>& constants,
273  const std::vector<jit_type *>& args);
274 
275  // arguments to the llvm::Function for loops
276  const std::vector<std::pair<std::string, bool>>& get_arguments(void) const
277  { return m_argument_vec; }
278 
279 #define JIT_METH(clname) \
280  virtual void visit (jit_ ## clname&);
281 
283 
284 #undef JIT_METH
285 
286  private:
287 
288  // name -> argument index (used for compiling functions)
289  std::map<std::string, int> m_argument_index;
290 
291  std::vector<std::pair<std::string, bool>> m_argument_vec;
292 
293  // name -> llvm argument (used for compiling loops)
294  std::map<std::string, llvm::Value *> m_arguments;
295 
297 
298  // only used if we are converting a function
300 
301  llvm::Function *m_function;
302  llvm::BasicBlock *m_prelude;
303 
304  void convert (const jit_block_list& blocks,
305  const std::list<jit_value *>& constants);
306 
307  void finish_phi (jit_phi *phi);
308 
309  void visit (jit_value *jvalue)
310  {
311  return visit (*jvalue);
312  }
313 
314  void visit (jit_value& jvalue)
315  {
316  jvalue.accept (*this);
317  }
318  };
319 
320  // type inference and SSA construction on the low level Octave IR
321  class
322  jit_infer
323  {
324  public:
325 
327 
328  jit_infer (jit_factory& afactory, jit_block_list& ablocks,
329  const variable_map& avmap);
330 
331  jit_block_list& get_blocks (void) const { return m_blocks; }
332 
333  jit_factory& get_factory (void) const { return m_factory; }
334 
335  void infer (void);
336 
337  private:
338 
342  std::list<jit_instruction *> m_worklist;
343 
344  void append_users (jit_value *v);
345 
346  void append_users_term (jit_terminator *term);
347 
348  void construct_ssa (void);
349 
350  void do_construct_ssa (jit_block& block, size_t avisit_count);
351 
352  jit_block& entry_block (void) { return *m_blocks.front (); }
353 
354  jit_block& final_block (void) { return *m_blocks.back (); }
355 
356  void place_releases (void);
357 
358  void push_worklist (jit_instruction *instr);
359 
360  void remove_dead ();
361 
362  void release_dead_phi (jit_block& ablock);
363 
364  void release_temp (jit_block& ablock, std::set<jit_value *>& temp);
365 
366  void simplify_phi (void);
367 
368  void simplify_phi (jit_phi& phi);
369  };
370 
371 
372  class jit_module;
373 
374  class
375  tree_jit
376  {
377  // ----- Constructor/destructor (singleton pattern) -----
378 
379  public:
380 
381  ~tree_jit (void);
382 
383  private:
384 
385  tree_jit (void);
386  static tree_jit& instance (void);
387 
388  // ----- Initialization -----
389 
390  private:
391 
392  static bool initialized;
393  bool do_initialize (void);
394 
395  // ----- Target machine ----
396 
397  public:
398 
399  static const llvm::TargetMachine* get_target_machine (void)
400  { return instance ().target_machine; }
401 
402  private:
403 
404  llvm::TargetMachine *target_machine;
405 
406  // ----- Create LLVM modules and engines -----
407 
408  public:
409 
410  static jit::ModuleOwner
411  open_new_module (const std::string& module_name = generate_unique_module_name ());
412 
413  static jit::EngineOwner
414  create_new_engine (jit::ModuleOwner module_owner);
415 
416  private:
417 
419  do_open_new_module (const std::string& module_name) const;
420 
421  // ----- Registering JIT modules (module+engine pairs) -----
422 
423  public:
424 
425  static void register_jit_module (jit_module* jm)
426  { instance ().do_register_jit_module (jm); }
427 
429  { instance ().do_unregister_jit_module (jm); }
430 
431  private:
432 
433  // List of all currently registered jit modules
434  std::list<jit_module*> jm_list;
435  void do_register_jit_module (jit_module* jm);
436  void do_unregister_jit_module (jit_module* jm);
437  void do_dump_all_modules (void) const;
438 
439  // ----- Symbol resolution -----
440 
441  public:
442 
444  { return instance ().do_getPointerToNamedFunction (name); }
445 
446  static uint64_t getSymbolAddress (const std::string &name)
447  { return instance ().do_getSymbolAddress (name); }
448 
449  private:
450 
451  void* do_getPointerToNamedFunction (const std::string &Name) const;
452 
453  uint64_t do_getSymbolAddress (const std::string &name) const;
454 
455  // ----- Generate unique identifiers -----
456 
457  public:
458 
460  {
461  return std::string ("jittedForLoop")
462  + std::to_string (next_forloop_number ++);
463  }
464  // FIXME: Check that the identifier does not exist
465 
467  {
468  return std::string ("jittedFunction")
469  + std::to_string (next_function_number ++);
470  }
471  // FIXME: Check that the identifier does not exist
472 
474  {
475  return std::string ("octaveJITModule")
476  + std::to_string (next_module_number ++);
477  }
478  // FIXME: Check that the identifier does not exist
479 
480  private:
481 
484  static int next_module_number;
485 
486  // ----- JIT and execute ASTs -----
487 
488  public:
489 
490  static bool execute (tree_simple_for_command& cmd,
491  const octave_value& bounds)
492  { return instance ().do_execute (cmd, bounds); }
493 
494  static bool execute (tree_while_command& cmd)
495  { return instance ().do_execute (cmd); }
496 
498  const octave_value_list& args,
500  { return instance ().do_execute (fcn, args, retval); }
501 
502  private:
503 
504  bool do_execute (tree_simple_for_command& cmd,
505  const octave_value& bounds);
506 
507  bool do_execute (tree_while_command& cmd);
508 
509  bool do_execute (octave_user_function& fcn,
510  const octave_value_list& args,
512 
513  // ----- Miscellaneous -----
514 
515  bool enabled (void);
516 
517  size_t trip_count (const octave_value& bounds) const;
518  };
519 
520 
521  class
522  jit_module
523  {
524  // TODO: Encapsulate all operations that can modify the module,
525  // and prevent them if the module has been finalized
526 
527  // TODO: Consider creating the engine at the end only?
528  // I have read somewhere that this is more efficient (nor sure)
529 
530  public:
531 
532  // Create an open module and associated JIT engine
533  jit_module (const std::string& module_name
535 
536  // Delete the underlying JIT engine
537  ~jit_module ();
538 
539  // Create an LLVM function in the module, with external linkage
540  llvm::Function*
541  create_llvm_function (llvm::FunctionType *ftype,
542  const llvm::Twine &name) const;
543 
544  // Create a global in the module, with external linkage
545  llvm::GlobalVariable*
546  create_global_variable (llvm::Type *type, bool is_constant,
547  const llvm::Twine& name) const;
548 
549  // Create or insert an LLVM Function declaration for an intrinsic,
550  // and return it
551  llvm::Function*
552  get_intrinsic_declaration (size_t id,
553  std::vector<llvm::Type*> types) const;
554 
555  // Underlying type of enums defined in yet-inconplete types
556  typedef unsigned llvm_gv_linkage; // FIXME: autoconf this
557 
558  // add_global_mapping tells the execution engine where a specified
559  // global value (variable or function) is
560  template <typename ptr_type>
561  void add_global_mapping (const llvm::GlobalValue* gv, ptr_type p) const
562  {
563  do_add_global_mapping (gv, reinterpret_cast<void *> (p));
564  }
565 
566  // Return the address of the specified function.
567  uint64_t getFunctionAddress (const std::string &name) const;
568 
569  // Optimize a function in the LLVM module
570  void optimize (llvm::Function *fn) const;
571 
572  // FIXME: Once this has been called, we should not be able
573  // to change anything in the module...
574  void finalizeObject (void);
575 
576  private:
577 
578  void do_add_global_mapping (const llvm::GlobalValue* gv, void* p) const;
579 
580  llvm::Module *m_module;
581  llvm::ExecutionEngine *m_engine;
582  };
583 
584 
585  class
586  jit_info : public jit_module
587  {
588  public:
589 
590  // we use a pointer here so we don't have to include ov.h
591  typedef std::map<std::string, const octave_value *> vmap;
592 
593  jit_info (tree& tee);
594 
595  jit_info (tree& tee, const octave_value& for_bounds);
596 
597  jit_info (tree_simple_for_command& tee, const octave_value& for_bounds);
598 
599  bool execute (const vmap& extra_vars = vmap ()) const;
600 
601  bool match (const vmap& extra_vars = vmap ()) const;
602 
603  private:
604 
607  typedef void (*jited_function)(octave_base_value**);
608 
609  void compile (tree& tee, jit_type *for_bounds = 0);
610 
611  octave_value find (const vmap& extra_vars, const std::string& vname) const;
612 
613  // LLVM function associated to this jit_info object
615  jited_function m_function;
616 
617  std::vector<std::pair<std::string, bool>> m_arguments;
619  };
620 
621 
622  class
624  {
625  public:
626 
628  const octave_value_list& ov_args);
629 
630  bool execute (const octave_value_list& ov_args,
631  octave_value_list& retval) const;
632 
633  bool match (const octave_value_list& ov_args) const;
634 
635  private:
636 
637  typedef octave_base_value *(*jited_function)(octave_base_value**);
638 
639  // LLVM function associated to this jit_info object
641  jited_function m_function;
642 
643  std::vector<jit_type *> m_argument_types;
644  };
645 }
646 
647 #endif
648 
649 #endif
size_t m_for_bounds_count
Definition: pt-jit.h:203
size_t m_iterator_count
Definition: pt-jit.h:202
#define JIT_VISIT_IR_CLASSES
Definition: jit-ir.h:68
std::unique_ptr< llvm::Module > ModuleOwner
Definition: pt-jit.h:52
llvm::Function * m_function
Definition: pt-jit.h:301
std::string m_llvm_function_name
Definition: pt-jit.h:614
jit_factory & get_factory(void) const
Definition: pt-jit.h:333
uint64_t do_getSymbolAddress(const std::string &name) const
Definition: pt-jit.cc:2202
void visit(jit_value *jvalue)
Definition: pt-jit.h:309
std::list< jit_module * > jm_list
Definition: pt-jit.h:434
jit_factory m_factory
Definition: pt-jit.h:185
static bool initialized
Definition: pt-jit.h:392
static const llvm::TargetMachine * get_target_machine(void)
Definition: pt-jit.h:399
std::map< std::string, const octave_value * > vmap
Definition: pt-jit.h:591
jit_value * m_result
Definition: pt-jit.h:188
static std::string generate_unique_function_name(void)
Definition: pt-jit.h:466
static int next_function_number
Definition: pt-jit.h:483
std::vector< jit_magic_end::context > m_end_context
Definition: pt-jit.h:200
jit_convert::type_bound type_bound
Definition: pt-jit.h:605
std::map< std::string, int > m_argument_index
Definition: pt-jit.h:282
static void unregister_jit_module(jit_module *jm)
Definition: pt-jit.h:428
llvm::BasicBlock * m_prelude
Definition: pt-jit.h:302
void do_register_jit_module(jit_module *jm)
Definition: pt-jit.cc:2174
void * do_getPointerToNamedFunction(const std::string &Name) const
Definition: pt-jit.cc:2186
jit_block_list & get_blocks(void) const
Definition: pt-jit.h:331
jit_factory & m_factory
Definition: pt-jit.h:340
jit_block & final_block(void)
Definition: pt-jit.h:354
symbol_scope m_scope
Definition: pt-jit.h:183
static bool execute(tree_while_command &cmd)
Definition: pt-jit.h:494
jited_function m_function
Definition: pt-jit.h:641
s
Definition: file-io.cc:2729
static bool execute(octave_user_function &fcn, const octave_value_list &args, octave_value_list &retval)
Definition: pt-jit.h:497
jited_function m_function
Definition: pt-jit.h:615
variable_map m_vmap
Definition: pt-jit.h:206
std::map< std::string, jit_variable * > variable_map
Definition: pt-jit.h:64
octave_function * fcn
Definition: ov-class.cc:1754
llvm::PassManager PassManager
Definition: pt-jit.h:48
const type_bound_vector & get_bounds(void) const
Definition: pt-jit.h:79
const variable_map & get_variable_map(void) const
Definition: pt-jit.h:85
llvm::FunctionPassManager FunctionPassManager
Definition: pt-jit.h:49
block_list m_breaks
Definition: pt-jit.h:252
static void initialize(void)
std::string next_shortcircut_result(bool inc=true)
Definition: pt-jit.h:233
static void * getPointerToNamedFunction(const std::string &name)
Definition: pt-jit.h:443
std::string next_iterator(bool inc=true)
Definition: pt-jit.h:227
block_list m_continues
Definition: pt-jit.h:253
jit_convert::variable_map variable_map
Definition: pt-jit.h:326
std::unique_ptr< llvm::ExecutionEngine > EngineOwner
Definition: pt-jit.h:53
llvm::ExecutionEngine * m_engine
Definition: pt-jit.h:581
nd deftypefn *std::string name
Definition: sysdep.cc:647
jit_block * back(void) const
Definition: jit-ir.h:144
std::vector< std::pair< std::string, bool > > m_argument_vec
Definition: pt-jit.h:291
jit_call * create_checked(const Args &... args)
Definition: pt-jit.h:71
std::list< jit_block * > block_list
Definition: pt-jit.h:251
static void register_jit_module(jit_module *jm)
Definition: pt-jit.h:425
bool do_execute(tree_simple_for_command &cmd, const octave_value &bounds)
Definition: pt-jit.cc:2260
virtual void accept(jit_ir_walker &walker)=0
jit_block & entry_block(void)
Definition: pt-jit.h:352
jit_factory & get_factory(void)
Definition: pt-jit.h:81
llvm::Function * get_function(void) const
Definition: pt-jit.h:83
std::string next_for_bounds(bool inc=true)
Definition: pt-jit.h:230
octave_value retval
Definition: data.cc:6246
void visit(jit_value &jvalue)
Definition: pt-jit.h:314
unsigned llvm_gv_linkage
Definition: pt-jit.h:556
std::vector< std::pair< std::string, bool > > m_arguments
Definition: pt-jit.h:617
void add_global_mapping(const llvm::GlobalValue *gv, ptr_type p) const
Definition: pt-jit.h:561
idx type
Definition: ov.cc:3114
jit_block_list & get_blocks(void)
Definition: pt-jit.h:77
const std::vector< std::pair< std::string, bool > > & get_arguments(void) const
Definition: pt-jit.h:276
jit_function m_creating
Definition: pt-jit.h:299
static octave_idx_type find(octave_idx_type i, octave_idx_type *pp)
Definition: colamd.cc:103
jit_block * front(void) const
Definition: jit-ir.h:156
std::string m_llvm_function_name
Definition: pt-jit.h:640
std::list< jit_instruction * > m_worklist
Definition: pt-jit.h:342
static int next_forloop_number
Definition: pt-jit.h:482
std::vector< type_bound > type_bound_vector
Definition: pt-jit.h:63
jit_convert::type_bound_vector type_bound_vector
Definition: pt-jit.h:606
jit_block * m_block
Definition: pt-jit.h:194
static int next_module_number
Definition: pt-jit.h:484
p
Definition: lu.cc:138
std::vector< std::pair< std::string, bool > > m_arguments
Definition: pt-jit.h:177
jit_block * m_entry_block
Definition: pt-jit.h:190
jit_block * m_final_block
Definition: pt-jit.h:192
type_bound_vector m_bounds
Definition: pt-jit.h:618
std::pair< jit_type *, std::string > type_bound
Definition: pt-jit.h:62
llvm::Module * m_module
Definition: pt-jit.h:580
static std::string get_variable(const char *name, const std::string &defval)
jit_block_list & m_blocks
Definition: pt-jit.h:339
jit_value * visit(tree *tee)
Definition: pt-jit.h:247
static bool execute(tree_simple_for_command &cmd, const octave_value &bounds)
Definition: pt-jit.h:490
size_t m_short_count
Definition: pt-jit.h:204
void do_unregister_jit_module(jit_module *jm)
Definition: pt-jit.cc:2180
std::vector< jit_type * > m_argument_types
Definition: pt-jit.h:643
jit_block_list m_blocks
Definition: pt-jit.h:198
llvm::TargetMachine * target_machine
Definition: pt-jit.h:404
type_bound_vector m_bounds
Definition: pt-jit.h:178
If this string is the system will ring the terminal sometimes it is useful to be able to print the original representation of the string
Definition: utils.cc:888
bool m_converting_function
Definition: pt-jit.h:180
llvm::Function * m_function
Definition: pt-jit.h:196
static uint64_t getSymbolAddress(const std::string &name)
Definition: pt-jit.h:446
std::map< std::string, llvm::Value * > m_arguments
Definition: pt-jit.h:294
static std::string generate_unique_module_name(void)
Definition: pt-jit.h:473
static std::string generate_unique_forloop_name(void)
Definition: pt-jit.h:459
const variable_map & m_vmap
Definition: pt-jit.h:341