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

    <tr>
        <th>Summary</th>
        <td>
            [LoopVectorize] Missed optimization: fail to recognize `memset` pattern after vectorization
        </td>
    </tr>

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

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

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

<pre>
    Alive2 proof: https://alive2.llvm.org/ce/z/yK_USj (No unrolling due to the slow verfication)

### Motivating example 

For the source IR (similar to what memset do):
```llvm
define i1 @src(i64 %0, ptr %vla) {
entry:
  br label %for.body

for.body: ; preds = %for.body, %entry
  %conv26 = phi i64 [ %conv, %for.body ], [ 0, %entry ]
  %i.025 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  %arrayidx = getelementptr i8, ptr %vla, i64 %conv26
  store i8 0, ptr %arrayidx, align 1
  %inc = add i32 %i.025, 1
  %conv = zext i32 %inc to i64
  %cmp = icmp ugt i64 %0, %conv
  br i1 %cmp, label %for.body, label %for.end

for.end: ; preds = %for.body
  ret i1 false
}
```

With `opt -O3`, we vectorize it to https://godbolt.org/z/6d5cxeh8K:
```llvm
define noundef i1 @src(i64 %0, ptr nocapture writeonly %vla) local_unnamed_addr #0 {
entry:
  %umax1 = tail call i64 @llvm.umax.i64(i64 %0, i64 1)
 %min.iters.check = icmp ult i64 %0, 12
  br i1 %min.iters.check, label %for.body.preheader, label %vector.scevcheck

vector.scevcheck: ; preds = %entry
  %1 = add i64 %0, -1
  %2 = trunc i64 %1 to i32
  %3 = icmp eq i32 %2, -1
  %4 = icmp ugt i64 %1, 4294967295
  %5 = or i1 %3, %4
  br i1 %5, label %for.body.preheader, label %vector.ph

vector.ph:                                        ; preds = %vector.scevcheck
  %n.vec = and i64 %umax1, 8589934588
 %ind.end = trunc i64 %n.vec to i32
  br label %vector.body

vector.body:                                      ; preds = %vector.body, %vector.ph
  %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
  %6 = getelementptr i8, ptr %vla, i64 %index
  store <4 x i8> zeroinitializer, ptr %6, align 1
  %index.next = add nuw i64 %index, 4
  %7 = icmp eq i64 %index.next, %n.vec
  br i1 %7, label %middle.block, label %vector.body, !llvm.loop !0

middle.block:                                     ; preds = %vector.body
  %cmp.n = icmp eq i64 %umax1, %n.vec
  br i1 %cmp.n, label %for.end, label %for.body.preheader

for.body.preheader: ; preds = %vector.scevcheck, %entry, %middle.block
 %conv26.ph = phi i64 [ 0, %vector.scevcheck ], [ 0, %entry ], [ %n.vec, %middle.block ]
  %i.025.ph = phi i32 [ 0, %vector.scevcheck ], [ 0, %entry ], [ %ind.end, %middle.block ]
  br label %for.body

for.body:                                         ; preds = %for.body.preheader, %for.body
  %conv26 = phi i64 [ %conv, %for.body ], [ %conv26.ph, %for.body.preheader ]
  %i.025 = phi i32 [ %inc, %for.body ], [ %i.025.ph, %for.body.preheader ]
  %arrayidx = getelementptr i8, ptr %vla, i64 %conv26
  store i8 0, ptr %arrayidx, align 1
  %inc = add i32 %i.025, 1
  %conv = zext i32 %inc to i64
  %cmp = icmp ult i64 %conv, %0
  br i1 %cmp, label %for.body, label %for.end, !llvm.loop !3

for.end:                                          ; preds = %for.body, %middle.block
  ret i1 false
}
```

The `vector.body` loop is obviously equivalent to `@llvm.memset.p0.i64(ptr align 1 %vla, i8 0, i64 %n.vec, i1 false)`.
It seems to be a phase-ordering problem since LoopIdiomRecoginze goes before LoopVectorize.

### Real-world motivation

This snippet of IR is derived from [jemalloc/src/background_thread.c@background_threads_enable](https://github.com/jemalloc/jemalloc/blob/373884ab482ad1de4b839e40bd38fd154f324707/src/background_thread.c#L576) (after O3 pipeline).
The example above is a reduced from a big real ir. If you're interested in the original suboptimal IR and optimal IR, please email me.

**Let me know if you can confirm that it's an optimization opportunity, thanks.**
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzcWEuP27oO_jXKhhjDlp9ZZDGPG6A4PfcAvc_dQLbpWK0s-Uhy5vHrLyQ7iZ1kptP2rk4RdGyJIkXy-yjKzBi-k4gbkt6R9GHFBtsqvfnvffuyKlX9srkVfI8Ueq1UQ-JbaK3tDYlvCd0SumV-NhBi3wVK7wjdVkjo9pXQ7ctvj__6x1cgtPi7gkFqJQSXO6gHBKvAtghGqCfYo254xSxXktA1CR9IeDv9T-PxB78ry_fMuuX4zLpeIMwFt0qP-tSgK4RPX5xRwzsumHa2nlpmocPOoIVaOSvxwUQWjj_nwDhUY8MlAo-AJKHRFaEFzxIgNA0JvYfeave8F4zQNZD8blyF0uqXo1qAUoNgJQon2ygduFDOt3wci2-BxHfQa6wNkPhhsYDeu9dR96SY0LRSck8zL9y3HPzu0rvDzLTooANI-uCH0jsI5wr9xEkpD0KannTG9KCTy-onVTKt2Quvn73WHVoU2KG0LoK8OI_lPUxRHr07qDFWaQRewDz4B8VuiAm-kxDNPZGVt8jqevRjcs5JR2dh9IKv-GyPkrJyiOFZMpfsei_I3cOwszAHxCHsp8Q76PhFbvoSBeeDKOtzZLihd4ExGdNonbWGCYOTjvzhDNlz3f_htgWShaq3cPNH7GbpPTwh7LGySvNXBG6d_0uS71RdKmEngjtuZ3VaPWNb_PYBJkk1yBqbdxklVcV6O2iEJ80tKileZiwTqmLicZCSdVg_srp2KIjDt9lHaDp07DnycbOMC6iYEGPaEr_DwM0HLs3Lzbjn6FiH3HDHZcAtahNULVbfZkAQSyBE9AIDZ2uv4iHoNbbIatSL6TEjgalwP66dpfFi7hpWzqtGdCLFbNM3c0bQMV56kNVBKPJsiOlMKj6FAP888IZeKEuuUiZycgldJ-ssp-t0Jj8WH3UIXTxxK7kIavoTYezbK_HrWxe4D_67iO_1BHlXZLDHqQbJY7g9IN3eirRYr-MkLYoTyLisHekv4z-qWuZgfrZMuzg_XubDH_XxLQ9nJ9FZNKdyW-PzxWEUnq-YHxqHVYHEZ7sUPJ4vJwPZj50fXvPy-CDxfQLPblH8N3hFrbjkljPBX0e0THqyt86Tw1aPDJLD09KcA_VsSb6kyExy7rLP7QW88wV-O17XAoNSqLPycZGcyJc1oVTvXhZlf6Hkg3B4Fw2LozGQ17w9wv1NR_3Sq6fhd_h9pY2azV6rhRdcnTdW4_MiRkdejs2Ih-_7AD-qfr85OhFgjMml7Wtt2cL-1Jn9qv2p4nxnBz_Sxv50Jb1ewq-0O7_S-86TeSZ2svv_6Ylnafuopb9oq3zqkGbZCX-tVb5S7OI3-udfh-TbxeGHe-9_tuha73kZzULwLnADqtxzNRjxAvjnwPdMoPSNuFMydazjBTbow6ltdRmeUjqHxpT_ef_g3w9bpWuShcG4p08WDGJnnKUSgUHfMoM3Steo3WW716oU2IHhskL4rFT_qeaq-4KV2nH5irBTaKDExiHPTf_7cI8Irl_kvyATN09Kixq66U6v5DJK3ICRvO_RgmrcXZ4bcNvZYw2NVp2j2FfsmBCqInTr7xPbklXfdtpdNB5tq5HVQUWS8GLUPKJkpUBP1uLsksNtO5RBpTpCtzMDs8dSqJLQbZzHRZGwMikoq6Mak7KI15iEZR0XTR2lSRPTJA_zd3dH489pnvlvCLRgjUUNf8TQ8x4Fly5LwQk2h28erFR7dPFgoLEeqkNEGJR8BxqZAK4D-NTAixoIzV05kBY1Gos1cOk_kijNd1wyAWYoVW95x4SLsutUT6--gghkBgE7d3_qzjPqfp_RQofwTaon4N4oVExCpWTDdQe2ZRa4JTQ3wOSonb_6lIPqe6XtILn1HLMtk99MMKpd1Zu4XsdrtsJNlIfrJI-KbL1qN01TxmmdFVmTVmUSJVVVR2kT04jFYVStsxXf0JAmYRzGURzlyTrIsiovsMgxb8oiTpEkoffn-MFqxY0ZcFPEOU1WvtYY_yWMUolP4CcJpSR9WOmNW3NTDjvjGMmNNSctllvhP6EtSEDSB_idG4P1wnlXmhoXVKtAOypJd_EmWTgy3JWFnlmLWsIIjMPt3K9eDVps3oGuv3-Pf256rb5iZQndek8MoVvv6f8CAAD__zVRvXg">