[llvm-dev] [RFC] Tablegen-erated GlobalISel Combine Rules

Daniel Sanders via llvm-dev llvm-dev at lists.llvm.org
Tue Nov 27 09:59:40 PST 2018

Hi All,

I've more or less finished updating the examples to the DAG style we were talking about. Hopefully I haven't forgotten anything, there was a lot to keep track of :-). Overall, I think there's a couple places where things get a a little awkward (mainly debug info) but things generally look good to me.

A Simple Example

def : GICombineRule<(defs reg:$D, reg:$S),
                    (match (G_ZEXT s32:$t1, s8:$S),
                           (G_TRUNC s16:$D, s32:$t1)),
                    (apply (G_ZEXT s16:$D, s8:$S))>;

This has been converted to the style that fits within tblgen's DAG type but isn't (directly) a DAG. The DAG structure is defined by the matching names instead of tblgen's DAG type. This avoids the restrictions of the DAG type and is something that's needed anyway to allow one node to be referenced in multiple places. I've kept the 'match' node at the top of the match to allow instructions and predicates to be freely combined within this section (see later examples). Without it, the stricter type checking on list<X> would require Instruction, GIMatchPredicate, and any future matching extensions to have a common base class.

The explicit specification of root has also been removed in favour of a default value and a 'let' assignment to deal with any cases where the algorithm-chosen default is unsuitable (see the upside-down match section below). The default would be the set of defs minus the set of uses. This covers the common single-root case, as well as the multi-root case. The 'let' would be required for the upside-down and inside-out matches.

One consequence of this style is that there's no means to have anonymous operands that still define the edges of the DAG being matched as shown by the need to name $t1 above.

I'll come back to possibility of removing the defs section in a follow-up email as I suspect I'm over the size limit again. The bit I need to mention in this email is that the formerly anonymous operands are omitted from the defs section in these examples.

Generalizing the Simple Example

As before, this is the example above with the concrete types removed.
    def isScalarType : GIMatchPredicate<bool, (ins type:$A), (outs), [{
      return ${A}.isScalar();
    def isLargerType : GIMatchPredicate<bool, (ins type:$A, type:$B), (outs), [{
      return ${A}.getSizeInBits() > ${B}.getSizeInBits();
    def : GICombineRule<(defs reg:$D, reg:$S),
                        (match (G_ZEXT $t1, $S),
                               (G_TRUNC $D, $t1),
                               (isScalarType type:$D),
                               (isLargerType type:$D, type:$S)),
                        (apply (G_ZEXT $D, $S))>;

There's little different here aside from what's mentioned in the simple example. I've just changed the argument order of GIMatchPredicate to better match the order in the underlying function prototype.

Preserving DILocation and other debug info

We have a choice of syntax here and neither seems to be clearly better than the other when considering just locations:
    def : GICombineRule<(defs reg:$D, reg:$S, instr:$MI0, instr:$MI1),
                        (match (G_ZEXT $t0, $S):$MI0,
                               (G_TRUNC $D, $t0):$MI1),
                               (isScalarType type:$D),
                               (isLargerType type:$D, type:$S)),
                        (apply (G_ZEXT $D, $S, (debug_locations $MI0, $MI1)))>;

    def : GICombineRule<(defs reg:$D, reg:$S, debug_location:$DL0, debug_location:$DL0),
                        (match (G_ZEXT $t0, $S, debug_location:$DL0),
                               (G_TRUNC $D, $t0, debug_location:$DL1)),
                               (isScalarType type:$D),
                               (isLargerType type:$D, type:$S)),
                        (apply (G_ZEXT $D, $S, (debug_locations $DL0, $DL1)))>;

However, the former is more compact when DBG_VALUE is involved since naming the instruction gives access to three of the four pieces of data we need to pass on to the apply step:
    def : GICombineRule<(defs reg:$D, reg:$S, instr:$MI0, instr:$MI1, instr:$MI2, instr:$MI3, debug_expr:$DNewExpr),
                        (match (G_ZEXT $t0, $S):$MI0,
                               (G_TRUNC $D, $t0):$MI1,
                               (DBG_VALUE $t0):$MI2,
                               (DBG_VALUE $D):$MI3,
                               (isScalarType type:$D),
                               (isLargerType type:$D, type:$S)),
                        (apply (createDIExprLLVMFragment debug_expr:$MI2, type:$D):$DNewExpr,
                               (G_ZEXT $D, $S, (debug_location $MI0, $MI1)),
                               (DBG_VALUE $D, debug_local:$MI2, debug_expr:$DNewExpr, (debug_location $MI2)),
                               (DBG_VALUE $D, debug_local:$MI3, debug_expr:$MI3, (debug_location $MI3))))>;

Matching immediates and G_CONSTANT/G_FCONSTANT

There isn't much that's special about the changes in this section. Rewriting the examples into the DAG style gives:
    def : GICombineRule<(defs reg:$D, reg:$A, imm:$VAL),
                        (match (G_MUL $D, $A, $VAL),
                               (isTwo imm:$VAL)),
                        (apply (MYTGT_DOUBLE $D, $A))>;
Or equivalently:
    def imm_2 : GIPredicatedDefKind<(isTwo imm)>;
    def : GICombineRule<(defs reg:$D, reg:$A, imm_2:$VAL),
                        (match (G_MUL $D, $A, $VAL)),
                        (apply (MYTGT_DOUBLE $D, $A))>;

And here's the example that replaces 2 * (A + B) with 2A + 2B:
    def : GICombineRule<
      (defs reg:$D, reg:$A, imm:$B, imm_2:$C),
      (match (G_ADD $t1, $A, $B),
             (G_MUL $D, $t1, $C)),
      (apply (create_imm [{ 2 * ${B}->getZExtValue() }], apint_value:$B):$NB,
             (G_ADD $t1, $A, $A),
             (G_ADD $D, $t1, $NB))>;

Passing arbitrary data from match to apply

The main change in this section that hasn't already been discussed is that the result of extending_load_predicate has been moved to the new 'outs' section of GIMatchPredicate and the code expansion refers to a particular output of the predicate using 'matchinfo.B' similar to a struct member or multi-operand ComplexPatterns.

    def extending_load_matchdata : GIDefMatchData<"PreferredTuple">;
    def extending_load_predicate : GIMatchPredicate<
         bool, (ins reg:$A), (outs extending_load_matchdata:$B), [{
      return Helper.matchCombineExtendingLoads(${A}, ${B});
    def extending_loads : GICombineRule<
      (defs operand:$D, reg:$A, extending_load_matchdata:$matchinfo),
      (match (G_LOAD $D, $A),
             (extending_load_predicate operand:$A,
      (apply (exec [{ Helper.applyCombineExtendingLoads(${D}, ${matchinfo.B}); }],
                   reg:$D, extending_load_matchdata:$matchinfo)>;

The main problem with this is that this prevents access to the contents of matchinfo from outside of C++. To overcome this, I'd suggest allowing the '${foo.bar}' syntax in tablegen's dag type. It should be a fairly simple change and there's no tblgen-internal reason to not allow dots in the names. Existing backends would have to check for it though which could be a tblgen performance issue.


Aside from changing to the DAG style, the main change here is that the children of 'oneof' all have 'match' at the top-level. This is for the same reason 'match' was kept on the simple example: the relaxed type checking on 'dag' compared to 'list<X>' allows us to freely mix DAG-style matches and predicates.
    def ANYLOAD : GIMacro<(defs def:$R, use:$S, uint64_t:$IDX),
                          (match (oneof (match (G_LOAD $R, $S)),
                                        (match (G_SEXTLOAD $R, $S)),
                                        (match (G_ZEXTLOAD $R, $S))):$IDX>;
    def extending_loads : GICombineRule<
      (defs reg:$D, reg:$A, extending_load_matchdata:$matchinfo, ANYLOAD:$ANYLOAD),
      (match (ANYLOAD $D, $A),
             (extending_load_predicate operand:$A,
      (apply (exec [{ Helper.applyCombineExtendingLoads(${D}, ${matchinfo.B}); }],
                   reg:$D, extending_load_matchdata:$matchinfo)>;

'Upside-down' matches (i.e. roots at the top) and similar

As mentioned back in the simple example, these need to specify the match roots using a 'let' statement to override the default:
def : GICombineRule<
  (defs reg:$D, reg:$A),
  (match (G_LOAD $t1, $D),
         (G_SEXT $A, $t1)),
  (apply (G_SEXTLOAD $A, $D))> {
  let MatchStartsFrom = (roots $D);

def : GICombineRule<
  (defs reg:$D, reg:$A, reg:$B, reg:$C),
  (match (G_TRUNC s32:$t1, s64:$A),
         (G_TRUNC s32:$t2, s64:$B),
         (G_ADD $D, $t1, $t2)
         (G_SEXT s64:$C, $D)),
  (apply (G_ADD $D, $A, $B),
         (G_SEXT_INREG $C, $D))> {
  let MatchStartsFrom = (roots $D);

Multiple roots

All the changes in this section have already been discussed above:
def : GICombineRule<
  (defs reg:$D1, reg:$D2, reg:$A, reg:$B),
  (match (G_ADD $D1, $A, $B),
         (G_SUB $D2, $A, $B)),
  (apply (BUTTERFLY $D1, $D2, $A, $B))>;
$D1 and $D2 are both automatically chosen as roots since they are def'd but not used.


This is a new example based on our discussion about MIR having direct support for subregisters. We use subregister indexes to specify that it's a subregister that should be emitted by the apply step.
def : GICombineRule<
  (defs reg:$D, reg:$A, reg:$B),
  (match (G_TRUNC s32:$t1, s64:$A),
         (G_TRUNC s32:$t2, s64:$B),
         (G_ADD $D, $t1, $t2),
  (apply (ADD32 $D, (sub_lo $A), (sub_lo $B)))>;

Matching MachineMemOperands

While re-writing these examples, I also realized I didn't have any examples for testing properties of the MachineMemOperand, so here's one:
    def mmo_is_load_8 : GIMatchPredicate<
         (ins instr:$A), (outs), [{
      if (!${A}.hasOneMemOperand())
        return false;
      const auto &MMO = *${A}.memoperands_begin();
      return MMO.isLoad() && MMO.getSize() == 1;
    def : GICombineRule<
      (defs operand:$D, operand:$A),
      (match (G_LOAD $D, $A):$MI,
             (mmo_is_load8 instr:$MI)),
      (apply ...)>;
I've made use of the naming instructions here since this was better in the debug info section. If we choose the alternative in that section then we can change it to $D or $A instead (either way the generated code would call getParent()).

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20181127/637d63ed/attachment.html>

More information about the llvm-dev mailing list