[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