Mercurial > octave-nkf
annotate src/pt-jit.h @ 14903:54ea692b8ab5
Reworking JIT implementation
src/TEMPLATE-INST/Array-jit.cc: New file.
src/TEMPLATE-INST/module.mk: Add Array-jit.cc.
src/ov-base.h (octave_base_value::grab,
octave_base_value::release): New functions.
src/pt-jit.cc: Rewrite.
src/pt-jit.h: Rewrite.
| author | Max Brister <max@2bass.com> |
|---|---|
| date | Sat, 12 May 2012 19:24:32 -0600 |
| parents | 516b4a15b775 |
| children | 3f81e8b42955 |
| rev | line source |
|---|---|
| 14899 | 1 /* |
| 2 | |
|
14901
516b4a15b775
doc: Copyright fix in pt-jit.h and pt-jit.cc
Max Brister <max@2bass.com>
parents:
14899
diff
changeset
|
3 Copyright (C) 2012 Max Brister <max@2bass.com> |
| 14899 | 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_tree_jit_h) | |
| 24 #define octave_tree_jit_h 1 | |
| 25 | |
| 14903 | 26 #include <list> |
| 14899 | 27 #include <map> |
| 14903 | 28 #include <set> |
| 14899 | 29 #include <stdexcept> |
| 30 #include <vector> | |
| 31 | |
| 14903 | 32 #include "Array.h" |
| 14899 | 33 #include "pt-walk.h" |
| 34 | |
| 14903 | 35 // -------------------- Current status -------------------- |
| 36 // Simple binary operations (+-*/) on octave_scalar's (doubles) are optimized. | |
| 37 // However, there is no warning emitted on divide by 0. For example, | |
| 38 // a = 5; | |
| 39 // b = a * 5 + a; | |
| 40 // | |
| 41 // For other types all binary operations are compiled but not optimized. For | |
| 42 // example, | |
| 43 // a = [1 2 3] | |
| 44 // b = a + a; | |
| 45 // will compile to do_binary_op (a, a). | |
| 46 // --------------------------------------------------------- | |
| 14899 | 47 |
| 14903 | 48 |
| 49 // we don't want to include llvm headers here, as they require __STDC_LIMIT_MACROS | |
| 50 // and __STDC_CONSTANT_MACROS be defined in the entire compilation unit | |
| 14899 | 51 namespace llvm |
| 52 { | |
| 53 class Value; | |
| 54 class Module; | |
| 55 class FunctionPassManager; | |
| 14903 | 56 class PassManager; |
| 14899 | 57 class ExecutionEngine; |
| 58 class Function; | |
| 59 class BasicBlock; | |
| 60 class LLVMContext; | |
| 14903 | 61 class Type; |
| 62 class GenericValue; | |
| 14899 | 63 } |
| 64 | |
| 14903 | 65 class octave_base_value; |
| 66 class octave_value; | |
| 14899 | 67 class tree; |
| 68 | |
| 14903 | 69 // thrown when we should give up on JIT and interpret |
| 70 class jit_fail_exception : public std::exception {}; | |
| 71 | |
| 72 // Used to keep track of estimated (infered) types during JIT. This is a | |
| 73 // hierarchical type system which includes both concrete and abstract types. | |
| 74 // | |
| 75 // Current, we only support any and scalar types. If we can't figure out what | |
| 76 // type a variable is, we assign it the any type. This allows us to generate | |
| 77 // code even for the case of poor type inference. | |
| 78 class | |
| 79 OCTINTERP_API | |
| 80 jit_type | |
| 81 { | |
| 82 public: | |
| 83 jit_type (const std::string& n, bool fi, jit_type *mparent, llvm::Type *lt, | |
| 84 int tid) : | |
| 85 mname (n), finit (fi), p (mparent), llvm_type (lt), id (tid) | |
| 86 {} | |
| 87 | |
| 88 // a user readable type name | |
| 89 const std::string& name (void) const { return mname; } | |
| 90 | |
| 91 // do we need to initialize variables of this type, even if they are not | |
| 92 // input arguments? | |
| 93 bool force_init (void) const { return finit; } | |
| 94 | |
| 95 // a unique id for the type | |
| 96 int type_id (void) const { return id; } | |
| 97 | |
| 98 // An abstract base type, may be null | |
| 99 jit_type *parent (void) const { return p; } | |
| 100 | |
| 101 // convert to an llvm type | |
| 102 llvm::Type *to_llvm (void) const { return llvm_type; } | |
| 103 | |
| 104 // how this type gets passed as a function argument | |
| 105 llvm::Type *to_llvm_arg (void) const; | |
| 106 private: | |
| 107 std::string mname; | |
| 108 bool finit; | |
| 109 jit_type *p; | |
| 110 llvm::Type *llvm_type; | |
| 111 int id; | |
| 112 int depth; | |
| 113 }; | |
| 114 | |
| 115 | |
| 116 // Keeps track of overloads for a builtin function. Used for both type inference | |
| 117 // and code generation. | |
| 118 class | |
| 119 jit_function | |
| 120 { | |
| 121 public: | |
| 122 struct overload | |
| 123 { | |
| 124 overload (void) : function (0), can_error (true), result (0) {} | |
| 125 | |
| 126 overload (llvm::Function *f, bool e, jit_type *r, jit_type *arg0) : | |
| 127 function (f), can_error (e), result (r), arguments (1) | |
| 128 { | |
| 129 arguments[0] = arg0; | |
| 130 } | |
| 131 | |
| 132 overload (llvm::Function *f, bool e, jit_type *r, jit_type *arg0, | |
| 133 jit_type *arg1) : function (f), can_error (e), result (r), | |
| 134 arguments (2) | |
| 135 { | |
| 136 arguments[0] = arg0; | |
| 137 arguments[1] = arg1; | |
| 138 } | |
| 139 | |
| 140 llvm::Function *function; | |
| 141 bool can_error; | |
| 142 jit_type *result; | |
| 143 std::vector<jit_type*> arguments; | |
| 144 }; | |
| 145 | |
| 146 void add_overload (const overload& func) | |
| 147 { | |
| 148 add_overload (func, func.arguments); | |
| 149 } | |
| 150 | |
| 151 void add_overload (llvm::Function *f, bool e, jit_type *r, jit_type *arg0, | |
| 152 jit_type *arg1) | |
| 153 { | |
| 154 overload ol (f, e, r, arg0, arg1); | |
| 155 add_overload (ol); | |
| 156 } | |
| 157 | |
| 158 void add_overload (const overload& func, | |
| 159 const std::vector<jit_type*>& args); | |
| 160 | |
| 161 const overload& get_overload (const std::vector<jit_type *>& types) const; | |
| 162 | |
| 163 const overload& get_overload (jit_type *arg0) const | |
| 164 { | |
| 165 std::vector<jit_type *> types (1); | |
| 166 types[0] = arg0; | |
| 167 return get_overload (types); | |
| 168 } | |
| 169 | |
| 170 const overload& get_overload (jit_type *arg0, jit_type *arg1) const | |
| 171 { | |
| 172 std::vector<jit_type *> types (2); | |
| 173 types[0] = arg0; | |
| 174 types[1] = arg1; | |
| 175 return get_overload (types); | |
| 176 } | |
| 177 | |
| 178 jit_type *get_result (const std::vector<jit_type *>& types) const | |
| 179 { | |
| 180 const overload& temp = get_overload (types); | |
| 181 return temp.result; | |
| 182 } | |
| 183 | |
| 184 jit_type *get_result (jit_type *arg0, jit_type *arg1) const | |
| 185 { | |
| 186 const overload& temp = get_overload (arg0, arg1); | |
| 187 return temp.result; | |
| 188 } | |
| 189 private: | |
| 190 Array<octave_idx_type> to_idx (const std::vector<jit_type*>& types) const; | |
| 191 | |
| 192 std::vector<Array<overload> > overloads; | |
| 193 }; | |
| 194 | |
| 195 // Get information and manipulate jit types. | |
| 196 class | |
| 197 OCTINTERP_API | |
| 198 jit_typeinfo | |
| 199 { | |
| 200 public: | |
| 201 jit_typeinfo (llvm::Module *m, llvm::ExecutionEngine *e, llvm::Type *ov); | |
| 202 | |
| 203 jit_type *get_any (void) const { return any; } | |
| 204 | |
| 205 jit_type *get_scalar (void) const { return scalar; } | |
| 206 | |
| 207 jit_type *type_of (const octave_value& ov) const; | |
| 208 | |
| 209 const jit_function& binary_op (int op) const; | |
| 210 | |
| 211 const jit_function::overload& binary_op_overload (int op, jit_type *lhs, | |
| 212 jit_type *rhs) const | |
| 213 { | |
| 214 const jit_function& jf = binary_op (op); | |
| 215 return jf.get_overload (lhs, rhs); | |
| 216 } | |
| 217 | |
| 218 jit_type *binary_op_result (int op, jit_type *lhs, jit_type *rhs) const | |
| 219 { | |
| 220 const jit_function::overload& ol = binary_op_overload (op, lhs, rhs); | |
| 221 return ol.result; | |
| 222 } | |
| 223 | |
| 224 const jit_function::overload& assign_op (jit_type *lhs, jit_type *rhs) const; | |
| 225 | |
| 226 const jit_function::overload& print_value (jit_type *to_print) const; | |
| 227 | |
| 228 // FIXME: generic creation should probably be handled seperatly | |
| 229 void to_generic (jit_type *type, llvm::GenericValue& gv); | |
| 230 void to_generic (jit_type *type, llvm::GenericValue& gv, octave_value ov); | |
| 231 | |
| 232 octave_value to_octave_value (jit_type *type, llvm::GenericValue& gv); | |
| 233 | |
| 234 void reset_generic (size_t nargs); | |
| 235 private: | |
| 236 jit_type *new_type (const std::string& name, bool force_init, | |
| 237 jit_type *parent, llvm::Type *llvm_type); | |
| 238 | |
| 239 void add_print (jit_type *ty, void *call); | |
| 240 | |
| 241 void add_binary_op (jit_type *ty, int op, int llvm_op); | |
| 242 | |
| 243 llvm::Module *module; | |
| 244 llvm::ExecutionEngine *engine; | |
| 245 int next_id; | |
| 246 | |
| 247 llvm::Type *ov_t; | |
| 248 | |
| 249 std::vector<jit_type*> id_to_type; | |
| 250 jit_type *any; | |
| 251 jit_type *scalar; | |
| 252 | |
| 253 std::vector<jit_function> binary_ops; | |
| 254 jit_function assign_fn; | |
| 255 jit_function print_fn; | |
| 256 | |
| 257 size_t scalar_out_idx; | |
| 258 std::vector<double> scalar_out; | |
| 259 | |
| 260 size_t ov_out_idx; | |
| 261 std::vector<octave_base_value*> ov_out; | |
| 262 }; | |
| 263 | |
| 14899 | 264 class |
| 265 OCTINTERP_API | |
| 14903 | 266 tree_jit |
| 14899 | 267 { |
| 268 public: | |
| 269 tree_jit (void); | |
| 270 | |
| 271 ~tree_jit (void); | |
| 272 | |
| 273 bool execute (tree& tee); | |
| 274 private: | |
| 14903 | 275 typedef std::map<std::string, jit_type *> type_map; |
| 276 | |
| 277 class | |
| 278 type_infer : public tree_walker | |
| 279 { | |
| 280 public: | |
| 281 type_infer (jit_typeinfo *ti) : tinfo (ti), is_lvalue (false), | |
| 282 rvalue_type (0) | |
| 283 {} | |
| 284 | |
| 285 const std::set<std::string>& get_argin () const { return argin; } | |
| 286 | |
| 287 const type_map& get_types () const { return types; } | |
| 288 | |
| 289 void visit_anon_fcn_handle (tree_anon_fcn_handle&); | |
| 290 | |
| 291 void visit_argument_list (tree_argument_list&); | |
| 292 | |
| 293 void visit_binary_expression (tree_binary_expression&); | |
| 294 | |
| 295 void visit_break_command (tree_break_command&); | |
| 296 | |
| 297 void visit_colon_expression (tree_colon_expression&); | |
| 298 | |
| 299 void visit_continue_command (tree_continue_command&); | |
| 300 | |
| 301 void visit_global_command (tree_global_command&); | |
| 302 | |
| 303 void visit_persistent_command (tree_persistent_command&); | |
| 304 | |
| 305 void visit_decl_elt (tree_decl_elt&); | |
| 306 | |
| 307 void visit_decl_init_list (tree_decl_init_list&); | |
| 308 | |
| 309 void visit_simple_for_command (tree_simple_for_command&); | |
| 310 | |
| 311 void visit_complex_for_command (tree_complex_for_command&); | |
| 312 | |
| 313 void visit_octave_user_script (octave_user_script&); | |
| 314 | |
| 315 void visit_octave_user_function (octave_user_function&); | |
| 316 | |
| 317 void visit_octave_user_function_header (octave_user_function&); | |
| 318 | |
| 319 void visit_octave_user_function_trailer (octave_user_function&); | |
| 320 | |
| 321 void visit_function_def (tree_function_def&); | |
| 322 | |
| 323 void visit_identifier (tree_identifier&); | |
| 324 | |
| 325 void visit_if_clause (tree_if_clause&); | |
| 326 | |
| 327 void visit_if_command (tree_if_command&); | |
| 328 | |
| 329 void visit_if_command_list (tree_if_command_list&); | |
| 330 | |
| 331 void visit_index_expression (tree_index_expression&); | |
| 332 | |
| 333 void visit_matrix (tree_matrix&); | |
| 334 | |
| 335 void visit_cell (tree_cell&); | |
| 336 | |
| 337 void visit_multi_assignment (tree_multi_assignment&); | |
| 338 | |
| 339 void visit_no_op_command (tree_no_op_command&); | |
| 340 | |
| 341 void visit_constant (tree_constant&); | |
| 342 | |
| 343 void visit_fcn_handle (tree_fcn_handle&); | |
| 344 | |
| 345 void visit_parameter_list (tree_parameter_list&); | |
| 346 | |
| 347 void visit_postfix_expression (tree_postfix_expression&); | |
| 348 | |
| 349 void visit_prefix_expression (tree_prefix_expression&); | |
| 350 | |
| 351 void visit_return_command (tree_return_command&); | |
| 352 | |
| 353 void visit_return_list (tree_return_list&); | |
| 354 | |
| 355 void visit_simple_assignment (tree_simple_assignment&); | |
| 356 | |
| 357 void visit_statement (tree_statement&); | |
| 358 | |
| 359 void visit_statement_list (tree_statement_list&); | |
| 360 | |
| 361 void visit_switch_case (tree_switch_case&); | |
| 362 | |
| 363 void visit_switch_case_list (tree_switch_case_list&); | |
| 364 | |
| 365 void visit_switch_command (tree_switch_command&); | |
| 366 | |
| 367 void visit_try_catch_command (tree_try_catch_command&); | |
| 368 | |
| 369 void visit_unwind_protect_command (tree_unwind_protect_command&); | |
| 370 | |
| 371 void visit_while_command (tree_while_command&); | |
| 372 | |
| 373 void visit_do_until_command (tree_do_until_command&); | |
| 374 private: | |
| 375 void handle_identifier (const std::string& name, octave_value v); | |
| 376 | |
| 377 jit_typeinfo *tinfo; | |
| 378 | |
| 379 bool is_lvalue; | |
| 380 jit_type *rvalue_type; | |
| 381 | |
| 382 type_map types; | |
| 383 std::set<std::string> argin; | |
| 384 | |
| 385 std::vector<jit_type *> type_stack; | |
| 386 }; | |
| 387 | |
| 388 class | |
| 389 code_generator : public tree_walker | |
| 390 { | |
| 391 public: | |
| 392 code_generator (jit_typeinfo *ti, llvm::Module *module, tree &tee, | |
| 393 const std::set<std::string>& argin, | |
| 394 const type_map& infered_types); | |
| 395 | |
| 396 llvm::Function *get_function () const { return function; } | |
| 397 | |
| 398 void visit_anon_fcn_handle (tree_anon_fcn_handle&); | |
| 399 | |
| 400 void visit_argument_list (tree_argument_list&); | |
| 401 | |
| 402 void visit_binary_expression (tree_binary_expression&); | |
| 403 | |
| 404 void visit_break_command (tree_break_command&); | |
| 405 | |
| 406 void visit_colon_expression (tree_colon_expression&); | |
| 407 | |
| 408 void visit_continue_command (tree_continue_command&); | |
| 409 | |
| 410 void visit_global_command (tree_global_command&); | |
| 411 | |
| 412 void visit_persistent_command (tree_persistent_command&); | |
| 413 | |
| 414 void visit_decl_elt (tree_decl_elt&); | |
| 415 | |
| 416 void visit_decl_init_list (tree_decl_init_list&); | |
| 417 | |
| 418 void visit_simple_for_command (tree_simple_for_command&); | |
| 419 | |
| 420 void visit_complex_for_command (tree_complex_for_command&); | |
| 421 | |
| 422 void visit_octave_user_script (octave_user_script&); | |
| 423 | |
| 424 void visit_octave_user_function (octave_user_function&); | |
| 425 | |
| 426 void visit_octave_user_function_header (octave_user_function&); | |
| 427 | |
| 428 void visit_octave_user_function_trailer (octave_user_function&); | |
| 429 | |
| 430 void visit_function_def (tree_function_def&); | |
| 431 | |
| 432 void visit_identifier (tree_identifier&); | |
| 433 | |
| 434 void visit_if_clause (tree_if_clause&); | |
| 435 | |
| 436 void visit_if_command (tree_if_command&); | |
| 437 | |
| 438 void visit_if_command_list (tree_if_command_list&); | |
| 439 | |
| 440 void visit_index_expression (tree_index_expression&); | |
| 441 | |
| 442 void visit_matrix (tree_matrix&); | |
| 443 | |
| 444 void visit_cell (tree_cell&); | |
| 445 | |
| 446 void visit_multi_assignment (tree_multi_assignment&); | |
| 447 | |
| 448 void visit_no_op_command (tree_no_op_command&); | |
| 449 | |
| 450 void visit_constant (tree_constant&); | |
| 451 | |
| 452 void visit_fcn_handle (tree_fcn_handle&); | |
| 453 | |
| 454 void visit_parameter_list (tree_parameter_list&); | |
| 455 | |
| 456 void visit_postfix_expression (tree_postfix_expression&); | |
| 457 | |
| 458 void visit_prefix_expression (tree_prefix_expression&); | |
| 459 | |
| 460 void visit_return_command (tree_return_command&); | |
| 461 | |
| 462 void visit_return_list (tree_return_list&); | |
| 463 | |
| 464 void visit_simple_assignment (tree_simple_assignment&); | |
| 465 | |
| 466 void visit_statement (tree_statement&); | |
| 467 | |
| 468 void visit_statement_list (tree_statement_list&); | |
| 469 | |
| 470 void visit_switch_case (tree_switch_case&); | |
| 471 | |
| 472 void visit_switch_case_list (tree_switch_case_list&); | |
| 473 | |
| 474 void visit_switch_command (tree_switch_command&); | |
| 475 | |
| 476 void visit_try_catch_command (tree_try_catch_command&); | |
| 477 | |
| 478 void visit_unwind_protect_command (tree_unwind_protect_command&); | |
| 479 | |
| 480 void visit_while_command (tree_while_command&); | |
| 481 | |
| 482 void visit_do_until_command (tree_do_until_command&); | |
| 483 private: | |
| 484 typedef std::pair<jit_type *, llvm::Value *> value; | |
| 485 | |
| 486 void emit_print (const std::string& name, const value& v); | |
| 487 | |
| 488 void push_value (jit_type *type, llvm::Value *v) | |
| 489 { | |
| 490 value_stack.push_back (value (type, v)); | |
| 491 } | |
| 492 | |
| 493 jit_typeinfo *tinfo; | |
| 494 llvm::Function *function; | |
| 495 | |
| 496 bool is_lvalue; | |
| 497 std::map<std::string, value> variables; | |
| 498 std::vector<value> value_stack; | |
| 499 }; | |
| 14899 | 500 |
| 501 class function_info | |
| 502 { | |
| 503 public: | |
| 14903 | 504 function_info (tree_jit& tjit, tree& tee); |
| 14899 | 505 |
| 14903 | 506 bool execute () const; |
| 507 | |
| 508 bool match () const; | |
| 14899 | 509 private: |
| 14903 | 510 jit_typeinfo *tinfo; |
| 511 llvm::ExecutionEngine *engine; | |
| 512 std::set<std::string> argin; | |
| 513 type_map types; | |
| 514 llvm::Function *function; | |
| 14899 | 515 }; |
| 516 | |
| 14903 | 517 typedef std::list<function_info *> function_list; |
| 518 typedef std::map<tree *, function_list> compiled_map; | |
| 14899 | 519 |
| 14903 | 520 static void fail (void) |
| 521 { | |
| 522 throw jit_fail_exception (); | |
| 523 } | |
| 14899 | 524 |
| 525 llvm::LLVMContext &context; | |
| 526 llvm::Module *module; | |
| 14903 | 527 llvm::PassManager *module_pass_manager; |
| 14899 | 528 llvm::FunctionPassManager *pass_manager; |
| 529 llvm::ExecutionEngine *engine; | |
| 530 | |
| 14903 | 531 jit_typeinfo *tinfo; |
| 532 | |
| 533 compiled_map compiled; | |
| 14899 | 534 }; |
| 535 | |
| 536 #endif |