In order to activate more optimizations and simplify code generators and analysis, the `while` and `for` loops must be transformed into simpler forms (in fact in complex forms but with simpler elements)
However, to do such a transformation, the escaping mechanism (break/continue/goto) must be rewrote.
Previously, for each loop control structure (loop for, while), a single EscapeMark was generated and breaks and continues are associated to the same mark, even if they branch in distinct points (so each escapemark had 2 branching mechanisms)
Now, with the first commits, two escapemarks are generated for each loop control structure, and breaks and continues are associated to a different one. The advantage is that each mark only have a single branching mechanism and that once associated to their mark, there is no need to distinguish break and continue (both become simple gotos).
The transformations of loops can be then implemented.
The `while`
~~~
while cond do block
~~~
is transformed into
~~~
loop if cond then block else break
~~~
and `for`
~~~
for i in col do block
~~~
is transformed into
~~~
var it = col.iterator
loop
if it.is_ok then
var i = it.item
do block
# ^ `continue` in the block it attached to the `do`
# this is why the transformation of escape-marks where needed in fact.
# and break is associated to the main loop
it.next
else
break
end
end
it.finish
~~~
Note that these transformations are basically what is currently implemented in rta, niti and nitg. Except that, now with a single transformation point, those three workers does not need to do their own transformation and basically can just rely on the one done on the AST level.
Pull-Request: #818
Reviewed-by: Lucas Bajolet <r4pass@hotmail.com>
return new ABlockExpr.make
end
+ # Make a new, empty, loop of statements
+ fun make_loop: ALoopExpr
+ do
+ return new ALoopExpr.make
+ end
+
# Make a new variable read
fun make_var_read(variable: Variable, mtype: MType): AVarExpr
do
return new ADoExpr.make
end
+ # Make a new break for a given escapemark
+ fun make_break(escapemark: EscapeMark): ABreakExpr
+ do
+ return new ABreakExpr.make(escapemark)
+ end
+
# Make a new condinionnal
# `mtype` is the return type of the whole if, in case of a ternary operator.
fun make_if(condition: AExpr, mtype: nullable MType): AIfExpr
# Note: this method, aimed to `ABlockExpr` is promoted to `AExpr` because of the limitations of the hierarchies generated by sablecc3
fun add(expr: AExpr)
do
+ print "add not implemented in {inspect}"
abort
end
end
end
end
+redef class ALoopExpr
+ private init make
+ do
+ _n_kwloop = new TKwloop
+ self.is_typed = true
+ n_block = new ABlockExpr
+ n_block.is_typed = true
+ end
+
+ redef fun add(expr: AExpr)
+ do
+ n_block.add expr
+ end
+end
+
redef class ADoExpr
private init make
do
_n_kwdo = new TKwdo
- escapemark = new EscapeMark(null, false)
+ self.is_typed = true
+ n_block = new ABlockExpr
+ n_block.is_typed = true
end
# Make a new break expression of the given do
fun make_break: ABreakExpr
do
- var escapemark = self.escapemark
+ var escapemark = self.break_mark
if escapemark == null then
- escapemark = new EscapeMark(null, false)
- self.escapemark = escapemark
+ escapemark = new EscapeMark(null)
+ self.break_mark = escapemark
end
return new ABreakExpr.make(escapemark)
end
+
+ redef fun add(expr: AExpr)
+ do
+ n_block.add expr
+ end
end
redef class ABreakExpr
private init make(escapemark: EscapeMark)
do
+ _n_kwbreak = new TKwbreak
self.escapemark = escapemark
+ escapemark.escapes.add self
+ self.is_typed = true
end
end
var opt_compile_dir = new OptionString("Directory used to generate temporary files", "--compile-dir")
# --hardening
var opt_hardening = new OptionBool("Generate contracts in the C code against bugs in the compiler", "--hardening")
- # --no-shortcut-range
- var opt_no_shortcut_range = new OptionBool("Always insantiate a range and its iterator on 'for' loops", "--no-shortcut-range")
# --no-check-covariance
var opt_no_check_covariance = new OptionBool("Disable type tests of covariant parameters (dangerous)", "--no-check-covariance")
# --no-check-attr-isset
redef init
do
super
- self.option_context.add_option(self.opt_output, self.opt_dir, self.opt_no_cc, self.opt_no_main, self.opt_make_flags, self.opt_compile_dir, self.opt_hardening, self.opt_no_shortcut_range)
+ self.option_context.add_option(self.opt_output, self.opt_dir, self.opt_no_cc, self.opt_no_main, self.opt_make_flags, self.opt_compile_dir, self.opt_hardening)
self.option_context.add_option(self.opt_no_check_covariance, self.opt_no_check_attr_isset, self.opt_no_check_assert, self.opt_no_check_autocast, self.opt_no_check_null, self.opt_no_check_all)
self.option_context.add_option(self.opt_typing_test_metrics, self.opt_invocation_metrics, self.opt_isset_checks_metrics)
self.option_context.add_option(self.opt_stacktrace)
return name
end
+ # Insert a C label for associated with an escapemark
+ fun add_escape_label(e: nullable EscapeMark)
+ do
+ if e == null then return
+ if e.escapes.is_empty then return
+ add("BREAK_{escapemark_name(e)}: (void)0;")
+ end
+
private var escapemark_names = new HashMap[EscapeMark, String]
# Return a "const char*" variable associated to the classname of the dynamic type of an object
redef fun expr(v) do return v.frame.arguments.first
end
-redef class AContinueExpr
- redef fun stmt(v) do v.add("goto CONTINUE_{v.escapemark_name(self.escapemark)};")
-end
-
-redef class ABreakExpr
+redef class AEscapeExpr
redef fun stmt(v) do v.add("goto BREAK_{v.escapemark_name(self.escapemark)};")
end
redef fun stmt(v)
do
v.stmt(self.n_block)
- var escapemark = self.escapemark
- if escapemark != null then
- v.add("BREAK_{v.escapemark_name(escapemark)}: (void)0;")
- end
+ v.add_escape_label(break_mark)
end
end
var cond = v.expr_bool(self.n_expr)
v.add("if (!{cond}) break;")
v.stmt(self.n_block)
- v.add("CONTINUE_{v.escapemark_name(escapemark)}: (void)0;")
+ v.add_escape_label(continue_mark)
v.add("\}")
- v.add("BREAK_{v.escapemark_name(escapemark)}: (void)0;")
+ v.add_escape_label(break_mark)
end
end
do
v.add("for(;;) \{")
v.stmt(self.n_block)
- v.add("CONTINUE_{v.escapemark_name(escapemark)}: (void)0;")
+ v.add_escape_label(continue_mark)
v.add("\}")
- v.add("BREAK_{v.escapemark_name(escapemark)}: (void)0;")
+ v.add_escape_label(break_mark)
end
end
redef class AForExpr
redef fun stmt(v)
do
- # Shortcut on explicit range
- # Avoid the instantiation of the range and the iterator
- var nexpr = self.n_expr
- if self.variables.length == 1 and nexpr isa ARangeExpr and not v.compiler.modelbuilder.toolcontext.opt_no_shortcut_range.value then
- var from = v.expr(nexpr.n_expr, null)
- var to = v.expr(nexpr.n_expr2, null)
- var variable = v.variable(variables.first)
- var one = v.new_expr("1", v.get_class("Int").mclass_type)
-
- v.assign(variable, from)
- v.add("for(;;) \{ /* shortcut range */")
-
- var ok
- if nexpr isa AOrangeExpr then
- ok = v.send(v.get_property("<", variable.mtype), [variable, to])
- else
- ok = v.send(v.get_property("<=", variable.mtype), [variable, to])
- end
- assert ok != null
- v.add("if(!{ok}) break;")
-
- v.stmt(self.n_block)
-
- v.add("CONTINUE_{v.escapemark_name(escapemark)}: (void)0;")
- var succ = v.send(v.get_property("successor", variable.mtype), [variable, one])
- assert succ != null
- v.assign(variable, succ)
- v.add("\}")
- v.add("BREAK_{v.escapemark_name(escapemark)}: (void)0;")
- return
- end
-
var cl = v.expr(self.n_expr, null)
var it_meth = self.method_iterator
assert it_meth != null
abort
end
v.stmt(self.n_block)
- v.add("CONTINUE_{v.escapemark_name(escapemark)}: (void)0;")
+ v.add_escape_label(continue_mark)
var next_meth = self.method_next
assert next_meth != null
v.compile_callsite(next_meth, [it])
v.add("\}")
- v.add("BREAK_{v.escapemark_name(escapemark)}: (void)0;")
+ v.add_escape_label(break_mark)
var method_finish = self.method_finish
if method_finish != null then
end
end
-redef class AContinueExpr
- redef fun after_simple_misc(v)
- do
- var e = n_expr
- if e != null then
- e.warn_parentheses(v)
- end
- end
-end
-
-redef class ABreakExpr
+redef class AEscapeExpr
redef fun after_simple_misc(v)
do
var e = n_expr
# Set this mark to skip the evaluation until the end of the specified method frame
var returnmark: nullable Frame = null
- # Is a break executed?
- # Set this mark to skip the evaluation until a labeled statement catch it with `is_break`
- var breakmark: nullable EscapeMark = null
-
- # Is a continue executed?
- # Set this mark to skip the evaluation until a labeled statement catch it with `is_continue`
- var continuemark: nullable EscapeMark = null
+ # Is a break or a continue executed?
+ # Set this mark to skip the evaluation until a labeled statement catch it with `is_escape`
+ var escapemark: nullable EscapeMark = null
# Is a return or a break or a continue executed?
# Use this function to know if you must skip the evaluation of statements
- fun is_escaping: Bool do return returnmark != null or breakmark != null or continuemark != null
+ fun is_escaping: Bool do return returnmark != null or escapemark != null
# The value associated with the current return/break/continue, if any.
# Set the value when you set a escapemark.
# Read the value when you catch a mark or reach the end of a method
var escapevalue: nullable Instance = null
- # If there is a break and is associated with `escapemark`, then return true an clear the mark.
- # If there is no break or if `escapemark` is null then return false.
- # Use this function to catch a potential break.
- fun is_break(escapemark: nullable EscapeMark): Bool
- do
- if escapemark != null and self.breakmark == escapemark then
- self.breakmark = null
- return true
- else
- return false
- end
- end
-
- # If there is a continue and is associated with `escapemark`, then return true an clear the mark.
- # If there is no continue or if `escapemark` is null then return false.
- # Use this function to catch a potential continue.
- fun is_continue(escapemark: nullable EscapeMark): Bool
+ # If there is a break/continue and is associated with `escapemark`, then return true and clear the mark.
+ # If there is no break/continue or if `escapemark` is null then return false.
+ # Use this function to catch a potential break/continue.
+ fun is_escape(escapemark: nullable EscapeMark): Bool
do
- if escapemark != null and self.continuemark == escapemark then
- self.continuemark = null
+ if escapemark != null and self.escapemark == escapemark then
+ self.escapemark = null
return true
else
return false
end
end
-redef class AContinueExpr
- redef fun stmt(v)
- do
- var ne = self.n_expr
- if ne != null then
- var i = v.expr(ne)
- if i == null then return
- v.escapevalue = i
- end
- v.continuemark = self.escapemark
- end
-end
-
-redef class ABreakExpr
+redef class AEscapeExpr
redef fun stmt(v)
do
var ne = self.n_expr
if i == null then return
v.escapevalue = i
end
- v.breakmark = self.escapemark
+ v.escapemark = self.escapemark
end
end
redef fun stmt(v)
do
v.stmt(self.n_block)
- v.is_break(self.escapemark) # Clear the break (if any)
+ v.is_escape(self.break_mark) # Clear the break (if any)
end
end
if cond == null then return
if not cond.is_true then return
v.stmt(self.n_block)
- if v.is_break(self.escapemark) then return
- v.is_continue(self.escapemark) # Clear the break
+ if v.is_escape(self.break_mark) then return
+ v.is_escape(self.continue_mark) # Clear the break
if v.is_escaping then return
end
end
do
loop
v.stmt(self.n_block)
- if v.is_break(self.escapemark) then return
- v.is_continue(self.escapemark) # Clear the break
+ if v.is_escape(self.break_mark) then return
+ v.is_escape(self.continue_mark) # Clear the break
if v.is_escaping then return
end
end
abort
end
v.stmt(self.n_block)
- if v.is_break(self.escapemark) then break
- v.is_continue(self.escapemark) # Clear the break
+ if v.is_escape(self.break_mark) then break
+ v.is_escape(self.continue_mark) # Clear the break
if v.is_escaping then break
v.callsite(method_next, [iter])
end
var n_label: nullable ALabel = null is writable
end
-# A `break` statement.
-class ABreakExpr
+# A `break` or a `continue`
+abstract class AEscapeExpr
super AExpr
super ALabelable
- var n_kwbreak: TKwbreak is writable, noinit
var n_expr: nullable AExpr = null is writable
end
+# A `break` statement.
+class ABreakExpr
+ super AEscapeExpr
+ var n_kwbreak: TKwbreak is writable, noinit
+end
+
# An `abort` statement
class AAbortExpr
super AExpr
# A `continue` statement
class AContinueExpr
- super AExpr
- super ALabelable
+ super AEscapeExpr
var n_kwcontinue: nullable TKwcontinue = null is writable
- var n_expr: nullable AExpr = null is writable
end
# A `do` statement
fun merge_continues_to(before_loop: FlowContext, escapemark: nullable EscapeMark)
do
if escapemark == null then return
- for b in escapemark.continues do
+ for b in escapemark.escapes do
var before = b.before_flow_context
if before == null then continue # Forward error
before_loop.add_loop(before)
fun merge_breaks(escapemark: nullable EscapeMark)
do
if escapemark == null then return
- for b in escapemark.breaks do
+ for b in escapemark.escapes do
var before = b.before_flow_context
if before == null then continue # Forward error
self.make_merge_flow(self.current_flow_context, before)
end
end
-redef class AContinueExpr
- # The flow just before it become unreachable
- fun before_flow_context: nullable FlowContext
- do
- var after = self.after_flow_context
- if after == null then return null
- return after.previous.first
- end
- redef fun accept_flow_visitor(v)
- do
- super
- v.make_unreachable_flow
- end
-end
-
-redef class ABreakExpr
+redef class AEscapeExpr
# The flow just before it become unreachable
fun before_flow_context: nullable FlowContext
do
redef fun accept_flow_visitor(v)
do
super
- v.merge_breaks(self.escapemark)
+ v.merge_breaks(self.break_mark)
end
end
var after_block = v.current_flow_context
before_loop.add_loop(after_block)
- v.merge_continues_to(after_block, self.escapemark)
+ v.merge_continues_to(after_block, self.continue_mark)
v.current_flow_context = after_expr.when_false
- v.merge_breaks(self.escapemark)
+ v.merge_breaks(self.break_mark)
end
end
var after_block = v.current_flow_context
before_loop.add_loop(after_block)
- v.merge_continues_to(after_block, self.escapemark)
+ v.merge_continues_to(after_block, self.continue_mark)
v.make_unreachable_flow
- v.merge_breaks(self.escapemark)
+ v.merge_breaks(self.break_mark)
end
end
var after_block = v.current_flow_context
before_loop.add_loop(after_block)
- v.merge_continues_to(after_block, self.escapemark)
+ v.merge_continues_to(after_block, self.continue_mark)
v.make_merge_flow(v.current_flow_context, before_loop)
- v.merge_breaks(self.escapemark)
+ v.merge_breaks(self.break_mark)
end
end
# The name of the label (unless the mark is an anonymous loop mark)
var name: nullable String
- # Is the mark attached to a loop (loop, while, for)
- # Such a mark is a candidate to a labelless 'continue' or 'break'
- var for_loop: Bool
+ # The associated `continue` mark, if any.
+ # If the mark attached to a loop (loop, while, for), a distinct mark is used.
+ private var continue_mark: nullable EscapeMark = null
- # Each 'continue' attached to the mark
- var continues = new Array[AContinueExpr]
-
- # Each 'break' attached to the mark
- var breaks = new Array[ABreakExpr]
+ # Each break/continue attached to the mark
+ var escapes = new Array[AEscapeExpr]
end
# Visit a npropdef and:
end
# All stacked scope. `scopes.first` is the current scope
- private var scopes = new List[Scope]
+ var scopes = new List[Scope]
# Shift and check the last scope
fun shift_scope
else
name = null
end
- var res = new EscapeMark(name, for_loop)
+ var res = new EscapeMark(name)
+ if for_loop then res.continue_mark = new EscapeMark(name)
return res
end
end
end
-redef class AContinueExpr
- # The escape mark associated with the continue
+redef class AEscapeExpr
+ # The escape mark associated with the break/continue
var escapemark: nullable EscapeMark
+end
+
+redef class AContinueExpr
redef fun accept_scope_visitor(v)
do
super
var escapemark = v.get_escapemark(self, self.n_label)
if escapemark == null then return # Skip error
- if not escapemark.for_loop then
+ escapemark = escapemark.continue_mark
+ if escapemark == null then
v.error(self, "Error: cannot 'continue', only 'break'.")
+ return
end
- escapemark.continues.add(self)
+ escapemark.escapes.add(self)
self.escapemark = escapemark
end
end
redef class ABreakExpr
- # The escape mark associated with the break
- var escapemark: nullable EscapeMark
redef fun accept_scope_visitor(v)
do
super
var escapemark = v.get_escapemark(self, self.n_label)
if escapemark == null then return # Skip error
- escapemark.breaks.add(self)
+ escapemark.escapes.add(self)
self.escapemark = escapemark
end
end
redef class ADoExpr
- # The escape mark associated with the 'do' block
- var escapemark: nullable EscapeMark
+ # The break escape mark associated with the 'do' block
+ var break_mark: nullable EscapeMark
+
redef fun accept_scope_visitor(v)
do
- self.escapemark = v.make_escape_mark(n_label, false)
- v.enter_visit_block(n_block, self.escapemark)
+ self.break_mark = v.make_escape_mark(n_label, false)
+ v.enter_visit_block(n_block, self.break_mark)
end
end
end
redef class AWhileExpr
- # The escape mark associated with the 'while'
- var escapemark: nullable EscapeMark
+ # The break escape mark associated with the 'while'
+ var break_mark: nullable EscapeMark
+
+ # The continue escape mark associated with the 'while'
+ var continue_mark: nullable EscapeMark
+
redef fun accept_scope_visitor(v)
do
var escapemark = v.make_escape_mark(n_label, true)
- self.escapemark = escapemark
+ self.break_mark = escapemark
+ self.continue_mark = escapemark.continue_mark
v.enter_visit(n_expr)
v.enter_visit_block(n_block, escapemark)
end
end
redef class ALoopExpr
- # The escape mark associated with the 'loop'
- var escapemark: nullable EscapeMark
+ # The break escape mark associated with the 'loop'
+ var break_mark: nullable EscapeMark
+
+ # The continue escape mark associated with the 'loop'
+ var continue_mark: nullable EscapeMark
+
redef fun accept_scope_visitor(v)
do
var escapemark = v.make_escape_mark(n_label, true)
- self.escapemark = escapemark
+ self.break_mark = escapemark
+ self.continue_mark = escapemark.continue_mark
v.enter_visit_block(n_block, escapemark)
end
end
# The automatic variables in order
var variables: nullable Array[Variable]
- # The escape mark associated with the 'for'
- var escapemark: nullable EscapeMark
+ # The break escape mark associated with the 'for'
+ var break_mark: nullable EscapeMark
+
+ # The continue escape mark associated with the 'for'
+ var continue_mark: nullable EscapeMark
redef fun accept_scope_visitor(v)
do
end
var escapemark = v.make_escape_mark(n_label, true)
- self.escapemark = escapemark
+ self.break_mark = escapemark
+ self.continue_mark = escapemark.continue_mark
v.enter_visit_block(n_block, escapemark)
v.shift_scope
var method_key: nullable CallSite
var method_finish: nullable CallSite
+ var method_lt: nullable CallSite
+ var method_successor: nullable CallSite
+
private fun do_type_iterator(v: TypeVisitor, mtype: MType)
do
if mtype isa MNullType then
end
self.method_key = keydef
end
+
+ if self.variables.length == 1 and n_expr isa ARangeExpr then
+ var variable = variables.first
+ var vtype = variable.declared_type.as(not null)
+
+ if n_expr isa AOrangeExpr then
+ self.method_lt = v.get_method(self, vtype, "<", false)
+ else
+ self.method_lt = v.get_method(self, vtype, "<=", false)
+ end
+
+ self.method_successor = v.get_method(self, vtype, "successor", false)
+ end
end
redef fun accept_typing(v)
import astbuilder
import astvalidation
import semantize
+intrude import semantize::scope
redef class ToolContext
var transform_phase: Phase = new TransformPhase(self, [typing_phase, auto_super_init_phase])
+
+ # --no-shortcut-range
+ var opt_no_shortcut_range: OptionBool = new OptionBool("Always insantiate a range and its iterator on 'for' loops", "--no-shortcut-range")
+
+ redef init
+ do
+ super
+ self.option_context.add_option(self.opt_no_shortcut_range)
+ end
end
private class TransformPhase
redef class AWhileExpr
redef fun accept_transform_visitor(v)
do
- # TODO
+ var nloop = v.builder.make_loop
+ var nif = v.builder.make_if(n_expr, null)
+ nloop.add nif
+
+ var nblock = n_block
+ if nblock != null then nif.n_then.add nblock
+
+ var escapemark = self.break_mark.as(not null)
+ var nbreak = v.builder.make_break(escapemark)
+ nif.n_else.add nbreak
+
+ nloop.break_mark = self.break_mark
+ nloop.continue_mark = self.continue_mark
+
+ replace_with(nloop)
end
end
redef class AForExpr
redef fun accept_transform_visitor(v)
do
- # TODO
+ var escapemark = self.break_mark
+ assert escapemark != null
+
+ var nblock = v.builder.make_block
+
+ var nexpr = n_expr
+
+ # Shortcut on explicit range
+ # Avoid the instantiation of the range and the iterator
+ if self.variables.length == 1 and nexpr isa ARangeExpr and not v.phase.toolcontext.opt_no_shortcut_range.value then
+ var variable = variables.first
+ nblock.add v.builder.make_var_assign(variable, nexpr.n_expr)
+ var to = nexpr.n_expr2
+ nblock.add to
+
+ var nloop = v.builder.make_loop
+ nloop.break_mark = escapemark
+ nblock.add nloop
+
+ var is_ok = v.builder.make_call(v.builder.make_var_read(variable, variable.declared_type.as(not null)), method_lt.as(not null), [to.make_var_read])
+
+ var nif = v.builder.make_if(is_ok, null)
+ nloop.add nif
+
+ var nthen = nif.n_then
+ var ndo = v.builder.make_do
+ ndo.break_mark = escapemark.continue_mark
+ nthen.add ndo
+
+ ndo.add self.n_block.as(not null)
+
+ var one = v.builder.make_int(1)
+ var succ = v.builder.make_call(v.builder.make_var_read(variable, variable.declared_type.as(not null)), method_successor.as(not null), [one])
+ nthen.add v.builder.make_var_assign(variable, succ)
+
+ var nbreak = v.builder.make_break(escapemark)
+ nif.n_else.add nbreak
+
+ replace_with(nblock)
+ return
+ end
+
+ nblock.add nexpr
+
+ var iter = v.builder.make_call(nexpr.make_var_read, method_iterator.as(not null), null)
+ nblock.add iter
+
+ var nloop = v.builder.make_loop
+ nloop.break_mark = escapemark
+ nblock.add nloop
+
+ var is_ok = v.builder.make_call(iter.make_var_read, method_is_ok.as(not null), null)
+
+ var nif = v.builder.make_if(is_ok, null)
+ nloop.add nif
+
+ var nthen = nif.n_then
+ var ndo = v.builder.make_do
+ ndo.break_mark = escapemark.continue_mark
+ nthen.add ndo
+
+ if self.variables.length == 1 then
+ var item = v.builder.make_call(iter.make_var_read, method_item.as(not null), null)
+ ndo.add v.builder.make_var_assign(variables.first, item)
+ else if self.variables.length == 2 then
+ var key = v.builder.make_call(iter.make_var_read, method_key.as(not null), null)
+ ndo.add v.builder.make_var_assign(variables[0], key)
+ var item = v.builder.make_call(iter.make_var_read, method_item.as(not null), null)
+ ndo.add v.builder.make_var_assign(variables[1], item)
+ else
+ abort
+ end
+
+ ndo.add self.n_block.as(not null)
+
+ nthen.add v.builder.make_call(iter.make_var_read, method_next.as(not null), null)
+
+ var nbreak = v.builder.make_break(escapemark)
+ nif.n_else.add nbreak
+
+ var method_finish = self.method_finish
+ if method_finish != null then
+ nblock.add v.builder.make_call(iter.make_var_read, method_finish, null)
+ end
+
+ replace_with(nblock)
end
end
nitlanguage / nit.git / commitdiff