min_infmachine_lltk 0.1.0

//! Module provides final transition table (code) optimization routines.

use super::*;

use std::collections::{HashMap, HashSet};

fn remove_unused_instrs<Map, Idx>(
    code: Vec<MinInfInstr>,
    map: Map,
    visited: Vec<bool>,
) -> (Vec<MinInfInstr>, Vec<(Idx, usize)>)
where
    Map: IntoIterator<Item = (Idx, usize)>,
{
    let code_len = code.len();
    // eprintln!("Visited: {:?}", visited);
    // generate translation table
    let trans_table = {
        let mut trans_table = vec![None; code_len];
        let mut count = 0;
        for (i, v) in visited.into_iter().enumerate() {
            if v {
                trans_table[i] = Some(count);
                count += 1;
            }
        }
        trans_table
    };
    // generate new code
    let new_code = code
        .into_iter()
        .enumerate()
        .filter_map(|(i, instr)| {
            if trans_table[i].is_some() {
                Some(MinInfInstr::new(
                    instr.func_fr0,
                    instr.func_fr1,
                    trans_table[instr.next_fr0].unwrap_or_default(),
                    trans_table[instr.next_fr1].unwrap_or_default(),
                ))
            } else {
                None
            }
        })
        .collect::<Vec<_>>();
    // generate new map
    let map = map
        .into_iter()
        .filter_map(|(idx, pos)| {
            if let Some(new_pos) = trans_table.get(pos).unwrap_or(&None) {
                Some((idx, *new_pos))
            } else {
                None
            }
        })
        .collect::<Vec<_>>();
    (new_code, map)
}

// Map in form: (index,state). Returned map in original order of input map.

// Returns new code and new map.

/// Removes paths that will not be visited (dead code) from code.
///
/// Function removes all paths that will not be visited (dead code) from code and returns
/// new code and new map. Map is list of indexed states.
pub fn only_visited_states<Map, Idx>(
    code: Vec<MinInfInstr>,
    start: MinInfPos,
    map: Map,
) -> (Vec<MinInfInstr>, Vec<(Idx, usize)>)
where
    Map: IntoIterator<Item = (Idx, usize)>,
{
    let code_len = code.len();
    let mut visited = vec![false; code_len];
    struct StackEntry {
        pos: usize,
        way: u8,
    }
    let mut stack = vec![StackEntry {
        pos: start.0,
        way: 0,
    }];
    // traverse from start
    while !stack.is_empty() {
        let stack_len = stack.len();
        let top = stack.last_mut().unwrap();
        match top.way {
            0 => {
                if !visited[top.pos] {
                    visited[top.pos] = true;
                } else {
                    stack.pop();
                    continue;
                }
                // if not start then way can be any.
                top.way += 1;
                let pos = top.pos;
                if (stack_len != 1 || is_fr0(start)) && !code[pos].func_fr0.is_stop() {
                    stack.push(StackEntry {
                        pos: code[pos].next_fr0,
                        way: 0,
                    })
                }
            }
            1 => {
                // if not start then way can be any.
                top.way += 1;
                let pos = top.pos;
                if (stack_len != 1 || is_fr1(start)) && !code[pos].func_fr1.is_stop() {
                    stack.push(StackEntry {
                        pos: code[pos].next_fr1,
                        way: 0,
                    })
                }
            }
            _ => {
                stack.pop();
            }
        }
    }
    remove_unused_instrs(code, map, visited)
}

// IMPORTANT: this table MUST BE sorted.
const INSTR_REPLACEMENTS_2_0: [[MinInfFunc; 2]; 2] = [[MINF_MARF, MINF_MAB], [MINF_TBRF, MINF_TBB]];

// two instructions in two func_rets [instr0, instr1_fr0, instr1_fr1]
// IMPORTANT: this table MUST BE sorted.
const INSTR_REPLACEMENTS_2_2_0: [[MinInfFunc; 3]; 3] = [
    [MINF_MR, MINF_MRW0, MINF_MRW1],
    [MINF_MAR, MINF_MARW0, MINF_MARW1],
    [MINF_TBR, MINF_TBRW0, MINF_TBRW1],
];

// two instructions in two func_rets [instr0, instr1_fr0, instr1_fr1] -> [instr]
// const INSTR_REPLACEMENTS_2_2_1: [([MinInfFunc; 3], MinInfFunc); 1] = [
//     ([MINF_MAB, MINF_MAR, MINF_MARF], MINF_MAR),
// ];

// (original chain, replaced chain)
// IMPORTANT: this table MUST BE sorted.
const INSTR_REPLACEMENTS_2_1: [([MinInfFunc; 2], MinInfFunc); 60] = [
    ([MINF_MR, MINF_MARF], MINF_MARF),
    ([MINF_MR, MINF_MR], MINF_MR),
    ([MINF_MR, MINF_MRW0], MINF_MRW0),
    ([MINF_MR, MINF_MRW1], MINF_MRW1),
    ([MINF_MR, MINF_MAB], MINF_MAB),
    ([MINF_MR, MINF_MAR], MINF_MAR),
    ([MINF_MR, MINF_MARW0], MINF_MARW0),
    ([MINF_MR, MINF_MARW1], MINF_MARW1),
    ([MINF_MR, MINF_TBRF], MINF_TBRF),
    ([MINF_MR, MINF_TBR], MINF_TBR),
    ([MINF_MR, MINF_TBRW0], MINF_TBRW0),
    ([MINF_MR, MINF_TBRW1], MINF_TBRW1),
    ([MINF_MR, MINF_TBB], MINF_TBB),
    ([MINF_MR, MINF_STOP3], MINF_STOP3),
    ([MINF_MR, MINF_STOP2], MINF_STOP2),
    ([MINF_MR, MINF_STOP], MINF_STOP),
    ([MINF_MRW0, MINF_MRW0], MINF_MRW0),
    ([MINF_MRW0, MINF_MRW1], MINF_MRW1),
    ([MINF_MRW1, MINF_MRW0], MINF_MRW0),
    ([MINF_MRW1, MINF_MRW1], MINF_MRW1),
    ([MINF_MAR, MINF_MARF], MINF_MARF),
    ([MINF_MAR, MINF_MR], MINF_MR),
    ([MINF_MAR, MINF_MRW0], MINF_MRW0),
    ([MINF_MAR, MINF_MRW1], MINF_MRW1),
    ([MINF_MAR, MINF_MAB], MINF_MAB),
    ([MINF_MAR, MINF_MAR], MINF_MAR),
    ([MINF_MAR, MINF_MARW0], MINF_MARW0),
    ([MINF_MAR, MINF_MARW1], MINF_MARW1),
    ([MINF_MAR, MINF_TBRF], MINF_TBRF),
    ([MINF_MAR, MINF_TBR], MINF_TBR),
    ([MINF_MAR, MINF_TBRW0], MINF_TBRW0),
    ([MINF_MAR, MINF_TBRW1], MINF_TBRW1),
    ([MINF_MAR, MINF_TBB], MINF_TBB),
    ([MINF_MAR, MINF_STOP3], MINF_STOP3),
    ([MINF_MAR, MINF_STOP2], MINF_STOP2),
    ([MINF_MAR, MINF_STOP], MINF_STOP),
    ([MINF_MARW0, MINF_MARW0], MINF_MARW0),
    ([MINF_MARW0, MINF_MARW1], MINF_MARW1),
    ([MINF_MARW1, MINF_MARW0], MINF_MARW0),
    ([MINF_MARW1, MINF_MARW1], MINF_MARW1),
    ([MINF_TBR, MINF_MARF], MINF_MARF),
    ([MINF_TBR, MINF_MR], MINF_MR),
    ([MINF_TBR, MINF_MRW0], MINF_MRW0),
    ([MINF_TBR, MINF_MRW1], MINF_MRW1),
    ([MINF_TBR, MINF_MAB], MINF_MAB),
    ([MINF_TBR, MINF_MAR], MINF_MAR),
    ([MINF_TBR, MINF_MARW0], MINF_MARW0),
    ([MINF_TBR, MINF_MARW1], MINF_MARW1),
    ([MINF_TBR, MINF_TBRF], MINF_TBRF),
    ([MINF_TBR, MINF_TBR], MINF_TBR),
    ([MINF_TBR, MINF_TBRW0], MINF_TBRW0),
    ([MINF_TBR, MINF_TBRW1], MINF_TBRW1),
    ([MINF_TBR, MINF_TBB], MINF_TBB),
    ([MINF_TBR, MINF_STOP3], MINF_STOP3),
    ([MINF_TBR, MINF_STOP2], MINF_STOP2),
    ([MINF_TBR, MINF_STOP], MINF_STOP),
    ([MINF_TBRW0, MINF_TBRW0], MINF_TBRW0),
    ([MINF_TBRW0, MINF_TBRW1], MINF_TBRW1),
    ([MINF_TBRW1, MINF_TBRW0], MINF_TBRW0),
    ([MINF_TBRW1, MINF_TBRW1], MINF_TBRW1),
];

/// Removes code that doesn't impact to next instructions and next results.
///
/// Function removes all instructions that doesn't impact ot next instructions and results.
/// For example: chain [TBR, MARF] can replaced by one MARF, because result of TBR will be ignored.
/// Function returns new optimized code and new map for this code.
/// Map is list of indexed states.
pub fn remove_no_impacts<Map, Idx>(
    mut code: Vec<MinInfInstr>,
    start: MinInfPos,
    map: Map,
) -> (Vec<MinInfInstr>, Vec<(Idx, usize)>)
where
    Map: IntoIterator<Item = (Idx, usize)>,
{
    let code_len = code.len();
    let mut visited = vec![false; code_len];
    // preds_list - predecessors
    let mut preds_list: Vec<Vec<MinInfPos>> = vec![vec![]; code_len];
    struct StackEntry {
        pos: usize,
        way: u8,
    }
    let mut stack = vec![StackEntry {
        pos: start.0,
        way: 0,
    }];
    // traverse from start
    while !stack.is_empty() {
        let stack_len = stack.len();
        let top = stack.last_mut().unwrap();
        match top.way {
            0 => {
                if !visited[top.pos] {
                    visited[top.pos] = true;
                } else {
                    stack.pop();
                    continue;
                }
                // if not start then way can be any.
                top.way += 1;
                let pos = top.pos;
                if (stack_len != 1 || is_fr0(start)) && !code[pos].func_fr0.is_stop() {
                    preds_list[code[pos].next_fr0].push((pos, false));
                    stack.push(StackEntry {
                        pos: code[pos].next_fr0,
                        way: 0,
                    })
                }
            }
            1 => {
                // if not start then way can be any.
                top.way += 1;
                let pos = top.pos;
                if (stack_len != 1 || is_fr1(start)) && !code[pos].func_fr1.is_stop() {
                    preds_list[code[pos].next_fr1].push((pos, true));
                    stack.push(StackEntry {
                        pos: code[pos].next_fr1,
                        way: 0,
                    })
                }
            }
            _ => {
                stack.pop();
            }
        }
    }
    // sort predecessors lists
    for preds in &mut preds_list {
        preds.sort();
    }
    // main algorithm: removing instructions that does impact to next results
    // (MINF_MEMORY_READ, MINF_MEMORY_ADDRESS_READ, MINF_TEMP_BUFFER_READ).
    let mut changes = vec![];
    for (i, (instr, _)) in code
        .iter()
        .zip(visited)
        .enumerate()
        .filter(|(_, (_, vis))| *vis)
    {
        if instr.func_fr0 == instr.func_fr1 && instr.next_fr0 == instr.next_fr1 {
            let pairs = preds_list[i]
                .iter()
                .map(|(pos, fr)| {
                    (
                        (*pos, *fr),
                        [
                            if *fr {
                                code[*pos].func_fr1
                            } else {
                                code[*pos].func_fr0
                            },
                            instr.func_fr0,
                        ],
                    )
                })
                .collect::<Vec<_>>();
            // Scheme: [.....],{FUNC,NEXT} - second must be same for all function returns.
            // pairs in format: (position, pair of functions)

            let mut used_pairs = vec![false; pairs.len()];
            // check if pair to single
            for (ph, (_, first_pair)) in pairs.iter().enumerate() {
                if !used_pairs[ph] {
                    // find replacement
                    if let Ok(idx) =
                        INSTR_REPLACEMENTS_2_1.binary_search_by_key(&first_pair, |(p, _)| p)
                    {
                        let single = INSTR_REPLACEMENTS_2_1[idx].1;
                        // only for pairs
                        for (pi, ((pos, fr), pair)) in pairs.iter().enumerate() {
                            if let Ok(idx) =
                                INSTR_REPLACEMENTS_2_1.binary_search_by_key(&pair, |(p, _)| p)
                            {
                                if !used_pairs[pi] && INSTR_REPLACEMENTS_2_1[idx].1 == single {
                                    changes.push(((*pos, *fr), single, instr.next_fr0));
                                }
                                used_pairs[pi] = true;
                            }
                        }
                    }
                }
            }
            // check if removal of two instructions.
            let preds = &preds_list[i];
            for ((pos2_0, fr2_0), (pos2_1, fr2_1)) in preds.iter().zip(preds.iter().skip(1)) {
                if pos2_0 == pos2_1 && !*fr2_0 && *fr2_1 {
                    for (pos1, fr1) in &preds_list[*pos2_0] {
                        let pair0 = [
                            if *fr1 {
                                code[*pos1].func_fr1
                            } else {
                                code[*pos1].func_fr0
                            },
                            code[*pos2_0].func_fr0,
                        ];
                        let pair1 = [
                            if *fr1 {
                                code[*pos1].func_fr1
                            } else {
                                code[*pos1].func_fr0
                            },
                            code[*pos2_0].func_fr1,
                        ];
                        let pairs = [
                            if *fr1 {
                                code[*pos1].func_fr1
                            } else {
                                code[*pos1].func_fr0
                            },
                            code[*pos2_0].func_fr0,
                            code[*pos2_1].func_fr1,
                        ];
                        if (INSTR_REPLACEMENTS_2_0.binary_search(&pair0).is_ok()
                            && INSTR_REPLACEMENTS_2_0.binary_search(&pair1).is_ok())
                            || INSTR_REPLACEMENTS_2_2_0.binary_search(&pairs).is_ok()
                        {
                            changes.push(((*pos1, *fr1), instr.func_fr0, instr.next_fr0));
                        }
                    }
                }
            }
        }
        // Scheme: [{FUNC0,FUNC1,NEXT},{FUNC,NEXT}],{FUNC0,NEXT0,FUNC1,NEXT1},
        // second can be any, first next must be same for all function returns.
        // NO! Because relacement can be based on result from first function.
    }
    // apply changes
    for ((pos, fr), single, next) in changes {
        if fr {
            code[pos].func_fr1 = single;
            code[pos].next_fr1 = next;
        } else {
            code[pos].func_fr0 = single;
            code[pos].next_fr0 = next;
        }
    }
    only_visited_states(code, start, map)
}

/// Removes code that doesn't impact to next instructions and next results multiple times.
///
/// Function removes all instructions that doesn't impact ot next instructions and results.
/// For example: chain [TBR, MARF] can replaced by one MARF, because result of TBR will be ignored.
/// Function returns new optimized code and new map for this code.
/// This function repeat that optimization at most `iter_count` times.
/// Map is list of indexed states.
pub fn remove_no_impacts_many<Map, Idx>(
    code: Vec<MinInfInstr>,
    start: MinInfPos,
    map: Map,
    iter_count: usize,
) -> (Vec<MinInfInstr>, Vec<(Idx, usize)>)
where
    Idx: Clone,
    Map: IntoIterator<Item = (Idx, usize)>,
{
    let mut code = code.clone();
    let mut map = map
        .into_iter()
        .map(|(x, y)| (Some(x), y))
        .collect::<Vec<_>>();
    let mut start = start;
    for _ in 0..iter_count {
        map.push((None, start.0));
        let (new_code, new_map) = remove_no_impacts(code.clone(), start, map.clone());
        let end = new_code == code;
        code = new_code;
        map = new_map;
        let (idx, start_pos) = map.pop().unwrap();
        assert!(idx.is_none());
        start.0 = start_pos;
        if end {
            break;
        }
    }
    let map = map
        .into_iter()
        .map(|(x, y)| (x.unwrap(), y))
        .collect::<Vec<_>>();
    (code, map)
}

// Deduplicate paths in code.
// Example: Ix - different instruction than Iy.
// P0: I10->I0->I1->I2->I3  -->  P0: I10->I0->I1->I2->I3
// P1: I20->I0->I1-/             P1: I20-/
// Remove path P1.
// Simple algorithm:
// * Use subgraph with given step number.
// * Forward subgraph comparison - start from some state move forward choosing one of subgraph.
//   Paths are equal if any functions in steps are same and final next states are same.
// * BTreeMap for subgraphs. Comparison is lexicographical (first is major).
// * While joining subgraphs: remove duplicate and join start to first copy.
// * Loop detection: by checking visited states. Compare loops as subgraphs:
//   Use translation states to isolated subgraph state counting.
// * Remove duplications in loops: distance between first start end second start is minimal
//   loop length. Loop will be  confirmed if second end will be first start.
//   Then only keep first minimal states of loop.
// * Multiloop duplications: use maximal (for all loops) minimal loop length.
// * Use BTreeMap to sort subgraphs (or vector):
//   Entry: key - subgraph for state (node), value - (state, map).

// Subgraph key structure:
// Subgraph is traversed by Depth first search. Structure is subgraph in code array and
// final nexts. Final next can be non-exists if stop encountered.
// Subgraph: [[instr0,.......,instr1],[final_nexts]]. Any next above code array length is
// refers to final next: FINAL_NEXT = ARRAY_LEN + ORIG_NEXT. -
//     ORIG_NEXT - next state in original code. ARRAY_LEN - subgraph code length.
//
// Loop deduplication:
// For given number of subgraph entries:
//    for all subgraphs:
//        map end of some subgraphs in same place to start of other subgraphs in same place.
//    same place - same place for all subgraphs.
//    if mapping done then replace ends by one value for all subgraphs.
// Some special for loops: multiple entries and returns to subgraphs that creates loop.
//    other entries are other nodes in subgraph. start can be one.
// Simpler algorithm:
//     traverse by n subgraphs and if joins with start of first reduce loop.

// Returns subgraph code
fn dfs_subgraph_key(
    code: &[MinInfInstr],
    start: usize,
    depth: usize,
) -> (Vec<MinInfInstr>, Vec<(usize, usize)>) {
    let mut trans_map = HashMap::<usize, usize>::new();
    let mut subgraph_code = vec![];
    let mut visited = HashSet::new();
    let mut paths = vec![start];
    let mut next_paths = vec![];
    // traverse in depth first search
    for i in 0..depth {
        for (j, pos) in paths.drain(..).enumerate() {
            if !visited.contains(&pos) {
                trans_map.insert(pos, subgraph_code.len());
                // push with original state positions.
                subgraph_code.push(code[pos]);
                visited.insert(pos);
                if i + 1 < depth {
                    if !code[pos].func_fr0.is_stop() {
                        next_paths.push((code[pos].next_fr0, (j << 1)));
                    }
                    if !code[pos].func_fr1.is_stop() {
                        next_paths.push((code[pos].next_fr1, (j << 1) + 1));
                    }
                }
            }
        }
        // sort nexts
        next_paths.sort_by_key(|k| k.0);
        next_paths.dedup_by_key(|k| k.0);
        // sort back to original order
        next_paths.sort_by_key(|k| k.1);
        paths = next_paths.drain(..).map(|k| k.0).collect::<Vec<_>>();
    }
    // translate nexts in code
    for instr in &mut subgraph_code {
        if !instr.func_fr0.is_stop() {
            if let Some(next) = trans_map.get(&instr.next_fr0) {
                instr.next_fr0 = *next;
            } else {
                instr.next_fr0 |= DFS_EXT_ADD;
            }
        } else {
            // if stop then make to ignore it
            instr.next_fr0 = 0;
        }
        if !instr.func_fr1.is_stop() {
            if let Some(next) = trans_map.get(&instr.next_fr1) {
                instr.next_fr1 = *next;
            } else {
                instr.next_fr1 |= DFS_EXT_ADD;
            }
        } else {
            // if stop then make to ignore it
            instr.next_fr1 = 0;
        }
    }
    let mut rev_trans_map = trans_map
        .into_iter()
        .map(|(k, v)| (v, k))
        .collect::<Vec<_>>();
    rev_trans_map.sort_by_key(|(k, _)| *k);
    // return subgraph and
    // map: key - state in subgraph, value - state in main code
    (subgraph_code, rev_trans_map)
}

fn apply_inter_trans_map<Map, Idx>(
    code: Vec<MinInfInstr>,
    map: Map,
    mut inter_trans_map: Vec<Option<usize>>,
) -> (Vec<MinInfInstr>, Vec<(Idx, usize)>)
where
    Map: IntoIterator<Item = (Idx, usize)>,
{
    let code_len = code.len();
    // resolve inter_trans_map
    for i in 0..code_len {
        let v = inter_trans_map[i];
        if let Some(v) = v {
            let mut p = v;
            let mut list = vec![i];
            while let Some(next) = inter_trans_map[p] {
                list.push(p);
                p = next;
            }
            for s in list {
                inter_trans_map[s] = Some(p);
            }
        }
    }
    // resolve inter_trans_map
    for i in 0..code_len {
        let v = inter_trans_map[i];
        if let Some(v) = v {
            let mut p = v;
            let mut list = vec![i];
            while let Some(next) = inter_trans_map[p] {
                list.push(p);
                p = next;
            }
            for s in list {
                inter_trans_map[s] = Some(p);
            }
        }
    }
    // translate states in code.
    let new_code = code
        .into_iter()
        .map(|instr| {
            MinInfInstr::new(
                instr.func_fr0,
                instr.func_fr1,
                inter_trans_map[instr.next_fr0].unwrap_or(instr.next_fr0),
                inter_trans_map[instr.next_fr1].unwrap_or(instr.next_fr1),
            )
        })
        .collect::<Vec<_>>();
    let map = map
        .into_iter()
        .map(|(idx, pos)| (idx, inter_trans_map[pos].unwrap_or(pos)))
        .collect::<Vec<_>>();
    (new_code, map)
}

fn join_subgraphs(
    used_states: &mut [bool],
    trans_map: &[(usize, usize)],
    trans_map2: &[(usize, usize)],
    inter_trans_map: &mut [Option<usize>],
) {
    let required_states = HashSet::<usize>::from_iter(trans_map.iter().map(|(_, v)| *v));
    // remove states from second subgraph
    for v in trans_map2.iter().map(|(_, v)| *v) {
        if !required_states.contains(&v) {
            used_states[v] = false;
        }
    }
    // update inter trans
    for (v, v2) in trans_map
        .into_iter()
        .map(|(_, v)| v)
        .zip(trans_map2.into_iter().map(|(_, v)| v))
    {
        if !required_states.contains(v2) && inter_trans_map[*v2].is_none() {
            inter_trans_map[*v2] = Some(*v);
        }
    }
}

/// Deduplicates subgraphs (paths) in code.
///
/// Functions deduplicates subgraphs (paths) in code. Deduplicated subgraphs are direct acyclic
/// graphs (subgraphs without loops). Maximal depth (length of paths in subgraphs) is `max_depth`.
/// The `sort_depth` defines subgraph of depth that will be sorted.
/// `sort_depth` should be smaller than `max_depth`. Default value of `max_depth` is 24 and
/// default value of `sort_depth` is 6. Function returns deduplicated code and map to this code.
/// Map is list of indexed states.
pub fn dedup_subgraphs<Map, Idx>(
    code: Vec<MinInfInstr>,
    map: Map,
    max_depth: Option<usize>,
    sort_depth: Option<usize>,
) -> (Vec<MinInfInstr>, Vec<(Idx, usize)>)
where
    Map: IntoIterator<Item = (Idx, usize)>,
{
    // println!("DEDUP_SUBGRAPHS");
    if let Some(max_depth) = max_depth {
        assert_ne!(max_depth, 0);
    }
    if let Some(sort_depth) = sort_depth {
        assert_ne!(sort_depth, 0);
    }
    let code_len = code.len();
    assert!(code_len <= DFS_EXT_ADD);
    let max_depth = max_depth.unwrap_or(std::cmp::min(24, code_len));
    let sort_depth = sort_depth.unwrap_or(std::cmp::min(6, code_len));
    // println!("IterCode: {:?}", code);
    let code_len = code.len();
    let mut subgraph_list = (0..code_len)
        .map(|pos| {
            let (key, v) = dfs_subgraph_key(&code, pos, sort_depth);
            (key, Some((pos, v)))
        })
        .collect::<Vec<_>>();
    subgraph_list.sort_by_key(|k| k.0.clone());
    // inter trans - translation (from removed to used)
    let mut inter_trans_map = vec![None; code_len];
    // used states
    let mut used_states = vec![true; code_len];
    // compare and join.
    let subgraph_list_len = subgraph_list.len();
    for depth in 1..=max_depth {
        // println!("Depth: {}", depth);
        for idx in 0..subgraph_list_len {
            let (_, pos_v_opt) = &subgraph_list[idx];
            if let Some((pos, _)) = pos_v_opt {
                // println!("DDD: {} {:?}", depth, pos_v_opt);
                let (subgraph, trans) = dfs_subgraph_key(&code, *pos, depth);
                let mut count = 0;
                for idx2 in idx + 1..subgraph_list_len {
                    let (_, pos2_v2_opt) = &subgraph_list[idx2];
                    // println!("DDD2: {} {:?} {:?}", depth, pos_v_opt, pos2_v2_opt);
                    if let Some((pos2, _)) = pos2_v2_opt {
                        let (subgraph2, trans2) = dfs_subgraph_key(&code, *pos2, depth);
                        if subgraph == subgraph2 {
                            // println!(
                            //     "Subgraph join: {} {}: {:?} {:?} {}",
                            //     *pos, *pos2, subgraph, subgraph2, depth
                            // );
                            // println!("Subgraph join: {} {}:  {}", *pos, *pos2, depth);
                            join_subgraphs(&mut used_states, &trans, &trans2, &mut inter_trans_map);
                        } else {
                            // println!(
                            //     "Subgraph NOT join: {} {}: {:?} {:?} {}",
                            //     *pos, *pos2, subgraph, subgraph2, depth
                            // );
                            if count >= 5 {
                                break;
                            }
                            count += 1;
                        }
                    }
                }
            }
        }
    }
    let (new_code, map) = apply_inter_trans_map(code, map, inter_trans_map);
    remove_unused_instrs(new_code, map, used_states)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_dfs_subgraph_key() {
        let code0 = vec![
            MinInfInstr::new(MINF_MARF, MINF_MR, 2, 0),
            MinInfInstr::new(MINF_MRW0, MINF_MRW1, 0, 3),
            MinInfInstr::new(MINF_MAB, MINF_MAR, 0, 2),
            MinInfInstr::new(MINF_MARW0, MINF_MARW1, 4, 5),
            MinInfInstr::new(MINF_TBRF, MINF_TBR, 6, 7),
            MinInfInstr::new(MINF_TBRW0, MINF_TBRW1, 8, 9),
            MinInfInstr::new(MINF_MARF, MINF_STOP2, 6, 1),
            MinInfInstr::new(MINF_STOP3, MINF_MRW1, 0, 7),
            MinInfInstr::new(MINF_MAB, MINF_STOP2, 8, 1),
            MinInfInstr::new(MINF_STOP, MINF_STOP, 4, 5),
        ];
        assert_eq!(
            (
                vec![MinInfInstr::new(MINF_MARF, MINF_MR, 2 | DFS_EXT_ADD, 0)],
                vec![(0, 0)],
            ),
            dfs_subgraph_key(&code0, 0, 1)
        );
        assert_eq!(
            (
                vec![
                    MinInfInstr::new(MINF_MARF, MINF_MR, 1, 0),
                    MinInfInstr::new(MINF_MAB, MINF_MAR, 0, 1)
                ],
                vec![(0, 0), (1, 2)],
            ),
            dfs_subgraph_key(&code0, 0, 2)
        );
        assert_eq!(
            (
                vec![
                    MinInfInstr::new(MINF_MARF, MINF_MR, 1, 0),
                    MinInfInstr::new(MINF_MAB, MINF_MAR, 0, 1)
                ],
                vec![(0, 0), (1, 2)],
            ),
            dfs_subgraph_key(&code0, 0, 5)
        );
        assert_eq!(
            (
                vec![
                    MinInfInstr::new(MINF_MRW0, MINF_MRW1, 1, 2),
                    MinInfInstr::new(MINF_MARF, MINF_MR, 3, 1),
                    MinInfInstr::new(MINF_MARW0, MINF_MARW1, 4, 5),
                    MinInfInstr::new(MINF_MAB, MINF_MAR, 1, 3),
                    MinInfInstr::new(MINF_TBRF, MINF_TBR, DFS_EXT_ADD | 6, DFS_EXT_ADD | 7),
                    MinInfInstr::new(MINF_TBRW0, MINF_TBRW1, DFS_EXT_ADD | 8, DFS_EXT_ADD | 9),
                ],
                vec![(0, 1), (1, 0), (2, 3), (3, 2), (4, 4), (5, 5)],
            ),
            dfs_subgraph_key(&code0, 1, 3)
        );
        assert_eq!(
            (
                vec![
                    MinInfInstr::new(MINF_MRW0, MINF_MRW1, 1, 2),
                    MinInfInstr::new(MINF_MARF, MINF_MR, 3, 1),
                    MinInfInstr::new(MINF_MARW0, MINF_MARW1, 4, 5),
                    MinInfInstr::new(MINF_MAB, MINF_MAR, 1, 3),
                    MinInfInstr::new(MINF_TBRF, MINF_TBR, 6, 7),
                    MinInfInstr::new(MINF_TBRW0, MINF_TBRW1, 8, 9),
                    MinInfInstr::new(MINF_MARF, MINF_STOP2, 6, 0),
                    MinInfInstr::new(MINF_STOP3, MINF_MRW1, 0, 7),
                    MinInfInstr::new(MINF_MAB, MINF_STOP2, 8, 0),
                    MinInfInstr::new(MINF_STOP, MINF_STOP, 0, 0),
                ],
                vec![
                    (0, 1),
                    (1, 0),
                    (2, 3),
                    (3, 2),
                    (4, 4),
                    (5, 5),
                    (6, 6),
                    (7, 7),
                    (8, 8),
                    (9, 9)
                ],
            ),
            dfs_subgraph_key(&code0, 1, 4)
        );
        let code0 = vec![
            MinInfInstr::new(MINF_MARF, MINF_MR, 2, 0),
            MinInfInstr::new(MINF_MRW0, MINF_MRW1, 0, 3),
            MinInfInstr::new(MINF_MAB, MINF_MAR, 0, 2),
            MinInfInstr::new(MINF_MARW0, MINF_MARW1, 4, 5),
            MinInfInstr::new(MINF_TBRF, MINF_TBR, 6, 9),
            MinInfInstr::new(MINF_TBRW0, MINF_TBRW1, 7, 8),
            MinInfInstr::new(MINF_MARF, MINF_STOP2, 6, 1),
            MinInfInstr::new(MINF_STOP3, MINF_MRW1, 0, 7),
            MinInfInstr::new(MINF_MAB, MINF_STOP2, 8, 1),
            MinInfInstr::new(MINF_STOP, MINF_STOP, 4, 5),
        ];
        assert_eq!(
            (
                vec![
                    MinInfInstr::new(MINF_MRW0, MINF_MRW1, 1, 2),
                    MinInfInstr::new(MINF_MARF, MINF_MR, 3, 1),
                    MinInfInstr::new(MINF_MARW0, MINF_MARW1, 4, 5),
                    MinInfInstr::new(MINF_MAB, MINF_MAR, 1, 3),
                    MinInfInstr::new(MINF_TBRF, MINF_TBR, 6, 7),
                    MinInfInstr::new(MINF_TBRW0, MINF_TBRW1, 8, 9),
                    MinInfInstr::new(MINF_MARF, MINF_STOP2, 6, 0),
                    MinInfInstr::new(MINF_STOP, MINF_STOP, 0, 0),
                    MinInfInstr::new(MINF_STOP3, MINF_MRW1, 0, 8),
                    MinInfInstr::new(MINF_MAB, MINF_STOP2, 9, 0),
                ],
                vec![
                    (0, 1),
                    (1, 0),
                    (2, 3),
                    (3, 2),
                    (4, 4),
                    (5, 5),
                    (6, 6),
                    (7, 9),
                    (8, 7),
                    (9, 8)
                ],
            ),
            dfs_subgraph_key(&code0, 1, 4)
        );
    }

    #[test]
    fn test_mininf_instr_equal_by_inner_states() {
        assert!(
            MinInfInstr::new(MINF_MAB, MINF_TBB, 3, 6)
                .equal_by_inner_states(&MinInfInstr::new(MINF_MAB, MINF_TBB, 3, 6))
        );
        assert!(
            !MinInfInstr::new(MINF_MAB, MINF_TBB, 3, 6)
                .equal_by_inner_states(&MinInfInstr::new(MINF_MAB, MINF_TBB, 3, 7))
        );
        assert!(
            !MinInfInstr::new(MINF_MAB, MINF_TBB, 3, 6)
                .equal_by_inner_states(&MinInfInstr::new(MINF_MAB, MINF_TBB, 4, 6))
        );
        assert!(
            !MinInfInstr::new(MINF_MAB, MINF_TBB, 3, 6)
                .equal_by_inner_states(&MinInfInstr::new(MINF_MAB, MINF_TBRF, 3, 6))
        );
        assert!(
            !MinInfInstr::new(MINF_MAB, MINF_TBB, 3, 6)
                .equal_by_inner_states(&MinInfInstr::new(MINF_MAR, MINF_TBB, 3, 6))
        );

        assert!(
            MinInfInstr::new(MINF_MAB, MINF_TBB, DFS_EXT_ADD + 3, 6)
                .equal_by_inner_states(&MinInfInstr::new(MINF_MAB, MINF_TBB, DFS_EXT_ADD + 3, 6))
        );
        assert!(
            MinInfInstr::new(MINF_MAB, MINF_TBB, DFS_EXT_ADD + 3, 6)
                .equal_by_inner_states(&MinInfInstr::new(MINF_MAB, MINF_TBB, DFS_EXT_ADD + 5, 6))
        );
        assert!(
            !MinInfInstr::new(MINF_MAB, MINF_TBB, DFS_EXT_ADD + 3, 6)
                .equal_by_inner_states(&MinInfInstr::new(MINF_MAB, MINF_TBB, 3, 6))
        );
        assert!(
            !MinInfInstr::new(MINF_MAB, MINF_TBB, 3, 6).equal_by_inner_states(&MinInfInstr::new(
                MINF_MAB,
                MINF_TBB,
                DFS_EXT_ADD + 3,
                6
            ))
        );

        assert!(
            MinInfInstr::new(MINF_MAB, MINF_TBB, 6, DFS_EXT_ADD + 3)
                .equal_by_inner_states(&MinInfInstr::new(MINF_MAB, MINF_TBB, 6, DFS_EXT_ADD + 3))
        );
        assert!(
            MinInfInstr::new(MINF_MAB, MINF_TBB, 6, DFS_EXT_ADD + 3)
                .equal_by_inner_states(&MinInfInstr::new(MINF_MAB, MINF_TBB, 6, DFS_EXT_ADD + 9))
        );
        assert!(
            !MinInfInstr::new(MINF_MAB, MINF_TBB, 6, DFS_EXT_ADD + 3)
                .equal_by_inner_states(&MinInfInstr::new(MINF_MAB, MINF_TBB, 6, 3))
        );
        assert!(
            !MinInfInstr::new(MINF_MAB, MINF_TBB, 6, 3).equal_by_inner_states(&MinInfInstr::new(
                MINF_MAB,
                MINF_TBB,
                6,
                DFS_EXT_ADD + 3
            ))
        );
    }
}