<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/121446>121446</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [GlobalISel] Inconsistent pattern import order comparing to SelectionDAG
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            bug,
            tablegen,
            llvm:globalisel
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          e-kud
      </td>
    </tr>
</table>

<pre>
    I've been working on transferring `G_LOAD` and `G_STORE` selection on X86 from C++ to SelectionDAG patterns when noticed that GlobalISel always prefers unaligned loads even if a mem operation is aligned.

Here is a small reproducer of the problem
```
// RUN: llvm-tblgen -gen-global-isel -optimize-match-table=false -I %p/../../../include -I %p/../Common %s | FileCheck -check-prefix=GISEL %s

include "llvm/Target/Target.td"
include "GlobalISelEmitterCommon.td"

def alignedst: PatFrag<(ops node:$v, node:$a), (store $v, $a), [{
  return true;
}]>{
  let GISelPredicateCode = [{ return true; }];
}

def MOVALIGNED : I<(outs), (ins GPR32:$src0, GPR32:$src1),
    [(alignedst GPR32:$src0, GPR32:$src1)]>;


def MOVUNALIGNED : I<(outs), (ins GPR32:$src0, GPR32:$src1),
    [(store GPR32:$src0, GPR32:$src1)]>;
```
We will see this output
```
const uint8_t *MyTargetInstructionSelector::getMatchTable() const {
  constexpr static uint8_t MatchTable0[] = {
    GIM_Try, /*On fail goto*//*Label 0*/ GIMT_Encode4(41), // Rule ID 1 //
      GIM_CheckNumOperands, /*MI*/0, /*Expected*/2,
      GIM_CheckOpcode, /*MI*/0, GIMT_Encode2(TargetOpcode::G_STORE),
      GIM_CheckMemorySizeEqualToLLT, /*MI*/0, /*MMO*/0, /*OpIdx*/0,
      GIM_CheckAtomicOrdering, /*MI*/0, /*Order*/(uint8_t)AtomicOrdering::NotAtomic,
      // MIs[0] src0
 GIM_RootCheckType, /*Op*/0, /*Type*/GILLT_s32,
 GIM_RootCheckRegBankForClass, /*Op*/0, /*RC*/GIMT_Encode2(MyTarget::GPR32RegClassID),
      // MIs[0] src1
 GIM_CheckPointerToAny, /*MI*/0, /*Op*/1, /*SizeInBits*/32,
 GIM_RootCheckRegBankForClass, /*Op*/1, /*RC*/GIMT_Encode2(MyTarget::GPR32RegClassID),
      // (st GPR32:{ *:[i32] }:$src0, GPR32:{ *:[i32] }:$src1)<<P:Predicate_unindexedstore>><<P:Predicate_store>>  => (MOVUNALIGNED GPR32:{ *:[i32] }:$src0, GPR32:{ *:[i32] }:$src1)
 GIR_MutateOpcode, /*InsnID*/0, /*RecycleInsnID*/0, /*Opcode*/GIMT_Encode2(MyTarget::MOVUNALIGNED),
 GIR_RootConstrainSelectedInstOperands,
      // GIR_Coverage, 1,
` GIR_Done,
    // Label 0: @41
    GIM_Try, /*On fail goto*//*Label 1*/ GIMT_Encode4(86), // Rule ID 0 //
      GIM_CheckNumOperands, /*MI*/0, /*Expected*/2,
      GIM_CheckOpcode, /*MI*/0, GIMT_Encode2(TargetOpcode::G_STORE),
      GIM_CheckMemorySizeEqualToLLT, /*MI*/0, /*MMO*/0, /*OpIdx*/0,
      GIM_CheckAtomicOrdering, /*MI*/0, /*Order*/(uint8_t)AtomicOrdering::NotAtomic,
      // MIs[0] src0
 GIM_RootCheckType, /*Op*/0, /*Type*/GILLT_s32,
 GIM_RootCheckRegBankForClass, /*Op*/0, /*RC*/GIMT_Encode2(MyTarget::GPR32RegClassID),
      // MIs[0] src1
 GIM_CheckPointerToAny, /*MI*/0, /*Op*/1, /*SizeInBits*/32,
 GIM_RootCheckRegBankForClass, /*Op*/1, /*RC*/GIMT_Encode2(MyTarget::GPR32RegClassID),
 GIM_CheckCxxInsnPredicate, /*MI*/0, /*FnId*/GIMT_Encode2(GICXXPred_MI_Predicate_alignedst),
      // (st GPR32:{ *:[i32] }:$src0, GPR32:{ *:[i32] }:$src1)<<P:Predicate_unindexedstore>><<P:Predicate_store>><<P:Predicate_alignedst>> =>  (MOVALIGNED GPR32:{ *:[i32] }:$src0, GPR32:{ *:[i32] }:$src1)
 GIR_MutateOpcode, /*InsnID*/0, /*RecycleInsnID*/0, /*Opcode*/GIMT_Encode2(MyTarget::MOVALIGNED),
 GIR_RootConstrainSelectedInstOperands,
      // GIR_Coverage, 0,
 GIR_Done,
    // Label 1: @86
    GIM_Reject,
    }; // Size: 87 bytes
 return MatchTable0;
}
```
So we don't have a chance to match the aligned store because we are going to always match unaligned store.

The reason is in the comparator for pattern sorting, the part about predicates specifically:
https://github.com/llvm/llvm-project/blob/62cd050b635cbb201dd08188696448cf5ab23260/llvm/utils/TableGen/Common/GlobalISel/GlobalISelMatchTable.cpp#L1754-L1778

`MOVUNALIGNED` has these predicates:
```
 Kind = llvm::gi::PredicateMatcher::IPM_Opcode, InsnVarID = 0,
 Kind = llvm::gi::PredicateMatcher::IPM_MemoryVsLLTSize, InsnVarID = 0
 Kind = llvm::gi::PredicateMatcher::IPM_AtomicOrderingMMO, InsnVarID = 0
```
`MOVALIGNED` has these predicates:
```
 Kind = llvm::gi::PredicateMatcher::IPM_Opcode, InsnVarID = 0,
 Kind = llvm::gi::PredicateMatcher::IPM_MemoryVsLLTSize, InsnVarID = 0
 Kind = llvm::gi::PredicateMatcher::IPM_GenericPredicate, InsnVarID = 0
 Kind = llvm::gi::PredicateMatcher::IPM_AtomicOrderingMMO, InsnVarID = 0
```
Where `IPM_GenericPredicate` is an alignment check. Since `IPM_AtomicOrderingMMO` has higher priority than `IPM_GenericPredicate` we sort in an inconsistent with SelectionDAG order.

For loads and stores in particular it could be easily fixed in https://github.com/llvm/llvm-project/blob/62cd050b635cbb201dd08188696448cf5ab23260/llvm/utils/TableGen/GlobalISelEmitter.cpp#L832 when we move the generation of the atomic check before `TreePredicateCall` checks.

But I'm not sure if this solution is not just an ad-hoc fix for mem operations. So my questions are
1) Was this issue addressed or discussed earlier?
2) Should we give higher priority to the patterns with more predicates before comparing predicate priority one by one?
3) Should we sort predicates by their priority before sorting patterns?

</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJzsWd1v2zgS_2uYl4EDifJXHvLgj9gnnN0EibftW0BJY5tbitSSVBLvX38gKdlykmZvCxSLOxQo6ogczvf8RhwxY_hOIl6TwZQM5hestnulr7H3rS4uMlUcrlNCR08IGaKEZ6W_cbkDJcFqJs0WtXbPZBgtH1e3kzkZRsBkERYeNrf3N27FoMDcciXdwa_jIWy1KmFG6JTQKVgFDy3BfLKEilmLWhp43qMEqSzPsQC7ZxaWQmVMpA8ogIlndjBQadyiNlBLJpwhBQjFCgP4hBL4FhiUWIKqUDOvADfQEF6SaEKiyb9Qo18FUzIhQGOlVVHnqEFtwe4RKq0ygaUjH0bNv2hC6ILQBdz_9okkExDiqezZTOxQQm-Hsrfzmva4QQE9VVle8j-xVzKb73uWZQJJMt8yYRB6KRA6qAhdXF6e_cdlLuriDcFMlaWSbskAGc1gwQXO9ph_g17ufnrOJfyFJPNl-nCz8oTB1JYhodTpS-hiw_QO7fGPS1sQSs8pTy6_KbkLTJB_JCXRpMBt61RjnTfumF1otiPJjNCxqgxIVSBJJoT2nwiddR4ZoVduhdCxsUo7iYGkuzeYktGURBMAjbbWLvdqJIlbIqM5GcxJctNSCLSwdNreaSx4zizOlDMkmTd8XvGAlkPL7WjR-vbzZJUuP93MwdmUNtbU1px05tLA8u4-ocEao_PI7ZwvxYHeqwdeCzo-uuu_PB5sDEp2Nfzt08_TMQTk7-vXKZIvCM9cCDCIYPfcgKptVdtXVLmSxkLNpR0_WiB0sj6EfEylsbr2wBAQQmknNpns0K5dKW18JdExoVcQuLR54J_wpdJgLLM8P7I_nYsC5IXcaI4BLNP140YfgvMWhE5uJWwZF7BTVhHa1D2hkxXLUEAUltyxzeONzFWBfULH_fgYgAATtUBI5xA3C42wIM5X76e6vHUoJQtzkr1OA_votHTzUmFusQgb9BS0Dq_byunxHTYdTSmh4-Dp5oR3bgvc3YzoMF9jqfThgf-JN3_UTGzUarX5UOP1-vbN2m2VFi-n1bdSJlaVPL_VBboG8yF_T9RGZtzEmdCrVyy8bZ-UDctdoU2M1qkhg2nkUsJnejTx6twrZb1Km0OFXQveKBII3OIyXa02jyZpw3PG5x53Uya_LZSeCWbMhyzvZy3Ds6C1BdIEzNXjPe48u3T-KnDvWhe3WnmN7hSXFvVGTeThY1c3GsanJZcIqZxyBzlu6wdtjn-GzR7ETnA1mjpwcX8NpjyhvvZH8-9g218Q-_pOZiSZ3ZFkcmw2j7XkssAXB-1KowfFm_foOtvgEMj9OiO7kP7zFPfhuX9c15ZZfI0WqTTSefR1KmJ-yAV-Z7dl8peB61p4iprTxieLg23NeIP3WLgW0MHF1xF252bqCTXbeQviQONeOt3WXEnstLVwpgXuZAKkH_XjHwP--H3gHw_fB_7oF_D_Av5fwP8Tgf9o1OzlxYHUEWs_NGwh0-Jdqct09vWr4_G4Th9PuH265_wPd5z3tjsXON-Ump7UNKX_95b00xpS1OH3QTeKm240Hna60T3-jrntnHA-m7YHXf25U-MRZAeL7o7f3m27d5zuxbZz53pQ8IxQKEnoyMKePSEwyPdM5ghWgR9U-OlHO1YJt8EMc1YbdGeZRtgpLneOvpnGhGOnWYw_1AxaNnsEjcyEIQyXnnuuyoppZpWGrdLt6AeM0rZBfz-BYdoCy1RtoWoT1oCpMOdbnjMhDi6Q0WRvbWV8WjkP7bjd19llrkpCF83Aw89pKq2CYxeZUBmhiyHNi2gQZcNkkGcZjeKiiMbxeDy8Gvb743w7YBlN6DA68aktF8bPTTKBS5THuYzLtePE5OzhFJTLvKoITVbxaNDvreLRaNxc64fR2dvRMII9M84DBjuGB1u7wYR_c1n4e6xXL1yRefg9VriXj80FOr1bP56KzBXQZ6bTcBduU_aHmIaXhM9mtdr4BH2H-4-yPm_r_uXiPeZnQzrv0V_-fJf1EiVqnp_1yX8wVl_2qBHIMHpXt2Hkh7Qy4FGJ0oKfdl7CA3eY1Zx7K7cJ-p7v9qih0lxpbg9g90x-JOwZPQg5nGISuMyVNNxYJ_eZ2_35xFo5eQ3MLZRuRtBMNgDo0c5hGM9rwTRwC7mqRQEZAjLDxQG2_AULR_aPQtibWW-LVOOEhmn8M0KpntCj8s65LUzVm0k5894PgYEMtyoEdKMRT-NYJoRzsCcyjdOmtYWU0FEJUlkwtUbg2zAxNErU7eTebf5eG-vzoOjtVe4c5zvH2ZTfXMKDgvIAf9Ro_ILrViSauDcN-OIxwPUgY2oEVhQajcEClIaCm7z2D8i04C6l3ZWNunMPex-0Z4Qdf8K3GaWaXtV-vXBpUjoXdHpW45TQ9lzvPO6dGCmJkPmfIDw5F-7TssvSJTPyjiaNkKaJHjUK3C6K66S4Sq7YBV7Ho2QwGvfjwehif50l-faqz5Kr7XgwzOMCB_kQ8zjKIlrkdFRc8Gsa0UEURzSi8WAwuhwlCRv144QWLB4M-mPSj7BkXFy6DLtUenfhPXwd07jfH14I96Zj_IcmSrN6R6i_MVDqv4fsXAY2Cw3ShG8o3LhG6l4aL_S1T_6s3hnSjwQ31pxkWW6F_4zV6b-DOaTd0m3fL3hZOS_6uu0E49WXqItai-u_XZDeZldYjdlP1_Q_AQAA___tpQ0k">