wasm2usharp/pass/
recursive.rs

1use std::collections::HashSet;
2
3use crate::ir::{
4    code::{Call, Inst, InstId},
5    module::Module,
6};
7
8use cranelift_entity::PrimaryMap;
9use petgraph::{algo::tarjan_scc, graph::Graph};
10
11/// 関数のコールグラフがサイクルを含むか判定し、
12/// 含むなら関数のrecursiveをtrue、含まないならfalseにする
13pub fn recursive(module: &mut Module<'_>) {
14    // 関数呼び出しに対応するグラフ
15    let mut graph = Graph::<(), ()>::new();
16
17    // 関数をノードとして追加
18    let nodes = (0..module.all_funcs.len())
19        .map(|_| graph.add_node(()))
20        .collect::<Vec<_>>();
21
22    // 関数呼び出しに対応するエッジを追加
23    for (i_caller, caller) in module.all_funcs.iter_mut().enumerate() {
24        if let Some(code) = &mut caller.code {
25            iterate_call(&mut code.insts, |call| {
26                graph.add_edge(nodes[i_caller], nodes[call.func], ());
27            });
28        }
29    }
30
31    // 強連結成分を求める
32    let scc = tarjan_scc(&graph);
33
34    for nodes in scc {
35        let nodes_set: HashSet<usize> = HashSet::from_iter(nodes.iter().map(|x| x.index()));
36        for node in nodes {
37            if let Some(code) = &mut module.all_funcs[node.index()].code {
38                iterate_call(&mut code.insts, |call| {
39                    if nodes_set.contains(&call.func) {
40                        // 同じ強連結成分に含まれる関数の呼び出しをrecursiveとする
41                        call.recursive = true;
42                    }
43                });
44            }
45        }
46    }
47}
48
49fn iterate_call(tree: &mut PrimaryMap<InstId, Inst>, mut f: impl FnMut(&mut Call)) {
50    for (_, inst) in tree.iter_mut() {
51        if let Some(call) = &mut inst.call {
52            f(call);
53        }
54    }
55}