/
Combine.td
403 lines (351 loc) · 16.8 KB
/
Combine.td
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
//===- Combine.td - Combine rule definitions ---------------*- tablegen -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Declare GlobalISel combine rules and provide mechanisms to opt-out.
//
//===----------------------------------------------------------------------===//
// Common base class for GICombineRule and GICombineGroup.
class GICombine {
// See GICombineGroup. We only declare it here to make the tablegen pass
// simpler.
list<GICombine> Rules = ?;
}
// A group of combine rules that can be added to a GICombiner or another group.
class GICombineGroup<list<GICombine> rules> : GICombine {
// The rules contained in this group. The rules in a group are flattened into
// a single list and sorted into whatever order is most efficient. However,
// they will never be re-ordered such that behaviour differs from the
// specified order. It is therefore possible to use the order of rules in this
// list to describe priorities.
let Rules = rules;
}
class GICombinerHelperArg<string type, string name> {
string Type = type;
string Name = name;
}
// Declares a combiner helper class
class GICombinerHelper<string classname, list<GICombine> rules>
: GICombineGroup<rules> {
// The class name to use in the generated output.
string Classname = classname;
// The name of a run-time compiler option that will be generated to disable
// specific rules within this combiner.
string DisableRuleOption = ?;
// The state class to inherit from (if any). The generated helper will inherit
// from this class and will forward arguments to its constructors.
string StateClass = "";
// Any additional arguments that should be appended to the tryCombine*().
list<GICombinerHelperArg> AdditionalArguments =
[GICombinerHelperArg<"CombinerHelper &", "Helper">];
}
class GICombineRule<dag defs, dag match, dag apply> : GICombine {
/// Defines the external interface of the match rule. This includes:
/// * The names of the root nodes (requires at least one)
/// See GIDefKind for details.
dag Defs = defs;
/// Defines the things which must be true for the pattern to match
/// See GIMatchKind for details.
dag Match = match;
/// Defines the things which happen after the decision is made to apply a
/// combine rule.
/// See GIApplyKind for details.
dag Apply = apply;
}
/// The operator at the root of a GICombineRule.Defs dag.
def defs;
/// All arguments of the defs operator must be subclasses of GIDefKind or
/// sub-dags whose operator is GIDefKindWithArgs.
class GIDefKind;
class GIDefKindWithArgs;
/// Declare a root node. There must be at least one of these in every combine
/// rule.
/// TODO: The plan is to elide `root` definitions and determine it from the DAG
/// itself with an overide for situations where the usual determination
/// is incorrect.
def root : GIDefKind;
/// Declares data that is passed from the match stage to the apply stage.
class GIDefMatchData<string type> : GIDefKind {
/// A C++ type name indicating the storage type.
string Type = type;
}
def extending_load_matchdata : GIDefMatchData<"PreferredTuple">;
def indexed_load_store_matchdata : GIDefMatchData<"IndexedLoadStoreMatchInfo">;
def instruction_steps_matchdata: GIDefMatchData<"InstructionStepsMatchInfo">;
/// The operator at the root of a GICombineRule.Match dag.
def match;
/// All arguments of the match operator must be either:
/// * A subclass of GIMatchKind
/// * A subclass of GIMatchKindWithArgs
/// * A subclass of Instruction
/// * A MIR code block (deprecated)
/// The GIMatchKind and GIMatchKindWithArgs cases are described in more detail
/// in their definitions below.
/// For the Instruction case, these are collected into a DAG where operand names
/// that occur multiple times introduce edges.
class GIMatchKind;
class GIMatchKindWithArgs;
/// In lieu of having proper macro support. Trivial one-off opcode checks can be
/// performed with this.
def wip_match_opcode : GIMatchKindWithArgs;
/// The operator at the root of a GICombineRule.Apply dag.
def apply;
/// All arguments of the apply operator must be subclasses of GIApplyKind, or
/// sub-dags whose operator is GIApplyKindWithArgs, or an MIR block
/// (deprecated).
class GIApplyKind;
class GIApplyKindWithArgs;
def copy_prop : GICombineRule<
(defs root:$d),
(match (COPY $d, $s):$mi,
[{ return Helper.matchCombineCopy(*${mi}); }]),
(apply [{ Helper.applyCombineCopy(*${mi}); }])>;
def extending_loads : GICombineRule<
(defs root:$root, extending_load_matchdata:$matchinfo),
(match (wip_match_opcode G_LOAD, G_SEXTLOAD, G_ZEXTLOAD):$root,
[{ return Helper.matchCombineExtendingLoads(*${root}, ${matchinfo}); }]),
(apply [{ Helper.applyCombineExtendingLoads(*${root}, ${matchinfo}); }])>;
def combines_for_extload: GICombineGroup<[extending_loads]>;
def sext_trunc_sextload : GICombineRule<
(defs root:$d),
(match (wip_match_opcode G_SEXT_INREG):$d,
[{ return Helper.matchSextTruncSextLoad(*${d}); }]),
(apply [{ Helper.applySextTruncSextLoad(*${d}); }])>;
def sext_inreg_of_load_matchdata : GIDefMatchData<"std::tuple<Register, unsigned>">;
def sext_inreg_of_load : GICombineRule<
(defs root:$root, sext_inreg_of_load_matchdata:$matchinfo),
(match (wip_match_opcode G_SEXT_INREG):$root,
[{ return Helper.matchSextInRegOfLoad(*${root}, ${matchinfo}); }]),
(apply [{ return Helper.applySextInRegOfLoad(*${root}, ${matchinfo}); }])>;
def combine_indexed_load_store : GICombineRule<
(defs root:$root, indexed_load_store_matchdata:$matchinfo),
(match (wip_match_opcode G_LOAD, G_SEXTLOAD, G_ZEXTLOAD, G_STORE):$root,
[{ return Helper.matchCombineIndexedLoadStore(*${root}, ${matchinfo}); }]),
(apply [{ Helper.applyCombineIndexedLoadStore(*${root}, ${matchinfo}); }])>;
// FIXME: Is there a reason this wasn't in tryCombine? I've left it out of
// all_combines because it wasn't there.
def elide_br_by_inverting_cond : GICombineRule<
(defs root:$root),
(match (wip_match_opcode G_BR):$root,
[{ return Helper.matchElideBrByInvertingCond(*${root}); }]),
(apply [{ Helper.applyElideBrByInvertingCond(*${root}); }])>;
def ptr_add_immed_matchdata : GIDefMatchData<"PtrAddChain">;
def ptr_add_immed_chain : GICombineRule<
(defs root:$d, ptr_add_immed_matchdata:$matchinfo),
(match (wip_match_opcode G_PTR_ADD):$d,
[{ return Helper.matchPtrAddImmedChain(*${d}, ${matchinfo}); }]),
(apply [{ Helper.applyPtrAddImmedChain(*${d}, ${matchinfo}); }])>;
def mul_to_shl_matchdata : GIDefMatchData<"unsigned">;
def mul_to_shl : GICombineRule<
(defs root:$d, mul_to_shl_matchdata:$matchinfo),
(match (G_MUL $d, $op1, $op2):$mi,
[{ return Helper.matchCombineMulToShl(*${mi}, ${matchinfo}); }]),
(apply [{ Helper.applyCombineMulToShl(*${mi}, ${matchinfo}); }])>;
// shl ([asz]ext x), y => zext (shl x, y), if shift does not overflow int
def reduce_shl_of_extend_matchdata : GIDefMatchData<"RegisterImmPair">;
def reduce_shl_of_extend : GICombineRule<
(defs root:$dst, reduce_shl_of_extend_matchdata:$matchinfo),
(match (G_SHL $dst, $src0, $src1):$mi,
[{ return Helper.matchCombineShlOfExtend(*${mi}, ${matchinfo}); }]),
(apply [{ Helper.applyCombineShlOfExtend(*${mi}, ${matchinfo}); }])>;
// [us]itofp(undef) = 0, because the result value is bounded.
def undef_to_fp_zero : GICombineRule<
(defs root:$root),
(match (wip_match_opcode G_UITOFP, G_SITOFP):$root,
[{ return Helper.matchAnyExplicitUseIsUndef(*${root}); }]),
(apply [{ Helper.replaceInstWithFConstant(*${root}, 0.0); }])>;
def undef_to_int_zero: GICombineRule<
(defs root:$root),
(match (wip_match_opcode G_AND, G_MUL):$root,
[{ return Helper.matchAnyExplicitUseIsUndef(*${root}); }]),
(apply [{ Helper.replaceInstWithConstant(*${root}, 0); }])>;
def undef_to_negative_one: GICombineRule<
(defs root:$root),
(match (wip_match_opcode G_OR):$root,
[{ return Helper.matchAnyExplicitUseIsUndef(*${root}); }]),
(apply [{ Helper.replaceInstWithConstant(*${root}, -1); }])>;
// Instructions where if any source operand is undef, the instruction can be
// replaced with undef.
def propagate_undef_any_op: GICombineRule<
(defs root:$root),
(match (wip_match_opcode G_ADD, G_FPTOSI, G_FPTOUI, G_SUB, G_XOR):$root,
[{ return Helper.matchAnyExplicitUseIsUndef(*${root}); }]),
(apply [{ Helper.replaceInstWithUndef(*${root}); }])>;
// Instructions where if all source operands are undef, the instruction can be
// replaced with undef.
def propagate_undef_all_ops: GICombineRule<
(defs root:$root),
(match (wip_match_opcode G_SHUFFLE_VECTOR):$root,
[{ return Helper.matchAllExplicitUsesAreUndef(*${root}); }]),
(apply [{ Helper.replaceInstWithUndef(*${root}); }])>;
// Replace a G_SHUFFLE_VECTOR with an undef mask with a G_IMPLICIT_DEF.
def propagate_undef_shuffle_mask: GICombineRule<
(defs root:$root),
(match (wip_match_opcode G_SHUFFLE_VECTOR):$root,
[{ return Helper.matchUndefShuffleVectorMask(*${root}); }]),
(apply [{ Helper.replaceInstWithUndef(*${root}); }])>;
// Fold (cond ? x : x) -> x
def select_same_val: GICombineRule<
(defs root:$root),
(match (wip_match_opcode G_SELECT):$root,
[{ return Helper.matchSelectSameVal(*${root}); }]),
(apply [{ return Helper.replaceSingleDefInstWithOperand(*${root}, 2); }])
>;
// Fold (undef ? x : y) -> y
def select_undef_cmp: GICombineRule<
(defs root:$root),
(match (wip_match_opcode G_SELECT):$root,
[{ return Helper.matchUndefSelectCmp(*${root}); }]),
(apply [{ return Helper.replaceSingleDefInstWithOperand(*${root}, 2); }])
>;
// Fold (true ? x : y) -> x
// Fold (false ? x : y) -> y
def select_constant_cmp_matchdata : GIDefMatchData<"unsigned">;
def select_constant_cmp: GICombineRule<
(defs root:$root, select_constant_cmp_matchdata:$matchinfo),
(match (wip_match_opcode G_SELECT):$root,
[{ return Helper.matchConstantSelectCmp(*${root}, ${matchinfo}); }]),
(apply [{ return Helper.replaceSingleDefInstWithOperand(*${root}, ${matchinfo}); }])
>;
// Fold x op 0 -> x
def right_identity_zero: GICombineRule<
(defs root:$root),
(match (wip_match_opcode G_SUB, G_ADD, G_OR, G_XOR, G_SHL, G_ASHR, G_LSHR):$root,
[{ return Helper.matchConstantOp(${root}->getOperand(2), 0); }]),
(apply [{ return Helper.replaceSingleDefInstWithOperand(*${root}, 1); }])
>;
// Fold (x op x) - > x
def binop_same_val: GICombineRule<
(defs root:$root),
(match (wip_match_opcode G_AND, G_OR):$root,
[{ return Helper.matchBinOpSameVal(*${root}); }]),
(apply [{ return Helper.replaceSingleDefInstWithOperand(*${root}, 1); }])
>;
// Fold (0 op x) - > 0
def binop_left_to_zero: GICombineRule<
(defs root:$root),
(match (wip_match_opcode G_SDIV, G_UDIV, G_SREM, G_UREM):$root,
[{ return Helper.matchOperandIsZero(*${root}, 1); }]),
(apply [{ return Helper.replaceSingleDefInstWithOperand(*${root}, 1); }])
>;
// Fold (x op 0) - > 0
def binop_right_to_zero: GICombineRule<
(defs root:$root),
(match (wip_match_opcode G_MUL):$root,
[{ return Helper.matchOperandIsZero(*${root}, 2); }]),
(apply [{ return Helper.replaceSingleDefInstWithOperand(*${root}, 2); }])
>;
// Erase stores of undef values.
def erase_undef_store : GICombineRule<
(defs root:$root),
(match (wip_match_opcode G_STORE):$root,
[{ return Helper.matchUndefStore(*${root}); }]),
(apply [{ return Helper.eraseInst(*${root}); }])
>;
def simplify_add_to_sub_matchinfo: GIDefMatchData<"std::tuple<Register, Register>">;
def simplify_add_to_sub: GICombineRule <
(defs root:$root, simplify_add_to_sub_matchinfo:$info),
(match (wip_match_opcode G_ADD):$root,
[{ return Helper.matchSimplifyAddToSub(*${root}, ${info}); }]),
(apply [{ return Helper.applySimplifyAddToSub(*${root}, ${info});}])
>;
// Fold int2ptr(ptr2int(x)) -> x
def p2i_to_i2p_matchinfo: GIDefMatchData<"Register">;
def p2i_to_i2p: GICombineRule<
(defs root:$root, p2i_to_i2p_matchinfo:$info),
(match (wip_match_opcode G_INTTOPTR):$root,
[{ return Helper.matchCombineI2PToP2I(*${root}, ${info}); }]),
(apply [{ return Helper.applyCombineI2PToP2I(*${root}, ${info}); }])
>;
// Fold ptr2int(int2ptr(x)) -> x
def i2p_to_p2i_matchinfo: GIDefMatchData<"Register">;
def i2p_to_p2i: GICombineRule<
(defs root:$root, i2p_to_p2i_matchinfo:$info),
(match (wip_match_opcode G_PTRTOINT):$root,
[{ return Helper.matchCombineP2IToI2P(*${root}, ${info}); }]),
(apply [{ return Helper.applyCombineP2IToI2P(*${root}, ${info}); }])
>;
// Fold add ptrtoint(x), y -> ptrtoint (ptr_add x), y
def add_p2i_to_ptradd_matchinfo : GIDefMatchData<"std::pair<Register, bool>">;
def add_p2i_to_ptradd : GICombineRule<
(defs root:$root, add_p2i_to_ptradd_matchinfo:$info),
(match (wip_match_opcode G_ADD):$root,
[{ return Helper.matchCombineAddP2IToPtrAdd(*${root}, ${info}); }]),
(apply [{ return Helper.applyCombineAddP2IToPtrAdd(*${root}, ${info}); }])
>;
// Simplify: (logic_op (op x...), (op y...)) -> (op (logic_op x, y))
def hoist_logic_op_with_same_opcode_hands: GICombineRule <
(defs root:$root, instruction_steps_matchdata:$info),
(match (wip_match_opcode G_AND, G_OR, G_XOR):$root,
[{ return Helper.matchHoistLogicOpWithSameOpcodeHands(*${root}, ${info}); }]),
(apply [{ return Helper.applyBuildInstructionSteps(*${root}, ${info});}])
>;
// Fold ashr (shl x, C), C -> sext_inreg (C)
def shl_ashr_to_sext_inreg_matchinfo : GIDefMatchData<"std::tuple<Register, int64_t>">;
def shl_ashr_to_sext_inreg : GICombineRule<
(defs root:$root, shl_ashr_to_sext_inreg_matchinfo:$info),
(match (wip_match_opcode G_ASHR): $root,
[{ return Helper.matchAshrShlToSextInreg(*${root}, ${info}); }]),
(apply [{ return Helper.applyAshShlToSextInreg(*${root}, ${info});}])
>;
// Fold (x & mask) -> x when (x & mask) is known to equal x.
def and_trivial_mask_matchinfo : GIDefMatchData<"Register">;
def and_trivial_mask: GICombineRule <
(defs root:$root, and_trivial_mask_matchinfo:$matchinfo),
(match (wip_match_opcode G_AND):$root,
[{ return Helper.matchAndWithTrivialMask(*${root}, ${matchinfo}); }]),
(apply [{ return Helper.replaceSingleDefInstWithReg(*${root}, ${matchinfo}); }])
>;
// If the input is already sign extended, just drop the extension.
// sext_inreg x, K ->
// if computeNumSignBits(x) >= (x.getScalarSizeInBits() - K + 1)
def redundant_sext_inreg: GICombineRule <
(defs root:$root),
(match (wip_match_opcode G_SEXT_INREG):$root,
[{ return Helper.matchRedundantSExtInReg(*${root}); }]),
(apply [{ return Helper.replaceSingleDefInstWithOperand(*${root}, 1); }])
>;
// Fold (anyext (trunc x)) -> x if the source type is same as
// the destination type.
def anyext_trunc_fold_matchinfo : GIDefMatchData<"Register">;
def anyext_trunc_fold: GICombineRule <
(defs root:$root, anyext_trunc_fold_matchinfo:$matchinfo),
(match (wip_match_opcode G_ANYEXT):$root,
[{ return Helper.matchCombineAnyExtTrunc(*${root}, ${matchinfo}); }]),
(apply [{ return Helper.applyCombineAnyExtTrunc(*${root}, ${matchinfo}); }])
>;
// Fold ([asz]ext ([asz]ext x)) -> ([asz]ext x).
def ext_ext_fold_matchinfo : GIDefMatchData<"std::tuple<Register, unsigned>">;
def ext_ext_fold: GICombineRule <
(defs root:$root, ext_ext_fold_matchinfo:$matchinfo),
(match (wip_match_opcode G_ANYEXT, G_SEXT, G_ZEXT):$root,
[{ return Helper.matchCombineExtOfExt(*${root}, ${matchinfo}); }]),
(apply [{ return Helper.applyCombineExtOfExt(*${root}, ${matchinfo}); }])
>;
// FIXME: These should use the custom predicate feature once it lands.
def undef_combines : GICombineGroup<[undef_to_fp_zero, undef_to_int_zero,
undef_to_negative_one,
propagate_undef_any_op,
propagate_undef_all_ops,
propagate_undef_shuffle_mask,
erase_undef_store]>;
def identity_combines : GICombineGroup<[select_same_val, right_identity_zero,
binop_same_val, binop_left_to_zero,
binop_right_to_zero, p2i_to_i2p,
i2p_to_p2i, anyext_trunc_fold]>;
def known_bits_simplifications : GICombineGroup<[
and_trivial_mask, redundant_sext_inreg]>;
def width_reduction_combines : GICombineGroup<[reduce_shl_of_extend]>;
def select_combines : GICombineGroup<[select_undef_cmp, select_constant_cmp]>;
def trivial_combines : GICombineGroup<[copy_prop, mul_to_shl, add_p2i_to_ptradd]>;
def all_combines : GICombineGroup<[trivial_combines, ptr_add_immed_chain,
combines_for_extload, combine_indexed_load_store, undef_combines,
identity_combines, simplify_add_to_sub,
hoist_logic_op_with_same_opcode_hands,
shl_ashr_to_sext_inreg, sext_inreg_of_load,
width_reduction_combines, select_combines,
known_bits_simplifications, ext_ext_fold]>;