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