dce.rs

use hercules_ir::def_use::*;
use hercules_ir::ir::*;

use crate::*;

/*
 * Top level function to run dead code elimination.
 */
pub fn dce(editor: &mut FunctionEditor) {
    // Create worklist (starts as all nodes).
    let mut worklist: Vec<NodeID> = editor.node_ids().collect();

    while let Some(work) = worklist.pop() {
        // If a node on the worklist is a start node, it is either *the* start
        // node (which we shouldn't delete), or is a gravestone for an already
        // deleted node earlier in the worklist. If a node is a return node, it
        // shouldn't be removed.
        if editor.func().nodes[work.idx()].is_start() || editor.func().nodes[work.idx()].is_return()
        {
            continue;
        }

        // If a node on the worklist has 0 users, delete it. Add its uses onto
        // the worklist.
        if editor.get_users(work).len() == 0 {
            let uses = get_uses(&editor.func().nodes[work.idx()]);
            let success = editor.edit(|edit| edit.delete_node(work));
            if success {
                // If the edit was performed, then its uses may now be dead.
                for u in uses.as_ref() {
                    worklist.push(*u);
                }
            }
        }
    }
}