Merge: doc: fixed some typos and other misc. corrections

[nit.git] / src / ssa.nit

# This file is part of NIT ( http://www.nitlanguage.org ).
#
# Copyright 2015 Julien Pagès <julien.pages@lirmm.fr>
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

# Single-Static Assignment algorithm from an AST
module ssa

import semantize
import astbuilder

# Represent a sequence of the program
# A basic block is composed of several instructions without a jump
class BasicBlock
        # First instruction of the basic block
        var first: ANode is noinit

        # Last instruction of the basic block
        var last: ANode is noinit

        # Direct successors
        var successors = new Array[BasicBlock]

        # Direct predecessors
        var predecessors = new Array[BasicBlock]

        # Parts of AST that contain a read to a variable
        var read_sites = new Array[AVarFormExpr]

        # Parts of AST that contain a write to a variable
        var write_sites = new Array[AVarFormExpr]

        # Parts of AST that contain a variable access (read or write)
        var variables_sites = new Array[AExpr]

        # The iterated dominance frontier of this block
        # i.e. the set of blocks this block dominate directly or indirectly
        var dominance_frontier: Array[BasicBlock] = new Array[BasicBlock] is lazy

        # Self is the old block to link to the new,
        # The two blocks are not linked if the current ends with a `AReturnExpr` or `ABreakExpr`
        # i.e. self is the predecessor of `successor`
        # `successor` The successor block
        fun link(successor: BasicBlock)
        do
                # Do not link the two blocks if the current block end with a return, break or continue
                if last isa AReturnExpr or last isa ABreakExpr or last isa AContinueExpr then return

                successors.add(successor)
                successor.predecessors.add(self)
        end

        # Self is the old block to link to the new
        # i.e. self is the predecessor of `successor`
        # `successor` The successor block
        fun link_special(successor: BasicBlock)
        do
                # Link the two blocks even if the current block ends with a return or a break
                successors.add(successor)
                successor.predecessors.add(self)
        end

        # Add the `block` to the dominance frontier of this block
        fun add_df(block: BasicBlock)
        do
                dominance_frontier.add(block)

                # Add this block recursively in super-blocks to compute the iterated
                # dominance frontier
                for successor in block.successors do
                        # If this successor has not already been add to the dominance frontier
                        if not dominance_frontier.has(successor) then
                                add_df(successor)
                        end
                end
        end

        # Compute recursively the dominance frontier of self block and its successors
        private fun compute_df
        do
                # Treat each block only one time
                df_computed = true

                for s in successors do
                        add_df(s)

                        if not s.df_computed then s.compute_df
                end
        end

        # Used to handle recursions by treating only one time each block
        var treated: Bool = false

        # Used to dump the BasicBlock to dot
        var treated_debug: Bool = false

        # If true, the iterated dominance frontier of this block has been computed
        var df_computed: Bool = false

        # Indicate the BasicBlock is newly created and needs to be updated
        var need_update: Bool = false

        # Indicate if the variables renaming step has been made for this block
        var is_renaming: Bool = false

        # The variables that are accessed in this block
        var variables = new Array[Variable] is lazy

        # The PhiFunction this block contains at the beginning
        var phi_functions = new Array[PhiFunction] is lazy
end

# Contain the currently analyzed propdef
class SSA
        # The currently analyzed APropdef
        var propdef: APropdef

        # The PhiFunction `current_propdef` contains
        var phi_functions = new Array[PhiFunction]

        # Recursively generate the basic blocks for this propdef
        fun generate_basic_blocks
        do
                propdef.generate_basic_blocks(self)
        end
end

redef class Variable
        # The expressions of AST of this variable depends
        var dep_exprs = new Array[AExpr]

        # The blocks in which this variable is assigned
        var assignment_blocks: Array[BasicBlock] = new Array[BasicBlock] is lazy

        # Part of the program where this variable is read
        var read_blocks: Array[BasicBlock] = new Array[BasicBlock] is lazy

        # The stack of this variable, used for SSA renaming
        var stack = new Array[Variable] is lazy

        # The original Variable in case of renaming
        var original_variable: nullable Variable = self

        # If true, this variable is a parameter of a method
        var parameter: Bool = false
end

# A PhiFunction is a kind of Variable used in SSA-construction,
# it is placed at the beginning of a BasicBlock with many incoming blocks
class PhiFunction
        super Variable

        # The dependences of this variable for SSA-Algorithm
        var dependences = new Array[Couple[Variable, BasicBlock]]

        # The position in the AST of the phi-function
        var block: BasicBlock

        # Set the dependences for the phi-function
        # *`block` BasicBlock in which we go through the dominance-frontier
        # *`v` The variable to looking for
        fun add_dependences(block: BasicBlock, v: Variable)
        do
                # Look in which blocks of DF(block) `v` has been assigned
                for b in block.predecessors do
                        if v.assignment_blocks.has(b) then
                                var dep = new Couple[Variable, BasicBlock](v, b)
                                dependences.add(dep)
                        end
                end
        end

        # Print the PhiFunction with all its dependences
        redef fun to_s: String
        do
                var s = ""
                s += " dependences = [ "
                for d in dependences do
                        s += d.first.to_s + " "
                end
                s += "]"

                return s
        end
end

redef class APropdef
        # The variables contained in the body on this propdef
        var variables: HashSet[Variable] = new HashSet[Variable] is lazy

        # The first basic block of the code
        var basic_block: nullable BasicBlock

        # If true, the basic blocks where generated
        var is_generated: Bool = false

        # Generate all basic blocks for this code
        fun generate_basic_blocks(ssa: SSA) is abstract

        # Contain all AST-parts related to object mechanisms the propdef has:
        # instantiation, method dispatch, attribute access, subtyping-test
        var object_sites: Array[AExpr] = new Array[AExpr]

        # The return variable of the propdef
        # Create an empty variable for the return of the method
        # and treat returns like variable assignments
        var returnvar: Variable = new Variable("returnvar")

        # Compute the three steps of SSA-algorithm
        # `ssa` A new instance of SSA class initialized with `self`
        fun compute_ssa(ssa: SSA)
        do
                if is_generated then return

                # The first step is to generate the basic blocks
                generate_basic_blocks(ssa)

                # The propdef has no body (abstract)
                if not is_generated then return

                # Once basic blocks were generated, compute SSA algorithm
                compute_phi(ssa)
                rename_variables(ssa)
                ssa_destruction(ssa)
        end

        # Compute the first phase of SSA algorithm: placing phi-functions
        fun compute_phi(ssa: SSA)
        do
                var root_block = basic_block.as(not null)

                # Compute the iterated dominance frontier of the graph of basic blocks
                root_block.compute_df

                # Places where a phi-function is added per variable
                var phi_blocks = new HashMap[Variable, Array[BasicBlock]]

                # For each variables in the propdef
                for v in variables do
                        var phi_variables = new Array[BasicBlock]

                        var read_blocks = new Array[BasicBlock]
                        read_blocks.add_all(v.read_blocks)
                        read_blocks.add_all(v.assignment_blocks)

                        # While we have not treated each part accessing `v`
                        while not read_blocks.is_empty do
                                # Remove a block from the array
                                var block = read_blocks.shift

                                # For each block in the dominance frontier of `block`
                                for df in block.dominance_frontier do
                                        # If we have not yet put a phi-function at the beginning of this block
                                        if not phi_variables.has(df) then
                                                phi_variables.add(df)

                                                # Create a new phi-function and set its dependences
                                                var phi = new PhiFunction("phi", df)
                                                phi.add_dependences(df, v)
                                                phi.block = df
                                                phi.original_variable = phi
                                                phi.declared_type = v.declared_type

                                                # Indicate this phi-function is assigned in this block
                                                phi.assignment_blocks.add(block)
                                                ssa.phi_functions.add(phi)

                                                # Add a phi-function at the beginning of df for variable v
                                                df.phi_functions.add(phi)

                                                if not v.read_blocks.has(df) or not v.assignment_blocks.has(df) then read_blocks.add(df)
                                        end
                                end
                        end

                        # Add `phi-variables` to the global map
                        phi_blocks[v] = phi_variables
                end
        end

        # Compute the second phase of SSA algorithm: renaming variables
        # NOTE: `compute_phi` must has been called before
        fun rename_variables(ssa: SSA)
        do
                # A counter for each variable
                # The key is the variable, the value the number of assignment into the variable
                var counter = new HashMap[Variable, Int]

                for v in variables do
                        counter[v] = 0
                        v.stack.push(v)
                end

                for phi in ssa.phi_functions do counter[phi] = 0

                # Launch the recursive renaming from the root block
                rename(basic_block.as(not null), counter, ssa)
        end

        # Recursively rename each variable from `block`
        # *`block` The starting basic block
        # *`counter` The key is the variable, the value the number of assignment into the variable
        fun rename(block: BasicBlock, counter: HashMap[Variable, Int], ssa: SSA)
        do
                if block.is_renaming then return

                block.is_renaming = true

                # For each phi-function of this block
                for phi in block.phi_functions do
                        generate_name(phi, counter, block.first, ssa)

                        # Replace the phi into the block
                        block.phi_functions[block.phi_functions.index_of(phi)] = phi.original_variable.stack.last.as(PhiFunction)
                end

                # For each variable read in `block`
                for vread in block.read_sites do
                        # Replace the old variable in AST
                        vread.variable = vread.variable.original_variable.stack.last
                end

                # For each variable write
                for vwrite in block.write_sites do
                        generate_name(vwrite.variable.as(not null), counter, vwrite, ssa)

                        var new_version = vwrite.variable.original_variable.stack.last

                        # Set dependence of the new variable
                        if vwrite isa AVarReassignExpr then
                                new_version.dep_exprs.add(vwrite.n_value)
                        else if vwrite isa AVarAssignExpr then
                                new_version.dep_exprs.add(vwrite.n_value)
                        end

                        # Replace the old variable by the last created
                        vwrite.variable = new_version
                end

                # Rename occurrence of old names in phi-function
                for successor in block.dominance_frontier do
                        for sphi in successor.phi_functions do
                                # Go over the couples in the phi dependences to rename variables
                                for couple in sphi.dependences do
                                        if couple.second == block then
                                                # Rename this variable
                                                couple.first = couple.first.original_variable.stack.last
                                        end
                                end
                        end
                end

                # Recurse in successor blocks
                for successor in block.successors do
                        rename(successor, counter, ssa)
                end

                # Pop old names off the stack for each phi-function
                for phi in block.phi_functions do
                        if not phi.stack.is_empty then phi.stack.pop
                end
        end

        # Generate a new version of the variable `v` and return it
        # *`v` The variable for which we generate a name
        # *`counter` The key is the variable, the value the number of assignment into the variable
        # *`expr` The AST node in which the assignment of v is made
        # *`ssa` The instance of SSA
        fun generate_name(v: Variable, counter: HashMap[Variable, Int], expr: ANode, ssa: SSA): Variable
        do
                var original_variable = v.original_variable.as(not null)

                var i = counter[original_variable]

                var new_version: Variable

                # Create a new version of Variable
                if original_variable isa PhiFunction then
                        var block = original_variable.block
                        new_version = new PhiFunction(original_variable.name + i.to_s, block)
                        new_version.dependences.add_all(original_variable.dependences)
                        ssa.phi_functions.add(new_version)
                else
                        new_version = new Variable(original_variable.name + i.to_s)
                        new_version.declared_type = expr.as(AVarFormExpr).variable.declared_type
                        variables.add(new_version)
                end

                # Recopy the fields into the new version
                new_version.location = expr.location
                new_version.original_variable = original_variable

                # Push a new version on the stack
                original_variable.stack.add(new_version)
                counter[v] = i + 1

                return new_version
        end

        # Transform SSA-representation into an executable code (delete phi-functions)
        # `ssa` Current instance of SSA
        fun ssa_destruction(ssa: SSA)
        do
                var builder = new ASTBuilder(mpropdef.mclassdef.mmodule, mpropdef.mclassdef.bound_mtype)

                # Iterate over all phi-functions
                for phi in ssa.phi_functions do
                        for dep in phi.dependences do
                                # dep.second is the block where we need to create a varassign
                                var var_read = builder.make_var_read(dep.first, dep.first.declared_type.as(not null))
                                var nvar = builder.make_var_assign(dep.first, var_read)

                                var block = dep.second.last.parent

                                # This variable read must be add to a ABlockExpr
                                if block isa ABlockExpr then
                                        block.add(nvar)
                                end

                                propagate_dependences(phi, phi.block)
                                ssa.propdef.variables.add(dep.first)
                        end
                end
        end

        # Propagate the dependences of the phi-functions into following variables
        # `phi` The PhiFunction
        # `block` Current block where we propagate dependences
        fun propagate_dependences(phi: PhiFunction, block: BasicBlock)
        do
                # Treat each block once
                if block.treated then return

                # For each variable access site in the block
                for site in block.variables_sites do
                        if site isa AVarExpr then
                                # Propagate the dependences of the phi-function in variables after the phi
                                for dep in phi.dependences do
                                        for expr in dep.first.dep_exprs do
                                                if site.variable.dep_exprs.has(expr) then break

                                                if dep.first.original_variable == site.variable.original_variable then
                                                        site.variable.dep_exprs.add(expr)
                                                end
                                        end
                                end
                        else
                                # The site is a variable write, we stop the propagation
                                return
                        end
                end

                block.treated = true

                # If we do not meet a variable write, continue the propagation
                for b in block.successors do propagate_dependences(phi, b)
        end
end

redef class AAttrPropdef
        redef fun generate_basic_blocks(ssa: SSA)
        do
                basic_block = new BasicBlock
                basic_block.first = self
                basic_block.last = self

                # Add the return variable
                variables.add(returnvar)

                # Add the self variable
                if self.selfvariable != null then variables.add(selfvariable.as(not null))

                # Recursively goes into the nodes
                if n_block != null then
                        n_block.generate_basic_blocks(ssa, basic_block.as(not null))
                        is_generated = true
                end
        end
end

redef class AMethPropdef
        redef fun generate_basic_blocks(ssa: SSA)
        do
                basic_block = new BasicBlock
                basic_block.first = self
                basic_block.last = self

                # If the method has a signature
                if n_signature != null then
                        for p in n_signature.n_params do
                                # Add parameters to the local variables
                                variables.add(p.variable.as(not null))
                                p.variable.parameter = true
                        end
                end

                # Add the return variable
                variables.add(returnvar)

                # Add the self variable
                if self.selfvariable != null then variables.add(selfvariable.as(not null))

                # Recursively goes into the nodes
                if n_block != null then
                        n_block.generate_basic_blocks(ssa, basic_block.as(not null))
                        is_generated = true
                end
        end
end

# Utility class for dump basic block and SSA output to dot files
class BlockDebug
        # The output file
        var file: FileWriter

        # Dump all the hierarchy of BasicBlock from `block` to the leaves
        fun dump(block: BasicBlock)
        do
                # Write the basic blocks hierarchy in output file
                file.write("digraph basic_blocks\n\{\n")
                var i = 0
                file.write(print_block(block, i))
                file.write("\n\}")

                file.close
        end

        # Print all the block recursively from `block` to the leaves
        # *`block` The root BasicBlock
        # *`i` Used for the recursion
        private fun print_block(block: BasicBlock, i: Int): String
        do
                # Precise the type and location of the begin and end of current block
                var s = "block{block.hash.to_s} [shape=record, label="+"\"\{"
                s += "block" + block.to_s.escape_to_dot
                s += "|\{" + block.first.location.file.filename.to_s + block.first.location.line_start.to_s
                s += " | " + block.first.to_s.escape_to_dot

                # Print phi-functions if any
                for phi in block.phi_functions do
                        s += " | " + phi.to_s.escape_to_dot + " "
                end

                s += "}|\{" + block.last.location.file.filename.to_s + block.last.location.line_start.to_s
                s += " | " + block.last.to_s.escape_to_dot + "}}\"];"+ "\n"

                i += 1
                block.treated_debug = true

                for b in block.successors do
                        # Print edges to successors
                        s += "block{block.hash.to_s} -> " + " block{b.hash.to_s};\n"

                        # Recursively print child blocks
                        if not b.treated_debug then s += print_block(b, i)
                end

                return s
        end
end

redef class AExpr
        # Generate recursively basic block for this expression
        # *`ssa` An instance of the SSA class initialized with the enclosing `APropdef`
        # *`old_block` A basic block not completely filled
        # Return the last created block (the last block can be nested)
        fun generate_basic_blocks(ssa: SSA, old_block: BasicBlock): BasicBlock
        do
                return old_block
        end
end

redef class AVarFormExpr
        # The original variable
        var original_variable: nullable Variable = variable
end

redef class AVarExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                self.variable.as(not null).read_blocks.add(old_block)
                old_block.variables.add(self.variable.as(not null))

                self.variable.as(not null).original_variable = self.variable.as(not null)
                # Save this read site in the block
                old_block.read_sites.add(self)
                old_block.variables_sites.add(self)

                return old_block
        end
end

redef class AVardeclExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                var decl = self.variable.as(not null)

                # Add the corresponding variable to the enclosing mpropdef
                ssa.propdef.variables.add(decl)

                decl.original_variable = decl
                decl.assignment_blocks.add(old_block)
                old_block.variables.add(decl)

                if self.n_expr != null then
                        self.variable.dep_exprs.add(self.n_expr.as(not null))
                        old_block = self.n_expr.generate_basic_blocks(ssa, old_block)
                end

                return old_block
        end
end

redef class AVarAssignExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                self.variable.as(not null).assignment_blocks.add(old_block)
                old_block.variables.add(self.variable.as(not null))
                self.variable.as(not null).original_variable = self.variable.as(not null)

                # Save this write site in the block
                old_block.write_sites.add(self)
                old_block.variables_sites.add(self)

                ssa.propdef.variables.add(self.variable.as(not null))

                return self.n_value.generate_basic_blocks(ssa, old_block)
        end
end

redef class AVarReassignExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                self.variable.as(not null).assignment_blocks.add(old_block)
                old_block.variables.add(self.variable.as(not null))
                self.variable.as(not null).original_variable = self.variable.as(not null)

                # Save this write site in the block
                old_block.write_sites.add(self)
                old_block.variables_sites.add(self)

                ssa.propdef.variables.add(self.variable.as(not null))
                return self.n_value.generate_basic_blocks(ssa, old_block)
        end
end

redef class ABreakExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                # Finish the old block
                old_block.last = self

                return old_block
        end
end

redef class AContinueExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                return old_block
        end
end

redef class AReturnExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                # The return just set the current block and stop the recursion
                if self.n_expr != null then
                        old_block = self.n_expr.generate_basic_blocks(ssa, old_block)

                        # Store the return expression in the dependences of the dedicated returnvar
                        ssa.propdef.returnvar.dep_exprs.add(n_expr.as(not null))
                end

                old_block.last = self

                return old_block
        end
end

redef class AAssertExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                self.n_expr.generate_basic_blocks(ssa, old_block)

                # The condition of the assert is the last expression of the previous block
                old_block.last = self.n_expr

                # The block if the assert fail
                var block_false = new BasicBlock

                if self.n_else != null then
                        block_false.first = self.n_else.as(not null)
                        block_false.last = self.n_else.as(not null)
                        self.n_else.generate_basic_blocks(ssa, block_false)
                else
                        block_false.first = self
                        block_false.last = self
                end

                old_block.link(block_false)

                # The block if the assert is true: the execution continue
                var block_true = new BasicBlock
                block_true.first = self
                block_true.last = self

                old_block.link(block_true)

                return block_true
        end
end

redef class AOrExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                self.n_expr.generate_basic_blocks(ssa, old_block)
                return self.n_expr2.generate_basic_blocks(ssa, old_block)
        end
end

redef class AImpliesExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                self.n_expr.generate_basic_blocks(ssa, old_block)
                return self.n_expr2.generate_basic_blocks(ssa, old_block)
        end
end

redef class AAndExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                self.n_expr.generate_basic_blocks(ssa, old_block)
                return self.n_expr2.generate_basic_blocks(ssa, old_block)
        end
end

redef class ANotExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                return self.n_expr.generate_basic_blocks(ssa, old_block)
        end
end

redef class AOrElseExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                self.n_expr.generate_basic_blocks(ssa, old_block)
                return self.n_expr2.generate_basic_blocks(ssa, old_block)
        end
end

redef class AArrayExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                for nexpr in self.n_exprs do
                        old_block = nexpr.generate_basic_blocks(ssa, old_block)
                end

                return old_block
        end
end

redef class ASuperstringExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                for nexpr in self.n_exprs do old_block = nexpr.generate_basic_blocks(ssa, old_block)

                return old_block
        end
end

redef class ACrangeExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                self.n_expr.generate_basic_blocks(ssa, old_block)
                return self.n_expr2.generate_basic_blocks(ssa, old_block)
        end
end

redef class AOrangeExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                self.n_expr.generate_basic_blocks(ssa, old_block)
                return self.n_expr2.generate_basic_blocks(ssa, old_block)
        end
end

redef class AIsaExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                ssa.propdef.object_sites.add(self)

                return self.n_expr.generate_basic_blocks(ssa, old_block)
        end
end

redef class AAsCastExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                ssa.propdef.object_sites.add(self)

                return self.n_expr.generate_basic_blocks(ssa, old_block)
        end
end

redef class AAsNotnullExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                return self.n_expr.generate_basic_blocks(ssa, old_block)
        end
end

redef class AParExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                return self.n_expr.generate_basic_blocks(ssa, old_block)
        end
end

redef class AOnceExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                return self.n_expr.generate_basic_blocks(ssa, old_block)
        end
end

redef class ASendExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                # A call does not finish the current block,
                # because we create intra-procedural basic blocks here

                ssa.propdef.object_sites.add(self)

                # Recursively goes into arguments to find variables if any
                for e in self.raw_arguments do e.generate_basic_blocks(ssa, old_block)

                return self.n_expr.generate_basic_blocks(ssa, old_block)
        end
end

redef class ASendReassignFormExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                self.n_expr.generate_basic_blocks(ssa, old_block)

                ssa.propdef.object_sites.add(self)

                # Recursively goes into arguments to find variables if any
                for e in self.raw_arguments do e.generate_basic_blocks(ssa, old_block)

                return self.n_value.generate_basic_blocks(ssa, old_block)
        end
end

redef class ASuperExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                # Recursively goes into arguments to find variables if any
                for arg in self.n_args.n_exprs do arg.generate_basic_blocks(ssa, old_block)

                return old_block
        end
end

redef class ANewExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                for e in self.n_args.n_exprs do e.generate_basic_blocks(ssa, old_block)

                ssa.propdef.object_sites.add(self)

                return old_block
        end
end

redef class AAttrExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                ssa.propdef.object_sites.add(self)

                return self.n_expr.generate_basic_blocks(ssa, old_block)
        end
end

redef class AAttrAssignExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                ssa.propdef.object_sites.add(self)

                return self.n_expr.generate_basic_blocks(ssa, old_block)
        end
end

redef class AAttrReassignExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                ssa.propdef.object_sites.add(self)

                return self.n_expr.generate_basic_blocks(ssa, old_block)
        end
end

redef class AIssetAttrExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                return self.n_expr.generate_basic_blocks(ssa, old_block)
        end
end

redef class ABlockExpr
        # The block needs to know if a new block is created
        redef fun generate_basic_blocks(ssa, old_block)
        do
                var last_block = old_block
                var current_block: BasicBlock

                # Recursively continue in the body of the block
                for i in [0..self.n_expr.length[ do
                        current_block = self.n_expr[i].generate_basic_blocks(ssa, last_block)

                        if current_block.need_update then
                                if i < (self.n_expr.length-1) then
                                        # Current_block must be filled
                                        current_block.first = self.n_expr[i+1]
                                        current_block.last = self.n_expr[i+1]
                                        current_block.need_update = false
                                else
                                        # Put the current block at the end of the block
                                        current_block.first = last_block.last
                                        current_block.last = last_block.last
                                end
                        end

                        if not current_block.last isa AEscapeExpr or current_block.last isa AReturnExpr then
                                # Re-affected the last block
                                current_block.last = self.n_expr[i]
                        end

                        last_block = current_block
                end

                return last_block
        end
end

redef class AIfExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                # Terminate the previous block
                old_block.last = self

                # We start two new blocks if the if has two branches
                var block_then = new BasicBlock

                # Visit the test of the if
                self.n_expr.generate_basic_blocks(ssa, old_block)

                # Launch the recursion in two successors if they exist
                if self.n_then != null then
                        old_block.link(block_then)

                        block_then.first = self.n_then.as(not null)
                        block_then.last = self.n_then.as(not null)
                        self.n_then.generate_basic_blocks(ssa, block_then)
                end

                var block_else = new BasicBlock

                if self.n_else != null then
                        old_block.link(block_else)

                        block_else.first = self.n_else.as(not null)
                        block_else.last = self.n_else.as(not null)
                        self.n_else.generate_basic_blocks(ssa, block_else)
                end

                # Create a new BasicBlock to represent the two successor
                # branches of the if
                var new_block = new BasicBlock
                new_block.first = self
                new_block.last = self

                if self.n_then != null then block_then.link(new_block)

                # The new block needs to be filled by the caller
                new_block.need_update = true

                if block_else.predecessors.length != 0 then block_else.link(new_block)

                return new_block
        end
end

redef class AIfexprExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                # Terminate the previous block
                old_block.last = self

                # We start two new blocks if the if has two branches
                var block_then = new BasicBlock

                # Visit the test of the if
                self.n_expr.generate_basic_blocks(ssa, old_block)

                # Launch the recursion in two successors if they exist
                old_block.link(block_then)

                block_then.first = self.n_then
                block_then.last = self.n_then
                self.n_then.generate_basic_blocks(ssa, block_then)

                var block_else = new BasicBlock

                old_block.link(block_else)

                block_else.first = self.n_else
                block_else.last = self.n_else
                self.n_else.generate_basic_blocks(ssa, block_else)

                # Create a new BasicBlock to represent the two successor
                # branches of the if
                var new_block = new BasicBlock
                new_block.first = self
                new_block.last = self

                block_then.link(new_block)

                # The new block needs to be filled by the caller
                new_block.need_update = true

                block_else.link(new_block)

                return new_block
        end
end

redef class ADoExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                old_block.last = self

                # The beginning of the block is the first instruction
                var block = new BasicBlock
                block.first = self.n_block.as(not null)
                block.last = self.n_block.as(not null)

                old_block.link(block)
                return self.n_block.generate_basic_blocks(ssa, block)
        end
end

redef class AWhileExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                old_block.last = self

                # The beginning of the block is the test of the while
                var block = new BasicBlock
                block.first = self.n_expr
                block.last = self.n_block.as(not null)

                old_block.link(block)

                self.n_expr.generate_basic_blocks(ssa, old_block)
                self.n_block.generate_basic_blocks(ssa, block)

                # Link the inside of the block to the previous block
                block.link_special(old_block)

                # Create a new Block after the while
                var new_block = new BasicBlock
                new_block.first = self
                new_block.last = self
                new_block.need_update = true

                old_block.link_special(new_block)

                return new_block
        end
end

redef class ALoopExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                old_block.last = self

                # The beginning of the block is the first instruction
                var block = new BasicBlock
                block.first = self.n_block.as(not null)
                block.last = self.n_block.as(not null)

                old_block.link(block)
                self.n_block.generate_basic_blocks(ssa, block)

                return block
        end
end

redef class AForExpr
        redef fun generate_basic_blocks(ssa, old_block)
        do
                old_block.last = self

                # The beginning of the block is the first instruction
                var block = new BasicBlock
                block.first = self.n_groups.first.n_expr
                block.last = self.n_block.as(not null)

                for g in n_groups do
                        # Visit the test of the if
                        g.n_expr.generate_basic_blocks(ssa, block)

                        # Collect the variables declared in the for
                        for v in g.variables do
                                ssa.propdef.variables.add(v)
                        end
                end

                old_block.link(block)

                block.link(old_block)

                var new_block = new BasicBlock
                new_block.first = self
                new_block.last = self

                new_block.need_update = true

                return new_block
        end
end