42 if isinstance(a[0], m2_expr.ExprInt):
46 sources_int[a[1]] = (m2_expr.ExprInt(int(a[0].arg),
50 elif isinstance(a[0], m2_expr.ExprSlice):
51 if not a[0].arg
in sources:
52 sources[a[0].arg] = []
53 sources[a[0].arg].append(a)
59 if max_size
is None or max_size < a[2]:
65 for x
in sources_int.values():
68 v = x[0].arg & ((1 << (x[2] - x[1])) - 1)
69 x[0] = m2_expr.ExprInt_from(x[0], v)
71 sorted_s.append((x[1], x))
74 start, v = sorted_s.pop()
75 out = [m2_expr.ExprInt(v[0].arg), v[1], v[2]]
78 if sorted_s[-1][1][2] != start:
80 s_start, s_stop = sorted_s[-1][1][1], sorted_s[-1][1][2]
81 size += s_stop - s_start
82 a = m2_expr.mod_size2uint[size](
83 (int(out[0].arg) << (out[1] - s_start)) +
84 int(sorted_s[-1][1][0].arg))
85 out[0] = m2_expr.ExprInt(a)
88 out[0] = m2_expr.ExprInt(int(out[0].arg), size)
89 final_sources.append((start, out))
91 final_sources_int = final_sources
95 for args
in sources.values():
99 sorted_s.append((x[1], x))
102 start, v = sorted_s.pop()
103 ee = v[0].arg[v[0].start:v[0].stop]
106 if sorted_s[-1][1][2] != start:
108 if sorted_s[-1][1][0].stop != out[0].start:
111 start = sorted_s[-1][1][1]
114 o1, o2 = sorted_s[-1][1][0].start, o_e.stop
116 out = o_e, start, o_stop
120 out = out[0], start, out[2]
122 final_sources.append((start, out))
124 simp_sources += final_sources
126 simp_sources += final_sources_int
128 for i, v
in non_slice.items():
129 simp_sources.append((i, v))
132 simp_sources = [x[1]
for x
in simp_sources]
136 op_propag_cst = [
'+',
'*',
'^',
'&',
'|',
'>>',
137 '<<',
"a>>",
">>>",
"<<<",
138 "/",
"%",
'idiv',
'imod',
'umod',
'udiv']
143 return True if expr is only composed with integers
144 /!\ ExprCond returns True is src1 and src2 are integers
147 if isinstance(e, m2_expr.ExprCond):
148 return e.src1 | e.src2
152 if isinstance(e, m2_expr.ExprId)
or isinstance(e, m2_expr.ExprMem):
156 new_e = e.visit(modify_cond)
157 new_e.visit(
lambda x: find_int(x, s))
164 if isinstance(e, m2_expr.ExprInt):
166 if isinstance(e, m2_expr.ExprCond):
167 return (isinstance(e.src1, m2_expr.ExprInt)
and
168 isinstance(e.src2, m2_expr.ExprInt))
188 """Return a list of missing interval in all_interval
189 @all_interval: list of (int, int)
190 @i_min: int, minimal missing interval bound
191 @i_max: int, maximal missing interval bound"""
193 my_intervals = all_intervals[:]
195 my_intervals.append((i_max, i_max))
199 for start, stop
in my_intervals:
200 if last_pos != start:
201 missing_i.append((last_pos, start))
207 """Identify variables in an expression.
209 - variables with their corresponding values
210 - original expression with variables translated
214 is_var_ident =
"is_var_ident"
217 """Set the expression @expr to handle and launch variable identification
220 @var_prefix: (optional) prefix of the variable name, default is 'v'"""
235 for var_id, var_value
in self._vars.iteritems():
239 to_replace = {v_val:v_id
240 for v_id, v_val
in self._vars.iteritems()
242 var_value = var_value.replace_expr(to_replace)
247 self.
_vars[var_id] = var_value
251 self.
_equation = expr.replace_expr({v_val: v_id
for v_id, v_val
252 in self._vars.iteritems()})
256 todo = set(self._vars.iterkeys())
260 for var_id, var_expr
in self._vars.iteritems():
263 needs[var_id] = [var_name
264 for var_name
in var_expr.get_r(mem_read=
True)
266 var_name
in todo
and \
274 for need
in needs[var_id]:
287 for element_done
in done:
288 todo.remove(element_done)
292 "Return True iff @expr is a variable identifier"
293 if not isinstance(expr, m2_expr.ExprId):
296 return hasattr(expr, cls.is_var_ident)
and \
297 getattr(expr, cls.is_var_ident) ==
True
300 """Recursive method called by find_variable to expand @expr.
301 Set @var_names and @var_values.
302 This implementation is faster than an expression visitor because
303 we do not rebuild each expression.
309 if (expr
not in self._vars.values()):
311 identifier = m2_expr.ExprId(
"%s%s" % (self.
var_prefix,
312 self.var_indice.next()),
314 setattr(identifier, self.__class__.is_var_ident,
True)
315 self.
_vars[identifier] = expr
321 self.var_asked.add(expr)
323 if isinstance(expr, m2_expr.ExprOp):
327 elif isinstance(expr, m2_expr.ExprInt):
330 elif isinstance(expr, m2_expr.ExprId):
333 elif isinstance(expr, m2_expr.ExprMem):
336 elif isinstance(expr, m2_expr.ExprCompose):
340 elif isinstance(expr, m2_expr.ExprSlice):
343 elif isinstance(expr, m2_expr.ExprCond):
349 raise NotImplementedError(
"Type not handled: %s" % expr)
360 "Display variables and final equation"
362 for var_id, var_expr
in self.vars.iteritems():
363 out +=
"%s = %s\n" % (var_id, var_expr)
369 """Return an expression randomly generated"""
374 identifier_charset = string.letters
376 number_max = 0xFFFFFFFF
378 operations_by_args_number = {1: [
"-"],
379 2: [
"<<",
"<<<",
">>",
">>>"],
380 "2+": [
"+",
"*",
"&",
"|",
"^"],
383 operations_max_args_number = 5
389 compose_max_layer = 5
391 memory_max_address_size = 32
394 generated_elements = {}
398 """Return a random identifier
399 @size: (optional) identifier size
401 return m2_expr.ExprId(
"".join([random.choice(cls.identifier_charset)
402 for _
in xrange(cls.identifier_len)]),
407 """Return a random number
408 @size: (optional) number max bits
410 num = random.randint(0, cls.number_max % (2**size))
411 return m2_expr.ExprInt(num, size)
415 """Return an atomic Expression
416 @size: (optional) Expr size
418 available_funcs = [cls.identifier, cls.number]
419 return random.choice(available_funcs)(size=size)
424 @size: (optional) Operation size
425 @depth: (optional) Expression depth
427 operand_type = random.choice(cls.operations_by_args_number.keys())
428 if isinstance(operand_type, str)
and "+" in operand_type:
429 number_args = random.randint(int(operand_type[:-1]),
430 cls.operations_max_args_number)
432 number_args = operand_type
434 args = [cls._gen(size=size, depth=depth - 1)
435 for _
in xrange(number_args)]
436 operand = random.choice(cls.operations_by_args_number[operand_type])
437 return m2_expr.ExprOp(operand,
442 """Return an ExprSlice
443 @size: (optional) Operation size
444 @depth: (optional) Expression depth
446 start = random.randint(0, size)
448 return cls._gen(size=random.randint(stop, stop + cls.slice_add_size),
449 depth=depth - 1)[start:stop]
453 """Return an ExprCompose
454 @size: (optional) Operation size
455 @depth: (optional) Expression depth
458 upper_bound = random.randint(1, size)
459 args = [(cls._gen(size=upper_bound, depth=depth - 1), 0, upper_bound)]
462 while (upper_bound < size):
463 if len(args) == (cls.compose_max_layer - 1):
467 upper_bound = random.randint(args[-1][-1] + 1, size)
469 args.append((cls._gen(size=upper_bound - args[-1][-1]),
473 return m2_expr.ExprCompose(args)
478 @size: (optional) Operation size
479 @depth: (optional) Expression depth
482 address_size = random.randint(1, cls.memory_max_address_size)
483 return m2_expr.ExprMem(cls._gen(size=address_size,
488 def _gen(cls, size=32, depth=1):
489 """Internal function for generating sub-expression according to options
490 @size: (optional) Operation size
491 @depth: (optional) Expression depth
492 /!\ @generated_elements is left modified
495 if not cls.perfect_tree:
496 depth = random.randint(max(0, depth - 2), depth)
499 if cls.reuse_element
and random.choice([
True,
False])
and \
500 (depth, size)
in cls.generated_elements:
501 return random.choice(cls.generated_elements[(depth, size)])
505 return cls.atomic(size=size)
508 available_funcs = [cls.operation, cls.slice, cls.compose, cls.memory]
509 gen = random.choice(available_funcs)(size=size, depth=depth)
512 new_value = cls.generated_elements.get((depth, size), []) + [gen]
513 cls.generated_elements[(depth, size)] = new_value
517 def get(cls, size=32, depth=1, clean=True):
518 """Return a randomly generated expression
519 @size: (optional) Operation size
520 @depth: (optional) Expression depth
521 @clean: (optional) Clean expression cache between two calls
525 cls.generated_elements = {}
528 got = cls._gen(size=size, depth=depth)
532 cls.generated_elements = {}
537 return (arg2 - arg1) ^ ((arg2 ^ arg1) & ((arg2 - arg1) ^ arg2))
541 Returns a one bit long Expression:
542 * 1 if @arg1 is strictly greater than @arg2 (unsigned)
549 Returns a one bit long Expression:
550 * 1 if @arg1 is strictly greater than @arg2 (signed)
def is_int_or_cond_src_int