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
pt-jit.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 <[email protected]>
24 
25 #define __STDC_LIMIT_MACROS
26 #define __STDC_CONSTANT_MACROS
27 
28 #ifdef HAVE_CONFIG_H
29 #include <config.h>
30 #endif
31 
32 #include "debug.h"
33 #include "defun.h"
34 #include "ov.h"
35 #include "pt-all.h"
36 #include "pt-jit.h"
37 #include "sighandlers.h"
38 #include "symtab.h"
39 #include "variables.h"
40 
41 #ifdef HAVE_LLVM
42 
43 static bool Vdebug_jit = false;
44 
45 static bool Vjit_enable = false;
46 
47 static int Vjit_startcnt = 1000;
48 
49 #include <llvm/Analysis/CallGraph.h>
50 #include <llvm/Analysis/Passes.h>
51 #include <llvm/Analysis/Verifier.h>
52 #include <llvm/Bitcode/ReaderWriter.h>
53 #include <llvm/ExecutionEngine/ExecutionEngine.h>
54 #include <llvm/ExecutionEngine/JIT.h>
55 #include <llvm/PassManager.h>
56 
57 #ifdef HAVE_LLVM_IR_FUNCTION_H
58 #include <llvm/IR/LLVMContext.h>
59 #include <llvm/IR/Module.h>
60 #else
61 #include <llvm/LLVMContext.h>
62 #include <llvm/Module.h>
63 #endif
64 
65 #ifdef HAVE_LLVM_SUPPORT_IRBUILDER_H
66 #include <llvm/Support/IRBuilder.h>
67 #elif defined(HAVE_LLVM_IR_IRBUILDER_H)
68 #include <llvm/IR/IRBuilder.h>
69 #else
70 #include <llvm/IRBuilder.h>
71 #endif
72 
73 #include <llvm/Support/raw_os_ostream.h>
74 #include <llvm/Support/TargetSelect.h>
75 
76 #ifdef HAVE_LLVM_IR_DATALAYOUT_H
77 #include <llvm/IR/DataLayout.h>
78 #elif defined(HAVE_LLVM_DATALAYOUT_H)
79 #include <llvm/DataLayout.h>
80 #else
81 #include <llvm/Target/TargetData.h>
82 #endif
83 
84 #include <llvm/Transforms/IPO.h>
85 #include <llvm/Transforms/Scalar.h>
86 
87 static llvm::IRBuilder<> builder (llvm::getGlobalContext ());
88 
89 static llvm::LLVMContext& context = llvm::getGlobalContext ();
90 
91 // -------------------- jit_break_exception --------------------
92 
93 // jit_break is thrown whenever a branch we are converting has only breaks or
94 // continues. This is because all code that follows a break or continue is dead.
95 class jit_break_exception : public std::exception {};
96 
97 // -------------------- jit_convert --------------------
99  : converting_function (false)
100 {
102 
103  if (for_bounds)
104  create_variable (next_for_bounds (false), for_bounds);
105 
106  try
107  {
108  visit (tee);
109  }
110  catch (const jit_break_exception&)
111  { }
112 
113  // breaks must have been handled by the top level loop
114  assert (breaks.empty ());
115  assert (continues.empty ());
116 
119 
120  for (variable_map::iterator iter = vmap.begin (); iter != vmap.end (); ++iter)
121  {
122  jit_variable *var = iter->second;
123  const std::string& name = var->name ();
124  if (name.size () && name[0] != '#')
126  }
127 
129 }
130 
132  const std::vector<jit_type *>& args)
133  : converting_function (true)
134 {
135  initialize (fcn.scope ());
136 
137  tree_parameter_list *plist = fcn.parameter_list ();
138  tree_parameter_list *rlist = fcn.return_list ();
139  if (plist && plist->takes_varargs ())
140  throw jit_fail_exception ("varags not supported");
141 
142  if (rlist && (rlist->size () > 1 || rlist->takes_varargs ()))
143  throw jit_fail_exception ("multiple returns not supported");
144 
145  if (plist)
146  {
147  tree_parameter_list::iterator piter = plist->begin ();
148  for (size_t i = 0; i < args.size (); ++i, ++piter)
149  {
150  if (piter == plist->end ())
151  throw jit_fail_exception ("Too many parameter to function");
152 
153  tree_decl_elt *elt = *piter;
154  std::string name = elt->name ();
155  create_variable (name, args[i]);
156  }
157  }
158 
159  jit_value *return_value = 0;
160  bool all_breaking = false;
161  if (fcn.is_special_expr ())
162  {
163  tree_expression *expr = fcn.special_expr ();
164  if (expr)
165  {
166  jit_variable *retvar = get_variable ("#return");
167  jit_value *retval;
168  try
169  {
170  retval = visit (expr);
171  }
172  catch (const jit_break_exception&)
173  { }
174 
175  if (breaks.size () || continues.size ())
176  throw jit_fail_exception ("break/continue not supported in "
177  "anonymous functions");
178 
179  block->append (factory.create<jit_assign> (retvar, retval));
180  return_value = retvar;
181  }
182  }
183  else
184  {
185  try
186  {
187  visit_statement_list (*fcn.body ());
188  }
189  catch (const jit_break_exception&)
190  {
191  all_breaking = true;
192  }
193 
194  // the user may use break or continue to exit the function
197  }
198 
199  if (! all_breaking)
201 
203  block = final_block;
204 
205  if (! return_value && rlist && rlist->size () == 1)
206  {
207  tree_decl_elt *elt = rlist->front ();
208  return_value = get_variable (elt->name ());
209  }
210 
211  // FIXME: We should use live range analysis to delete variables where needed.
212  // For now we just delete everything at the end of the function.
213  for (variable_map::iterator iter = vmap.begin (); iter != vmap.end (); ++iter)
214  {
215  if (iter->second != return_value)
216  {
217  jit_call *call;
219  iter->second);
220  final_block->append (call);
221  }
222  }
223 
224  if (return_value)
225  final_block->append (factory.create<jit_return> (return_value));
226  else
228 }
229 
230 void
232 {
233  throw jit_fail_exception ();
234 }
235 
236 void
238 {
239  throw jit_fail_exception ();
240 }
241 
242 void
244 {
246  {
248  boole = dynamic_cast<tree_boolean_expression *> (&be);
249  assert (boole);
250  bool is_and = boole->op_type () == tree_boolean_expression::bool_and;
251 
252  std::string short_name = next_shortcircut_result ();
253  jit_variable *short_result = factory.create<jit_variable> (short_name);
254  vmap[short_name] = short_result;
255 
256  jit_block *done = factory.create<jit_block> (block->name ());
257  tree_expression *lhs = be.lhs ();
258  jit_value *lhsv = visit (lhs);
260 
261  jit_block *short_early = factory.create<jit_block> ("short_early");
262  blocks.push_back (short_early);
263 
264  jit_block *short_cont = factory.create<jit_block> ("short_cont");
265 
266  if (is_and)
267  block->append (factory.create<jit_cond_branch> (lhsv, short_cont,
268  short_early));
269  else
270  block->append (factory.create<jit_cond_branch> (lhsv, short_early,
271  short_cont));
272 
273  block = short_early;
274 
275  jit_value *early_result = factory.create<jit_const_bool> (! is_and);
276  block->append (factory.create<jit_assign> (short_result, early_result));
277  block->append (factory.create<jit_branch> (done));
278 
279  blocks.push_back (short_cont);
280  block = short_cont;
281 
282  tree_expression *rhs = be.rhs ();
283  jit_value *rhsv = visit (rhs);
285  block->append (factory.create<jit_assign> (short_result, rhsv));
286  block->append (factory.create<jit_branch> (done));
287 
288  blocks.push_back (done);
289  block = done;
290  result = short_result;
291  }
292  else
293  {
294  tree_expression *lhs = be.lhs ();
295  jit_value *lhsv = visit (lhs);
296 
297  tree_expression *rhs = be.rhs ();
298  jit_value *rhsv = visit (rhs);
299 
300  const jit_operation& fn = jit_typeinfo::binary_op (be.op_type ());
301  result = create_checked (fn, lhsv, rhsv);
302  }
303 }
304 
305 void
307 {
308  breaks.push_back (block);
309  throw jit_break_exception ();
310 }
311 
312 void
314 {
315  // in the futher we need to add support for classes and deal with rvalues
316  jit_value *base = visit (expr.base ());
317  jit_value *limit = visit (expr.limit ());
318  jit_value *increment;
319  tree_expression *tinc = expr.increment ();
320 
321  if (tinc)
322  increment = visit (tinc);
323  else
324  increment = factory.create<jit_const_scalar> (1);
325 
327  base, limit, increment));
328 }
329 
330 void
332 {
333  continues.push_back (block);
334  throw jit_break_exception ();
335 }
336 
337 void
339 {
340  throw jit_fail_exception ();
341 }
342 
343 void
345 {
346  throw jit_fail_exception ();
347 }
348 
349 void
351 {
352  throw jit_fail_exception ();
353 }
354 
355 void
357 {
358  throw jit_fail_exception ();
359 }
360 
361 void
363 {
364  // Note we do an initial check to see if the loop will run atleast once.
365  // This allows us to get better type inference bounds on variables defined
366  // and used only inside the for loop (e.g. the index variable)
367 
368  // If we are a nested for loop we need to store the previous breaks
369  unwind_protect prot;
370  prot.protect_var (breaks);
371  prot.protect_var (continues);
372  breaks.clear ();
373  continues.clear ();
374 
375  // we need a variable for our iterator, because it is used in multiple blocks
376  std::string iter_name = next_iterator ();
377  jit_variable *iterator = factory.create<jit_variable> (iter_name);
378  factory.create<jit_variable> (iter_name);
379  vmap[iter_name] = iterator;
380 
381  jit_block *body = factory.create<jit_block> ("for_body");
382  jit_block *tail = factory.create<jit_block> ("for_tail");
383 
384  // do control expression, iter init, and condition check in prev_block (block)
385  // if we are the top level for loop, the bounds is an input argument.
386  jit_value *control = find_variable (next_for_bounds ());
387  if (! control)
388  control = visit (cmd.control_expr ());
390  control);
391  block->append (init_iter);
392  block->append (factory.create<jit_assign> (iterator, init_iter));
393 
395  iterator);
396  block->append (check);
397  block->append (factory.create<jit_cond_branch> (check, body, tail));
398 
399  blocks.push_back (body);
400  block = body;
401 
402  // compute the syntactical iterator
404  control, iterator);
405  block->append (idx_rhs);
406  do_assign (cmd.left_hand_side (), idx_rhs);
407 
408  // do loop
409  tree_statement_list *pt_body = cmd.body ();
410  bool all_breaking = false;
411  try
412  {
413  pt_body->accept (*this);
414  }
415  catch (const jit_break_exception&)
416  {
417  if (continues.empty ())
418  {
419  // WTF are you doing user? Every branch was a break, why did you have
420  // a loop??? Users are silly people...
421  finish_breaks (tail, breaks);
422  blocks.push_back (tail);
423  block = tail;
424  return;
425  }
426 
427  all_breaking = true;
428  }
429 
430  // check our condition, continues jump to this block
431  jit_block *check_block = factory.create<jit_block> ("for_check");
432  blocks.push_back (check_block);
433 
434  jit_block *interrupt_check = factory.create<jit_block> ("for_interrupt");
435  blocks.push_back (interrupt_check);
436 
437  if (! all_breaking)
438  block->append (factory.create<jit_branch> (check_block));
439  finish_breaks (check_block, continues);
440 
441  block = check_block;
444  jit_call *iter_inc = factory.create<jit_call> (add_fn, iterator, one);
445  block->append (iter_inc);
446  block->append (factory.create<jit_assign> (iterator, iter_inc));
447  check = block->append (factory.create<jit_call> (jit_typeinfo::for_check,
448  control, iterator));
449  block->append (factory.create<jit_cond_branch> (check, interrupt_check,
450  tail));
451 
452  block = interrupt_check;
453  jit_error_check *ec
455  body, final_block);
456  block->append (ec);
457 
458  // breaks will go to our tail
459  blocks.push_back (tail);
460  finish_breaks (tail, breaks);
461  block = tail;
462 }
463 
464 void
466 {
467  throw jit_fail_exception ();
468 }
469 
470 void
472 {
473  throw jit_fail_exception ();
474 }
475 
476 void
478 {
479  throw jit_fail_exception ();
480 }
481 
482 void
484 {
485  throw jit_fail_exception ();
486 }
487 
488 void
490 {
491  throw jit_fail_exception ();
492 }
493 
494 void
496 {
497  throw jit_fail_exception ();
498 }
499 
500 void
502 {
503  if (ti.has_magic_end ())
504  {
505  if (!end_context.size ())
506  throw jit_fail_exception ("Illegal end");
508  }
509  else
510  {
511  jit_variable *var = get_variable (ti.name ());
512  jit_instruction *instr;
513  instr = factory.create<jit_call> (&jit_typeinfo::grab, var);
514  result = block->append (instr);
515  }
516 }
517 
518 void
520 {
521  throw jit_fail_exception ();
522 }
523 
524 void
526 {
527  tree_if_command_list *lst = cmd.cmd_list ();
528  assert (lst); // jwe: Can this be null?
529  lst->accept (*this);
530 }
531 
532 void
534 {
535  tree_if_clause *last = lst.back ();
536  size_t last_else = static_cast<size_t> (last->is_else_clause ());
537 
538  // entry_blocks represents the block you need to enter in order to execute
539  // the condition check for the ith clause. For the else, it is simple the
540  // else body. If there is no else body, then it is padded with the tail
541  std::vector<jit_block *> entry_blocks (lst.size () + 1 - last_else);
542  std::vector<jit_block *> branch_blocks (lst.size (), 0); // final blocks
543  entry_blocks[0] = block;
544 
545  // we need to construct blocks first, because they have jumps to eachother
547  ++iter;
548  for (size_t i = 1; iter != lst.end (); ++iter, ++i)
549  {
550  tree_if_clause *tic = *iter;
551  if (tic->is_else_clause ())
552  entry_blocks[i] = factory.create<jit_block> ("else");
553  else
554  entry_blocks[i] = factory.create<jit_block> ("ifelse_cond");
555  }
556 
557  jit_block *tail = factory.create<jit_block> ("if_tail");
558  if (! last_else)
559  entry_blocks[entry_blocks.size () - 1] = tail;
560 
561 
562  // each branch in the if statement will have different breaks/continues
563  block_list current_breaks = breaks;
564  block_list current_continues = continues;
565  breaks.clear ();
566  continues.clear ();
567 
568  size_t num_incomming = 0; // number of incomming blocks to our tail
569  iter = lst.begin ();
570  for (size_t i = 0; iter != lst.end (); ++iter, ++i)
571  {
572  tree_if_clause *tic = *iter;
573  block = entry_blocks[i];
574  assert (block);
575 
576  if (i) // the first block is prev_block, so it has already been added
577  blocks.push_back (entry_blocks[i]);
578 
579  if (! tic->is_else_clause ())
580  {
581  tree_expression *expr = tic->condition ();
582  jit_value *cond = visit (expr);
584  cond);
585  jit_block *body = factory.create<jit_block> (i == 0 ? "if_body"
586  : "ifelse_body");
587  blocks.push_back (body);
588 
589  jit_instruction *br = factory.create<jit_cond_branch> (check, body,
590  entry_blocks[i + 1]);
591  block->append (br);
592  block = body;
593  }
594 
595  tree_statement_list *stmt_lst = tic->commands ();
596  assert (stmt_lst); // jwe: Can this be null?
597 
598  try
599  {
600  stmt_lst->accept (*this);
601  ++num_incomming;
602  block->append (factory.create<jit_branch> (tail));
603  }
604  catch (const jit_break_exception&)
605  { }
606 
607  current_breaks.splice (current_breaks.end (), breaks);
608  current_continues.splice (current_continues.end (), continues);
609  }
610 
611  breaks.splice (breaks.end (), current_breaks);
612  continues.splice (continues.end (), current_continues);
613 
614  if (num_incomming || ! last_else)
615  {
616  blocks.push_back (tail);
617  block = tail;
618  }
619  else
620  // every branch broke, so we don't have a tail
621  throw jit_break_exception ();
622 }
623 
624 void
626 {
627  result = resolve (exp);
628 }
629 
630 void
632 {
633  throw jit_fail_exception ();
634 }
635 
636 void
638 {
639  throw jit_fail_exception ();
640 }
641 
642 void
644 {
645  throw jit_fail_exception ();
646 }
647 
648 void
650 {
651  throw jit_fail_exception ();
652 }
653 
654 void
656 {
657  octave_value v = tc.rvalue1 ();
659 
660  if (ty == jit_typeinfo::get_scalar ())
661  {
662  double dv = v.double_value ();
664  }
665  else if (ty == jit_typeinfo::get_range ())
666  {
667  Range rv = v.range_value ();
669  }
670  else if (ty == jit_typeinfo::get_complex ())
671  {
672  Complex cv = v.complex_value ();
674  }
675  else
676  throw jit_fail_exception ("Unknown constant");
677 }
678 
679 void
681 {
682  throw jit_fail_exception ();
683 }
684 
685 void
687 {
688  throw jit_fail_exception ();
689 }
690 
691 void
693 {
694  octave_value::unary_op etype = tpe.op_type ();
695  tree_expression *operand = tpe.operand ();
696  jit_value *operandv = visit (operand);
697 
698  const jit_operation& fn = jit_typeinfo::unary_op (etype);
699  result = create_checked (fn, operandv);
700 
701  if (etype == octave_value::op_incr || etype == octave_value::op_decr)
702  {
703  jit_value *ret = create_checked (&jit_typeinfo::grab, operandv);
704  do_assign (operand, result);
705  result = ret;
706  }
707 }
708 
709 void
711 {
712  octave_value::unary_op etype = tpe.op_type ();
713  tree_expression *operand = tpe.operand ();
714  const jit_operation& fn = jit_typeinfo::unary_op (etype);
715  result = create_checked (fn, visit (operand));
716 
717  if (etype == octave_value::op_incr || etype == octave_value::op_decr)
718  do_assign (operand, result);
719 }
720 
721 void
723 {
724  throw jit_fail_exception ();
725 }
726 
727 void
729 {
730  throw jit_fail_exception ();
731 }
732 
733 void
735 {
736  tree_expression *rhs = tsa.right_hand_side ();
737  jit_value *rhsv = visit (rhs);
738  octave_value::assign_op op = tsa.op_type ();
739 
740  if (op != octave_value::op_asn_eq)
741  {
742  // do the equivlent binary operation, then assign. This is always correct,
743  // but isn't always optimal.
744  tree_expression *lhs = tsa.left_hand_side ();
745  jit_value *lhsv = visit (lhs);
747  const jit_operation& fn = jit_typeinfo::binary_op (bop);
748  rhsv = create_checked (fn, lhsv, rhsv);
749  }
750 
751  result = do_assign (tsa.left_hand_side (), rhsv);
752 }
753 
754 void
756 {
757  tree_command *cmd = stmt.command ();
758  tree_expression *expr = stmt.expression ();
759 
760  if (cmd)
761  visit (cmd);
762  else
763  {
764  // stolen from tree_evaluator::visit_statement
765  bool do_bind_ans = false;
766 
767  if (expr->is_identifier ())
768  {
769  tree_identifier *id = dynamic_cast<tree_identifier *> (expr);
770 
771  do_bind_ans = (! id->is_variable ());
772  }
773  else
774  do_bind_ans = (! expr->is_assignment_expression ());
775 
776  jit_value *expr_result = visit (expr);
777 
778  if (do_bind_ans)
779  do_assign ("ans", expr_result, expr->print_result ());
780  else if (expr->is_identifier () && expr->print_result ())
781  {
782  // FIXME: ugly hack, we need to come up with a way to pass
783  // nargout to visit_identifier
786  (expr->name ());
787  block->append (factory.create<jit_call> (fn, name, expr_result));
788  }
789  }
790 }
791 
792 void
794 {
795  for (tree_statement_list::iterator iter = lst.begin (); iter != lst.end();
796  ++iter)
797  {
798  tree_statement *elt = *iter;
799  // jwe: Can this ever be null?
800  assert (elt);
801  elt->accept (*this);
802  }
803 }
804 
805 void
807 {
808  throw jit_fail_exception ();
809 }
810 
811 void
813 {
814  throw jit_fail_exception ();
815 }
816 
817 void
819 {
820  throw jit_fail_exception ();
821 }
822 
823 void
825 {
826  throw jit_fail_exception ();
827 }
828 
829 void
831 {
832  throw jit_fail_exception ();
833 }
834 
835 void
837 {
838  unwind_protect prot;
839  prot.protect_var (breaks);
840  prot.protect_var (continues);
841  breaks.clear ();
842  continues.clear ();
843 
844  jit_block *cond_check = factory.create<jit_block> ("while_cond_check");
845  block->append (factory.create<jit_branch> (cond_check));
846  blocks.push_back (cond_check);
847  block = cond_check;
848 
849  tree_expression *expr = wc.condition ();
850  assert (expr && "While expression can not be null");
851  jit_value *check = visit (expr);
853 
854  jit_block *body = factory.create<jit_block> ("while_body");
855  blocks.push_back (body);
856 
857  jit_block *tail = factory.create<jit_block> ("while_tail");
858  block->append (factory.create<jit_cond_branch> (check, body, tail));
859  block = body;
860 
861  tree_statement_list *loop_body = wc.body ();
862  bool all_breaking = false;
863  if (loop_body)
864  {
865  try
866  {
867  loop_body->accept (*this);
868  }
869  catch (const jit_break_exception&)
870  {
871  all_breaking = true;
872  }
873  }
874 
875  finish_breaks (tail, breaks);
876 
877  if (! all_breaking || continues.size ())
878  {
879  jit_block *interrupt_check
880  = factory.create<jit_block> ("interrupt_check");
881  blocks.push_back (interrupt_check);
882  finish_breaks (interrupt_check, continues);
883  if (! all_breaking)
884  block->append (factory.create<jit_branch> (interrupt_check));
885 
886  block = interrupt_check;
887  jit_error_check *ec
889  cond_check, final_block);
890  block->append (ec);
891  }
892 
893  blocks.push_back (tail);
894  block = tail;
895 }
896 
897 void
899 {
900  throw jit_fail_exception ();
901 }
902 
903 void
905 {
906  scope = s;
907  iterator_count = 0;
908  for_bounds_count = 0;
909  short_count = 0;
911 
912  entry_block = factory.create<jit_block> ("body");
913  final_block = factory.create<jit_block> ("final");
916  block = entry_block;
917 }
918 
919 jit_call *
921 {
922  block->append (ret);
923 
924  jit_block *normal = factory.create<jit_block> (block->name ());
925  jit_error_check *check
927  normal, final_block);
928  block->append (check);
929  blocks.push_back (normal);
930  block = normal;
931 
932  return ret;
933 }
934 
935 jit_variable *
936 jit_convert::find_variable (const std::string& vname) const
937 {
938  variable_map::const_iterator iter;
939  iter = vmap.find (vname);
940  return iter != vmap.end () ? iter->second : 0;
941 }
942 
943 jit_variable *
944 jit_convert::get_variable (const std::string& vname)
945 {
946  jit_variable *ret = find_variable (vname);
947  if (ret)
948  return ret;
949 
951  if (record.is_persistent () || record.is_global ())
952  throw jit_fail_exception ("Persistent and global not yet supported");
953 
955  return create_variable (vname, jit_typeinfo::get_any (), false);
956  else
957  {
958  octave_value val = record.varval ();
960  bounds.push_back (type_bound (type, vname));
961 
962  return create_variable (vname, type);
963  }
964 }
965 
966 jit_variable *
967 jit_convert::create_variable (const std::string& vname, jit_type *type,
968  bool isarg)
969 {
970  jit_variable *var = factory.create<jit_variable> (vname);
971 
972  if (isarg)
973  {
974  jit_extract_argument *extract;
975  extract = factory.create<jit_extract_argument> (type, var);
976  entry_block->prepend (extract);
977  }
978  else
979  {
981  jit_assign *assign = factory.create<jit_assign> (var, init);
982  entry_block->prepend (assign);
983  entry_block->prepend (init);
984  }
985 
986  return vmap[vname] = var;
987 }
988 
989 std::string
990 jit_convert::next_name (const char *prefix, size_t& count, bool inc)
991 {
992  std::stringstream ss;
993  ss << prefix << count;
994  if (inc)
995  ++count;
996  return ss.str ();
997 }
998 
1001  bool lhs)
1002 {
1003  std::string type = exp.type_tags ();
1004  if (! (type.size () == 1 && type[0] == '('))
1005  throw jit_fail_exception ("Unsupported index operation");
1006 
1007  std::list<tree_argument_list *> args = exp.arg_lists ();
1008  if (args.size () != 1)
1009  throw jit_fail_exception ("Bad number of arguments in "
1010  "tree_index_expression");
1011 
1012  tree_argument_list *arg_list = args.front ();
1013  if (! arg_list)
1014  throw jit_fail_exception ("null argument list");
1015 
1016  if (arg_list->size () < 1)
1017  throw jit_fail_exception ("Empty arg_list");
1018 
1019  tree_expression *tree_object = exp.expression ();
1020  jit_value *object;
1021  if (lhs)
1022  {
1023  tree_identifier *id = dynamic_cast<tree_identifier *> (tree_object);
1024  if (! id)
1025  throw jit_fail_exception ("expected identifier");
1026  object = get_variable (id->name ());
1027  }
1028  else
1029  object = visit (tree_object);
1030 
1031  size_t narg = arg_list->size ();
1032  tree_argument_list::iterator iter = arg_list->begin ();
1033  bool have_extra = extra_arg;
1034  std::vector<jit_value *> call_args (narg + 1 + have_extra);
1035  call_args[0] = object;
1036 
1037  for (size_t idx = 0; iter != arg_list->end (); ++idx, ++iter)
1038  {
1039  unwind_protect prot;
1040  prot.add_method (&end_context,
1041  &std::vector<jit_magic_end::context>::pop_back);
1042 
1043  jit_magic_end::context ctx (factory, object, idx, narg);
1044  end_context.push_back (ctx);
1045  call_args[idx + 1] = visit (*iter);
1046  }
1047 
1048  if (extra_arg)
1049  call_args[call_args.size () - 1] = extra_arg;
1050 
1051  const jit_operation& fres = lhs ? jit_typeinfo::paren_subsasgn ()
1053 
1054  return create_checked (fres, call_args);
1055 }
1056 
1057 jit_value *
1058 jit_convert::do_assign (tree_expression *exp, jit_value *rhs, bool artificial)
1059 {
1060  if (! exp)
1061  throw jit_fail_exception ("NULL lhs in assign");
1062 
1063  if (isa<tree_identifier> (exp))
1064  return do_assign (exp->name (), rhs, exp->print_result (), artificial);
1065  else if (tree_index_expression *idx
1066  = dynamic_cast<tree_index_expression *> (exp))
1067  {
1068  jit_value *new_object = resolve (*idx, rhs, true);
1069  do_assign (idx->expression (), new_object, true);
1070 
1071  // FIXME: Will not work for values that must be release/grabed
1072  return rhs;
1073  }
1074  else
1075  throw jit_fail_exception ("Unsupported assignment");
1076 }
1077 
1078 jit_value *
1079 jit_convert::do_assign (const std::string& lhs, jit_value *rhs,
1080  bool print, bool artificial)
1081 {
1082  jit_variable *var = get_variable (lhs);
1083  jit_assign *assign = block->append (factory.create<jit_assign> (var, rhs));
1084 
1085  if (artificial)
1086  assign->mark_artificial ();
1087 
1088  if (print)
1089  {
1090  const jit_operation& print_fn = jit_typeinfo::print_value ();
1092  block->append (factory.create<jit_call> (print_fn, name, var));
1093  }
1094 
1095  return var;
1096 }
1097 
1098 jit_value *
1100 {
1101  unwind_protect prot;
1102  prot.protect_var (result);
1103 
1104  tee.accept (*this);
1105  return result;
1106 }
1107 
1108 void
1110 {
1111  for (block_list::const_iterator iter = lst.begin (); iter != lst.end ();
1112  ++iter)
1113  {
1114  jit_block *b = *iter;
1115  b->append (factory.create<jit_branch> (dest));
1116  }
1117 }
1118 
1119 // -------------------- jit_convert_llvm --------------------
1120 llvm::Function *
1121 jit_convert_llvm::convert_loop (llvm::Module *module,
1122  const jit_block_list& blocks,
1123  const std::list<jit_value *>& constants)
1124 {
1125  converting_function = false;
1126 
1127  // for now just init arguments from entry, later we will have to do something
1128  // more interesting
1129  jit_block *entry_block = blocks.front ();
1130  for (jit_block::iterator iter = entry_block->begin ();
1131  iter != entry_block->end (); ++iter)
1132  if (jit_extract_argument *extract
1133  = dynamic_cast<jit_extract_argument *> (*iter))
1134  argument_vec.push_back (std::make_pair (extract->name (), true));
1135 
1136 
1137  jit_type *any = jit_typeinfo::get_any ();
1138 
1139  // argument is an array of octave_base_value*, or octave_base_value**
1140  llvm::Type *arg_type = any->to_llvm (); // this is octave_base_value*
1141  arg_type = arg_type->getPointerTo ();
1142  llvm::FunctionType *ft;
1143  ft = llvm::FunctionType::get (llvm::Type::getVoidTy (context), arg_type,
1144  false);
1145  function = llvm::Function::Create (ft, llvm::Function::ExternalLinkage,
1146  "foobar", module);
1147 
1148  try
1149  {
1150  prelude = llvm::BasicBlock::Create (context, "prelude", function);
1151  builder.SetInsertPoint (prelude);
1152 
1153  llvm::Value *arg = function->arg_begin ();
1154  for (size_t i = 0; i < argument_vec.size (); ++i)
1155  {
1156  llvm::Value *loaded_arg = builder.CreateConstInBoundsGEP1_32 (arg, i);
1157  arguments[argument_vec[i].first] = loaded_arg;
1158  }
1159 
1160  convert (blocks, constants);
1161  }
1162  catch (const jit_fail_exception& e)
1163  {
1164  function->eraseFromParent ();
1165  throw;
1166  }
1167 
1168  return function;
1169 }
1170 
1171 
1174  const jit_block_list& blocks,
1175  const std::list<jit_value *>& constants,
1176  octave_user_function& fcn,
1177  const std::vector<jit_type *>& args)
1178 {
1179  converting_function = true;
1180 
1181  jit_block *final_block = blocks.back ();
1182  jit_return *ret = dynamic_cast<jit_return *> (final_block->back ());
1183  assert (ret);
1184 
1186  "foobar", ret->result_type (), args);
1187  function = creating.to_llvm ();
1188 
1189  try
1190  {
1191  prelude = creating.new_block ("prelude");
1192  builder.SetInsertPoint (prelude);
1193 
1194  tree_parameter_list *plist = fcn.parameter_list ();
1195  if (plist)
1196  {
1197  tree_parameter_list::iterator piter = plist->begin ();
1198  tree_parameter_list::iterator pend = plist->end ();
1199  for (size_t i = 0; i < args.size () && piter != pend; ++i, ++piter)
1200  {
1201  tree_decl_elt *elt = *piter;
1202  std::string arg_name = elt->name ();
1203  arguments[arg_name] = creating.argument (builder, i);
1204  }
1205  }
1206 
1207  convert (blocks, constants);
1208  }
1209  catch (const jit_fail_exception& e)
1210  {
1211  function->eraseFromParent ();
1212  throw;
1213  }
1214 
1215  return creating;
1216 }
1217 
1218 void
1220  const std::list<jit_value *>& constants)
1221 {
1222  std::list<jit_block *>::const_iterator biter;
1223  for (biter = blocks.begin (); biter != blocks.end (); ++biter)
1224  {
1225  jit_block *jblock = *biter;
1226  llvm::BasicBlock *block = llvm::BasicBlock::Create (context,
1227  jblock->name (),
1228  function);
1229  jblock->stash_llvm (block);
1230  }
1231 
1232  jit_block *first = *blocks.begin ();
1233  builder.CreateBr (first->to_llvm ());
1234 
1235  // constants aren't in the IR, we visit those first
1236  for (std::list<jit_value *>::const_iterator iter = constants.begin ();
1237  iter != constants.end (); ++iter)
1238  if (! isa<jit_instruction> (*iter))
1239  visit (*iter);
1240 
1241  // convert all instructions
1242  for (biter = blocks.begin (); biter != blocks.end (); ++biter)
1243  visit (*biter);
1244 
1245  // now finish phi nodes
1246  for (biter = blocks.begin (); biter != blocks.end (); ++biter)
1247  {
1248  jit_block& block = **biter;
1249  for (jit_block::iterator piter = block.begin ();
1250  piter != block.end () && isa<jit_phi> (*piter); ++piter)
1251  {
1252  jit_instruction *phi = *piter;
1253  finish_phi (static_cast<jit_phi *> (phi));
1254  }
1255  }
1256 }
1257 
1258 void
1260 {
1261  llvm::PHINode *llvm_phi = phi->to_llvm ();
1262  for (size_t i = 0; i < phi->argument_count (); ++i)
1263  {
1264  llvm::BasicBlock *pred = phi->incomming_llvm (i);
1265  llvm_phi->addIncoming (phi->argument_llvm (i), pred);
1266  }
1267 }
1268 
1269 void
1271 {
1272  cs.stash_llvm (builder.CreateGlobalStringPtr (cs.value ()));
1273 }
1274 
1275 void
1277 {
1278  cb.stash_llvm (llvm::ConstantInt::get (cb.type_llvm (), cb.value ()));
1279 }
1280 
1281 void
1283 {
1284  cs.stash_llvm (llvm::ConstantFP::get (cs.type_llvm (), cs.value ()));
1285 }
1286 
1287 void
1289 {
1290  llvm::Type *scalar_t = jit_typeinfo::get_scalar_llvm ();
1291  Complex value = cc.value ();
1292  llvm::Value *real = llvm::ConstantFP::get (scalar_t, value.real ());
1293  llvm::Value *imag = llvm::ConstantFP::get (scalar_t, value.imag ());
1294  cc.stash_llvm (jit_typeinfo::create_complex (real, imag));
1295 }
1296 
1298 {
1299  ci.stash_llvm (llvm::ConstantInt::get (ci.type_llvm (), ci.value ()));
1300 }
1301 
1302 void
1304 {
1305  llvm::StructType *stype = llvm::cast<llvm::StructType>(cr.type_llvm ());
1306  llvm::Type *scalar_t = jit_typeinfo::get_scalar_llvm ();
1307  llvm::Type *idx = jit_typeinfo::get_index_llvm ();
1308  const jit_range& rng = cr.value ();
1309 
1310  llvm::Constant *constants[4];
1311  constants[0] = llvm::ConstantFP::get (scalar_t, rng.base);
1312  constants[1] = llvm::ConstantFP::get (scalar_t, rng.limit);
1313  constants[2] = llvm::ConstantFP::get (scalar_t, rng.inc);
1314  constants[3] = llvm::ConstantInt::get (idx, rng.nelem);
1315 
1316  llvm::Value *as_llvm;
1317  as_llvm = llvm::ConstantStruct::get (stype,
1318  llvm::makeArrayRef (constants, 4));
1319  cr.stash_llvm (as_llvm);
1320 }
1321 
1322 void
1324 {
1325  llvm::BasicBlock *block = b.to_llvm ();
1326  builder.SetInsertPoint (block);
1327  for (jit_block::iterator iter = b.begin (); iter != b.end (); ++iter)
1328  visit (*iter);
1329 }
1330 
1331 void
1333 {
1334  b.stash_llvm (builder.CreateBr (b.successor_llvm ()));
1335 }
1336 
1337 void
1339 {
1340  llvm::Value *cond = cb.cond_llvm ();
1341  llvm::Value *br;
1342  br = builder.CreateCondBr (cond, cb.successor_llvm (0),
1343  cb.successor_llvm (1));
1344  cb.stash_llvm (br);
1345 }
1346 
1347 void
1349 {
1350  const jit_function& ol = call.overload ();
1351 
1352  std::vector<jit_value *> args (call.arguments ().size ());
1353  for (size_t i = 0; i < args.size (); ++i)
1354  args[i] = call.argument (i);
1355 
1356  llvm::Value *ret = ol.call (builder, args);
1357  call.stash_llvm (ret);
1358 }
1359 
1360 void
1362 {
1363  llvm::Value *arg = arguments[extract.name ()];
1364  assert (arg);
1365 
1366  if (converting_function)
1367  extract.stash_llvm (arg);
1368  else
1369  {
1370  arg = builder.CreateLoad (arg);
1371 
1372  const jit_function& ol = extract.overload ();
1373  extract.stash_llvm (ol.call (builder, arg));
1374  }
1375 }
1376 
1377 void
1379 {
1380  const jit_function& ol = store.overload ();
1381  llvm::Value *arg_value = ol.call (builder, store.result ());
1382  llvm::Value *arg = arguments[store.name ()];
1383  store.stash_llvm (builder.CreateStore (arg_value, arg));
1384 }
1385 
1386 void
1388 {
1389  jit_value *res = ret.result ();
1390 
1391  if (converting_function)
1392  creating.do_return (builder, res->to_llvm (), false);
1393  else
1394  {
1395  if (res)
1396  builder.CreateRet (res->to_llvm ());
1397  else
1398  builder.CreateRetVoid ();
1399  }
1400 }
1401 
1402 void
1404 {
1405  // we might not have converted all incoming branches, so we don't
1406  // set incomming branches now
1407  llvm::PHINode *node = llvm::PHINode::Create (phi.type_llvm (),
1408  phi.argument_count ());
1409  builder.Insert (node);
1410  phi.stash_llvm (node);
1411 }
1412 
1413 void
1415 {
1416  throw jit_fail_exception ("ERROR: SSA construction should remove all variables");
1417 }
1418 
1419 void
1421 {
1422  llvm::Value *cond;
1423 
1424  switch (check.check_variable ())
1425  {
1428  break;
1431  break;
1432  default:
1433  panic_impossible ();
1434  }
1435 
1436  llvm::Value *br = builder.CreateCondBr (cond, check.successor_llvm (0),
1437  check.successor_llvm (1));
1438  check.stash_llvm (br);
1439 }
1440 
1441 void
1443 {
1444  jit_value *new_value = assign.src ();
1445  assign.stash_llvm (new_value->to_llvm ());
1446 
1447  if (assign.artificial ())
1448  return;
1449 
1450  jit_value *overwrite = assign.overwrite ();
1451  if (isa<jit_assign_base> (overwrite))
1452  {
1453  const jit_function& ol = jit_typeinfo::get_release (overwrite->type ());
1454  if (ol.valid ())
1455  ol.call (builder, overwrite);
1456  }
1457 }
1458 
1459 void
1461 {}
1462 
1463 void
1465 {
1466  const jit_function& ol = me.overload ();
1467 
1469  llvm::Value *ret = ol.call (builder, ctx.value, ctx.index, ctx.count);
1470  me.stash_llvm (ret);
1471 }
1472 
1473 // -------------------- jit_infer --------------------
1475  const variable_map& avmap)
1476  : blocks (ablocks), factory (afactory), vmap (avmap) { }
1477 
1478 void
1480 {
1481  construct_ssa ();
1482 
1483  // initialize the worklist to instructions derived from constants
1484  const std::list<jit_value *>& constants = factory.constants ();
1485  for (std::list<jit_value *>::const_iterator iter = constants.begin ();
1486  iter != constants.end (); ++iter)
1487  append_users (*iter);
1488 
1489  // the entry block terminator may be a regular branch statement
1490  if (entry_block ().terminator ())
1492 
1493  // FIXME: Describe algorithm here
1494  while (worklist.size ())
1495  {
1496  jit_instruction *next = worklist.front ();
1497  worklist.pop_front ();
1498  next->stash_in_worklist (false);
1499 
1500  if (next->infer ())
1501  {
1502  // terminators need to be handles specially
1503  if (jit_terminator *term = dynamic_cast<jit_terminator *> (next))
1504  append_users_term (term);
1505  else
1506  append_users (next);
1507  }
1508  }
1509 
1510  remove_dead ();
1511  blocks.label ();
1512  place_releases ();
1513  simplify_phi ();
1514 }
1515 
1516 void
1518 {
1519  for (jit_use *use = v->first_use (); use; use = use->next ())
1520  push_worklist (use->user ());
1521 }
1522 
1523 void
1525 {
1526  for (size_t i = 0; i < term->successor_count (); ++i)
1527  {
1528  if (term->alive (i))
1529  {
1530  jit_block *succ = term->successor (i);
1531  for (jit_block::iterator iter = succ->begin ();
1532  iter != succ->end () && isa<jit_phi> (*iter); ++iter)
1533  push_worklist (*iter);
1534 
1535  jit_terminator *sterm = succ->terminator ();
1536  if (sterm)
1537  push_worklist (sterm);
1538  }
1539  }
1540 }
1541 
1542 void
1544 {
1545  blocks.label ();
1547  entry_block ().compute_df ();
1549 
1550  // insert phi nodes where needed, this is done on a per variable basis
1551  for (variable_map::const_iterator iter = vmap.begin (); iter != vmap.end ();
1552  ++iter)
1553  {
1554  jit_block::df_set visited, added_phi;
1555  std::list<jit_block *> ssa_worklist;
1556  iter->second->use_blocks (visited);
1557  ssa_worklist.insert (ssa_worklist.begin (), visited.begin (),
1558  visited.end ());
1559 
1560  while (ssa_worklist.size ())
1561  {
1562  jit_block *b = ssa_worklist.front ();
1563  ssa_worklist.pop_front ();
1564 
1565  for (jit_block::df_iterator diter = b->df_begin ();
1566  diter != b->df_end (); ++diter)
1567  {
1568  jit_block *dblock = *diter;
1569  if (! added_phi.count (dblock))
1570  {
1571  jit_phi *phi = factory.create<jit_phi> (iter->second,
1572  dblock->use_count ());
1573  dblock->prepend (phi);
1574  added_phi.insert (dblock);
1575  }
1576 
1577  if (! visited.count (dblock))
1578  {
1579  ssa_worklist.push_back (dblock);
1580  visited.insert (dblock);
1581  }
1582  }
1583  }
1584  }
1585 
1586  do_construct_ssa (entry_block (), entry_block ().visit_count ());
1587 }
1588 
1589 void
1590 jit_infer::do_construct_ssa (jit_block& ablock, size_t avisit_count)
1591 {
1592  if (ablock.visited (avisit_count))
1593  return;
1594 
1595  // replace variables with their current SSA value
1596  for (jit_block::iterator iter = ablock.begin (); iter != ablock.end ();
1597  ++iter)
1598  {
1599  jit_instruction *instr = *iter;
1600  instr->construct_ssa ();
1601  instr->push_variable ();
1602  }
1603 
1604  // finish phi nodes of successors
1605  for (size_t i = 0; i < ablock.successor_count (); ++i)
1606  {
1607  jit_block *finish = ablock.successor (i);
1608 
1609  for (jit_block::iterator iter = finish->begin ();
1610  iter != finish->end () && isa<jit_phi> (*iter);)
1611  {
1612  jit_phi *phi = static_cast<jit_phi *> (*iter);
1613  jit_variable *var = phi->dest ();
1614  ++iter;
1615 
1616  if (var->has_top ())
1617  phi->add_incomming (&ablock, var->top ());
1618  else
1619  {
1620  // temporaries may have extranious phi nodes which can be removed
1621  assert (! phi->use_count ());
1622  assert (var->name ().size () && var->name ()[0] == '#');
1623  phi->remove ();
1624  }
1625  }
1626  }
1627 
1628  for (size_t i = 0; i < ablock.dom_successor_count (); ++i)
1629  do_construct_ssa (*ablock.dom_successor (i), avisit_count);
1630 
1631  ablock.pop_all ();
1632 }
1633 
1634 void
1636 {
1637  std::set<jit_value *> temporaries;
1638  for (jit_block_list::iterator iter = blocks.begin (); iter != blocks.end ();
1639  ++iter)
1640  {
1641  jit_block& ablock = **iter;
1642  if (ablock.id () != jit_block::NO_ID)
1643  {
1644  release_temp (ablock, temporaries);
1645  release_dead_phi (ablock);
1646  }
1647  }
1648 }
1649 
1650 void
1652 {
1653  if (! instr->in_worklist ())
1654  {
1655  instr->stash_in_worklist (true);
1656  worklist.push_back (instr);
1657  }
1658 }
1659 
1660 void
1662 {
1664  for (biter = blocks.begin (); biter != blocks.end (); ++biter)
1665  {
1666  jit_block *b = *biter;
1667  if (b->alive ())
1668  {
1669  for (jit_block::iterator iter = b->begin ();
1670  iter != b->end () && isa<jit_phi> (*iter);)
1671  {
1672  jit_phi *phi = static_cast<jit_phi *> (*iter);
1673  if (phi->prune ())
1674  iter = b->remove (iter);
1675  else
1676  ++iter;
1677  }
1678  }
1679  }
1680 
1681  for (biter = blocks.begin (); biter != blocks.end ();)
1682  {
1683  jit_block *b = *biter;
1684  if (b->alive ())
1685  {
1686  // FIXME: A special case for jit_error_check, if we generalize to
1687  // we will need to change!
1688  jit_terminator *term = b->terminator ();
1689  if (term && term->successor_count () == 2 && ! term->alive (0))
1690  {
1691  jit_block *succ = term->successor (1);
1692  term->remove ();
1693  jit_branch *abreak = factory.create<jit_branch> (succ);
1694  b->append (abreak);
1695  abreak->infer ();
1696  }
1697 
1698  ++biter;
1699  }
1700  else
1701  {
1702  jit_terminator *term = b->terminator ();
1703  if (term)
1704  term->remove ();
1705  biter = blocks.erase (biter);
1706  }
1707  }
1708 }
1709 
1710 void
1712 {
1713  jit_block::iterator iter = ablock.begin ();
1714  while (iter != ablock.end () && isa<jit_phi> (*iter))
1715  {
1716  jit_phi *phi = static_cast<jit_phi *> (*iter);
1717  ++iter;
1718 
1719  jit_use *use = phi->first_use ();
1720  if (phi->use_count () == 1 && isa<jit_assign> (use->user ()))
1721  {
1722  // instead of releasing on assign, release on all incomming branches,
1723  // this can get rid of casts inside loops
1724  for (size_t i = 0; i < phi->argument_count (); ++i)
1725  {
1726  jit_value *arg = phi->argument (i);
1727  if (! arg->needs_release ())
1728  continue;
1729 
1730  jit_block *inc = phi->incomming (i);
1731  jit_block *split = inc->maybe_split (factory, blocks, ablock);
1732  jit_terminator *term = split->terminator ();
1733  jit_call *release
1735  release->infer ();
1736  split->insert_before (term, release);
1737  }
1738 
1739  phi->replace_with (0);
1740  phi->remove ();
1741  }
1742  }
1743 }
1744 
1745 void
1746 jit_infer::release_temp (jit_block& ablock, std::set<jit_value *>& temp)
1747 {
1748  for (jit_block::iterator iter = ablock.begin (); iter != ablock.end ();
1749  ++iter)
1750  {
1751  jit_instruction *instr = *iter;
1752 
1753  // check for temporaries that require release and live across
1754  // multiple blocks
1755  if (instr->needs_release ())
1756  {
1757  jit_block *fu_block = instr->first_use_block ();
1758  if (fu_block && fu_block != &ablock && instr->needs_release ())
1759  temp.insert (instr);
1760  }
1761 
1762  if (isa<jit_call> (instr))
1763  {
1764  // place releases for temporary arguments
1765  for (size_t i = 0; i < instr->argument_count (); ++i)
1766  {
1767  jit_value *arg = instr->argument (i);
1768  if (! arg->needs_release ())
1769  continue;
1770 
1771  jit_call *release
1773  release->infer ();
1774  ablock.insert_after (iter, release);
1775  ++iter;
1776  temp.erase (arg);
1777  }
1778  }
1779  }
1780 
1781  if (! temp.size () || ! isa<jit_error_check> (ablock.terminator ()))
1782  return;
1783 
1784  // FIXME: If we support try/catch or unwind_protect final_block
1785  // may not be the destination
1786  jit_block *split = ablock.maybe_split (factory, blocks, final_block ());
1787  jit_terminator *term = split->terminator ();
1788  for (std::set<jit_value *>::const_iterator iter = temp.begin ();
1789  iter != temp.end (); ++iter)
1790  {
1791  jit_value *value = *iter;
1792  jit_call *release
1794  split->insert_before (term, release);
1795  release->infer ();
1796  }
1797 }
1798 
1799 void
1801 {
1802  for (jit_block_list::iterator biter = blocks.begin (); biter != blocks.end ();
1803  ++biter)
1804  {
1805  jit_block &ablock = **biter;
1806  for (jit_block::iterator iter = ablock.begin ();
1807  iter != ablock.end () && isa<jit_phi> (*iter); ++iter)
1808  simplify_phi (*static_cast<jit_phi *> (*iter));
1809  }
1810 }
1811 
1812 void
1814 {
1815  jit_block& pblock = *phi.parent ();
1816  const jit_operation& cast_fn = jit_typeinfo::cast (phi.type ());
1817  jit_variable *dest = phi.dest ();
1818  for (size_t i = 0; i < phi.argument_count (); ++i)
1819  {
1820  jit_value *arg = phi.argument (i);
1821  if (arg->type () != phi.type ())
1822  {
1823  jit_block *pred = phi.incomming (i);
1824  jit_block *split = pred->maybe_split (factory, blocks, pblock);
1825  jit_terminator *term = split->terminator ();
1826  jit_instruction *cast = factory.create<jit_call> (cast_fn, arg);
1827  jit_assign *assign = factory.create<jit_assign> (dest, cast);
1828 
1829  split->insert_before (term, cast);
1830  split->insert_before (term, assign);
1831  cast->infer ();
1832  assign->infer ();
1833  phi.stash_argument (i, assign);
1834  }
1835  }
1836 }
1837 
1838 // -------------------- tree_jit --------------------
1839 
1840 tree_jit::tree_jit (void) : module (0), engine (0)
1841 {
1842 }
1843 
1845 {}
1846 
1847 bool
1849 {
1850  return instance ().do_execute (cmd, bounds);
1851 }
1852 
1853 bool
1855 {
1856  return instance ().do_execute (cmd);
1857 }
1858 
1859 bool
1861  octave_value_list& retval)
1862 {
1863  return instance ().do_execute (fcn, args, retval);
1864 }
1865 
1866 tree_jit&
1868 {
1869  static tree_jit ret;
1870  return ret;
1871 }
1872 
1873 bool
1875 {
1876  if (engine)
1877  return true;
1878 
1879  if (! module)
1880  {
1881  llvm::InitializeNativeTarget ();
1882  module = new llvm::Module ("octave", context);
1883  }
1884 
1885  // sometimes this fails pre main
1886  engine = llvm::ExecutionEngine::createJIT (module);
1887 
1888  if (! engine)
1889  return false;
1890 
1891  module_pass_manager = new llvm::PassManager ();
1892  module_pass_manager->add (llvm::createAlwaysInlinerPass ());
1893 
1894  pass_manager = new llvm::FunctionPassManager (module);
1895 #ifdef HAVE_LLVM_DATALAYOUT
1896  pass_manager->add (new llvm::DataLayout (*engine->getDataLayout ()));
1897 #else
1898  pass_manager->add (new llvm::TargetData (*engine->getTargetData ()));
1899 #endif
1900  pass_manager->add (llvm::createCFGSimplificationPass ());
1901  pass_manager->add (llvm::createBasicAliasAnalysisPass ());
1902  pass_manager->add (llvm::createPromoteMemoryToRegisterPass ());
1903  pass_manager->add (llvm::createInstructionCombiningPass ());
1904  pass_manager->add (llvm::createReassociatePass ());
1905  pass_manager->add (llvm::createGVNPass ());
1906  pass_manager->add (llvm::createCFGSimplificationPass ());
1907  pass_manager->doInitialization ();
1908 
1910 
1911  return true;
1912 }
1913 
1914 bool
1916 {
1917  size_t tc = trip_count (bounds);
1918  if (! tc || ! initialize () || ! enabled ())
1919  return false;
1920 
1921  jit_info::vmap extra_vars;
1922  extra_vars["#for_bounds0"] = &bounds;
1923 
1924  jit_info *info = cmd.get_info ();
1925  if (! info || ! info->match (extra_vars))
1926  {
1927  if (tc < static_cast<size_t> (Vjit_startcnt))
1928  return false;
1929 
1930  delete info;
1931  info = new jit_info (*this, cmd, bounds);
1932  cmd.stash_info (info);
1933  }
1934 
1935  return info->execute (extra_vars);
1936 }
1937 
1938 bool
1940 {
1941  if (! initialize () || ! enabled ())
1942  return false;
1943 
1944  jit_info *info = cmd.get_info ();
1945  if (! info || ! info->match ())
1946  {
1947  delete info;
1948  info = new jit_info (*this, cmd);
1949  cmd.stash_info (info);
1950  }
1951 
1952  return info->execute ();
1953 }
1954 
1955 bool
1957  octave_value_list& retval)
1958 {
1959  if (! initialize () || ! enabled ())
1960  return false;
1961 
1962  jit_function_info *info = fcn.get_info ();
1963  if (! info || ! info->match (args))
1964  {
1965  delete info;
1966  info = new jit_function_info (*this, fcn, args);
1967  fcn.stash_info (info);
1968  }
1969 
1970  return info->execute (args, retval);
1971 }
1972 
1973 bool
1975 {
1976  // Ideally, we should only disable JIT if there is a breakpoint in the code we
1977  // are about to run. However, we can't figure this out in O(1) time, so we
1978  // conservatively check for the existence of any breakpoints.
1981 }
1982 
1983 size_t
1984 tree_jit::trip_count (const octave_value& bounds) const
1985 {
1986  if (bounds.is_range ())
1987  {
1988  Range rng = bounds.range_value ();
1989  return rng.nelem ();
1990  }
1991 
1992  // unsupported type
1993  return 0;
1994 }
1995 
1996 
1997 void
1998 tree_jit::optimize (llvm::Function *fn)
1999 {
2000  if (Vdebug_jit)
2001  llvm::verifyModule (*module);
2002 
2003  module_pass_manager->run (*module);
2004  pass_manager->run (*fn);
2005 
2006  if (Vdebug_jit)
2007  {
2008  std::string error;
2009  llvm::raw_fd_ostream fout ("test.bc", error,
2010  llvm::raw_fd_ostream::F_Binary);
2011  llvm::WriteBitcodeToFile (module, fout);
2012  }
2013 }
2014 
2015 // -------------------- jit_function_info --------------------
2017  octave_user_function& fcn,
2018  const octave_value_list& ov_args)
2019  : argument_types (ov_args.length ()), function (0)
2020 {
2021  size_t nargs = ov_args.length ();
2022  for (size_t i = 0; i < nargs; ++i)
2023  argument_types[i] = jit_typeinfo::type_of (ov_args(i));
2024 
2025  jit_function raw_fn;
2026  jit_function wrapper;
2027 
2028  try
2029  {
2030  jit_convert conv (fcn, argument_types);
2031  jit_infer infer (conv.get_factory (), conv.get_blocks (),
2032  conv.get_variable_map ());
2033  infer.infer ();
2034 
2035  if (Vdebug_jit)
2036  {
2037  jit_block_list& blocks = infer.get_blocks ();
2038  blocks.label ();
2039  std::cout << "-------------------- Compiling function ";
2040  std::cout << "--------------------\n";
2041 
2042  tree_print_code tpc (std::cout);
2044  tpc.visit_statement_list (*fcn.body ());
2046  blocks.print (std::cout, "octave jit ir");
2047  }
2048 
2049  jit_factory& factory = conv.get_factory ();
2050  llvm::Module *module = tjit.get_module ();
2051  jit_convert_llvm to_llvm;
2052  raw_fn = to_llvm.convert_function (module, infer.get_blocks (),
2053  factory.constants (), fcn,
2054  argument_types);
2055 
2056  if (Vdebug_jit)
2057  {
2058  std::cout << "-------------------- raw function ";
2059  std::cout << "--------------------\n";
2060  std::cout << *raw_fn.to_llvm () << std::endl;
2061  llvm::verifyFunction (*raw_fn.to_llvm ());
2062  }
2063 
2064  std::string wrapper_name = fcn.name () + "_wrapper";
2065  jit_type *any_t = jit_typeinfo::get_any ();
2066  std::vector<jit_type *> wrapper_args (1, jit_typeinfo::get_any_ptr ());
2067  wrapper = jit_function (module, jit_convention::internal, wrapper_name,
2068  any_t, wrapper_args);
2069 
2070  llvm::BasicBlock *wrapper_body = wrapper.new_block ();
2071  builder.SetInsertPoint (wrapper_body);
2072 
2073  llvm::Value *wrapper_arg = wrapper.argument (builder, 0);
2074  std::vector<llvm::Value *> raw_args (nargs);
2075  for (size_t i = 0; i < nargs; ++i)
2076  {
2077  llvm::Value *arg;
2078  arg = builder.CreateConstInBoundsGEP1_32 (wrapper_arg, i);
2079  arg = builder.CreateLoad (arg);
2080 
2081  jit_type *arg_type = argument_types[i];
2082  const jit_function& cast = jit_typeinfo::cast (arg_type, any_t);
2083  raw_args[i] = cast.call (builder, arg);
2084  }
2085 
2086  llvm::Value *result = raw_fn.call (builder, raw_args);
2087  if (raw_fn.result ())
2088  {
2089  jit_type *raw_result_t = raw_fn.result ();
2090  const jit_function& cast = jit_typeinfo::cast (any_t, raw_result_t);
2091  result = cast.call (builder, result);
2092  }
2093  else
2094  {
2095  llvm::Value *zero = builder.getInt32 (0);
2096  result = builder.CreateBitCast (zero, any_t->to_llvm ());
2097  }
2098 
2099  wrapper.do_return (builder, result);
2100 
2101  llvm::Function *llvm_function = wrapper.to_llvm ();
2102  tjit.optimize (llvm_function);
2103 
2104  if (Vdebug_jit)
2105  {
2106  std::cout << "-------------------- optimized and wrapped ";
2107  std::cout << "--------------------\n";
2108  std::cout << *llvm_function << std::endl;
2109  llvm::verifyFunction (*llvm_function);
2110  }
2111 
2112  llvm::ExecutionEngine* engine = tjit.get_engine ();
2113  void *void_fn = engine->getPointerToFunction (llvm_function);
2114  function = reinterpret_cast<jited_function> (void_fn);
2115  }
2116  catch (const jit_fail_exception& e)
2117  {
2118  argument_types.clear ();
2119 
2120  if (Vdebug_jit)
2121  {
2122  if (e.known ())
2123  std::cout << "jit fail: " << e.what () << std::endl;
2124  }
2125 
2126  wrapper.erase ();
2127  raw_fn.erase ();
2128  }
2129 }
2130 
2131 bool
2133  octave_value_list& retval) const
2134 {
2135  if (! function)
2136  return false;
2137 
2138  // TODO figure out a way to delete ov_args so we avoid duplicating refcount
2139  size_t nargs = ov_args.length ();
2140  std::vector<octave_base_value *> args (nargs);
2141  for (size_t i = 0; i < nargs; ++i)
2142  {
2143  octave_base_value *obv = ov_args(i).internal_rep ();
2144  obv->grab ();
2145  args[i] = obv;
2146  }
2147 
2148  octave_base_value *ret = function (&args[0]);
2149  if (ret)
2150  retval(0) = octave_value (ret);
2151 
2152  octave_quit ();
2153 
2154  return true;
2155 }
2156 
2157 bool
2159 {
2160  if (! function)
2161  return true;
2162 
2163  size_t nargs = ov_args.length ();
2164  if (nargs != argument_types.size ())
2165  return false;
2166 
2167  for (size_t i = 0; i < nargs; ++i)
2168  if (jit_typeinfo::type_of (ov_args(i)) != argument_types[i])
2169  return false;
2170 
2171  return true;
2172 }
2173 
2174 // -------------------- jit_info --------------------
2176  : engine (tjit.get_engine ()), function (0), llvm_function (0)
2177 {
2178  compile (tjit, tee);
2179 }
2180 
2181 jit_info::jit_info (tree_jit& tjit, tree& tee, const octave_value& for_bounds)
2182  : engine (tjit.get_engine ()), function (0), llvm_function (0)
2183 {
2184  compile (tjit, tee, jit_typeinfo::type_of (for_bounds));
2185 }
2186 
2188 {
2189  if (llvm_function)
2190  llvm_function->eraseFromParent ();
2191 }
2192 
2193 bool
2194 jit_info::execute (const vmap& extra_vars) const
2195 {
2196  if (! function)
2197  return false;
2198 
2199  std::vector<octave_base_value *> real_arguments (arguments.size ());
2200  for (size_t i = 0; i < arguments.size (); ++i)
2201  {
2202  if (arguments[i].second)
2203  {
2204  octave_value current = find (extra_vars, arguments[i].first);
2205  octave_base_value *obv = current.internal_rep ();
2206  obv->grab ();
2207  real_arguments[i] = obv;
2208  }
2209  }
2210 
2211  function (&real_arguments[0]);
2212 
2213  for (size_t i = 0; i < arguments.size (); ++i)
2214  {
2215  const std::string& name = arguments[i].first;
2216 
2217  // do not store for loop bounds temporary
2218  if (name.size () && name[0] != '#')
2219  symbol_table::assign (arguments[i].first, real_arguments[i]);
2220  }
2221 
2222  octave_quit ();
2223 
2224  return true;
2225 }
2226 
2227 bool
2228 jit_info::match (const vmap& extra_vars) const
2229 {
2230  if (! function)
2231  return true;
2232 
2233  for (size_t i = 0; i < bounds.size (); ++i)
2234  {
2235  const std::string& arg_name = bounds[i].second;
2236  octave_value value = find (extra_vars, arg_name);
2237  jit_type *type = jit_typeinfo::type_of (value);
2238 
2239  // FIXME: Check for a parent relationship
2240  if (type != bounds[i].first)
2241  return false;
2242  }
2243 
2244  return true;
2245 }
2246 
2247 void
2248 jit_info::compile (tree_jit& tjit, tree& tee, jit_type *for_bounds)
2249 {
2250  try
2251  {
2252  jit_convert conv (tee, for_bounds);
2253  jit_infer infer (conv.get_factory (), conv.get_blocks (),
2254  conv.get_variable_map ());
2255 
2256  infer.infer ();
2257 
2258  if (Vdebug_jit)
2259  {
2260  jit_block_list& blocks = infer.get_blocks ();
2261  blocks.label ();
2262  std::cout << "-------------------- Compiling tree --------------------\n";
2263  std::cout << tee.str_print_code () << std::endl;
2264  blocks.print (std::cout, "octave jit ir");
2265  }
2266 
2267  jit_factory& factory = conv.get_factory ();
2268  jit_convert_llvm to_llvm;
2269  llvm_function = to_llvm.convert_loop (tjit.get_module (),
2270  infer.get_blocks (),
2271  factory.constants ());
2272  arguments = to_llvm.get_arguments ();
2273  bounds = conv.get_bounds ();
2274  }
2275  catch (const jit_fail_exception& e)
2276  {
2277  if (Vdebug_jit)
2278  {
2279  if (e.known ())
2280  std::cout << "jit fail: " << e.what () << std::endl;
2281  }
2282  }
2283 
2284  if (llvm_function)
2285  {
2286  if (Vdebug_jit)
2287  {
2288  std::cout << "-------------------- llvm ir --------------------";
2289  std::cout << *llvm_function << std::endl;
2290  llvm::verifyFunction (*llvm_function);
2291  }
2292 
2293  tjit.optimize (llvm_function);
2294 
2295  if (Vdebug_jit)
2296  {
2297  std::cout << "-------------------- optimized llvm ir "
2298  << "--------------------\n";
2299  std::cout << *llvm_function << std::endl;
2300  }
2301 
2302  void *void_fn = engine->getPointerToFunction (llvm_function);
2303  function = reinterpret_cast<jited_function> (void_fn);
2304  }
2305 }
2306 
2308 jit_info::find (const vmap& extra_vars, const std::string& vname) const
2309 {
2310  vmap::const_iterator iter = extra_vars.find (vname);
2311  return iter == extra_vars.end () ? symbol_table::varval (vname)
2312  : *iter->second;
2313 }
2314 
2315 #endif
2316 
2317 DEFUN (debug_jit, args, nargout,
2318  "-*- texinfo -*-\n\
2319 @deftypefn {Built-in Function} {@var{val} =} debug_jit ()\n\
2320 @deftypefnx {Built-in Function} {@var{old_val} =} debug_jit (@var{new_val})\n\
2321 @deftypefnx {Built-in Function} {} debug_jit (@var{new_val}, \"local\")\n\
2322 Query or set the internal variable that determines whether\n\
2323 debugging/tracing is enabled for Octave's JIT compiler.\n\
2324 \n\
2325 When called from inside a function with the @qcode{\"local\"} option, the\n\
2326 variable is changed locally for the function and any subroutines it calls. \n\
2327 The original variable value is restored when exiting the function.\n\
2328 @seealso{jit_enable, jit_startcnt}\n\
2329 @end deftypefn")
2330 {
2331 #if defined (HAVE_LLVM)
2332  return SET_INTERNAL_VARIABLE (debug_jit);
2333 #else
2334  warning ("debug_jit: JIT compiling not available in this version of Octave");
2335  return octave_value ();
2336 #endif
2337 }
2338 
2339 DEFUN (jit_enable, args, nargout,
2340  "-*- texinfo -*-\n\
2341 @deftypefn {Built-in Function} {@var{val} =} jit_enable ()\n\
2342 @deftypefnx {Built-in Function} {@var{old_val} =} jit_enable (@var{new_val})\n\
2343 @deftypefnx {Built-in Function} {} jit_enable (@var{new_val}, \"local\")\n\
2344 Query or set the internal variable that enables Octave's JIT compiler.\n\
2345 \n\
2346 When called from inside a function with the @qcode{\"local\"} option, the\n\
2347 variable is changed locally for the function and any subroutines it calls. \n\
2348 The original variable value is restored when exiting the function.\n\
2349 @seealso{jit_startcnt, debug_jit}\n\
2350 @end deftypefn")
2351 {
2352 #if defined (HAVE_LLVM)
2353  return SET_INTERNAL_VARIABLE (jit_enable);
2354 #else
2355  warning ("jit_enable: JIT compiling not available in this version of Octave");
2356  return octave_value ();
2357 #endif
2358 }
2359 
2360 DEFUN (jit_startcnt, args, nargout,
2361  "-*- texinfo -*-\n\
2362 @deftypefn {Built-in Function} {@var{val} =} jit_startcnt ()\n\
2363 @deftypefnx {Built-in Function} {@var{old_val} =} jit_startcnt (@var{new_val})\n\
2364 @deftypefnx {Built-in Function} {} jit_startcnt (@var{new_val}, \"local\")\n\
2365 Query or set the internal variable that determines whether JIT compilation\n\
2366 will take place for a specific loop. Because compilation is a costly\n\
2367 operation it does not make sense to employ JIT when the loop count is low.\n\
2368 By default only loops with greater than 1000 iterations will be accelerated.\n\
2369 \n\
2370 When called from inside a function with the @qcode{\"local\"} option, the\n\
2371 variable is changed locally for the function and any subroutines it calls. \n\
2372 The original variable value is restored when exiting the function.\n\
2373 @seealso{jit_enable, debug_jit}\n\
2374 @end deftypefn")
2375 {
2376 #if defined (HAVE_LLVM)
2377  return SET_INTERNAL_VARIABLE_WITH_LIMITS (jit_startcnt, 1,
2379 #else
2380  warning ("jit_enable: JIT compiling not available in this version of Octave");
2381  return octave_value ();
2382 #endif
2383 }