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 // defines required by llvm 27 #define __STDC_LIMIT_MACROS 28 #define __STDC_CONSTANT_MACROS 29 30 #if defined (HAVE_CONFIG_H) 31 # include "config.h" 32 #endif 33 34 #if defined (HAVE_LLVM) 35 36 #include "jit-ir.h" 37 38 #if defined (HAVE_LLVM_IR_FUNCTION_H) 39 # include <llvm/IR/BasicBlock.h> 40 # include <llvm/IR/Instructions.h> 41 #else 42 # include <llvm/BasicBlock.h> 43 # include <llvm/Instructions.h> 44 #endif 45 46 #include "error.h" 47 48 namespace octave 49 { 50 51 // -------------------- jit_factory -------------------- ~jit_factory(void)52 jit_factory::~jit_factory (void) 53 { 54 for (auto iter = m_all_values.begin (); 55 iter != m_all_values.end (); ++iter) 56 delete *iter; 57 } 58 59 void track_value(jit_value * value)60 jit_factory::track_value (jit_value *value) 61 { 62 if (value->type ()) 63 m_constants.push_back (value); 64 m_all_values.push_back (value); 65 } 66 67 // -------------------- jit_block_list -------------------- 68 void insert_after(iterator iter,jit_block * ablock)69 jit_block_list::insert_after (iterator iter, jit_block *ablock) 70 { 71 ++iter; 72 insert_before (iter, ablock); 73 } 74 75 void insert_after(jit_block * loc,jit_block * ablock)76 jit_block_list::insert_after (jit_block *loc, jit_block *ablock) 77 { 78 insert_after (loc->location (), ablock); 79 } 80 81 void insert_before(iterator iter,jit_block * ablock)82 jit_block_list::insert_before (iterator iter, jit_block *ablock) 83 { 84 iter = m_list.insert (iter, ablock); 85 ablock->stash_location (iter); 86 } 87 88 void insert_before(jit_block * loc,jit_block * ablock)89 jit_block_list::insert_before (jit_block *loc, jit_block *ablock) 90 { 91 insert_before (loc->location (), ablock); 92 } 93 94 void label(void)95 jit_block_list::label (void) 96 { 97 if (m_list.size ()) 98 { 99 jit_block *block = m_list.back (); 100 block->label (); 101 } 102 } 103 104 std::ostream& print(std::ostream & os,const std::string & header) const105 jit_block_list::print (std::ostream& os, const std::string& header) const 106 { 107 os << "-------------------- " << header << " --------------------\n"; 108 return os << *this; 109 } 110 111 std::ostream& print_dom(std::ostream & os) const112 jit_block_list::print_dom (std::ostream& os) const 113 { 114 os << "-------------------- dom info --------------------\n"; 115 for (auto iter = begin (); iter != end (); ++iter) 116 { 117 assert (*iter); 118 (*iter)->print_dom (os); 119 } 120 os << std::endl; 121 122 return os; 123 } 124 125 void push_back(jit_block * b)126 jit_block_list::push_back (jit_block *b) 127 { 128 m_list.push_back (b); 129 auto iter = m_list.end (); 130 b->stash_location (--iter); 131 } 132 133 std::ostream& operator <<(std::ostream & os,const jit_block_list & blocks)134 operator<<(std::ostream& os, const jit_block_list& blocks) 135 { 136 for (auto iter = blocks.begin (); iter != blocks.end (); ++iter) 137 { 138 assert (*iter); 139 (*iter)->print (os, 0); 140 } 141 return os << std::endl; 142 } 143 144 // -------------------- jit_use -------------------- 145 jit_block * user_parent(void) const146 jit_use::user_parent (void) const 147 { 148 return m_user->parent (); 149 } 150 151 // -------------------- jit_value -------------------- ~jit_value(void)152 jit_value::~jit_value (void) 153 { } 154 155 jit_block * first_use_block(void)156 jit_value::first_use_block (void) 157 { 158 jit_use *use = first_use (); 159 while (use) 160 { 161 if (! isa<jit_error_check> (use->user ())) 162 return use->user_parent (); 163 164 use = use->next (); 165 } 166 167 return 0; 168 } 169 170 void replace_with(jit_value * value)171 jit_value::replace_with (jit_value *value) 172 { 173 while (first_use ()) 174 { 175 jit_instruction *user = first_use ()->user (); 176 std::size_t idx = first_use ()->index (); 177 user->stash_argument (idx, value); 178 } 179 } 180 181 #define JIT_METH(clname) \ 182 void \ 183 jit_ ## clname::accept (jit_ir_walker& walker) \ 184 { \ 185 walker.visit (*this); \ 186 } 187 188 JIT_VISIT_IR_NOTEMPLATE 189 #undef JIT_METH 190 191 std::ostream& operator <<(std::ostream & os,const jit_value & value)192 operator<< (std::ostream& os, const jit_value& value) 193 { 194 return value.short_print (os); 195 } 196 197 std::ostream& jit_print(std::ostream & os,jit_value * avalue)198 jit_print (std::ostream& os, jit_value *avalue) 199 { 200 if (avalue) 201 return avalue->print (os); 202 return os << "NULL"; 203 } 204 205 // -------------------- jit_instruction -------------------- 206 void remove(void)207 jit_instruction::remove (void) 208 { 209 if (m_parent) 210 m_parent->remove (m_location); 211 resize_arguments (0); 212 } 213 214 llvm::BasicBlock * parent_llvm(void) const215 jit_instruction::parent_llvm (void) const 216 { 217 return m_parent->to_llvm (); 218 } 219 220 std::ostream& short_print(std::ostream & os) const221 jit_instruction::short_print (std::ostream& os) const 222 { 223 if (type ()) 224 jit_print (os, type ()) << ": "; 225 return os << '#' << m_id; 226 } 227 228 void do_construct_ssa(std::size_t start,std::size_t end)229 jit_instruction::do_construct_ssa (std::size_t start, std::size_t end) 230 { 231 for (std::size_t i = start; i < end; ++i) 232 { 233 jit_value *arg = argument (i); 234 jit_variable *var = dynamic_cast<jit_variable *> (arg); 235 if (var && var->has_top ()) 236 stash_argument (i, var->top ()); 237 } 238 } 239 240 // -------------------- jit_block -------------------- 241 void replace_with(jit_value * value)242 jit_block::replace_with (jit_value *value) 243 { 244 assert (isa<jit_block> (value)); 245 jit_block *block = static_cast<jit_block *> (value); 246 247 jit_value::replace_with (block); 248 249 while (ILIST_T::first_use ()) 250 { 251 jit_phi_incoming *incoming = ILIST_T::first_use (); 252 incoming->stash_value (block); 253 } 254 } 255 256 void replace_in_phi(jit_block * ablock,jit_block * with)257 jit_block::replace_in_phi (jit_block *ablock, jit_block *with) 258 { 259 jit_phi_incoming *node = ILIST_T::first_use (); 260 while (node) 261 { 262 jit_phi_incoming *prev = node; 263 node = node->next (); 264 265 if (prev->user_parent () == ablock) 266 prev->stash_value (with); 267 } 268 } 269 270 jit_block * maybe_merge(void)271 jit_block::maybe_merge (void) 272 { 273 if (successor_count () == 1 && successor (0) != this 274 && (successor (0)->use_count () == 1 || m_instructions.size () == 1)) 275 { 276 jit_block *to_merge = successor (0); 277 merge (*to_merge); 278 return to_merge; 279 } 280 281 return 0; 282 } 283 284 void merge(jit_block & block)285 jit_block::merge (jit_block& block) 286 { 287 // the merge block will contain a new terminator 288 jit_terminator *old_term = terminator (); 289 if (old_term) 290 old_term->remove (); 291 292 bool was_empty = end () == begin (); 293 auto merge_begin = end (); 294 if (! was_empty) 295 --merge_begin; 296 297 m_instructions.splice (end (), block.m_instructions); 298 if (was_empty) 299 merge_begin = begin (); 300 else 301 ++merge_begin; 302 303 // now merge_begin points to the start of the new instructions, we must 304 // update their parent information 305 for (auto iter = merge_begin; iter != end (); ++iter) 306 { 307 jit_instruction *instr = *iter; 308 instr->stash_parent (this, iter); 309 } 310 311 block.replace_with (this); 312 } 313 314 jit_instruction * prepend(jit_instruction * instr)315 jit_block::prepend (jit_instruction *instr) 316 { 317 m_instructions.push_front (instr); 318 instr->stash_parent (this, m_instructions.begin ()); 319 return instr; 320 } 321 322 jit_instruction * prepend_after_phi(jit_instruction * instr)323 jit_block::prepend_after_phi (jit_instruction *instr) 324 { 325 // FIXME: Make this O(1) 326 for (auto iter = begin (); iter != end (); ++iter) 327 { 328 jit_instruction *temp = *iter; 329 if (! isa<jit_phi> (temp)) 330 { 331 insert_before (iter, instr); 332 return instr; 333 } 334 } 335 336 return append (instr); 337 } 338 339 void internal_append(jit_instruction * instr)340 jit_block::internal_append (jit_instruction *instr) 341 { 342 m_instructions.push_back (instr); 343 instr->stash_parent (this, --m_instructions.end ()); 344 } 345 346 jit_instruction * insert_before(iterator loc,jit_instruction * instr)347 jit_block::insert_before (iterator loc, jit_instruction *instr) 348 { 349 auto iloc = m_instructions.insert (loc, instr); 350 instr->stash_parent (this, iloc); 351 return instr; 352 } 353 354 jit_instruction * insert_after(iterator loc,jit_instruction * instr)355 jit_block::insert_after (iterator loc, jit_instruction *instr) 356 { 357 ++loc; 358 auto iloc = m_instructions.insert (loc, instr); 359 instr->stash_parent (this, iloc); 360 return instr; 361 } 362 363 jit_terminator * terminator(void) const364 jit_block::terminator (void) const 365 { 366 if (m_instructions.empty ()) 367 return nullptr; 368 369 jit_instruction *last = m_instructions.back (); 370 return dynamic_cast<jit_terminator *> (last); 371 } 372 373 bool branch_alive(jit_block * asucc) const374 jit_block::branch_alive (jit_block *asucc) const 375 { 376 return terminator ()->alive (asucc); 377 } 378 379 jit_block * successor(std::size_t i) const380 jit_block::successor (std::size_t i) const 381 { 382 jit_terminator *term = terminator (); 383 return term->successor (i); 384 } 385 386 std::size_t successor_count(void) const387 jit_block::successor_count (void) const 388 { 389 jit_terminator *term = terminator (); 390 return term ? term->successor_count () : 0; 391 } 392 393 llvm::BasicBlock * to_llvm(void) const394 jit_block::to_llvm (void) const 395 { 396 return llvm::cast<llvm::BasicBlock> (m_llvm_value); 397 } 398 399 std::ostream& print_dom(std::ostream & os) const400 jit_block::print_dom (std::ostream& os) const 401 { 402 short_print (os); 403 os << ":\n"; 404 os << " m_id: " << m_id << std::endl; 405 os << " predecessors: "; 406 for (jit_use *use = first_use (); use; use = use->next ()) 407 os << *use->user_parent () << ' '; 408 os << std::endl; 409 410 os << " successors: "; 411 for (std::size_t i = 0; i < successor_count (); ++i) 412 os << *successor (i) << ' '; 413 os << std::endl; 414 415 os << " m_idom: "; 416 if (m_idom) 417 os << *m_idom; 418 else 419 os << "NULL"; 420 os << std::endl; 421 os << " df: "; 422 for (auto iter = df_begin (); iter != df_end (); ++iter) 423 os << **iter << ' '; 424 os << std::endl; 425 426 os << " m_dom_succ: "; 427 for (std::size_t i = 0; i < m_dom_succ.size (); ++i) 428 os << *m_dom_succ[i] << ' '; 429 430 return os << std::endl; 431 } 432 433 void compute_df(std::size_t avisit_count)434 jit_block::compute_df (std::size_t avisit_count) 435 { 436 if (visited (avisit_count)) 437 return; 438 439 if (use_count () >= 2) 440 { 441 for (jit_use *use = first_use (); use; use = use->next ()) 442 { 443 jit_block *runner = use->user_parent (); 444 while (runner != m_idom) 445 { 446 runner->m_df.insert (this); 447 runner = runner->m_idom; 448 } 449 } 450 } 451 452 for (std::size_t i = 0; i < successor_count (); ++i) 453 successor (i)->compute_df (avisit_count); 454 } 455 456 bool update_idom(std::size_t avisit_count)457 jit_block::update_idom (std::size_t avisit_count) 458 { 459 if (visited (avisit_count) || ! use_count ()) 460 return false; 461 462 bool changed = false; 463 for (jit_use *use = first_use (); use; use = use->next ()) 464 { 465 jit_block *pred = use->user_parent (); 466 changed = pred->update_idom (avisit_count) || changed; 467 } 468 469 jit_use *use = first_use (); 470 jit_block *new_idom = use->user_parent (); 471 use = use->next (); 472 473 for (; use; use = use->next ()) 474 { 475 jit_block *pred = use->user_parent (); 476 jit_block *pidom = pred->m_idom; 477 if (pidom) 478 new_idom = idom_intersect (pidom, new_idom); 479 } 480 481 if (m_idom != new_idom) 482 { 483 m_idom = new_idom; 484 return true; 485 } 486 487 return changed; 488 } 489 490 void label(std::size_t avisit_count,std::size_t & number)491 jit_block::label (std::size_t avisit_count, std::size_t& number) 492 { 493 if (visited (avisit_count)) 494 return; 495 496 for (jit_use *use = first_use (); use; use = use->next ()) 497 { 498 jit_block *pred = use->user_parent (); 499 pred->label (avisit_count, number); 500 } 501 502 m_id = number++; 503 } 504 505 void pop_all(void)506 jit_block::pop_all (void) 507 { 508 for (auto iter = begin (); iter != end (); ++iter) 509 { 510 jit_instruction *instr = *iter; 511 instr->pop_variable (); 512 } 513 } 514 515 std::ostream& print(std::ostream & os,std::size_t indent) const516 jit_block::print (std::ostream& os, std::size_t indent) const 517 { 518 print_indent (os, indent); 519 short_print (os) << ": %pred = "; 520 for (jit_use *use = first_use (); use; use = use->next ()) 521 { 522 jit_block *pred = use->user_parent (); 523 os << *pred; 524 if (use->next ()) 525 os << ", "; 526 } 527 os << std::endl; 528 529 for (auto iter = begin (); iter != end (); ++iter) 530 { 531 jit_instruction *instr = *iter; 532 instr->print (os, indent + 1) << std::endl; 533 } 534 return os; 535 } 536 537 jit_block * maybe_split(jit_factory & factory,jit_block_list & blocks,jit_block * asuccessor)538 jit_block::maybe_split (jit_factory& factory, jit_block_list& blocks, 539 jit_block *asuccessor) 540 { 541 if (successor_count () > 1) 542 { 543 jit_terminator *term = terminator (); 544 std::size_t idx = term->successor_index (asuccessor); 545 jit_block *split = factory.create<jit_block> ("phi_split", m_visit_count); 546 547 // place after this to ensure define before use in the blocks list 548 blocks.insert_after (this, split); 549 550 term->stash_argument (idx, split); 551 jit_branch *br = split->append (factory.create<jit_branch> (asuccessor)); 552 replace_in_phi (asuccessor, split); 553 554 if (alive ()) 555 { 556 split->mark_alive (); 557 br->infer (); 558 } 559 560 return split; 561 } 562 563 return this; 564 } 565 566 void create_dom_tree(std::size_t avisit_count)567 jit_block::create_dom_tree (std::size_t avisit_count) 568 { 569 if (visited (avisit_count)) 570 return; 571 572 if (m_idom != this) 573 m_idom->m_dom_succ.push_back (this); 574 575 for (std::size_t i = 0; i < successor_count (); ++i) 576 successor (i)->create_dom_tree (avisit_count); 577 } 578 579 jit_block * idom_intersect(jit_block * i,jit_block * j)580 jit_block::idom_intersect (jit_block *i, jit_block *j) 581 { 582 while (i && j && i != j) 583 { 584 while (i && i->id () > j->id ()) 585 i = i->m_idom; 586 587 while (i && j && j->id () > i->id ()) 588 j = j->m_idom; 589 } 590 591 return i ? i : j; 592 } 593 594 // -------------------- jit_phi_incoming -------------------- 595 596 jit_block * user_parent(void) const597 jit_phi_incoming::user_parent (void) const 598 { return m_user->parent (); } 599 600 // -------------------- jit_phi -------------------- 601 bool prune(void)602 jit_phi::prune (void) 603 { 604 jit_block *p = parent (); 605 std::size_t new_idx = 0; 606 jit_value *unique = argument (1); 607 608 for (std::size_t i = 0; i < argument_count (); ++i) 609 { 610 jit_block *inc = incoming (i); 611 if (inc->branch_alive (p)) 612 { 613 if (unique != argument (i)) 614 unique = 0; 615 616 if (new_idx != i) 617 { 618 stash_argument (new_idx, argument (i)); 619 m_incoming[new_idx].stash_value (inc); 620 } 621 622 ++new_idx; 623 } 624 } 625 626 if (new_idx != argument_count ()) 627 { 628 resize_arguments (new_idx); 629 m_incoming.resize (new_idx); 630 } 631 632 assert (argument_count () > 0); 633 if (unique) 634 { 635 replace_with (unique); 636 return true; 637 } 638 639 return false; 640 } 641 642 bool infer(void)643 jit_phi::infer (void) 644 { 645 jit_block *p = parent (); 646 if (! p->alive ()) 647 return false; 648 649 jit_type *infered = nullptr; 650 for (std::size_t i = 0; i < argument_count (); ++i) 651 { 652 jit_block *inc = incoming (i); 653 if (inc->branch_alive (p)) 654 infered = jit_type_join (infered, argument_type (i)); 655 } 656 657 if (infered != type ()) 658 { 659 stash_type (infered); 660 return true; 661 } 662 663 return false; 664 } 665 666 llvm::PHINode * to_llvm(void) const667 jit_phi::to_llvm (void) const 668 { 669 return llvm::cast<llvm::PHINode> (jit_value::to_llvm ()); 670 } 671 672 // -------------------- jit_terminator -------------------- 673 std::size_t successor_index(const jit_block * asuccessor) const674 jit_terminator::successor_index (const jit_block *asuccessor) const 675 { 676 std::size_t scount = successor_count (); 677 for (std::size_t i = 0; i < scount; ++i) 678 if (successor (i) == asuccessor) 679 return i; 680 681 panic_impossible (); 682 } 683 684 bool infer(void)685 jit_terminator::infer (void) 686 { 687 if (! parent ()->alive ()) 688 return false; 689 690 bool changed = false; 691 for (std::size_t i = 0; i < m_alive.size (); ++i) 692 if (! m_alive[i] && check_alive (i)) 693 { 694 changed = true; 695 m_alive[i] = true; 696 successor (i)->mark_alive (); 697 } 698 699 return changed; 700 } 701 702 llvm::TerminatorInst * to_llvm(void) const703 jit_terminator::to_llvm (void) const 704 { 705 return llvm::cast<llvm::TerminatorInst> (jit_value::to_llvm ()); 706 } 707 708 // -------------------- jit_call -------------------- 709 bool needs_release(void) const710 jit_call::needs_release (void) const 711 { 712 if (type () && jit_typeinfo::get_release (type ()).valid ()) 713 { 714 for (jit_use *use = first_use (); use; use = use->next ()) 715 { 716 jit_assign *assign = dynamic_cast<jit_assign *> (use->user ()); 717 if (assign && assign->artificial ()) 718 return false; 719 } 720 721 return true; 722 } 723 return false; 724 } 725 726 bool infer(void)727 jit_call::infer (void) 728 { 729 // FIXME: explain algorithm 730 for (std::size_t i = 0; i < argument_count (); ++i) 731 { 732 m_already_infered[i] = argument_type (i); 733 if (! m_already_infered[i]) 734 return false; 735 } 736 737 jit_type *infered = m_operation.result (m_already_infered); 738 if (! infered && use_count ()) 739 { 740 std::stringstream ss; 741 ss << "Missing overload in type inference for "; 742 print (ss, 0); 743 throw jit_fail_exception (ss.str ()); 744 } 745 746 if (infered != type ()) 747 { 748 stash_type (infered); 749 return true; 750 } 751 752 return false; 753 } 754 755 // -------------------- jit_error_check -------------------- 756 std::string variable_to_string(variable v)757 jit_error_check::variable_to_string (variable v) 758 { 759 switch (v) 760 { 761 case var_error_state: 762 return "error_state"; 763 case var_interrupt: 764 return "interrupt"; 765 default: 766 panic_impossible (); 767 } 768 } 769 770 std::ostream& print(std::ostream & os,std::size_t indent) const771 jit_error_check::print (std::ostream& os, std::size_t indent) const 772 { 773 print_indent (os, indent) << "error_check " << variable_to_string (m_variable) 774 << ", "; 775 776 if (has_check_for ()) 777 os << "<for> " << *check_for () << ", "; 778 print_successor (os << "<normal> ", 1) << ", "; 779 return print_successor (os << "<error> ", 0); 780 } 781 782 // -------------------- jit_magic_end -------------------- context(jit_factory & factory,jit_value * avalue,std::size_t aindex,std::size_t acount)783 jit_magic_end::context::context (jit_factory& factory, jit_value *avalue, 784 std::size_t aindex, std::size_t acount) 785 : m_value (avalue), m_index (factory.create<jit_const_index> (aindex)), 786 m_count (factory.create<jit_const_index> (acount)) 787 { } 788 jit_magic_end(const std::vector<context> & full_context)789 jit_magic_end::jit_magic_end (const std::vector<context>& full_context) 790 : m_contexts (full_context) 791 { 792 resize_arguments (m_contexts.size ()); 793 794 std::size_t i; 795 std::vector<context>::const_iterator iter; 796 for (iter = m_contexts.begin (), i = 0; iter != m_contexts.end (); ++iter, ++i) 797 stash_argument (i, iter->m_value); 798 } 799 800 jit_magic_end::context resolve_context(void) const801 jit_magic_end::resolve_context (void) const 802 { 803 std::size_t idx; 804 for (idx = 0; idx < m_contexts.size (); ++idx) 805 { 806 jit_type *ctx_type = m_contexts[idx].m_value->type (); 807 if (! ctx_type || ctx_type->skip_paren ()) 808 break; 809 } 810 811 if (idx >= m_contexts.size ()) 812 idx = 0; 813 814 context ret = m_contexts[idx]; 815 ret.m_value = argument (idx); 816 return ret; 817 } 818 819 bool infer(void)820 jit_magic_end::infer (void) 821 { 822 jit_type *new_type = overload ().result (); 823 if (new_type != type ()) 824 { 825 stash_type (new_type); 826 return true; 827 } 828 829 return false; 830 } 831 832 std::ostream& print(std::ostream & os,std::size_t indent) const833 jit_magic_end::print (std::ostream& os, std::size_t indent) const 834 { 835 context ctx = resolve_context (); 836 short_print (print_indent (os, indent)) << " (" << *ctx.m_value << ", "; 837 return os << *ctx.m_index << ", " << *ctx.m_count << ')'; 838 } 839 840 const jit_function& overload(void) const841 jit_magic_end::overload (void) const 842 { 843 const context& ctx = resolve_context (); 844 return jit_typeinfo::end (ctx.m_value, ctx.m_index, ctx.m_count); 845 } 846 847 } 848 849 #endif 850