1;; Prelude definitions specific to the mid-end.
2
3;; Any `extern` definitions here are generally implemented in `src/opts.rs`.
4
5;;;;; eclass and enode access ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
6
7;; Extract any node(s) for the given eclass ID.
8(decl multi inst_data_value (Type InstructionData) Value)
9(extern extractor inst_data_value inst_data_value_etor)
10
11;; An extractor from an `Inst` to its `InstructionData`.
12(decl inst_data (InstructionData) Inst)
13(extern extractor inst_data inst_data_etor)
14
15;; Identical to `inst_data_value`, just with a different ISLE type.  This is
16;; basically a manual version of `curry`/`uncurry` in Haskell: to compose
17;; extractors the outer one needs to be single-parameter, so this combines the
18;; two parameters of `inst_data_value` into one.
19(type TypeAndInstructionData (primitive TypeAndInstructionData))
20(decl multi inst_data_value_tupled (TypeAndInstructionData) Value)
21(extern extractor inst_data_value_tupled inst_data_value_tupled_etor)
22
23;; Construct a pure node, returning a new (or deduplicated
24;; already-existing) eclass ID.
25(decl make_inst (Type InstructionData) Value)
26(extern constructor make_inst make_inst_ctor)
27
28;; Make a new side-effectful instruction, do not insert it into the layout, and
29;; return its `Inst`.
30(decl make_skeleton_inst (InstructionData) Inst)
31(extern constructor make_skeleton_inst make_skeleton_inst_ctor)
32
33;; Constructors for value arrays.
34(decl value_array_2_ctor (Value Value) ValueArray2)
35(extern constructor value_array_2_ctor value_array_2_ctor)
36(decl value_array_3_ctor (Value Value Value) ValueArray3)
37(extern constructor value_array_3_ctor value_array_3_ctor)
38
39(rule (eq ty x y) (icmp ty (IntCC.Equal) x y))
40(rule (ne ty x y) (icmp ty (IntCC.NotEqual) x y))
41(rule (ult ty x y) (icmp ty (IntCC.UnsignedLessThan) x y))
42(rule (ule ty x y) (icmp ty (IntCC.UnsignedLessThanOrEqual) x y))
43(rule (ugt ty x y) (icmp ty (IntCC.UnsignedGreaterThan) x y))
44(rule (uge ty x y) (icmp ty (IntCC.UnsignedGreaterThanOrEqual) x y))
45(rule (slt ty x y) (icmp ty (IntCC.SignedLessThan) x y))
46(rule (sle ty x y) (icmp ty (IntCC.SignedLessThanOrEqual) x y))
47(rule (sgt ty x y) (icmp ty (IntCC.SignedGreaterThan) x y))
48(rule (sge ty x y) (icmp ty (IntCC.SignedGreaterThanOrEqual) x y))
49
50;; 3-way comparison, returning -1/0/+1 in I8
51(decl spaceship_s (Type Value Value) Value)
52(rule (spaceship_s ty x y) (isub $I8 (sgt ty x y) (slt ty x y)))
53(extractor (spaceship_s ty x y) (isub $I8 (sgt ty x y) (slt ty x y)))
54(decl spaceship_u (Type Value Value) Value)
55(rule (spaceship_u ty x y) (isub $I8 (ugt ty x y) (ult ty x y)))
56(extractor (spaceship_u ty x y) (isub $I8 (ugt ty x y) (ult ty x y)))
57
58;;;;; optimization toplevel ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
59
60;; The main matcher rule invoked by the toplevel driver.
61(decl multi simplify (Value) Value)
62
63;; The kind of simplification to perform on a skeleton instruction.
64(type SkeletonInstSimplification
65      (enum
66        ;; Remove the instruction being simplified from the skeleton, it is
67        ;; unnecessary.
68        ;;
69        ;; The instruction must not define any results.
70        (Remove)
71
72        ;; Remove the instruction being simplified from the skeleton, and
73        ;; replace its result value with the given `val`.
74        (RemoveWithVal (val Value))
75
76        ;; Replace the instruction being simplified with the given instruction.
77        ;;
78        ;; The given instruction must not already be in a block and must define
79        ;; the same number and types of results as the old instruction that it
80        ;; is replacing.
81        (Replace (inst Inst))
82
83        ;; Like `Replace` but replace the old instruction's result value with
84        ;; the given `val`.
85        ;;
86        ;; The old instruction must define a single result value and `val` must
87        ;; match its type. The new instruction need not define the same number
88        ;; or types of results as the old instruction.
89        (ReplaceWithVal (inst Inst) (val Value))))
90
91(decl pure inst_to_skeleton_inst_simplification (Inst) SkeletonInstSimplification)
92(rule (inst_to_skeleton_inst_simplification inst)
93      (SkeletonInstSimplification.Replace inst))
94
95(decl pure value_to_skeleton_inst_simplification (Value) SkeletonInstSimplification)
96(rule (value_to_skeleton_inst_simplification val)
97      (SkeletonInstSimplification.RemoveWithVal val))
98
99(decl pure remove_inst () SkeletonInstSimplification)
100(rule (remove_inst) (SkeletonInstSimplification.Remove))
101
102(decl pure replace_with_val (Inst Value) SkeletonInstSimplification)
103(rule (replace_with_val inst val) (SkeletonInstSimplification.ReplaceWithVal inst val))
104
105(convert Inst SkeletonInstSimplification inst_to_skeleton_inst_simplification)
106(convert Value SkeletonInstSimplification value_to_skeleton_inst_simplification)
107
108;; The main term for simplifying side-effectful instructions, invoked by the
109;; egraph driver.
110(decl multi simplify_skeleton (Inst) SkeletonInstSimplification)
111
112;; Mark a node as requiring remat when used in a different block.
113(decl remat (Value) Value)
114(extern constructor remat remat)
115
116;; Mark a node as subsuming whatever else it's rewritten from -- this
117;; is definitely preferable, not just a possible option. Useful for,
118;; e.g., constant propagation where we arrive at a definite "final
119;; answer".
120(decl subsume (Value) Value)
121(extern constructor subsume subsume)
122
123;;;;; constructors ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
124
125(decl iconst_sextend_etor (Type i64) TypeAndInstructionData)
126(extern extractor iconst_sextend_etor iconst_sextend_etor)
127
128;; Construct an `iconst` from an `i64` or Extract an `i64` from an `iconst`
129;; by treating the constant as signed.
130;; When extracting, smaller types get their value sign-extended to 64-bits,
131;; so that `iconst.i8 255` will give you a `-1_i64`.
132;; When constructing, the rule will fail if the value cannot be represented in
133;; the target type.  If it fits, it'll be masked accordingly in the constant.
134(decl iconst_s (Type i64) Value)
135(extractor (iconst_s ty c) (inst_data_value_tupled (iconst_sextend_etor ty c)))
136(rule 0 (iconst_s ty c)
137    (if-let c_masked (u64_and (i64_as_u64 c) (ty_umax ty)))
138    (if-let c_reextended (i64_sextend_u64 ty c_masked))
139    (if-let true (u64_eq (i64_as_u64 c) (i64_as_u64 c_reextended)))
140    (iconst ty (imm64 c_masked)))
141(rule 1 (iconst_s $I128 c) (sextend $I128 (iconst_s $I64 c)))
142
143;; Construct an `iconst` from a `u64` or Extract a `u64` from an `iconst`
144;; by treating the constant as unsigned.
145;; When extracting, smaller types get their value zero-extended to 64-bits,
146;; so that `iconst.i8 255` will give you a `255_u64`.
147;; When constructing, the rule will fail if the value cannot be represented in
148;; the target type.
149(decl iconst_u (Type u64) Value)
150(extractor (iconst_u ty c) (iconst ty (u64_from_imm64 c)))
151(rule 0 (iconst_u ty c)
152    (if-let true (u64_le c (ty_umax ty)))
153    (iconst ty (imm64 c)))
154(rule 1 (iconst_u $I128 c) (uextend $I128 (iconst_u $I64 c)))
155
156;; These take `Value`, rather than going through `inst_data_value_tupled`,
157;; because most of the time they want to return the original `Value`, and it
158;; would be a waste to need to re-GVN the instruction data in those cases.
159(decl multi sextend_maybe_etor (Type Value) Value)
160(extern extractor infallible sextend_maybe_etor sextend_maybe_etor)
161(decl multi uextend_maybe_etor (Type Value) Value)
162(extern extractor infallible uextend_maybe_etor uextend_maybe_etor)
163
164;; Match or Construct a possibly-`uextend`ed value.
165;; Gives the extended-to type and inner value when matching something that was
166;; extended, or the input value and its type when the value isn't an extension.
167;; Useful to write a single pattern that can match things that may or may not
168;; have undergone C's "usual arithmetic conversions".
169;; When generating values, extending to the same type is invalid CLIF,
170;; so this avoids doing that where there's no extension actually needed.
171(decl uextend_maybe (Type Value) Value)
172(extractor (uextend_maybe ty val) (uextend_maybe_etor ty val))
173(rule 0 (uextend_maybe ty val) (uextend ty val))
174(rule 1 (uextend_maybe ty val@(value_type ty)) val)
175
176;; Same as `uextend_maybe` above, just for `sextend`.
177(decl sextend_maybe (Type Value) Value)
178(extractor (sextend_maybe ty val) (sextend_maybe_etor ty val))
179(rule 0 (sextend_maybe ty val) (sextend ty val))
180(rule 1 (sextend_maybe ty val@(value_type ty)) val)
181
182;;;;;; Helper CLIF Extractors ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
183
184(decl eq (Type Value Value) Value)
185(extractor (eq ty x y) (icmp ty (IntCC.Equal) x y))
186
187(decl ne (Type Value Value) Value)
188(extractor (ne ty x y) (icmp ty (IntCC.NotEqual) x y))
189
190(decl ult (Type Value Value) Value)
191(extractor (ult ty x y) (icmp ty (IntCC.UnsignedLessThan) x y))
192
193(decl ule (Type Value Value) Value)
194(extractor (ule ty x y) (icmp ty (IntCC.UnsignedLessThanOrEqual) x y))
195
196(decl ugt (Type Value Value) Value)
197(extractor (ugt ty x y) (icmp ty (IntCC.UnsignedGreaterThan) x y))
198
199(decl uge (Type Value Value) Value)
200(extractor (uge ty x y) (icmp ty (IntCC.UnsignedGreaterThanOrEqual) x y))
201
202(decl slt (Type Value Value) Value)
203(extractor (slt ty x y) (icmp ty (IntCC.SignedLessThan) x y))
204
205(decl sle (Type Value Value) Value)
206(extractor (sle ty x y) (icmp ty (IntCC.SignedLessThanOrEqual) x y))
207
208(decl sgt (Type Value Value) Value)
209(extractor (sgt ty x y) (icmp ty (IntCC.SignedGreaterThan) x y))
210
211(decl sge (Type Value Value) Value)
212(extractor (sge ty x y) (icmp ty (IntCC.SignedGreaterThanOrEqual) x y))
213