5 redef class AnalysisManager
6 fun build_cfg
( model
: Model ) : CFG
8 var cfg
= new CFG( model
)
13 redef class ABranchInstruction
17 return op
isa AAnyOperand and (once
["x","d"]).has
(op
.addressing_mode
)
22 var start
: BasicBlock
23 var finish
: BasicBlock
24 var addr_to_blocks
= new HashMap[Int,BasicBlock]
25 var blocks
= new Array[BasicBlock]
27 var has_function_calls
= false
31 assert not model
.lines
.is_empty
34 var ends
= [model
.lines
.last
.address
]
36 # check for indirect branches
37 #var indirect_jump_sites = new Array[Int]
38 var has_indirect_jump_sites
= false
40 # detect basic block limits
41 for line
in model
.lines
do
42 if line
isa AInstructionLine then
43 var instr
= line
.n_instruction
44 if instr
isa ABranchInstruction then
45 if instr
.is_indirect
then
46 #indirect_jump_sites.add(line.address)
47 has_indirect_jump_sites
= true
48 manager
.notes
.add
(new Warn(instr
.location
, "jumps to a dynamic address, this may be OK but the CFG may be wrong"))
50 var op
= instr
.n_operand
51 var dest
= op
.n_value
.to_i
54 ends
.add
(line
.address
)
55 if not instr
isa ABrInstruction then
56 # next line is possible start
57 starts
.add
(line
.address
+4)
59 else if instr
isa AStopInstruction or
60 instr
isa ARetInstruction then
61 ends
.add
(line
.address
)
66 var addresses_in_memory
= new Array[Int]
67 #if not indirect_jumps.is_empty then
68 if has_indirect_jump_sites
then
69 # find possible jump destinations
71 for line
in model
.lines
do
72 if line
isa ADirectiveLine then
73 var dir
= line
.n_directive
74 if dir
isa AAddrssDirective then
75 var dest
= dir
.n_value
.to_i
77 addresses_in_memory
.add
(dest
)
82 # link indirect jumps to possible destinations
83 #for src in addresses_in_memory do
87 # sort breakpoints in order
88 starts
= starts
.iterator
.uniq
.sort
.to_a
89 ends
= ends
.iterator
.uniq
.sort
.to_a
92 var current_block
: nullable BasicBlock = null
95 for line
in model
.lines
do
96 var addr
= line
.address
97 while next_start_i
< starts
.length
and
98 starts
[next_start_i
] < addr
do next_start_i
+= 1
99 if next_start_i
< starts
.length
and
100 starts
[next_start_i
] == addr
then
101 # is a dest, and not already started
102 current_block
= new BasicBlock
103 blocks
.add
(current_block
)
106 if current_block
== null then
107 current_block
= new BasicBlock
108 blocks
.add
(current_block
)
111 current_block
.lines
.add
(line
)
113 while next_end_i
< ends
.length
and
114 ends
[next_end_i
] < addr
do next_end_i
+= 1
115 if next_end_i
< ends
.length
and
116 ends
[next_end_i
] == addr
then
117 # stops here, unless already at the end
122 # adds created blocks to instance attribute
124 # save them in the class attribute
125 addr_to_blocks
[b
.lines
.first
.address
] = b
129 start
= new BasicBlock.start
131 if blocks
.length
> 0 and blocks
.first
!= start
then
132 start
.successors
.add
(blocks
.first
)
133 blocks
.first
.predecessors
.add
(start
)
135 addr_to_blocks
[-2] = start
138 finish
= new BasicBlock.finish
140 addr_to_blocks
[-1] = finish
142 # set successors and predecessors
143 for b
in blocks
do if not b
.lines
.is_empty
then
144 var line
= b
.lines
.last
146 if line
isa AInstructionLine then
147 var instr
= line
.n_instruction
148 if instr
isa ABranchInstruction then
149 var op
= instr
.n_operand
150 if instr
.is_indirect
then
151 for dest
in addresses_in_memory
do
152 var db
= addr_to_blocks
[dest
]
154 db
.predecessors
.add
(b
)
157 var dest
= op
.n_value
.to_i
158 var db
= addr_to_blocks
[dest
]
160 db
.predecessors
.add
(b
)
164 if not instr
isa ABrInstruction and
165 not instr
isa AStopInstruction and
166 not instr
isa ACallInstruction and
167 not instr
isa ARetInstruction then
168 # next line is possible start
169 var dest
= line
.address
+4
170 if addr_to_blocks
.has_key
(dest
) then
171 var db
= addr_to_blocks
[dest
]
173 db
.predecessors
.add
(b
)
175 manager
.notes
.add
(new P8Error(line
.location
,
176 "this instruction is not followed by valid code as it should (misplaced data or missing BR?)"))
180 if instr
isa ACallInstruction then
181 has_function_calls
= true
182 var next_addr
= line
.address
+4
183 if not addr_to_blocks
.has_key
(next_addr
) then
184 manager
.notes
.add
(new P8Error(line
.location
,
185 "this CALL is not followed by valide code as it should"))
187 b
.after_call
= addr_to_blocks
[next_addr
]
191 if b
.successors
.is_empty
and
192 not instr
isa ARetInstruction then
193 b
.successors
.add
(finish
)
194 finish
.predecessors
.add
(b
)
199 # Verify use of function calls
200 # To be by the book, each path from the start to the end should have
201 # the same number of calls and rets. There should never be more rets
204 # TODO check for instructions not in a path from start to end
206 # TODO check if branching on variable
208 # TODO check there is there is a consistant use of the stack between
212 # duplicate function calls
213 # at each call site, the tree representing the
216 inline_functions_recursive
(start
, new List[BasicBlock]) #0)
218 # retain only blocks reachble from start
219 var reachables
= new HashSet[BasicBlock]
220 var todo
= new Array[BasicBlock]
222 while not todo
.is_empty
do
224 if not reachables
.has
(n
) then
226 for s
in n
.successors
do if not reachables
.has
(s
) then
231 self.blocks
= reachables
.to_a
234 private fun inline_functions_recursive
(b
: BasicBlock, seq
: List[BasicBlock]) #depth: Int)
236 # Protection against cycles
237 #if depth > 1000 then return
240 if sl
> loop_length
then
241 for i
in [0..sl-loop_length
[ do
243 for j
in [0..loop_length
[ do if seq
[i
+j
]!=seq
[sl-3
+j
] then
249 print
"recursive since {seq[i].name}"
254 #if seq.has(b) then return
256 if not b
.lines
.is_empty
then
257 var line
= b
.lines
.last
258 if line
isa AInstructionLine then
259 var instr
= line
.n_instruction
260 if instr
isa ACallInstruction then
261 # replace called by a dup
262 assert b
.successors
.length
== 1
263 var called
= b
.successors
.first
264 var rets
= new HashSet[BasicBlock]
265 var n
= called
.duplicate_tree
(
266 new HashMap[BasicBlock,BasicBlock], rets
, 0, blocks
)
268 n
.predecessors
.add
(b
)
270 if b
.after_call
== null then
271 print
"Already inlined"
274 # TODO bring back assert
275 if n
.predecessors
.length
> 1 then
278 print
"preds {n.predecessors.join(" ")}"
280 assert n
.predecessors
.length
== 1 else print n
.predecessors
.length
281 assert b
.successors
.length
== 1
282 # TODO add information about duplicated block that are not dead
285 var next
= b
.after_call
.as(not null)
286 # Another protection against cycles
288 ret
.successors
.add
(next
)
289 next
.predecessors
.add
(ret
)
291 #print "linking {b.name} to {next.name} ret len {rets.length}"
300 while si
< b
.successors
.length
do
301 var s
= b
.successors
[si
]
303 inline_functions_recursive
(s
, seq
)
309 var watchdog
= 0 is writable
310 fun link_ret_to_calls
(b
: BasicBlock, to_link_ori
: List[BasicBlock], seq
: List[BasicBlock], depth
: Int): Bool
313 if watchdog
== 10000 then
314 print
"Error: Umanagable cycle detected"
320 if sl
> loop_length
then
321 for i
in [0..sl-loop_length
[ do
323 for j
in [0..loop_length
[ do if seq
[i
+j
]!=seq
[sl-loop_length
+j
] then
329 #print "recursive since {seq[i].name}"
336 var to_link
= new List[BasicBlock]
337 to_link
.add_all
(to_link_ori
)
339 if not b
.lines
.is_empty
then
340 var line
= b
.lines
.last
341 if line
isa AInstructionLine then
342 var instr
= line
.n_instruction
343 if instr
isa ACallInstruction then
346 else if instr
isa ARetInstruction then
347 if to_link
.is_empty
then
348 manager
.notes
.add
( new P8Error(instr
.location
,"no CALL can be linked to this RET") )
351 var caller
= to_link
.pop
353 var next
= caller
.after_call
.as(not null)
355 # Another protection against cycles
356 if b
.successors
.has
(next
) then return true
358 b
.successors
.add
(next
)
359 next
.predecessors
.add
(b
)
366 while si
< b
.successors
.length
do
367 var s
= b
.successors
[si
]
369 if not link_ret_to_calls
(s
, to_link
,seq
,depth
+1) then return false
379 var name
: String is noinit
380 var lines
= new Array[ANonEmptyLine]
381 var successors
= new Array[BasicBlock]
382 var predecessors
= new Array[BasicBlock]
383 var after_call
: nullable BasicBlock = null
387 var count
= (once
new Counter).next
390 init named
(name
: String) do self.name
= name
391 init start
do name
= "start"
397 fun duplicate_tree
(dups
: HashMap[BasicBlock,BasicBlock],
398 rets
: Set[BasicBlock], calls
: Int,
399 blocks
: Array[BasicBlock]) : BasicBlock
401 if dups
.has_key
(self) then return dups
[self]
403 var n
= new BasicBlock.from
(self)
406 n
.successors
= new Array[BasicBlock]
407 n
.predecessors
= new Array[BasicBlock]
409 if after_call
!= null then
410 var nac
= after_call
.duplicate_tree
(dups
, rets
, calls
, blocks
)
412 calls
+= 1 # for within that call
415 for s
in successors
do
416 var ns
= s
.duplicate_tree
(dups
, rets
, calls
, blocks
)
418 ns
.predecessors
.add
(n
)
421 if calls
== 0 and successors
.is_empty
then rets
.add
(n
)
426 init from
(o
: BasicBlock)
428 var count
= (once
new Counter).next
429 name
= "c{count}_from_{o.name}"
431 successors
= o
.successors
432 predecessors
= o
.predecessors
433 after_call
= o
.after_call
437 private class Counter