1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2015 Julien Pagès <julien.pages@lirmm.fr>
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
9 # http://www.apache.org/licenses/LICENSE-2.0
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.
17 # Single-Static Assignment algorithm from an AST
23 # Represent a sequence of the program
24 # A basic block is composed of several instructions without a jump
26 # First instruction of the basic block
27 var first
: ANode is noinit
29 # Last instruction of the basic block
30 var last
: ANode is noinit
33 var successors
= new Array[BasicBlock]
36 var predecessors
= new Array[BasicBlock]
38 # Parts of AST that contain a read to a variable
39 var read_sites
= new Array[AVarFormExpr]
41 # Parts of AST that contain a write to a variable
42 var write_sites
= new Array[AVarFormExpr]
44 # Parts of AST that contain a variable access (read or write)
45 var variables_sites
= new Array[AExpr]
47 # The iterated dominance frontier of this block
48 # i.e. the set of blocks this block dominate directly or indirectly
49 var dominance_frontier
: Array[BasicBlock] = new Array[BasicBlock] is lazy
51 # Self is the old block to link to the new,
52 # The two blocks are not linked if the current ends with a `AReturnExpr` or `ABreakExpr`
53 # i.e. self is the predecessor of `successor`
54 # `successor` The successor block
55 fun link
(successor
: BasicBlock)
57 # Do not link the two blocks if the current block end with a return, break or continue
58 if last
isa AReturnExpr or last
isa ABreakExpr or last
isa AContinueExpr then return
60 successors
.add
(successor
)
61 successor
.predecessors
.add
(self)
64 # Self is the old block to link to the new
65 # i.e. self is the predecessor of `successor`
66 # `successor` The successor block
67 fun link_special
(successor
: BasicBlock)
69 # Link the two blocks even if the current block ends with a return or a break
70 successors
.add
(successor
)
71 successor
.predecessors
.add
(self)
74 # Add the `block` to the dominance frontier of this block
75 fun add_df
(block
: BasicBlock)
77 dominance_frontier
.add
(block
)
79 # Add this block recursively in super-blocks to compute the iterated
81 for successor
in block
.successors
do
82 # If this successor has not already been add to the dominance frontier
83 if not dominance_frontier
.has
(successor
) then
89 # Compute recursively the dominance frontier of self block and its successors
90 private fun compute_df
92 # Treat each block only one time
95 for s
in successors
do
98 if not s
.df_computed
then s
.compute_df
102 # Used to handle recursions by treating only one time each block
103 var treated
: Bool = false
105 # Used to dump the BasicBlock to dot
106 var treated_debug
: Bool = false
108 # If true, the iterated dominance frontier of this block has been computed
109 var df_computed
: Bool = false
111 # Indicate the BasicBlock is newly created and needs to be updated
112 var need_update
: Bool = false
114 # Indicate if the variables renaming step has been made for this block
115 var is_renaming
: Bool = false
117 # The variables that are accessed in this block
118 var variables
= new Array[Variable] is lazy
120 # The PhiFunction this block contains at the beginning
121 var phi_functions
= new Array[PhiFunction] is lazy
124 # Contain the currently analyzed propdef
126 # The currently analyzed APropdef
127 var propdef
: APropdef
129 # The PhiFunction `current_propdef` contains
130 var phi_functions
= new Array[PhiFunction]
132 # Recursively generate the basic blocks for this propdef
133 fun generate_basic_blocks
135 propdef
.generate_basic_blocks
(self)
140 # The expressions of AST of this variable depends
141 var dep_exprs
= new Array[AExpr]
143 # The blocks in which this variable is assigned
144 var assignment_blocks
: Array[BasicBlock] = new Array[BasicBlock] is lazy
146 # Part of the program where this variable is read
147 var read_blocks
: Array[BasicBlock] = new Array[BasicBlock] is lazy
149 # The stack of this variable, used for SSA renaming
150 var stack
= new Array[Variable] is lazy
152 # The original Variable in case of renaming
153 var original_variable
: nullable Variable = self
155 # If true, this variable is a parameter of a method
156 var parameter
: Bool = false
159 # A PhiFunction is a kind of Variable used in SSA-construction,
160 # it is placed at the beginning of a BasicBlock with many incoming blocks
164 # The dependences of this variable for SSA-Algorithm
165 var dependences
= new Array[Couple[Variable, BasicBlock]]
167 # The position in the AST of the phi-function
168 var block
: BasicBlock
170 # Set the dependences for the phi-function
171 # *`block` BasicBlock in which we go through the dominance-frontier
172 # *`v` The variable to looking for
173 fun add_dependences
(block
: BasicBlock, v
: Variable)
175 # Look in which blocks of DF(block) `v` has been assigned
176 for b
in block
.predecessors
do
177 if v
.assignment_blocks
.has
(b
) then
178 var dep
= new Couple[Variable, BasicBlock](v
, b
)
184 # Print the PhiFunction with all its dependences
185 redef fun to_s
: String
188 s
+= " dependences = [ "
189 for d
in dependences
do
190 s
+= d
.first
.to_s
+ " "
199 # The variables contained in the body on this propdef
200 var variables
: HashSet[Variable] = new HashSet[Variable] is lazy
202 # The first basic block of the code
203 var basic_block
: nullable BasicBlock
205 # If true, the basic blocks where generated
206 var is_generated
: Bool = false
208 # Generate all basic blocks for this code
209 fun generate_basic_blocks
(ssa
: SSA) is abstract
211 # Contain all AST-parts related to object mechanisms the propdef has:
212 # instantiation, method dispatch, attribute access, subtyping-test
213 var object_sites
: Array[AExpr] = new Array[AExpr]
215 # The return variable of the propdef
216 # Create an empty variable for the return of the method
217 # and treat returns like variable assignments
218 var returnvar
: Variable = new Variable("returnvar")
220 # Compute the three steps of SSA-algorithm
221 # `ssa` A new instance of SSA class initialized with `self`
222 fun compute_ssa
(ssa
: SSA)
224 if is_generated
then return
226 # The first step is to generate the basic blocks
227 generate_basic_blocks
(ssa
)
229 # The propdef has no body (abstract)
230 if not is_generated
then return
232 # Once basic blocks were generated, compute SSA algorithm
234 rename_variables
(ssa
)
238 # Compute the first phase of SSA algorithm: placing phi-functions
239 fun compute_phi
(ssa
: SSA)
241 var root_block
= basic_block
.as(not null)
243 # Compute the iterated dominance frontier of the graph of basic blocks
244 root_block
.compute_df
246 # Places where a phi-function is added per variable
247 var phi_blocks
= new HashMap[Variable, Array[BasicBlock]]
249 # For each variables in the propdef
250 for v
in variables
do
251 var phi_variables
= new Array[BasicBlock]
253 var read_blocks
= new Array[BasicBlock]
254 read_blocks
.add_all
(v
.read_blocks
)
255 read_blocks
.add_all
(v
.assignment_blocks
)
257 # While we have not treated each part accessing `v`
258 while not read_blocks
.is_empty
do
259 # Remove a block from the array
260 var block
= read_blocks
.shift
262 # For each block in the dominance frontier of `block`
263 for df
in block
.dominance_frontier
do
264 # If we have not yet put a phi-function at the beginning of this block
265 if not phi_variables
.has
(df
) then
266 phi_variables
.add
(df
)
268 # Create a new phi-function and set its dependences
269 var phi
= new PhiFunction("phi", df
)
270 phi
.add_dependences
(df
, v
)
272 phi
.original_variable
= phi
273 phi
.declared_type
= v
.declared_type
275 # Indicate this phi-function is assigned in this block
276 phi
.assignment_blocks
.add
(block
)
277 ssa
.phi_functions
.add
(phi
)
279 # Add a phi-function at the beginning of df for variable v
280 df
.phi_functions
.add
(phi
)
282 if not v
.read_blocks
.has
(df
) or not v
.assignment_blocks
.has
(df
) then read_blocks
.add
(df
)
287 # Add `phi-variables` to the global map
288 phi_blocks
[v
] = phi_variables
292 # Compute the second phase of SSA algorithm: renaming variables
293 # NOTE: `compute_phi` must has been called before
294 fun rename_variables
(ssa
: SSA)
296 # A counter for each variable
297 # The key is the variable, the value the number of assignment into the variable
298 var counter
= new HashMap[Variable, Int]
300 for v
in variables
do
305 for phi
in ssa
.phi_functions
do counter
[phi
] = 0
307 # Launch the recursive renaming from the root block
308 rename
(basic_block
.as(not null), counter
, ssa
)
311 # Recursively rename each variable from `block`
312 # *`block` The starting basic block
313 # *`counter` The key is the variable, the value the number of assignment into the variable
314 fun rename
(block
: BasicBlock, counter
: HashMap[Variable, Int], ssa
: SSA)
316 if block
.is_renaming
then return
318 block
.is_renaming
= true
320 # For each phi-function of this block
321 for phi
in block
.phi_functions
do
322 generate_name
(phi
, counter
, block
.first
, ssa
)
324 # Replace the phi into the block
325 block
.phi_functions
[block
.phi_functions
.index_of
(phi
)] = phi
.original_variable
.stack
.last
.as(PhiFunction)
328 # For each variable read in `block`
329 for vread
in block
.read_sites
do
330 # Replace the old variable in AST
331 vread
.variable
= vread
.variable
.original_variable
.stack
.last
334 # For each variable write
335 for vwrite
in block
.write_sites
do
336 generate_name
(vwrite
.variable
.as(not null), counter
, vwrite
, ssa
)
338 var new_version
= vwrite
.variable
.original_variable
.stack
.last
340 # Set dependence of the new variable
341 if vwrite
isa AVarReassignExpr then
342 new_version
.dep_exprs
.add
(vwrite
.n_value
)
343 else if vwrite
isa AVarAssignExpr then
344 new_version
.dep_exprs
.add
(vwrite
.n_value
)
347 # Replace the old variable by the last created
348 vwrite
.variable
= new_version
351 # Rename occurrence of old names in phi-function
352 for successor
in block
.dominance_frontier
do
353 for sphi
in successor
.phi_functions
do
354 # Go over the couples in the phi dependences to rename variables
355 for couple
in sphi
.dependences
do
356 if couple
.second
== block
then
357 # Rename this variable
358 couple
.first
= couple
.first
.original_variable
.stack
.last
364 # Recurse in successor blocks
365 for successor
in block
.successors
do
366 rename
(successor
, counter
, ssa
)
369 # Pop old names off the stack for each phi-function
370 for phi
in block
.phi_functions
do
371 if not phi
.stack
.is_empty
then phi
.stack
.pop
375 # Generate a new version of the variable `v` and return it
376 # *`v` The variable for which we generate a name
377 # *`counter` The key is the variable, the value the number of assignment into the variable
378 # *`expr` The AST node in which the assignment of v is made
379 # *`ssa` The instance of SSA
380 fun generate_name
(v
: Variable, counter
: HashMap[Variable, Int], expr
: ANode, ssa
: SSA): Variable
382 var original_variable
= v
.original_variable
.as(not null)
384 var i
= counter
[original_variable
]
386 var new_version
: Variable
388 # Create a new version of Variable
389 if original_variable
isa PhiFunction then
390 var block
= original_variable
.block
391 new_version
= new PhiFunction(original_variable
.name
+ i
.to_s
, block
)
392 new_version
.dependences
.add_all
(original_variable
.dependences
)
393 ssa
.phi_functions
.add
(new_version
)
395 new_version
= new Variable(original_variable
.name
+ i
.to_s
)
396 new_version
.declared_type
= expr
.as(AVarFormExpr).variable
.declared_type
397 variables
.add
(new_version
)
400 # Recopy the fields into the new version
401 new_version
.location
= expr
.location
402 new_version
.original_variable
= original_variable
404 # Push a new version on the stack
405 original_variable
.stack
.add
(new_version
)
411 # Transform SSA-representation into an executable code (delete phi-functions)
412 # `ssa` Current instance of SSA
413 fun ssa_destruction
(ssa
: SSA)
415 var builder
= new ASTBuilder(mpropdef
.mclassdef
.mmodule
, mpropdef
.mclassdef
.bound_mtype
)
417 # Iterate over all phi-functions
418 for phi
in ssa
.phi_functions
do
419 for dep
in phi
.dependences
do
420 # dep.second is the block where we need to create a varassign
421 var var_read
= builder
.make_var_read
(dep
.first
, dep
.first
.declared_type
.as(not null))
422 var nvar
= builder
.make_var_assign
(dep
.first
, var_read
)
424 var block
= dep
.second
.last
.parent
426 # This variable read must be add to a ABlockExpr
427 if block
isa ABlockExpr then
431 propagate_dependences
(phi
, phi
.block
)
432 ssa
.propdef
.variables
.add
(dep
.first
)
437 # Propagate the dependences of the phi-functions into following variables
438 # `phi` The PhiFunction
439 # `block` Current block where we propagate dependences
440 fun propagate_dependences
(phi
: PhiFunction, block
: BasicBlock)
442 # Treat each block once
443 if block
.treated
then return
445 # For each variable access site in the block
446 for site
in block
.variables_sites
do
447 if site
isa AVarExpr then
448 # Propagate the dependences of the phi-function in variables after the phi
449 for dep
in phi
.dependences
do
450 for expr
in dep
.first
.dep_exprs
do
451 if site
.variable
.dep_exprs
.has
(expr
) then break
453 if dep
.first
.original_variable
== site
.variable
.original_variable
then
454 site
.variable
.dep_exprs
.add
(expr
)
459 # The site is a variable write, we stop the propagation
466 # If we do not meet a variable write, continue the propagation
467 for b
in block
.successors
do propagate_dependences
(phi
, b
)
471 redef class AAttrPropdef
472 redef fun generate_basic_blocks
(ssa
: SSA)
474 basic_block
= new BasicBlock
475 basic_block
.first
= self
476 basic_block
.last
= self
478 # Add the return variable
479 variables
.add
(returnvar
)
481 # Add the self variable
482 if self.selfvariable
!= null then variables
.add
(selfvariable
.as(not null))
484 # Recursively goes into the nodes
485 if n_block
!= null then
486 n_block
.generate_basic_blocks
(ssa
, basic_block
.as(not null))
492 redef class AMethPropdef
493 redef fun generate_basic_blocks
(ssa
: SSA)
495 basic_block
= new BasicBlock
496 basic_block
.first
= self
497 basic_block
.last
= self
499 # If the method has a signature
500 if n_signature
!= null then
501 for p
in n_signature
.n_params
do
502 # Add parameters to the local variables
503 variables
.add
(p
.variable
.as(not null))
504 p
.variable
.parameter
= true
508 # Add the return variable
509 variables
.add
(returnvar
)
511 # Add the self variable
512 if self.selfvariable
!= null then variables
.add
(selfvariable
.as(not null))
514 # Recursively goes into the nodes
515 if n_block
!= null then
516 n_block
.generate_basic_blocks
(ssa
, basic_block
.as(not null))
522 # Utility class for dump basic block and SSA output to dot files
527 # Dump all the hierarchy of BasicBlock from `block` to the leaves
528 fun dump
(block
: BasicBlock)
530 # Write the basic blocks hierarchy in output file
531 file
.write
("digraph basic_blocks\n\{\n")
533 file
.write
(print_block
(block
, i
))
539 # Print all the block recursively from `block` to the leaves
540 # *`block` The root BasicBlock
541 # *`i` Used for the recursion
542 private fun print_block
(block
: BasicBlock, i
: Int): String
544 # Precise the type and location of the begin and end of current block
545 var s
= "block{block.hash.to_s} [shape=record, label="+"\"\
{"
546 s += "block
" + block.to_s.escape_to_dot
547 s += "|\
{" + block.first.location.file.filename.to_s + block.first.location.line_start.to_s
548 s += " | " + block.first.to_s.escape_to_dot
550 # Print phi-functions if any
551 for phi in block.phi_functions do
552 s += " | " + phi.to_s.escape_to_dot + " "
555 s += "}|\
{" + block.last.location.file.filename.to_s + block.last.location.line_start.to_s
556 s += " | " + block.last.to_s.escape_to_dot + "}}\
"];"+ "\n"
559 block
.treated_debug
= true
561 for b
in block
.successors
do
562 # Print edges to successors
563 s
+= "block{block.hash.to_s} -> " + " block{b.hash.to_s};\n"
565 # Recursively print child blocks
566 if not b
.treated_debug
then s
+= print_block
(b
, i
)
574 # Generate recursively basic block for this expression
575 # *`ssa` An instance of the SSA class initialized with the enclosing `APropdef`
576 # *`old_block` A basic block not completely filled
577 # Return the last created block (the last block can be nested)
578 fun generate_basic_blocks
(ssa
: SSA, old_block
: BasicBlock): BasicBlock
584 redef class AVarFormExpr
585 # The original variable
586 var original_variable
: nullable Variable = variable
590 redef fun generate_basic_blocks
(ssa
, old_block
)
592 self.variable
.as(not null).read_blocks
.add
(old_block
)
593 old_block
.variables
.add
(self.variable
.as(not null))
595 self.variable
.as(not null).original_variable
= self.variable
.as(not null)
596 # Save this read site in the block
597 old_block
.read_sites
.add
(self)
598 old_block
.variables_sites
.add
(self)
604 redef class AVardeclExpr
605 redef fun generate_basic_blocks
(ssa
, old_block
)
607 var decl
= self.variable
.as(not null)
609 # Add the corresponding variable to the enclosing mpropdef
610 ssa
.propdef
.variables
.add
(decl
)
612 decl
.original_variable
= decl
613 decl
.assignment_blocks
.add
(old_block
)
614 old_block
.variables
.add
(decl
)
616 if self.n_expr
!= null then
617 self.variable
.dep_exprs
.add
(self.n_expr
.as(not null))
618 old_block
= self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
625 redef class AVarAssignExpr
626 redef fun generate_basic_blocks
(ssa
, old_block
)
628 self.variable
.as(not null).assignment_blocks
.add
(old_block
)
629 old_block
.variables
.add
(self.variable
.as(not null))
630 self.variable
.as(not null).original_variable
= self.variable
.as(not null)
632 # Save this write site in the block
633 old_block
.write_sites
.add
(self)
634 old_block
.variables_sites
.add
(self)
636 ssa
.propdef
.variables
.add
(self.variable
.as(not null))
638 return self.n_value
.generate_basic_blocks
(ssa
, old_block
)
642 redef class AVarReassignExpr
643 redef fun generate_basic_blocks
(ssa
, old_block
)
645 self.variable
.as(not null).assignment_blocks
.add
(old_block
)
646 old_block
.variables
.add
(self.variable
.as(not null))
647 self.variable
.as(not null).original_variable
= self.variable
.as(not null)
649 # Save this write site in the block
650 old_block
.write_sites
.add
(self)
651 old_block
.variables_sites
.add
(self)
653 ssa
.propdef
.variables
.add
(self.variable
.as(not null))
654 return self.n_value
.generate_basic_blocks
(ssa
, old_block
)
658 redef class ABreakExpr
659 redef fun generate_basic_blocks
(ssa
, old_block
)
661 # Finish the old block
662 old_block
.last
= self
668 redef class AContinueExpr
669 redef fun generate_basic_blocks
(ssa
, old_block
)
675 redef class AReturnExpr
676 redef fun generate_basic_blocks
(ssa
, old_block
)
678 # The return just set the current block and stop the recursion
679 if self.n_expr
!= null then
680 old_block
= self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
682 # Store the return expression in the dependences of the dedicated returnvar
683 ssa
.propdef
.returnvar
.dep_exprs
.add
(n_expr
.as(not null))
686 old_block
.last
= self
692 redef class AAssertExpr
693 redef fun generate_basic_blocks
(ssa
, old_block
)
695 self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
697 # The condition of the assert is the last expression of the previous block
698 old_block
.last
= self.n_expr
700 # The block if the assert fail
701 var block_false
= new BasicBlock
703 if self.n_else
!= null then
704 block_false
.first
= self.n_else
.as(not null)
705 block_false
.last
= self.n_else
.as(not null)
706 self.n_else
.generate_basic_blocks
(ssa
, block_false
)
708 block_false
.first
= self
709 block_false
.last
= self
712 old_block
.link
(block_false
)
714 # The block if the assert is true: the execution continue
715 var block_true
= new BasicBlock
716 block_true
.first
= self
717 block_true
.last
= self
719 old_block
.link
(block_true
)
726 redef fun generate_basic_blocks
(ssa
, old_block
)
728 self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
729 return self.n_expr2
.generate_basic_blocks
(ssa
, old_block
)
733 redef class AImpliesExpr
734 redef fun generate_basic_blocks
(ssa
, old_block
)
736 self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
737 return self.n_expr2
.generate_basic_blocks
(ssa
, old_block
)
742 redef fun generate_basic_blocks
(ssa
, old_block
)
744 self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
745 return self.n_expr2
.generate_basic_blocks
(ssa
, old_block
)
750 redef fun generate_basic_blocks
(ssa
, old_block
)
752 return self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
756 redef class AOrElseExpr
757 redef fun generate_basic_blocks
(ssa
, old_block
)
759 self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
760 return self.n_expr2
.generate_basic_blocks
(ssa
, old_block
)
764 redef class AArrayExpr
765 redef fun generate_basic_blocks
(ssa
, old_block
)
767 for nexpr
in self.n_exprs
do
768 old_block
= nexpr
.generate_basic_blocks
(ssa
, old_block
)
775 redef class ASuperstringExpr
776 redef fun generate_basic_blocks
(ssa
, old_block
)
778 for nexpr
in self.n_exprs
do old_block
= nexpr
.generate_basic_blocks
(ssa
, old_block
)
784 redef class ACrangeExpr
785 redef fun generate_basic_blocks
(ssa
, old_block
)
787 self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
788 return self.n_expr2
.generate_basic_blocks
(ssa
, old_block
)
792 redef class AOrangeExpr
793 redef fun generate_basic_blocks
(ssa
, old_block
)
795 self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
796 return self.n_expr2
.generate_basic_blocks
(ssa
, old_block
)
801 redef fun generate_basic_blocks
(ssa
, old_block
)
803 ssa
.propdef
.object_sites
.add
(self)
805 return self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
809 redef class AAsCastExpr
810 redef fun generate_basic_blocks
(ssa
, old_block
)
812 ssa
.propdef
.object_sites
.add
(self)
814 return self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
818 redef class AAsNotnullExpr
819 redef fun generate_basic_blocks
(ssa
, old_block
)
821 return self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
826 redef fun generate_basic_blocks
(ssa
, old_block
)
828 return self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
832 redef class AOnceExpr
833 redef fun generate_basic_blocks
(ssa
, old_block
)
835 return self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
839 redef class ASendExpr
840 redef fun generate_basic_blocks
(ssa
, old_block
)
842 # A call does not finish the current block,
843 # because we create intra-procedural basic blocks here
845 ssa
.propdef
.object_sites
.add
(self)
847 # Recursively goes into arguments to find variables if any
848 for e
in self.raw_arguments
do e
.generate_basic_blocks
(ssa
, old_block
)
850 return self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
854 redef class ASendReassignFormExpr
855 redef fun generate_basic_blocks
(ssa
, old_block
)
857 self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
859 ssa
.propdef
.object_sites
.add
(self)
861 # Recursively goes into arguments to find variables if any
862 for e
in self.raw_arguments
do e
.generate_basic_blocks
(ssa
, old_block
)
864 return self.n_value
.generate_basic_blocks
(ssa
, old_block
)
868 redef class ASuperExpr
869 redef fun generate_basic_blocks
(ssa
, old_block
)
871 # Recursively goes into arguments to find variables if any
872 for arg
in self.n_args
.n_exprs
do arg
.generate_basic_blocks
(ssa
, old_block
)
879 redef fun generate_basic_blocks
(ssa
, old_block
)
881 for e
in self.n_args
.n_exprs
do e
.generate_basic_blocks
(ssa
, old_block
)
883 ssa
.propdef
.object_sites
.add
(self)
889 redef class AAttrExpr
890 redef fun generate_basic_blocks
(ssa
, old_block
)
892 ssa
.propdef
.object_sites
.add
(self)
894 return self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
898 redef class AAttrAssignExpr
899 redef fun generate_basic_blocks
(ssa
, old_block
)
901 ssa
.propdef
.object_sites
.add
(self)
903 return self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
907 redef class AAttrReassignExpr
908 redef fun generate_basic_blocks
(ssa
, old_block
)
910 ssa
.propdef
.object_sites
.add
(self)
912 return self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
916 redef class AIssetAttrExpr
917 redef fun generate_basic_blocks
(ssa
, old_block
)
919 return self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
923 redef class ABlockExpr
924 # The block needs to know if a new block is created
925 redef fun generate_basic_blocks
(ssa
, old_block
)
927 var last_block
= old_block
928 var current_block
: BasicBlock
930 # Recursively continue in the body of the block
931 for i
in [0..self.n_expr
.length
[ do
932 current_block
= self.n_expr
[i
].generate_basic_blocks
(ssa
, last_block
)
934 if current_block
.need_update
then
935 if i
< (self.n_expr
.length-1
) then
936 # Current_block must be filled
937 current_block
.first
= self.n_expr
[i
+1]
938 current_block
.last
= self.n_expr
[i
+1]
939 current_block
.need_update
= false
941 # Put the current block at the end of the block
942 current_block
.first
= last_block
.last
943 current_block
.last
= last_block
.last
947 if not current_block
.last
isa AEscapeExpr or current_block
.last
isa AReturnExpr then
948 # Re-affected the last block
949 current_block
.last
= self.n_expr
[i
]
952 last_block
= current_block
960 redef fun generate_basic_blocks
(ssa
, old_block
)
962 # Terminate the previous block
963 old_block
.last
= self
965 # We start two new blocks if the if has two branches
966 var block_then
= new BasicBlock
968 # Visit the test of the if
969 self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
971 # Launch the recursion in two successors if they exist
972 if self.n_then
!= null then
973 old_block
.link
(block_then
)
975 block_then
.first
= self.n_then
.as(not null)
976 block_then
.last
= self.n_then
.as(not null)
977 self.n_then
.generate_basic_blocks
(ssa
, block_then
)
980 var block_else
= new BasicBlock
982 if self.n_else
!= null then
983 old_block
.link
(block_else
)
985 block_else
.first
= self.n_else
.as(not null)
986 block_else
.last
= self.n_else
.as(not null)
987 self.n_else
.generate_basic_blocks
(ssa
, block_else
)
990 # Create a new BasicBlock to represent the two successor
992 var new_block
= new BasicBlock
993 new_block
.first
= self
994 new_block
.last
= self
996 if self.n_then
!= null then block_then
.link
(new_block
)
998 # The new block needs to be filled by the caller
999 new_block
.need_update
= true
1001 if block_else
.predecessors
.length
!= 0 then block_else
.link
(new_block
)
1007 redef class AIfexprExpr
1008 redef fun generate_basic_blocks
(ssa
, old_block
)
1010 # Terminate the previous block
1011 old_block
.last
= self
1013 # We start two new blocks if the if has two branches
1014 var block_then
= new BasicBlock
1016 # Visit the test of the if
1017 self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
1019 # Launch the recursion in two successors if they exist
1020 old_block
.link
(block_then
)
1022 block_then
.first
= self.n_then
1023 block_then
.last
= self.n_then
1024 self.n_then
.generate_basic_blocks
(ssa
, block_then
)
1026 var block_else
= new BasicBlock
1028 old_block
.link
(block_else
)
1030 block_else
.first
= self.n_else
1031 block_else
.last
= self.n_else
1032 self.n_else
.generate_basic_blocks
(ssa
, block_else
)
1034 # Create a new BasicBlock to represent the two successor
1035 # branches of the if
1036 var new_block
= new BasicBlock
1037 new_block
.first
= self
1038 new_block
.last
= self
1040 block_then
.link
(new_block
)
1042 # The new block needs to be filled by the caller
1043 new_block
.need_update
= true
1045 block_else
.link
(new_block
)
1052 redef fun generate_basic_blocks
(ssa
, old_block
)
1054 old_block
.last
= self
1056 # The beginning of the block is the first instruction
1057 var block
= new BasicBlock
1058 block
.first
= self.n_block
.as(not null)
1059 block
.last
= self.n_block
.as(not null)
1061 old_block
.link
(block
)
1062 return self.n_block
.generate_basic_blocks
(ssa
, block
)
1066 redef class AWhileExpr
1067 redef fun generate_basic_blocks
(ssa
, old_block
)
1069 old_block
.last
= self
1071 # The beginning of the block is the test of the while
1072 var block
= new BasicBlock
1073 block
.first
= self.n_expr
1074 block
.last
= self.n_block
.as(not null)
1076 old_block
.link
(block
)
1078 self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
1079 self.n_block
.generate_basic_blocks
(ssa
, block
)
1081 # Link the inside of the block to the previous block
1082 block
.link_special
(old_block
)
1084 # Create a new Block after the while
1085 var new_block
= new BasicBlock
1086 new_block
.first
= self
1087 new_block
.last
= self
1088 new_block
.need_update
= true
1090 old_block
.link_special
(new_block
)
1096 redef class ALoopExpr
1097 redef fun generate_basic_blocks
(ssa
, old_block
)
1099 old_block
.last
= self
1101 # The beginning of the block is the first instruction
1102 var block
= new BasicBlock
1103 block
.first
= self.n_block
.as(not null)
1104 block
.last
= self.n_block
.as(not null)
1106 old_block
.link
(block
)
1107 self.n_block
.generate_basic_blocks
(ssa
, block
)
1113 redef class AForExpr
1114 redef fun generate_basic_blocks
(ssa
, old_block
)
1116 old_block
.last
= self
1118 # The beginning of the block is the first instruction
1119 var block
= new BasicBlock
1120 block
.first
= self.n_groups
.first
.n_expr
1121 block
.last
= self.n_block
.as(not null)
1123 for g
in n_groups
do
1124 # Visit the test of the if
1125 g
.n_expr
.generate_basic_blocks
(ssa
, block
)
1127 # Collect the variables declared in the for
1128 for v
in g
.variables
do
1129 ssa
.propdef
.variables
.add
(v
)
1133 old_block
.link
(block
)
1135 block
.link
(old_block
)
1137 var new_block
= new BasicBlock
1138 new_block
.first
= self
1139 new_block
.last
= self
1141 new_block
.need_update
= true