xref: /llvm-project/mlir/lib/Dialect/Arith/IR/ArithCanonicalization.td (revision 345f57df16af7e4fac3a321035e504b5d49206f4) 
1//===- ArithPatterns.td - Arith dialect patterns -*- tablegen -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef ARITH_PATTERNS
10#define ARITH_PATTERNS
11
12include "mlir/IR/PatternBase.td"
13include "mlir/Dialect/Arith/IR/ArithOps.td"
14
15// Create zero attribute of type matching the argument's type.
16def GetZeroAttr : NativeCodeCall<"$_builder.getZeroAttr($0.getType())">;
17
18// Add two integer attributes and create a new one with the result.
19def AddIntAttrs : NativeCodeCall<"addIntegerAttrs($_builder, $0, $1, $2)">;
20
21// Subtract two integer attributes and create a new one with the result.
22def SubIntAttrs : NativeCodeCall<"subIntegerAttrs($_builder, $0, $1, $2)">;
23
24// Multiply two integer attributes and create a new one with the result.
25def MulIntAttrs : NativeCodeCall<"mulIntegerAttrs($_builder, $0, $1, $2)">;
26
27// Merge overflow flags from 2 ops, selecting the most conservative combination.
28def MergeOverflow : NativeCodeCall<"mergeOverflowFlags($0, $1)">;
29
30// Default overflow flag (all wraparounds allowed).
31defvar DefOverflow = ConstantEnumCase<Arith_IntegerOverflowAttr, "none">;
32
33class cast<string type> : NativeCodeCall<"::mlir::cast<" # type # ">($0)">;
34
35//===----------------------------------------------------------------------===//
36// AddIOp
37//===----------------------------------------------------------------------===//
38
39// addi is commutative and will be canonicalized to have its constants appear
40// as the second operand.
41
42// addi(addi(x, c0), c1) -> addi(x, c0 + c1)
43def AddIAddConstant :
44    Pat<(Arith_AddIOp:$res
45          (Arith_AddIOp $x, (ConstantLikeMatcher APIntAttr:$c0), $ovf1),
46          (ConstantLikeMatcher APIntAttr:$c1), $ovf2),
47        (Arith_AddIOp $x, (Arith_ConstantOp (AddIntAttrs $res, $c0, $c1)),
48            (MergeOverflow $ovf1, $ovf2))>;
49
50// addi(subi(x, c0), c1) -> addi(x, c1 - c0)
51def AddISubConstantRHS :
52    Pat<(Arith_AddIOp:$res
53          (Arith_SubIOp $x, (ConstantLikeMatcher APIntAttr:$c0), $ovf1),
54          (ConstantLikeMatcher APIntAttr:$c1), $ovf2),
55        (Arith_AddIOp $x, (Arith_ConstantOp (SubIntAttrs $res, $c1, $c0)),
56            (MergeOverflow $ovf1, $ovf2))>;
57
58// addi(subi(c0, x), c1) -> subi(c0 + c1, x)
59def AddISubConstantLHS :
60    Pat<(Arith_AddIOp:$res
61          (Arith_SubIOp (ConstantLikeMatcher APIntAttr:$c0), $x, $ovf1),
62          (ConstantLikeMatcher APIntAttr:$c1), $ovf2),
63        (Arith_SubIOp (Arith_ConstantOp (AddIntAttrs $res, $c0, $c1)), $x,
64            (MergeOverflow $ovf1, $ovf2))>;
65
66def IsScalarOrSplatNegativeOne :
67    Constraint<And<[
68      CPred<"succeeded(getIntOrSplatIntValue($0))">,
69      CPred<"getIntOrSplatIntValue($0)->isAllOnes()">]>>;
70
71// addi(x, muli(y, -1)) -> subi(x, y)
72def AddIMulNegativeOneRhs :
73    Pat<(Arith_AddIOp
74           $x,
75           (Arith_MulIOp $y, (ConstantLikeMatcher AnyAttr:$c0), $ovf1), $ovf2),
76        (Arith_SubIOp $x, $y, DefOverflow), // TODO: overflow flags
77        [(IsScalarOrSplatNegativeOne $c0)]>;
78
79// addi(muli(x, -1), y) -> subi(y, x)
80def AddIMulNegativeOneLhs :
81    Pat<(Arith_AddIOp
82           (Arith_MulIOp $x, (ConstantLikeMatcher AnyAttr:$c0), $ovf1),
83           $y, $ovf2),
84        (Arith_SubIOp $y, $x, DefOverflow), // TODO: overflow flags
85        [(IsScalarOrSplatNegativeOne $c0)]>;
86
87// muli(muli(x, c0), c1) -> muli(x, c0 * c1)
88def MulIMulIConstant :
89    Pat<(Arith_MulIOp:$res
90          (Arith_MulIOp $x, (ConstantLikeMatcher APIntAttr:$c0), $ovf1),
91          (ConstantLikeMatcher APIntAttr:$c1), $ovf2),
92        (Arith_MulIOp $x, (Arith_ConstantOp (MulIntAttrs $res, $c0, $c1)),
93            (MergeOverflow $ovf1, $ovf2))>;
94
95//===----------------------------------------------------------------------===//
96// AddUIExtendedOp
97//===----------------------------------------------------------------------===//
98
99// addui_extended(x, y) -> [addi(x, y), x], when the `overflow` result has no
100// uses. Since the 'overflow' result is unused, any replacement value will do.
101def AddUIExtendedToAddI:
102    Pattern<(Arith_AddUIExtendedOp:$res $x, $y),
103             [(Arith_AddIOp $x, $y, DefOverflow), (replaceWithValue $x)],
104             [(Constraint<CPred<"$0.getUses().empty()">> $res__1)]>;
105
106//===----------------------------------------------------------------------===//
107// SubIOp
108//===----------------------------------------------------------------------===//
109
110// subi(addi(x, c0), c1) -> addi(x, c0 - c1)
111def SubIRHSAddConstant :
112    Pat<(Arith_SubIOp:$res
113          (Arith_AddIOp $x, (ConstantLikeMatcher APIntAttr:$c0), $ovf1),
114          (ConstantLikeMatcher APIntAttr:$c1), $ovf2),
115        (Arith_AddIOp $x, (Arith_ConstantOp (SubIntAttrs $res, $c0, $c1)),
116            DefOverflow)>; // TODO: overflow flags
117
118// subi(c1, addi(x, c0)) -> subi(c1 - c0, x)
119def SubILHSAddConstant :
120    Pat<(Arith_SubIOp:$res
121          (ConstantLikeMatcher APIntAttr:$c1),
122          (Arith_AddIOp $x, (ConstantLikeMatcher APIntAttr:$c0), $ovf1), $ovf2),
123        (Arith_SubIOp (Arith_ConstantOp (SubIntAttrs $res, $c1, $c0)), $x,
124            (MergeOverflow $ovf1, $ovf2))>;
125
126// subi(subi(x, c0), c1) -> subi(x, c0 + c1)
127def SubIRHSSubConstantRHS :
128    Pat<(Arith_SubIOp:$res
129          (Arith_SubIOp $x, (ConstantLikeMatcher APIntAttr:$c0), $ovf1),
130          (ConstantLikeMatcher APIntAttr:$c1), $ovf2),
131        (Arith_SubIOp $x, (Arith_ConstantOp (AddIntAttrs $res, $c0, $c1)),
132            (MergeOverflow $ovf1, $ovf2))>;
133
134// subi(subi(c0, x), c1) -> subi(c0 - c1, x)
135def SubIRHSSubConstantLHS :
136    Pat<(Arith_SubIOp:$res
137          (Arith_SubIOp (ConstantLikeMatcher APIntAttr:$c0), $x, $ovf1),
138          (ConstantLikeMatcher APIntAttr:$c1), $ovf2),
139        (Arith_SubIOp (Arith_ConstantOp (SubIntAttrs $res, $c0, $c1)), $x,
140            (MergeOverflow $ovf1, $ovf2))>;
141
142// subi(c1, subi(x, c0)) -> subi(c0 + c1, x)
143def SubILHSSubConstantRHS :
144    Pat<(Arith_SubIOp:$res
145          (ConstantLikeMatcher APIntAttr:$c1),
146          (Arith_SubIOp $x, (ConstantLikeMatcher APIntAttr:$c0), $ovf1), $ovf2),
147        (Arith_SubIOp (Arith_ConstantOp (AddIntAttrs $res, $c0, $c1)), $x,
148            (MergeOverflow $ovf1, $ovf2))>;
149
150// subi(c1, subi(c0, x)) -> addi(x, c1 - c0)
151def SubILHSSubConstantLHS :
152    Pat<(Arith_SubIOp:$res
153          (ConstantLikeMatcher APIntAttr:$c1),
154          (Arith_SubIOp (ConstantLikeMatcher APIntAttr:$c0), $x, $ovf1), $ovf2),
155        (Arith_AddIOp $x, (Arith_ConstantOp (SubIntAttrs $res, $c1, $c0)),
156            (MergeOverflow $ovf1, $ovf2))>;
157
158// subi(subi(a, b), a) -> subi(0, b)
159def SubISubILHSRHSLHS :
160    Pat<(Arith_SubIOp:$res (Arith_SubIOp $x, $y, $ovf1), $x, $ovf2),
161        (Arith_SubIOp (Arith_ConstantOp (GetZeroAttr $y)), $y,
162            (MergeOverflow $ovf1, $ovf2))>;
163
164//===----------------------------------------------------------------------===//
165// MulSIExtendedOp
166//===----------------------------------------------------------------------===//
167
168// mulsi_extended(x, y) -> [muli(x, y), x], when the `high` result is unused.
169// Since the `high` result it not used, any replacement value will do.
170def MulSIExtendedToMulI :
171    Pattern<(Arith_MulSIExtendedOp:$res $x, $y),
172        [(Arith_MulIOp $x, $y, DefOverflow), (replaceWithValue $x)],
173        [(Constraint<CPred<"$0.getUses().empty()">> $res__1)]>;
174
175
176def IsScalarOrSplatOne :
177    Constraint<And<[
178      CPred<"succeeded(getIntOrSplatIntValue($0))">,
179      CPred<"getIntOrSplatIntValue($0)->isStrictlyPositive()">,
180      CPred<"*getIntOrSplatIntValue($0) == 1">]>>;
181
182// mulsi_extended(x, 1) -> [x, extsi(cmpi slt, x, 0)]
183def MulSIExtendedRHSOne :
184    Pattern<(Arith_MulSIExtendedOp $x, (ConstantLikeMatcher AnyAttr:$c1)),
185            [(replaceWithValue $x),
186             (Arith_ExtSIOp(Arith_CmpIOp
187                ConstantEnumCase<Arith_CmpIPredicateAttr, "slt">,
188                $x,
189                (Arith_ConstantOp (GetZeroAttr $x))))],
190            [(IsScalarOrSplatOne $c1)]>;
191
192//===----------------------------------------------------------------------===//
193// MulUIExtendedOp
194//===----------------------------------------------------------------------===//
195
196// mului_extended(x, y) -> [muli(x, y), x], when the `high` result is unused.
197// Since the `high` result it not used, any replacement value will do.
198def MulUIExtendedToMulI :
199    Pattern<(Arith_MulUIExtendedOp:$res $x, $y),
200        [(Arith_MulIOp $x, $y, DefOverflow), (replaceWithValue $x)],
201        [(Constraint<CPred<"$0.getUses().empty()">> $res__1)]>;
202
203//===----------------------------------------------------------------------===//
204// XOrIOp
205//===----------------------------------------------------------------------===//
206
207// xori is commutative and will be canonicalized to have its constants appear
208// as the second operand.
209
210// not(cmpi(pred, a, b)) -> cmpi(~pred, a, b), where not(x) is xori(x, 1)
211def InvertPredicate : NativeCodeCall<"invertPredicate($0)">;
212def XOrINotCmpI :
213    Pat<(Arith_XOrIOp
214          (Arith_CmpIOp $pred, $a, $b),
215          (ConstantLikeMatcher ConstantAttr<I1Attr, "1">)),
216        (Arith_CmpIOp (InvertPredicate $pred), $a, $b)>;
217
218// xor extui(x), extui(y) -> extui(xor(x,y))
219def XOrIOfExtUI :
220    Pat<(Arith_XOrIOp (Arith_ExtUIOp $x), (Arith_ExtUIOp $y)), (Arith_ExtUIOp (Arith_XOrIOp $x, $y)),
221      [(Constraint<CPred<"$0.getType() == $1.getType()">> $x, $y)]>;
222
223// xor extsi(x), extsi(y) -> extsi(xor(x,y))
224def XOrIOfExtSI :
225    Pat<(Arith_XOrIOp (Arith_ExtSIOp $x), (Arith_ExtSIOp $y)), (Arith_ExtSIOp (Arith_XOrIOp $x, $y)),
226      [(Constraint<CPred<"$0.getType() == $1.getType()">> $x, $y)]>;
227
228//===----------------------------------------------------------------------===//
229// CmpIOp
230//===----------------------------------------------------------------------===//
231
232// cmpi(== or !=, a ext iNN, b ext iNN) == cmpi(== or !=, a, b)
233def CmpIExtSI :
234    Pat<(Arith_CmpIOp $pred,
235          (Arith_ExtSIOp $a),
236          (Arith_ExtSIOp $b)),
237        (Arith_CmpIOp $pred, $a, $b),
238        [(Constraint<CPred<"$0.getType() == $1.getType()">> $a, $b),
239         (Constraint<
240            CPred<"$0.getValue() == arith::CmpIPredicate::eq || "
241                  "$0.getValue() == arith::CmpIPredicate::ne">> $pred)]>;
242
243// cmpi(== or !=, a ext iNN, b ext iNN) == cmpi(== or !=, a, b)
244def CmpIExtUI :
245    Pat<(Arith_CmpIOp $pred,
246          (Arith_ExtUIOp $a),
247          (Arith_ExtUIOp $b)),
248        (Arith_CmpIOp $pred, $a, $b),
249        [(Constraint<CPred<"$0.getType() == $1.getType()">> $a, $b),
250         (Constraint<
251            CPred<"$0.getValue() == arith::CmpIPredicate::eq || "
252                  "$0.getValue() == arith::CmpIPredicate::ne">> $pred)]>;
253
254//===----------------------------------------------------------------------===//
255// SelectOp
256//===----------------------------------------------------------------------===//
257
258// select(not(pred), a, b) => select(pred, b, a)
259def SelectNotCond :
260    Pat<(SelectOp (Arith_XOrIOp $pred, (ConstantLikeMatcher APIntAttr:$ones)), $a, $b),
261        (SelectOp $pred, $b, $a),
262        [(IsScalarOrSplatNegativeOne $ones)]>;
263
264// select(pred, select(pred, a, b), c) => select(pred, a, c)
265def RedundantSelectTrue :
266    Pat<(SelectOp $pred, (SelectOp $pred, $a, $b), $c),
267        (SelectOp $pred, $a, $c)>;
268
269// select(pred, a, select(pred, b, c)) => select(pred, a, c)
270def RedundantSelectFalse :
271    Pat<(SelectOp $pred, $a, (SelectOp $pred, $b, $c)),
272        (SelectOp $pred, $a, $c)>;
273
274// select(pred, false, true) => not(pred)
275def SelectI1ToNot :
276    Pat<(SelectOp $pred,
277                  (ConstantLikeMatcher ConstantAttr<I1Attr, "0">),
278                  (ConstantLikeMatcher ConstantAttr<I1Attr, "1">)),
279        (Arith_XOrIOp $pred, (Arith_ConstantOp ConstantAttr<I1Attr, "1">))>;
280
281//===----------------------------------------------------------------------===//
282// IndexCastOp
283//===----------------------------------------------------------------------===//
284
285// index_cast(index_cast(x)) -> x, if dstType == srcType.
286def IndexCastOfIndexCast :
287    Pat<(Arith_IndexCastOp:$res (Arith_IndexCastOp $x)),
288        (replaceWithValue $x),
289        [(Constraint<CPred<"$0.getType() == $1.getType()">> $res, $x)]>;
290
291// index_cast(extsi(x)) -> index_cast(x)
292def IndexCastOfExtSI :
293    Pat<(Arith_IndexCastOp (Arith_ExtSIOp $x)), (Arith_IndexCastOp $x)>;
294
295//===----------------------------------------------------------------------===//
296// IndexCastUIOp
297//===----------------------------------------------------------------------===//
298
299// index_castui(index_castui(x)) -> x, if dstType == srcType.
300def IndexCastUIOfIndexCastUI :
301    Pat<(Arith_IndexCastUIOp:$res (Arith_IndexCastUIOp $x)),
302        (replaceWithValue $x),
303        [(Constraint<CPred<"$0.getType() == $1.getType()">> $res, $x)]>;
304
305// index_castui(extui(x)) -> index_castui(x)
306def IndexCastUIOfExtUI :
307    Pat<(Arith_IndexCastUIOp (Arith_ExtUIOp $x)), (Arith_IndexCastUIOp $x)>;
308
309
310//===----------------------------------------------------------------------===//
311// BitcastOp
312//===----------------------------------------------------------------------===//
313
314// bitcast(bitcast(x)) -> x
315def BitcastOfBitcast :
316    Pat<(Arith_BitcastOp (Arith_BitcastOp $x)), (replaceWithValue $x)>;
317
318//===----------------------------------------------------------------------===//
319// ExtSIOp
320//===----------------------------------------------------------------------===//
321
322// extsi(extui(x iN : iM) : iL) -> extui(x : iL)
323def ExtSIOfExtUI :
324    Pat<(Arith_ExtSIOp (Arith_ExtUIOp $x)), (Arith_ExtUIOp $x)>;
325
326//===----------------------------------------------------------------------===//
327// AndIOp
328//===----------------------------------------------------------------------===//
329
330// and extui(x), extui(y) -> extui(and(x,y))
331def AndOfExtUI :
332    Pat<(Arith_AndIOp (Arith_ExtUIOp $x), (Arith_ExtUIOp $y)),
333        (Arith_ExtUIOp (Arith_AndIOp $x, $y)),
334        [(Constraint<CPred<"$0.getType() == $1.getType()">> $x, $y)]>;
335
336// and extsi(x), extsi(y) -> extsi(and(x,y))
337def AndOfExtSI :
338    Pat<(Arith_AndIOp (Arith_ExtSIOp $x), (Arith_ExtSIOp $y)),
339        (Arith_ExtSIOp (Arith_AndIOp $x, $y)),
340        [(Constraint<CPred<"$0.getType() == $1.getType()">> $x, $y)]>;
341
342//===----------------------------------------------------------------------===//
343// OrIOp
344//===----------------------------------------------------------------------===//
345
346// or extui(x), extui(y) -> extui(or(x,y))
347def OrOfExtUI :
348    Pat<(Arith_OrIOp (Arith_ExtUIOp $x), (Arith_ExtUIOp $y)),
349        (Arith_ExtUIOp (Arith_OrIOp $x, $y)),
350        [(Constraint<CPred<"$0.getType() == $1.getType()">> $x, $y)]>;
351
352// or extsi(x), extsi(y) -> extsi(or(x,y))
353def OrOfExtSI :
354    Pat<(Arith_OrIOp (Arith_ExtSIOp $x), (Arith_ExtSIOp $y)),
355        (Arith_ExtSIOp (Arith_OrIOp $x, $y)),
356        [(Constraint<CPred<"$0.getType() == $1.getType()">> $x, $y)]>;
357
358//===----------------------------------------------------------------------===//
359// TruncIOp
360//===----------------------------------------------------------------------===//
361
362def ValuesWithSameType :
363    Constraint<
364      CPred<"llvm::all_equal({$0.getType(), $1.getType(), $2.getType()})">>;
365
366def ValueWiderThan :
367    Constraint<And<[
368      CPred<"getScalarOrElementWidth($0) > getScalarOrElementWidth($1)">,
369      CPred<"getScalarOrElementWidth($1) > 0">]>>;
370
371def TruncationMatchesShiftAmount :
372    Constraint<And<[
373      CPred<"succeeded(getIntOrSplatIntValue($2))">,
374      CPred<"(getScalarOrElementWidth($0) - getScalarOrElementWidth($1)) == "
375              "*getIntOrSplatIntValue($2)">]>>;
376
377// trunci(extsi(x)) -> extsi(x), when only the sign-extension bits are truncated
378def TruncIExtSIToExtSI :
379    Pat<(Arith_TruncIOp:$tr (Arith_ExtSIOp:$ext $x)),
380        (Arith_ExtSIOp $x),
381        [(ValueWiderThan $ext, $tr),
382         (ValueWiderThan $tr, $x)]>;
383
384// trunci(extui(x)) -> extui(x), when only the zero-extension bits are truncated
385def TruncIExtUIToExtUI :
386    Pat<(Arith_TruncIOp:$tr (Arith_ExtUIOp:$ext $x)),
387        (Arith_ExtUIOp $x),
388        [(ValueWiderThan $ext, $tr),
389         (ValueWiderThan $tr, $x)]>;
390
391// trunci(shrsi(x, c)) -> trunci(shrui(x, c))
392def TruncIShrSIToTrunciShrUI :
393    Pat<(Arith_TruncIOp:$tr
394          (Arith_ShRSIOp $x, (ConstantLikeMatcher TypedAttrInterface:$c0))),
395        (Arith_TruncIOp (Arith_ShRUIOp $x, (Arith_ConstantOp (cast<"TypedAttr"> $c0)))),
396        [(TruncationMatchesShiftAmount $x, $tr, $c0)]>;
397
398// trunci(shrui(mul(sext(x), sext(y)), c)) -> mulsi_extended(x, y)
399def TruncIShrUIMulIToMulSIExtended :
400    Pat<(Arith_TruncIOp:$tr (Arith_ShRUIOp
401                              (Arith_MulIOp:$mul
402                                (Arith_ExtSIOp $x), (Arith_ExtSIOp $y), $ovf1),
403                              (ConstantLikeMatcher AnyAttr:$c0))),
404        (Arith_MulSIExtendedOp:$res__1 $x, $y),
405      [(ValuesWithSameType $tr, $x, $y),
406       (ValueWiderThan $mul, $x),
407       (TruncationMatchesShiftAmount $mul, $x, $c0)]>;
408
409// trunci(shrui(mul(zext(x), zext(y)), c)) -> mului_extended(x, y)
410def TruncIShrUIMulIToMulUIExtended :
411    Pat<(Arith_TruncIOp:$tr (Arith_ShRUIOp
412                              (Arith_MulIOp:$mul
413                                (Arith_ExtUIOp $x), (Arith_ExtUIOp $y), $ovf1),
414                              (ConstantLikeMatcher AnyAttr:$c0))),
415        (Arith_MulUIExtendedOp:$res__1 $x, $y),
416      [(ValuesWithSameType $tr, $x, $y),
417       (ValueWiderThan $mul, $x),
418       (TruncationMatchesShiftAmount $mul, $x, $c0)]>;
419
420//===----------------------------------------------------------------------===//
421// MulFOp
422//===----------------------------------------------------------------------===//
423
424// mulf(negf(x), negf(y)) -> mulf(x,y)
425// (retain fastmath flags of original mulf)
426def MulFOfNegF :
427    Pat<(Arith_MulFOp (Arith_NegFOp $x, $_), (Arith_NegFOp $y, $_), $fmf),
428        (Arith_MulFOp $x, $y, $fmf),
429        [(Constraint<CPred<"$0.getType() == $1.getType()">> $x, $y)]>;
430
431//===----------------------------------------------------------------------===//
432// DivFOp
433//===----------------------------------------------------------------------===//
434
435// divf(negf(x), negf(y)) -> divf(x,y)
436// (retain fastmath flags of original divf)
437def DivFOfNegF :
438    Pat<(Arith_DivFOp (Arith_NegFOp $x, $_), (Arith_NegFOp $y, $_), $fmf),
439        (Arith_DivFOp $x, $y, $fmf),
440        [(Constraint<CPred<"$0.getType() == $1.getType()">> $x, $y)]>;
441
442#endif // ARITH_PATTERNS
443