Miasm2
miasm2.expression.simplifications_common Namespace Reference

## Functions

def simp_cst_propagation

def simp_cond_op_int

def simp_cond_factor

def simp_slice

def simp_compose

def simp_cond

## Function Documentation

 def miasm2.expression.simplifications_common.simp_compose ( e_s, e )

Definition at line 498 of file simplifications_common.py.

499 def simp_compose(e_s, e):
500  "Commons simplification on ExprCompose"
501  args = merge_sliceto_slice(e.args)
502  out = []
503  # compose of compose
504  for a in args:
505  if isinstance(a[0], ExprCompose):
506  for x, start, stop in a[0].args:
507  out.append((x, start + a[1], stop + a[1]))
508  else:
509  out.append(a)
510  args = out
511  # Compose(a) with a.size = compose.size => a
512  if len(args) == 1 and args[0][1] == 0 and args[0][2] == e.size:
513  return args[0][0]
514
515  # {(X[z:], 0, X.size-z), (0, X.size-z, X.size)} => (X >> z)
516  if (len(args) == 2 and
517  isinstance(args[1][0], ExprInt) and
518  args[1][0].arg == 0):
519  a1 = args[0]
520  a2 = args[1]
521  if (isinstance(a1[0], ExprSlice) and
522  a1[1] == 0 and
523  a1[0].stop == a1[0].arg.size and
524  a2[1] == a1[0].size and
525  a2[2] == a1[0].arg.size):
526  new_e = a1[0].arg >> ExprInt(
527  a1[0].start, a1[0].arg.size)
528  return new_e
529
530  # Compose with ExprCond with integers for src1/src2 and intergers =>
531  # propagage integers
532  # {XXX?(0x0,0x1)?(0x0,0x1),0,8, 0x0,8,32} => XXX?(int1, int2)
533
534  ok = True
535  expr_cond = None
536  expr_ints = []
537  for i, a in enumerate(args):
538  if not is_int_or_cond_src_int(a[0]):
539  ok = False
540  break
541  expr_ints.append(a)
542  if isinstance(a[0], ExprCond):
543  if expr_cond is not None:
544  ok = False
545  expr_cond = i
546  cond = a[0]
547
548  if ok and expr_cond is not None:
549  src1 = []
550  src2 = []
551  for i, a in enumerate(expr_ints):
552  if i == expr_cond:
553  src1.append((a[0].src1, a[1], a[2]))
554  src2.append((a[0].src2, a[1], a[2]))
555  else:
556  src1.append(a)
557  src2.append(a)
558  src1 = e_s.apply_simp(ExprCompose(src1))
559  src2 = e_s.apply_simp(ExprCompose(src2))
560  if isinstance(src1, ExprInt) and isinstance(src2, ExprInt):
561  return ExprCond(cond.cond, src1, src2)
562  return ExprCompose(args)
563

Here is the call graph for this function:

 def miasm2.expression.simplifications_common.simp_cond ( e_s, e )

Definition at line 564 of file simplifications_common.py.

565 def simp_cond(e_s, e):
566  "Common simplifications on ExprCond"
567  # eval exprcond src1/src2 with satifiable/unsatisfiable condition
568  # propagation
569  if (not isinstance(e.cond, ExprInt)) and e.cond.size == 1:
570  src1 = e.src1.replace_expr({e.cond: ExprInt1(1)})
571  src2 = e.src2.replace_expr({e.cond: ExprInt1(0)})
572  if src1 != e.src1 or src2 != e.src2:
573  return ExprCond(e.cond, src1, src2)
574
575  # -A ? B:C => A ? B:C
576  if (isinstance(e.cond, ExprOp) and
577  e.cond.op == '-' and
578  len(e.cond.args) == 1):
579  e = ExprCond(e.cond.args[0], e.src1, e.src2)
580  # a?x:x
581  elif e.src1 == e.src2:
582  e = e.src1
583  # int ? A:B => A or B
584  elif isinstance(e.cond, ExprInt):
585  if e.cond.arg == 0:
586  e = e.src2
587  else:
588  e = e.src1
589  # a?(a?b:c):x => a?b:x
590  elif isinstance(e.src1, ExprCond) and e.cond == e.src1.cond:
591  e = ExprCond(e.cond, e.src1.src1, e.src2)
592  # a?x:(a?b:c) => a?x:c
593  elif isinstance(e.src2, ExprCond) and e.cond == e.src2.cond:
594  e = ExprCond(e.cond, e.src1, e.src2.src2)
595  # a|int ? b:c => b with int != 0
596  elif (isinstance(e.cond, ExprOp) and
597  e.cond.op == '|' and
598  isinstance(e.cond.args[1], ExprInt) and
599  e.cond.args[1].arg != 0):
600  return e.src1
601
602  # (C?int1:int2)?(A:B) =>
603  elif (isinstance(e.cond, ExprCond) and
604  isinstance(e.cond.src1, ExprInt) and
605  isinstance(e.cond.src2, ExprInt)):
606  int1 = e.cond.src1.arg.arg
607  int2 = e.cond.src2.arg.arg
608  if int1 and int2:
609  e = e.src1
610  elif int1 == 0 and int2 == 0:
611  e = e.src2
612  elif int1 == 0 and int2:
613  e = ExprCond(e.cond.cond, e.src2, e.src1)
614  elif int1 and int2 == 0:
615  e = ExprCond(e.cond.cond, e.src1, e.src2)
616  return e

Here is the call graph for this function:

 def miasm2.expression.simplifications_common.simp_cond_factor ( e_s, e )

Definition at line 358 of file simplifications_common.py.

359 def simp_cond_factor(e_s, e):
360  "Merge similar conditions"
361  if not e.op in ["+", "|", "^", "&", "*", '<<', '>>', 'a>>']:
362  return e
363  if len(e.args) < 2:
364  return e
365  conds = {}
366  not_conds = []
367  multi_cond = False
368  for a in e.args:
369  if not isinstance(a, ExprCond):
370  not_conds.append(a)
371  continue
372  c = a.cond
373  if not c in conds:
374  conds[c] = []
375  else:
376  multi_cond = True
377  conds[c].append(a)
378  if not multi_cond:
379  return e
380  c_out = not_conds[:]
381  for c, vals in conds.items():
382  new_src1 = [x.src1 for x in vals]
383  new_src2 = [x.src2 for x in vals]
384  src1 = e_s.expr_simp_wrapper(ExprOp(e.op, *new_src1))
385  src2 = e_s.expr_simp_wrapper(ExprOp(e.op, *new_src2))
386  c_out.append(ExprCond(c, src1, src2))
387
388  if len(c_out) == 1:
389  new_e = c_out[0]
390  else:
391  new_e = ExprOp(e.op, *c_out)
392  return new_e
393
 def miasm2.expression.simplifications_common.simp_cond_op_int ( e_s, e )

Definition at line 332 of file simplifications_common.py.

333 def simp_cond_op_int(e_s, e):
334  "Extract conditions from operations"
335
336  if not e.op in ["+", "|", "^", "&", "*", '<<', '>>', 'a>>']:
337  return e
338  if len(e.args) < 2:
339  return e
340  if not isinstance(e.args[-1], ExprInt):
341  return e
342  a_int = e.args[-1]
343  conds = []
344  for a in e.args[:-1]:
345  if not isinstance(a, ExprCond):
346  return e
347  conds.append(a)
348  if not conds:
349  return e
350  c = conds.pop()
351  c = ExprCond(c.cond,
352  ExprOp(e.op, c.src1, a_int),
353  ExprOp(e.op, c.src2, a_int))
354  conds.append(c)
355  new_e = ExprOp(e.op, *conds)
356  return new_e
357
 def miasm2.expression.simplifications_common.simp_cst_propagation ( e_s, e )
```This passe includes:
- Constant folding
- Common logical identities
- Common binary identities```

Definition at line 10 of file simplifications_common.py.

11 def simp_cst_propagation(e_s, e):
12  """This passe includes:
13  - Constant folding
14  - Common logical identities
15  - Common binary identities
16  """
17
18  # merge associatif op
19  args = list(e.args)
20  op = e.op
21  # simpl integer manip
22  # int OP int => int
23  # TODO: <<< >>> << >> are architecture dependant
24  if op in op_propag_cst:
25  while (len(args) >= 2 and
26  isinstance(args[-1], ExprInt) and
27  isinstance(args[-2], ExprInt)):
28  i2 = args.pop()
29  i1 = args.pop()
30  if op == '+':
31  o = i1.arg + i2.arg
32  elif op == '*':
33  o = i1.arg * i2.arg
34  elif op == '^':
35  o = i1.arg ^ i2.arg
36  elif op == '&':
37  o = i1.arg & i2.arg
38  elif op == '|':
39  o = i1.arg | i2.arg
40  elif op == '>>':
41  o = i1.arg >> i2.arg
42  elif op == '<<':
43  o = i1.arg << i2.arg
44  elif op == 'a>>':
45  x1 = mod_size2int[i1.arg.size](i1.arg)
46  x2 = mod_size2int[i2.arg.size](i2.arg)
47  o = mod_size2uint[i1.arg.size](x1 >> x2)
48  elif op == '>>>':
49  rounds = i2.arg
50  o = i1.arg >> i2.arg | i1.arg << (i1.size - i2.arg)
51  elif op == '<<<':
52  o = i1.arg << i2.arg | i1.arg >> (i1.size - i2.arg)
53  elif op == '/':
54  o = i1.arg / i2.arg
55  elif op == '%':
56  o = i1.arg % i2.arg
57  elif op == 'idiv':
58  assert(i2.arg.arg)
59  x1 = mod_size2int[i1.arg.size](i1.arg)
60  x2 = mod_size2int[i2.arg.size](i2.arg)
61  o = mod_size2uint[i1.arg.size](x1 / x2)
62  elif op == 'imod':
63  assert(i2.arg.arg)
64  x1 = mod_size2int[i1.arg.size](i1.arg)
65  x2 = mod_size2int[i2.arg.size](i2.arg)
66  o = mod_size2uint[i1.arg.size](x1 % x2)
67  elif op == 'umod':
68  assert(i2.arg.arg)
69  x1 = mod_size2uint[i1.arg.size](i1.arg)
70  x2 = mod_size2uint[i2.arg.size](i2.arg)
71  o = mod_size2uint[i1.arg.size](x1 % x2)
72  elif op == 'udiv':
73  assert(i2.arg.arg)
74  x1 = mod_size2uint[i1.arg.size](i1.arg)
75  x2 = mod_size2uint[i2.arg.size](i2.arg)
76  o = mod_size2uint[i1.arg.size](x1 / x2)
77
78
79
80  o = ExprInt(o, i1.size)
81  args.append(o)
82
83  # bsf(int) => int
84  if op == "bsf" and isinstance(args[0], ExprInt) and args[0].arg != 0:
85  i = 0
86  while args[0].arg & (1 << i) == 0:
87  i += 1
88  return ExprInt_from(args[0], i)
89
90  # bsr(int) => int
91  if op == "bsr" and isinstance(args[0], ExprInt) and args[0].arg != 0:
92  i = args[0].size - 1
93  while args[0].arg & (1 << i) == 0:
94  i -= 1
95  return ExprInt_from(args[0], i)
96
97  # -(-(A)) => A
98  if op == '-' and len(args) == 1 and isinstance(args[0], ExprOp) and \
99  args[0].op == '-' and len(args[0].args) == 1:
100  return args[0].args[0]
101
102  # -(int) => -int
103  if op == '-' and len(args) == 1 and isinstance(args[0], ExprInt):
104  return ExprInt(-args[0].arg)
105  # A op 0 =>A
106  if op in ['+', '|', "^", "<<", ">>", "<<<", ">>>"] and len(args) > 1:
107  if isinstance(args[-1], ExprInt) and args[-1].arg == 0:
108  args.pop()
109  # A - 0 =>A
110  if op == '-' and len(args) > 1 and args[-1].arg == 0:
111  assert(len(args) == 2) # Op '-' with more than 2 args: SantityCheckError
112  return args[0]
113
114  # A * 1 =>A
115  if op == "*" and len(args) > 1:
116  if isinstance(args[-1], ExprInt) and args[-1].arg == 1:
117  args.pop()
118
119  # for cannon form
120  # A * -1 => - A
121  if op == "*" and len(args) > 1:
122  if (isinstance(args[-1], ExprInt) and
123  args[-1].arg == (1 << args[-1].size) - 1):
124  args.pop()
125  args[-1] = - args[-1]
126
127  # op A => A
128  if op in ['+', '*', '^', '&', '|', '>>', '<<',
129  'a>>', '<<<', '>>>', 'idiv', 'imod', 'umod', 'udiv'] and len(args) == 1:
130  return args[0]
131
132  # A-B => A + (-B)
133  if op == '-' and len(args) > 1:
134  if len(args) > 2:
135  raise ValueError(
136  'sanity check fail on expr -: should have one or 2 args ' +
137  '%r %s' % (e, e))
138  return ExprOp('+', args[0], -args[1])
139
140  # A op 0 => 0
141  if op in ['&', "*"] and isinstance(args[1], ExprInt) and args[1].arg == 0:
142  return ExprInt_from(e, 0)
143
144  # - (A + B +...) => -A + -B + -C
145  if (op == '-' and
146  len(args) == 1 and
147  isinstance(args[0], ExprOp) and
148  args[0].op == '+'):
149  args = [-a for a in args[0].args]
150  e = ExprOp('+', *args)
151  return e
152
153  # -(a?int1:int2) => (a?-int1:-int2)
154  if (op == '-' and
155  len(args) == 1 and
156  isinstance(args[0], ExprCond) and
157  isinstance(args[0].src1, ExprInt) and
158  isinstance(args[0].src2, ExprInt)):
159  i1 = args[0].src1
160  i2 = args[0].src2
161  i1 = ExprInt_from(i1, -i1.arg)
162  i2 = ExprInt_from(i2, -i2.arg)
163  return ExprCond(args[0].cond, i1, i2)
164
165  i = 0
166  while i < len(args) - 1:
167  j = i + 1
168  while j < len(args):
169  # A ^ A => 0
170  if op == '^' and args[i] == args[j]:
171  args[i] = ExprInt_from(args[i], 0)
172  del(args[j])
173  continue
174  # A + (- A) => 0
175  if op == '+' and isinstance(args[j], ExprOp) and args[j].op == "-":
176  if len(args[j].args) == 1 and args[i] == args[j].args[0]:
177  args[i] = ExprInt_from(args[i], 0)
178  del(args[j])
179  continue
180  # (- A) + A => 0
181  if op == '+' and isinstance(args[i], ExprOp) and args[i].op == "-":
182  if len(args[i].args) == 1 and args[j] == args[i].args[0]:
183  args[i] = ExprInt_from(args[i], 0)
184  del(args[j])
185  continue
186  # A | A => A
187  if op == '|' and args[i] == args[j]:
188  del(args[j])
189  continue
190  # A & A => A
191  if op == '&' and args[i] == args[j]:
192  del(args[j])
193  continue
194  j += 1
195  i += 1
196
197  if op in ['|', '&', '%', '/'] and len(args) == 1:
198  return args[0]
199
200  # A <<< A.size => A
201  if (op in ['<<<', '>>>'] and
202  isinstance(args[1], ExprInt) and
203  args[1].arg == args[0].size):
204  return args[0]
205
206  # A <<< X <<< Y => A <<< (X+Y) (ou <<< >>>)
207  if (op in ['<<<', '>>>'] and
208  isinstance(args[0], ExprOp) and
209  args[0].op in ['<<<', '>>>']):
210  op1 = op
211  op2 = args[0].op
212  if op1 == op2:
213  op = op1
214  args1 = args[0].args[1] + args[1]
215  else:
216  op = op2
217  args1 = args[0].args[1] - args[1]
218
219  args0 = args[0].args[0]
220  args = [args0, args1]
221
222  # A >> X >> Y => A >> (X+Y)
223  if (op in ['<<', '>>'] and
224  isinstance(args[0], ExprOp) and
225  args[0].op == op):
226  args = [args[0].args[0], args[0].args[1] + args[1]]
227
229  if op == "&" and args[-1] == e.mask:
230  return ExprOp('&', *args[:-1])
231
233  if op == "|" and args[-1] == e.mask:
234  return args[-1]
235
236  # ! (!X + int) => X - int
237  # TODO
238
239  # ((A & mask) >> shift) whith mask < 2**shift => 0
240  if (op == ">>" and
241  isinstance(args[1], ExprInt) and
242  isinstance(args[0], ExprOp) and args[0].op == "&"):
243  if (isinstance(args[0].args[1], ExprInt) and
244  2 ** args[1].arg > args[0].args[1].arg):
245  return ExprInt_from(args[0], 0)
246
247  # parity(int) => int
248  if op == 'parity' and isinstance(args[0], ExprInt):
249  return ExprInt1(parity(args[0].arg))
250
251  # (-a) * b * (-c) * (-d) => (-a) * b * c * d
252  if op == "*" and len(args) > 1:
253  new_args = []
254  counter = 0
255  for a in args:
256  if isinstance(a, ExprOp) and a.op == '-' and len(a.args) == 1:
257  new_args.append(a.args[0])
258  counter += 1
259  else:
260  new_args.append(a)
261  if counter % 2:
262  return -ExprOp(op, *new_args)
263  args = new_args
264
265  # A << int with A ExprCompose => move index
266  if op == "<<" and isinstance(args[0], ExprCompose) and isinstance(args[1], ExprInt):
267  final_size = args[0].size
268  shift = int(args[1].arg)
269  new_args = []
270  # shift indexes
271  for expr, start, stop in args[0].args:
272  new_args.append((expr, start+shift, stop+shift))
273  # filter out expression
274  filter_args = []
275  min_index = final_size
276  for expr, start, stop in new_args:
277  if start >= final_size:
278  continue
279  if stop > final_size:
280  expr = expr[:expr.size - (stop - final_size)]
281  stop = final_size
282  filter_args.append((expr, start, stop))
283  min_index = min(start, min_index)
284  # create entry 0
285  expr = ExprInt(0, min_index)
286  filter_args = [(expr, 0, min_index)] + filter_args
287  return ExprCompose(filter_args)
288
289  # A >> int with A ExprCompose => move index
290  if op == ">>" and isinstance(args[0], ExprCompose) and isinstance(args[1], ExprInt):
291  final_size = args[0].size
292  shift = int(args[1].arg)
293  new_args = []
294  # shift indexes
295  for expr, start, stop in args[0].args:
296  new_args.append((expr, start-shift, stop-shift))
297  # filter out expression
298  filter_args = []
299  max_index = 0
300  for expr, start, stop in new_args:
301  if stop <= 0:
302  continue
303  if start < 0:
304  expr = expr[-start:]
305  start = 0
306  filter_args.append((expr, start, stop))
307  max_index = max(stop, max_index)
308  # create entry 0
309  expr = ExprInt(0, final_size - max_index)
310  filter_args += [(expr, max_index, final_size)]
311  return ExprCompose(filter_args)
312
313
314  # Compose(a) OP Compose(b) with a/b same bounds => Compose(a OP b)
315  if op in ['|', '&', '^'] and all([isinstance(arg, ExprCompose) for arg in args]):
316  bounds = set()
317  for arg in args:
318  bound = tuple([(start, stop) for (expr, start, stop) in arg.args])
320  if len(bounds) == 1:
321  bound = list(bounds)[0]
322  new_args = [[expr] for (expr, start, stop) in args[0].args]
323  for sub_arg in args[1:]:
324  for i, (expr, start, stop) in enumerate(sub_arg.args):
325  new_args[i].append(expr)
326  for i, arg in enumerate(new_args):
327  new_args[i] = ExprOp(op, *arg), bound[i][0], bound[i][1]
328  return ExprCompose(new_args)
329
330  return ExprOp(op, *args)
331

Here is the call graph for this function:

 def miasm2.expression.simplifications_common.simp_slice ( e_s, e )

Definition at line 394 of file simplifications_common.py.

395 def simp_slice(e_s, e):
396  "Slice optimization"
397
398  # slice(A, 0, a.size) => A
399  if e.start == 0 and e.stop == e.arg.size:
400  return e.arg
401  # Slice(int) => int
402  elif isinstance(e.arg, ExprInt):
403  total_bit = e.stop - e.start
404  mask = (1 << (e.stop - e.start)) - 1
405  return ExprInt(int((e.arg.arg >> e.start) & mask), total_bit)
406  # Slice(Slice(A, x), y) => Slice(A, z)
407  elif isinstance(e.arg, ExprSlice):
408  if e.stop - e.start > e.arg.stop - e.arg.start:
409  raise ValueError('slice in slice: getting more val', str(e))
410
411  new_e = ExprSlice(e.arg.arg, e.start + e.arg.start,
412  e.start + e.arg.start + (e.stop - e.start))
413  return new_e
414  elif isinstance(e.arg, ExprCompose):
415  # Slice(Compose(A), x) => Slice(A, y)
416  for a in e.arg.args:
417  if a[1] <= e.start and a[2] >= e.stop:
418  new_e = a[0][e.start - a[1]:e.stop - a[1]]
419  return new_e
420  # Slice(Compose(A, B, C), x) => Compose(A, B, C) with truncated A/B/C
421  out = []
422  for arg, s_start, s_stop in e.arg.args:
423  # arg is before slice start
424  if e.start >= s_stop:
425  continue
426  # arg is after slice stop
427  elif e.stop <= s_start:
428  continue
429  # arg is fully included in slice
430  elif e.start <= s_start and s_stop <= e.stop:
431  out.append((arg, s_start - e.start, s_stop - e.start))
432  continue
433  # arg is truncated at start
434  if e.start > s_start:
435  slice_start = e.start - s_start
436  a_start = 0
437  else:
438  # arg is not truncated at start
439  slice_start = 0
440  a_start = s_start - e.start
441  # a is truncated at stop
442  if e.stop < s_stop:
443  slice_stop = arg.size + e.stop - s_stop - slice_start
444  a_stop = e.stop - e.start
445  else:
446  slice_stop = arg.size
447  a_stop = s_stop - e.start
448  out.append((arg[slice_start:slice_stop], a_start, a_stop))
449  return ExprCompose(out)
450
451  # ExprMem(x, size)[:A] => ExprMem(x, a)
452  # XXXX todo hum, is it safe?
453  elif (isinstance(e.arg, ExprMem) and
454  e.start == 0 and
455  e.arg.size > e.stop and e.stop % 8 == 0):
456  e = ExprMem(e.arg.arg, size=e.stop)
457  return e
458  # distributivity of slice and &
459  # (a & int)[x:y] => 0 if int[x:y] == 0
460  elif (isinstance(e.arg, ExprOp) and
461  e.arg.op == "&" and
462  isinstance(e.arg.args[-1], ExprInt)):
463  tmp = e_s.expr_simp_wrapper(e.arg.args[-1][e.start:e.stop])
464  if isinstance(tmp, ExprInt) and tmp.arg == 0:
465  return tmp
466  # distributivity of slice and exprcond
467  # (a?int1:int2)[x:y] => (a?int1[x:y]:int2[x:y])
468  elif (isinstance(e.arg, ExprCond) and
469  isinstance(e.arg.src1, ExprInt) and
470  isinstance(e.arg.src2, ExprInt)):
471  src1 = e.arg.src1[e.start:e.stop]
472  src2 = e.arg.src2[e.start:e.stop]
473  e = ExprCond(e.arg.cond, src1, src2)
474
475  # (a * int)[0:y] => (a[0:y] * int[0:y])
476  elif (e.start == 0 and isinstance(e.arg, ExprOp) and
477  e.arg.op == "*" and isinstance(e.arg.args[-1], ExprInt)):
478  args = [e_s.expr_simp_wrapper(a[e.start:e.stop]) for a in e.arg.args]
479  e = ExprOp(e.arg.op, *args)
480
481  # (a >> int)[x:y] => a[x+int:y+int] with int+y <= a.size
482  # (a << int)[x:y] => a[x-int:y-int] with x-int >= 0
483  elif (isinstance(e.arg, ExprOp) and e.arg.op in [">>", "<<"] and
484  isinstance(e.arg.args[1], ExprInt)):
485  arg, shift = e.arg.args
486  shift = int(shift.arg)
487  if e.arg.op == ">>":
488  if shift + e.stop <= arg.size:
489  return arg[e.start + shift:e.stop + shift]
490  elif e.arg.op == "<<":
491  if e.start - shift >= 0:
492  return arg[e.start - shift:e.stop - shift]
493  else: