tin_lang/ir/system/
infer_layouts.rs

1use std::collections;
2use std::usize;
3
4use specs;
5
6use ir::component::element;
7use ir::component::layout;
8use std::ops;
9
10pub struct System {
11    ptr_size: usize,
12}
13
14const BOOL_LAYOUT: layout::Layout = layout::Layout::scalar(1);
15
16impl<'a> specs::System<'a> for System {
17    type SystemData = (
18        specs::Entities<'a>,
19        specs::ReadStorage<'a, element::Element>,
20        specs::WriteStorage<'a, layout::Layout>,
21    );
22
23    fn run(&mut self, (entities, elements, mut layouts): Self::SystemData) {
24        use specs::prelude::ParallelIterator;
25        use specs::ParJoin;
26
27        loop {
28            let new_layouts = (&entities, &elements, !&layouts)
29                .par_join()
30                .flat_map(|(entity, element, _)| {
31                    self.infer_layout(element, &elements, &layouts)
32                        .map(|layout| (entity, layout))
33                })
34                .collect::<Vec<_>>();
35            debug!("inferred new layouts: {:?}", new_layouts);
36            if new_layouts.is_empty() {
37                break;
38            }
39
40            for (entity, layout) in new_layouts {
41                layouts.insert(entity, layout).unwrap();
42            }
43        }
44    }
45}
46
47impl System {
48    pub fn new(ptr_size: usize) -> System {
49        System { ptr_size }
50    }
51
52    fn infer_layout<DE, DL>(
53        &self,
54        element: &element::Element,
55        elements: &specs::Storage<element::Element, DE>,
56        layouts: &specs::Storage<layout::Layout, DL>,
57    ) -> Option<layout::Layout>
58    where
59        DE: ops::Deref<Target = specs::storage::MaskedStorage<element::Element>>,
60        DL: ops::Deref<Target = specs::storage::MaskedStorage<layout::Layout>>,
61    {
62        match *element {
63            element::Element::NumberValue(ref n) => self.infer_number_layout(n),
64            element::Element::StringValue(_) => Some(layout::Layout::scalar(self.ptr_size)),
65            element::Element::Tuple(element::Tuple { ref fields }) => {
66                self.infer_tuple_layout(fields, layouts)
67            }
68            element::Element::Record(element::Record { ref fields }) => {
69                self.infer_record_layout(fields, layouts)
70            }
71            element::Element::UnOp(element::UnOp { operator, operand }) => {
72                self.infer_un_op_layout(operator, operand, layouts)
73            }
74            element::Element::BiOp(element::BiOp { lhs, operator, rhs }) => {
75                self.infer_bi_op_layout(lhs, operator, rhs, layouts)
76            }
77            element::Element::Variable(element::Variable { initializer, .. }) => {
78                self.infer_variable_layout(initializer, layouts)
79            }
80            element::Element::Select(element::Select { record, ref field }) => {
81                self.infer_select_layout(record, field, elements, layouts)
82            }
83            element::Element::Apply(element::Apply {
84                function,
85                ref parameters,
86            }) => self.infer_apply_layout(function, parameters, layouts),
87            element::Element::Parameter(element::Parameter { signature, .. }) => {
88                self.infer_parameter_layout(signature, layouts)
89            }
90            element::Element::Capture(element::Capture { captured, .. }) => {
91                self.infer_capture_layout(captured, layouts)
92            }
93            element::Element::Closure(element::Closure {
94                ref parameters,
95                signature,
96                result,
97                ..
98            }) => self.infer_closure_layout(parameters, signature, result, layouts),
99            element::Element::Module(element::Module { ref variables }) => {
100                self.infer_module_layout(variables, layouts)
101            }
102        }
103    }
104
105    fn infer_number_layout(&self, number: &element::NumberValue) -> Option<layout::Layout> {
106        match *number {
107            element::NumberValue::U8(_) => Some(layout::Layout::scalar(1)),
108            element::NumberValue::U16(_) => Some(layout::Layout::scalar(2)),
109            element::NumberValue::U32(_) => Some(layout::Layout::scalar(4)),
110            element::NumberValue::U64(_) => Some(layout::Layout::scalar(8)),
111            element::NumberValue::I8(_) => Some(layout::Layout::scalar(1)),
112            element::NumberValue::I16(_) => Some(layout::Layout::scalar(2)),
113            element::NumberValue::I32(_) => Some(layout::Layout::scalar(4)),
114            element::NumberValue::I64(_) => Some(layout::Layout::scalar(8)),
115            element::NumberValue::F32(_) => Some(layout::Layout::scalar(4)),
116            element::NumberValue::F64(_) => Some(layout::Layout::scalar(8)),
117        }
118    }
119
120    fn infer_tuple_layout<D>(
121        &self,
122        fields: &[specs::Entity],
123        layouts: &specs::Storage<layout::Layout, D>,
124    ) -> Option<layout::Layout>
125    where
126        D: ops::Deref<Target = specs::storage::MaskedStorage<layout::Layout>>,
127    {
128        if let Some(mut layouts) = fields
129            .iter()
130            .enumerate()
131            .map(|(i, f)| layouts.get(*f).map(|l| (i, l)))
132            .collect::<Option<Vec<_>>>()
133        {
134            if layouts.is_empty() {
135                Some(layout::Layout::zero())
136            } else {
137                layouts.sort_unstable_by_key(|(i, l)| (usize::MAX - l.size, *i));
138                let alignment = layouts.iter().map(|(_, l)| l.alignment).max().unwrap();
139                let mut size = 0;
140
141                let mut unnamed_field_offsets = vec![0; layouts.len()];
142
143                for (i, layout) in layouts {
144                    let offset = align_up(size, layout.alignment);
145                    size = offset + layout.size;
146                    unnamed_field_offsets[i] = offset;
147                }
148
149                Some(layout::Layout::unnamed_fields(
150                    size,
151                    alignment,
152                    unnamed_field_offsets,
153                ))
154            }
155        } else {
156            None
157        }
158    }
159
160    fn infer_record_layout<D>(
161        &self,
162        fields: &collections::HashMap<String, specs::Entity>,
163        layouts: &specs::Storage<layout::Layout, D>,
164    ) -> Option<layout::Layout>
165    where
166        D: ops::Deref<Target = specs::storage::MaskedStorage<layout::Layout>>,
167    {
168        if let Some(mut layouts) = fields
169            .iter()
170            .map(|(n, f)| layouts.get(*f).map(|l| (n, l)))
171            .collect::<Option<Vec<_>>>()
172        {
173            if layouts.is_empty() {
174                Some(layout::Layout::zero())
175            } else {
176                layouts.sort_unstable_by_key(|(n, l)| (usize::MAX - l.size, n.as_str()));
177                let alignment = layouts.iter().map(|(_, l)| l.alignment).max().unwrap();
178                let mut size = 0;
179
180                let named_field_offsets = layouts
181                    .into_iter()
182                    .map(|(n, l)| {
183                        let offset = align_up(size, l.alignment);
184                        size = offset + l.size;
185                        (n.clone(), offset)
186                    })
187                    .collect::<collections::HashMap<_, _>>();
188
189                Some(layout::Layout::named_fields(
190                    size,
191                    alignment,
192                    named_field_offsets,
193                ))
194            }
195        } else {
196            None
197        }
198    }
199
200    fn infer_un_op_layout<D>(
201        &self,
202        operator: element::UnOperator,
203        operand: specs::Entity,
204        layouts: &specs::Storage<layout::Layout, D>,
205    ) -> Option<layout::Layout>
206    where
207        D: ops::Deref<Target = specs::storage::MaskedStorage<layout::Layout>>,
208    {
209        let operand = layouts.get(operand).cloned();
210
211        match operator {
212            element::UnOperator::Not => Some(BOOL_LAYOUT),
213            element::UnOperator::BNot => operand,
214            element::UnOperator::Cl0 => operand,
215            element::UnOperator::Cl1 => operand,
216            element::UnOperator::Cls => operand,
217            element::UnOperator::Ct0 => operand,
218            element::UnOperator::Ct1 => operand,
219            element::UnOperator::C0 => operand,
220            element::UnOperator::C1 => operand,
221            element::UnOperator::Sqrt => operand,
222        }
223    }
224
225    fn infer_bi_op_layout<D>(
226        &self,
227        lhs: specs::Entity,
228        operator: element::BiOperator,
229        rhs: specs::Entity,
230        layouts: &specs::Storage<layout::Layout, D>,
231    ) -> Option<layout::Layout>
232    where
233        D: ops::Deref<Target = specs::storage::MaskedStorage<layout::Layout>>,
234    {
235        let lhs = layouts.get(lhs).cloned();
236        let rhs = layouts.get(rhs).cloned();
237
238        match (lhs.as_ref(), rhs.as_ref()) {
239            (Some(lhs), Some(rhs)) => {
240                assert_eq!(lhs.size, rhs.size);
241                assert_eq!(lhs.alignment, rhs.alignment);
242            }
243            _ => (),
244        };
245
246        match operator {
247            element::BiOperator::Eq => Some(BOOL_LAYOUT),
248            element::BiOperator::Ne => Some(BOOL_LAYOUT),
249            element::BiOperator::Lt => Some(BOOL_LAYOUT),
250            element::BiOperator::Ge => Some(BOOL_LAYOUT),
251            element::BiOperator::Gt => Some(BOOL_LAYOUT),
252            element::BiOperator::Le => Some(BOOL_LAYOUT),
253            element::BiOperator::Cmp => unimplemented!(),
254            element::BiOperator::Add => lhs,
255            element::BiOperator::Sub => lhs,
256            element::BiOperator::Mul => lhs,
257            element::BiOperator::Div => lhs,
258            element::BiOperator::Rem => lhs,
259            element::BiOperator::And => Some(BOOL_LAYOUT),
260            element::BiOperator::BAnd => lhs,
261            element::BiOperator::Or => Some(BOOL_LAYOUT),
262            element::BiOperator::BOr => lhs,
263            element::BiOperator::Xor => Some(BOOL_LAYOUT),
264            element::BiOperator::BXor => lhs,
265            element::BiOperator::AndNot => Some(BOOL_LAYOUT),
266            element::BiOperator::BAndNot => lhs,
267            element::BiOperator::OrNot => Some(BOOL_LAYOUT),
268            element::BiOperator::BOrNot => lhs,
269            element::BiOperator::XorNot => Some(BOOL_LAYOUT),
270            element::BiOperator::BXorNot => lhs,
271            element::BiOperator::RotL => lhs,
272            element::BiOperator::RotR => lhs,
273            element::BiOperator::ShL => lhs,
274            element::BiOperator::ShR => lhs,
275        }
276    }
277
278    fn infer_variable_layout<D>(
279        &self,
280        initializer: specs::Entity,
281        layouts: &specs::Storage<layout::Layout, D>,
282    ) -> Option<layout::Layout>
283    where
284        D: ops::Deref<Target = specs::storage::MaskedStorage<layout::Layout>>,
285    {
286        layouts.get(initializer).cloned()
287    }
288
289    fn infer_select_layout<DE, DL>(
290        &self,
291        record: specs::Entity,
292        field: &str,
293        elements: &specs::Storage<element::Element, DE>,
294        layouts: &specs::Storage<layout::Layout, DL>,
295    ) -> Option<layout::Layout>
296    where
297        DE: ops::Deref<Target = specs::storage::MaskedStorage<element::Element>>,
298        DL: ops::Deref<Target = specs::storage::MaskedStorage<layout::Layout>>,
299    {
300        match elements.get(record) {
301            None => None,
302            Some(t) => match t {
303                element::Element::Record(element::Record { ref fields }) => {
304                    if let Some(f) = fields.get(field) {
305                        layouts.get(*f).cloned()
306                    } else {
307                        None
308                    }
309                }
310                _ => None,
311            },
312        }
313    }
314
315    fn infer_apply_layout<D>(
316        &self,
317        _function: specs::Entity,
318        _parameters: &[specs::Entity],
319        _layouts: &specs::Storage<layout::Layout, D>,
320    ) -> Option<layout::Layout>
321    where
322        D: ops::Deref<Target = specs::storage::MaskedStorage<layout::Layout>>,
323    {
324        // TODO
325        None
326        /*
327        match types.get(function) {
328            None => {
329                trace!("inference failure: missing function type for apply");
330                None
331            }
332            Some(f) => match f {
333                ty::Type::Function(ty::Function {
334                    parameters: ref formal_parameters,
335                    result,
336                }) => {
337                    if let Some(parameters) = parameters
338                        .iter()
339                        .map(|p| types.get(*p).cloned())
340                        .collect::<Option<Vec<_>>>()
341                    {
342                        if parameters == *formal_parameters {
343                            Some((**result).clone())
344                        } else {
345                            Some(ty::Type::Conflict(ty::Conflict {
346                                expected: Box::new(ty::Type::Function(ty::Function {
347                                    parameters,
348                                    result: Box::new(ty::Type::Any),
349                                })),
350                                actual: Box::new(f.clone()),
351                            }))
352                        }
353                    } else {
354                        None
355                    }
356                }
357                something => Some(ty::Type::Conflict(ty::Conflict {
358                    expected: Box::new(ty::Type::Function(ty::Function {
359                        parameters: vec![ty::Type::Any],
360                        result: Box::new(ty::Type::Any),
361                    })),
362                    actual: Box::new(something.clone()),
363                })),
364            },
365        }
366        */
367    }
368
369    fn infer_parameter_layout<D>(
370        &self,
371        _signature: Option<specs::Entity>,
372        _layouts: &specs::Storage<layout::Layout, D>,
373    ) -> Option<layout::Layout>
374    where
375        D: ops::Deref<Target = specs::storage::MaskedStorage<layout::Layout>>,
376    {
377        // TODO
378        None
379        /*
380        if let Some(signature) = signature {
381            types.get(signature).cloned()
382        } else {
383            trace!("inference failure: no signature for parameter");
384            // TODO: implement surjective type inference
385            None
386        }
387        */
388    }
389
390    fn infer_capture_layout<D>(
391        &self,
392        capture: specs::Entity,
393        layouts: &specs::Storage<layout::Layout, D>,
394    ) -> Option<layout::Layout>
395    where
396        D: ops::Deref<Target = specs::storage::MaskedStorage<layout::Layout>>,
397    {
398        layouts.get(capture).cloned()
399    }
400
401    fn infer_closure_layout<D>(
402        &self,
403        _parameters: &[specs::Entity],
404        _signature: Option<specs::Entity>,
405        _result: specs::Entity,
406        _layouts: &specs::Storage<layout::Layout, D>,
407    ) -> Option<layout::Layout>
408    where
409        D: ops::Deref<Target = specs::storage::MaskedStorage<layout::Layout>>,
410    {
411        // TODO
412        None
413        /*
414            if let Some(parameters) = parameters
415                .iter()
416                .map(|p| types.get(*p).cloned())
417                .collect::<Option<Vec<_>>>()
418            {
419            if let Some(signature) = signature {
420                if let Some(result) = types.get(signature).cloned() {
421                    let result = Box::new(result);
422                    Some(ty::Type::Function(ty::Function { parameters, result }))
423                } else {
424                    trace!("inference failure: no signature for closure");
425                    None
426                }
427            } else if let Some(result) = types.get(result).cloned() {
428                let result = Box::new(result);
429                Some(ty::Type::Function(ty::Function { parameters, result }))
430            } else {
431                trace!("inference failure: missing signature type for closure, and no inferrable result type");
432                None
433            }
434        } else {
435            trace!("inference failure: missing parameter type(s) for closure");
436            // TODO: implement surjective type inference
437            None
438        }
439        */
440    }
441
442    fn infer_module_layout<D>(
443        &self,
444        _variables: &collections::HashMap<String, specs::Entity>,
445        _layouts: &specs::Storage<layout::Layout, D>,
446    ) -> Option<layout::Layout>
447    where
448        D: ops::Deref<Target = specs::storage::MaskedStorage<layout::Layout>>,
449    {
450        // TODO
451        None
452        /*
453        variables
454            .iter()
455            .map(|(k, v)| types.get(*v).map(|t| (k.clone(), t.clone())))
456            .collect::<Option<collections::HashMap<_, _>>>()
457            .map(|fields| ty::Type::Record(ty::Record { fields }))
458            */
459    }
460}
461
462fn align_up(offset: usize, alignment: usize) -> usize {
463    debug_assert!(alignment.is_power_of_two());
464    offset + ((-(offset as isize)) & (alignment as isize - 1)) as usize
465}
466
467#[cfg(test)]
468mod tests {
469    use super::*;
470
471    #[test]
472    fn align_up_4() {
473        assert_eq!(0, align_up(0, 4));
474        assert_eq!(4, align_up(1, 4));
475        assert_eq!(4, align_up(2, 4));
476        assert_eq!(4, align_up(3, 4));
477        assert_eq!(4, align_up(4, 4));
478        assert_eq!(8, align_up(5, 4));
479        assert_eq!(8, align_up(6, 4));
480        assert_eq!(8, align_up(7, 4));
481        assert_eq!(8, align_up(8, 4));
482        assert_eq!(12, align_up(9, 4));
483    }
484
485    #[test]
486    fn align_up_8() {
487        assert_eq!(0, align_up(0, 8));
488        assert_eq!(8, align_up(1, 8));
489        assert_eq!(8, align_up(2, 8));
490        assert_eq!(8, align_up(3, 8));
491        assert_eq!(8, align_up(4, 8));
492        assert_eq!(8, align_up(5, 8));
493        assert_eq!(8, align_up(6, 8));
494        assert_eq!(8, align_up(7, 8));
495        assert_eq!(8, align_up(8, 8));
496        assert_eq!(16, align_up(9, 8));
497    }
498}
tin_lang/ir/system/infer_layouts.rs

tin_lang/ir/system/
infer_layouts.rs
