1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

/// Build call graphs for the program being compiled.
/// If a function F1 calls function F2, then the call
/// graph has an edge F1->F2.
use crate::{Context, Function, Instruction, ValueDatum};

use rustc_hash::{FxHashMap, FxHashSet};

pub type CallGraph = FxHashMap<Function, FxHashSet<Function>>;

/// Build call graph considering all providing functions.
pub fn build_call_graph(ctx: &Context, functions: &[Function]) -> CallGraph {
    let mut res = CallGraph::default();
    for function in functions {
        let entry = res.entry(*function);
        let entry = entry.or_insert_with(FxHashSet::default);
        for (_, inst) in function.instruction_iter(ctx) {
            if let ValueDatum::Instruction(Instruction::Call(callee, _)) = ctx.values[inst.0].value
            {
                entry.insert(callee);
            }
        }
    }
    res
}

/// Given a call graph, return reverse topological sort
/// (post order traversal), i.e., If A calls B, then B
/// occurs before A in the returned Vec.
pub fn callee_first_order(cg: &CallGraph) -> Vec<Function> {
    let mut res = Vec::new();

    let mut visited = FxHashSet::<Function>::default();
    fn post_order_visitor(
        cg: &CallGraph,
        visited: &mut FxHashSet<Function>,
        res: &mut Vec<Function>,
        node: Function,
    ) {
        if visited.contains(&node) {
            return;
        }
        visited.insert(node);
        for callee in &cg[&node] {
            post_order_visitor(cg, visited, res, *callee);
        }
        res.push(node);
    }
    for node in cg.keys() {
        post_order_visitor(cg, &mut visited, &mut res, *node);
    }

    res
}