llvm/include/llvm/Target/GlobalISel/Combine.td

   1 //===- Combine.td - Combine rule definitions ---------------*- 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 // Declare GlobalISel combine rules and provide mechanisms to opt-out.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 // Common base class for GICombineRule and GICombineGroup.
  14 class GICombine {
  15   // See GICombineGroup. We only declare it here to make the tablegen pass
  16   // simpler.
  17   list<GICombine> Rules = ?;
  18 }
  19
  20 // A group of combine rules that can be added to a GICombiner or another group.
  21 class GICombineGroup<list<GICombine> rules> : GICombine {
  22   // The rules contained in this group. The rules in a group are flattened into
  23   // a single list and sorted into whatever order is most efficient. However,
  24   // they will never be re-ordered such that behaviour differs from the
  25   // specified order. It is therefore possible to use the order of rules in this
  26   // list to describe priorities.
  27   let Rules = rules;
  28 }
  29
  30 // Declares a combiner helper class
  31 class GICombinerHelper<string classname, list<GICombine> rules>
  32     : GICombineGroup<rules> {
  33   // The class name to use in the generated output.
  34   string Classname = classname;
  35   // The name of a run-time compiler option that will be generated to disable
  36   // specific rules within this combiner.
  37   string DisableRuleOption = ?;
  38 }
  39 class GICombineRule<dag defs, dag match, dag apply> : GICombine {
  40   /// Defines the external interface of the match rule. This includes:
  41   /// * The names of the root nodes (requires at least one)
  42   /// See GIDefKind for details.
  43   dag Defs = defs;
  44
  45   /// Defines the things which must be true for the pattern to match
  46   /// See GIMatchKind for details.
  47   dag Match = match;
  48
  49   /// Defines the things which happen after the decision is made to apply a
  50   /// combine rule.
  51   /// See GIApplyKind for details.
  52   dag Apply = apply;
  53 }
  54
  55 /// The operator at the root of a GICombineRule.Defs dag.
  56 def defs;
  57
  58 /// All arguments of the defs operator must be subclasses of GIDefKind or
  59 /// sub-dags whose operator is GIDefKindWithArgs.
  60 class GIDefKind;
  61 class GIDefKindWithArgs;
  62 /// Declare a root node. There must be at least one of these in every combine
  63 /// rule.
  64 /// TODO: The plan is to elide `root` definitions and determine it from the DAG
  65 ///       itself with an overide for situations where the usual determination
  66 ///       is incorrect.
  67 def root : GIDefKind;
  68
  69 /// Declares data that is passed from the match stage to the apply stage.
  70 class GIDefMatchData<string type> : GIDefKind {
  71   /// A C++ type name indicating the storage type.
  72   string Type = type;
  73 }
  74
  75 def extending_load_matchdata : GIDefMatchData<"PreferredTuple">;
  76 def indexed_load_store_matchdata : GIDefMatchData<"IndexedLoadStoreMatchInfo">;
  77
  78 /// The operator at the root of a GICombineRule.Match dag.
  79 def match;
  80 /// All arguments of the match operator must be either:
  81 /// * A subclass of GIMatchKind
  82 /// * A subclass of GIMatchKindWithArgs
  83 /// * A subclass of Instruction
  84 /// * A MIR code block (deprecated)
  85 /// The GIMatchKind and GIMatchKindWithArgs cases are described in more detail
  86 /// in their definitions below.
  87 /// For the Instruction case, these are collected into a DAG where operand names
  88 /// that occur multiple times introduce edges.
  89 class GIMatchKind;
  90 class GIMatchKindWithArgs;
  91
  92 /// In lieu of having proper macro support. Trivial one-off opcode checks can be
  93 /// performed with this.
  94 def wip_match_opcode : GIMatchKindWithArgs;
  95
  96 /// The operator at the root of a GICombineRule.Apply dag.
  97 def apply;
  98 /// All arguments of the apply operator must be subclasses of GIApplyKind, or
  99 /// sub-dags whose operator is GIApplyKindWithArgs, or an MIR block
 100 /// (deprecated).
 101 class GIApplyKind;
 102 class GIApplyKindWithArgs;
 103
 104 def copy_prop : GICombineRule<
 105   (defs root:$d),
 106   (match (COPY $d, $s):$mi,
 107          [{ return Helper.matchCombineCopy(*${mi}); }]),
 108   (apply [{ Helper.applyCombineCopy(*${mi}); }])>;
 109
 110 def extending_loads : GICombineRule<
 111   (defs root:$root, extending_load_matchdata:$matchinfo),
 112   (match (wip_match_opcode G_LOAD, G_SEXTLOAD, G_ZEXTLOAD):$root,
 113          [{ return Helper.matchCombineExtendingLoads(*${root}, ${matchinfo}); }]),
 114   (apply [{ Helper.applyCombineExtendingLoads(*${root}, ${matchinfo}); }])>;
 115 def combines_for_extload: GICombineGroup<[extending_loads]>;
 116
 117 def combine_indexed_load_store : GICombineRule<
 118   (defs root:$root, indexed_load_store_matchdata:$matchinfo),
 119   (match (wip_match_opcode G_LOAD, G_SEXTLOAD, G_ZEXTLOAD, G_STORE):$root,
 120          [{ return Helper.matchCombineIndexedLoadStore(*${root}, ${matchinfo}); }]),
 121   (apply [{ Helper.applyCombineIndexedLoadStore(*${root}, ${matchinfo}); }])>;
 122
 123 // FIXME: Is there a reason this wasn't in tryCombine? I've left it out of
 124 //        all_combines because it wasn't there.
 125 def elide_br_by_inverting_cond : GICombineRule<
 126   (defs root:$root),
 127   (match (wip_match_opcode G_BR):$root,
 128          [{ return Helper.matchElideBrByInvertingCond(*${root}); }]),
 129   (apply [{ Helper.applyElideBrByInvertingCond(*${root}); }])>;
 130
 131 def ptr_add_immed_matchdata : GIDefMatchData<"PtrAddChain">;
 132 def ptr_add_immed_chain : GICombineRule<
 133   (defs root:$d, ptr_add_immed_matchdata:$matchinfo),
 134   (match (wip_match_opcode G_PTR_ADD):$d,
 135          [{ return Helper.matchPtrAddImmedChain(*${d}, ${matchinfo}); }]),
 136   (apply [{ Helper.applyPtrAddImmedChain(*${d}, ${matchinfo}); }])>;
 137
 138 def mul_to_shl_matchdata : GIDefMatchData<"unsigned">;
 139 def mul_to_shl : GICombineRule<
 140   (defs root:$d, mul_to_shl_matchdata:$matchinfo),
 141   (match (G_MUL $d, $op1, $op2):$mi,
 142          [{ return Helper.matchCombineMulToShl(*${mi}, ${matchinfo}); }]),
 143   (apply [{ Helper.applyCombineMulToShl(*${mi}, ${matchinfo}); }])>;
 144
 145 // [us]itofp(undef) = 0, because the result value is bounded.
 146 def undef_to_fp_zero : GICombineRule<
 147   (defs root:$root),
 148   (match (wip_match_opcode G_UITOFP, G_SITOFP):$root,
 149          [{ return Helper.matchAnyExplicitUseIsUndef(*${root}); }]),
 150   (apply [{ Helper.replaceInstWithFConstant(*${root}, 0.0); }])>;
 151
 152 def undef_to_int_zero: GICombineRule<
 153   (defs root:$root),
 154   (match (wip_match_opcode G_AND, G_MUL):$root,
 155          [{ return Helper.matchAnyExplicitUseIsUndef(*${root}); }]),
 156   (apply [{ Helper.replaceInstWithConstant(*${root}, 0); }])>;
 157
 158 def undef_to_negative_one: GICombineRule<
 159   (defs root:$root),
 160   (match (wip_match_opcode G_OR):$root,
 161          [{ return Helper.matchAnyExplicitUseIsUndef(*${root}); }]),
 162   (apply [{ Helper.replaceInstWithConstant(*${root}, -1); }])>;
 163
 164 // Instructions where if any source operand is undef, the instruction can be
 165 // replaced with undef.
 166 def propagate_undef_any_op: GICombineRule<
 167   (defs root:$root),
 168   (match (wip_match_opcode G_ADD, G_FPTOSI, G_FPTOUI, G_SUB, G_XOR):$root,
 169          [{ return Helper.matchAnyExplicitUseIsUndef(*${root}); }]),
 170   (apply [{ Helper.replaceInstWithUndef(*${root}); }])>;
 171
 172 // Instructions where if all source operands are undef, the instruction can be
 173 // replaced with undef.
 174 def propagate_undef_all_ops: GICombineRule<
 175   (defs root:$root),
 176   (match (wip_match_opcode G_SHUFFLE_VECTOR):$root,
 177           [{ return Helper.matchAllExplicitUsesAreUndef(*${root}); }]),
 178   (apply [{ Helper.replaceInstWithUndef(*${root}); }])>;
 179
 180 // Replace a G_SHUFFLE_VECTOR with an undef mask with a G_IMPLICIT_DEF.
 181 def propagate_undef_shuffle_mask: GICombineRule<
 182   (defs root:$root),
 183   (match (wip_match_opcode G_SHUFFLE_VECTOR):$root,
 184          [{ return Helper.matchUndefShuffleVectorMask(*${root}); }]),
 185   (apply [{ Helper.replaceInstWithUndef(*${root}); }])>;
 186
 187 // Fold (cond ? x : x) -> x
 188 def select_same_val: GICombineRule<
 189   (defs root:$root),
 190   (match (wip_match_opcode G_SELECT):$root,
 191     [{ return Helper.matchSelectSameVal(*${root}); }]),
 192   (apply [{ return Helper.replaceSingleDefInstWithOperand(*${root}, 2); }])
 193 >;
 194
 195 // Fold x op 0 -> x
 196 def right_identity_zero: GICombineRule<
 197   (defs root:$root),
 198   (match (wip_match_opcode G_SUB, G_ADD, G_OR, G_XOR, G_SHL, G_ASHR, G_LSHR):$root,
 199     [{ return Helper.matchConstantOp(${root}->getOperand(2), 0); }]),
 200   (apply [{ return Helper.replaceSingleDefInstWithOperand(*${root}, 1); }])
 201 >;
 202
 203 // Fold (x op x) - > x
 204 def binop_same_val: GICombineRule<
 205   (defs root:$root),
 206   (match (wip_match_opcode G_AND, G_OR):$root,
 207     [{ return Helper.matchBinOpSameVal(*${root}); }]),
 208   (apply [{ return Helper.replaceSingleDefInstWithOperand(*${root}, 1); }])
 209 >;
 210
 211 // Fold (0 op x) - > 0
 212 def binop_left_to_zero: GICombineRule<
 213   (defs root:$root),
 214   (match (wip_match_opcode G_SDIV, G_UDIV, G_SREM, G_UREM):$root,
 215     [{ return Helper.matchOperandIsZero(*${root}, 1); }]),
 216   (apply [{ return Helper.replaceSingleDefInstWithOperand(*${root}, 1); }])
 217 >;
 218
 219 // Fold (x op 0) - > 0
 220 def binop_right_to_zero: GICombineRule<
 221   (defs root:$root),
 222   (match (wip_match_opcode G_MUL):$root,
 223     [{ return Helper.matchOperandIsZero(*${root}, 2); }]),
 224   (apply [{ return Helper.replaceSingleDefInstWithOperand(*${root}, 2); }])
 225 >;
 226
 227 // Erase stores of undef values.
 228 def erase_undef_store : GICombineRule<
 229   (defs root:$root),
 230   (match (wip_match_opcode G_STORE):$root,
 231     [{ return Helper.matchUndefStore(*${root}); }]),
 232   (apply [{ return Helper.eraseInst(*${root}); }])
 233 >;
 234
 235 // FIXME: These should use the custom predicate feature once it lands.
 236 def undef_combines : GICombineGroup<[undef_to_fp_zero, undef_to_int_zero,
 237                                      undef_to_negative_one,
 238                                      propagate_undef_any_op,
 239                                      propagate_undef_all_ops,
 240                                      propagate_undef_shuffle_mask,
 241                                      erase_undef_store]>;
 242
 243 def identity_combines : GICombineGroup<[select_same_val, right_identity_zero,
 244                                         binop_same_val, binop_left_to_zero,
 245                                         binop_right_to_zero]>;
 246
 247 def trivial_combines : GICombineGroup<[copy_prop, mul_to_shl]>;
 248 def all_combines : GICombineGroup<[trivial_combines, ptr_add_immed_chain,
 249     combines_for_extload, combine_indexed_load_store, undef_combines,
 250     identity_combines]>;