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 # Compute the three steps of SSA-algorithm
216 # `ssa` A new instance of SSA class initialized with `self`
217 fun compute_ssa
(ssa
: SSA)
219 if is_generated
then return
221 # The first step is to generate the basic blocks
222 generate_basic_blocks
(ssa
)
224 # The propdef has no body (abstract)
225 if not is_generated
then return
227 # Once basic blocks were generated, compute SSA algorithm
229 rename_variables
(ssa
)
233 # Compute the first phase of SSA algorithm: placing phi-functions
234 fun compute_phi
(ssa
: SSA)
236 var root_block
= basic_block
.as(not null)
238 # Compute the iterated dominance frontier of the graph of basic blocks
239 root_block
.compute_df
241 # Places where a phi-function is added per variable
242 var phi_blocks
= new HashMap[Variable, Array[BasicBlock]]
244 # For each variables in the propdef
245 for v
in variables
do
246 var phi_variables
= new Array[BasicBlock]
248 var read_blocks
= new Array[BasicBlock]
249 read_blocks
.add_all
(v
.read_blocks
)
250 read_blocks
.add_all
(v
.assignment_blocks
)
252 # While we have not treated each part accessing `v`
253 while not read_blocks
.is_empty
do
254 # Remove a block from the array
255 var block
= read_blocks
.shift
257 # For each block in the dominance frontier of `block`
258 for df
in block
.dominance_frontier
do
259 # If we have not yet put a phi-function at the beginning of this block
260 if not phi_variables
.has
(df
) then
261 phi_variables
.add
(df
)
263 # Create a new phi-function and set its dependences
264 var phi
= new PhiFunction("phi", df
)
265 phi
.add_dependences
(df
, v
)
267 phi
.original_variable
= phi
268 phi
.declared_type
= v
.declared_type
270 # Indicate this phi-function is assigned in this block
271 phi
.assignment_blocks
.add
(block
)
272 ssa
.phi_functions
.add
(phi
)
274 # Add a phi-function at the beginning of df for variable v
275 df
.phi_functions
.add
(phi
)
277 if not v
.read_blocks
.has
(df
) or not v
.assignment_blocks
.has
(df
) then read_blocks
.add
(df
)
282 # Add `phi-variables` to the global map
283 phi_blocks
[v
] = phi_variables
287 # Compute the second phase of SSA algorithm: renaming variables
288 # NOTE: `compute_phi` must has been called before
289 fun rename_variables
(ssa
: SSA)
291 # A counter for each variable
292 # The key is the variable, the value the number of assignment into the variable
293 var counter
= new HashMap[Variable, Int]
295 for v
in variables
do
300 for phi
in ssa
.phi_functions
do counter
[phi
] = 0
302 # Launch the recursive renaming from the root block
303 rename
(basic_block
.as(not null), counter
, ssa
)
306 # Recursively rename each variable from `block`
307 # *`block` The starting basic block
308 # *`counter` The key is the variable, the value the number of assignment into the variable
309 fun rename
(block
: BasicBlock, counter
: HashMap[Variable, Int], ssa
: SSA)
311 if block
.is_renaming
then return
313 block
.is_renaming
= true
315 # For each phi-function of this block
316 for phi
in block
.phi_functions
do
317 generate_name
(phi
, counter
, block
.first
, ssa
)
319 # Replace the phi into the block
320 block
.phi_functions
[block
.phi_functions
.index_of
(phi
)] = phi
.original_variable
.stack
.last
.as(PhiFunction)
323 # For each variable read in `block`
324 for vread
in block
.read_sites
do
325 # Replace the old variable in AST
326 vread
.variable
= vread
.variable
.original_variable
.stack
.last
329 # For each variable write
330 for vwrite
in block
.write_sites
do
331 generate_name
(vwrite
.variable
.as(not null), counter
, vwrite
, ssa
)
333 var new_version
= vwrite
.variable
.original_variable
.stack
.last
335 # Set dependence of the new variable
336 if vwrite
isa AVarReassignExpr then
337 new_version
.dep_exprs
.add
(vwrite
.n_value
)
338 else if vwrite
isa AVarAssignExpr then
339 new_version
.dep_exprs
.add
(vwrite
.n_value
)
342 # Replace the old variable by the last created
343 vwrite
.variable
= new_version
346 # Rename occurrence of old names in phi-function
347 for successor
in block
.dominance_frontier
do
348 for sphi
in successor
.phi_functions
do
349 # Go over the couples in the phi dependences to rename variables
350 for couple
in sphi
.dependences
do
351 if couple
.second
== block
then
352 # Rename this variable
353 couple
.first
= couple
.first
.original_variable
.stack
.last
359 # Recurse in successor blocks
360 for successor
in block
.successors
do
361 rename
(successor
, counter
, ssa
)
364 # Pop old names off the stack for each phi-function
365 for phi
in block
.phi_functions
do
366 if not phi
.stack
.is_empty
then phi
.stack
.pop
370 # Generate a new version of the variable `v` and return it
371 # *`v` The variable for which we generate a name
372 # *`counter` The key is the variable, the value the number of assignment into the variable
373 # *`expr` The AST node in which the assignment of v is made
374 # *`ssa` The instance of SSA
375 fun generate_name
(v
: Variable, counter
: HashMap[Variable, Int], expr
: ANode, ssa
: SSA): Variable
377 var original_variable
= v
.original_variable
.as(not null)
379 var i
= counter
[original_variable
]
381 var new_version
: Variable
383 # Create a new version of Variable
384 if original_variable
isa PhiFunction then
385 var block
= original_variable
.block
386 new_version
= new PhiFunction(original_variable
.name
+ i
.to_s
, block
)
387 new_version
.dependences
.add_all
(original_variable
.dependences
)
388 ssa
.phi_functions
.add
(new_version
)
390 new_version
= new Variable(original_variable
.name
+ i
.to_s
)
391 new_version
.declared_type
= expr
.as(AVarFormExpr).variable
.declared_type
392 variables
.add
(new_version
)
395 # Recopy the fields into the new version
396 new_version
.location
= expr
.location
397 new_version
.original_variable
= original_variable
399 # Push a new version on the stack
400 original_variable
.stack
.add
(new_version
)
406 # Transform SSA-representation into an executable code (delete phi-functions)
407 # `ssa` Current instance of SSA
408 fun ssa_destruction
(ssa
: SSA)
410 var builder
= new ASTBuilder(mpropdef
.mclassdef
.mmodule
, mpropdef
.mclassdef
.bound_mtype
)
412 # Iterate over all phi-functions
413 for phi
in ssa
.phi_functions
do
414 for dep
in phi
.dependences
do
415 # dep.second is the block where we need to create a varassign
416 var var_read
= builder
.make_var_read
(dep
.first
, dep
.first
.declared_type
.as(not null))
417 var nvar
= builder
.make_var_assign
(dep
.first
, var_read
)
419 var block
= dep
.second
.last
.parent
421 # This variable read must be add to a ABlockExpr
422 if block
isa ABlockExpr then
426 propagate_dependences
(phi
, phi
.block
)
427 ssa
.propdef
.variables
.add
(dep
.first
)
432 # Propagate the dependences of the phi-functions into following variables
433 # `phi` The PhiFunction
434 # `block` Current block where we propagate dependences
435 fun propagate_dependences
(phi
: PhiFunction, block
: BasicBlock)
437 # Treat each block once
438 if block
.treated
then return
440 # For each variable access site in the block
441 for site
in block
.variables_sites
do
442 if site
isa AVarExpr then
443 # Propagate the dependences of the phi-function in variables after the phi
444 for dep
in phi
.dependences
do
445 for expr
in dep
.first
.dep_exprs
do
446 if site
.variable
.dep_exprs
.has
(expr
) then break
448 if dep
.first
.original_variable
== site
.variable
.original_variable
then
449 site
.variable
.dep_exprs
.add
(expr
)
454 # The site is a variable write, we stop the propagation
461 # If we do not meet a variable write, continue the propagation
462 for b
in block
.successors
do propagate_dependences
(phi
, b
)
466 redef class AAttrPropdef
467 redef fun generate_basic_blocks
(ssa
: SSA)
469 basic_block
= new BasicBlock
470 basic_block
.first
= self
471 basic_block
.last
= self
473 # Add the self variable
474 if self.selfvariable
!= null then variables
.add
(selfvariable
.as(not null))
476 # Recursively goes into the nodes
477 if n_block
!= null then
478 n_block
.generate_basic_blocks
(ssa
, basic_block
.as(not null))
484 redef class AMethPropdef
486 # The return variable of the propdef
487 # Create an empty variable for the return of the method
488 # and treat returns like variable assignments
489 var returnvar
: Variable = new Variable("returnvar")
491 redef fun generate_basic_blocks
(ssa
: SSA)
493 basic_block
= new BasicBlock
494 basic_block
.first
= self
495 basic_block
.last
= self
497 # If the method has a signature
498 if n_signature
!= null then
499 for p
in n_signature
.n_params
do
500 # Add parameters to the local variables
501 variables
.add
(p
.variable
.as(not null))
502 p
.variable
.parameter
= true
506 # Add the return variable
507 variables
.add
(returnvar
)
509 # Add the self variable
510 if self.selfvariable
!= null then variables
.add
(selfvariable
.as(not null))
512 # Recursively goes into the nodes
513 if n_block
!= null then
514 n_block
.generate_basic_blocks
(ssa
, basic_block
.as(not null))
520 # Utility class for dump basic block and SSA output to dot files
525 # Dump all the hierarchy of BasicBlock from `block` to the leaves
526 fun dump
(block
: BasicBlock)
528 # Write the basic blocks hierarchy in output file
529 file
.write
("digraph basic_blocks\n\{\n")
531 file
.write
(print_block
(block
, i
))
537 # Print all the block recursively from `block` to the leaves
538 # *`block` The root BasicBlock
539 # *`i` Used for the recursion
540 private fun print_block
(block
: BasicBlock, i
: Int): String
542 # Precise the type and location of the begin and end of current block
543 var s
= "block{block.hash.to_s} [shape=record, label="+"\"\
{"
544 s += "block
" + block.to_s.escape_to_dot
545 s += "|\
{" + block.first.location.file.filename.to_s + block.first.location.line_start.to_s
546 s += " | " + block.first.to_s.escape_to_dot
548 # Print phi-functions if any
549 for phi in block.phi_functions do
550 s += " | " + phi.to_s.escape_to_dot + " "
553 s += "}|\
{" + block.last.location.file.filename.to_s + block.last.location.line_start.to_s
554 s += " | " + block.last.to_s.escape_to_dot + "}}\
"];"+ "\n"
557 block
.treated_debug
= true
559 for b
in block
.successors
do
560 # Print edges to successors
561 s
+= "block{block.hash.to_s} -> " + " block{b.hash.to_s};\n"
563 # Recursively print child blocks
564 if not b
.treated_debug
then s
+= print_block
(b
, i
)
572 # Generate recursively basic block for this expression
573 # *`ssa` An instance of the SSA class initialized with the enclosing `APropdef`
574 # *`old_block` A basic block not completely filled
575 # Return the last created block (the last block can be nested)
576 fun generate_basic_blocks
(ssa
: SSA, old_block
: BasicBlock): BasicBlock
582 redef class AVarFormExpr
583 # The original variable
584 var original_variable
: nullable Variable = variable
588 redef fun generate_basic_blocks
(ssa
, old_block
)
590 self.variable
.as(not null).read_blocks
.add
(old_block
)
591 old_block
.variables
.add
(self.variable
.as(not null))
593 self.variable
.as(not null).original_variable
= self.variable
.as(not null)
594 # Save this read site in the block
595 old_block
.read_sites
.add
(self)
596 old_block
.variables_sites
.add
(self)
602 redef class AVardeclExpr
603 redef fun generate_basic_blocks
(ssa
, old_block
)
605 var decl
= self.variable
.as(not null)
607 # Add the corresponding variable to the enclosing mpropdef
608 ssa
.propdef
.variables
.add
(decl
)
610 decl
.original_variable
= decl
611 decl
.assignment_blocks
.add
(old_block
)
612 old_block
.variables
.add
(decl
)
614 if self.n_expr
!= null then
615 self.variable
.dep_exprs
.add
(self.n_expr
.as(not null))
616 old_block
= self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
623 redef class AVarAssignExpr
624 redef fun generate_basic_blocks
(ssa
, old_block
)
626 self.variable
.as(not null).assignment_blocks
.add
(old_block
)
627 old_block
.variables
.add
(self.variable
.as(not null))
628 self.variable
.as(not null).original_variable
= self.variable
.as(not null)
630 # Save this write site in the block
631 old_block
.write_sites
.add
(self)
632 old_block
.variables_sites
.add
(self)
634 ssa
.propdef
.variables
.add
(self.variable
.as(not null))
636 return self.n_value
.generate_basic_blocks
(ssa
, old_block
)
640 redef class AVarReassignExpr
641 redef fun generate_basic_blocks
(ssa
, old_block
)
643 self.variable
.as(not null).assignment_blocks
.add
(old_block
)
644 old_block
.variables
.add
(self.variable
.as(not null))
645 self.variable
.as(not null).original_variable
= self.variable
.as(not null)
647 # Save this write site in the block
648 old_block
.write_sites
.add
(self)
649 old_block
.variables_sites
.add
(self)
651 ssa
.propdef
.variables
.add
(self.variable
.as(not null))
652 return self.n_value
.generate_basic_blocks
(ssa
, old_block
)
656 redef class ABreakExpr
657 redef fun generate_basic_blocks
(ssa
, old_block
)
659 # Finish the old block
660 old_block
.last
= self
666 redef class AContinueExpr
667 redef fun generate_basic_blocks
(ssa
, old_block
)
673 redef class AReturnExpr
674 redef fun generate_basic_blocks
(ssa
, old_block
)
676 # The return just set the current block and stop the recursion
677 if self.n_expr
!= null then
678 old_block
= self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
680 # Store the return expression in the dependences of the dedicated returnvar
681 if ssa
.propdef
isa AMethPropdef then
682 ssa
.propdef
.as(AMethPropdef).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
.first
= 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 var inside_block
= 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
.need_update
= true
1088 old_block
.link_special
(new_block
)
1094 redef class ALoopExpr
1095 redef fun generate_basic_blocks
(ssa
, old_block
)
1097 old_block
.last
= self
1099 # The beginning of the block is the first instruction
1100 var block
= new BasicBlock
1101 block
.first
= self.n_block
.as(not null)
1102 block
.last
= self.n_block
.as(not null)
1104 old_block
.link
(block
)
1105 self.n_block
.generate_basic_blocks
(ssa
, block
)
1111 redef class AForExpr
1112 redef fun generate_basic_blocks
(ssa
, old_block
)
1114 old_block
.last
= self
1116 # The beginning of the block is the first instruction
1117 var block
= new BasicBlock
1118 block
.first
= self.n_expr
1119 block
.last
= self.n_block
.as(not null)
1121 # Visit the test of the if
1122 self.n_expr
.generate_basic_blocks
(ssa
, block
)
1124 # Collect the variables declared in the for
1125 for v
in variables
do
1126 ssa
.propdef
.variables
.add
(v
)
1129 old_block
.link
(block
)
1131 block
.link
(old_block
)
1133 var new_block
= new BasicBlock
1134 new_block
.need_update
= true