Алгоритмы, структуры данных

       

Новый алгоритм


? t ? tuples lattice(t) = T unvisited(t) = true

Visit all basic blocks B in the program Visit all tuples t within B propagate(t)

propagate (tuple t) if not unvisited(t) return unvisited(t) = false label restart:

if ssa_link(t) ? 0 then ssa_link(t) lattice(t) = lattice(t) П lattice(ssa_link(t)) endif if type(t) ? arithmetic operation

propagate(left(t)) propagate(right(t)) endif

case on type (t) constant C: lattice(t) = C arithmetic or logic operation: if type(left(t)) = ?-function or (type(right(t)) = ?-function then if type(left(t)) = ?-function and (type(right(t)) = ?-function or type(ssa_link(right(t))) = ?-function) and (predicate(left(t)) = predicate(right(t)) or type(ssa_link(left(t))) = ?-function) then join_common_predicate(t) goto restart else join_gamma_with_operand(t) goto restart endif else propagate(left(t)) propagate(right(t)) endif

if all operands have constant lattice value then lattice(t) = arithmetic result of lattice values of operands else lattice(t) = ? endif store: lattice(t) = lattice(RHS) ?-function: lattice(t) = lattice(left(t))П lattice(right(t)) ?-function: propagate(predicate(t)) if lattice(predicate(t)) = C then lattice(t) = lattice value of ?-argument corresponding to C else lattice(t) = lattice(left(t)) П lattice(right(t)) endif ?-function: lattice(t) = ? &#951-function: lattice(t) = lattice &#951-argument) default: lattice(t) = ? end case end propagate

Функция join_common_predicate – объединяет две ?-функции с одинаковыми предикатами в одну

join_common_predicate (tuple t) tuple new_t = new ?-function predicate(new_t) = predicate(left(t))

left(new_t) = new operation node, same as t ssa_link(left(new_t)) = 0 unvisited(left(new_t)) = true lattice(left(new_t)) = T left(left(new_t)) = left(left(t)) right(left(new_t)) = right(left(t))

right(new_t) = new operation node, same as t ssa_link(right(new_t)) = 0 unvisited(right(new_t)) = true lattice(right(new_t)) = T left(right(new_t)) = left(right(t)) right(right(new_t)) = right(right(t))

t = new_t ssa_link(t) = 0 lattice(t) = T end join_common_predicate

Функция join_gamma_with_operand – объединяет ?-функцию и операнд, который не является ?-функцией join_gamma_with_operand (tuple t) tuple g, op tuple g_left = new operation node, same as t tuple g_right = new operation node, same as t if type(left(t)) = ?-function then g = left(t)   op = right(t)   left(g_left) = left(g)   left(g_right) = right(g)   right(g_left) = op   right(g_right) = op else   op = left(t)   g = right(t)   left(g_left) = op   left(g_right) = op   right(g_left) = left(g)   right(g_right) = right(g) endif left(g) = g_left right(g) = g_right t = g

unvisited(g_left) = true lattice(g_left) = T ssa_link(g_left) = 0

unvisited(g_right) = true lattice(g_right) = T ssa_link(g_right) = 0 end join_gamma_with_operand



Содержание раздела