6 var current_in
: nullable S
= default_in_set
is writable
7 var current_out
: nullable S
= default_in_set
is writable
9 fun in_set
(bb
: BasicBlock): nullable S
is abstract
10 fun out_set
(bb
: BasicBlock): nullable S
is abstract
11 fun in_set
=(bb
: BasicBlock, s
: S
) is abstract
12 fun out_set
=(bb
: BasicBlock, s
: S
) is abstract
14 redef fun visit
( node
) do node
.visit_all
(self)
16 # If false, it is a backwards analysis
17 fun is_forward
: Bool is abstract
19 # ex: do return in1.union( in2 )
20 # ex: do return in1.intersection( in2 )
21 fun merge
( in1
, in2
: nullable S
): nullable S
is abstract
23 fun default_in_set
: nullable S
do return null
24 fun empty_set
: S
is abstract
29 var current_in
: nullable S
30 var current_out
: nullable S
32 # set current input as default start case
33 var todo
= new List[BasicBlock]
34 todo
.add_all
(cfg
.blocks
)
36 # iterate until fixed point reached
37 while not todo
.is_empty
do
39 var block
= todo
.shift
41 if block
== cfg
.start
then
43 else if block
.predecessors
.is_empty
then
44 # get default in (the most safe one)
45 current_in
= default_in_set
47 current_in
= out_set
(block
.predecessors
.first
)
48 for l
in [1..block
.predecessors
.length
[ do
49 var b
= block
.predecessors
[l
]
50 current_in
= merge
(current_in
, out_set
(b
))
54 if current_in
!= null then
55 in_set
(block
) = current_in
.as(not null)
60 if block
== cfg
.finish
then continue
62 var old_out
= out_set
(block
)
63 for line
in block
.lines
do
64 self.current_in
= current_in
.as(not null)
65 self.current_out
= empty_set
69 current_out
= self.current_out
70 current_in
= self.current_out
.as(not null)
71 #self.current_in = current_in
74 current_out
= self.current_out
75 if old_out
!= current_out
then
76 out_set
(block
) = current_out
.as(not null)
78 for b
in block
.successors
do todo
.add
(b
)
80 for b
in block
.predecessors
do todo
.add
(b
)
86 fun pre_line_visit
(l
: ALine) do end
87 fun post_line_visit
(l
: ALine) do end
90 class FineFlowAnalysis[V
]
95 if bb
.lines
.is_empty
then return backup_in
(bb
)
96 return line_in
( bb
.lines
.first
)
99 redef fun in_set
=(bb
, v
)
101 if bb
.lines
.is_empty
then
103 else line_in
( bb
.lines
.first
) = v
106 redef fun out_set
(bb
)
108 if bb
.lines
.is_empty
then return backup_out
(bb
)
109 return line_out
( bb
.lines
.last
)
112 redef fun out_set
=(bb
, v
)
114 if bb
.lines
.is_empty
then
116 else line_out
( bb
.lines
.last
) = v
119 fun backup_in
(l
: BasicBlock): nullable V
is abstract
120 fun backup_out
(l
: BasicBlock): nullable V
is abstract
121 fun backup_in
=(l
: BasicBlock, v
: nullable V
) is abstract
122 fun backup_out
=(l
: BasicBlock, v
: nullable V
) is abstract
124 fun line_in
(l
: ALine): nullable V
is abstract
125 fun line_out
(l
: ALine): nullable V
is abstract
126 fun line_in
=(l
: ALine, v
: nullable V
) is abstract
127 fun line_out
=(l
: ALine, v
: nullable V
) is abstract
129 redef fun pre_line_visit
(line
) do line_in
(line
) = current_in
130 redef fun post_line_visit
(line
) do line_out
(line
) = current_out
133 class StaticAnalysis[S
]
137 init (set
: S
) do self.set
= set
139 redef fun visit
( node
) do node
.visit_all
(self)
140 fun analyze
(ast
: AListing): S