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

    <tr>
        <th>Summary</th>
        <td>
            [DAGCombine][expandmemcmp] Poor code generation
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

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

    <tr>
      <th>Reporter</th>
      <td>
          rlougher
      </td>
    </tr>
</table>

<pre>
    If the following IR is lowered with SelectionDAGISel we get much less efficient code compared to FastISel:

```
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

define i32 @foo(ptr %0, ptr %1) #0 {
  %3 = load i256, ptr %0, align 1
  %4 = load i256, ptr %1, align 1
  %5 = icmp ne i256 %3, %4
  %6 = zext i1 %5 to i32
  %7 = icmp eq i32 %6, 0
  %8 = zext i1 %7 to i32
  %9 = sub i32 %8, %6
  ret i32 %9
}

attributes #0 = { "target-cpu"="haswell" }
```
```
$ clang --version
clang version 18.0.0 (7f3ee3ca1d09daf0f7d350ed9d62796640a59bf4)

$ llc test.ll -o - | wc
 200     712    4450
$ llc test.ll --fast-isel -o - | wc
     26 66     559 
```

With SelectionDAGISel each 32 byte load is done by four 8-byte scalar loads. The values are then inserted byte-by-byte (using vpinsrb) into two xmm registers, which are combined into a ymm register.

```
$ llc test.ll -o - | grep vpinsrb | wc
     60 300    1944
```

With FastISel the loads are done in a single 256-bit load (the second load is folded into the xor):

```
 vmovdqu (%rdi), %ymm0
        vpxor   (%rsi), %ymm0, %ymm0
```

The reason SelectionDAGISel fails to select this, is because of the "sub" instruction which uses the results of both comparisons. The DAG combiner is unable to simplify the comparisons, and instead results in a situation where the loads have multiple uses which prevents subsequent folds (see below).

The testcase was generated from the following program, with the IR taken after expandmemcmp. A sub instruction was then inserted to use both comparisons. This occurred in a real program, but instead of the sub it was a sequence involving the comparison of two bcmps.

```
#include <strings.h>

int foo(char *p1, char *p2) {
  if(bcmp(p1, p2, 32) == 0)
    return 1;
 return 0;
}

*** IR Dump After Expand memcmp() to load/stores (expandmemcmp) ***
; Function Attrs: mustprogress nofree nounwind willreturn memory(argmem: read) uwtable
define dso_local i32 @foo(ptr nocapture noundef readonly %0, ptr nocapture noundef readonly %1) local_unnamed_addr #0 {
  %3 = load i256, ptr %0, align 1
  %4 = load i256, ptr %1, align 1
  %5 = icmp ne i256 %3, %4
  %6 = zext i1 %5 to i32
  %7 = icmp eq i32 %6, 0
  %8 = zext i1 %7 to i32
  ret i32 %8
}
```

Given the above IR (without the sub) SelectionDAG selects 256-bit loads. Examining the behaviour of DAG Combine we see that in pre-legalize mode it simplifies the comparisons leaving a single setcc:

```
SelectionDAG has 15 nodes:
  t0: ch,glue = EntryToken
          t2: i64,ch = CopyFromReg t0, Register:i64 %0
 t7: i256,ch = load<(load (s256) from %ir.0, align 1)> t0, t2, undef:i64
 t4: i64,ch = CopyFromReg t0, Register:i64 %1
        t8: i256,ch = load<(load (s256) from %ir.1, align 1)> t0, t4, undef:i64
      t22: i1 = setcc t7, t8, seteq:ch
    t15: i32 = zero_extend t22
  t18: ch,glue = CopyToReg t0, Register:i32 $eax, t15
  t19: ch = X86ISD::RET_GLUE t18, TargetConstant:i32<0>, Register:i32 $eax, t18:1
```

The setcc is then rewritten by target lowering into a sequence with bitcasts:

```
SelectionDAG has 21 nodes:
  t0: ch,glue = EntryToken
          t27: i32 = X86ISD::PTEST t26, t26
        t29: i8 = X86ISD::SETCC TargetConstant:i8<4>, t27
      t30: i1 = truncate t29
 t15: i32 = zero_extend t30
  t18: ch,glue = CopyToReg t0, Register:i32 $eax, t15
          t2: i64,ch = CopyFromReg t0, Register:i64 %0
 t7: i256,ch = load<(load (s256) from %ir.0, align 1)> t0, t2, undef:i64
 t23: v32i8 = bitcast t7
          t4: i64,ch = CopyFromReg t0, Register:i64 %1
        t8: i256,ch = load<(load (s256) from %ir.1, align 1)> t0, t4, undef:i64
      t24: v32i8 = bitcast t8
    t25: v32i8 = xor t23, t24
  t26: v4i64 = bitcast t25
  t19: ch = X86ISD::RET_GLUE t18, TargetConstant:i32<0>, Register:i32 $eax, t18:1
```

These bitcasts are then folded into the load instructions. The optimized lowered selection DAG now has valid types, which passes unchanged through type-legalization:

```
Type-legalized selection DAG: %bb.0 'foo:'
SelectionDAG has 18 nodes:
  t0: ch,glue = EntryToken
 t27: i32 = X86ISD::PTEST t26, t26
      t29: i8 = X86ISD::SETCC TargetConstant:i8<4>, t27
    t33: i32 = zero_extend t29
  t18: ch,glue = CopyToReg t0, Register:i32 $eax, t33
        t2: i64,ch = CopyFromReg t0, Register:i64 %0
      t32: v32i8,ch = load<(load (s256) from %ir.0, align 1)> t0, t2, undef:i64
        t4: i64,ch = CopyFromReg t0, Register:i64 %1
      t31: v32i8,ch = load<(load (s256) from %ir.1, align 1)> t0, t4, undef:i64
    t25: v32i8 = xor t32, t31
  t26: v4i64 = bitcast t25
  t19: ch = X86ISD::RET_GLUE t18, TargetConstant:i32<0>, Register:i32 $eax, t18:1
```

With the sub instruction, DAGCombine converts the second setcc into a setcc which directly uses the loads. This is then replaced by the bitcast sequence. But as the loads have multiple uses (the bitcasts and the first setcc), the bitcasts cannot be folded into the loads:

```
SelectionDAG has 25 nodes:
  t0: ch,glue = EntryToken
    t2: i64,ch = CopyFromReg t0, Register:i64 %0
  t7: i256,ch = load<(load (s256) from %ir.0, align 1)> t0, t2, undef:i64
 t4: i64,ch = CopyFromReg t0, Register:i64 %1
  t8: i256,ch = load<(load (s256) from %ir.1, align 1)> t0, t4, undef:i64
            t35: i32 = X86ISD::PTEST t34, t34
          t37: i8 = X86ISD::SETCC TargetConstant:i8<4>, t35
        t38: i1 = truncate t37
      t15: i32 = zero_extend t38
        t10: i1 = setcc t7, t8, setne:ch
      t11: i32 = zero_extend t10
    t16: i32 = sub t15, t11
  t19: ch,glue = CopyToReg t0, Register:i32 $eax, t16
      t31: v32i8 = bitcast t7
 t32: v32i8 = bitcast t8
    t33: v32i8 = xor t31, t32
  t34: v4i64 = bitcast t33
  t20: ch = X86ISD::RET_GLUE t19, TargetConstant:i32<0>, Register:i32 $eax, t19:1
```

The first setcc is later simplified but the bitcasts are never revisited so they are not folded into the load instructions. This means the optimized lowered selection DAG has non-legal types, which are scalarized by type-legalization:

```
Optimized lowered selection DAG: %bb.0 'foo:'
SelectionDAG has 24 nodes:
  t0: ch,glue = EntryToken
        t37: i8 = X86ISD::SETCC TargetConstant:i8<4>, t35
      t39: i32 = zero_extend t37
        t43: i8 = X86ISD::SETCC TargetConstant:i8<5>, t35
      t45: i32 = zero_extend t43
    t16: i32 = sub t39, t45
  t19: ch,glue = CopyToReg t0, Register:i32 $eax, t16
 t2: i64,ch = CopyFromReg t0, Register:i64 %0
        t7: i256,ch = load<(load (s256) from %ir.0, align 1)> t0, t2, undef:i64
      t31: v32i8 = bitcast t7
          t4: i64,ch = CopyFromReg t0, Register:i64 %1
 t8: i256,ch = load<(load (s256) from %ir.1, align 1)> t0, t4, undef:i64
      t32: v32i8 = bitcast t8
    t33: v32i8 = xor t31, t32
  t34: v4i64 = bitcast t33
  t35: i32 = X86ISD::PTEST t34, t34
 t20: ch = X86ISD::RET_GLUE t19, TargetConstant:i32<0>, Register:i32 $eax, t19:1

Type-legalized selection DAG: %bb.0 'foo:'
SelectionDAG has 209 nodes:
  t0: ch,glue = EntryToken
  t2: i64,ch = CopyFromReg t0, Register:i64 %0
  t4: i64,ch = CopyFromReg t0, Register:i64 %1
 t37: i8 = X86ISD::SETCC TargetConstant:i8<4>, t35
      t39: i32 = zero_extend t37
        t43: i8 = X86ISD::SETCC TargetConstant:i8<5>, t35
      t45: i32 = zero_extend t43
    t16: i32 = sub t39, t45
 t19: ch,glue = CopyToReg t0, Register:i32 $eax, t16
        t200: i8 = truncate t191
            t199: i16 = truncate t191
          t69: i16 = srl t199, Constant:i8<8>
        t70: i8 = truncate t69
        t71: i8 = truncate t65
            t66: i16 = truncate t65
          t72: i16 = srl t66, Constant:i8<8>
        t73: i8 = truncate t72
...
 t149: v32i8 = BUILD_VECTOR t200, t70, t71, t73, t77, t79, t80, t82, t197, t91, t92, t94, t98, t100, t101, t103, t190, t115, t116, t118, t122, t124, t125, t127, t187, t136, t137, t139, t143, t145, t146, t148
...
...
```

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzsWl9v27qS_zTKC2FDIvX3IQ-unRQFLnAv2pw9-1ZQ0tjmHol0ScqOz6dfDEnbsuOkbZIttsAJAtuS5h9nOL-Zoc2NESsJcBtlH6JsccMHu1b6VndqWK1B39Sq3d9-WhK7BrJUXad2Qq7Ip89EGNKpHWhoyU7YNfkCHTRWKLmYffz0BTqyA7ICS_qhWZMOjCGwXIpGgLSkUS2QRvUbjuxWkXtuLDJFbBbFiyg-vOZx-HeXlmuU2HLLO75XgyURW5CIUpj0EZvBZEOLOGIzRt0LXibnl_gpT93LRBw-LEtkSmg5kSV-yA88eTr5ktAyovRMv9Vi08FB92OZf83TySD_kmonJ52Qw-NkJYcjl39tYSkkEMEoidJ4qVREy43VJKJZHNE5CZ-TiFYkoiwmUfHBcxK8z5y6TvGWCJrlIw7HzTuxkiQZMaTPMiTXGTLHIJp-Q9BOmuVOLxKjuBFl7ij_hkdLROJZrcKVjWiKkzT45lcdrIhHVOWlpOKppMrRmKE-SCmDSfmBSIM9PKuCy4vF2PfcWi3qwYIJrsXIFR8wej6kk2bj4sUWEaVrbnbQdRGl5CTnfCNeXtKUNB2XKzKZbEEboaR_4G-GWyQpp_E0JhEtiyUDYA1P2rhq-TJeFi3LYmirNqdFledpzLOqXqYRrc7Sgaak6xpiwdhp15GJIhMSFXOya4IvaBwT_CsSim9pmsXPsE6W3NiJMHBNDP7RnOS5-5RhDK6u273-eTX7gTdrwiip9xbCNjSkVRJIvSdLNWhSTtwz0_COa0dipuRhDWTLuwEM4RoQdSQR0oC20DpZk3rv-SJaDgaxaLsR0ugaE0dIq4jdKfLY90TDShgL2uB-2a1Fs3YiG9XXQkLriTnZj0inL4DPs85fadgcjHjqxjwmzAclqdL0e2484KCDW-cSZ7Pzm5CEE1xxB4Rm-aQW1js2oiWSG2iUbI--XqquPawSHz8qjdvpRYAl215t228DioxopluBLD7d9n0fj9ZFCNluHpUm5EBsLokv-a4uGwOugRsln-6hJRedQUQw7gmxa-GCKQypoeGDAaJ8ZYooNUONKSuksXpwYkLQBwPGEWkwQ2cN8tTKrkMBEkbJsPEWs4-H7aFRySB53YEzQPSbTiz3Ts6Iz0GpbJ1W4O1RRYiVHXgwBPxmDjFd8y2QfuisKyTOQG_rRsMWpDWIdwa-DVgsMZAIXKUBIDV0ahfRanrpQ9yWDTdAdtyQFUjQHFNmqVV_Ubs3Wq00711W4J7Dp58-E8v_Akn40oIm8Ljhsu2hb_rNlMw8-o4dy81FalqFy7jqV2GIappBa7cbCcdwd2Mr6sEeHRji6RRap4cT74gGM2Crui2u4TwMjmunSN30G_NyDjMhm25osXrPjdVCrsx0HbG7MZNwTscC3aw5lszZxtXM4xV1RfpUn8UyoiUqx5ruSJFkTpgnZAssOPERzDF3NNhBYwFmBynhTny8c1HEIhr-MViLod-QmYvVnYsV8cFyqVhhNHCjRfTeWKVd2SvHMfVNxkGkF88-kPtB-vjOrNUmYjPSD8a6SGH_JtVSAxCpBrkTEtu-rgtW99ArvY9oyfWqB2zGMMot6hl2FrPorAtqjfraqYZ3T_shqRq-sYP2elpYOkFKdvuzVullMtdFOQVfByl5D-1X3rb6n8aKXumZysvtdg2mP4otSJd2vFZbBxgRLRE_sA0PKYteH4N4wG1zVq7MlNw98l7IQx7XsOZbgR2BWjoInnsIxgECIc-uOeIDYuOkgxXvxN9AepwghD0AswgQP4Ie0gF3WHEsmgZs07xcAM-sX3NDkoxI1YI5shFicVogzTqi81U3-DngTlq9f1B_gTwvkYRYHCQIzhp03qwd8Vxt9vda9Z9hhcLonHwO_UfEZiJP_ebzcmzh2H2IA79LbTaPaHko_8Y9rzzaRzQTenq2e7Hu3wVd1kGTyxmv7qApfZWhyfmCbflKe5Nn7U2v2xu8692b-CEBA4wuQzY3Jhiw8C1is2Z94rJJ5nhw97sk0eorPFqQrRN3iHJSPg0zOuRBXXeHS6YU-KPTnmQnQZUX5CT8d5l_-rLA3cRmn-8evn781x93Thedkwc3i8yVNJZL62VGbB5jeXpZmRtbv9NkeeeIULg17LSwFiS242GudeM8ZkzojI9117UJtcD-wpqfTCCavDmBinG4xg78z8Pdlwdiae73dX6xFV23S0T5hO_L3cP8mrvLiM3T4G1UO95oLB5tNKsH2XALTkdInxd2FYvffVf9fvBCGaraMhoCEvYTmnC5pt8TidJn1leOoIdm50Q4QKFnnOOO8nArI1nqVjaWRf-_wQr2_AEYTgP75ejpm6XT_BDGLbWxohd_Q3s8SDQH9HB9gFQ7ByFb3omW2P0GRqP8hhscmwbZrLlc4QSy1mpYrR3doU9w09fLgPUwIr-0AB0c0ayu3alNgU0qm0UHYHjaK5Svg7pXItw74ptl7PmSWL0TeDF2ic9vgq4Ay_SYUP_XCPaO6GRZ8lqzX4NO12GHUR-W5HeDnT8PpxYXxxLIvZh9PIwPjZJb0NYPBuFwLDRBh_4GLzyctEJDY7v96bToeCApzKhr2nS8cSeRfnQJDjp0SlPyYbCEm5ePesJ53Qk3Mc3WQJZCO1k4pfiTtDOyhkupLKnhKr7-dF_2-sHmrYn7-8w0v7iHOIBD9p1ywFKfuU-YLSveUhLYRXtpWXm16WXnrfFLnW95ITGJvzevSbiY15AreVZDEo8nu3xMh_CAxjlQSZ4g2Ctb8Pw5IL_e1Y4r1PN9IWPXADrxUTnNpCx9BqBPtdXS-PsAXb0NoKsfGDdHYOa-KuYW9Om0pnWHvucoqIFI2IImGrbCCIvdmMO3vX-m7I81lsKQHrj0IPy9HhOhUCrpO8DLHhPV-q-nnAQE_Z9rLv_9svaf7C9p-qZR-l3BwbLq-aQvLjsm9grF2TOK0-fRJmUvYwHzRTV92s28EQveo5X9lXXxB7HrvSbyXz2K_2rI_emC_atB-r0nXRpXr4SiN_eOb9yJ_2DgBQa-azvk2o94tNBTz5hUyZVWN6m8C5P8--Q2P6M1uvP8dE4u_VYev9E9Yet1s_Lqki65Tvfk5BUNyq8b_5TYFvSJ7Xn-o6azqyYVAaSm0-kxlml1Dmof_vj0r8XX_7qbP_z7s48NBq0Ibx7sCn_8WPg2vPD7o_QkJQ1g4h9WnqPydyuPalXpaYLwJE7COwu84f6xE8_De-CjQQdNw3ugo0U4DgjvLPCxw7W3NEmDnjTwpYEuLS_8c_xw0aXdtLesrVjFb-A2KWLKqrRkyc36tkh4XDV5mQIAsCJly7qlvGraOi_LpqhuxC2NKUtoQpOMFkkyzVib1bxKSsjqpMh5lMbQc9FNu27bT5Ve3QhjBrgtMhonNx2voTPul5eUStgR9zCiNMoWN_oWeSb1sDJRGnfCWHOSYoXt3E82T-cdUbaIsg9n3_JnC_IfpbT_uWX4TYhQ8mbQ3e3a2o2Db3of0fuVsOuhnjaqj-g9aglvk41W_wONjei9s81E9N7Z_r8BAAD__6-t1b0">