waffle/passes/
empty_blocks.rs

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
//! Pass to remove empty blocks.

use crate::entity::EntityRef;
use crate::ir::{Block, BlockTarget, FunctionBody, Terminator};

/// Determines whether a block (i) has no blockparams, and (ii) is
/// solely a jump to another block. We can remove these blocks.
///
/// Why can't we remove blocks that are solely jumps but *do* have
/// blockparams? Because They still serve a purpose in SSA: they
/// define these blockparams as a join of multiple possible other
/// definitions in preds.
fn block_is_empty_jump(body: &FunctionBody, block: Block) -> Option<BlockTarget> {
    // Must be empty except for terminator, and must have no
    // blockparams, and must have an unconditional-branch terminator.
    if body.blocks[block].insts.len() > 0 {
        return None;
    }
    if body.blocks[block].params.len() > 0 {
        return None;
    }
    let target = match &body.blocks[block].terminator {
        &Terminator::Br { ref target } => target,
        _ => return None,
    };

    Some(target.clone())
}

fn rewrite_target(
    forwardings: &[Option<BlockTarget>],
    target: &BlockTarget,
) -> Option<BlockTarget> {
    if target.args.len() > 0 {
        return None;
    }
    forwardings[target.block.index()].clone()
}

pub(crate) fn run(body: &mut FunctionBody) {
    log::trace!(
        "empty_blocks: running on func:\n{}\n",
        body.display_verbose("| ", None)
    );

    // Identify empty blocks, and to where they should forward.
    let forwardings = body
        .blocks
        .iter()
        .map(|block| {
            if block != body.entry {
                block_is_empty_jump(body, block)
            } else {
                None
            }
        })
        .collect::<Vec<_>>();

    // Rewrite every target according to a forwarding (or potentially
    // a chain of composed forwardings).
    for block_data in body.blocks.values_mut() {
        block_data.terminator.update_targets(|target| {
            if let Some(new_target) = rewrite_target(&forwardings[..], target) {
                log::trace!("empty_blocks: replacing {:?} with {:?}", target, new_target);
                *target = new_target;
            }
        });
    }

    // Recompute preds/succs.
    body.recompute_edges();

    log::trace!(
        "empty_blocks: finished:\n{}\n",
        body.display_verbose("| ", None)
    );
}