9 import ExprAff, ExprCond, ExprId, ExprInt, ExprMem
11 log = logging.getLogger(
"analysis")
12 console_handler = logging.StreamHandler()
13 console_handler.setFormatter(logging.Formatter(
"%(levelname)-5s: %(message)s"))
14 log.addHandler(console_handler)
15 log.setLevel(logging.WARNING)
20 """Returns ids of all registers used in the IR"""
21 return self.arch.regs.all_regs_ids + [self.IRDst]
27 if self.ExprIsLabel(dst):
29 elif isinstance(dst, ExprMem)
or isinstance(dst, ExprInt):
31 elif isinstance(dst, ExprCond):
34 elif isinstance(dst, ExprId):
45 for irs
in reversed(b.irs):
71 @link_all: also gen edges to non present irblocs
74 for lbl, b
in self.blocs.items():
81 if isinstance(d, ExprInt):
83 self.symbol_pool.getby_offset_create(int(d.arg)))
84 if self.ExprIsLabel(d):
85 if d.name
in self.blocs
or link_all
is True:
86 self.g.add_edge(lbl, d.name)
89 """Output the graphviz script"""
99 for lbl
in self.g.nodes():
100 if lbl
not in self.blocs:
102 irb = self.blocs[lbl]
106 ir_txt.append(str(l))
109 all_lbls[hash(lbl)] =
"\l\\\n".join(ir_txt)
110 for l, v
in all_lbls.items():
112 out +=
'%s [label="%s"];\n' % (l, v)
114 for a, b
in self.g.edges():
116 out +=
'%s -> %s;\n' % (hash(a), hash(b))
121 """Remove dead affectations using previous reaches analysis
122 @irb: irbloc instance
123 @useful: useful statements from previous reach analysis
124 Return True iff the block state has changed
125 PRE: compute_reach(self)
128 for k, ir
in enumerate(irb.irs):
132 if (isinstance(cur_instr.dst, ExprId)
133 and (irb.label, k, cur_instr)
not in useful):
141 """Computes a set of triples (block, instruction number, instruction)
142 containing initially useful instructions :
143 - Instructions affecting final value of return registers
144 - Instructions affecting IRDst register
145 - Instructions writing in memory
146 - Function call instructions
147 Return set of intial useful instructions
152 for node
in self.g.nodes():
153 if node
not in self.blocs:
156 block = self.blocs[node]
157 successors = self.g.successors(node)
158 has_son = bool(successors)
159 for p_son
in successors:
160 if p_son
not in self.blocs:
164 useful.update(block.cur_reach[-1][r].union(
165 block.defout[-1][r]))
168 for k, ir
in enumerate(block.irs):
170 if i_cur.src.is_function_call():
172 useful.add((block.label, k, i_cur))
173 if isinstance(i_cur.dst, ExprMem):
174 useful.add((block.label, k, i_cur))
175 useful.update(block.defout[k][self.IRDst])
179 for r
in self.get_out_regs(block):
180 useful.update(block.defout[-1][r]
181 if block.defout[-1][r]
else
182 block.cur_reach[-1][r])
187 """Mark useful statements using previous reach analysis
189 Source : Kennedy, K. (1979). A survey of data flow analysis techniques.
190 IBM Thomas J. Watson Research Division, Algorithm MK
192 Return a set of triplets (block, instruction number, instruction) of
194 PRE: compute_reach(self)
199 worklist = useful.copy()
201 elem = worklist.pop()
203 irb, irs_ind, ins = elem
205 block = self.blocs[irb]
206 instr_defout = block.defout[irs_ind]
207 cur_kill = block.cur_kill[irs_ind]
208 cur_reach = block.cur_reach[irs_ind]
211 for reg
in ins.get_r(
True).intersection(self.
ira_regs_ids()):
213 cur_reach[reg].difference(useful).difference(
215 if not instr_defout[reg]
else
217 for _, _, i
in instr_defout[reg]:
220 worklist.update(cur_reach[reg].difference(useful))
224 """Remove dead instructions in each block of the graph using the reach
226 Returns True if a block has been modified
227 PRE : compute_reach(self)
231 for block
in self.blocs.values():
243 """Print each triplet contained in a set
244 @v_set: set containing triplets elements
247 print ' (%s, %s, %s)' % p
251 for k, irs
in enumerate(irb.irs):
252 for i
in xrange(len(irs)):
254 print 'instr', k, irs[i]
257 if irb.cur_reach[k][v]:
258 print 'REACH[%d][%s]' % (k, v)
260 if irb.cur_kill[k][v]:
261 print 'KILL[%d][%s]' % (k, v)
264 print 'DEFOUT[%d][%s]' % (k, v)
268 """Variable influence computation for a single block
269 @irb: irbloc instance
273 reach_block = {key: value.copy()
274 for key, value
in irb.cur_reach[0].iteritems()}
277 for n_pred
in self.g.predecessors(irb.label):
278 p_block = self.blocs[n_pred]
283 pred_through = p_block.defout[-1][c_reg].union(
284 p_block.cur_reach[-1][c_reg].difference(
285 p_block.cur_kill[-1][c_reg]))
286 reach_block[c_reg].update(pred_through)
289 if reach_block != irb.cur_reach[0]:
290 irb.cur_reach[0] = reach_block
292 if irb.defout[0][c_reg]:
294 irb.cur_kill[0][c_reg].update(
295 reach_block[c_reg].difference(irb.defout[0][c_reg]))
298 for i
in xrange(1, len(irb.irs)):
301 pred_through = irb.defout[i - 1][c_reg].union(
302 irb.cur_reach[i - 1][c_reg].difference(
303 irb.cur_kill[i - 1][c_reg]))
304 irb.cur_reach[i][c_reg].update(pred_through)
305 if irb.defout[i][c_reg]:
307 irb.cur_kill[i][c_reg].update(
308 irb.cur_reach[i][c_reg].difference(
309 irb.defout[i][c_reg]))
312 """Return True iff a fixed point has been reached during reach
316 for node
in self.g.nodes():
317 if node
in self.blocs:
318 irb = self.blocs[node]
319 if (irb.cur_reach != irb.prev_reach
or
320 irb.cur_kill != irb.prev_kill):
322 irb.prev_reach = irb.cur_reach[:]
323 irb.prev_kill = irb.cur_kill[:]
328 Compute reach, defout and kill sets until a fixed point is reached.
330 Source : Kennedy, K. (1979). A survey of data flow analysis techniques.
331 IBM Thomas J. Watson Research Division, page 43
336 log.debug(
'iteration...')
337 while not fixed_point:
338 for node
in self.g.nodes():
339 if node
in self.blocs:
345 This function is used to analyse relation of a * complete function *
346 This means the blocks under study represent a solid full function graph.
348 Source : Kennedy, K. (1979). A survey of data flow analysis techniques.
349 IBM Thomas J. Watson Research Division, page 43
359 self.simplify_blocs()
362 for irb
in self.blocs.values():
364 for r
in self.arch.regs.all_regs_ids:
365 x = ExprId(r.name, r.size)
368 sb =
symbexec(self, dict(symbols_init))
371 for n_w
in sb.symbols:
373 if n_w
in symbols_init
and symbols_init[n_w] == v:
375 eqs.append(ExprAff(n_w, v))
382 "Return the size of a char in bits"
383 raise NotImplementedError(
"Abstract method")
386 "Return the size of a short in bits"
387 raise NotImplementedError(
"Abstract method")
390 "Return the size of an int in bits"
391 raise NotImplementedError(
"Abstract method")
394 "Return the size of a long in bits"
395 raise NotImplementedError(
"Abstract method")
398 "Return the size of a void* in bits"
399 raise NotImplementedError(
"Abstract method")