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