Miasm2
 All Classes Namespaces Files Functions Variables Typedefs Properties Macros
Public Member Functions | Static Public Member Functions | Public Attributes | Private Member Functions | List of all members
miasm2.ir.analysis.ira Class Reference
+ Inheritance diagram for miasm2.ir.analysis.ira:
+ Collaboration diagram for miasm2.ir.analysis.ira:

Public Member Functions

def ira_regs_ids
 
def sort_dst
 
def dst_trackback
 
def gen_graph
 
def graph
 
def remove_dead_instr
 
def init_useful_instr
 
def remove_dead_code
 
def set_dead_regs
 
def add_unused_regs
 
def dump_bloc_state
 
def compute_reach_block
 
def compute_reach
 
def dead_simp
 
def gen_equations
 
def sizeof_char
 
def sizeof_short
 
def sizeof_int
 
def sizeof_long
 
def sizeof_pointer
 

Static Public Member Functions

def print_set
 

Public Attributes

 g
 

Private Member Functions

def _mark_useful_code
 
def _test_kill_reach_fix
 

Detailed Description

Definition at line 17 of file analysis.py.

Member Function Documentation

def miasm2.ir.analysis.ira._mark_useful_code (   self)
private 
Mark useful statements using previous reach analysis

Source : Kennedy, K. (1979). A survey of data flow analysis techniques.
IBM Thomas J. Watson Research Division,  Algorithm MK

Return a set of triplets (block, instruction number, instruction) of
useful instructions
PRE: compute_reach(self)

Definition at line 186 of file analysis.py.

186 
187  def _mark_useful_code(self):
188  """Mark useful statements using previous reach analysis
189 
190  Source : Kennedy, K. (1979). A survey of data flow analysis techniques.
191  IBM Thomas J. Watson Research Division, Algorithm MK
192 
193  Return a set of triplets (block, instruction number, instruction) of
194  useful instructions
195  PRE: compute_reach(self)
196 
197  """
198 
199  useful = self.init_useful_instr()
200  worklist = useful.copy()
201  while worklist:
202  elem = worklist.pop()
203  useful.add(elem)
204  irb, irs_ind, ins = elem
205 
206  block = self.blocs[irb]
207  instr_defout = block.defout[irs_ind]
208  cur_kill = block.cur_kill[irs_ind]
209  cur_reach = block.cur_reach[irs_ind]
210 
211  # Handle dependencies of used variables in ins
212  for reg in ins.get_r(True).intersection(self.ira_regs_ids()):
213  worklist.update(
214  cur_reach[reg].difference(useful).difference(
215  cur_kill[reg]
216  if not instr_defout[reg] else
217  set()))
218  for _, _, i in instr_defout[reg]:
219  # Loop case (i in defout of current block)
220  if i == ins:
221  worklist.update(cur_reach[reg].difference(useful))
222  return useful

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.ir.analysis.ira._test_kill_reach_fix (   self)
private 
Return True iff a fixed point has been reached during reach
analysis

Definition at line 311 of file analysis.py.

311 
312  def _test_kill_reach_fix(self):
313  """Return True iff a fixed point has been reached during reach
314  analysis"""
315 
316  fixed = True
317  for node in self.g.nodes():
318  if node in self.blocs:
319  irb = self.blocs[node]
320  if (irb.cur_reach != irb.prev_reach or
321  irb.cur_kill != irb.prev_kill):
322  fixed = False
323  irb.prev_reach = irb.cur_reach[:]
324  irb.prev_kill = irb.cur_kill[:]
325  return fixed

+ Here is the caller graph for this function:

def miasm2.ir.analysis.ira.add_unused_regs (   self)

Definition at line 238 of file analysis.py.

238 
239  def add_unused_regs(self):
240  pass
def miasm2.ir.analysis.ira.compute_reach (   self) 
Compute reach, defout and kill sets until a fixed point is reached.

Source : Kennedy, K. (1979). A survey of data flow analysis techniques.
IBM Thomas J. Watson Research Division, page 43

PRE: gen_graph()

Definition at line 326 of file analysis.py.

326 
327  def compute_reach(self):
328  """
329  Compute reach, defout and kill sets until a fixed point is reached.
330 
331  Source : Kennedy, K. (1979). A survey of data flow analysis techniques.
332  IBM Thomas J. Watson Research Division, page 43
333 
334  PRE: gen_graph()
335  """
336  fixed_point = False
337  log.debug('iteration...')
338  while not fixed_point:
339  for node in self.g.nodes():
340  if node in self.blocs:
341  self.compute_reach_block(self.blocs[node])
342  fixed_point = self._test_kill_reach_fix()

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.ir.analysis.ira.compute_reach_block (   self,
  irb 
) 
Variable influence computation for a single block
@irb: irbloc instance
PRE: init_reach()

Definition at line 267 of file analysis.py.

267 
268  def compute_reach_block(self, irb):
269  """Variable influence computation for a single block
270  @irb: irbloc instance
271  PRE: init_reach()
272  """
273 
274  reach_block = {key: value.copy()
275  for key, value in irb.cur_reach[0].iteritems()}
276 
277  # Compute reach from predecessors
278  for n_pred in self.g.predecessors(irb.label):
279  p_block = self.blocs[n_pred]
280 
281  # Handle each register definition
282  for c_reg in self.ira_regs_ids():
283  # REACH(n) = U[p in pred] DEFOUT(p) U REACH(p)\KILL(p)
284  pred_through = p_block.defout[-1][c_reg].union(
285  p_block.cur_reach[-1][c_reg].difference(
286  p_block.cur_kill[-1][c_reg]))
287  reach_block[c_reg].update(pred_through)
288 
289  # If a predecessor has changed
290  if reach_block != irb.cur_reach[0]:
291  irb.cur_reach[0] = reach_block
292  for c_reg in self.ira_regs_ids():
293  if irb.defout[0][c_reg]:
294  # KILL(n) = DEFOUT(n) ? REACH(n)\DEFOUT(n) : EMPTY
295  irb.cur_kill[0][c_reg].update(
296  reach_block[c_reg].difference(irb.defout[0][c_reg]))
297 
298  # Compute reach and kill for block's instructions
299  for i in xrange(1, len(irb.irs)):
300  for c_reg in self.ira_regs_ids():
301  # REACH(n) = U[p in pred] DEFOUT(p) U REACH(p)\KILL(p)
302  pred_through = irb.defout[i - 1][c_reg].union(
303  irb.cur_reach[i - 1][c_reg].difference(
304  irb.cur_kill[i - 1][c_reg]))
305  irb.cur_reach[i][c_reg].update(pred_through)
306  if irb.defout[i][c_reg]:
307  # KILL(n) = DEFOUT(n) ? REACH(n)\DEFOUT(n) : EMPTY
308  irb.cur_kill[i][c_reg].update(
309  irb.cur_reach[i][c_reg].difference(
310  irb.defout[i][c_reg]))

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.ir.analysis.ira.dead_simp (   self) 
This function is used to analyse relation of a * complete function *
This means the blocks under study represent a solid full function graph.

Source : Kennedy, K. (1979). A survey of data flow analysis techniques.
IBM Thomas J. Watson Research Division, page 43

PRE: gen_graph()

Definition at line 343 of file analysis.py.

343 
344  def dead_simp(self):
345  """
346  This function is used to analyse relation of a * complete function *
347  This means the blocks under study represent a solid full function graph.
348 
349  Source : Kennedy, K. (1979). A survey of data flow analysis techniques.
350  IBM Thomas J. Watson Research Division, page 43
351 
352  PRE: gen_graph()
353  """
354  # Update r/w variables for all irblocs
355  self.get_rw(self.ira_regs_ids())
356  # Liveness step
357  self.compute_reach()
358  self.remove_dead_code()
359  # Simplify expressions
360  self.simplify_blocs()

+ Here is the call graph for this function:

def miasm2.ir.analysis.ira.dst_trackback (   self,
  b 
)

Definition at line 40 of file analysis.py.

40 
41  def dst_trackback(self, b):
42  dst = b.dst
43  todo = set([dst])
44  done = set()
45 
46  for irs in reversed(b.irs):
47  if len(todo) == 0:
48  break
49  out = self.sort_dst(todo, done)
50  found = set()
51  follow = set()
52  for i in irs:
53  if not out:
54  break
55  for o in out:
56  if i.dst == o:
57  follow.add(i.src)
58  found.add(o)
59  for o in found:
60  out.remove(o)
61 
62  for o in out:
63  if o not in found:
64  follow.add(o)
65  todo = follow
66 
67  return done

+ Here is the call graph for this function:

def miasm2.ir.analysis.ira.dump_bloc_state (   self,
  irb 
)

Definition at line 249 of file analysis.py.

249 
250  def dump_bloc_state(self, irb):
251  print '*'*80
252  for k, irs in enumerate(irb.irs):
253  for i in xrange(len(irs)):
254  print 5*"-"
255  print 'instr', k, irs[i]
256  print 5*"-"
257  for v in self.ira_regs_ids():
258  if irb.cur_reach[k][v]:
259  print 'REACH[%d][%s]' % (k, v)
260  self.print_set(irb.cur_reach[k][v])
261  if irb.cur_kill[k][v]:
262  print 'KILL[%d][%s]' % (k, v)
263  self.print_set(irb.cur_kill[k][v])
264  if irb.defout[k][v]:
265  print 'DEFOUT[%d][%s]' % (k, v)
266  self.print_set(irb.defout[k][v])

+ Here is the call graph for this function:

def miasm2.ir.analysis.ira.gen_equations (   self)

Definition at line 361 of file analysis.py.

361 
362  def gen_equations(self):
363  for irb in self.blocs.values():
364  symbols_init = {}
365  for r in self.arch.regs.all_regs_ids:
366  x = ExprId(r.name, r.size)
367  x.is_term = True
368  symbols_init[r] = x
369  sb = symbexec(self, dict(symbols_init))
370  sb.emulbloc(irb)
371  eqs = []
372  for n_w in sb.symbols:
373  v = sb.symbols[n_w]
374  if n_w in symbols_init and symbols_init[n_w] == v:
375  continue
376  eqs.append(ExprAff(n_w, v))
377  print '*' * 40
378  print irb
379  irb.irs = [eqs]
380  irb.lines = [None]
def miasm2.ir.analysis.ira.gen_graph (   self,
  link_all = True 
) 
Gen irbloc digraph
@link_all: also gen edges to non present irblocs

Definition at line 68 of file analysis.py.

68 
69  def gen_graph(self, link_all = True):
70  """
71  Gen irbloc digraph
72  @link_all: also gen edges to non present irblocs
73  """
74  self.g = DiGraph()
75  for lbl, b in self.blocs.items():
76  # print 'add', lbl
77  self.g.add_node(lbl)
78  # dst = self.get_bloc_dst(b)
79  dst = self.dst_trackback(b)
80  # print "\tdst", dst
81  for d in dst:
82  if isinstance(d, ExprInt):
83  d = ExprId(
84  self.symbol_pool.getby_offset_create(int(d.arg)))
85  if self.ExprIsLabel(d):
86  if d.name in self.blocs or link_all is True:
87  self.g.add_edge(lbl, d.name)
def miasm2.ir.analysis.ira.graph (   self) 
Output the graphviz script

Definition at line 88 of file analysis.py.

88 
89  def graph(self):
90  """Output the graphviz script"""
91  out = """
92  digraph asm_graph {
93  size="80,50";
94  node [
95  fontsize = "16",
96  shape = "box"
97  ];
98  """
99  all_lbls = {}
100  for lbl in self.g.nodes():
101  if lbl not in self.blocs:
102  continue
103  irb = self.blocs[lbl]
104  ir_txt = [str(lbl)]
105  for irs in irb.irs:
106  for l in irs:
107  ir_txt.append(str(l))
108  ir_txt.append("")
109  ir_txt.append("")
110  all_lbls[hash(lbl)] = "\l\\\n".join(ir_txt)
111  for l, v in all_lbls.items():
112  # print l, v
113  out += '%s [label="%s"];\n' % (l, v)
114 
115  for a, b in self.g.edges():
116  # print 'edge', a, b, hash(a), hash(b)
117  out += '%s -> %s;\n' % (hash(a), hash(b))
118  out += '}'
119  return out
def miasm2.ir.analysis.ira.init_useful_instr (   self) 
Computes a set of triples (block, instruction number, instruction)
containing initially useful instructions :
  - Instructions affecting final value of return registers
  - Instructions affecting IRDst register
  - Instructions writing in memory
  - Function call instructions
Return set of intial useful instructions

Definition at line 140 of file analysis.py.

140 
141  def init_useful_instr(self):
142  """Computes a set of triples (block, instruction number, instruction)
143  containing initially useful instructions :
144  - Instructions affecting final value of return registers
145  - Instructions affecting IRDst register
146  - Instructions writing in memory
147  - Function call instructions
148  Return set of intial useful instructions
149  """
150 
151  useful = set()
152 
153  for node in self.g.nodes():
154  if node not in self.blocs:
155  continue
156 
157  block = self.blocs[node]
158  successors = self.g.successors(node)
159  has_son = bool(successors)
160  for p_son in successors:
161  if p_son not in self.blocs:
162  # Leaf has lost its son: don't remove anything
163  # reaching this block
164  for r in self.ira_regs_ids():
165  useful.update(block.cur_reach[-1][r].union(
166  block.defout[-1][r]))
167 
168  # Function call, memory write or IRDst affectation
169  for k, ir in enumerate(block.irs):
170  for i_cur in ir:
171  if i_cur.src.is_function_call():
172  # /!\ never remove ir calls
173  useful.add((block.label, k, i_cur))
174  if isinstance(i_cur.dst, ExprMem):
175  useful.add((block.label, k, i_cur))
176  useful.update(block.defout[k][self.IRDst])
177 
178  # Affecting return registers
179  if not has_son:
180  for r in self.get_out_regs(block):
181  useful.update(block.defout[-1][r]
182  if block.defout[-1][r] else
183  block.cur_reach[-1][r])
184 
185  return useful

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.ir.analysis.ira.ira_regs_ids (   self) 
Returns ids of all registers used in the IR

Definition at line 19 of file analysis.py.

19 
20  def ira_regs_ids(self):
21  """Returns ids of all registers used in the IR"""
22  return self.arch.regs.all_regs_ids + [self.IRDst]

+ Here is the caller graph for this function:

def miasm2.ir.analysis.ira.print_set (   v_set)
static 
Print each triplet contained in a set
@v_set: set containing triplets elements

Definition at line 242 of file analysis.py.

242 
243  def print_set(v_set):
244  """Print each triplet contained in a set
245  @v_set: set containing triplets elements
246  """
247  for p in v_set:
248  print ' (%s, %s, %s)' % p

+ Here is the caller graph for this function:

def miasm2.ir.analysis.ira.remove_dead_code (   self) 
Remove dead instructions in each block of the graph using the reach
analysis .
Returns True if a block has been modified
PRE : compute_reach(self)

Definition at line 223 of file analysis.py.

223 
224  def remove_dead_code(self):
225  """Remove dead instructions in each block of the graph using the reach
226  analysis .
227  Returns True if a block has been modified
228  PRE : compute_reach(self)
229  """
230  useful = self._mark_useful_code()
231  modified = False
232  for block in self.blocs.values():
233  modified |= self.remove_dead_instr(block, useful)
234  return modified

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.ir.analysis.ira.remove_dead_instr (   self,
  irb,
  useful 
) 
Remove dead affectations using previous reaches analysis
@irb: irbloc instance
@useful: useful statements from previous reach analysis
Return True iff the block state has changed
PRE: compute_reach(self)

Definition at line 120 of file analysis.py.

120 
121  def remove_dead_instr(self, irb, useful):
122  """Remove dead affectations using previous reaches analysis
123  @irb: irbloc instance
124  @useful: useful statements from previous reach analysis
125  Return True iff the block state has changed
126  PRE: compute_reach(self)
127  """
128  modified = False
129  for k, ir in enumerate(irb.irs):
130  j = 0
131  while j < len(ir):
132  cur_instr = ir[j]
133  if (isinstance(cur_instr.dst, ExprId)
134  and (irb.label, k, cur_instr) not in useful):
135  del ir[j]
136  modified = True
137  else:
138  j += 1
139  return modified

+ Here is the caller graph for this function:

def miasm2.ir.analysis.ira.set_dead_regs (   self,
  b 
)

Definition at line 235 of file analysis.py.

235 
236  def set_dead_regs(self, b):
237  pass
def miasm2.ir.analysis.ira.sizeof_char (   self)

Definition at line 381 of file analysis.py.

381 
382  def sizeof_char(self):
383  "Return the size of a char in bits"
384  raise NotImplementedError("Abstract method")
def miasm2.ir.analysis.ira.sizeof_int (   self)

Definition at line 389 of file analysis.py.

389 
390  def sizeof_int(self):
391  "Return the size of an int in bits"
392  raise NotImplementedError("Abstract method")
def miasm2.ir.analysis.ira.sizeof_long (   self)

Definition at line 393 of file analysis.py.

393 
394  def sizeof_long(self):
395  "Return the size of a long in bits"
396  raise NotImplementedError("Abstract method")
def miasm2.ir.analysis.ira.sizeof_pointer (   self)

Definition at line 397 of file analysis.py.

397 
398  def sizeof_pointer(self):
399  "Return the size of a void* in bits"
400  raise NotImplementedError("Abstract method")
def miasm2.ir.analysis.ira.sizeof_short (   self)

Definition at line 385 of file analysis.py.

385 
386  def sizeof_short(self):
387  "Return the size of a short in bits"
388  raise NotImplementedError("Abstract method")
def miasm2.ir.analysis.ira.sort_dst (   self,
  todo,
  done 
)

Definition at line 23 of file analysis.py.

23 
24  def sort_dst(self, todo, done):
25  out = set()
26  while todo:
27  dst = todo.pop()
28  if self.ExprIsLabel(dst):
29  done.add(dst)
30  elif isinstance(dst, ExprMem) or isinstance(dst, ExprInt):
31  done.add(dst)
32  elif isinstance(dst, ExprCond):
33  todo.add(dst.src1)
34  todo.add(dst.src2)
35  elif isinstance(dst, ExprId):
36  out.add(dst)
37  else:
38  done.add(dst)
39  return out

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

Member Data Documentation

miasm2.ir.analysis.ira.g

Definition at line 73 of file analysis.py.

The documentation for this class was generated from the following file:
Generated by   doxygen 1.8.8