ir_lang/builder.rs
1//! The [`Builder`]: how IR is constructed, and the interface a front-end lowers
2//! through.
3
4use alloc::string::String;
5use alloc::vec::Vec;
6
7use crate::entity::{Block, Value};
8use crate::function::{BlockData, Function, ValueData, ValueDef};
9use crate::inst::{BinOp, Inst, Terminator, UnOp};
10use crate::ty::Type;
11
12/// Constructs a [`Function`] one instruction at a time.
13///
14/// The builder is ir-lang's lowering interface. A front-end walks its own syntax
15/// tree and, for each construct, calls a builder method: a literal becomes a
16/// constant, an operator becomes a [`bin`](Builder::bin) or [`un`](Builder::un), an
17/// `if` becomes two blocks and a [`branch`](Builder::branch), a join becomes a block
18/// with parameters reached by [`jump`](Builder::jump). The builder mints a fresh
19/// [`Value`] for every result and hands it back, so the tree's structure is captured
20/// as flat SSA without the caller tracking numbering. Result types are inferred from
21/// the operation, so they never have to be supplied.
22///
23/// Construction does not check well-formedness as it goes — that keeps the hot path
24/// of lowering allocation-light and lets the caller emit blocks in whatever order is
25/// convenient. Call [`Function::validate`](crate::Function::validate) on the result
26/// (or build it and validate before handing it to a pass) to confirm the IR is
27/// sound.
28///
29/// # Examples
30///
31/// Lower `fn max(a: int, b: int) -> int { if a < b { b } else { a } }`:
32///
33/// ```
34/// use ir_lang::{Builder, BinOp, Type};
35///
36/// let mut b = Builder::new("max", &[Type::Int, Type::Int], Type::Int);
37/// let entry = b.entry();
38/// let a = b.block_params(entry)[0];
39/// let bb = b.block_params(entry)[1];
40///
41/// // The join block takes the chosen value as a parameter.
42/// let join = b.create_block(&[Type::Int]);
43/// let then_blk = b.create_block(&[]);
44/// let else_blk = b.create_block(&[]);
45///
46/// let cond = b.bin(BinOp::Lt, a, bb);
47/// b.branch(cond, then_blk, &[], else_blk, &[]);
48///
49/// b.switch_to(then_blk);
50/// b.jump(join, &[bb]);
51///
52/// b.switch_to(else_blk);
53/// b.jump(join, &[a]);
54///
55/// b.switch_to(join);
56/// let result = b.block_params(join)[0];
57/// b.ret(Some(result));
58///
59/// let func = b.finish();
60/// assert!(func.validate().is_ok());
61/// ```
62pub struct Builder {
63 name: String,
64 params: Vec<Type>,
65 ret: Type,
66 entry: Block,
67 blocks: Vec<BlockData>,
68 values: Vec<ValueData>,
69 current: Block,
70}
71
72impl Builder {
73 /// Starts a new function with the given name, parameter types, and return type.
74 ///
75 /// The entry block is created automatically with one parameter per function
76 /// parameter; those parameter values are the function's inputs and are read with
77 /// [`block_params`](Builder::block_params) on [`entry`](Builder::entry). The
78 /// entry block is the current block, so emission can begin immediately.
79 ///
80 /// # Examples
81 ///
82 /// ```
83 /// use ir_lang::{Builder, Type};
84 ///
85 /// let b = Builder::new("identity", &[Type::Int], Type::Int);
86 /// assert_eq!(b.block_params(b.entry()).len(), 1);
87 /// ```
88 #[must_use]
89 pub fn new(name: impl Into<String>, params: &[Type], ret: Type) -> Self {
90 let entry = Block::from_raw(0);
91 let mut values = Vec::with_capacity(params.len());
92 let mut entry_params = Vec::with_capacity(params.len());
93 for &ty in params {
94 let value = Value::from_raw(values.len() as u32);
95 values.push(ValueData {
96 ty,
97 def: ValueDef::Param(entry),
98 });
99 entry_params.push(value);
100 }
101 let entry_data = BlockData {
102 params: entry_params,
103 insts: Vec::new(),
104 term: None,
105 };
106 Self {
107 name: name.into(),
108 params: params.to_vec(),
109 ret,
110 entry,
111 blocks: alloc::vec![entry_data],
112 values,
113 current: entry,
114 }
115 }
116
117 /// Returns the entry block.
118 ///
119 /// # Examples
120 ///
121 /// ```
122 /// use ir_lang::{Builder, Type};
123 ///
124 /// let b = Builder::new("f", &[], Type::Unit);
125 /// assert_eq!(b.entry().index(), 0);
126 /// ```
127 #[must_use]
128 pub const fn entry(&self) -> Block {
129 self.entry
130 }
131
132 /// Returns the block that emission currently targets — the one the next
133 /// instruction or terminator is added to.
134 ///
135 /// # Examples
136 ///
137 /// ```
138 /// use ir_lang::{Builder, Type};
139 ///
140 /// let mut b = Builder::new("f", &[], Type::Unit);
141 /// let next = b.create_block(&[]);
142 /// b.switch_to(next);
143 /// assert_eq!(b.current_block(), next);
144 /// ```
145 #[must_use]
146 pub const fn current_block(&self) -> Block {
147 self.current
148 }
149
150 /// Creates a new block with the given parameter types and returns its handle.
151 ///
152 /// Block parameters are how a value crosses a control-flow join in SSA form:
153 /// each predecessor passes a matching argument on its
154 /// [`jump`](Builder::jump) or [`branch`](Builder::branch). The new block does
155 /// not become current — call [`switch_to`](Builder::switch_to) to emit into it.
156 ///
157 /// # Examples
158 ///
159 /// ```
160 /// use ir_lang::{Builder, Type};
161 ///
162 /// let mut b = Builder::new("f", &[], Type::Int);
163 /// let join = b.create_block(&[Type::Int]);
164 /// assert_eq!(b.block_params(join).len(), 1);
165 /// ```
166 pub fn create_block(&mut self, params: &[Type]) -> Block {
167 let block = Block::from_raw(self.blocks.len() as u32);
168 let mut block_params = Vec::with_capacity(params.len());
169 for &ty in params {
170 let value = Value::from_raw(self.values.len() as u32);
171 self.values.push(ValueData {
172 ty,
173 def: ValueDef::Param(block),
174 });
175 block_params.push(value);
176 }
177 self.blocks.push(BlockData {
178 params: block_params,
179 insts: Vec::new(),
180 term: None,
181 });
182 block
183 }
184
185 /// Returns a block's parameter values, in order, or an empty slice if the block
186 /// handle is out of range.
187 ///
188 /// # Examples
189 ///
190 /// ```
191 /// use ir_lang::{Builder, Type};
192 ///
193 /// let b = Builder::new("f", &[Type::Bool], Type::Unit);
194 /// assert_eq!(b.block_params(b.entry()).len(), 1);
195 /// ```
196 #[must_use]
197 pub fn block_params(&self, block: Block) -> &[Value] {
198 match self.blocks.get(block.index()) {
199 Some(data) => &data.params,
200 None => &[],
201 }
202 }
203
204 /// Switches emission to `block`. Subsequent instructions and the terminator are
205 /// added to it.
206 ///
207 /// # Examples
208 ///
209 /// ```
210 /// use ir_lang::{Builder, Type};
211 ///
212 /// let mut b = Builder::new("f", &[], Type::Unit);
213 /// let other = b.create_block(&[]);
214 /// b.switch_to(other);
215 /// b.ret(None);
216 /// ```
217 pub fn switch_to(&mut self, block: Block) {
218 self.current = block;
219 }
220
221 /// Emits an integer constant into the current block and returns its value.
222 ///
223 /// # Examples
224 ///
225 /// ```
226 /// use ir_lang::{Builder, Type};
227 ///
228 /// let mut b = Builder::new("f", &[], Type::Int);
229 /// let n = b.iconst(42);
230 /// b.ret(Some(n));
231 /// assert_eq!(b.finish().value_type(n), Some(Type::Int));
232 /// ```
233 pub fn iconst(&mut self, value: i64) -> Value {
234 self.push_inst(Inst::Iconst(value), Type::Int)
235 }
236
237 /// Emits a floating-point constant into the current block and returns its value.
238 ///
239 /// # Examples
240 ///
241 /// ```
242 /// use ir_lang::{Builder, Type};
243 ///
244 /// let mut b = Builder::new("f", &[], Type::Float);
245 /// let pi = b.fconst(3.14);
246 /// b.ret(Some(pi));
247 /// assert_eq!(b.finish().value_type(pi), Some(Type::Float));
248 /// ```
249 pub fn fconst(&mut self, value: f64) -> Value {
250 self.push_inst(Inst::Fconst(value), Type::Float)
251 }
252
253 /// Emits a boolean constant into the current block and returns its value.
254 ///
255 /// # Examples
256 ///
257 /// ```
258 /// use ir_lang::{Builder, Type};
259 ///
260 /// let mut b = Builder::new("f", &[], Type::Bool);
261 /// let t = b.bconst(true);
262 /// b.ret(Some(t));
263 /// assert_eq!(b.finish().value_type(t), Some(Type::Bool));
264 /// ```
265 pub fn bconst(&mut self, value: bool) -> Value {
266 self.push_inst(Inst::Bconst(value), Type::Bool)
267 }
268
269 /// Emits a binary operation over two values and returns the result.
270 ///
271 /// The result type follows the operation: a comparison or a logical operation
272 /// yields [`Bool`](crate::Type::Bool); an arithmetic operation yields the type
273 /// of its operands. Whether the operands actually satisfy the operation is
274 /// checked by [`validate`](crate::Function::validate), not here.
275 ///
276 /// # Examples
277 ///
278 /// ```
279 /// use ir_lang::{Builder, BinOp, Type};
280 ///
281 /// let mut b = Builder::new("f", &[Type::Int, Type::Int], Type::Bool);
282 /// let a = b.block_params(b.entry())[0];
283 /// let c = b.block_params(b.entry())[1];
284 /// let lt = b.bin(BinOp::Lt, a, c);
285 /// b.ret(Some(lt));
286 /// assert_eq!(b.finish().value_type(lt), Some(Type::Bool));
287 /// ```
288 pub fn bin(&mut self, op: BinOp, lhs: Value, rhs: Value) -> Value {
289 let ty = if op.is_comparison() || op.is_logical() {
290 Type::Bool
291 } else {
292 self.value_ty(lhs)
293 };
294 self.push_inst(Inst::Bin(op, lhs, rhs), ty)
295 }
296
297 /// Emits a unary operation over one value and returns the result.
298 ///
299 /// [`Neg`](crate::UnOp::Neg) yields the operand's type;
300 /// [`Not`](crate::UnOp::Not) yields [`Bool`](crate::Type::Bool).
301 ///
302 /// # Examples
303 ///
304 /// ```
305 /// use ir_lang::{Builder, UnOp, Type};
306 ///
307 /// let mut b = Builder::new("f", &[Type::Int], Type::Int);
308 /// let x = b.block_params(b.entry())[0];
309 /// let neg = b.un(UnOp::Neg, x);
310 /// b.ret(Some(neg));
311 /// assert_eq!(b.finish().value_type(neg), Some(Type::Int));
312 /// ```
313 pub fn un(&mut self, op: UnOp, operand: Value) -> Value {
314 let ty = match op {
315 UnOp::Neg => self.value_ty(operand),
316 UnOp::Not => Type::Bool,
317 };
318 self.push_inst(Inst::Un(op, operand), ty)
319 }
320
321 /// Sets the current block's terminator to a return.
322 ///
323 /// `Some(v)` returns the value `v`; `None` returns from a function whose return
324 /// type is [`Unit`](crate::Type::Unit).
325 ///
326 /// # Examples
327 ///
328 /// ```
329 /// use ir_lang::{Builder, Type};
330 ///
331 /// let mut b = Builder::new("f", &[], Type::Unit);
332 /// b.ret(None);
333 /// assert!(b.finish().validate().is_ok());
334 /// ```
335 pub fn ret(&mut self, value: Option<Value>) {
336 self.set_terminator(Terminator::Return(value));
337 }
338
339 /// Sets the current block's terminator to an unconditional jump, passing one
340 /// argument per parameter of the target block.
341 ///
342 /// # Examples
343 ///
344 /// ```
345 /// use ir_lang::{Builder, Type};
346 ///
347 /// let mut b = Builder::new("f", &[], Type::Int);
348 /// let exit = b.create_block(&[Type::Int]);
349 /// let n = b.iconst(7);
350 /// b.jump(exit, &[n]);
351 /// b.switch_to(exit);
352 /// let r = b.block_params(exit)[0];
353 /// b.ret(Some(r));
354 /// assert!(b.finish().validate().is_ok());
355 /// ```
356 pub fn jump(&mut self, target: Block, args: &[Value]) {
357 self.set_terminator(Terminator::Jump(target, args.to_vec()));
358 }
359
360 /// Sets the current block's terminator to a conditional branch.
361 ///
362 /// Control takes `then_block` (with `then_args`) when `cond` is true, and
363 /// `else_block` (with `else_args`) otherwise. Each arm's arguments are matched
364 /// against the parameters of the block it targets.
365 ///
366 /// # Examples
367 ///
368 /// ```
369 /// use ir_lang::{Builder, Type};
370 ///
371 /// let mut b = Builder::new("f", &[Type::Bool], Type::Unit);
372 /// let cond = b.block_params(b.entry())[0];
373 /// let yes = b.create_block(&[]);
374 /// let no = b.create_block(&[]);
375 /// b.branch(cond, yes, &[], no, &[]);
376 /// b.switch_to(yes);
377 /// b.ret(None);
378 /// b.switch_to(no);
379 /// b.ret(None);
380 /// assert!(b.finish().validate().is_ok());
381 /// ```
382 pub fn branch(
383 &mut self,
384 cond: Value,
385 then_block: Block,
386 then_args: &[Value],
387 else_block: Block,
388 else_args: &[Value],
389 ) {
390 self.set_terminator(Terminator::Branch {
391 cond,
392 then_block,
393 then_args: then_args.to_vec(),
394 else_block,
395 else_args: else_args.to_vec(),
396 });
397 }
398
399 /// Finishes construction and returns the assembled [`Function`].
400 ///
401 /// The function is not validated by this call; run
402 /// [`Function::validate`](crate::Function::validate) on the result before relying
403 /// on it.
404 ///
405 /// # Examples
406 ///
407 /// ```
408 /// use ir_lang::{Builder, Type};
409 ///
410 /// let mut b = Builder::new("f", &[], Type::Unit);
411 /// b.ret(None);
412 /// let func = b.finish();
413 /// assert_eq!(func.block_count(), 1);
414 /// ```
415 #[must_use]
416 pub fn finish(self) -> Function {
417 Function::from_parts(
418 self.name,
419 self.params,
420 self.ret,
421 self.entry,
422 self.blocks,
423 self.values,
424 )
425 }
426
427 fn value_ty(&self, value: Value) -> Type {
428 self.values
429 .get(value.index())
430 .map_or(Type::Unit, |data| data.ty)
431 }
432
433 fn push_inst(&mut self, inst: Inst, ty: Type) -> Value {
434 let value = Value::from_raw(self.values.len() as u32);
435 self.values.push(ValueData {
436 ty,
437 def: ValueDef::Inst(self.current, inst),
438 });
439 if let Some(block) = self.blocks.get_mut(self.current.index()) {
440 block.insts.push(value);
441 }
442 value
443 }
444
445 fn set_terminator(&mut self, term: Terminator) {
446 if let Some(block) = self.blocks.get_mut(self.current.index()) {
447 block.term = Some(term);
448 }
449 }
450}
451
452#[cfg(test)]
453mod tests {
454 use super::*;
455
456 #[test]
457 fn test_new_seeds_entry_with_function_params() {
458 let b = Builder::new("f", &[Type::Int, Type::Bool], Type::Unit);
459 let params = b.block_params(b.entry());
460 assert_eq!(params.len(), 2);
461 assert_eq!(b.current_block(), b.entry());
462 }
463
464 #[test]
465 fn test_bin_result_type_follows_operation() {
466 let mut b = Builder::new("f", &[Type::Int, Type::Int], Type::Bool);
467 let a = b.block_params(b.entry())[0];
468 let c = b.block_params(b.entry())[1];
469 let sum = b.bin(BinOp::Add, a, c);
470 let cmp = b.bin(BinOp::Lt, a, c);
471 let and = b.bin(BinOp::And, cmp, cmp);
472 b.ret(Some(cmp));
473 let func = b.finish();
474 assert_eq!(func.value_type(sum), Some(Type::Int));
475 assert_eq!(func.value_type(cmp), Some(Type::Bool));
476 assert_eq!(func.value_type(and), Some(Type::Bool));
477 }
478
479 #[test]
480 fn test_un_result_type_follows_operation() {
481 let mut b = Builder::new("f", &[Type::Int, Type::Bool], Type::Int);
482 let x = b.block_params(b.entry())[0];
483 let flag = b.block_params(b.entry())[1];
484 let neg = b.un(UnOp::Neg, x);
485 let not = b.un(UnOp::Not, flag);
486 b.ret(Some(neg));
487 let func = b.finish();
488 assert_eq!(func.value_type(neg), Some(Type::Int));
489 assert_eq!(func.value_type(not), Some(Type::Bool));
490 }
491
492 #[test]
493 fn test_handles_are_dense_from_zero() {
494 let mut b = Builder::new("f", &[Type::Int], Type::Int);
495 let p = b.block_params(b.entry())[0];
496 let one = b.iconst(1);
497 let two = b.iconst(2);
498 assert_eq!(p.index(), 0);
499 assert_eq!(one.index(), 1);
500 assert_eq!(two.index(), 2);
501 }
502}