1 //////////////////////////////////////////////////////////////////////// 2 // 3 // Copyright (C) 2012-2021 The Octave Project Developers 4 // 5 // See the file COPYRIGHT.md in the top-level directory of this 6 // distribution or <https://octave.org/copyright/>. 7 // 8 // This file is part of Octave. 9 // 10 // Octave is free software: you can redistribute it and/or modify it 11 // under the terms of the GNU General Public License as published by 12 // the Free Software Foundation, either version 3 of the License, or 13 // (at your option) any later version. 14 // 15 // Octave is distributed in the hope that it will be useful, but 16 // WITHOUT ANY WARRANTY; without even the implied warranty of 17 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 // GNU General Public License for more details. 19 // 20 // You should have received a copy of the GNU General Public License 21 // along with Octave; see the file COPYING. If not, see 22 // <https://www.gnu.org/licenses/>. 23 // 24 //////////////////////////////////////////////////////////////////////// 25 26 #if ! defined (octave_jit_ir_h) 27 #define octave_jit_ir_h 1 28 29 #include "octave-config.h" 30 31 #if defined (HAVE_LLVM) 32 33 #include <list> 34 #include <stack> 35 #include <set> 36 37 #include "jit-typeinfo.h" 38 39 namespace octave 40 { 41 42 // The low level octave JIT IR. This ir is close to llvm, but 43 // contains information for doing type inference. We convert the 44 // octave parse tree to this IR directly. 45 46 #define JIT_VISIT_IR_NOTEMPLATE \ 47 JIT_METH (block); \ 48 JIT_METH (branch); \ 49 JIT_METH (cond_branch); \ 50 JIT_METH (call); \ 51 JIT_METH (extract_argument); \ 52 JIT_METH (store_argument); \ 53 JIT_METH (return); \ 54 JIT_METH (phi); \ 55 JIT_METH (variable); \ 56 JIT_METH (error_check); \ 57 JIT_METH (assign) \ 58 JIT_METH (argument) \ 59 JIT_METH (magic_end) 60 61 #define JIT_VISIT_IR_CONST \ 62 JIT_METH (const_bool); \ 63 JIT_METH (const_scalar); \ 64 JIT_METH (const_complex); \ 65 JIT_METH (const_index); \ 66 JIT_METH (const_string); \ 67 JIT_METH (const_range) 68 69 #define JIT_VISIT_IR_CLASSES \ 70 JIT_VISIT_IR_NOTEMPLATE \ 71 JIT_VISIT_IR_CONST 72 73 // forward declare all ir classes 74 #define JIT_METH(cname) \ 75 class jit_ ## cname; 76 77 JIT_VISIT_IR_NOTEMPLATE 78 79 #undef JIT_METH 80 81 // ABCs which aren't included in JIT_VISIT_IR_ALL 82 class jit_instruction; 83 class jit_terminator; 84 85 template <typename T, jit_type *(*EXTRACT_T)(void), typename PASS_T = T, 86 bool QUOTE=false> 87 class jit_const; 88 89 typedef jit_const<bool, jit_typeinfo::get_bool> jit_const_bool; 90 typedef jit_const<double, jit_typeinfo::get_scalar> jit_const_scalar; 91 typedef jit_const<Complex, jit_typeinfo::get_complex> jit_const_complex; 92 typedef jit_const<octave_idx_type, jit_typeinfo::get_index> jit_const_index; 93 94 typedef jit_const<std::string, jit_typeinfo::get_string, 95 const std::string&, true> 96 jit_const_string; 97 typedef jit_const<jit_range, jit_typeinfo::get_range, const jit_range&> 98 jit_const_range; 99 100 class jit_ir_walker; 101 class jit_use; 102 103 // Creates and tracks memory for jit_value and subclasses. 104 // Memory management is simple, all values that are created live as 105 // long as the factory. 106 class 107 jit_factory 108 { 109 typedef std::list<jit_value *> value_list; 110 111 public: 112 113 ~jit_factory (void); 114 constants(void)115 const value_list& constants (void) const { return m_constants; } 116 117 template <typename T, typename ...Args> create(const Args &...args)118 T * create (const Args&... args) 119 { 120 T *ret = new T (args...); 121 track_value (ret); 122 return ret; 123 } 124 125 private: 126 127 void track_value (jit_value *v); 128 129 value_list m_all_values; 130 131 value_list m_constants; 132 }; 133 134 // A list of basic blocks (jit_block) which form some body of code. 135 // 136 // We do not directly inherit from std::list because we need to update the 137 // blocks stashed location in push_back and insert. 138 class 139 jit_block_list 140 { 141 public: 142 143 typedef std::list<jit_block *>::iterator iterator; 144 typedef std::list<jit_block *>::const_iterator const_iterator; 145 back(void)146 jit_block * back (void) const { return m_list.back (); } 147 begin(void)148 iterator begin (void) { return m_list.begin (); } 149 begin(void)150 const_iterator begin (void) const { return m_list.begin (); } 151 end(void)152 iterator end (void) { return m_list.end (); } 153 end(void)154 const_iterator end (void) const { return m_list.end (); } 155 erase(iterator iter)156 iterator erase (iterator iter) { return m_list.erase (iter); } 157 front(void)158 jit_block * front (void) const { return m_list.front (); } 159 160 void insert_after (iterator iter, jit_block *ablock); 161 162 void insert_after (jit_block *loc, jit_block *ablock); 163 164 void insert_before (iterator iter, jit_block *ablock); 165 166 void insert_before (jit_block *loc, jit_block *ablock); 167 168 void label (void); 169 170 std::ostream& print (std::ostream& os, const std::string& header) const; 171 172 std::ostream& print_dom (std::ostream& os) const; 173 174 void push_back (jit_block *b); 175 176 private: 177 178 std::list<jit_block *> m_list; 179 }; 180 181 std::ostream& operator<<(std::ostream& os, const jit_block_list& blocks); 182 183 class 184 jit_value : public jit_internal_list<jit_value, jit_use> 185 { 186 public: 187 jit_value(void)188 jit_value (void) 189 : m_llvm_value (0), m_type (0), m_last_use (0), m_in_worklist (false) 190 { } 191 192 virtual ~jit_value (void); 193 in_worklist(void)194 bool in_worklist (void) const 195 { 196 return m_in_worklist; 197 } 198 stash_in_worklist(bool ain_worklist)199 void stash_in_worklist (bool ain_worklist) 200 { 201 m_in_worklist = ain_worklist; 202 } 203 204 // The block of the first use which is not a jit_error_check 205 // So this is not necessarily first_use ()->parent (). 206 jit_block * first_use_block (void); 207 208 // replace all uses with 209 virtual void replace_with (jit_value *m_value); 210 type(void)211 jit_type * type (void) const { return m_type; } 212 type_llvm(void)213 llvm::Type * type_llvm (void) const 214 { 215 return m_type ? m_type->to_llvm () : nullptr; 216 } 217 type_name(void)218 const std::string& type_name (void) const 219 { 220 return m_type->name (); 221 } 222 stash_type(jit_type * new_type)223 void stash_type (jit_type *new_type) { m_type = new_type; } 224 print_string(void)225 std::string print_string (void) 226 { 227 std::stringstream ss; 228 print (ss); 229 return ss.str (); 230 } 231 last_use(void)232 jit_instruction * last_use (void) const { return m_last_use; } 233 stash_last_use(jit_instruction * alast_use)234 void stash_last_use (jit_instruction *alast_use) 235 { 236 m_last_use = alast_use; 237 } 238 needs_release(void)239 virtual bool needs_release (void) const { return false; } 240 241 virtual std::ostream& print (std::ostream& os, std::size_t indent = 0) const = 0; 242 short_print(std::ostream & os)243 virtual std::ostream& short_print (std::ostream& os) const 244 { return print (os); } 245 246 virtual void accept (jit_ir_walker& walker) = 0; 247 has_llvm(void)248 bool has_llvm (void) const 249 { 250 return m_llvm_value; 251 } 252 to_llvm(void)253 llvm::Value * to_llvm (void) const 254 { 255 assert (m_llvm_value); 256 return m_llvm_value; 257 } 258 stash_llvm(llvm::Value * compiled)259 void stash_llvm (llvm::Value *compiled) 260 { 261 m_llvm_value = compiled; 262 } 263 264 protected: 265 266 std::ostream& print_indent (std::ostream& os, std::size_t indent = 0) const 267 { 268 for (std::size_t i = 0; i < indent * 8; ++i) 269 os << ' '; 270 return os; 271 } 272 273 llvm::Value *m_llvm_value; 274 275 private: 276 277 jit_type *m_type; 278 jit_instruction *m_last_use; 279 bool m_in_worklist; 280 }; 281 282 std::ostream& operator<< (std::ostream& os, const jit_value& value); 283 std::ostream& jit_print (std::ostream& os, jit_value *avalue); 284 285 class 286 jit_use : public jit_internal_node<jit_value, jit_use> 287 { 288 public: 289 290 // some compilers don't allow us to use jit_internal_node without template 291 // parameters 292 typedef jit_internal_node<jit_value, jit_use> PARENT_T; 293 jit_use(void)294 jit_use (void) : m_user (0), m_index (0) { } 295 296 // we should really have a move operator, but not until c++11 :( jit_use(const jit_use & use)297 jit_use (const jit_use& use) : m_user (0), m_index (0) 298 { 299 *this = use; 300 } 301 302 jit_use& operator= (const jit_use& use) 303 { 304 stash_value (use.value (), use.user (), use.index ()); 305 return *this; 306 } 307 index(void)308 std::size_t index (void) const { return m_index; } 309 user(void)310 jit_instruction * user (void) const { return m_user; } 311 312 jit_block * user_parent (void) const; 313 314 std::list<jit_block *> user_parent_location (void) const; 315 316 void stash_value (jit_value *avalue, jit_instruction *auser = nullptr, 317 std::size_t aindex = -1) 318 { 319 PARENT_T::stash_value (avalue); 320 m_index = aindex; 321 m_user = auser; 322 } 323 324 private: 325 326 jit_instruction *m_user; 327 std::size_t m_index; 328 }; 329 330 class 331 jit_instruction : public jit_value 332 { 333 public: 334 335 // FIXME: this code could be so much pretier with varadic templates... jit_instruction(void)336 jit_instruction (void) 337 : m_id (next_id ()), m_parent (0) 338 { } 339 jit_instruction(std::size_t nargs)340 jit_instruction (std::size_t nargs) 341 : m_id (next_id ()), m_parent (0) 342 { 343 m_already_infered.reserve (nargs); 344 m_arguments.reserve (nargs); 345 } 346 347 template <typename ...Args> jit_instruction(jit_value * arg1,Args...other_args)348 jit_instruction (jit_value * arg1, Args... other_args) 349 : m_already_infered (1 + sizeof... (other_args)), 350 m_arguments (1 + sizeof... (other_args)), 351 m_id (next_id ()), m_parent (nullptr) 352 { 353 stash_argument (0, arg1, other_args...); 354 } 355 jit_instruction(const std::vector<jit_value * > & aarguments)356 jit_instruction (const std::vector<jit_value *>& aarguments) 357 : m_already_infered (aarguments.size ()), m_arguments (aarguments.size ()), 358 m_id (next_id ()), m_parent (0) 359 { 360 for (std::size_t i = 0; i < aarguments.size (); ++i) 361 stash_argument (i, aarguments[i]); 362 } 363 reset_ids(void)364 static void reset_ids (void) 365 { 366 next_id (true); 367 } 368 argument(std::size_t i)369 jit_value * argument (std::size_t i) const 370 { 371 return m_arguments[i].value (); 372 } 373 argument_llvm(std::size_t i)374 llvm::Value * argument_llvm (std::size_t i) const 375 { 376 assert (argument (i)); 377 return argument (i)->to_llvm (); 378 } 379 argument_type(std::size_t i)380 jit_type * argument_type (std::size_t i) const 381 { 382 return argument (i)->type (); 383 } 384 argument_type_llvm(std::size_t i)385 llvm::Type * argument_type_llvm (std::size_t i) const 386 { 387 assert (argument (i)); 388 return argument_type (i)->to_llvm (); 389 } 390 print_argument(std::ostream & os,std::size_t i)391 std::ostream& print_argument (std::ostream& os, std::size_t i) const 392 { 393 if (argument (i)) 394 return argument (i)->short_print (os); 395 else 396 return os << "NULL"; 397 } 398 stash_argument(std::size_t i,jit_value * arg)399 void stash_argument (std::size_t i, jit_value * arg) 400 { 401 m_arguments[i].stash_value (arg, this, i); 402 } 403 404 template <typename ...Args> stash_argument(std::size_t i,jit_value * arg1,Args...aargs)405 void stash_argument (std::size_t i, jit_value * arg1, Args... aargs) 406 { 407 m_arguments[i].stash_value (arg1, this, i); 408 stash_argument (++i, aargs...); 409 } 410 push_argument(jit_value * arg)411 void push_argument (jit_value *arg) 412 { 413 m_arguments.push_back (jit_use ()); 414 stash_argument (m_arguments.size () - 1, arg); 415 m_already_infered.push_back (0); 416 } 417 argument_count(void)418 std::size_t argument_count (void) const 419 { 420 return m_arguments.size (); 421 } 422 423 void resize_arguments (std::size_t acount, jit_value *adefault = nullptr) 424 { 425 std::size_t old = m_arguments.size (); 426 m_arguments.resize (acount); 427 m_already_infered.resize (acount); 428 429 if (adefault) 430 for (std::size_t i = old; i < acount; ++i) 431 stash_argument (i, adefault); 432 } 433 arguments(void)434 const std::vector<jit_use>& arguments (void) const { return m_arguments; } 435 436 // argument types which have been infered already argument_types(void)437 const std::vector<jit_type *>& argument_types (void) const 438 { return m_already_infered; } 439 push_variable(void)440 virtual void push_variable (void) { } 441 pop_variable(void)442 virtual void pop_variable (void) { } 443 construct_ssa(void)444 virtual void construct_ssa (void) 445 { 446 do_construct_ssa (0, argument_count ()); 447 } 448 infer(void)449 virtual bool infer (void) { return false; } 450 451 void remove (void); 452 453 virtual std::ostream& short_print (std::ostream& os) const; 454 parent(void)455 jit_block * parent (void) const { return m_parent; } 456 location(void)457 std::list<jit_instruction *>::iterator location (void) const 458 { 459 return m_location; 460 } 461 462 llvm::BasicBlock * parent_llvm (void) const; 463 stash_parent(jit_block * aparent,std::list<jit_instruction * >::iterator alocation)464 void stash_parent (jit_block *aparent, 465 std::list<jit_instruction *>::iterator alocation) 466 { 467 m_parent = aparent; 468 m_location = alocation; 469 } 470 id(void)471 std::size_t id (void) const { return m_id; } 472 473 protected: 474 475 // Do SSA replacement on arguments in [start, end) 476 void do_construct_ssa (std::size_t start, std::size_t end); 477 478 std::vector<jit_type *> m_already_infered; 479 480 private: 481 482 static std::size_t next_id (bool reset = false) 483 { 484 static std::size_t ret = 0; 485 if (reset) 486 return ret = 0; 487 488 return ret++; 489 } 490 491 std::vector<jit_use> m_arguments; 492 493 std::size_t m_id; 494 jit_block *m_parent; 495 std::list<jit_instruction *>::iterator m_location; 496 }; 497 498 // defnie accept methods for subclasses 499 #define JIT_VALUE_ACCEPT \ 500 virtual void accept (jit_ir_walker& walker); 501 502 // for use as a dummy argument during conversion to LLVM 503 class 504 jit_argument : public jit_value 505 { 506 public: 507 jit_argument(jit_type * atype,llvm::Value * avalue)508 jit_argument (jit_type *atype, llvm::Value *avalue) 509 { 510 stash_type (atype); 511 stash_llvm (avalue); 512 } 513 514 virtual std::ostream& print (std::ostream& os, std::size_t indent = 0) const 515 { 516 print_indent (os, indent); 517 return jit_print (os, type ()) << ": DUMMY"; 518 } 519 520 JIT_VALUE_ACCEPT; 521 }; 522 523 template <typename T, jit_type *(*EXTRACT_T)(void), typename PASS_T, bool QUOTE> 524 class 525 jit_const : public jit_value 526 { 527 public: 528 529 typedef PASS_T pass_t; 530 jit_const(PASS_T avalue)531 jit_const (PASS_T avalue) : m_value (avalue) 532 { 533 stash_type (EXTRACT_T ()); 534 } 535 value(void)536 PASS_T value (void) const { return m_value; } 537 538 virtual std::ostream& print (std::ostream& os, std::size_t indent = 0) const 539 { 540 print_indent (os, indent); 541 jit_print (os, type ()) << ": "; 542 if (QUOTE) 543 os << '"'; 544 os << m_value; 545 if (QUOTE) 546 os << '"'; 547 return os; 548 } 549 550 JIT_VALUE_ACCEPT; 551 552 private: 553 554 T m_value; 555 }; 556 557 class jit_phi_incoming; 558 559 class 560 jit_block : public jit_value, public jit_internal_list<jit_block, 561 jit_phi_incoming> 562 { 563 typedef jit_internal_list<jit_block, jit_phi_incoming> ILIST_T; 564 565 public: 566 567 typedef std::list<jit_instruction *> instruction_list; 568 typedef instruction_list::iterator iterator; 569 typedef instruction_list::const_iterator const_iterator; 570 571 typedef std::set<jit_block *> df_set; 572 typedef df_set::const_iterator df_iterator; 573 574 static const std::size_t NO_ID = static_cast<std::size_t> (-1); 575 576 jit_block (const std::string& aname, std::size_t avisit_count = 0) m_visit_count(avisit_count)577 : m_visit_count (avisit_count), m_id (NO_ID), m_idom (0), m_name (aname), 578 m_alive (false) 579 { } 580 581 virtual void replace_with (jit_value *value); 582 583 void replace_in_phi (jit_block *ablock, jit_block *with); 584 585 // we have a new internal list, but we want to stay compatible with jit_value first_use(void)586 jit_use * first_use (void) const { return jit_value::first_use (); } 587 use_count(void)588 std::size_t use_count (void) const { return jit_value::use_count (); } 589 590 // if a block is alive, then it might be visited during execution alive(void)591 bool alive (void) const { return m_alive; } 592 mark_alive(void)593 void mark_alive (void) { m_alive = true; } 594 595 // If we can merge with a successor, do so and return the now empty block 596 jit_block * maybe_merge (); 597 598 // merge another block into this block, leaving the merge block empty 599 void merge (jit_block& merge); 600 name(void)601 const std::string& name (void) const { return m_name; } 602 603 jit_instruction * prepend (jit_instruction *instr); 604 605 jit_instruction * prepend_after_phi (jit_instruction *instr); 606 607 template <typename T> append(T * instr)608 T * append (T *instr) 609 { 610 internal_append (instr); 611 return instr; 612 } 613 614 jit_instruction * insert_before (iterator loc, jit_instruction *instr); 615 insert_before(jit_instruction * loc,jit_instruction * instr)616 jit_instruction * insert_before (jit_instruction *loc, jit_instruction *instr) 617 { 618 return insert_before (loc->location (), instr); 619 } 620 621 jit_instruction * insert_after (iterator loc, jit_instruction *instr); 622 insert_after(jit_instruction * loc,jit_instruction * instr)623 jit_instruction * insert_after (jit_instruction *loc, jit_instruction *instr) 624 { 625 return insert_after (loc->location (), instr); 626 } 627 remove(iterator iter)628 iterator remove (iterator iter) 629 { 630 jit_instruction *instr = *iter; 631 iter = m_instructions.erase (iter); 632 instr->stash_parent (0, m_instructions.end ()); 633 return iter; 634 } 635 636 jit_terminator * terminator (void) const; 637 638 // is the jump from pred alive? 639 bool branch_alive (jit_block *asucc) const; 640 641 jit_block * successor (std::size_t i) const; 642 643 std::size_t successor_count (void) const; 644 begin(void)645 iterator begin (void) { return m_instructions.begin (); } 646 begin(void)647 const_iterator begin (void) const { return m_instructions.begin (); } 648 end(void)649 iterator end (void) { return m_instructions.end (); } 650 end(void)651 const_iterator end (void) const { return m_instructions.end (); } 652 653 iterator phi_begin (void); 654 655 iterator phi_end (void); 656 657 iterator nonphi_begin (void); 658 659 // must label before id is valid id(void)660 std::size_t id (void) const { return m_id; } 661 662 // dominance frontier df(void)663 const df_set& df (void) const { return m_df; } 664 df_begin(void)665 df_iterator df_begin (void) const { return m_df.begin (); } 666 df_end(void)667 df_iterator df_end (void) const { return m_df.end (); } 668 669 // label with a RPO walk label(void)670 void label (void) 671 { 672 std::size_t number = 0; 673 label (m_visit_count, number); 674 } 675 676 void label (std::size_t avisit_count, std::size_t& number); 677 678 // See for idom computation algorithm 679 // Cooper, Keith D.; Harvey, Timothy J; and Kennedy, Ken (2001). 680 // "A Simple, Fast Dominance Algorithm" compute_idom(jit_block & entry_block)681 void compute_idom (jit_block& entry_block) 682 { 683 bool changed; 684 entry_block.m_idom = &entry_block; 685 do 686 changed = update_idom (m_visit_count); 687 while (changed); 688 } 689 690 // compute dominance frontier compute_df(void)691 void compute_df (void) 692 { 693 compute_df (m_visit_count); 694 } 695 create_dom_tree(void)696 void create_dom_tree (void) 697 { 698 create_dom_tree (m_visit_count); 699 } 700 dom_successor(std::size_t idx)701 jit_block * dom_successor (std::size_t idx) const 702 { 703 return m_dom_succ[idx]; 704 } 705 dom_successor_count(void)706 std::size_t dom_successor_count (void) const 707 { 708 return m_dom_succ.size (); 709 } 710 711 // call pop_variable on all instructions 712 void pop_all (void); 713 714 virtual std::ostream& print (std::ostream& os, std::size_t indent = 0) const; 715 716 jit_block * maybe_split (jit_factory& factory, jit_block_list& blocks, 717 jit_block *asuccessor); 718 maybe_split(jit_factory & factory,jit_block_list & blocks,jit_block & asuccessor)719 jit_block * maybe_split (jit_factory& factory, jit_block_list& blocks, 720 jit_block& asuccessor) 721 { 722 return maybe_split (factory, blocks, &asuccessor); 723 } 724 725 // print dominator infomration 726 std::ostream& print_dom (std::ostream& os) const; 727 short_print(std::ostream & os)728 virtual std::ostream& short_print (std::ostream& os) const 729 { 730 os << m_name; 731 if (m_id != NO_ID) 732 os << m_id; 733 else 734 os << '!'; 735 return os; 736 } 737 738 llvm::BasicBlock * to_llvm (void) const; 739 location(void)740 std::list<jit_block *>::iterator location (void) const 741 { return m_location; } 742 stash_location(std::list<jit_block * >::iterator alocation)743 void stash_location (std::list<jit_block *>::iterator alocation) 744 { m_location = alocation; } 745 746 // used to prevent visiting the same node twice in the graph visit_count(void)747 std::size_t visit_count (void) const { return m_visit_count; } 748 749 // check if this node has been visited yet at the given visit count. 750 // If we have not been visited yet, mark us as visited. visited(std::size_t avisit_count)751 bool visited (std::size_t avisit_count) 752 { 753 if (m_visit_count <= avisit_count) 754 { 755 m_visit_count = avisit_count + 1; 756 return false; 757 } 758 759 return true; 760 } 761 front(void)762 jit_instruction * front (void) { return m_instructions.front (); } 763 back(void)764 jit_instruction * back (void) { return m_instructions.back (); } 765 766 JIT_VALUE_ACCEPT; 767 768 private: 769 770 void internal_append (jit_instruction *instr); 771 772 void compute_df (std::size_t avisit_count); 773 774 bool update_idom (std::size_t avisit_count); 775 776 void create_dom_tree (std::size_t avisit_count); 777 778 static jit_block * idom_intersect (jit_block *i, jit_block *j); 779 780 std::size_t m_visit_count; 781 std::size_t m_id; 782 jit_block *m_idom; 783 df_set m_df; 784 std::vector<jit_block *> m_dom_succ; 785 std::string m_name; 786 instruction_list m_instructions; 787 bool m_alive; 788 std::list<jit_block *>::iterator m_location; 789 }; 790 791 // keeps track of phi functions that use a block on incoming edges 792 class 793 jit_phi_incoming : public jit_internal_node<jit_block, jit_phi_incoming> 794 { 795 public: 796 jit_phi_incoming(void)797 jit_phi_incoming (void) : m_user (0) { } 798 jit_phi_incoming(jit_phi * auser)799 jit_phi_incoming (jit_phi *auser) : m_user (auser) { } 800 jit_phi_incoming(const jit_phi_incoming & use)801 jit_phi_incoming (const jit_phi_incoming& use) 802 { 803 *this = use; 804 } 805 806 jit_phi_incoming& operator= (const jit_phi_incoming& use) 807 { 808 stash_value (use.value ()); 809 m_user = use.m_user; 810 return *this; 811 } 812 user(void)813 jit_phi * user (void) const { return m_user; } 814 815 jit_block * user_parent (void) const; 816 817 private: 818 819 jit_phi *m_user; 820 }; 821 822 // A non-ssa variable 823 class 824 jit_variable : public jit_value 825 { 826 public: 827 jit_variable(const std::string & aname)828 jit_variable (const std::string& aname) : m_name (aname), m_last_use (0) { } 829 name(void)830 const std::string& name (void) const { return m_name; } 831 832 // manipulate the value_stack, for use during SSA construction. The top of 833 // the value stack represents the current value for this variable has_top(void)834 bool has_top (void) const 835 { 836 return ! value_stack.empty (); 837 } 838 top(void)839 jit_value * top (void) const 840 { 841 return value_stack.top (); 842 } 843 push(jit_instruction * v)844 void push (jit_instruction *v) 845 { 846 value_stack.push (v); 847 m_last_use = v; 848 } 849 pop(void)850 void pop (void) 851 { 852 value_stack.pop (); 853 } 854 last_use(void)855 jit_instruction * last_use (void) const 856 { 857 return m_last_use; 858 } 859 stash_last_use(jit_instruction * instr)860 void stash_last_use (jit_instruction *instr) 861 { 862 m_last_use = instr; 863 } 864 865 // blocks in which we are used use_blocks(jit_block::df_set & result)866 void use_blocks (jit_block::df_set& result) 867 { 868 jit_use *use = first_use (); 869 while (use) 870 { 871 result.insert (use->user_parent ()); 872 use = use->next (); 873 } 874 } 875 876 virtual std::ostream& print (std::ostream& os, std::size_t indent = 0) const 877 { 878 return print_indent (os, indent) << m_name; 879 } 880 881 JIT_VALUE_ACCEPT; 882 883 private: 884 885 std::string m_name; 886 std::stack<jit_value *> value_stack; 887 jit_instruction *m_last_use; 888 }; 889 890 class 891 jit_assign_base : public jit_instruction 892 { 893 public: 894 jit_assign_base(jit_variable * adest)895 jit_assign_base (jit_variable *adest) 896 : jit_instruction (), m_dest (adest) 897 { } 898 jit_assign_base(jit_variable * adest,std::size_t npred)899 jit_assign_base (jit_variable *adest, std::size_t npred) 900 : jit_instruction (npred), m_dest (adest) 901 { } 902 jit_assign_base(jit_variable * adest,jit_value * arg0,jit_value * arg1)903 jit_assign_base (jit_variable *adest, jit_value *arg0, jit_value *arg1) 904 : jit_instruction (arg0, arg1), m_dest (adest) 905 { } 906 dest(void)907 jit_variable * dest (void) const { return m_dest; } 908 push_variable(void)909 virtual void push_variable (void) 910 { 911 m_dest->push (this); 912 } 913 pop_variable(void)914 virtual void pop_variable (void) 915 { 916 m_dest->pop (); 917 } 918 short_print(std::ostream & os)919 virtual std::ostream& short_print (std::ostream& os) const 920 { 921 if (type ()) 922 jit_print (os, type ()) << ": "; 923 924 dest ()->short_print (os); 925 return os << '#' << id (); 926 } 927 928 private: 929 930 jit_variable *m_dest; 931 }; 932 933 class 934 jit_assign : public jit_assign_base 935 { 936 public: 937 jit_assign(jit_variable * adest,jit_value * asrc)938 jit_assign (jit_variable *adest, jit_value *asrc) 939 : jit_assign_base (adest, adest, asrc), m_artificial (false) 940 { } 941 overwrite(void)942 jit_value * overwrite (void) const 943 { 944 return argument (0); 945 } 946 src(void)947 jit_value * src (void) const 948 { 949 return argument (1); 950 } 951 952 // Variables don't get modified in an SSA, but COW requires we 953 // modify variables. An artificial assign is for when a variable 954 // gets modified. We need an assign in the SSA, but the reference 955 // counts shouldn't be updated. 956 artificial(void)957 bool artificial (void) const { return m_artificial; } 958 mark_artificial(void)959 void mark_artificial (void) { m_artificial = true; } 960 infer(void)961 virtual bool infer (void) 962 { 963 jit_type *stype = src ()->type (); 964 if (stype != type()) 965 { 966 stash_type (stype); 967 return true; 968 } 969 970 return false; 971 } 972 973 virtual std::ostream& print (std::ostream& os, std::size_t indent = 0) const 974 { 975 print_indent (os, indent) << *this << " = " << *src (); 976 977 if (artificial ()) 978 os << " [artificial]"; 979 980 return os; 981 } 982 983 JIT_VALUE_ACCEPT; 984 985 private: 986 987 bool m_artificial; 988 }; 989 990 class 991 jit_phi : public jit_assign_base 992 { 993 public: 994 jit_phi(jit_variable * adest,std::size_t npred)995 jit_phi (jit_variable *adest, std::size_t npred) 996 : jit_assign_base (adest, npred) 997 { 998 m_incoming.reserve (npred); 999 } 1000 1001 // removes arguments form dead incoming jumps 1002 bool prune (void); 1003 add_incoming(jit_block * from,jit_value * value)1004 void add_incoming (jit_block *from, jit_value *value) 1005 { 1006 push_argument (value); 1007 m_incoming.push_back (jit_phi_incoming (this)); 1008 m_incoming[m_incoming.size () - 1].stash_value (from); 1009 } 1010 incoming(std::size_t i)1011 jit_block * incoming (std::size_t i) const 1012 { 1013 return m_incoming[i].value (); 1014 } 1015 incoming_llvm(std::size_t i)1016 llvm::BasicBlock * incoming_llvm (std::size_t i) const 1017 { 1018 return incoming (i)->to_llvm (); 1019 } 1020 construct_ssa(void)1021 virtual void construct_ssa (void) { } 1022 1023 virtual bool infer (void); 1024 1025 virtual std::ostream& print (std::ostream& os, std::size_t indent = 0) const 1026 { 1027 std::stringstream ss; 1028 print_indent (ss, indent); 1029 short_print (ss) << " phi "; 1030 std::string ss_str = ss.str (); 1031 std::string indent_str (ss_str.size (), ' '); 1032 os << ss_str; 1033 1034 for (std::size_t i = 0; i < argument_count (); ++i) 1035 { 1036 if (i > 0) 1037 os << indent_str; 1038 os << "| "; 1039 1040 os << *incoming (i) << " -> "; 1041 os << *argument (i); 1042 1043 if (i + 1 < argument_count ()) 1044 os << std::endl; 1045 } 1046 1047 return os; 1048 } 1049 1050 llvm::PHINode * to_llvm (void) const; 1051 1052 JIT_VALUE_ACCEPT; 1053 1054 private: 1055 1056 std::vector<jit_phi_incoming> m_incoming; 1057 }; 1058 1059 class 1060 jit_terminator : public jit_instruction 1061 { 1062 public: 1063 1064 template <typename ...Args> jit_terminator(std::size_t asuccessor_count,Args...args)1065 jit_terminator (std::size_t asuccessor_count, Args... args) 1066 : jit_instruction (args...), 1067 m_alive (asuccessor_count, false) { } 1068 1069 jit_block * successor (std::size_t idx = 0) const 1070 { 1071 return static_cast<jit_block *> (argument (idx)); 1072 } 1073 1074 llvm::BasicBlock * successor_llvm (std::size_t idx = 0) const 1075 { 1076 return successor (idx)->to_llvm (); 1077 } 1078 1079 std::size_t successor_index (const jit_block *asuccessor) const; 1080 1081 std::ostream& print_successor (std::ostream& os, std::size_t idx = 0) const 1082 { 1083 if (alive (idx)) 1084 os << "[live] "; 1085 else 1086 os << "[dead] "; 1087 1088 return successor (idx)->short_print (os); 1089 } 1090 1091 // Check if the jump to successor is live alive(const jit_block * asuccessor)1092 bool alive (const jit_block *asuccessor) const 1093 { 1094 return alive (successor_index (asuccessor)); 1095 } 1096 alive(std::size_t idx)1097 bool alive (std::size_t idx) const { return m_alive[idx]; } 1098 alive(int idx)1099 bool alive (int idx) const { return m_alive[idx]; } 1100 successor_count(void)1101 std::size_t successor_count (void) const { return m_alive.size (); } 1102 1103 virtual bool infer (void); 1104 1105 llvm::TerminatorInst * to_llvm (void) const; 1106 1107 protected: 1108 check_alive(std::size_t)1109 virtual bool check_alive (std::size_t) const { return true; } 1110 1111 private: 1112 1113 std::vector<bool> m_alive; 1114 }; 1115 1116 class 1117 jit_branch : public jit_terminator 1118 { 1119 public: 1120 jit_branch(jit_block * succ)1121 jit_branch (jit_block *succ) : jit_terminator (1, succ) { } 1122 successor_count(void)1123 virtual std::size_t successor_count (void) const { return 1; } 1124 1125 virtual std::ostream& print (std::ostream& os, std::size_t indent = 0) const 1126 { 1127 print_indent (os, indent) << "branch: "; 1128 return print_successor (os); 1129 } 1130 1131 JIT_VALUE_ACCEPT; 1132 }; 1133 1134 class 1135 jit_cond_branch : public jit_terminator 1136 { 1137 public: 1138 jit_cond_branch(jit_value * c,jit_block * ctrue,jit_block * cfalse)1139 jit_cond_branch (jit_value *c, jit_block *ctrue, jit_block *cfalse) 1140 : jit_terminator (2, ctrue, cfalse, c) { } 1141 cond(void)1142 jit_value * cond (void) const { return argument (2); } 1143 print_cond(std::ostream & os)1144 std::ostream& print_cond (std::ostream& os) const 1145 { 1146 return cond ()->short_print (os); 1147 } 1148 cond_llvm(void)1149 llvm::Value * cond_llvm (void) const 1150 { 1151 return cond ()->to_llvm (); 1152 } 1153 successor_count(void)1154 virtual std::size_t successor_count (void) const { return 2; } 1155 1156 virtual std::ostream& print (std::ostream& os, std::size_t indent = 0) const 1157 { 1158 print_indent (os, indent) << "cond_branch: "; 1159 print_cond (os) << ", "; 1160 print_successor (os, 0) << ", "; 1161 return print_successor (os, 1); 1162 } 1163 1164 JIT_VALUE_ACCEPT; 1165 }; 1166 1167 class 1168 jit_call : public jit_instruction 1169 { 1170 public: 1171 jit_call(const jit_operation & (* aoperation)(void))1172 jit_call (const jit_operation& (*aoperation) (void)) 1173 : m_operation (aoperation ()) 1174 { 1175 const jit_function& ol = overload (); 1176 if (ol.valid ()) 1177 stash_type (ol.result ()); 1178 } 1179 jit_call(const jit_operation & aoperation)1180 jit_call (const jit_operation& aoperation) : m_operation (aoperation) 1181 { 1182 const jit_function& ol = overload (); 1183 if (ol.valid ()) 1184 stash_type (ol.result ()); 1185 } 1186 1187 template <typename ...Args> jit_call(const jit_operation & aoperation,jit_value * arg1,Args...other_args)1188 jit_call (const jit_operation& aoperation, 1189 jit_value * arg1, Args... other_args) 1190 : jit_instruction (arg1, other_args...), m_operation (aoperation) 1191 { } 1192 1193 template <typename ...Args> jit_call(const jit_operation & (* aoperation)(void),jit_value * arg1,Args...other_args)1194 jit_call (const jit_operation& (*aoperation) (void), 1195 jit_value * arg1, Args... other_args) 1196 : jit_instruction (arg1, other_args...), m_operation (aoperation ()) 1197 { } 1198 jit_call(const jit_operation & aoperation,const std::vector<jit_value * > & args)1199 jit_call (const jit_operation& aoperation, 1200 const std::vector<jit_value *>& args) 1201 : jit_instruction (args), m_operation (aoperation) 1202 { } 1203 operation(void)1204 const jit_operation& operation (void) const { return m_operation; } 1205 can_error(void)1206 bool can_error (void) const 1207 { 1208 return overload ().can_error (); 1209 } 1210 overload(void)1211 const jit_function& overload (void) const 1212 { 1213 return m_operation.overload (argument_types ()); 1214 } 1215 1216 virtual bool needs_release (void) const; 1217 1218 virtual std::ostream& print (std::ostream& os, std::size_t indent = 0) const 1219 { 1220 print_indent (os, indent); 1221 1222 if (use_count ()) 1223 short_print (os) << " = "; 1224 os << "call " << m_operation.name () << " ("; 1225 1226 for (std::size_t i = 0; i < argument_count (); ++i) 1227 { 1228 print_argument (os, i); 1229 if (i + 1 < argument_count ()) 1230 os << ", "; 1231 } 1232 return os << ')'; 1233 } 1234 1235 virtual bool infer (void); 1236 1237 JIT_VALUE_ACCEPT; 1238 1239 private: 1240 1241 const jit_operation& m_operation; 1242 }; 1243 1244 // FIXME: This is just ugly... 1245 // checks error_state, if error_state is false then goto the normal branch, 1246 // otherwise goto the error branch 1247 class 1248 jit_error_check : public jit_terminator 1249 { 1250 public: 1251 1252 // Which variable is the error check for? 1253 enum variable 1254 { 1255 var_error_state, 1256 var_interrupt 1257 }; 1258 1259 static std::string variable_to_string (variable v); 1260 jit_error_check(variable var,jit_call * acheck_for,jit_block * normal,jit_block * error)1261 jit_error_check (variable var, jit_call *acheck_for, jit_block *normal, 1262 jit_block *error) 1263 : jit_terminator (2, error, normal, acheck_for), m_variable (var) { } 1264 jit_error_check(variable var,jit_block * normal,jit_block * error)1265 jit_error_check (variable var, jit_block *normal, jit_block *error) 1266 : jit_terminator (2, error, normal), m_variable (var) { } 1267 check_variable(void)1268 variable check_variable (void) const { return m_variable; } 1269 has_check_for(void)1270 bool has_check_for (void) const 1271 { 1272 return argument_count () == 3; 1273 } 1274 check_for(void)1275 jit_call * check_for (void) const 1276 { 1277 assert (has_check_for ()); 1278 return static_cast<jit_call *> (argument (2)); 1279 } 1280 1281 virtual std::ostream& print (std::ostream& os, std::size_t indent = 0) const; 1282 1283 JIT_VALUE_ACCEPT; 1284 1285 protected: 1286 check_alive(std::size_t idx)1287 virtual bool check_alive (std::size_t idx) const 1288 { 1289 if (! has_check_for ()) 1290 return true; 1291 return idx == 1 ? true : check_for ()->can_error (); 1292 } 1293 1294 private: 1295 1296 variable m_variable; 1297 }; 1298 1299 // for now only handles the 1D case 1300 class 1301 jit_magic_end : public jit_instruction 1302 { 1303 public: 1304 1305 class 1306 context 1307 { 1308 public: 1309 context(void)1310 context (void) : m_value (0), m_index (0), m_count (0) { } 1311 1312 context (jit_factory& factory, jit_value *avalue, std::size_t aindex, 1313 std::size_t acount); 1314 1315 jit_value *m_value; 1316 jit_const_index *m_index; 1317 jit_const_index *m_count; 1318 }; 1319 1320 jit_magic_end (const std::vector<context>& full_context); 1321 1322 virtual bool infer (void); 1323 1324 const jit_function& overload () const; 1325 1326 virtual std::ostream& print (std::ostream& os, std::size_t indent = 0) const; 1327 1328 context resolve_context (void) const; 1329 short_print(std::ostream & os)1330 virtual std::ostream& short_print (std::ostream& os) const 1331 { 1332 return os << "magic_end" << '#' << id (); 1333 } 1334 1335 JIT_VALUE_ACCEPT; 1336 1337 private: 1338 1339 std::vector<context> m_contexts; 1340 }; 1341 1342 class 1343 jit_extract_argument : public jit_assign_base 1344 { 1345 public: 1346 jit_extract_argument(jit_type * atype,jit_variable * adest)1347 jit_extract_argument (jit_type *atype, jit_variable *adest) 1348 : jit_assign_base (adest) 1349 { 1350 stash_type (atype); 1351 } 1352 name(void)1353 const std::string& name (void) const 1354 { 1355 return dest ()->name (); 1356 } 1357 overload(void)1358 const jit_function& overload (void) const 1359 { 1360 return jit_typeinfo::cast (type (), jit_typeinfo::get_any ()); 1361 } 1362 1363 virtual std::ostream& print (std::ostream& os, std::size_t indent = 0) const 1364 { 1365 print_indent (os, indent); 1366 1367 return short_print (os) << " = extract " << name (); 1368 } 1369 1370 JIT_VALUE_ACCEPT; 1371 }; 1372 1373 class 1374 jit_store_argument : public jit_instruction 1375 { 1376 public: 1377 jit_store_argument(jit_variable * var)1378 jit_store_argument (jit_variable *var) 1379 : jit_instruction (var), m_dest (var) 1380 { } 1381 name(void)1382 const std::string& name (void) const 1383 { 1384 return m_dest->name (); 1385 } 1386 overload(void)1387 const jit_function& overload (void) const 1388 { 1389 return jit_typeinfo::cast (jit_typeinfo::get_any (), result_type ()); 1390 } 1391 result(void)1392 jit_value * result (void) const 1393 { 1394 return argument (0); 1395 } 1396 result_type(void)1397 jit_type * result_type (void) const 1398 { 1399 return result ()->type (); 1400 } 1401 result_llvm(void)1402 llvm::Value * result_llvm (void) const 1403 { 1404 return result ()->to_llvm (); 1405 } 1406 1407 virtual std::ostream& print (std::ostream& os, std::size_t indent = 0) const 1408 { 1409 jit_value *res = result (); 1410 print_indent (os, indent) << "store "; 1411 m_dest->short_print (os); 1412 1413 if (! isa<jit_variable> (res)) 1414 { 1415 os << " = "; 1416 res->short_print (os); 1417 } 1418 1419 return os; 1420 } 1421 1422 JIT_VALUE_ACCEPT; 1423 1424 private: 1425 1426 jit_variable *m_dest; 1427 }; 1428 1429 class 1430 jit_return : public jit_instruction 1431 { 1432 public: 1433 jit_return(void)1434 jit_return (void) { } 1435 jit_return(jit_value * retval)1436 jit_return (jit_value *retval) : jit_instruction (retval) { } 1437 result(void)1438 jit_value * result (void) const 1439 { 1440 return argument_count () ? argument (0) : nullptr; 1441 } 1442 result_type(void)1443 jit_type * result_type (void) const 1444 { 1445 jit_value *res = result (); 1446 return res ? res->type () : nullptr; 1447 } 1448 1449 virtual std::ostream& print (std::ostream& os, std::size_t indent = 0) const 1450 { 1451 print_indent (os, indent) << "return"; 1452 1453 if (result ()) 1454 os << ' ' << *result (); 1455 1456 return os; 1457 } 1458 1459 JIT_VALUE_ACCEPT; 1460 }; 1461 1462 class 1463 jit_ir_walker 1464 { 1465 public: 1466 ~jit_ir_walker(void)1467 virtual ~jit_ir_walker (void) { } 1468 1469 #define JIT_METH(clname) \ 1470 virtual void visit (jit_ ## clname&) = 0; 1471 1472 JIT_VISIT_IR_CLASSES; 1473 1474 #undef JIT_METH 1475 }; 1476 1477 template <typename T, jit_type *(*EXTRACT_T)(void), typename PASS_T, bool QUOTE> 1478 void accept(jit_ir_walker & walker)1479 jit_const<T, EXTRACT_T, PASS_T, QUOTE>::accept (jit_ir_walker& walker) 1480 { 1481 walker.visit (*this); 1482 } 1483 1484 #undef JIT_VALUE_ACCEPT 1485 } 1486 1487 #endif 1488 1489 #endif 1490