vicis-core 0.2.1

Manipulate LLVM-IR in Pure Rust
Documentation 
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

// Sparse Conditional Constant Propagation

use crate::ir::{
    function::{
        basic_block::BasicBlockId,
        instruction::{Br, Instruction, Opcode, Operand},
        Function,
    },
    value::{ConstantData, Value},
};
use std::collections::VecDeque;

pub struct SCCP<'a> {
    func: &'a mut Function,
}

impl<'a> SCCP<'a> {
    pub fn new(func: &'a mut Function) -> Self {
        Self { func }
    }

    pub fn run(&mut self) {
        let mut foldable = VecDeque::new();
        let mut foldable_condbr = VecDeque::new();
        let mut changed = false;

        for block_id in self.func.layout.block_iter() {
            for inst_id in self.func.layout.inst_iter(block_id) {
                let inst = self.func.data.inst_ref(inst_id);

                if self.is_foldable(inst) {
                    foldable.push_back(inst_id);
                }

                if self.is_foldable_condbr(inst) {
                    foldable_condbr.push_back(inst_id);
                }
            }
        }

        while let Some(inst_id) = foldable_condbr.pop_front() {
            let condbr = &self.func.data.inst_ref(inst_id);
            let block = condbr.parent;
            let condbr = condbr.operand.as_condbr().unwrap();
            let [dst, not_dst] = condbr.blocks as [BasicBlockId; 2];
            // Create a new Br instruction to replace CondBr with.
            let br = Opcode::Br
                .with_block(block)
                .with_operand(Operand::Br(Br { block: dst }));
            let br = self.func.data.create_inst(br);
            // Append Br and remove CondBr
            self.func.layout.append_inst(br, block);
            self.func.remove_inst(inst_id);
            // Remove successor and predecessor from blocks properly
            self.func.data.remove_block_succ(block, not_dst);
            self.func.data.remove_block_pred(not_dst, block);
            changed |= true;
        }

        if changed {
            self.fold_phi();
        }

        while let Some(inst_id) = foldable.pop_front() {
            let inst = &self.func.data.inst_ref(inst_id);
            let folded = match inst.fold_consts(&self.func.data) {
                Some(folded) => folded,
                None => continue,
            };
            let folded = self.func.data.create_value(Value::Constant(folded));
            self.func.data.replace_all_uses(inst_id, folded);
            self.func.remove_inst(inst_id);
            changed |= true;
        }

        if changed {
            self.run()
        }
    }

    fn is_foldable(&self, inst: &Instruction) -> bool {
        matches!(
            inst.opcode,
            Opcode::Add | Opcode::Sub | Opcode::Mul | Opcode::ICmp | Opcode::Zext
        ) && inst
            .operand
            .args()
            .iter()
            .map(|arg| self.func.data.value_ref(*arg))
            .all(|arg| matches!(arg, Value::Constant(ConstantData::Int(_))))
    }

    fn is_foldable_condbr(&self, inst: &Instruction) -> bool {
        matches!(inst.opcode, Opcode::CondBr)
            && inst
                .operand
                .args()
                .iter()
                .map(|arg| self.func.data.value_ref(*arg))
                .all(|arg| matches!(arg, Value::Constant(ConstantData::Int(_))))
    }

    fn fold_phi(&mut self) {
        let mut remove_list = vec![];

        for block_id in self.func.layout.block_iter() {
            for inst_id in self.func.layout.inst_iter(block_id) {
                let inst = self.func.data.inst_ref(inst_id);

                if inst.opcode != Opcode::Phi {
                    continue;
                }

                let phi = inst;
                let phi = phi.operand.as_phi().unwrap();

                // TODO: Now very limited case supported
                let mut arg = None;
                let phi_has_single_valid_arg = phi.blocks.iter().zip(phi.args.iter()).fold(
                    0usize,
                    |acc, (&block_id, &arg_id)| {
                        let not_empty = !self.func.data.basic_blocks[block_id].preds().is_empty();
                        if not_empty {
                            arg = Some(arg_id);
                        }
                        acc + not_empty as usize
                    },
                ) == 1;

                if !phi_has_single_valid_arg {
                    continue;
                }

                self.func.data.replace_all_uses(inst_id, arg.unwrap());
                remove_list.push(inst_id)
            }
        }

        for id in remove_list {
            self.func.remove_inst(id);
        }
    }
}