Method topo_sorted_values

cranelift/codegen/src/egraph/elaborate.rs:222–283

(&self)

    }

    fn topo_sorted_values(&self) -> Vec<Value> {
        #[derive(Debug)]
        enum Event {
            Enter,
            Exit,
        }
        let mut stack = Vec::<(Event, Value)>::new();

        // Traverse the CFG in pre-order so that, when we look at the
        // instructions and operands inside each block, we see value defs before
        // uses.
        for block in crate::traversals::Dfs::new().pre_order_iter(&self.func) {
            for inst in self.func.layout.block_insts(block) {
                stack.extend(self.func.dfg.inst_values(inst).map(|v| (Event::Enter, v)));
            }
        }

        // We pushed in the desired order, so popping would implicitly reverse
        // that. Avoid that by reversing the initial stack before we start
        // traversing the DFG.
        stack.reverse();

        let mut sorted = Vec::with_capacity(self.func.dfg.values().len());
        let mut seen = EntitySet::<Value>::with_capacity(self.func.dfg.values().len());

        // Post-order traversal of the DFG, visiting value defs before uses.
        while let Some((event, value)) = stack.pop() {
            match event {
                Event::Enter => {
                    if seen.insert(value) {
                        stack.push((Event::Exit, value));
                        match self.func.dfg.value_def(value) {
                            ValueDef::Result(inst, _) => {
                                stack.extend(
                                    self.func
                                        .dfg
                                        .inst_values(inst)
                                        .rev()
                                        .filter(|v| !seen.contains(*v))
                                        .map(|v| (Event::Enter, v)),
                                );
                            }
                            ValueDef::Union(a, b) => {
                                if !seen.contains(b) {
                                    stack.push((Event::Enter, b));
                                }
                                if !seen.contains(a) {
                                    stack.push((Event::Enter, a));
                                }
                            }
                            ValueDef::Param(..) => {}
                        }
                    }
                }
                Event::Exit => {
                    sorted.push(value);
                }
            }