Новый алгоритм
? 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) = ? η-function: lattice(t) = lattice η-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
