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