souper_ir/
stringify.rs

1//! Emitting Souper IR's text format.
2
3use crate::ast;
4use id_arena::{Arena, Id};
5use std::{
6    collections::HashSet,
7    fmt::{self, Display},
8};
9
10/// Like `std::fmt::Display`, but with an arena of `ast::Statement`s as context.
11trait DisplayWithContext {
12    fn display(&self, statements: &Arena<ast::Statement>, f: &mut fmt::Formatter) -> fmt::Result;
13}
14
15fn topo_sort_statements(
16    stmts: &Arena<ast::Statement>,
17    seen: &mut HashSet<Id<ast::Statement>>,
18    root: Id<ast::Statement>,
19) -> Vec<Id<ast::Statement>> {
20    let mut seq = vec![];
21
22    let mut stack = vec![Entry::Trace(root)];
23    while let Some(entry) = stack.pop() {
24        let id = match entry {
25            Entry::Finished(id) => {
26                seq.push(id);
27                continue;
28            }
29            Entry::Trace(id) if seen.contains(&id) => continue,
30            Entry::Trace(id) => {
31                seen.insert(id);
32                id
33            }
34        };
35
36        stack.push(Entry::Finished(id));
37
38        match &stmts[id] {
39            ast::Statement::Pc(ast::Pc { x, y }) => {
40                if let ast::Operand::Value(v) = *y {
41                    stack.push(Entry::Trace(v.into()));
42                }
43                if let ast::Operand::Value(v) = *x {
44                    stack.push(Entry::Trace(v.into()));
45                }
46            }
47            ast::Statement::BlockPc(ast::BlockPc {
48                block,
49                predecessor: _,
50                x,
51                y,
52            }) => {
53                if let ast::Operand::Value(v) = *y {
54                    stack.push(Entry::Trace(v.into()));
55                }
56                if let ast::Operand::Value(v) = *x {
57                    stack.push(Entry::Trace(v.into()));
58                }
59                stack.push(Entry::Trace((*block).into()));
60            }
61            ast::Statement::Assignment(ast::Assignment { value, .. }) => match value {
62                | ast::AssignmentRhs::Var
63                | ast::AssignmentRhs::Block(_)
64                | ast::AssignmentRhs::ReservedInst
65                | ast::AssignmentRhs::ReservedConst => continue,
66                ast::AssignmentRhs::Phi(ast::Phi { block, values }) => {
67                    for v in values.iter().rev().copied() {
68                        if let ast::Operand::Value(v) = v {
69                            stack.push(Entry::Trace(v.into()));
70                        }
71                    }
72                    stack.push(Entry::Trace((*block).into()));
73                }
74                ast::AssignmentRhs::Instruction(inst) => {
75                    let n = stack.len();
76                    inst.value_ids(|v| stack.push(Entry::Trace(v.into())));
77                    stack[n..].reverse();
78                }
79            },
80        }
81    }
82
83    return seq;
84
85    enum Entry {
86        Trace(Id<ast::Statement>),
87        Finished(Id<ast::Statement>),
88    }
89}
90
91impl Display for ast::Replacement {
92    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
93        let mut seen = HashSet::new();
94        match self {
95            ast::Replacement::LhsRhs {
96                statements,
97                lhs,
98                rhs,
99            } => {
100                for s in topo_sort_statements(statements, &mut seen, lhs.value.into()) {
101                    statements[s].display(statements, f)?;
102                }
103                lhs.display(statements, f)?;
104                match rhs {
105                    ast::Operand::Value(v) => {
106                        for s in topo_sort_statements(statements, &mut seen, (*v).into()) {
107                            statements[s].display(statements, f)?;
108                        }
109                        writeln!(f, "result {}", self.assignment(*v).name)
110                    }
111                    ast::Operand::Constant(ast::Constant { value, r#type }) => {
112                        write!(f, "result {}", value)?;
113                        if let Some(ty) = r#type {
114                            write!(f, ":{}", ty)?;
115                        }
116                        writeln!(f)
117                    }
118                }
119            }
120            ast::Replacement::Cand { statements, cand } => {
121                if let ast::Operand::Value(v) = cand.lhs {
122                    for s in topo_sort_statements(statements, &mut seen, v.into()) {
123                        statements[s].display(statements, f)?;
124                    }
125                }
126                if let ast::Operand::Value(v) = cand.rhs {
127                    for s in topo_sort_statements(statements, &mut seen, v.into()) {
128                        statements[s].display(statements, f)?;
129                    }
130                }
131                cand.display(statements, f)
132            }
133        }
134    }
135}
136
137impl Display for ast::LeftHandSide {
138    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
139        let mut seen = HashSet::new();
140        for s in topo_sort_statements(&self.statements, &mut seen, self.infer.value.into()) {
141            self.statements[s].display(&self.statements, f)?;
142        }
143        self.infer.display(&self.statements, f)
144    }
145}
146
147impl Display for ast::RightHandSide {
148    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
149        let mut seen = HashSet::new();
150        if let ast::Operand::Value(v) = self.result {
151            for s in topo_sort_statements(&self.statements, &mut seen, v.into()) {
152                self.statements[s].display(&self.statements, f)?;
153            }
154        }
155        write!(f, "result ")?;
156        self.result.display(&self.statements, f)
157    }
158}
159
160fn assignment(statements: &Arena<ast::Statement>, id: ast::ValueId) -> &ast::Assignment {
161    match &statements[id.into()] {
162        ast::Statement::Assignment(a) => a,
163        _ => panic!("use of an `id` that is not from this `Replacement`'s arena"),
164    }
165}
166
167impl DisplayWithContext for ast::Infer {
168    fn display(&self, statements: &Arena<ast::Statement>, f: &mut fmt::Formatter) -> fmt::Result {
169        write!(f, "infer ")?;
170        self.value.display(statements, f)?;
171        for attr in &self.attributes {
172            write!(f, " {}", attr)?;
173        }
174        writeln!(f)
175    }
176}
177
178impl DisplayWithContext for ast::Cand {
179    fn display(&self, statements: &Arena<ast::Statement>, f: &mut fmt::Formatter) -> fmt::Result {
180        write!(f, "cand ")?;
181        self.lhs.display(statements, f)?;
182        write!(f, " ")?;
183        self.rhs.display(statements, f)?;
184        for attr in &self.attributes {
185            write!(f, " {}", attr)?;
186        }
187        writeln!(f)
188    }
189}
190
191impl DisplayWithContext for ast::Statement {
192    fn display(&self, statements: &Arena<ast::Statement>, f: &mut fmt::Formatter) -> fmt::Result {
193        match self {
194            ast::Statement::Assignment(a) => a.display(statements, f)?,
195            ast::Statement::Pc(pc) => pc.display(statements, f)?,
196            ast::Statement::BlockPc(bpc) => bpc.display(statements, f)?,
197        }
198
199        writeln!(f)
200    }
201}
202
203impl DisplayWithContext for ast::Assignment {
204    fn display(&self, statements: &Arena<ast::Statement>, f: &mut fmt::Formatter) -> fmt::Result {
205        write!(f, "{}", self.name)?;
206        if let Some(ty) = self.r#type {
207            write!(f, ":{}", ty)?;
208        }
209        write!(f, " = ")?;
210        self.value.display(statements, f)?;
211        for attr in &self.attributes {
212            write!(f, " {}", attr)?;
213        }
214        Ok(())
215    }
216}
217
218impl DisplayWithContext for ast::AssignmentRhs {
219    fn display(&self, statements: &Arena<ast::Statement>, f: &mut fmt::Formatter) -> fmt::Result {
220        match self {
221            ast::AssignmentRhs::Var => write!(f, "var"),
222            ast::AssignmentRhs::Block(block) => <ast::Block as Display>::fmt(block, f),
223            ast::AssignmentRhs::Phi(phi) => phi.display(statements, f),
224            ast::AssignmentRhs::ReservedInst => write!(f, "reservedinst"),
225            ast::AssignmentRhs::ReservedConst => write!(f, "reservedconst"),
226            ast::AssignmentRhs::Instruction(inst) => inst.display(statements, f),
227        }
228    }
229}
230
231impl Display for ast::Block {
232    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
233        write!(f, "block {}", self.predecessors)
234    }
235}
236
237impl DisplayWithContext for ast::Phi {
238    fn display(&self, statements: &Arena<ast::Statement>, f: &mut fmt::Formatter) -> fmt::Result {
239        write!(f, "phi ")?;
240        self.block.display(statements, f)?;
241        for v in &self.values {
242            write!(f, ", ")?;
243            v.display(statements, f)?;
244        }
245        Ok(())
246    }
247}
248
249impl DisplayWithContext for ast::Instruction {
250    fn display(&self, statements: &Arena<ast::Statement>, f: &mut fmt::Formatter) -> fmt::Result {
251        write!(f, "{}", self.instruction_name())?;
252        let mut first = true;
253        let mut result = Ok(());
254        self.operands(|x| {
255            result = result.and_then(|_| {
256                if first {
257                    write!(f, " ")?;
258                    first = false;
259                } else {
260                    write!(f, ", ")?;
261                }
262                x.display(statements, f)
263            });
264        });
265        result
266    }
267}
268
269impl DisplayWithContext for ast::Pc {
270    fn display(&self, statements: &Arena<ast::Statement>, f: &mut fmt::Formatter) -> fmt::Result {
271        write!(f, "pc ")?;
272        self.x.display(statements, f)?;
273        write!(f, " ")?;
274        self.y.display(statements, f)
275    }
276}
277
278impl DisplayWithContext for ast::BlockPc {
279    fn display(&self, statements: &Arena<ast::Statement>, f: &mut fmt::Formatter) -> fmt::Result {
280        write!(f, "blockpc ")?;
281        self.block.display(statements, f)?;
282        write!(f, " {}", self.predecessor)?;
283        self.x.display(statements, f)?;
284        write!(f, " ")?;
285        self.y.display(statements, f)
286    }
287}
288
289impl Display for ast::RootAttribute {
290    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
291        write!(f, "(")?;
292        match self {
293            ast::RootAttribute::DemandedBits(db) => {
294                write!(f, "demandedBits=")?;
295                for b in db {
296                    if *b {
297                        write!(f, "1")?;
298                    } else {
299                        write!(f, "0")?;
300                    }
301                }
302            }
303            ast::RootAttribute::HarvestedFromUse => write!(f, "harvestedFromUse")?,
304        }
305        write!(f, ")")
306    }
307}
308
309impl Display for ast::Attribute {
310    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
311        write!(f, "(")?;
312        match self {
313            ast::Attribute::KnownBits(bits) => {
314                write!(f, "knownBits=")?;
315                for b in bits {
316                    match b {
317                        None => write!(f, "x")?,
318                        Some(true) => write!(f, "1")?,
319                        Some(false) => write!(f, "0")?,
320                    }
321                }
322            }
323            ast::Attribute::PowerOfTwo => write!(f, "powerOfTwo")?,
324            ast::Attribute::Negative => write!(f, "negative")?,
325            ast::Attribute::NonNegative => write!(f, "nonNegative")?,
326            ast::Attribute::NonZero => write!(f, "nonZero")?,
327            ast::Attribute::HasExternalUses => write!(f, "hasExternalUses")?,
328            ast::Attribute::SignBits(n) => write!(f, "signBits={}", n)?,
329            ast::Attribute::Range(min, max) => write!(f, "range=[{},{})", min, max)?,
330        }
331        write!(f, ")")
332    }
333}
334
335impl DisplayWithContext for ast::Operand {
336    fn display(&self, statements: &Arena<ast::Statement>, f: &mut fmt::Formatter) -> fmt::Result {
337        match self {
338            ast::Operand::Value(id) => id.display(statements, f),
339            ast::Operand::Constant(c) => <ast::Constant as Display>::fmt(c, f),
340        }
341    }
342}
343
344impl Display for ast::Constant {
345    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
346        write!(f, "{}", self.value)?;
347        if let Some(ty) = self.r#type {
348            write!(f, ":{}", ty)?;
349        }
350        Ok(())
351    }
352}
353
354impl DisplayWithContext for ast::ValueId {
355    fn display(&self, statements: &Arena<ast::Statement>, f: &mut fmt::Formatter) -> fmt::Result {
356        write!(f, "{}", assignment(statements, *self).name)
357    }
358}
359
360impl DisplayWithContext for ast::BlockId {
361    fn display(&self, statements: &Arena<ast::Statement>, f: &mut fmt::Formatter) -> fmt::Result {
362        write!(f, "{}", assignment(statements, self.0).name)
363    }
364}
365
366impl Display for ast::Type {
367    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
368        write!(f, "i{}", self.width)
369    }
370}
souper_ir/stringify.rs

souper_ir/
stringify.rs
