1 //! Unreachable code elimination.
2 
3 use cranelift_entity::EntitySet;
4 
5 use crate::cursor::{Cursor, FuncCursor};
6 use crate::dominator_tree::DominatorTree;
7 use crate::flowgraph::ControlFlowGraph;
8 use crate::timing;
9 use crate::{ir, trace};
10 
11 /// Eliminate unreachable code.
12 ///
13 /// This pass deletes whole blocks that can't be reached from the entry block. It does not delete
14 /// individual instructions whose results are unused.
15 ///
16 /// The reachability analysis is performed by the dominator tree analysis.
17 pub fn eliminate_unreachable_code(
18     func: &mut ir::Function,
19     cfg: &mut ControlFlowGraph,
20     domtree: &DominatorTree,
21 ) {
22     let _tt = timing::unreachable_code();
23     let mut pos = FuncCursor::new(func);
24     let mut used_tables = EntitySet::with_capacity(pos.func.stencil.dfg.jump_tables.len());
25     while let Some(block) = pos.next_block() {
26         if domtree.is_reachable(block) {
27             let inst = pos.func.layout.last_inst(block).unwrap();
28             if let ir::InstructionData::BranchTable { table, .. } = pos.func.dfg.insts[inst] {
29                 used_tables.insert(table);
30             }
31             continue;
32         }
33 
34         trace!("Eliminating unreachable {}", block);
35         // Move the cursor out of the way and make sure the next lop iteration goes to the right
36         // block.
37         pos.prev_block();
38 
39         // Remove all instructions from `block`.
40         while let Some(inst) = pos.func.layout.first_inst(block) {
41             trace!(" - {}", pos.func.dfg.display_inst(inst));
42             pos.func.layout.remove_inst(inst);
43         }
44 
45         // Once the block is completely empty, we can update the CFG which removes it from any
46         // predecessor lists.
47         cfg.recompute_block(pos.func, block);
48 
49         // Finally, remove the block from the layout.
50         pos.func.layout.remove_block(block);
51     }
52 
53     for (table, jt_data) in func.stencil.dfg.jump_tables.iter_mut() {
54         if !used_tables.contains(table) {
55             jt_data.clear();
56         }
57     }
58 }
59