1 //! Optimization driver using ISLE rewrite rules on an egraph.
2 
3 use crate::egraph::{NewOrExistingInst, OptimizeCtx};
4 use crate::ir::condcodes;
5 pub use crate::ir::condcodes::{FloatCC, IntCC};
6 use crate::ir::dfg::ValueDef;
7 pub use crate::ir::immediates::{Ieee32, Ieee64, Imm64, Offset32, Uimm8, V128Imm};
8 pub use crate::ir::types::*;
9 pub use crate::ir::{
10     dynamic_to_fixed, AtomicRmwOp, BlockCall, Constant, DynamicStackSlot, FuncRef, GlobalValue,
11     Immediate, InstructionData, MemFlags, Opcode, StackSlot, Table, TrapCode, Type, Value,
12 };
13 use crate::isle_common_prelude_methods;
14 use crate::machinst::isle::*;
15 use crate::trace;
16 use cranelift_entity::packed_option::ReservedValue;
17 use smallvec::{smallvec, SmallVec};
18 use std::marker::PhantomData;
19 
20 #[allow(dead_code)]
21 pub type Unit = ();
22 pub type Range = (usize, usize);
23 pub type ValueArray2 = [Value; 2];
24 pub type ValueArray3 = [Value; 3];
25 
26 const MAX_ISLE_RETURNS: usize = 8;
27 
28 pub type ConstructorVec<T> = SmallVec<[T; MAX_ISLE_RETURNS]>;
29 
30 impl<T: smallvec::Array> generated_code::Length for SmallVec<T> {
31     #[inline]
32     fn len(&self) -> usize {
33         SmallVec::len(self)
34     }
35 }
36 
37 pub(crate) mod generated_code;
38 use generated_code::{ContextIter, IntoContextIter};
39 
40 pub(crate) struct IsleContext<'a, 'b, 'c> {
41     pub(crate) ctx: &'a mut OptimizeCtx<'b, 'c>,
42 }
43 
44 pub(crate) struct InstDataEtorIter<'a, 'b, 'c> {
45     stack: SmallVec<[Value; 8]>,
46     _phantom1: PhantomData<&'a ()>,
47     _phantom2: PhantomData<&'b ()>,
48     _phantom3: PhantomData<&'c ()>,
49 }
50 
51 impl Default for InstDataEtorIter<'_, '_, '_> {
52     fn default() -> Self {
53         InstDataEtorIter {
54             stack: SmallVec::default(),
55             _phantom1: PhantomData,
56             _phantom2: PhantomData,
57             _phantom3: PhantomData,
58         }
59     }
60 }
61 
62 impl<'a, 'b, 'c> InstDataEtorIter<'a, 'b, 'c> {
63     fn new(root: Value) -> Self {
64         debug_assert_ne!(root, Value::reserved_value());
65         Self {
66             stack: smallvec![root],
67             _phantom1: PhantomData,
68             _phantom2: PhantomData,
69             _phantom3: PhantomData,
70         }
71     }
72 }
73 
74 impl<'a, 'b, 'c> ContextIter for InstDataEtorIter<'a, 'b, 'c>
75 where
76     'b: 'a,
77     'c: 'b,
78 {
79     type Context = IsleContext<'a, 'b, 'c>;
80     type Output = (Type, InstructionData);
81 
82     fn next(&mut self, ctx: &mut IsleContext<'a, 'b, 'c>) -> Option<Self::Output> {
83         while let Some(value) = self.stack.pop() {
84             debug_assert_ne!(value, Value::reserved_value());
85             let value = ctx.ctx.func.dfg.resolve_aliases(value);
86             trace!("iter: value {:?}", value);
87             match ctx.ctx.func.dfg.value_def(value) {
88                 ValueDef::Union(x, y) => {
89                     debug_assert_ne!(x, Value::reserved_value());
90                     debug_assert_ne!(y, Value::reserved_value());
91                     trace!(" -> {}, {}", x, y);
92                     self.stack.push(x);
93                     self.stack.push(y);
94                     continue;
95                 }
96                 ValueDef::Result(inst, _) if ctx.ctx.func.dfg.inst_results(inst).len() == 1 => {
97                     let ty = ctx.ctx.func.dfg.value_type(value);
98                     trace!(" -> value of type {}", ty);
99                     return Some((ty, ctx.ctx.func.dfg.insts[inst].clone()));
100                 }
101                 _ => {}
102             }
103         }
104         None
105     }
106 }
107 
108 impl<'a, 'b, 'c> IntoContextIter for InstDataEtorIter<'a, 'b, 'c>
109 where
110     'b: 'a,
111     'c: 'b,
112 {
113     type Context = IsleContext<'a, 'b, 'c>;
114     type Output = (Type, InstructionData);
115     type IntoIter = Self;
116 
117     fn into_context_iter(self) -> Self {
118         self
119     }
120 }
121 
122 impl<'a, 'b, 'c> generated_code::Context for IsleContext<'a, 'b, 'c> {
123     isle_common_prelude_methods!();
124 
125     type inst_data_etor_returns = InstDataEtorIter<'a, 'b, 'c>;
126 
127     fn inst_data_etor(&mut self, eclass: Value, returns: &mut InstDataEtorIter<'a, 'b, 'c>) {
128         *returns = InstDataEtorIter::new(eclass);
129     }
130 
131     fn make_inst_ctor(&mut self, ty: Type, op: &InstructionData) -> Value {
132         let value = self
133             .ctx
134             .insert_pure_enode(NewOrExistingInst::New(op.clone(), ty));
135         trace!("make_inst_ctor: {:?} -> {}", op, value);
136         value
137     }
138 
139     fn value_array_2_ctor(&mut self, arg0: Value, arg1: Value) -> ValueArray2 {
140         [arg0, arg1]
141     }
142 
143     fn value_array_3_ctor(&mut self, arg0: Value, arg1: Value, arg2: Value) -> ValueArray3 {
144         [arg0, arg1, arg2]
145     }
146 
147     #[inline]
148     fn value_type(&mut self, val: Value) -> Type {
149         self.ctx.func.dfg.value_type(val)
150     }
151 
152     fn remat(&mut self, value: Value) -> Value {
153         trace!("remat: {}", value);
154         self.ctx.remat_values.insert(value);
155         self.ctx.stats.remat += 1;
156         value
157     }
158 
159     fn subsume(&mut self, value: Value) -> Value {
160         trace!("subsume: {}", value);
161         self.ctx.subsume_values.insert(value);
162         self.ctx.stats.subsume += 1;
163         value
164     }
165 
166     fn splat64(&mut self, val: u64) -> Constant {
167         let val = u128::from(val);
168         let val = val | (val << 64);
169         let imm = V128Imm(val.to_le_bytes());
170         self.ctx.func.dfg.constants.insert(imm.into())
171     }
172 }
173