GNU Octave  4.0.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
pt-jit.h
Go to the documentation of this file.
1 /*
2 
3 Copyright (C) 2012-2015 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 <[email protected]>
24 
25 #if !defined (octave_pt_jit_h)
26 #define octave_pt_jit_h 1
27 
28 #ifdef HAVE_LLVM
29 
30 #include "jit-ir.h"
31 #include "pt-walk.h"
32 #include "symtab.h"
33 
34 class octave_value_list;
35 
36 // Convert from the parse tree (AST) to the low level Octave IR.
37 class
38 jit_convert : public tree_walker
39 {
40 public:
41  typedef std::pair<jit_type *, std::string> type_bound;
42  typedef std::vector<type_bound> type_bound_vector;
43  typedef std::map<std::string, jit_variable *> variable_map;
44 
45  jit_convert (tree &tee, jit_type *for_bounds = 0);
46 
47  jit_convert (octave_user_function& fcn, const std::vector<jit_type *>& args);
48 
49 #define DECL_ARG(n) const ARG ## n& arg ## n
50 #define JIT_CREATE_CHECKED(N) \
51  template <OCT_MAKE_DECL_LIST (typename, ARG, N)> \
52  jit_call *create_checked (OCT_MAKE_LIST (DECL_ARG, N)) \
53  { \
54  jit_call *ret = factory.create<jit_call> (OCT_MAKE_ARG_LIST (arg, N)); \
55  return create_checked_impl (ret); \
56  }
57 
62 
63 #undef JIT_CREATE_CHECKED
64 #undef DECL_ARG
65 
66  jit_block_list& get_blocks (void) { return blocks; }
67 
68  const type_bound_vector& get_bounds (void) const { return bounds; }
69 
70  jit_factory& get_factory (void) { return factory; }
71 
72  llvm::Function *get_function (void) const { return function; }
73 
74  const variable_map &get_variable_map (void) const { return vmap; }
75 
76  void visit_anon_fcn_handle (tree_anon_fcn_handle&);
77 
78  void visit_argument_list (tree_argument_list&);
79 
80  void visit_binary_expression (tree_binary_expression&);
81 
82  void visit_break_command (tree_break_command&);
83 
84  void visit_colon_expression (tree_colon_expression&);
85 
86  void visit_continue_command (tree_continue_command&);
87 
88  void visit_global_command (tree_global_command&);
89 
90  void visit_persistent_command (tree_persistent_command&);
91 
92  void visit_decl_elt (tree_decl_elt&);
93 
94  void visit_decl_init_list (tree_decl_init_list&);
95 
96  void visit_simple_for_command (tree_simple_for_command&);
97 
98  void visit_complex_for_command (tree_complex_for_command&);
99 
100  void visit_octave_user_script (octave_user_script&);
101 
102  void visit_octave_user_function (octave_user_function&);
103 
104  void visit_octave_user_function_header (octave_user_function&);
105 
106  void visit_octave_user_function_trailer (octave_user_function&);
107 
108  void visit_function_def (tree_function_def&);
109 
110  void visit_identifier (tree_identifier&);
111 
112  void visit_if_clause (tree_if_clause&);
113 
114  void visit_if_command (tree_if_command&);
115 
116  void visit_if_command_list (tree_if_command_list&);
117 
118  void visit_index_expression (tree_index_expression&);
119 
120  void visit_matrix (tree_matrix&);
121 
122  void visit_cell (tree_cell&);
123 
124  void visit_multi_assignment (tree_multi_assignment&);
125 
126  void visit_no_op_command (tree_no_op_command&);
127 
128  void visit_constant (tree_constant&);
129 
130  void visit_fcn_handle (tree_fcn_handle&);
131 
132  void visit_funcall (tree_funcall&);
133 
134  void visit_parameter_list (tree_parameter_list&);
135 
136  void visit_postfix_expression (tree_postfix_expression&);
137 
138  void visit_prefix_expression (tree_prefix_expression&);
139 
140  void visit_return_command (tree_return_command&);
141 
142  void visit_return_list (tree_return_list&);
143 
144  void visit_simple_assignment (tree_simple_assignment&);
145 
146  void visit_statement (tree_statement&);
147 
148  void visit_statement_list (tree_statement_list&);
149 
150  void visit_switch_case (tree_switch_case&);
151 
152  void visit_switch_case_list (tree_switch_case_list&);
153 
154  void visit_switch_command (tree_switch_command&);
155 
156  void visit_try_catch_command (tree_try_catch_command&);
157 
158  void visit_unwind_protect_command (tree_unwind_protect_command&);
160  void visit_while_command (tree_while_command&);
161 
162  void visit_do_until_command (tree_do_until_command&);
163 private:
164  std::vector<std::pair<std::string, bool> > arguments;
165  type_bound_vector bounds;
166 
167  bool converting_function;
168 
169  // the scope of the function we are converting, or the current scope
171 
172  jit_factory factory;
173 
174  // used instead of return values from visit_* functions
175  jit_value *result;
177  jit_block *entry_block;
179  jit_block *final_block;
181  jit_block *block;
183  llvm::Function *function;
187  std::vector<jit_magic_end::context> end_context;
189  size_t iterator_count;
190  size_t for_bounds_count;
191  size_t short_count;
192 
193  variable_map vmap;
194 
196 
197  jit_call *create_checked_impl (jit_call *ret);
198 
199  // get an existing vairable. If the variable does not exist, it will not be
200  // created
201  jit_variable *find_variable (const std::string& vname) const;
202 
203  // get a variable, create it if it does not exist. The type will default to
204  // the variable's current type in the symbol table.
205  jit_variable *get_variable (const std::string& vname);
206 
207  // create a variable of the given name and given type. Will also insert an
208  // extract statement
209  jit_variable *create_variable (const std::string& vname, jit_type *type,
210  bool isarg = true);
211 
212  // The name of the next for loop iterator. If inc is false, then the iterator
213  // counter will not be incremented.
214  std::string next_iterator (bool inc = true)
215  { return next_name ("#iter", iterator_count, inc); }
216 
217  std::string next_for_bounds (bool inc = true)
218  { return next_name ("#for_bounds", for_bounds_count, inc); }
219 
220  std::string next_shortcircut_result (bool inc = true)
221  { return next_name ("#shortcircut_result", short_count, inc); }
222 
223  std::string next_name (const char *prefix, size_t& count, bool inc);
224 
225  jit_instruction *resolve (tree_index_expression& exp,
226  jit_value *extra_arg = 0, bool lhs = false);
227 
228  jit_value *do_assign (tree_expression *exp, jit_value *rhs,
229  bool artificial = false);
230 
231  jit_value *do_assign (const std::string& lhs, jit_value *rhs, bool print,
232  bool artificial = false);
234  jit_value *visit (tree *tee) { return visit (*tee); }
236  jit_value *visit (tree& tee);
237 
238  typedef std::list<jit_block *> block_list;
239  block_list breaks;
240  block_list continues;
242  void finish_breaks (jit_block *dest, const block_list& lst);
243 };
244 
245 // Convert from the low level Octave IR to LLVM
246 class
248 {
249 public:
250  llvm::Function *convert_loop (llvm::Module *module,
251  const jit_block_list& blocks,
252  const std::list<jit_value *>& constants);
253 
254  jit_function convert_function (llvm::Module *module,
255  const jit_block_list& blocks,
256  const std::list<jit_value *>& constants,
258  const std::vector<jit_type *>& args);
260  // arguments to the llvm::Function for loops
261  const std::vector<std::pair<std::string, bool> >& get_arguments(void) const
262  { return argument_vec; }
263 
264 #define JIT_METH(clname) \
265  virtual void visit (jit_ ## clname&);
266 
268 
269 #undef JIT_METH
270 private:
271  // name -> argument index (used for compiling functions)
272  std::map<std::string, int> argument_index;
273 
274  std::vector<std::pair<std::string, bool> > argument_vec;
275 
276  // name -> llvm argument (used for compiling loops)
277  std::map<std::string, llvm::Value *> arguments;
278 
279  bool converting_function;
281  // only used if we are converting a function
282  jit_function creating;
283 
284  llvm::Function *function;
285  llvm::BasicBlock *prelude;
286 
287  void convert (const jit_block_list& blocks,
288  const std::list<jit_value *>& constants);
289 
290  void finish_phi (jit_phi *phi);
291 
292  void visit (jit_value *jvalue)
293  {
294  return visit (*jvalue);
295  }
296 
297  void visit (jit_value &jvalue)
298  {
299  jvalue.accept (*this);
300  }
301 };
302 
303 // type inference and SSA construction on the low level Octave IR
304 class
305 jit_infer
306 {
307 public:
308  typedef jit_convert::variable_map variable_map;
309 
310  jit_infer (jit_factory& afactory, jit_block_list& ablocks,
311  const variable_map& avmap);
312 
313  jit_block_list& get_blocks (void) const { return blocks; }
315  jit_factory& get_factory (void) const { return factory; }
317  void infer (void);
318 private:
319  jit_block_list& blocks;
320  jit_factory& factory;
321  const variable_map& vmap;
322  std::list<jit_instruction *> worklist;
323 
324  void append_users (jit_value *v);
325 
326  void append_users_term (jit_terminator *term);
328  void construct_ssa (void);
330  void do_construct_ssa (jit_block& block, size_t avisit_count);
331 
332  jit_block& entry_block (void) { return *blocks.front (); }
333 
334  jit_block& final_block (void) { return *blocks.back (); }
335 
336  void place_releases (void);
337 
338  void push_worklist (jit_instruction *instr);
339 
340  void remove_dead ();
341 
342  void release_dead_phi (jit_block& ablock);
343 
344  void release_temp (jit_block& ablock, std::set<jit_value *>& temp);
345 
346  void simplify_phi (void);
347 
348  void simplify_phi (jit_phi& phi);
349 };
350 
351 class
352 tree_jit
353 {
354 public:
355  ~tree_jit (void);
356 
357  static bool execute (tree_simple_for_command& cmd,
358  const octave_value& bounds);
359 
360  static bool execute (tree_while_command& cmd);
361 
362  static bool execute (octave_user_function& fcn, const octave_value_list& args,
363  octave_value_list& retval);
364 
365  llvm::ExecutionEngine *get_engine (void) const { return engine; }
366 
367  llvm::Module *get_module (void) const { return module; }
368 
369  void optimize (llvm::Function *fn);
370 private:
371  tree_jit (void);
372 
373  static tree_jit& instance (void);
374 
375  bool initialize (void);
376 
377  bool do_execute (tree_simple_for_command& cmd, const octave_value& bounds);
378 
379  bool do_execute (tree_while_command& cmd);
380 
381  bool do_execute (octave_user_function& fcn, const octave_value_list& args,
382  octave_value_list& retval);
384  bool enabled (void);
385 
386  size_t trip_count (const octave_value& bounds) const;
387 
388  llvm::Module *module;
389 #ifdef LEGACY_PASSMANAGER
390  llvm::legacy::PassManager *module_pass_manager;
391  llvm::legacy::FunctionPassManager *pass_manager;
392 #else
393  llvm::PassManager *module_pass_manager;
394  llvm::FunctionPassManager *pass_manager;
395 #endif
396  llvm::ExecutionEngine *engine;
397 };
398 
399 class
401 {
402 public:
404  const octave_value_list& ov_args);
405 
406  bool execute (const octave_value_list& ov_args,
407  octave_value_list& retval) const;
409  bool match (const octave_value_list& ov_args) const;
410 private:
411  typedef octave_base_value *(*jited_function)(octave_base_value**);
413  std::vector<jit_type *> argument_types;
414  jited_function function;
415 };
416 
417 class
418 jit_info
419 {
420 public:
421  // we use a pointer here so we don't have to include ov.h
422  typedef std::map<std::string, const octave_value *> vmap;
423 
424  jit_info (tree_jit& tjit, tree& tee);
425 
426  jit_info (tree_jit& tjit, tree& tee, const octave_value& for_bounds);
427 
428  ~jit_info (void);
430  bool execute (const vmap& extra_vars = vmap ()) const;
432  bool match (const vmap& extra_vars = vmap ()) const;
433 private:
434  typedef jit_convert::type_bound type_bound;
435  typedef jit_convert::type_bound_vector type_bound_vector;
436  typedef void (*jited_function)(octave_base_value**);
438  void compile (tree_jit& tjit, tree& tee, jit_type *for_bounds = 0);
440  octave_value find (const vmap& extra_vars, const std::string& vname) const;
442  llvm::ExecutionEngine *engine;
443  jited_function function;
444  llvm::Function *llvm_function;
445 
446  std::vector<std::pair<std::string, bool> > arguments;
447  type_bound_vector bounds;
448 };
449 
450 #endif
451 #endif
#define JIT_VISIT_IR_CLASSES
Definition: jit-ir.h:63
virtual void accept(jit_ir_walker &walker)=0
jit_block * back(void) const
Definition: jit-ir.h:147
jit_factory & factory
Definition: pt-jit.h:315
std::list< jit_block * > block_list
Definition: pt-jit.h:233
jit_block * front(void) const
Definition: jit-ir.h:159
static std::string get_variable(const char *name, const std::string &defval)
Definition: mkoctfile.cc:92
static octave_idx_type find(octave_idx_type i, octave_idx_type *pp)
Definition: colamd.cc:111
std::pair< jit_type *, std::string > type_bound
Definition: pt-jit.h:41
Definition: pt.h:35
static int convert(int x, int ibase, int obase)
Definition: file-io.cc:2208
std::map< std::string, jit_variable * > variable_map
Definition: pt-jit.h:43
static bool match(const std::string &filename_arg, const std::string &path_elt_arg)
Definition: kpse.cc:1738
static void initialize(void)
Definition: mkoctfile.cc:111
#define JIT_CREATE_CHECKED(N)
Definition: pt-jit.h:50
void visit(jit_value &jvalue)
Definition: pt-jit.h:292
std::vector< type_bound > type_bound_vector
Definition: pt-jit.h:42