icode: 'IRoutine::optimize' need a module
[nit.git] / src / compiling / compiling_icode.nit
1 # This file is part of NIT ( http://www.nitlanguage.org ).
2 #
3 # Copyright 2009 Jean Privat <jean@pryen.org>
4 #
5 # Licensed under the Apache License, Version 2.0 (the "License");
6 # you may not use this file except in compliance with the License.
7 # You may obtain a copy of the License at
8 #
9 # http://www.apache.org/licenses/LICENSE-2.0
10 #
11 # Unless required by applicable law or agreed to in writing, software
12 # distributed under the License is distributed on an "AS IS" BASIS,
13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 # See the License for the specific language governing permissions and
15 # limitations under the License.
16
17 # Generate C code from intermediate code representation
18 package compiling_icode
19
20 import icode
21 private import analysis
22 import compiling_base
23
24 # Compiler context from ICode to C
25 class I2CCompilerVisitor
26 # Associate things
27 var _ids: HashMap[Object, String] = new HashMap[Object, String]
28 # Associate other things
29 var _ids2: HashMap[Object, String] = new HashMap[Object, String]
30
31 # Return the string associated with a register
32 fun register(e: IRegister): String
33 do
34 if e.stype isa MMTypeNone then return "NIT_NULL"
35 var ids = _ids
36 if closure and not e.is_local then ids = _ids2
37 if ids.has_key(e) then
38 return ids[e]
39 else
40 var i = e.slot_index
41 if i == null then
42 # The register is dead
43 var s = "NIT_NULL"
44 ids[e] = s
45 return s
46 else
47 var s: String
48 var strs: HashMap[Int, String]
49 if e.in_tag_slots then
50 strs = once new HashMap[Int, String]
51 if not strs.has_key(i) then strs[i] = "REGB{i}"
52 else if closure and not e.is_local then
53 strs = once new HashMap[Int, String]
54 if not strs.has_key(i) then strs[i] = "closctx->variable[{i}]"
55 else
56 strs = once new HashMap[Int, String]
57 if not strs.has_key(i) then strs[i] = "REG[{i}]"
58 end
59 s = strs[i]
60 ids[e] = s
61 return s
62 end
63 end
64 end
65
66 # Return the strings associated with registers
67 fun registers(a: Collection[IRegister]): Array[String]
68 do
69 var r = new Array[String].with_capacity(a.length)
70 for e in a do
71 r.add(register(e))
72 end
73 return r
74 end
75
76 var _last_number: Int = 0
77 # Give a new unique number (unique for the visitor)
78 fun new_number: Int
79 do
80 _last_number += 1
81 return _last_number
82 end
83
84 # Return the string associated with a escape label
85 fun lab(e: ISeq): String
86 do
87 if _ids.has_key(e) then
88 return _ids[e]
89 else
90 var s = "label{new_number}"
91 _ids[e] = s
92 return s
93 end
94 end
95
96 # The rank (number) of each closure
97 readable var _closures: HashMap[IClosureDecl, Int] = new HashMap[IClosureDecl, Int]
98
99 # The functionnal type of each closure
100 readable var _clostypes: HashMap[IClosureDecl, String] = new HashMap[IClosureDecl, String]
101
102 # label locally accessibles
103 readable writable var _local_labels: HashSet[ISeq] = new HashSet[ISeq]
104
105 # Not local escaped labels
106 # The integer value is an index identifying the label
107 readable writable var _escaped_labels: HashMap[ISeq, Int] = new HashMap[ISeq, Int]
108
109 # Register a escape to a non local label and return an index identifying the label
110 fun register_escape_label(e: ISeq): Int
111 do
112 if _escaped_labels.has_key(e) then
113 return _escaped_labels[e]
114 else
115 var res = _escaped_labels.length + 1
116 _escaped_labels[e] = res
117 return res
118 end
119 end
120
121 # Add a C label mark (if needed)
122 fun add_label(e: ISeq)
123 do
124 if _ids.has_key(e) then
125 add_instr("{_ids[e]}: while(0);")
126 end
127 end
128
129 # Add a goto to a label (even outside a closure)
130 fun add_goto(seq: ISeq)
131 do
132 if local_labels.has(seq) then
133 add_instr("goto {lab(seq)};")
134 else
135 assert closure
136 var ind = register_escape_label(seq)
137 add_instr("closctx->has_broke = (val_t*){ind};")
138 add_instr("goto {lab(return_label.as(not null))};")
139 end
140 end
141
142 # Are we in a closure ?
143 readable writable var _closure: Bool = false
144
145 # The current compiler visitor
146 readable var _visitor: CompilerVisitor
147
148 # The current compiled iroutine
149 readable var _iroutine: IRoutine
150
151 # The return label of the current compiling C function
152 readable writable var _return_label: nullable ISeq = null
153
154 fun add_decl(s: String)
155 do
156 visitor.add_decl(s)
157 end
158
159 fun add_instr(s: String)
160 do
161 var l = _next_location
162 if l != null then
163 visitor.add_instr("/* ", l.file, ":", l.line_start.to_s, " */")
164 _next_location = null
165 end
166 visitor.add_instr(s)
167 end
168
169 fun indent
170 do
171 visitor.indent
172 end
173
174 fun unindent
175 do
176 visitor.unindent
177 end
178
179 fun add_assignment(to, from: String)
180 do
181 visitor.add_assignment(to, from)
182 end
183
184 var _last_location: nullable Location = null
185 var _next_location: nullable Location = null
186
187 # Add location information in a comment
188 # Do nothing if the last location added is the same
189 fun add_location(l: nullable Location)
190 do
191 var last = _last_location
192 if last == l or l == null then return
193 _last_location = l
194 if last != null and last.file == l.file and last.line_start == l.line_start then
195 return
196 else
197 _next_location = l
198 end
199 end
200
201 # The C fonction name of the iroutine
202 readable var _basecname: String
203
204 init(v: CompilerVisitor, ir: IRoutine, cname: String)
205 do
206 _visitor = v
207 _iroutine = ir
208 _basecname = cname
209 end
210 end
211
212 redef class IRoutine
213 # Declare and start a C function that match the routine
214 # Return what must be given to compile_inside_to_c or to compile_to_c
215 # After the method, an openinig { and and indent is added.
216 # So, do not forget to add a sub_context, to unintent and to add a closing }
217 fun compile_signature_to_c(v: CompilerVisitor, cname: String, human_name: nullable String, before_params, after_params: nullable String): Array[String]
218 do
219 var cargs = new Array[String]
220 var cparams = new Array[String]
221 if before_params != null then cparams.add(before_params)
222 for i in [0..params.length[ do
223 cargs.add("p{i}")
224 cparams.add("val_t p{i}")
225 end
226 if closure_decls != null then
227 for i in [0..closure_decls.length[ do
228 var closcn = "CLOS_{cname}_{i}"
229 var cs = closure_decls[i].closure.signature
230 var subparams = new Array[String] # Parameters of the closure
231 subparams.add("struct WBT_ *")
232 for j in [0..cs.arity[ do
233 subparams.add("val_t")
234 end
235 var rr = "void"
236 if cs.return_type != null then rr = "val_t"
237 v.add_decl("typedef {rr} (*{closcn})({subparams.join(", ")});")
238 cargs.add("wd{i}")
239 cparams.add("struct WBT_ *wd{i}")
240 end
241 end
242 if after_params != null then cparams.add(after_params)
243 var r = "void"
244 if result != null then r = "val_t"
245 var p: String
246 if cparams.is_empty then
247 p = "void"
248 else
249 p = cparams.join(", ")
250 end
251 if human_name != null then v.add_decl("#define LOCATE_", cname, " \"", human_name, "\"")
252 v.add_decl(r, " ", cname, "(", p, ");")
253 v.add_decl("typedef ", r, " (*", cname, "_t)(", p, ");")
254 v.add_instr(r, " ", cname, "(", p, ")\{")
255 v.indent
256 return cargs
257 end
258
259 # Compile the body of the routine, return the result value is any
260 fun compile_inside_to_c(v: I2CCompilerVisitor, args: Array[String]): nullable String
261 do
262 # Add the trace
263 var ll = 0
264 if location != null then
265 ll = location.line_start
266 end
267 v.add_decl("struct trace_t trace = \{NULL, NULL, {ll}, LOCATE_{v.basecname}\};")
268 v.add_instr("trace.prev = tracehead; tracehead = &trace;")
269 v.add_instr("trace.file = LOCATE_{v.visitor.module.name};")
270
271 # Add local variables
272 if std_slots_nb == 0 then
273 v.add_decl("val_t *REG = NULL;")
274 else
275 v.add_decl("val_t REG[{std_slots_nb}];")
276 end
277 for i in [0..tag_slots_nb[ do
278 v.add_decl("val_t REGB{i};")
279 end
280 var iclosdecls = closure_decls
281 if iclosdecls != null then
282 v.add_decl("struct WBT_ *CREG[{iclosdecls.length}];")
283 else
284 v.add_decl("struct WBT_ **CREG = NULL;")
285 end
286 var k = 0
287 for r in params do
288 if r.slot_index != null then v.add_assignment(v.register(r), args[k])
289 k += 1
290 end
291 if iclosdecls != null then
292 for i in [0..iclosdecls.length[ do
293 var iclosdecl = iclosdecls[i]
294 v.add_instr("CREG[{i}] = {args[params.length+i]};")
295 v.closures[iclosdecl] = i
296 var cs = iclosdecl.closure.signature # Closure signature
297 var subparams = new Array[String] # Parameters of the closure
298 subparams.add("struct WBT_ *")
299 for j in [0..cs.arity[ do
300 var p = "val_t"
301 subparams.add(p)
302 end
303 var r = "void"
304 if cs.return_type != null then r = "val_t"
305 v.clostypes[iclosdecl] = "{r} (*)({subparams.join(", ")})"
306 end
307 end
308 v.add_decl("val_t tmp;")
309
310 # Prepare return
311 var old_rl = v.return_label
312 v.return_label = body
313
314 # Compile body
315 body.compile_to_c(v)
316
317 v.add_instr("tracehead = trace.prev;")
318 v.return_label = old_rl
319 var r = result
320 if r != null then
321 return v.register(r)
322 else
323 return null
324 end
325 end
326
327 # Full compilation of the routine
328 # Including optimization and other stuff.
329 # cv must be in the correct function
330 fun compile_to_c(cv: CompilerVisitor, cname: String, args: Array[String]): nullable String
331 do
332 optimize(cv.module)
333 var v = new I2CCompilerVisitor(cv, self, cname)
334 return compile_inside_to_c(v, args)
335 end
336 end
337
338 redef class ICode
339 # Full compilation of the icode
340 fun compile_to_c(v: I2CCompilerVisitor)
341 do
342 v.add_location(location)
343 store_result(v, inner_compile_to_c(v))
344 end
345
346 # Is a result really needed
347 private fun need_result: Bool
348 do
349 var r = result
350 return r != null and r.slot_index != null
351 end
352
353 # Store s in the result value of self
354 private fun store_result(v: I2CCompilerVisitor, s: nullable String)
355 do
356 var r = result
357 if r != null and r.slot_index != null then
358 assert s != null
359 v.add_assignment(v.register(r), s)
360 else if s != null and not is_pure then
361 # ICode with side effects must be evaluated
362 # even if the result is not wanted
363 v.add_instr(s + ";")
364 end
365 end
366
367 # Compilation of without the result assigment
368 # Return the right value is case of expression
369 # Return the full expression (witout ;) in case of statement
370 private fun inner_compile_to_c(v: I2CCompilerVisitor): nullable String is abstract
371 end
372
373 redef class ISeq
374 redef fun inner_compile_to_c(v)
375 do
376 v.local_labels.add(self)
377 for ic in icodes do
378 ic.compile_to_c(v)
379 end
380 v.add_label(self)
381 return null
382 end
383 end
384
385 redef class IIf
386 redef fun inner_compile_to_c(v)
387 do
388 v.add_instr("if (UNTAG_Bool({v.register(expr)})) \{")
389 if not then_seq.icodes.is_empty then
390 v.indent
391 then_seq.inner_compile_to_c(v)
392 v.unindent
393 end
394 if not else_seq.icodes.is_empty then
395 v.add_instr("} else \{")
396 v.indent
397 else_seq.inner_compile_to_c(v)
398 v.unindent
399 end
400 v.add_instr("}")
401 return null
402 end
403 end
404
405 redef class ILoop
406 redef fun inner_compile_to_c(v)
407 do
408 v.local_labels.add(self)
409 v.add_instr("while(1) \{")
410 v.indent
411 for ic in icodes do
412 ic.compile_to_c(v)
413 end
414 v.unindent
415 v.add_instr("}")
416 v.add_label(self)
417 return null
418 end
419 end
420
421 redef class IEscape
422 redef fun inner_compile_to_c(v)
423 do
424 v.add_goto(seq)
425 return null
426 end
427 end
428
429 redef class IAbsCall
430 redef fun compile_to_c(v)
431 do
432 v.add_location(location)
433 var args = v.registers(exprs)
434
435 # Compile closure definitions
436 var old_el = v.escaped_labels
437 var closdefs = closure_defs
438 var closcns: nullable Array[String] = null
439 if closdefs != null then
440 v.escaped_labels = new HashMap[ISeq, Int]
441 closcns = new Array[String]
442 for cd in closdefs do
443 if cd != null then
444 var cn = cd.compile_closure(v)
445 args.add(cn)
446 closcns.add(cn)
447 else
448 args.add("NULL")
449 end
450 end
451 end
452
453 var s = compile_call_to_c(v, args)
454 var r: nullable String = s
455
456 # Intercept escapes
457 if closcns != null then
458 var els = v.escaped_labels
459 v.escaped_labels = old_el
460 # Is there possible escapes?
461 if not els.is_empty then
462 # Call in a tmp variable to avoid 'break' overwrite
463 if need_result then
464 r = "tmp"
465 v.add_assignment(r, s)
466 else
467 r = null
468 v.add_instr(s + ";")
469 end
470 # What is the escape index (if any?)
471 # It's computed as the union of has_broke
472 var switcha = new Array[String]
473 for cn in closcns do
474 switcha.add("((int)({cn}->has_broke))")
475 end
476 var switch = switcha.join(" | ")
477 # What are the expected escape indexes
478 v.add_instr("switch ({switch}) \{")
479 v.indent
480 # No escape occured, continue as usual
481 v.add_instr("case 0: break;")
482 var lls = v.local_labels
483 var iels = els.iterator
484 var forward_escape = false
485 while iels.is_ok do
486 var seq = iels.key
487 if lls.has(seq) then
488 # Local escape occured
489 v.add_instr("case {iels.item}: goto {v.lab(seq)};")
490 else
491 # Forward escape occured: register the escape label
492 assert v.closure
493 v.register_escape_label(seq)
494 forward_escape = true
495 end
496 iels.next
497 end
498 # Forward escape occured, just pass to the next one
499 if forward_escape then
500 v.add_instr("default: closctx->has_broke = (val_t*)({switch}); goto {v.lab(v.return_label.as(not null))};")
501 end
502 v.unindent
503 v.add_instr("\}")
504 end
505 end
506
507 store_result(v, r)
508 end
509
510 redef fun inner_compile_to_c(v) do abort
511
512 # The single invocation witout fancy stuffs
513 private fun compile_call_to_c(v: I2CCompilerVisitor, args: Array[String]): String is abstract
514 end
515
516 redef class ICall
517 redef fun compile_call_to_c(v, args)
518 do
519 var prop = property
520 if prop.global.is_init then args.add("init_table")
521 if prop.name == (once ("add".to_symbol)) and prop.local_class.name == (once ("Array".to_symbol)) then
522 return "{prop.cname}({args.join(", ")})"
523 else
524 return "{prop.global.meth_call}({args[0]})({args.join(", ")})"
525 end
526 end
527 end
528
529 redef class ISuper
530 redef fun compile_call_to_c(v, args)
531 do
532 var prop = property
533 if prop.global.is_init then args.add("init_table")
534 return "{prop.super_meth_call}({args[0]})({args.join(", ")})"
535 end
536 end
537
538 redef class INew
539 redef fun compile_call_to_c(v, args)
540 do
541 return "NEW_{stype.local_class}_{property.global.intro.cname}({args.join(", ")})"
542 end
543 end
544
545 redef class INative
546 redef fun inner_compile_to_c(v)
547 do
548 if exprs.is_empty then
549 return code
550 else
551 var res = new Buffer
552 var i = 0
553 var c = code.split_with("@@@")
554 for s in c do
555 res.append(s)
556 if i < exprs.length and i < c.length-1 then
557 res.append(v.register(exprs[i]))
558 end
559 i += 1
560 end
561 return res.to_s
562 end
563 end
564 end
565
566 redef class IAbort
567 redef fun inner_compile_to_c(v)
568 do
569 var s = new Buffer.from("fprintf(stderr")
570 for t in texts do
571 s.append(", \"{t}\"")
572 end
573 s.append(");")
574 v.add_instr(s.to_s)
575
576 var ll = location
577 s = new Buffer.from("fprintf(stderr, \" (%s")
578 if ll != null then
579 s.append(":%d")
580 end
581 s.append(")\\n\", LOCATE_{module_location.name}")
582 if ll != null then
583 s.append(", {ll.line_start}")
584 end
585 s.append(");")
586 v.add_instr(s.to_s)
587
588 v.add_instr("nit_exit(1);")
589 return null
590 end
591 end
592
593 redef class IMove
594 redef fun inner_compile_to_c(v)
595 do
596 return v.register(expr)
597 end
598 end
599
600 redef class IAttrRead
601 redef fun inner_compile_to_c(v)
602 do
603 return "{property.global.attr_access}({v.register(expr)})"
604 end
605 end
606
607 redef class IAttrIsset
608 redef fun inner_compile_to_c(v)
609 do
610 return "TAG_Bool({property.global.attr_access}({v.register(expr)})!=NIT_NULL)"
611 end
612 end
613
614 redef class IAttrWrite
615 redef fun inner_compile_to_c(v)
616 do
617 v.add_instr("{property.global.attr_access}({v.register(expr1)}) = {v.register(expr2)};")
618 return null
619 end
620 end
621
622 redef class ITypeCheck
623 redef fun inner_compile_to_c(v)
624 do
625 # FIXME handle formaltypes
626 var g = stype.local_class.global
627 var recv = v.register(expr)
628 var s = ""
629 if expr.stype.is_nullable then
630 if stype.is_nullable then
631 s = "({recv}==NIT_NULL) || "
632 else if stype.as_nullable == expr.stype then
633 return "TAG_Bool({recv}!=NIT_NULL)"
634 else
635 s = "({recv}!=NIT_NULL) && "
636 end
637 end
638 return "TAG_Bool({s}VAL_ISA({recv}, {g.color_id}, {g.id_id})) /*cast {stype}*/"
639 end
640 end
641
642 redef class IIs
643 redef fun inner_compile_to_c(v)
644 do
645 var t1 = expr1.stype
646 var t2 = expr2.stype
647 if t1 isa MMTypeNone then
648 if t2 isa MMTypeNone then
649 return "TAG_Bool(1)"
650 else if t2.is_nullable then
651 return "TAG_Bool({v.register(expr2)}==NIT_NULL)"
652 else
653 return "TAG_Bool(0)"
654 end
655 else if t1.is_nullable then
656 if t2 isa MMTypeNone then
657 return "TAG_Bool({v.register(expr1)}==NIT_NULL)"
658 else if t2.is_nullable then
659 return "TAG_Bool(IS_EQUAL_NN({v.register(expr1)},{v.register(expr2)}))"
660 else
661 return "TAG_Bool(IS_EQUAL_ON({v.register(expr2)},{v.register(expr1)}))"
662 end
663 else
664 if t2 isa MMTypeNone then
665 return "TAG_Bool(0)"
666 else if t2.is_nullable then
667 return "TAG_Bool(IS_EQUAL_ON({v.register(expr1)},{v.register(expr2)}))"
668 else
669 return "TAG_Bool(IS_EQUAL_OO({v.register(expr1)},{v.register(expr2)}))"
670 end
671 end
672 end
673 end
674
675 redef class INot
676 redef fun inner_compile_to_c(v)
677 do
678 return "TAG_Bool(!UNTAG_Bool({v.register(expr)}))"
679 end
680 end
681
682 redef class IOnce
683 redef fun inner_compile_to_c(v)
684 do
685 var i = v.new_number
686 var res = result.as(not null)
687 if res.stype.is_nullable then
688 v.add_decl("static val_t once_value_{i}; static int once_bool_{i}; /* Once value */")
689 v.add_instr("if (!once_bool_{i}) \{")
690 else
691 # Since the value is not nullable, we use the null value to represent the boolean
692 v.add_decl("static val_t once_value_{i}; /* Once value */")
693 v.add_instr("if (!once_value_{i}) \{")
694 end
695 v.indent
696 body.compile_to_c(v)
697 var e = v.register(result.as(not null))
698 v.add_instr("once_value_{i} = {e};")
699 if res.stype.is_nullable then v.add_instr("once_bool_{i} = true;")
700 v.unindent
701 v.add_instr("} else {e} = once_value_{i};")
702 return e
703 end
704 end
705
706 redef class IClosCall
707 redef fun compile_to_c(v: I2CCompilerVisitor)
708 do
709 v.add_location(location)
710 var ivar: String
711 if v.closure then
712 ivar = "closctx->closurevariable[{v.closures[closure_decl]}]"
713 else
714 ivar = "CREG[{v.closures[closure_decl]}]"
715 end
716 var args = [ivar]
717 args.append(v.registers(exprs))
718
719 var s = "(({v.clostypes[closure_decl]})({ivar}->fun))({args.join(", ")})"
720 store_result(v, s)
721
722 v.add_instr("if ({ivar}->has_broke) \{")
723 v.indent
724 var bs = break_seq
725 if bs != null then
726 bs.compile_to_c(v)
727 end
728 v.add_goto(v.iroutine.body)
729 v.unindent
730 v.add_instr("\}")
731 end
732
733 redef fun inner_compile_to_c(v) do abort
734 end
735
736 redef class IHasClos
737 redef fun inner_compile_to_c(v)
738 do
739 var ivar: String
740 if v.closure then
741 ivar = "closctx->closurevariable[{v.closures[closure_decl]}]"
742 else
743 ivar = "CREG[{v.closures[closure_decl]}]"
744 end
745 return "TAG_Bool({ivar} != NULL)"
746 end
747 end
748
749
750 redef class IClosureDef
751 fun compile_closure(v: I2CCompilerVisitor): String
752 do
753 var cfc_old = v.closure
754 v.closure = true
755 var lls_old = v.local_labels
756 v.local_labels = new HashSet[ISeq]
757
758 var cv = v.visitor
759 var ctx_old = cv.ctx
760 cv.ctx = new CContext
761 cv.out_contexts.add(cv.ctx)
762
763 var cname = "OC_{v.basecname}_{v.new_number}"
764 var args = compile_signature_to_c(v.visitor, cname, null, "struct WBT_ *closctx", null)
765 var ctx_old2 = cv.ctx
766 cv.ctx = new CContext
767
768 var s = compile_inside_to_c(v, args)
769 if s == null then
770 v.add_instr("return;")
771 else
772 v.add_instr("return {s};")
773 end
774
775 ctx_old2.append(cv.ctx)
776 cv.ctx = ctx_old2
777 v.unindent
778 v.add_instr("}")
779 cv.ctx = ctx_old
780
781 v.closure = cfc_old
782
783 # Build closure
784 var closcnv = "wbclos{v.new_number}"
785 v.add_decl("struct WBT_ {closcnv};")
786 v.add_instr("{closcnv}.fun = (fun_t){cname};")
787 v.add_instr("{closcnv}.has_broke = NULL;")
788 if cfc_old then
789 v.add_instr("{closcnv}.variable = closctx->variable;")
790 v.add_instr("{closcnv}.closurevariable = closctx->closurevariable;")
791 else
792 v.add_instr("{closcnv}.variable = REG;")
793 v.add_instr("{closcnv}.closurevariable = CREG;")
794 end
795
796 v.local_labels = lls_old
797 return "(&{closcnv})"
798 end
799 end