[llvm-dev] [RFC] Tablegen-erated GlobalISel Combine Rules
Nicolai Hähnle via llvm-dev
llvm-dev at lists.llvm.org
Thu Nov 29 02:02:32 PST 2018
On 27.11.18 19:01, Daniel Sanders wrote:
> ...Continued from the other email
>
> _Removing the defs section_
>
> We can potentially infer quite a lot of the defs section but it requires
> both a complicated ruleset and that tblgen spends processing time doing
> the inferencing. That processing time is potentially significant for
> large combiners and for that reason we need to be careful not to let
> inferencing become a burden on tblgen. My main worry here is that it may
> require analyzing both the match and apply section to fully inference
> the types and I'd like the tablegen pass to be able to ignore the apply
> section until it's about to write it out to the output file.
Thank you for looking into this!
> There are however, some simple rules we can use to minimize the defs
> section with just a scan of the defs section (trivial) and match section
> (which we have to do anyway):
>
> 1. Match roots are implicitly declared in the defs section and have
> type 'reg'.
> 2. Names used as argument to an operator that subclasses Instruction
> are implicitly declared in the defs section with type 'reg'. This
> allows leaf-operands to be used in the apply section
> * This does however come at additional run-time memory cost
Can you explain this? You mean run-time as in when the compiler runs,
right? I guess I'm not familiar enough with the details of the matching
algorithm.
Cheers,
Nicolai
> 3. Names used as argument to an operator that subclasses Instruction
> are assumed to be 'reg'. This allows us to omit the
> formerly-anonymous names such as $t[0-3] in the above examples.
> * Using an 'operand' typed variable as the def of an instruction
> does not change it to 'reg' but does emit the isReg() check that
> 'reg' would normally emit.
> 4. Names used in an 'outs' position on a GIMatchPredicate are
> implicitly declared in the defs section using the type given by the
> predicate.
> 5. Any names not given in the defs section are assumed to be 'instr' if
> they are used as a name for an operator that subclasses Instruction.
> This allows us to omit the defs for MI's involved in debug info.
> 6. Any names used solely in the apply section and defined by a
> value-constructing operator (e.g. create*) can be omitted
>
>
> With these rules, the defs section isn't completely gone but is often
> empty and can be omitted with a variant of GICombineRule. The examples
> would be as below. I've indicated which rule eliminates which def with
> color coding and strike-through:
> // Omitted due to rule 1
> // Omitted due to rule 2
> // We haven't been listing any defs related to rule 3 since these
> are the formerly anonymous
> // operands that now need names to fit into the tblgen dag type
> // Omitted due to rule 4
> // Omitted due to rule 5
> //Omitted due to rule 6
> 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))>;
> 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))>;
> 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, 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))))>;
> // $VAL is needed to indicate it's an immediate and provide the
> predicate
> def : GICombineRule<(defs reg:$D, reg:$A, imm_2:$VAL),
> (match (G_MUL $D, $A, $VAL)),
> (apply (MYTGT_DOUBLE $D, $A))>;
> // $B/$C are needed to indicate they're immediates and provide $C's
> predicate
> 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))>;
> // $D is needed because we wanted operand instead of reg. We could
> rewrite the predicate to take a reg though.
> def extending_loads : GICombineRule<
> (defs operand:$D, reg:$A, extending_load_matchdata:$matchinfo),
> (match (G_LOAD $D, $A),
> (extending_load_predicate operand:$A,
> extending_load_matchdata:$matchinfo)),
> (apply (exec [{ Helper.applyCombineExtendingLoads(${D}, ${matchinfo.B}); }],
> reg:$D, extending_load_matchdata:$matchinfo)>;
> // I haven't included any rules for omitting defs from GIMacro but
> I can look into this if we want.
> 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>;
> // $ANYLOAD is needed to import the macro and name its instance
> def extending_loads : GICombineRule<
> (defs reg:$D, reg:$A, extending_load_matchdata:$matchinfo,
> ANYLOAD:$ANYLOAD),
> (match (ANYLOAD $D, $A),
> (extending_load_predicate operand:$A,
>
> extending_load_matchdata:$matchinfo)),
> (apply (exec [{ Helper.applyCombineExtendingLoads(${D},
> ${matchinfo.B}); }],
> reg:$D, extending_load_matchdata:$matchinfo)>;
> 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);
> };
> 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))>;
> 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)))>;
> // This one keeps the def of $D/$A because we wanted operand
> instead of reg. We didn't have
> // anything requiring that though and could trivially change them
> to reg.
> def : GICombineRule<
> (defs operand:$D, operand:$A),
> (match (G_LOAD $D, $A):$MI,
> (mmo_is_load8 instr:$MI)),
> (apply ...)>;
--
Lerne, wie die Welt wirklich ist,
Aber vergiss niemals, wie sie sein sollte.
More information about the llvm-dev
mailing list