let rec kill (b : (blabel * block) set) : (blabel * ide) set = match b with
    [] -> []
    | (l, BSkip)::b -> union (kill b) [l, " "]
    | (l, BAssignVar(n, _))::b -> union (kill b) [l, n]
    | (l, BAssignArray(n, _, _))::b -> union (kill b) [l, n]
    | (l, _)::b -> union (kill b) [l, " "];;

let rec var_list e = match e with
    N _ -> []
    | Val n -> [n]
    | ArrayVal(n, _) -> [n]
    | Add(e1, e2) -> var_list e1 @ var_list e2
    | Sub(e1, e2) -> var_list e1 @ var_list e2
    | Mul(e1, e2) -> var_list e1 @ var_list e2
    | Eq(e1, e2) -> var_list e1 @ var_list e2
    | Lt(e1, e2) -> var_list e1 @ var_list e2
    | Not(e') -> var_list e'
    | And(e1, e2) -> var_list e1 @ var_list e2
    | Or(e1, e2) -> var_list e1 @ var_list e2;;

let rec gen (b : (blabel * block) set) : (blabel * (ide set)) set = match b with
    [] -> []
    | (l, BSkip)::b -> union (gen b) [l, []]
    | (l, BAssignVar(_, e))::b -> union (gen b) [l, var_list e]
    | (l, BAssignArray(_, _, e))::b -> union (gen b) [l, var_list e]
    | (l, BGuard e)::b -> union (gen b) [l, var_list e];;

let rec flow_rev_get_l (l : blabel) (f : (blabel * blabel) set) : blabel =
    match f with
        [] -> ""
        | (l'', l')::f ->
            if l = l' then l'' else flow_rev_get_l l f;;

let rec get_block (l : blabel) (b : (blabel * block) set) : block = match b with
    [] -> raise NotFound
    | (l', b')::b -> if l = l' then b' else get_block l b;;

let rec search_and_destroy n l = match l with
    [] -> []
    | e::l -> if n = e then search_and_destroy n l else [e] @ search_and_destroy n l;;

let rec get_vars (l : blabel) (k : (blabel * 'a) set) : ide set = match k with
    [] -> []
    | (l', n)::k -> if l = l' then n else get_vars l k;;

let rec exit (l : blabel) (s : s) : ide set =
    if member l (final s)
    then []
    else
        let l' = flow_rev_get_l l (flow_rev s) in
        entry l' s
and entry (l : blabel) (s : s) : ide set =
    let bl = (l, get_block l (blocks s)) in
    let sub = search_and_destroy (List.hd (get_vars l (kill [bl]))) [l, (exit l)] in
    sub @ gen [bl];;

let test =
    ImpProg(Dseq(Var "x", Dseq(Var "y", Var "z")),
    Cseq(AssignVar("x", N 2), Cseq(AssignVar("y", N 4),
    Cseq(AssignVar("x", N 1), Cseq(If(Lt(Val "x", Val "y"), AssignVar("z", Val "y"),
    AssignVar("z", Mul(Val "y", Val "y"))), AssignVar("x", Val "z"))))));;

let test' = labeledprog test;;

(* Write a function lv: cfg -> (blabel -> ide set), which computes the live variables analysis on the given control flow graph.
Hint. The analysis for array assignments can be arbitrarily imprecise, e.g. you can consider live an array if any of its elements is used. *)
let lv (cfg:cfg) (l: blabel) : ide set = match cfg with
    (l1, l2) -> ;;