sway_ir/analysis/
call_graph.rs

1/// Build call graphs for the program being compiled.
2/// If a function F1 calls function F2, then the call
3/// graph has an edge F1->F2.
4use crate::{Context, Function, InstOp, Instruction, ValueDatum};
5
6use indexmap::IndexSet;
7use sway_types::{FxIndexMap, FxIndexSet};
8
9pub type CallGraph = FxIndexMap<Function, FxIndexSet<Function>>;
10
11/// Build call graph considering all providing functions.
12pub fn build_call_graph(ctx: &Context, functions: &[Function]) -> CallGraph {
13    let mut res = CallGraph::default();
14    for function in functions {
15        let entry = res.entry(*function);
16        let entry = entry.or_insert_with(IndexSet::default);
17        for (_, inst) in function.instruction_iter(ctx) {
18            if let ValueDatum::Instruction(Instruction {
19                op: InstOp::Call(callee, _),
20                ..
21            }) = ctx.values[inst.0].value
22            {
23                entry.insert(callee);
24            }
25        }
26    }
27    res
28}
29
30/// Given a call graph, return reverse topological sort
31/// (post order traversal), i.e., If A calls B, then B
32/// occurs before A in the returned Vec.
33pub fn callee_first_order(cg: &CallGraph) -> Vec<Function> {
34    let mut res = Vec::new();
35
36    let mut visited = FxIndexSet::<Function>::default();
37    fn post_order_visitor(
38        cg: &CallGraph,
39        visited: &mut FxIndexSet<Function>,
40        res: &mut Vec<Function>,
41        node: Function,
42    ) {
43        if visited.contains(&node) {
44            return;
45        }
46        visited.insert(node);
47        for callee in &cg[&node] {
48            post_order_visitor(cg, visited, res, *callee);
49        }
50        res.push(node);
51    }
52    for node in cg.keys() {
53        post_order_visitor(cg, &mut visited, &mut res, *node);
54    }
55
56    res
57}
sway_ir/analysis/call_graph.rs

sway_ir/analysis/
call_graph.rs
