b0e1bbefc0ac4ba693c5435932c2d167b2611c67
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 # If true, the iterated dominance frontier of this block has been computed
106 var df_computed
: Bool = false
108 # Indicate the BasicBlock is newly created and needs to be updated
109 var need_update
: Bool = false
111 # Indicate if the variables renaming step has been made for this block
112 var is_renaming
: Bool = false
114 # The variables that are accessed in this block
115 var variables
= new Array[Variable] is lazy
117 # The PhiFunction this block contains at the beginning
118 var phi_functions
= new Array[PhiFunction] is lazy
121 # Contain the currently analyzed propdef
123 # The currently analyzed APropdef
124 var propdef
: APropdef
126 # The PhiFunction `current_propdef` contains
127 var phi_functions
= new Array[PhiFunction]
129 # Recursively generate the basic blocks for this propdef
130 fun generate_basic_blocks
132 propdef
.generate_basic_blocks
(self)
137 # The expressions of AST of this variable depends
138 var dep_exprs
= new Array[AExpr]
140 # The blocks in which this variable is assigned
141 var assignment_blocks
: Array[BasicBlock] = new Array[BasicBlock] is lazy
143 # Part of the program where this variable is read
144 var read_blocks
: Array[BasicBlock] = new Array[BasicBlock] is lazy
146 # The stack of this variable, used for SSA renaming
147 var stack
= new Array[Variable] is lazy
149 # The original Variable in case of renaming
150 var original_variable
: nullable Variable = self
152 # If true, this variable is a parameter of a method
153 var parameter
: Bool = false
156 # A PhiFunction is a kind of Variable used in SSA-construction,
157 # it is placed at the beginning of a BasicBlock with many incoming blocks
161 # The dependences of this variable for SSA-Algorithm
162 var dependences
= new Array[Couple[Variable, BasicBlock]]
164 # The position in the AST of the phi-function
165 var block
: BasicBlock
167 # Set the dependences for the phi-function
168 # *`block` BasicBlock in which we go through the dominance-frontier
169 # *`v` The variable to looking for
170 fun add_dependences
(block
: BasicBlock, v
: Variable)
172 # Look in which blocks of DF(block) `v` has been assigned
173 for b
in block
.predecessors
do
174 if v
.assignment_blocks
.has
(b
) then
175 var dep
= new Couple[Variable, BasicBlock](v
, b
)
181 # Print the PhiFunction with all its dependences
182 redef fun to_s
: String
185 s
+= " dependences = [ "
186 for d
in dependences
do
187 s
+= d
.first
.to_s
+ " "
196 # The variables contained in the body on this propdef
197 var variables
: HashSet[Variable] = new HashSet[Variable] is lazy
199 # The first basic block of the code
200 var basic_block
: nullable BasicBlock
202 # If true, the basic blocks where generated
203 var is_generated
: Bool = false
205 # Generate all basic blocks for this code
206 fun generate_basic_blocks
(ssa
: SSA) is abstract
208 # Compute the three steps of SSA-algorithm
209 # `ssa` A new instance of SSA class initialized with `self`
210 fun compute_ssa
(ssa
: SSA)
212 if is_generated
then return
214 # The first step is to generate the basic blocks
215 generate_basic_blocks
(ssa
)
217 # The propdef has no body (abstract)
218 if not is_generated
then return
220 # Once basic blocks were generated, compute SSA algorithm
222 rename_variables
(ssa
)
226 # Compute the first phase of SSA algorithm: placing phi-functions
227 fun compute_phi
(ssa
: SSA)
229 var root_block
= basic_block
.as(not null)
231 # Compute the iterated dominance frontier of the graph of basic blocks
232 root_block
.compute_df
234 # Places where a phi-function is added per variable
235 var phi_blocks
= new HashMap[Variable, Array[BasicBlock]]
237 # For each variables in the propdef
238 for v
in variables
do
239 var phi_variables
= new Array[BasicBlock]
241 var read_blocks
= new Array[BasicBlock]
242 read_blocks
.add_all
(v
.read_blocks
)
243 read_blocks
.add_all
(v
.assignment_blocks
)
245 # While we have not treated each part accessing `v`
246 while not read_blocks
.is_empty
do
247 # Remove a block from the array
248 var block
= read_blocks
.shift
250 # For each block in the dominance frontier of `block`
251 for df
in block
.dominance_frontier
do
252 # If we have not yet put a phi-function at the beginning of this block
253 if not phi_variables
.has
(df
) then
254 phi_variables
.add
(df
)
256 # Create a new phi-function and set its dependences
257 var phi
= new PhiFunction("phi", df
)
258 phi
.add_dependences
(df
, v
)
260 phi
.original_variable
= phi
261 phi
.declared_type
= v
.declared_type
263 # Indicate this phi-function is assigned in this block
264 phi
.assignment_blocks
.add
(block
)
265 ssa
.phi_functions
.add
(phi
)
267 # Add a phi-function at the beginning of df for variable v
268 df
.phi_functions
.add
(phi
)
270 if not v
.read_blocks
.has
(df
) or not v
.assignment_blocks
.has
(df
) then read_blocks
.add
(df
)
275 # Add `phi-variables` to the global map
276 phi_blocks
[v
] = phi_variables
280 # Compute the second phase of SSA algorithm: renaming variables
281 # NOTE: `compute_phi` must has been called before
282 fun rename_variables
(ssa
: SSA)
284 # A counter for each variable
285 # The key is the variable, the value the number of assignment into the variable
286 var counter
= new HashMap[Variable, Int]
288 for v
in variables
do
293 for phi
in ssa
.phi_functions
do counter
[phi
] = 0
295 # Launch the recursive renaming from the root block
296 rename
(basic_block
.as(not null), counter
, ssa
)
299 # Recursively rename each variable from `block`
300 # *`block` The starting basic block
301 # *`counter` The key is the variable, the value the number of assignment into the variable
302 fun rename
(block
: BasicBlock, counter
: HashMap[Variable, Int], ssa
: SSA)
304 if block
.is_renaming
then return
306 block
.is_renaming
= true
308 # For each phi-function of this block
309 for phi
in block
.phi_functions
do
310 generate_name
(phi
, counter
, block
.first
, ssa
)
312 # Replace the phi into the block
313 block
.phi_functions
[block
.phi_functions
.index_of
(phi
)] = phi
.original_variable
.stack
.last
.as(PhiFunction)
316 # For each variable read in `block`
317 for vread
in block
.read_sites
do
318 # Replace the old variable in AST
319 vread
.variable
= vread
.variable
.original_variable
.stack
.last
322 # For each variable write
323 for vwrite
in block
.write_sites
do
324 generate_name
(vwrite
.variable
.as(not null), counter
, vwrite
, ssa
)
326 var new_version
= vwrite
.variable
.original_variable
.stack
.last
328 # Set dependence of the new variable
329 if vwrite
isa AVarReassignExpr then
330 new_version
.dep_exprs
.add
(vwrite
.n_value
)
331 else if vwrite
isa AVarAssignExpr then
332 new_version
.dep_exprs
.add
(vwrite
.n_value
)
335 # Replace the old variable by the last created
336 vwrite
.variable
= new_version
339 # Rename occurrence of old names in phi-function
340 for successor
in block
.dominance_frontier
do
341 for sphi
in successor
.phi_functions
do
342 # Go over the couples in the phi dependences to rename variables
343 for couple
in sphi
.dependences
do
344 if couple
.second
== block
then
345 # Rename this variable
346 couple
.first
= couple
.first
.original_variable
.stack
.last
352 # Recurse in successor blocks
353 for successor
in block
.successors
do
354 rename
(successor
, counter
, ssa
)
357 # Pop old names off the stack for each phi-function
358 for phi
in block
.phi_functions
do
359 if not phi
.stack
.is_empty
then phi
.stack
.pop
363 # Generate a new version of the variable `v` and return it
364 # *`v` The variable for which we generate a name
365 # *`counter` The key is the variable, the value the number of assignment into the variable
366 # *`expr` The AST node in which the assignment of v is made
367 # *`ssa` The instance of SSA
368 fun generate_name
(v
: Variable, counter
: HashMap[Variable, Int], expr
: ANode, ssa
: SSA): Variable
370 var original_variable
= v
.original_variable
.as(not null)
372 var i
= counter
[original_variable
]
374 var new_version
: Variable
376 # Create a new version of Variable
377 if original_variable
isa PhiFunction then
378 var block
= original_variable
.block
379 new_version
= new PhiFunction(original_variable
.name
+ i
.to_s
, block
)
380 new_version
.dependences
.add_all
(original_variable
.dependences
)
381 ssa
.phi_functions
.add
(new_version
)
383 new_version
= new Variable(original_variable
.name
+ i
.to_s
)
384 new_version
.declared_type
= expr
.as(AVarFormExpr).variable
.declared_type
385 variables
.add
(new_version
)
388 # Recopy the fields into the new version
389 new_version
.location
= expr
.location
390 new_version
.original_variable
= original_variable
392 # Push a new version on the stack
393 original_variable
.stack
.add
(new_version
)
399 # Transform SSA-representation into an executable code (delete phi-functions)
400 # `ssa` Current instance of SSA
401 fun ssa_destruction
(ssa
: SSA)
403 var builder
= new ASTBuilder(mpropdef
.mclassdef
.mmodule
, mpropdef
.mclassdef
.bound_mtype
)
405 # Iterate over all phi-functions
406 for phi
in ssa
.phi_functions
do
407 for dep
in phi
.dependences
do
408 # dep.second is the block where we need to create a varassign
409 var var_read
= builder
.make_var_read
(dep
.first
, dep
.first
.declared_type
.as(not null))
410 var nvar
= builder
.make_var_assign
(dep
.first
, var_read
)
412 var block
= dep
.second
.last
.parent
414 # This variable read must be add to a ABlockExpr
415 if block
isa ABlockExpr then
419 propagate_dependences
(phi
, phi
.block
)
420 ssa
.propdef
.variables
.add
(dep
.first
)
425 # Propagate the dependences of the phi-functions into following variables
426 # `phi` The PhiFunction
427 # `block` Current block where we propagate dependences
428 fun propagate_dependences
(phi
: PhiFunction, block
: BasicBlock)
430 # Treat each block once
431 if block
.treated
then return
433 # For each variable access site in the block
434 for site
in block
.variables_sites
do
435 if site
isa AVarExpr then
436 # Propagate the dependences of the phi-function in variables after the phi
437 for dep
in phi
.dependences
do
438 for expr
in dep
.first
.dep_exprs
do
439 if site
.variable
.dep_exprs
.has
(expr
) then break
441 if dep
.first
.original_variable
== site
.variable
.original_variable
then
442 site
.variable
.dep_exprs
.add
(expr
)
447 # The site is a variable write, we stop the propagation
454 # If we do not meet a variable write, continue the propagation
455 for b
in block
.successors
do propagate_dependences
(phi
, b
)
459 redef class AAttrPropdef
460 redef fun generate_basic_blocks
(ssa
: SSA)
462 basic_block
= new BasicBlock
463 basic_block
.first
= self
464 basic_block
.last
= self
466 # Add the self variable
467 if self.selfvariable
!= null then variables
.add
(selfvariable
.as(not null))
469 # Recursively goes into the nodes
470 if n_block
!= null then
471 n_block
.generate_basic_blocks
(ssa
, basic_block
.as(not null))
477 redef class AMethPropdef
479 # The return variable of the propdef
480 # Create an empty variable for the return of the method
481 # and treat returns like variable assignments
482 var returnvar
: Variable = new Variable("returnvar")
484 redef fun generate_basic_blocks
(ssa
: SSA)
486 basic_block
= new BasicBlock
487 basic_block
.first
= self
488 basic_block
.last
= self
490 # If the method has a signature
491 if n_signature
!= null then
492 for p
in n_signature
.n_params
do
493 # Add parameters to the local variables
494 variables
.add
(p
.variable
.as(not null))
495 p
.variable
.parameter
= true
499 # Add the return variable
500 variables
.add
(returnvar
)
502 # Add the self variable
503 if self.selfvariable
!= null then variables
.add
(selfvariable
.as(not null))
505 # Recursively goes into the nodes
506 if n_block
!= null then
507 n_block
.generate_basic_blocks
(ssa
, basic_block
.as(not null))
514 # Generate recursively basic block for this expression
515 # *`ssa` An instance of the SSA class initialized with the enclosing `APropdef`
516 # *`old_block` A basic block not completely filled
517 # Return the last created block (the last block can be nested)
518 fun generate_basic_blocks
(ssa
: SSA, old_block
: BasicBlock): BasicBlock
524 redef class AVarFormExpr
525 # The original variable
526 var original_variable
: nullable Variable = variable
530 redef fun generate_basic_blocks
(ssa
, old_block
)
532 self.variable
.as(not null).read_blocks
.add
(old_block
)
533 old_block
.variables
.add
(self.variable
.as(not null))
535 self.variable
.as(not null).original_variable
= self.variable
.as(not null)
536 # Save this read site in the block
537 old_block
.read_sites
.add
(self)
538 old_block
.variables_sites
.add
(self)
544 redef class AVardeclExpr
545 redef fun generate_basic_blocks
(ssa
, old_block
)
547 var decl
= self.variable
.as(not null)
549 # Add the corresponding variable to the enclosing mpropdef
550 ssa
.propdef
.variables
.add
(decl
)
552 decl
.original_variable
= decl
553 decl
.assignment_blocks
.add
(old_block
)
554 old_block
.variables
.add
(decl
)
556 if self.n_expr
!= null then
557 self.variable
.dep_exprs
.add
(self.n_expr
.as(not null))
558 old_block
= self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
565 redef class AVarAssignExpr
566 redef fun generate_basic_blocks
(ssa
, old_block
)
568 self.variable
.as(not null).assignment_blocks
.add
(old_block
)
569 old_block
.variables
.add
(self.variable
.as(not null))
570 self.variable
.as(not null).original_variable
= self.variable
.as(not null)
572 # Save this write site in the block
573 old_block
.write_sites
.add
(self)
574 old_block
.variables_sites
.add
(self)
576 ssa
.propdef
.variables
.add
(self.variable
.as(not null))
578 return self.n_value
.generate_basic_blocks
(ssa
, old_block
)
582 redef class AVarReassignExpr
583 redef fun generate_basic_blocks
(ssa
, old_block
)
585 self.variable
.as(not null).assignment_blocks
.add
(old_block
)
586 old_block
.variables
.add
(self.variable
.as(not null))
587 self.variable
.as(not null).original_variable
= self.variable
.as(not null)
589 # Save this write site in the block
590 old_block
.write_sites
.add
(self)
591 old_block
.variables_sites
.add
(self)
593 ssa
.propdef
.variables
.add
(self.variable
.as(not null))
594 return self.n_value
.generate_basic_blocks
(ssa
, old_block
)
598 redef class ABreakExpr
599 redef fun generate_basic_blocks
(ssa
, old_block
)
601 # Finish the old block
602 old_block
.last
= self
608 redef class AContinueExpr
609 redef fun generate_basic_blocks
(ssa
, old_block
)
615 redef class AReturnExpr
616 redef fun generate_basic_blocks
(ssa
, old_block
)
618 # The return just set the current block and stop the recursion
619 if self.n_expr
!= null then
620 old_block
= self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
622 # Store the return expression in the dependences of the dedicated returnvar
623 if ssa
.propdef
isa AMethPropdef then
624 ssa
.propdef
.as(AMethPropdef).returnvar
.dep_exprs
.add
(n_expr
.as(not null))
628 old_block
.last
= self
634 redef class AAssertExpr
635 redef fun generate_basic_blocks
(ssa
, old_block
)
637 self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
639 # The condition of the assert is the last expression of the previous block
640 old_block
.last
= self.n_expr
642 # The block if the assert fail
643 var block_false
= new BasicBlock
645 if self.n_else
!= null then
646 block_false
.first
= self.n_else
.as(not null)
647 block_false
.last
= self.n_else
.as(not null)
648 self.n_else
.generate_basic_blocks
(ssa
, block_false
)
650 block_false
.first
= self
651 block_false
.first
= self
654 old_block
.link
(block_false
)
656 # The block if the assert is true: the execution continue
657 var block_true
= new BasicBlock
658 block_true
.first
= self
659 block_true
.last
= self
661 old_block
.link
(block_true
)
668 redef fun generate_basic_blocks
(ssa
, old_block
)
670 self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
671 return self.n_expr2
.generate_basic_blocks
(ssa
, old_block
)
675 redef class AImpliesExpr
676 redef fun generate_basic_blocks
(ssa
, old_block
)
678 self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
679 return self.n_expr2
.generate_basic_blocks
(ssa
, old_block
)
684 redef fun generate_basic_blocks
(ssa
, old_block
)
686 self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
687 return self.n_expr2
.generate_basic_blocks
(ssa
, old_block
)
692 redef fun generate_basic_blocks
(ssa
, old_block
)
694 return self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
698 redef class AOrElseExpr
699 redef fun generate_basic_blocks
(ssa
, old_block
)
701 self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
702 return self.n_expr2
.generate_basic_blocks
(ssa
, old_block
)
706 redef class AArrayExpr
707 redef fun generate_basic_blocks
(ssa
, old_block
)
709 for nexpr
in self.n_exprs
do
710 old_block
= nexpr
.generate_basic_blocks
(ssa
, old_block
)
717 redef class ASuperstringExpr
718 redef fun generate_basic_blocks
(ssa
, old_block
)
720 for nexpr
in self.n_exprs
do old_block
= nexpr
.generate_basic_blocks
(ssa
, old_block
)
726 redef class ACrangeExpr
727 redef fun generate_basic_blocks
(ssa
, old_block
)
729 self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
730 return self.n_expr2
.generate_basic_blocks
(ssa
, old_block
)
734 redef class AOrangeExpr
735 redef fun generate_basic_blocks
(ssa
, old_block
)
737 self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
738 return self.n_expr2
.generate_basic_blocks
(ssa
, old_block
)
743 redef fun generate_basic_blocks
(ssa
, old_block
)
745 return self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
749 redef class AAsCastExpr
750 redef fun generate_basic_blocks
(ssa
, old_block
)
752 return self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
756 redef class AAsNotnullExpr
757 redef fun generate_basic_blocks
(ssa
, old_block
)
759 return self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
764 redef fun generate_basic_blocks
(ssa
, old_block
)
766 return self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
770 redef class AOnceExpr
771 redef fun generate_basic_blocks
(ssa
, old_block
)
773 return self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
777 redef class ASendExpr
778 redef fun generate_basic_blocks
(ssa
, old_block
)
780 # A call does not finish the current block,
781 # because we create intra-procedural basic blocks here
783 # Recursively goes into arguments to find variables if any
784 for e
in self.raw_arguments
do e
.generate_basic_blocks
(ssa
, old_block
)
786 return self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
790 redef class ASendReassignFormExpr
791 redef fun generate_basic_blocks
(ssa
, old_block
)
793 self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
795 # Recursively goes into arguments to find variables if any
796 for e
in self.raw_arguments
do e
.generate_basic_blocks
(ssa
, old_block
)
798 return self.n_value
.generate_basic_blocks
(ssa
, old_block
)
802 redef class ASuperExpr
803 redef fun generate_basic_blocks
(ssa
, old_block
)
805 # Recursively goes into arguments to find variables if any
806 for arg
in self.n_args
.n_exprs
do arg
.generate_basic_blocks
(ssa
, old_block
)
813 redef fun generate_basic_blocks
(ssa
, old_block
)
815 for e
in self.n_args
.n_exprs
do e
.generate_basic_blocks
(ssa
, old_block
)
821 redef class AAttrExpr
822 redef fun generate_basic_blocks
(ssa
, old_block
)
824 return self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
828 redef class AAttrAssignExpr
829 redef fun generate_basic_blocks
(ssa
, old_block
)
831 return self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
835 redef class AAttrReassignExpr
836 redef fun generate_basic_blocks
(ssa
, old_block
)
838 return self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
842 redef class AIssetAttrExpr
843 redef fun generate_basic_blocks
(ssa
, old_block
)
845 return self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
849 redef class ABlockExpr
850 # The block needs to know if a new block is created
851 redef fun generate_basic_blocks
(ssa
, old_block
)
853 var last_block
= old_block
854 var current_block
: BasicBlock
856 # Recursively continue in the body of the block
857 for i
in [0..self.n_expr
.length
[ do
858 current_block
= self.n_expr
[i
].generate_basic_blocks
(ssa
, last_block
)
860 if current_block
.need_update
then
861 if i
< (self.n_expr
.length-1
) then
862 # Current_block must be filled
863 current_block
.first
= self.n_expr
[i
+1]
864 current_block
.last
= self.n_expr
[i
+1]
865 current_block
.need_update
= false
867 # Put the current block at the end of the block
868 current_block
.first
= last_block
.last
869 current_block
.last
= last_block
.last
873 if not current_block
.last
isa AEscapeExpr or current_block
.last
isa AReturnExpr then
874 # Re-affected the last block
875 current_block
.last
= self.n_expr
[i
]
878 last_block
= current_block
886 redef fun generate_basic_blocks
(ssa
, old_block
)
888 # Terminate the previous block
889 old_block
.last
= self
891 # We start two new blocks if the if has two branches
892 var block_then
= new BasicBlock
894 # Visit the test of the if
895 self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
897 # Launch the recursion in two successors if they exist
898 if self.n_then
!= null then
899 old_block
.link
(block_then
)
901 block_then
.first
= self.n_then
.as(not null)
902 block_then
.last
= self.n_then
.as(not null)
903 self.n_then
.generate_basic_blocks
(ssa
, block_then
)
906 var block_else
= new BasicBlock
908 if self.n_else
!= null then
909 old_block
.link
(block_else
)
911 block_else
.first
= self.n_else
.as(not null)
912 block_else
.last
= self.n_else
.as(not null)
913 self.n_else
.generate_basic_blocks
(ssa
, block_else
)
916 # Create a new BasicBlock to represent the two successor
918 var new_block
= new BasicBlock
919 new_block
.first
= self
920 new_block
.last
= self
922 if self.n_then
!= null then block_then
.link
(new_block
)
924 # The new block needs to be filled by the caller
925 new_block
.need_update
= true
927 if block_else
.predecessors
.length
!= 0 then block_else
.link
(new_block
)
933 redef class AIfexprExpr
934 redef fun generate_basic_blocks
(ssa
, old_block
)
936 # Terminate the previous block
937 old_block
.last
= self
939 # We start two new blocks if the if has two branches
940 var block_then
= new BasicBlock
942 # Visit the test of the if
943 self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
945 # Launch the recursion in two successors if they exist
946 old_block
.link
(block_then
)
948 block_then
.first
= self.n_then
949 block_then
.last
= self.n_then
950 self.n_then
.generate_basic_blocks
(ssa
, block_then
)
952 var block_else
= new BasicBlock
954 old_block
.link
(block_else
)
956 block_else
.first
= self.n_else
957 block_else
.last
= self.n_else
958 self.n_else
.generate_basic_blocks
(ssa
, block_else
)
960 # Create a new BasicBlock to represent the two successor
962 var new_block
= new BasicBlock
963 new_block
.first
= self
964 new_block
.last
= self
966 block_then
.link
(new_block
)
968 # The new block needs to be filled by the caller
969 new_block
.need_update
= true
971 block_else
.link
(new_block
)
978 redef fun generate_basic_blocks
(ssa
, old_block
)
980 old_block
.last
= self
982 # The beginning of the block is the first instruction
983 var block
= new BasicBlock
984 block
.first
= self.n_block
.as(not null)
985 block
.last
= self.n_block
.as(not null)
987 old_block
.link
(block
)
988 return self.n_block
.generate_basic_blocks
(ssa
, block
)
992 redef class AWhileExpr
993 redef fun generate_basic_blocks
(ssa
, old_block
)
995 old_block
.last
= self
997 # The beginning of the block is the test of the while
998 var block
= new BasicBlock
999 block
.first
= self.n_expr
1000 block
.last
= self.n_block
.as(not null)
1002 old_block
.link
(block
)
1004 self.n_expr
.generate_basic_blocks
(ssa
, old_block
)
1005 var inside_block
= self.n_block
.generate_basic_blocks
(ssa
, block
)
1007 # Link the inside of the block to the previous block
1008 block
.link_special
(old_block
)
1010 # Create a new Block after the while
1011 var new_block
= new BasicBlock
1012 new_block
.need_update
= true
1014 old_block
.link_special
(new_block
)
1020 redef class ALoopExpr
1021 redef fun generate_basic_blocks
(ssa
, old_block
)
1023 old_block
.last
= self
1025 # The beginning of the block is the first instruction
1026 var block
= new BasicBlock
1027 block
.first
= self.n_block
.as(not null)
1028 block
.last
= self.n_block
.as(not null)
1030 old_block
.link
(block
)
1031 self.n_block
.generate_basic_blocks
(ssa
, block
)
1037 redef class AForExpr
1038 redef fun generate_basic_blocks
(ssa
, old_block
)
1040 old_block
.last
= self
1042 # The beginning of the block is the first instruction
1043 var block
= new BasicBlock
1044 block
.first
= self.n_expr
1045 block
.last
= self.n_block
.as(not null)
1047 # Visit the test of the if
1048 self.n_expr
.generate_basic_blocks
(ssa
, block
)
1050 # Collect the variables declared in the for
1051 for v
in variables
do
1052 ssa
.propdef
.variables
.add
(v
)
1055 old_block
.link
(block
)
1057 block
.link
(old_block
)
1059 var new_block
= new BasicBlock
1060 new_block
.need_update
= true